Theory And Approach Of Particle Swarm Optimization For Clustering Problem

Clustering is widely used in information retrieval, satellite remote sensing, financial instrument, data transmission and other fields. Due to the advantages, such as not depending on the specific issues of the problem, and being able to find the optimal or suboptimal solutions of the problem quickly, parcticle swarm optimization(PSO) based on the global search mechanism has been applied to clustering problems. Analyzing some defects in the study of PSO-based clustering algorithms, focusing on static data clustering problem that the number of clusters is unknown, and streaming data clustering problem, this thesis studies their PSO theories and approaches.(1) Considering static data clustering problem that the number of clusters is unknown, an effective mutil-objective PSO is presented. First, aiming at the shortcomings of the existing multi-objective PSO algorithms, this thesis puts forward a multi-objective quantum PSO algorithm. In this algorithm, a quantum update strategy based on adaptive disturbance is proposed to update the particle position; by combing the selection strategy based on the Global Differential(GD) value ordering method, a new selecting method for the global best position of particle is designed. After that, the effectiveness of the proposed algorithm is verified by comparing with several typical algorithms on typical ZDTs’ and DTLZs’ functions.Then, applying the above proposed PSO-based algorithm to static data clustering problem that the number of clusters is unknown, an improved clustering algorithm based on multi-objective quantum PSO is proposed. In this algorithm, an effective integer encoding strategy is presented to deal with the case that the number of clusters is unknown; a new population initialization method is introduced by using the canopybased method to predict the number of clusters; and, an improved discrete quantum update formular is defined to update the particle position. Finally, the experimental results demonstrate the effectiveness of the proposed algorithm by optimizing several typical UCI test data sets.(2) Considering streaming data clustering problem, a streaming data clustering algorithm based on cooperative particle swarm optimization is proposed. First the algorithm divides sequential stream data into several data subset according to the time stamp. Then a cooperative multi-swarm PSO algorithm is used to tackle these data subset one by one. For any data subset, a high-dimensional clustering problem is first transformed into multiple low-dimensional sub-problems with only one class center. One sub-swarm optimizes one sub-clustering problem independently; all the subswarms cooperates with each other to find the whole solution of streaming data. Moreover, in order to enhance the speed of tracking the environment changes, a forecast strategy is designed to predict the change trend of class centers; in order to avoid multiple sub-swarms repeatedly searching for the same class center, a merging strategy of similar sub-swarms is proposed. Finally, by applied the proposed algorithm in multiple data sets, experimental results confirm its effectiveness.