An Improved Spectral Clustering Algorithm Based on Local Neighbors in Kernel Space

Xinyue Liu1,2, Xing Yong2 and Hongfei Lin1

  1. School of Computer Science and Technology, Dalian University of Technology
    116024 Dalian, China
  2. School of Software, Dalian University of Technology
    116620 Dalian, China


Similarity matrix is critical to the performance of spectral clustering. Mercer kernels have become popular largely due to its successes in applying kernel methods such as kernel PCA. A novel spectral clustering method is proposed based on local neighborhood in kernel space (SC-LNK), which assumes that each data point can be linearly reconstructed from its neighbors. The SC-LNK algorithm tries to project the data to a feature space by the Mercer kernel, and then learn a sparse matrix using linear reconstruction as the similarity graph for spectral clustering. Experiments have been performed on synthetic and real world data sets and have shown that spectral clustering based on linear reconstruction in kernel space outperforms the conventional spectral clustering and the other two algorithms, especially in real world data sets.

Key words

Spectral Clustering, Kernel Space, Local Neighbors, Linear Reconstruction

Digital Object Identifier (DOI)

Publication information

Volume 8, Issue 4 (October 2011)
Cyber-Physical Networks and Software
Year of Publication: 2011
ISSN: 1820-0214 (Print) 2406-1018 (Online)
Publisher: ComSIS Consortium

Full text

DownloadAvailable in PDF
Portable Document Format

How to cite

Liu, X., Yong, X., Lin, H.: An Improved Spectral Clustering Algorithm Based on Local Neighbors in Kernel Space. Computer Science and Information Systems, Vol. 8, No. 4, 1143-1157. (2011),