Approximating Hierarchical MV-sets for Hierarchical Clustering

Assaf Glazer, Omer Weissbrod, Michael Lindenbaum, Shaul MarkovitchNeurIPS 2014

Overview

This paper introduces a novel hierarchical clustering method designed to bypass the "curse of dimensionality." By directly estimating density level sets—specifically Minimum Volume (MV) sets—using a convex optimization framework called $q$-OCSVM, the authors avoid the pitfalls of explicit global density estimation. This approach efficiently reveals the modal structure of high-dimensional data, outperforming traditional density-based methods on complex, real-world datasets like the 1000 Genomes project.

The Challenge of High-Dimensional Clustering

Hierarchical clustering aims to find nested partitions of data. This is often visualized as a "cluster tree" where branches represent high-density regions separated by sparse valleys. Traditionally, researchers tackle this using a two-step process: first, they estimate the underlying probability density function (PDF) of the data, and second, they find the connected components of the level sets of that PDF.

1D density plot illustrating how level sets correspond to the branches of a hierarchical cluster tree.

However, accurate density estimation is notoriously difficult in high-dimensional spaces. Furthermore, simple methods like "single-linkage" clustering often suffer from the "chaining effect," where a few noisy data points erroneously connect two distinct, dense clusters. The authors sought a method that remains robust in high dimensions, avoids global density estimation, and maintains a rigorous mathematical foundation.

A Three-Stage Methodology

To overcome these challenges, the authors propose a three-stage approach centered around Support Vector Machines (SVMs):

  1. Estimating MV-Sets with $q$-OCSVM: Instead of estimating the entire density, the method estimates Minimum Volume (MV) sets. An MV-set at level $\alpha$ is the smallest region containing at least $\alpha$ probability mass. They utilize the $q$-One Class SVM ($q$-OCSVM), a multi-quantile extension of the standard One-Class SVM. This allows them to jointly solve for multiple nested level sets using a single convex quadratic program, ensuring a globally optimal solution in polynomial time.
  2. Generalizing to Infinite Levels: While $q$-OCSVM finds a finite number of sets, the authors use linear interpolation between the SVM's bias terms to define a continuous spectrum of level sets. This allows them to assign an "expected probability mass" $\alpha(x)$ to any point in the space.
  3. Graph-Based Tree Construction: Finally, they construct a fully connected graph where nodes are data points. The edge weight between two points is the maximum $\alpha$ value found along the line segment connecting them. By iteratively removing edges with high weights (moving from low to high density), the connected components of the graph naturally reveal the hierarchical cluster structure.

Key Insights

  • Direct vs. Indirect Estimation: The core realization is that clustering does not require knowing the value of the density everywhere; it only requires knowing the boundaries of the densest regions. SVMs are specifically designed to find boundaries, making them a natural fit.
  • Convexity is King: By formulating the problem as a convex optimization task, the authors avoid the local minima issues that plague many other clustering heuristics (like K-means).
  • Parallelism in Feature Space: The $q$-OCSVM forces the decision boundaries to be parallel in the high-dimensional feature space. This geometric constraint naturally enforces the "nested" requirement of hierarchical clustering.

Key Results and Performance

The method was evaluated across synthetic data, the Olive Oil dataset (572 samples, 8 chemical features), and the high-dimensional 1000 Genomes dataset (1,092 individuals, 1,000 genetic features).

F-measure comparison on the Olive Oil dataset across different numbers of modes.
  • Robustness on Standard Data: On the Olive Oil dataset, the $q$-OCSVM method dominated other approaches (KDE, NNE, BiKMeans) as the number of clusters increased, maintaining a higher F-measure (averaging roughly 0.62 compared to KDE's 0.55).
  • Superiority in High Dimensions: On the 1000 Genomes dataset, the $q$-OCSVM method achieved an F-measure of approximately 0.4, significantly outperforming the next best competitor (BiKMeans at 0.35). Traditional Kernel Density Estimation (KDE) was not even applicable due to the extreme dimensionality.
  • Biological Accuracy: The method successfully reconstructed a tree that matches established evolutionary theory, showing a clear divergence between African and Eurasian populations, followed by a later split between East Asian and European groups.

Limitations and Future Work

While powerful, the approach has a few limitations. First, performance is highly sensitive to the choice of the RBF kernel bandwidth ($\gamma$). If $\gamma$ is too large, the tree collapses; if too small, it fragments. The authors currently suggest a grid search based on the expected number of modes. Second, the edge-weight calculation (sampling points along a line segment) relies on a heuristic that lacks the strict theoretical guarantees of the $q$-OCSVM step. Finally, while the optimization is polynomial, building a fully connected graph for datasets with millions of points could become a computational bottleneck, suggesting a need for graph sparsification techniques in future iterations.

Summary updated

BibTeX
@inproceedings{glazer2014approximating,
  author = {Assaf Glazer and Omer Weissbrod and Michael Lindenbaum and Shaul Markovitch},
  title = {{Approximating Hierarchical MV-sets for Hierarchical Clustering}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
}
Figure