Research On Two Types Of Spectral Clustering Algorithms Based On Sparse Similarity Matrix

With the rapid development of data mining,the clustering problem of non-linear separable data has become one of the hot spots in cluster research.The clustering results of these problems by traditional methods,such as K-means algorithm,are usually not ideal.In 2001,Ng,Jordan and Weiss constructed the NJW spectral clustering algorithm combined with K-means algorithm.This algorithm can not only solve the clustering problem of nonlinear separable but also get the global optimal solution.For NJW spectral clustering algorithm it is necessary to determine the parameter ? at first.In 2004,the conclusion of that NJW spectral clustering algorithm depends greatly on the range of param-eter ? is obtained through experiments,and the self-tuning spectral clustering algorithm is put forward.Here,the parameter ? is obtained adaptively.Since then,it has become one of the research targets to reduce the dependence of the spectral clustering algorithm on the range of the parameter ? or to improve the selection of ?.For example,Luo Huaijing proposed the spectral clustering algo-rithm based on the k-shared nearest neighbor principle in 2012,Based on the sparse similarity matrix and the selection of different distances,a constant pa-rameter spectral clustering algorithm based on the sparse similarity matrix and a self-tuning spectral clustering algorithm based on the sparse similarity matrix are put forward in this paper.Unlike NJW spectral clustering algorithm,the constant parameter spectral clustering algorithm based on the sparse similarity matrix in this paper uses Mahalanobis distance to calculate the similarity between data points,obtains a sparse similarity matrix via the k-shared nearest neighbor principle and completes cluster by the K-means algorithm selected the initial cluster centers according to maximum distance.Experiments on data sets show that the algorithm proposed is less dependent on the range of the constant parameter ? compared with the NJW spectral clustering algorithm.Unlike the self-tuning spectral clustering algorithm and the self-tuning spec-tral clustering algorithm based on k-shared nearest neighbor principle,the self-tuning spectral clustering algorithm based on the sparse similarity matrix p-resented in this paper obtains the sparse similarity matrix based on k-shared nearest neighbor principle,and uses the different local structure features of the data set and Grassmann distance to compute the parameter ? adaptively.Ex-periments on the swiss-roll data set,double ring data set,half-moon data set and scatter data set show that the accuracy of the algorithm in this paper is higher.