title: Spectral embedded clustering: a framework for in-sample and out-of-sample spectral clustering.
abstract: Spectral clustering (SC) methods have been successfully applied to many real-world applications. The success of these SC methods is largely based on the manifold assumption, namely, that two nearby data points in the high-density region of a low-dimensional data manifold have the same cluster label. However, such an assumption might not always hold on high-dimensional data. When the data do not exhibit a clear low-dimensional manifold structure (e.g., high-dimensional and sparse data), the clustering performance of SC will be degraded and become even worse than  K -means clustering. In this paper, motivated by the observation that the true cluster assignment matrix for high-dimensional data can be always embedded in a linear space spanned by the data, we propose the spectral embedded clustering (SEC) framework, in which a linearity regularization is explicitly added into the objective function of SC methods. More importantly, the proposed SEC framework can naturally deal with out-of-sample data. We also present a new Laplacian matrix constructed from a local regression of each pattern and incorporate it into our SEC framework to capture both local and global discriminative information for clustering. Comprehensive experiments on eight real-world high-dimensional datasets demonstrate the effectiveness and advantages of our SEC framework over existing SC methods and  K-means-based clustering methods. Our SEC framework significantly outperforms SC using the Nyström algorithm on unseen data.
authors.affiliation: University of Texas, Arlington, TX 76019, USA. feipingnie@gmail.com
authors.forename: Feiping
authors.initials: F
authors.lastname: Nie
authors.forename: Zinan
authors.initials: Z
authors.lastname: Zeng
authors.forename: Ivor W
authors.initials: IW
authors.lastname: Tsang
authors.forename: Dong
authors.initials: D
authors.lastname: Xu
authors.forename: Changshui
authors.initials: C
authors.lastname: Zhang
mesh_terms: D000465:Algorithms; D001185:Artificial Intelligence; D016000:Cluster Analysis; D003627:Data Interpretation, Statistical; D016014:Linear Models; D010363:Pattern Recognition, Automated; D012044:Regression Analysis