Abstract: In the spectral clustering algorithm,the construction of similarity graph is very important,which has a great impact on the clustering results and operation efficiency of algorithm.In order to speed up the operation of spectral clustering and improve the performance by nearest neighbor truncation,K nearest neighbor(KNN) method is usually used to construct the sparse similarity graph.But the K nearest neighbor graph is very sensitive to outliers in the data,and the noise will seriously affect the clustering performance.This paper presented a new efficient sparse affinity graph construction method HCKNN.In this method,the K nearest neighbor search based on heap is more efficient than the nearest neighbor selection process based on sort by log(n),and the sparse similarity matrix reduction based on the neighborhood coexistence cumulative threshold can not only remove the noise to enhance the performance of clustering,but also accelerate the eigenvector decomposition in spectral clustering.This paper proposed a new efficient method HCKNN for constructing sparse affinity graph based on heap and the information of two points in the same neighborhood,which can not only choose the neighbors more efficiently,but also can accelerate the spectral clustering because of the sparse matrix.

Key words: Spectral clustering,Similarity graph,Heap,Sparse k nearest neighborhood