Feature Selection for Unsupervised Learning

Jennifer G. Dy, Carla E. BrodleyJMLR 2004 · OpenReview

Abstract

Feature selection is a critical yet challenging task in unsupervised learning, where the absence of labels creates a "chicken and egg" dilemma: identifying optimal clusters requires the right features, but identifying the right features requires knowledge of the underlying clusters. This paper introduces FSSEM (Feature Subset Selection using EM clustering), a wrapper framework designed to automate feature selection while addressing two major hurdles: the dependency of the cluster count ($k$) on the feature subspace and the inherent mathematical bias of evaluation criteria toward specific dimensionalities.

The Challenges of Unsupervised Feature Selection

In supervised learning, features are selected based on their predictive power for a known label. In clustering, however, the objective is less defined. The authors identify two specific gaps in existing research that FSSEM aims to bridge:

  1. Dynamic Cluster Counts: Most algorithms assume a fixed number of clusters. However, the structure of data is inherently tied to its dimensionality. As shown in Figure 1, a dataset that clearly exhibits three clusters in a 2D space may collapse into only two clusters when projected onto a 1D line. A robust feature selection algorithm must therefore treat $k$ as a variable.
  2. Dimensionality Bias: Common evaluation metrics are mathematically biased. For instance, "Scatter Separability" (measuring cluster distance) naturally increases as features are added, even if those features are noise. Conversely, "Maximum Likelihood" often prefers fewer features. This bias makes it impossible to fairly compare feature subsets of different sizes without normalization.
Projection from 2D to 1D demonstrating how the optimal number of clusters can change with the feature subset.

The FSSEM Framework

The authors propose a wrapper framework that iterates through a search-and-evaluate loop to find the most "interesting" feature subset.

The FSSEM wrapper framework for unsupervised feature selection.

Methodology

The process follows three core steps:

  • Search: Utilizing Sequential Forward Search (SFS) to incrementally add features.
  • Cluster: Applying the Expectation-Maximization (EM) algorithm to identify clusters within the current candidate subspace.
  • Evaluate: Scoring the resulting clusters using a normalized criterion.

Key Innovations

To solve the identified hurdles, FSSEM incorporates two specific mechanisms:

  • FSSEM-k: Instead of a fixed $k$, the algorithm employs a "merge" strategy combined with the Bayesian Information Criterion (BIC) to determine the optimal number of clusters for every candidate feature subset.
  • Cross-Projection Normalization: To eliminate dimensionality bias, the authors introduce a method to compare subsets of different sizes. When comparing two subsets, the clusters found in Subset A are projected into the space of Subset B (and vice versa). By evaluating both sets of clusters in both spaces, the dimensional bias is cancelled out, enabling an "apples-to-apples" comparison.

Experimental Results and Insights

The framework was evaluated on synthetic Gaussian mixtures, classic UCI datasets (Iris, Wine, Ionosphere), and a high-resolution computed tomography (HRCT) lung dataset.

  • Performance Gains: On the Ionosphere dataset, FSSEM reduced cross-validated class error from ~35% (using all features) to ~18% using a optimized subset.
  • Sparsity in Medical Data: In the HRCT-Lung dataset, the algorithm successfully reduced 108 dimensions down to an average of fewer than 3 features while improving diagnostic accuracy.
  • The Role of Standardization: The paper demonstrates that Maximum Likelihood criteria are "density chasers," gravitating toward features with low variance. Consequently, data standardization is a prerequisite for ML-based selection to avoid trivial solutions.
  • Feature Selection as a Filter for k: Interestingly, the research found that feature selection helps the EM algorithm find the "correct" $k$. On noisy datasets, clustering on all features often led to incorrect cluster counts, whereas the selected subsets consistently hit the mark.

Conclusion and Future Directions

FSSEM provides a mathematically grounded approach to unsupervised feature selection. While effective, the authors note that the definition of an "interesting" cluster remains somewhat subjective; Scatter criteria prefer well-separated clusters, while ML prefers dense Gaussian shapes. Future work will focus on reducing the computational cost of the wrapper approach and extending the framework to handle mixed data types (nominal and discrete) alongside continuous features.

Summary updated

BibTeX
@article{dy2004feature,
  author = {Jennifer G. Dy and Carla E. Brodley},
  title = {{Feature Selection for Unsupervised Learning}},
  journal = {J. Mach. Learn. Res.},
  year = {2004},
  url = {https://openreview.net/forum?id=iHCWig3LEp},
}
Figure