Research Of Spectral Clustering

Clustering analysis is the classic problem in machine learning. Clustering can be divided into unsupervised clustering and semi-supervised clustering. Unsupervised clustering extracts potential structure of data, groups the similar data into the same cluster without any prior and assumption information. In the existing unsupervised clustering algorithms, k-means clustering is the popular and simple clustering algorithm. K-means clustering has a good performance in the spherical distribution data. But k-means clustering tends to failure in the non-context data. And k-means clustering uses iterative optimization method to find optimal solution, thus can’t guarantee converge to the global optimal solution.Spectral clustering is an unsupervised clustering algorithm appearing recently. Spectral clustering overcomes the shortcoming of k-means clustering. Spectral clustering can recognize non-convex distribution clustering, is suitable to practical problems. Spectral clustering shouldn’t get local optimal solution, and can avoid singular problem caused by the extra dimension of data. In this paper, we do two aspects research based on spectral clustering algorithm.1. we propose a clustering algorithm hierarchical spectral clustering (HSC). The proposed HSC algorithm absorbs higher clustering accuracy of hierarchical clustering and avoids skewed divisions because of using spectral clustering. Experimental results show that the proposed hierarchical spectral clustering is superior to spectral clustering or hierarchical clustering on cluster quality and is superior to hierarchical clustering on computational speed.2. we propose a spectral clustering based on affinity propagation. This clustering algorithm use the dimension reduction characteristics of spectral clustering to obtain the distribution of data in the mapping space, then do affinity propagation clustering on samples in mapping space. This method provide dimension and tightened input for affinity propagation clustering through spectral mapping. And affinity propagation algorithm can fast coverage to global optimization solution and not sensitive to the initiation. The clustering results based on MPEG-7database and the subset show the good performance of the spectral clustering based on affinity propagation.