Spectral Clustering Algorithm Based on Local Sparse Representation

摘要

Clustering based on sparse representation is an important technique in machine learning and data mining fields. However, it is time-consuming because it constructs l_1-graph by solving l_1-minimization with all other samples as dictionary for each sample. This paper is focused on improving the efficiency of clustering based on sparse representation. Specifically, the Spectral Clustering Algorithm Based on Local Sparse Representation (SCAL) is proposed. For a given sample the algorithm solves l_1-minimization with the local k nearest neighborhood as dictionary, constructs the similarity matrix by calculating sparsity induced similarity (SIS) of the sparse coefficients solution, and then uses spectral clustering with the similarity matrix to cluster the samples. Experiments using face recognition data sets ORL and Extended Yale B demonstrate that the proposed SCAL can get better clustering performance and less time consumption.