Source-linked AI summary
High-dimensional cluster analysis with the Masked EM Algorithm
Shabnam N. Kadir, Dan F. M. Goodman, Kenneth D. Harris
TL;DR
High-dimensional clustering must handle irrelevant features and costly computation, especially when informative features differ across data points. The paper introduces Masked EM, which uses data-point-specific masks and virtual noise distributions for Gaussian-mixture clustering. It reports good performance on simulated high-dimensional data and neurophysiological spike sorting, while the study’s scope is limited to one hard-EM mixture-of-Gaussians application.
Problem
High-dimensional clustering faces poor classification from uninformative features and impractical computation, while informative feature subsets may differ across data points.
Method
Masked EM computes data-point-specific feature masks and replaces masked measurements with virtual noise distributions during mixture-of-Gaussians clustering.
Results
The Masked EM algorithm performs well on simulated high-dimensional data and in neurophysiological spike sorting, with performance close to the theoretical upper bound in the hybrid dataset.
Takeaways & Limitations
Masked EM’s parameters and computational cost scale with unmasked features per data point rather than the total feature count.
Takeaways & Limitations
The study applies masking only to one unsupervised classification application using hard EM for Gaussian-mixture fitting.
Abstract
from arXiv · showhide
Cluster analysis faces two problems in high dimensions: first, the `curse of dimensionality' that can lead to overfitting and poor generalization performance; and second, the sheer time taken for conventional algorithms to process large amounts of high-dimensional data. In many applications, only a small subset of features provide information about the cluster membership of any one data point, however this informative feature subset may not be the same for all data points. Here we introduce a `Masked EM' algorithm for fitting mixture of Gaussians models in such cases. We show that the algorithm performs close to optimally on simulated Gaussian data, and in an application of `spike sorting' of high channel-count neuronal recordings.
1 Introduction
High-dimensional Gaussian-mixture clustering is limited by both statistical noise from irrelevant features and computational cost. The paper motivates Masked EM for data points whose informative feature subsets differ, using masks to reduce the effective dimensionality.
- 1 Introduction: High-dimensional mixture-of-Gaussians clustering suffers from poor classification when many features are uninformative and from impractical computational costs.Covariance estimation can require O(p^2) computation, while even O(p) costs may be prohibitive for repeatedly analyzing large datasets.
- 1 Introduction: Low-dimensional covariance modeling can reduce per-cluster parameters from O(p^2) to O(p), improving computational cost and potentially performance.Mixture of Factor Analyzers approximates each cluster covariance with a low-rank matrix plus a fixed diagonal noise matrix.
- 1 Introduction: Feature selection can reduce parameters and computation below O(p), but global selection cannot accommodate data points defined by different informative feature sets.This motivates selecting or weighting features separately for individual data points.
- 1 Introduction: Spike sorting provides the target application: clustering millions of neural waveforms recorded with high-count silicon microelectrodes.Earlier probes typically produced 12-dimensional feature vectors from four channels, where traditional EM-derived methods worked close to optimally but required rapid implementation for daily datasets.
- 1 Introduction: Masked EM first computes a data-point-specific mask weighting each feature, potentially using domain knowledge such as spatial contiguity of action potentials.When most mask values are zero, parameters and running time can both fall substantially below O(p).
2 The Masked EM Algorithm
Masked EM first assigns data-point-specific feature masks, then fits a Gaussian mixture over virtualized noisy features. This reduces the effective dimensionality, computation, and model penalty when most features are masked.
- 2.1 Stage 1: mask generation: Mask vectors assign each feature a weight from 0 to 1 for classifying each data point.Zero means ignored, one means used, and intermediate values give partial weighting.
- 2.1 Stage 1: mask generation: Domain-specific or threshold-based heuristics can generate masks; spike sorting additionally uses spatial contiguity across recording channels.The authors report that performance is not critical to the masking algorithm provided most non-informative features receive zero weight and clearly suprathreshold features receive one.
- 2.2 Stage 2: clustering: Masked EM replaces each data point with a virtual ensemble in which masked features follow independent Gaussian noise distributions.This preserves observed values for unmasked features while marginalizing over noisy masked variables.
- 2.2 Stage 2: clustering: The modified E- and M-steps operate on expectations over the virtual distribution, using expected feature values and covariance corrections.The M-step uses expected means and covariances, while the E-step averages responsibilities over the virtual ensemble.
- 2.5 Penalties: The effective parameter penalty depends on the average number of unmasked features per cluster rather than the full feature count.The function F(r) counts covariance, mean, and mixture-weight parameters for an effective dimension r, and the resulting estimate works well in AIC in practice.
- Implementation: Implementation uses custom C++ based on KlustaKwik, with hard classification and heuristics that reduce iterations for fast processing of millions of high-dimensional points.These approximations are intended to accelerate execution without significant impact on performance.
3 Evaluation
The Masked EM algorithm was evaluated on simulated high-dimensional Gaussian mixtures and hybrid spike-sorting data, where it performed close to theoretical or optimal benchmarks while classical EM degraded in high dimensions.
- Simulated data: The simulated data contained 20,000 points in 1,000 dimensions drawn from seven Gaussian clusters.Cluster means varied across selected features, while all clusters shared an exponentially decaying Toeplitz covariance matrix.
- Simulated data: Figure 1 compares Masked EM and classical EM using confusion matrices, variation of information, and estimated cluster counts across penalty values.The BIC penalty is marked in the variation-of-information and cluster-count panels.
- Simulated data: Classical EM achieved a variation-of-information value of 1.83, corresponding to merging all points into a single cluster.This was reported as poorer performance than the Masked EM result.
- Spike sorting: Spike-sorting evaluation used hybrid datasets with simulated ground truth and compared Masked EM and classical EM against an SVM-based supervised upper bound.Performance was assessed using false discovery rate and true positive rate, with the SVM evaluated by cross-validation.
- Spike sorting: Masked EM performed close to the SVM upper bound, whereas classical EM performed much more poorly on the full 96-feature hybrid dataset.Restricting classical EM to the nine unmasked features brought it close to the theoretical upper bound, indicating a high-dimensional failure mode.
4 Discussion and Conclusions
The masking strategy supports clustering when informative features vary across data points, while scaling parameters and computation with unmasked rather than total features. The study also addresses artificial cluster splitting but remains limited to one hard-EM Gaussian-mixture application.
- Contribution: Masked EM targets cases where each data point uses a small, potentially different subset of informative features.Unlike global feature selection, both the number and precise set of unmasked features can vary between data points.
- Contribution: The number of free parameters and computational cost scale with the number of unmasked features per data point rather than the total feature count.This is the central computational and statistical scaling property claimed for the approach.
- Caveat and mitigation: Real-valued masks and virtual subthreshold distributions prevent noisy threshold crossings from causing artificial cluster splitting.The authors report that erroneous splitting was not a problem in simulation or spike sorting.
- Scope: The present study applies masking to one unsupervised classification setting using hard EM for mixture-of-Gaussians fitting.The authors identify broader applications as possibilities rather than results established by this study.