Variable Selection in Model-Based Clustering: To Do or To Facilitate

Leonard K. M. Poon, Nevin Lianwen Zhang, Tao Chen, Yi WangICML 2010 · OpenReview

The Core Problem: The Multifaceted Nature of Data

In supervised learning, variable selection is relatively straightforward: you retain the features that best help predict a known label. In unsupervised clustering, however, the absence of labels makes this a significantly harder problem.

Traditional methods attempt to perform "variable selection" by finding a single optimal subset of attributes to produce one "best" clustering. However, this paper highlights a fundamental philosophical flaw in that approach: high-dimensional data is often naturally multifaceted. For instance, a dataset of customers could be meaningfully clustered by their "health habits" using one set of features, or by their "spending patterns" using an entirely different set.

If an algorithm forces a single choice, it might select a statistically strong facet that is completely irrelevant to the user’s actual domain goals. The authors propose a paradigm shift: an algorithm's job shouldn't be to do the selection automatically, but to facilitate it by presenting the various natural ways the data can be partitioned, allowing domain experts to choose the most relevant facet.

Methods: Pouch Latent Tree Models (PLTMs)

To achieve this facilitation, the authors introduce the Pouch Latent Tree Model (PLTM), a framework that generalizes the standard Gaussian Mixture Model (GMM).

The Structure and the "Pouch"

A PLTM is structured as a rooted tree where internal nodes are discrete latent (hidden) variables. Each of these latent variables represents a different way to cluster the data—a distinct "facet."

The leaf nodes are termed "pouch nodes." Unlike standard latent tree models where each leaf is a single variable, a pouch node can contain a vector of multiple continuous observed variables that follow a conditional Gaussian distribution. This design allows the model to capture local correlations between specific sets of features.

Comparison of PLTM and standard GMM structures

As shown above, a standard GMM can be viewed as a special, simplified case of a PLTM with only a single latent node and one giant pouch containing all features. By breaking this structure into a tree, PLTMs allow different clusters to focus on relevant features while effectively "ignoring" irrelevant noise.

Learning the Model

  • Parameters: The authors use the Expectation-Maximization (EM) algorithm to estimate means and covariances. They employ specific eigenvalue constraints to avoid the "singularities" (spurious local maxima) that commonly plague standard GMMs.
  • Structure: The model structure is learned using a hill-climbing search guided by the Bayesian Information Criterion (BIC). The algorithm starts with a simple model and iteratively applies operators (like adding/deleting nodes or merging pouches) to find a structure that optimally balances model fit with complexity.

Key Insights and Results

The authors evaluated PLTMs on a synthetic dataset designed with two distinct latent facets, as well as 9 well-known benchmarks from the UCI Repository (including Image, Ionosphere, Iris, and Breast Cancer). Performance was measured using Normalized Mutual Information (NMI) to evaluate how closely the discovered clusters matched original class labels (which were hidden during training).

Superiority Over Automated Selection

PLTM significantly outperformed specialized variable selection methods like CLUSTVARSEL (CVS) and LFJ on almost all datasets. On the synthetic dataset, PLTM achieved an NMI of 0.81, while CVS struggled at 0.07 because it latched onto the "wrong" facet and discarded the rest. PLTM also outperformed plain GMMs and MCLUST in most cases, proving that modeling the multifaceted nature of data helps isolate the "signal" from the "noise" more effectively.

Real-World Facet Recovery

The "facilitation" concept was perfectly demonstrated on the Image dataset.

Discovered PLTM structure for the Image dataset

Instead of returning one generic clustering, the PLTM identified four distinct latent variables (Y1 through Y4). By examining the tree, a user can see exactly which features drive which facet:

  • One latent variable perfectly captured the color-related features (which matched the dataset's ground truth).
  • Another captured edge-related facets.
  • Others captured location-related facets (centroids).

By providing these multiple latent variables, the PLTM acts as a powerful "feature discovery" tool, allowing the human expert to select the clustering that aligns with their specific analytical goals.

Limitations and Future Work

While highly effective, the PLTM approach has limitations, primarily regarding computational complexity. The structure learning process is computationally expensive; while moderate datasets took about 5 hours to cross-validate, the largest set (Zernike) took 2.5 days.

The authors note that their hill-climbing search is a greedy approach and suggest that future work could involve parallelization or more sophisticated heuristic searches to speed up tree discovery. Additionally, because the core value of PLTM is facilitation, future implementations would benefit greatly from a dedicated user interface where domain experts can easily visualize and browse the discovered facets.

Summary updated

Abstract

Variable selection for cluster analysis is a difficult problem. The difficulty originates not only from the lack of class information but also the fact that high-dimensional data are often multifaceted and can be meaningfully clustered in multiple ways. In such a case the effort to find one subset of attributes that presumably gives the "best" clustering may be misguided. It makes more sense to facilitate variable selection by domain experts, that is, to systematically identify various facets of a data set (each being based on a subset of attributes), cluster the data along each one, and present the results to the domain experts for appraisal and selection. In this paper, we propose a generalization of the Gaussian mixture model, show its ability to cluster data along multiple facets, and demonstrate it is often more reasonable to facilitate variable selection than to perform it.
BibTeX
@inproceedings{poon2010variable,
  author = {Leonard K. M. Poon and Nevin Lianwen Zhang and Tao Chen and Yi Wang},
  title = {{Variable Selection in Model-Based Clustering: To Do or To Facilitate}},
  booktitle = {International Conference on Machine Learning},
  year = {2010},
  url = {https://openreview.net/forum?id=r1VSMibOZS},
}
Figure