Ultra-Scalable Spectral Clustering and Ensemble Clustering

Abstract

This paper focuses on scalability and robustness of spectral clustering for extremely large-scale datasets with limited resources. Two novel algorithms are proposed, namely, ultra-scalable spectral clustering (U-SPEC) and ultra-scalable ensemble clustering (U-SENC). In U-SPEC, a hybrid representative selection strategy and a fast approximation method for K-nearest representatives are proposed for the construction of a sparse affinity sub-matrix. By interpreting the sparse sub-matrix as a bipartite graph, the transfer cut is then utilized to efficiently partition the graph and obtain the clustering result. In U-SENC, multiple U-SPEC clusterers are further integrated into an ensemble clustering framework to enhance the robustness of U-SPEC while maintaining high efficiency. Based on the ensemble generation via multiple U-SEPC's, a new bipartite graph is constructed between objects and base clusters and then efficiently partitioned to achieve the consensus clustering result. It is noteworthy that both U-SPEC and U-SENC have nearly linear time and space complexity, and are capable of robustly and efficiently partitioning ten-million-level nonlinearly-separable datasets on a PC with 64GB memory. Experiments on various large-scale datasets have demonstrated the scalability and robustness of our algorithms. The MATLAB code and experimental data are available at https://www.researchgate.net/publication/330760669.

arXiv commentTo appear in IEEE Transactions on Knowledge and Data Engineering, 2019

References in corpus (4)

• Locally Weighted Ensemble Clustering
• Enhanced Ensemble Clustering via Fast Propagation of Cluster-wise Similarities
• Robust Ensemble Clustering Using Probability Trajectories
• Combining Multiple Clusterings via Crowd Agreement Estimation and Multi-Granularity Link Analysis

Cited by in corpus (12)

• Fast Multi-view Clustering via Ensembles: Towards Scalability, Superiority, and Simplicity
• Efficient Multi-view Clustering via Unified and Discrete Bipartite Graph Learning
• Seeking Commonness and Inconsistencies: A Jointly Smoothed Approach to Multi-view Subspace Clustering
• Toward Multidiversified Ensemble Clustering of High-Dimensional Data: From Subspaces to Metrics and Beyond
• Spatial-Spectral Clustering with Anchor Graph for Hyperspectral Image
• Divide-and-conquer based Large-Scale Spectral Clustering
• LSEC: Large-scale spectral ensemble clustering
• Neural Normalized Cut: A Differential and Generalizable Approach for Spectral Clustering
• Which is which? Identification of the two compact objects in gravitational-wave binaries
• Scattering Transform Based Image Clustering using Projection onto Orthogonal Complement
• Beyond Linear Subspace Clustering: A Comparative Study of Nonlinear Manifold Clustering Algorithms
• Convex Programming Based Spectral Clustering