Deflation-based power iteration clustering

Spectral clustering (SC) is currently one of the most popular clustering techniques because of its advantages over conventional approaches such as K-means and hierarchical clustering. However, SC requires the use of computing eigenvectors, making it time consuming. To overcome this limitation, Lin a...

Full description

Saved in:
Bibliographic Details
Published in:Applied intelligence (Dordrecht, Netherlands) Netherlands), 2013-09, Vol.39 (2), p.367-385
Main Authors: The, Anh Pham, Thang, Nguyen Duc, Vinh, La The, Lee, Young-Koo, Lee, Sungyoung
Format: Article
Language:English
Subjects:
Accuracy
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Artificial Intelligence
Clustering
Computer Science
Computer science
control theory
systems
Conferences
Data processing. List processing. Character string processing
Datasets
Eigenvectors
Exact sciences and technology
Intelligence
Iterative methods
Machine learning
Machines
Manufacturing
Mechanical Engineering
Memory organisation. Data processing
Orthogonality
Processes
Sampling techniques
Software
Spectra
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Spectral clustering (SC) is currently one of the most popular clustering techniques because of its advantages over conventional approaches such as K-means and hierarchical clustering. However, SC requires the use of computing eigenvectors, making it time consuming. To overcome this limitation, Lin and Cohen proposed the power iteration clustering (PIC) technique (Lin and Cohen in Proceedings of the 27th International Conference on Machine Learning, pp. 655–662, 2010 ), which is a simple and fast version of SC. Instead of finding the eigenvectors, PIC finds only one pseudo-eigenvector, which is a linear combination of the eigenvectors in linear time. However, in certain critical situations, using only one pseudo-eigenvector is not enough for clustering because of the inter-class collision problem. In this paper, we propose a novel method based on the deflation technique to compute multiple orthogonal pseudo-eigenvectors (orthogonality is used to avoid redundancy). Our method is more accurate than PIC but has the same computational complexity. Experiments on synthetic and real datasets demonstrate the improvement of our approach.
ISSN:0924-669X
1573-7497
DOI:10.1007/s10489-012-0418-0