Adaptive Spectral Clustering Based On Evolutionary Algorithms

Spectral clustering algorithms as a subroutine of clustering have been playing an important role in solving many problems in pattern recognition and image processing. Morever spectral clustering has shown to be more effiective in finding clusters than many traditional algorithms such as k-means in clustering data mining. With the application of spectral clusting.there are many difficulties we have to face,such as how to decide cluster number. In this paper,we foucs on the cluster number detecting. Our main contributions are as follows:(1) With the consideration of validity measure, we propose a modified spectral clustering method. The basic idea is to use anther clustering algorithm to replace the k-means in the last step of spectral clustering. In this paper,we adopt three most popular validity indices for the comparison study. And the results show that the cluster number detected by the intra-cluster consistency of Vxb index is most close to the real cluster number.(2) In the process of computing the validity index, we propose a self-adaptive method to determine the number of clusters. The basic idea is to convert the spectral clustering to an optimization problem, by considering validity index as the optimization objective. Utilizeing the flexibility of evolutionary encoding determiniming the cluster number is designed into specific encoding.By using evolutionary algorithms we can both get the most proper clustering and the cluster number.The PSO(Particle Swarm Optimization Algorithm) is used as the basic optimizer, and it is compared with another evolutionary algorithms by convergence and stability.Through the results from experiments, we show the advantages of the adaptive algorithm.(3) Based on the two the validity indices, we propose a multi-objective evolutionary algorithm to determine the number of cluster. Considering that the intra-cluster consistency and inter-cluster scatter are the most basic validity indices, and the conflict between them can not be solved easily, we take advantage the power of evolutionary algorithm, we take these two measure as the objective function of evolutionary algorithm, then we can balance these two index by getting optimal solution set--Pareto. In this paper we take NSGA-? as our multi-objective evolutionary algorithm to campare with the single-objective evolutionary algorithm through some experiments. And the results shows the superiority of the multi-objective evolutionary algorithm on spectral clustering in convergence and stability.