Introduction: The "Big-K" Challenge
Clustering is a fundamental task in unsupervised learning, with the K-means (Lloyd’s) algorithm serving as the industry standard. However, K-means faces a significant scalability hurdle known as the "Big-K" problem. As the number of clusters ($K$) increases—a common scenario in modern big-data applications—K-means becomes highly sensitive to initialization and frequently converges to poor local minima. To achieve reliable results, practitioners often resort to thousands of random restarts, creating a massive computational bottleneck. This paper introduces the K-indicators model and the KindAP algorithm to provide a more stable, deterministic, and scalable alternative.
Methods: Subspace Matching and Alternating Projections
The authors reframe clustering as a subspace matching problem. Instead of searching for centroids, they seek an "indicator matrix" that aligns with the subspace spanned by the data.
- K-indicators Model: This model minimizes the distance between the data subspace and the space of indicator matrices. Unlike the non-convex K-means objective, the K-indicators objective is convex with respect to the indicator matrix $H$.
- KindAP (K-indicators by Alternating Projections): To solve the model, the authors employ a "semi-convex-relaxation." The algorithm alternates between projecting onto a convex set $\mathcal{N}$ (a relaxation of the indicator matrix) and a non-convex set $\mathcal{U}$ (representing the data's principal components).
- KindAP+L: This hybrid approach uses KindAP to "warm-start" K-means, combining KindAP's deterministic stability with K-means' local refinement capabilities.
Experimental Setup
The approach was evaluated across diverse benchmarks, including synthetic high-dimensional "data clouds," 35 real-world datasets (UCI, NLP, and image sets like YaleB and COIL100), and deep learning features extracted from pre-trained networks like Xception and VGG-16.
Key Insights
- Deterministic Stability: KindAP is essentially deterministic. In tests with 200 independent runs, it consistently achieved identical results, whereas K-means and Spectral Rotation (SR) exhibited high variance.
- Efficiency at Scale: On the AR face dataset ($K=120$), a single run of KindAP+L outperformed 10,000 random replications of K-means++.
- Confidence Metrics: KindAP produces "soft indicators." The ratio between the top two elements in a row of the result matrix serves as a built-in proxy for clustering confidence, allowing for uncertainty assessment without ground truth labels.
Key Results
KindAP demonstrates superior performance as the complexity of the clustering task increases. In synthetic tests, while K-means accuracy dropped significantly as the number of clusters $K$ grew from 10 to 150, KindAP maintained near-perfect accuracy.
On the AR dataset, KindAP+L reached 60.48% accuracy, surpassing the 58.33% achieved by K-means even after 10,000 runs. Furthermore, while a single KindAP iteration is slightly slower than a K-means iteration, it is orders of magnitude faster than the cumulative time K-means requires to reach comparable accuracy through multiple replications.
Limitations and Future Work
KindAP currently requires input data matrices to be orthogonal, a common constraint in spectral clustering but one that limits general-purpose use. Future research aims to optimize the semi-convex solver and establish a more rigorous theoretical foundation for the algorithm's consistent performance across various data distributions.
Summary updated