Back to Search
Start Over
Ultra-Scalable Spectral Clustering and Ensemble Clustering.
- Source :
-
IEEE Transactions on Knowledge & Data Engineering . Jun2020, Vol. 32 Issue 6, p1212-1226. 15p. - Publication Year :
- 2020
-
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$ 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 10-million-level nonlinearly-separable datasets on a PC with 64 GB 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. [ABSTRACT FROM AUTHOR]
- Subjects :
- *BIPARTITE graphs
*VECTOR spaces
*SPACETIME
*SCALABILITY
*SPARSE matrices
Subjects
Details
- Language :
- English
- ISSN :
- 10414347
- Volume :
- 32
- Issue :
- 6
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Knowledge & Data Engineering
- Publication Type :
- Academic Journal
- Accession number :
- 143000984
- Full Text :
- https://doi.org/10.1109/TKDE.2019.2903410