t-k-means: A ROBUST AND STABLE k-means VARIANT

Yiming Li, Yang Zhang, Qingtao Tang, Weipéng Huáng, Yong Jiang, Shu-Tao XiaICASSP 2021 · DOI

TL;DR

This paper introduces "t-k-means," a novel variant of the classic k-means clustering algorithm designed to be more robust to outliers and more stable in its results. By drawing inspiration from the t-mixture model (which handles heavy-tailed data better than Gaussian distributions), t-k-means offers improved performance on datasets with noise, while a "fast" version maintains computational efficiency comparable to standard k-means.

What Problem Does This Paper Address?

Clustering is a fundamental task in data analysis, and the k-means algorithm is a popular choice due to its simplicity and speed. However, standard k-means relies on assumptions that are violated by real-world data, particularly its sensitivity to outliers and its tendency to produce results with high variance (instability). This is because k-means is closely related to Gaussian Mixture Models (GMMs), which assume data follows a Gaussian distribution – a distribution with "thin tails" that doesn't adequately account for extreme values or noise. Consequently, k-means can struggle with datasets containing outliers or heavy-tailed distributions, leading to less reliable clustering outcomes.

Methods

The core innovation is the t-k-means algorithm, derived from the t-mixture model (TMM). TMM is a generalization of GMM that uses the heavy-tailed Student's t-distribution, making it inherently more robust to outliers. The authors adapt the Expectation-Maximization (EM) algorithm, typically used for GMMs, to work with TMM.

Key aspects of their approach include:

  • Theoretical Derivation: They derive t-k-means by assuming data is sampled from a TMM and then optimizing a loss function and clustering center update rule that incorporates the properties of the t-distribution.
  • Robustness and Stability Analysis: The paper provides theoretical analysis of why t-k-means is more robust (due to the heavy-tailed nature of the t-distribution in its objective function) and more stable (due to cluster center updates considering global information, unlike standard k-means).
  • Fast t-k-means: To address potential computational overhead of TMM, they propose a "fast" version by fixing certain parameters and letting others approach limits, achieving efficiency comparable to standard k-means.

Datasets

The authors evaluated their methods on:

  • Synthetic Datasets: Including datasets with varying cluster shapes and sizes (A1-A3, S1-S4), unbalanced clusters, and different dimensionality (dim32, dim64). These are standard benchmarks for evaluating clustering algorithms.
  • Real-World Datasets: Four unlabeled datasets were used: Iris, Bezdekiris, Seed, and Wine.

Key Insights and Ideas

  • Heavy Tails Matter: The fundamental insight is that the choice of distribution underlying a clustering algorithm significantly impacts its robustness. The heavy-tailed t-distribution is a natural fit for data with outliers, unlike the Gaussian distribution.
  • Stability from Global Information: The improved stability of t-k-means stems from its cluster center update mechanism, which, unlike standard k-means, considers information from all samples, not just those within a specific cluster. This makes the algorithm less susceptible to the initial random seeding of cluster centers.
  • Efficiency is Achievable: The development of "fast t-k-means" demonstrates that robustness and stability can be achieved without sacrificing computational efficiency, making the method practical for larger datasets.

Key Results

  • Superior Performance on Synthetic Data: t-k-means and its fast variants consistently outperformed standard k-means, k-means++, k-medoids, k-medians, GMM, and TMM on various synthetic datasets, as measured by Adjusted Rand Index (ARI). The "fast t-k-means++" (initialized with k-means++) achieved the best results on all synthetic datasets.
  • Improved Performance on Real-World Data: On real-world datasets (measured by MSE and W/B metrics), t-k-means variants also demonstrated strong performance, often achieving the best or second-best results.
  • Reduced Variance: The t-k-means methods exhibited a smaller standard deviation in their results across multiple runs, empirically confirming their enhanced stability.
  • Efficient Computation: The "fast t-k-means" achieved running times comparable to standard k-means, significantly faster than TMM, highlighting its practical utility.

Limitations and Future Work

  • Hyperparameter Sensitivity: While the paper mentions setting v=1 for fast t-k-means, the sensitivity of v and other hyperparameters to different datasets is not extensively discussed.
  • Initialization: The paper notes that "fast t-k-means++" (initialized with k-means++) performs best on synthetic data, suggesting that initialization strategy still plays a role. Further exploration into optimal initialization for t-k-means could be beneficial.
  • Scalability: While "fast t-k-means" is efficient, its scalability to extremely large datasets might still be a consideration compared to highly optimized k-means implementations.

The authors' work lays a strong foundation for robust and stable clustering, and future work could involve exploring more advanced initialization techniques, deeper analysis of hyperparameter tuning, and further optimizations for massive-scale data.

Summary updated

BibTeX
@inproceedings{li2021t,
  author = {Yiming Li and Yang Zhang and Qingtao Tang and Weipéng Huáng and Yong Jiang and Shu-Tao Xia},
  title = {{t-k-means: A ROBUST AND STABLE k-means VARIANT}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2021},
  doi = {10.1109/icassp39728.2021.9414687},
}
Figure