Big-Data Clustering: K-Means or K-Indicators?

Feiyu Chen, Yuchen Yang, Liwei Xu, Taiping Zhang, Yin ZhangarXiv 2019 · arXiv

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.

  1. 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$.
  2. 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).
The KindAP algorithm alternates projections between the relaxed indicator space $\mathcal{N}$ and the data subspace $\mathcal{U}$ to find the optimal indicator matrix.
  1. 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.

Clustering Accuracy and Running Time comparison: KindAP maintains high accuracy and superior speed as the number of clusters $k$ increases, whereas Lloyd's algorithm (K-means) degrades.

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

BibTeX
@misc{chen2019big,
  author = {Feiyu Chen and Yuchen Yang and Liwei Xu and Taiping Zhang and Yin Zhang},
  title = {{Big-Data Clustering: K-Means or K-Indicators?}},
  year = {2019},
  eprint = {1906.00938},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1906.00938},
}
Figure