Avoiding inferior clusterings with misspecified Gaussian mixture models

Siva Rajesh Kasa, Vaibhav RajanScientific 2023 · DOI

TL;DR

This paper tackles the problem of "inferior clusterings" that arise when using Gaussian Mixture Models (GMMs) on data that doesn't perfectly fit the GMM assumption (misspecified data). The authors introduce a new penalty term and a clustering algorithm called SIA that effectively avoids these problematic clusterings, leading to more accurate results, especially when data is noisy or has complex structures.

What Problem Does This Paper Address?

Clustering is a fundamental technique for finding groups in data. Gaussian Mixture Models (GMMs) are a popular choice for this, assuming data points are generated from a mix of Gaussian distributions. However, real-world data is often messy: it might not be perfectly Gaussian, or it could contain outliers and noise. When GMMs are applied to such "misspecified" data, they can produce two types of bad solutions:

  1. Spurious solutions: These have high likelihood (meaning they seem statistically good) but are hard to interpret and don't reflect the true cluster structure. They often arise from components with very small variances.
  2. Inferior solutions: This is the focus of this paper. These solutions also have high likelihood and poor interpretability, but they are distinct from spurious solutions. They are characterized by fitted Gaussian components that are asymmetric in their orientation and size, and they tend to appear more frequently than spurious solutions, even with different initializations.

The core problem is that standard GMM fitting methods (like Expectation-Maximization, EM) can get stuck in these inferior solutions when the data is misspecified, leading to incorrect clustering results.

Methods

The authors propose a novel approach to address inferior clusterings:

  • Theoretical Analysis of Asymmetry: They theoretically analyze how the asymmetry of fitted Gaussian components relates to data misspecification. This analysis provides a deeper understanding of why inferior solutions occur.
  • New Penalty Term: Based on their theoretical insights, they introduce a new penalty term for the GMM objective function. This penalty is designed to discourage asymmetry in the fitted components, thereby avoiding inferior solutions. It's based on the Kullback-Leibler (KL) divergence between pairs of fitted component Gaussians, penalizing differences in their sizes and orientations.
  • SIA Algorithm: They develop a new GMM-based clustering algorithm called SIA (Sequential Initialization Algorithm). SIA works in two steps:
  • It first uses standard GMM fitting (either EM or Automatic Differentiation Gradient Descent - AD-GD) to get an initial clustering.
  • Then, it refines this clustering using the penalized objective function. This second step helps to correct for any remaining asymmetry and improve the clustering quality.
  • MPKL Model Selection Criterion: They also propose a model selection criterion called MPKL (Maximum absolute Pairwise difference between KL divergence values). MPKL helps in selecting the optimal number of clusters by measuring how well-separated the clusters are, and it's independent of the SIA algorithm itself.
  • Automatic Differentiation (AD-GD): The paper leverages Automatic Differentiation (AD-GD) for efficient gradient computation, which is crucial for implementing their penalized likelihood approach, especially in complex models.

Datasets

The paper uses a variety of datasets for evaluation:

  • Pinwheel Data: A synthetic dataset specifically designed to mimic warped GMMs, allowing for controlled misspecification by varying parameters like radial and tangential standard deviation, and a warping rate. This is used extensively in the initial simulations and illustrations.
  • GMM-generated Data: Synthetic datasets generated from GMMs with varying overlap, cluster separation, covariance structures, and imbalance in component sizes, across different dimensions.
  • Real-world Datasets: A diverse set of 10 real-world datasets are used, including:
  • Wine
    • IRIS
    • Abalone
    • Urban Land cover
    • LUSC RNA-Seq
    • Breast Cancer
    • Crabs
    • Wholesale
    • Ceramics
    • HTRU (a pulsar dataset)

These real datasets are chosen to represent scenarios where clusters might not be perfectly Gaussian or well-separated.

Key Insights and Ideas

  • Inferior Clusterings are a Distinct Problem: The paper clearly distinguishes "inferior clusterings" from "spurious solutions," highlighting their unique characteristics (asymmetry, frequency) and the need for specific methods to address them.
  • Asymmetry as a Misspecification Indicator: The theoretical analysis reveals a direct link between the asymmetry of fitted GMM components and the degree of misspecification in the data. This is a crucial insight for understanding why standard GMMs fail.
  • Penalizing Asymmetry Works: The proposed penalty term effectively discourages asymmetric component fits, leading to more interpretable and accurate clusterings, especially when the data is not perfectly Gaussian.
  • SIA's Two-Stage Approach is Effective: The sequential nature of SIA, first getting a high-likelihood solution and then refining it with a penalty, proves to be a robust strategy for avoiding both inferior solutions and the pitfalls of hard constraints.
  • MPKL as a Useful Metric: The MPKL criterion offers a data-driven way to assess cluster separation, complementing traditional model selection criteria and aiding in choosing better clusterings.

Key Results

  • Empirical Evidence of Inferior Solutions: Simulations on the Pinwheel dataset and other synthetic data demonstrate that both EM and AD-GD frequently produce inferior solutions when data is misspecified. These solutions often have high likelihood but low Adjusted Rand Index (ARI).
  • SIA Outperforms: The SIA algorithm consistently outperforms standard EM and AD-GD, as well as MClust (which uses hard constraints), in terms of ARI on misspecified datasets, particularly when cluster separation is low or dimensionality is high.
  • Theoretical Guarantees: The paper provides theoretical guarantees that the penalized likelihood objective used by SIA is bounded, thus avoiding degenerate and spurious solutions.
  • Real-world Performance: SIA shows competitive or superior performance on various real-world datasets, demonstrating its practical applicability. For instance, on the Wine dataset, SIA achieved comparable or better ARI values with lower MPKL scores.

Limitations and Future Work

  • Computational Complexity: The computational complexity of SIA and MPKL is O(K²p³), which is comparable to standard GMM inference methods due to the matrix inversion step. While efficient, it can still be a bottleneck for very high-dimensional data.
  • Hyperparameter Tuning: The SIA algorithm involves hyperparameters (w1, w2 for the penalty term) that need to be chosen. While the paper suggests using the MPKL criterion and experimenting with values, further research into automated hyperparameter selection could be beneficial.
  • Theoretical Extensions: The authors suggest that further theoretical investigation into the connection between asymmetry and misspecification, and extending the statistical guarantees to high-dimensional settings, would be valuable future work.
  • Data and Code Availability: The authors provide Python implementations of their algorithms and experiments, which is a positive step for reproducibility and further research.

Summary updated

Abstract

Clustering is a fundamental tool for exploratory data analysis, and is ubiquitous across scientific disciplines. Gaussian Mixture Model (GMM) is a popular probabilistic and interpretable model for clustering. In many practical settings, the true data distribution, which is unknown, may be non-Gaussian and may be contaminated by noise or outliers. In such cases, clustering may still be done with a misspecified GMM. However, this may lead to incorrect classification of the underlying subpopulations. In this paper, we identify and characterize the problem of inferior clustering solutions. Similar to well-known spurious solutions, these inferior solutions have high likelihood and poor cluster interpretation; however, they differ from spurious solutions in other characteristics, such as asymmetry in the fitted components. We theoretically analyze this asymmetry and its relation to misspecification. We propose a new penalty term that is designed to avoid both inferior and spurious solutions. Using this penalty term, we develop a new model selection criterion and a new GMM-based clustering algorithm, SIA. We empirically demonstrate that, in cases of misspecification, SIA avoids inferior solutions and outperforms previous GMM-based clustering methods.
BibTeX
@inproceedings{kasa2023avoiding,
  author = {Siva Rajesh Kasa and Vaibhav Rajan},
  title = {{Avoiding inferior clusterings with misspecified Gaussian mixture models}},
  booktitle = {Scientific},
  year = {2023},
  doi = {10.1038/s41598-023-44608-3},
}

Loading related content...

Figure