Sparse Embedded k-Means Clustering

Weiwei Liu, Xiao-Bo Shen, Ivor W. TsangNeurIPS 2017 · OpenReview

Introduction

The $k$-means clustering algorithm is a fundamental and ubiquitous tool in data science, but it struggles with the "curse of dimensionality." As datasets grow to include millions of points ($n$) and features ($d$), the computational cost of $k$-means becomes prohibitive.

To solve this, researchers often use dimensionality reduction (DR) to shrink the data before clustering. However, existing DR methods present significant trade-offs. Singular Value Decomposition (SVD) based methods are highly accurate but computationally expensive. Random Projection (RP) methods are faster, but previous state-of-the-art versions still required dense matrix multiplications. This creates a bottleneck for large-scale data because the cost scales with the product of $n$ and $d$, even if the underlying data is highly sparse (like text or genomic data).

This paper introduces a "Sparse Embedded $k$-Means" algorithm that drastically speeds up clustering for massive, high-dimensional datasets. By utilizing a sparse random projection matrix, the authors achieve a $(1+\epsilon)$ approximation guarantee with a computational cost proportional only to the number of non-zero entries in the data—$O(nnz(X))$—outperforming previous methods in both speed and accuracy.

Methodology: Sparse Embedded $k$-Means

Instead of multiplying the data by a dense random matrix, the authors construct a sparse embedding matrix $R$ through two simple components:

  1. A Random Map ($h$): Each original feature is randomly assigned to one of the $\tilde{d}$ new dimensions.
  2. A Rademacher Matrix ($Q$): A diagonal matrix that randomly flips the signs ($\pm 1$) of the features to prevent "collisions" from canceling each other out.

The resulting transformation $\hat{X} = XQ\Phi$ is extremely fast to compute because it only requires iterating over the non-zero elements of the input matrix $X$. While sparse projections exist in other contexts (like the Sparse Johnson-Lindenstrauss Transform), this paper provides the first rigorous proof that such a sparse construction preserves the specific geometric structure required for $k$-means clustering with a tight $(1+\epsilon)$ error bound.

Experiments and Key Results

The algorithm was evaluated on four diverse real-world datasets representing a mix of dense and sparse data: COIL20 (images), SECTOR (web pages), RCV1 (newswire text), and ILSVRC2012 (ImageNet computer vision data).

Unprecedented Speedup

By making the complexity $O(nnz(X))$, the algorithm's speed scales with the actual information content of the data rather than its raw dimensions. On large datasets like RCV1 and ImageNet, the proposed Sparse Embedded (SE) method was several hundred times faster than previous random projection methods during the preprocessing phase.

Preprocessing time across datasets

Stable and Superior Accuracy

Surprisingly, the authors proved their sparse method achieves a $(1+\epsilon)$ approximation, theoretically superior to the previous best random projection method for $k$-means, which only guaranteed a $(2+\epsilon)$ approximation. Empirically, as the number of embedded dimensions increases, the clustering accuracy remains highly stable and closely tracks the results of $k$-means performed on the full, original dataset.

Clustering accuracy across datasets

Limitations and Future Work

While highly effective, the approach has a few limitations. The number of dimensions required for the embedding ($\tilde{d}$) depends on $1/\epsilon^2$. If a user requires an extremely tiny error margin ($\epsilon$), the "reduced" dimension might still be quite large. Additionally, like all RP methods, there is a small probability ($\delta$) that the embedding fails to preserve the structure, which must be accounted for in production environments.

Future directions could include applying this sparse embedding technique to other clustering variants, such as $k$-medians, or adapting it for streaming data environments where $O(nnz(X))$ efficiency is even more critical.

Summary updated

Abstract

The $k$-means clustering algorithm is a ubiquitous tool in data mining and machine learning that shows promising performance. However, its high computational cost has hindered its applications in broad domains. Researchers have successfully addressed these obstacles with dimensionality reduction methods. Recently, [1] develop a state-of-the-art random projection (RP) method for faster $k$-means clustering. Their method delivers many improvements over other dimensionality reduction methods. For example, compared to the advanced singular value decomposition based feature extraction approach, [1] reduce the running time by a factor of $\min \{n,d\}\epsilon^2 log(d)/k$ for data matrix $X \in \mathbb{R}^{n\times d} $ with $n$ data points and $d$ features, while losing only a factor of one in approximation accuracy. Unfortunately, they still require $\mathcal{O}(\frac{ndk}{\epsilon^2log(d)})$ for matrix multiplication and this cost will be prohibitive for large values of $n$ and $d$. To break this bottleneck, we carefully build a sparse embedded $k$-means clustering algorithm which requires $\mathcal{O}(nnz(X))$ ($nnz(X)$ denotes the number of non-zeros in $X$) for fast matrix multiplication. Moreover, our proposed algorithm improves on [1]'s results for approximation accuracy by a factor of one. Our empirical studies corroborate our theoretical findings, and demonstrate that our approach is able to significantly accelerate $k$-means clustering, while achieving satisfactory clustering performance.
BibTeX
@inproceedings{liu2017sparse,
  author = {Weiwei Liu and Xiao-Bo Shen and Ivor W. Tsang},
  title = {{Sparse Embedded k-Means Clustering}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=rJZlODWd-H},
}
Figure