DocumentCode :
18369
Title :
Discriminative Nonnegative Spectral Clustering with Out-of-Sample Extension
Author :
Yang Yang ; Yi Yang ; Heng Tao Shen ; Yanchun Zhang ; Xiaoyong Du ; Xiaofang Zhou
Author_Institution :
Sch. of Inf. Technol. & Electr. Eng., Univ. of Queensland, Brisbane, QLD, Australia
Volume :
25
Issue :
8
fYear :
2013
fDate :
Aug. 2013
Firstpage :
1760
Lastpage :
1771
Abstract :
Data clustering is one of the fundamental research problems in data mining and machine learning. Most of the existing clustering methods, for example, normalized cut and (k)-means, have been suffering from the fact that their optimization processes normally lead to an NP-hard problem due to the discretization of the elements in the cluster indicator matrix. A practical way to cope with this problem is to relax this constraint to allow the elements to be continuous values. The eigenvalue decomposition can be applied to generate a continuous solution, which has to be further discretized. However, the continuous solution is probably mixing-signed. This result may cause it deviate severely from the true solution, which should be naturally nonnegative. In this paper, we propose a novel clustering algorithm, i.e., discriminative nonnegative spectral clustering, to explicitly impose an additional nonnegative constraint on the cluster indicator matrix to seek for a more interpretable solution. Moreover, we show an effective regularization term which is able to not only provide more useful discriminative information but also learn a mapping function to predict cluster labels for the out-of-sample test data. Extensive experiments on various data sets illustrate the superiority of our proposal compared to the state-of-the-art clustering algorithms.
Keywords :
data mining; eigenvalues and eigenfunctions; learning (artificial intelligence); matrix algebra; pattern clustering; NP-hard problem; cluster indicator matrix; data clustering; data mining; discriminative nonnegative spectral clustering; effective regularization term; eigenvalue decomposition; machine learning; optimization processes; out-of-sample extension; Clustering algorithms; Educational institutions; Eigenvalues and eigenfunctions; Integrated circuits; Kernel; Laplace equations; Optimization; Nonnegative spectral clustering; discriminative regularization; out-of-sample;
fLanguage :
English
Journal_Title :
Knowledge and Data Engineering, IEEE Transactions on
Publisher :
ieee
ISSN :
1041-4347
Type :
jour
DOI :
10.1109/TKDE.2012.118
Filename :
6216379
Link To Document :
بازگشت