Discrete and Balanced Spectral Clustering With Scalability
- 5 September 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. 45 (12) , 14321-14336
Abstract
Spectral Clustering (SC) has been the main subject of intensive research due to its remarkable clustering performance. Despite its successes, most existing SC methods suffer from several critical issues. First, they typically involve two independent stages, i.e., learning the continuous relaxation matrix followed by the discretization of the cluster indicator matrix. This two-stage approach can result in suboptimal solutions that negatively impact the clustering performance. Second, these methods are hard to maintain the balance property of clusters inherent in many real-world data, which restricts their practical applicability. Finally, these methods are computationally expensive and hence unable to handle large-scale datasets. In light of these limitations, we present a novel Discrete and Balanced Spectral Clustering with Scalability (DBSC) model that integrates the learning the continuous relaxation matrix and the discrete cluster indicator matrix into a single step. Moreover, the proposed model also maintains the size of each cluster approximately equal, thereby achieving soft-balanced clustering. What's more, the DBSC model incorporates an anchor-based strategy to improve its scalability to large-scale datasets. The experimental results demonstrate that our proposed model outperforms existing methods in terms of both clustering performance and balance performance. Specifically, the clustering accuracy of DBSC on CMUPIE data achieved a 17.93% improvement compared with that of the SOTA methods (LABIN, EBSC, etc.).Keywords
Funding Information
- National Natural Science Foundation of China (62276212)
This publication has 61 references indexed in Scilit:
- Data clustering: 50 years beyond K-meansPattern Recognition Letters, 2010
- Community detection in graphsPhysics Reports, 2010
- Load balancing for clusters of VOD serversInformation Sciences, 2004
- Spectral grouping using the nystrom methodIEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- A modified version of the K-means algorithm with a distance based on cluster symmetryIEEE Transactions on Pattern Analysis and Machine Intelligence, 2001
- Normalized cuts and image segmentationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000
- Nonlinear Component Analysis as a Kernel Eigenvalue ProblemNeural Computation, 1998
- A simple min-cut algorithmJournal of the ACM, 1997
- Algorithm AS 136: A K-Means Clustering AlgorithmJournal of the Royal Statistical Society Series C: Applied Statistics, 1979
- The Hungarian method for the assignment problemNaval Research Logistics Quarterly, 1955