Research On Spectral Clustering Algorithm And Its Application

Spectral graph theory is the foundation of Spectral clustering algorithm,which can be used as a segmentation method for graph theory,because of its strong mathematical theory basis and broad applicability,the spectral clustering is the hot topic in the field of international pattern recognition currently.Spectral clustering data set can be changed from the original space conversion through the Gauss kernel function features,after the conversion the data in the original space will be linearly separable,in the obtained low dimensional linear space,the traditional clustering method such as k-means can be used.However,the cluster results of spectral clustering algorithm directly depends on the similarity function measure,in the existing spectral clustering algorithm,often using Gauss kernel function as the similarity measure function,but the measure methods have defects in the aspect of representing the spatial characteristics of data,which can not reflect the distribution characteristics of complex data space.Except the above,in the process of the implementation of the algorithm requires not only to store all the data in the similarity matrix resulting high time consumption,but also the space overhead of matrix eigenvalue decomposition is relatively high,the applicationis of large-scale data sets can not to obtain the promotion in the future.In view of the above problems,the research contents of this paper include the following aspects:Fist,to choose a new similarity measure method,we improved the manifold distance similarity which will be able to reflect the data the local and global properties in the complex space,and the robust method as a weighting parameter form the new similarity measure,The improved manifold distance measure can fully reflect the similarity of the multi-scale clustering data between pairs of points,for identify the various data sets have the applicability in broad sense.Then,based on the new similarity measure proposed a new spectral clustering.The algorithm can be used to void the Sensitive issues because of the Gauss Kernel function parameters,and the robustness of the parameter take full account of the neighborhood information effectively prevent noise data resulting error clustering and with good stability.Through with the Gauss kernel function,the common manifold distance similarity measurement comparison,the experimental results display that,the proposed algorithm has a better performance.Finally,improved the application of spectral clustering algorithm on large scale data set,this paper proposes the DBSCAN-based approximate algorithm which is based on the analysis of existing approximate measures and combined the thought of DBSCAN algorithm,proposed the approximate spectral clustering based on DBSCAN,The algorithm avoids the problem of noise sensitive points,and reduces the time complexity.Compared with other approximate algorithms,the algorithm can maintain higher clustering accuracy in most data sets.