2018 · 43 citations · 30 references
ComputingComputer ScienceData ScienceData MiningFeature EngineeringMachine LearningDimension ReductionDimensionality ReductionKernel MethodsMatrix ComputationMatrix FactorizationSpectral AnalysisAccuracy-computational Cost TradeoffClusteringEigenvectorsGraph SimilarityInformation Loss AnalysisSimilarity Graph ConstructionSparse Feature Representation
Spectral clustering is one of the most effective clustering approaches that capture hidden cluster structures in the data. However, it does not scale well to large-scale problems due to its quadratic complexity in constructing similarity graphs and computing subsequent eigendecomposition. Although a number of methods have been proposed to accelerate spectral clustering, most of them compromise considerable information loss in the original data for reducing computational bottlenecks. In this paper, we present a novel scalable spectral clustering method using Random Binning features (RB) to simultaneously accelerate both similarity graph construction and the eigendecomposition. Specifically, we implicitly approximate the graph similarity (kernel) matrix by the inner product of a large sparse feature matrix generated by RB. Then we introduce a state-of-the-art SVD solver to effectively compute eigenvectors of this large matrix for spectral clustering. Using these two building blocks, we reduce the computational cost from quadratic to linear in the number of data points while achieving similar accuracy. Our theoretical analysis shows that spectral clustering via RB converges faster to the exact spectral clustering than the standard Random Feature approximation. Extensive experiments on 8 benchmarks show that the proposed method either outperforms or matches the state-of-the-art methods in both accuracy and runtime. Moreover, our method exhibits linear scalability in both the number of data samples and the number of RB features.
30
Chih-Chung Chang, Chih‐Jen Lin · ACM Transactions on Intelligent Systems and Technology · 2011 · 41.3K citations
A tutorial on spectral clustering
Ulrike von Luxburg · Statistics and Computing · 2007 · 10.3K citations · Full text
On Spectral Clustering: Analysis and an algorithm
Andrew Y. Ng, Michael I. Jordan, Yair Weiss · 2001 · 7.8K citations