Spectral Clustering Based On The Graph Theory Algorithms Research And Implementation

The cluster analysis has very much wide range of applications in the information anddata mining and so on. It is an effective means that people know and explore the inner linkbetween thing and thing. At first, the clustering algorithm can find the valuable information inthe data of cluster, with the condition of no prior knowledge of data clustering. Spectralclustering algorithm as a new kind of clustering algorithm, it has obvious advantagescompared with the traditional k-means clustering algorithm. The spectral clustering algorithmmethod not only is not easy to fall into local optimal solution, but also has the recognition thatnot convex distribution of clustering ability and is able to cluster arbitrary shape of the sampleclustering. So that spectral clustering algorithm is very much suitable for many praticalapplication problems.Spectral clustering is a kind of clustering algorithm, based on similarity matrix and usedof the spectrum diagram theory in order to divide the similarity matrix. The traditionalspectral clustering algorithm at the beginning defines the data points of similaritymeasurement, and then based on this similarity measurement, structures the matrix W of thesimilarity all of data points and solves the Laplace matrix of L, the next step in order tocalculate the L of eigenvalues and eigenvectors, at last selects one or more feature vectorwhich can be clustered on the different data points. Because of the spectral clusteringalgorithm directly break up on the similarity matrix, it is big influence that different forms ofsimilar matrix to the spectral clustering algorithm. Therefore, it is important that the researchof similarity matrix for spectral clustering algorithm influence and the problem how toconstruct a suitable similarity matrix for spectral clustering. All of them are very muchimportant meaning for the spectral clustering algorithm research.This paper introduces the spectral clustering algorithm related theories and the methodsof spectral clustering. Not only illustrates the spectral clustering’s effect causes andadvantages, but also points out the traditional spectral clustering algorithm’s problem thateffect by similarity matrix. After this paper suggests the used of relevant theories andknowledge, the paper finally made two main jobs：At first, when structured the traditional spectral clustering algorithm, the last step usedthe k-means clustering algorithm in this paper. The purpose is to contrast spectral clusteringalgorithm and k-means clustering algorithm. Compared the last step operation used thek-means clustering algorithm structure of spectral clustering algorithm experimental resultswith the single k-means clustering algorithm experimental results, validation the results whether spectral clustering algorithm could reduce the initial and choice cluster centernumber affected the clustering algorithm’s results degree, not only could be conducted in thearbitrary shape and the sample space, but also spectral clustering is not easy to fall into localoptimal solution or not. Two algorithms codes realize on the matlab7.0. Through the based ongraph of the initial sample data set, contrasted analysis the experimental results both thek-means clustering algorithm and the traditional spectral clustering algorithm, whether byboth of them the experiment of results can prove spectral clustering algorithm better than thesingle and conventional k-means clustering algorithm in clustering accuracy and theclustering accuracy improved or not.Secondly, although there are already a variety of spectral clustering algorithm at present,but the only difference is handled different matrix, not only the relationship between both thematrix spectrum and characteristic vector and the clustering is not very clear, but also there isnot complete theory to describe and define spectral clustering method performances andanalysis spectral clustering limitations at now. Because the spectral clustering algorithmdirectly break up the similarity matrix, so, before introduce the spectral clustering, the paperfirstly introduced some existing similarity matrix construction methods. The methods includesimilar matrix produced by different distance formula, similar matrix produced by differentcharacteristics of types and similar matrix created by different characteristics integrationmethod. However, it is very big influence to the spectral clustering that different types formsimilar matrix. So it is very practicability to find a new method instead of similar matrix, fromthe point it maybe a new research point to spectral clustering. The paper puts forward adamping matrix which in order to reduce the similarity matrix to the influence of the spectralclustering algorithm instead of similar matrix. Why the method can obtain good results?Because the improved spectral clustering algorithm is not clustering analysis directly on thesimilarity matrix, but clustering analysis for damping matrix which is constructed by thedistance of damping. The distance of damping computed by based on Laplace matrix. Twoalgorithms codes realize on the matlab7.0. Through the based on graph of the initial sampledata set, contrasted analysis the experimental results both the improved spectral clusteringalgorithm and the traditional spectral clustering algorithm, whether by both of them theexperiment of results in most cases can prove the improved spectral clustering algorithmbetter than conventional spectral clustering algorithm in clustering accuracy and the clusteringaccuracy improved or not. Damping matrix is also further enrich the structure similaritymatrix theory.