Spectral embedded clustering: A framework for in-sample and out-of-sample spectral clustering

Nie, F; Zeng, Z; Tsang, IW; Xu, D; Zhang, C

Spectral embedded clustering: A framework for in-sample and out-of-sample spectral clustering

Nie, F Zeng, Z Tsang, IW

Xu, D

Zhang, C

Permalink

Publication Type:: Journal Article
Citation:: IEEE Transactions on Neural Networks, 2011, 22 (11), pp. 1796 - 1808
Issue Date:: 2011-11-01

Closed Access

	Filename	Description	Size
	2013004107OK.pdf		429.6 kB	Adobe PDF	View/Open

Copyright Clearance Process

Recently Added
In Progress
Closed Access

This item is closed access and not available.

Full metadata record

Field	Value	Language
dc.contributor.author	Nie, F	en_US
dc.contributor.author	Zeng, Z	en_US
dc.contributor.author	Tsang, IW https://orcid.org/0000-0001-8095-4637	en_US
dc.contributor.author	Xu, D https://orcid.org/0000-0003-2775-9730	en_US
dc.contributor.author	Zhang, C	en_US
dc.date.issued	2011-11-01	en_US
dc.identifier.citation	IEEE Transactions on Neural Networks, 2011, 22 (11), pp. 1796 - 1808	en_US
dc.identifier.issn	1045-9227	en_US
dc.identifier.uri	http://hdl.handle.net/10453/29713
dc.description.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 Nystrm algorithm on unseen data. © 2011 IEEE.	en_US
dc.relation.ispartof	IEEE Transactions on Neural Networks	en_US
dc.relation.isbasedon	10.1109/TNN.2011.2162000	en_US
dc.subject.classification	Artificial Intelligence & Image Processing	en_US
dc.subject.mesh	Cluster Analysis	en_US
dc.subject.mesh	Data Interpretation, Statistical	en_US
dc.subject.mesh	Linear Models	en_US
dc.subject.mesh	Regression Analysis	en_US
dc.subject.mesh	Algorithms	en_US
dc.subject.mesh	Artificial Intelligence	en_US
dc.subject.mesh	Pattern Recognition, Automated	en_US
dc.title	Spectral embedded clustering: A framework for in-sample and out-of-sample spectral clustering	en_US
dc.type	Journal Article
utslib.citation.volume	11	en_US
utslib.citation.volume	22	en_US
utslib.for	0801 Artificial Intelligence and Image Processing	en_US
pubs.embargo.period	Not known	en_US
pubs.organisational-group	/University of Technology Sydney
pubs.organisational-group	/University of Technology Sydney/Faculty of Engineering and Information Technology
pubs.organisational-group	/University of Technology Sydney/Strength - CAI - Centre for Artificial Intelligence
utslib.copyright.status	closed_access
pubs.issue	11	en_US
pubs.publication-status	Published	en_US
pubs.volume	22	en_US

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 Nystrm algorithm on unseen data. © 2011 IEEE.

Please use this identifier to cite or link to this item:

http://hdl.handle.net/10453/29713