Research On Spectral Clustering Algorithm Based On KD Landmarks

The spectral clustering algorithm based on landmarks reduces the computational complexity of the spectral clustering algorithm and avoids the application limitations of traditional spectral clustering algorithms.However,clustering accuracy and Normalized Mutual Information are used to measure cluster validity.The clustering algorithm based on landmarks is less efficient.How to balance cluster validity and clustering time becomes a difficult problem for spectral clustering algorithms based on landmarks.Aiming at this problem,a spectral clustering algorithm based on KD landmarks points is proposed.Firstly,a KD landmarks selection method is proposed.This method uses a hyperplane to divide the sample space into unequalities into p sub-blocks.The hyperplane is perpendicular to the first i dimension with the largest variance in the sample space,and the data in each sub-block after division.The number of points is basically equal,the average value of the data points in each sub-block is calculated as the center point,and the set of the center points is the selected landmark;Then,based on the KD landmarkers,a similarity matrix between the landmarkers and sample points is calculated by using a neighboring point effective allocation method,and the result is extended to the sample point to construct a similarity diagram;Finally,the singular value decomposition is used to replace the traditional feature decomposition process to speed up the algorithm,and k-means is performed on the right singular vector.Clustering results in the final result,which improves the clustering effectiveness.In the simulation experiment,four large data sets of different sizes,such as MNIST,Seismic,LetterRec and USPS,are used to compare the algorithm with classical spectral clustering algorithm and four representative spectral clustering algorithms based on landmarks.The algorithm is superior to the existing marker-based spectral clustering algorithm in clustering validity and clustering time.It balances clustering validity and clustering time when dealing with large-scale data.There are 23 figures,7 tables,and 51 references in this thesis.