Unsupervised Feature Selection for the $k$-means Clustering Problem

Christos Boutsidis, Michael W. Mahoney, Petros DrineasNeurIPS 2009 · OpenReview

TL;DR

This paper introduces the first randomized feature selection algorithm for $k$-means clustering that comes with strong theoretical guarantees. By sampling a small subset of features based on "leverage scores" derived from the data's Singular Value Decomposition (SVD), the authors prove you can achieve a near-optimal clustering partition while significantly reducing dimensionality.

The Challenge of High-Dimensional Clustering

Clustering high-dimensional data presents a "double whammy" challenge. First, the curse of dimensionality makes algorithms like $k$-means computationally expensive. Second, many features in massive datasets are simply noise; they don't contribute to the underlying structure and can actually lead clustering algorithms astray.

While practitioners often use feature extraction (like PCA) to create a few "artificial" features, these new variables are often impossible to interpret. Feature selection—picking a subset of the original features—is much more desirable for interpretability. However, until this paper, there were no selection methods that could provably guarantee the quality of the resulting clusters compared to the optimal solution on the full dataset.

Proposed Method: SVD-Based Randomized Selection

The authors propose a randomized algorithm that selects and rescales features in an unsupervised manner. The core steps are:

  1. Compute the SVD: Find the top-$k$ right singular vectors ($V_k$) of the data matrix $A$.
  2. Calculate Leverage Scores: For each feature, compute a "leverage score" based on the Euclidean norm of the corresponding row in $V_k$. These scores essentially quantify how much "influence" or "importance" each feature has relative to the best $k$-dimensional subspace.
  3. Randomized Sampling: Treat these scores as a probability distribution and sample $r$ features (where $r \approx \Theta(k \log k)$).
  4. Rescaling: Multiply the selected features by a weight to ensure the statistical properties of the original matrix are roughly preserved.

The "secret sauce" here is using the SVD not to transform the data, but to identify which original columns are most important to keep.

Key Insights and Interpretability

The paper demonstrates that features with high leverage scores have significant discriminative power.

Leverage scores for features in the NIPS dataset

For example, when evaluated on a NIPS document-term matrix (categorized into Neuroscience, Learning Theory, and Control/Reinforcement Learning), words like "ruyter," "hand," and "information" had high scores and were highly specific to certain paper categories.

Furthermore, there is a clear trade-off between selection and extraction. Feature extraction (SVD/PCA) typically provides a 2-approximation for $k$-means. This selection method provides a slightly worse $(2+\epsilon)$ approximation but critically maintains the interpretability of the original features. This is the first work to provide a $(1 + \epsilon)$ relative-error style bound for feature selection in $k$-means, moving the field beyond heuristics.

Empirical Results and Efficiency

The authors evaluated their approach on two real-world datasets: the NIPS document matrix and a Bio Microarray dataset containing gene expression levels for cancer patients.

Clustering performance across different numbers of selected features
  • Theoretical Guarantee: The authors prove that running a $\gamma$-approximate $k$-means algorithm on the selected features yields a partition that is at most $(1 + (1 + \epsilon)\gamma)$ times the optimal objective value on the full dataset.
  • Empirical Efficiency: While the theory suggests a larger number of features, experiments showed that selecting just $r = 10k$ or $r = 20k$ features (a tiny fraction of the original thousands) was enough to achieve near-perfect clustering accuracy.
  • Accuracy: On the Bio dataset, using just 60 selected features ($r=20k$ where $k=3$) resulted in a classification accuracy ($P$) of 1.0, matching the performance of using all 5520 features.

Limitations and Future Work

  • Computational Bottleneck: The algorithm requires computing the top-$k$ right singular vectors of the input matrix. For truly massive datasets, this $O(\min\{nd^2, n^2d\})$ step can still be expensive, though faster randomized SVD methods could potentially be swapped in.
  • Randomized Failure: As a randomized algorithm, there is a small probability of failure (selecting a "bad" subset), though this can be mitigated through standard boosting (running the process multiple times and picking the best result).
  • Refining $r$: There is a gap between the number of features required by the theory ($\Theta(k \log k / \epsilon^2)$) and the much smaller number that works in practice. Future work could focus on tightening these theoretical bounds to match empirical observations.

Summary updated

Abstract

We present a novel feature selection algorithm for the $k$-means clustering problem. Our algorithm is randomized and, assuming an accuracy parameter $\epsilon \in (0,1)$, selects and appropriately rescales in an unsupervised manner $\Theta(k \log(k / \epsilon) / \epsilon^2)$ features from a dataset of arbitrary dimensions. We prove that, if we run any $\gamma$-approximate $k$-means algorithm ($\gamma \geq 1$) on the features selected using our method, we can find a $(1+(1+\epsilon)\gamma)$-approximate partition with high probability.
BibTeX
@inproceedings{boutsidis2009unsupervised,
  author = {Christos Boutsidis and Michael W. Mahoney and Petros Drineas},
  title = {{Unsupervised Feature Selection for the $k$-means Clustering Problem}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2009},
  url = {https://openreview.net/forum?id=Sk-1GO-u-r},
}
Figure