The Study And Application Of Quantum-Inspired Multiobjective Evolutionary Clustering Algorithm

Data mining is a process from which we can get hidden, unknown but useful information and knowledge from a lot of incomplete, noisy, fuzzy and random data. At the same time we get the time trend and relevance, so we can provide decision support to user to solve problem. When people use data mining instruments to identify the model and relationship between data, the first step should be done is clustering. So clustering arouses more and more attention as one of the main data mining methods. A large number of clustering algorithms have been proposed so far, but they are designed only for special problems and users with imperfection theories and methods. With the development of bigger and bigger data scale but insufficient of priori knowledge, how to interpret large-scale data in higher space become a challenge problem. The paper combines the framework of multiobjective evolutionary computing with quantum computing theory, using optimized method to solve clustering problem, and an optimization method named Quantum-Inspired Multiobjective Evolutionary Clustering Algorithm is proposed. The algorithm is successfully used to artificial data clustering, UCI data clustering, texture image segmentation and remote sensing image segmentation. The main contribution can be listed as follows:1) A new quantum-inspired multiobjective evolutionary clustering method is proposed to overcome the drawbacks of traditional clustering methods, which only use one objective function to optimize and the obtained result is only good for one kind of data but have bad results for other data with different distributions. The algorithm is constructed in the framework of multiobjective optimization, and two complementary objective functions are used. The individuals in a population are represented by quantum bits based on the efficient parallelism and the composition of quantum. Non-dominated sort and quantum rotation gate strategy are used to update population. At last we use a kind of semi-supervised method to select one preferred solution as the optimal solution from the set of Pareto solutions. The experiments show that the algorithm has good population diversity and global search ability. Applied to a lot of artificial data and UCI data, it can get more precise correct clustering rate.2) A new image segmentation algorithm based on quantum-inspired multiobjective evolutionary clustering algorithm is proposed. First, using feature extraction method to obtain texture characters and use watershed algorithm to segment image into small regions which can get the information of the edge and reduce computing complexity. Then, we use quantum encoding to obtain quantum population and use two complementary objective functions to evaluate the clustering performance. During evolution process, non-dominated sort and quantum rotation gate strategy are used. We decode all the Pareto solution to obtain the clustering number and class labels, and select one preferred solution as the optimal solution, output the class label as grey value, so it is the image segmentation result. The experimental results show that the algorithm can resolve the drawbacks of existing clustering segmentation algorithms which have sole evaluate index and bad details maintaining performance.The segmentation precision has been improved.3) An improved quantum-inspired multiobjective evolutionary clustering algorithm is proposed. To solve the weaknness of the nomal quantum-inspired evolutionary algorithm which need to set the rotation angle in advance, we propose a new method, which can find the rotation step and direction self-adaption, to guide the population evolve to the optimal clustering center, and the algorithm accelerate the convergence speed. The compared experiments show that the improved algorithm has better clustering performance than the primary algorithm.This research is supported by the National High Technology Research and Development Program (863Program) of China (Grant No.2009AA12Z210), the Key Scientific and Technological Innovation Special Projects of Shaanxi "13115",(No.2008ZDKG-37), the National Natural Science Foundation of China(Grant No.60703107and60703108),the Natural Science Basic Research Plan in Shanxi Province of China(Grant No.2007F32), the China Postdoctoral Science Foundation Special funded project (No.200801426), the China Postdoctoral Science Foundation funded project (No.20080431228) and the Fundamental Research Funds for the Central Universities (No.JY10000902040).