Modal-set estimation with an application to clustering

Heinrich Jiang, Samory Kpotufe

Abstract: We present a first procedure that can estimate -- with statistical consistency guarantees -- any local-maxima of a density, under benign distributional conditions. The procedure estimates all such local maxima, or modal-sets, of any bounded shape or dimension, including usual point-modes. In practice, modal-sets can arise as dense low-dimensional structures in noisy data, and more generally serve to better model the rich variety of locally-high-density structures in data. The procedure is then shown to be competitive on clustering applications, and moreover is quite stable to a wide range of settings of its tuning parameter.

Introduction

In unsupervised learning, "modes" are the peaks of a probability density function where data is most concentrated. Traditionally, these are modeled as single points. However, modern high-dimensional data often clusters around lower-dimensional manifolds, such as rings or surfaces. Treating these structures as collections of individual point-modes often leads to over-segmentation and a failure to capture the underlying geometry of the data.

Heinrich Jiang and Samory Kpotufe introduce a robust framework for finding these high-density structures, termed modal-sets. Their algorithm, M-cores, is the first to estimate connected regions of locally high density of any shape or dimension with rigorous statistical consistency guarantees.

The M-cores Algorithm

M-cores operates on a $k$-Nearest Neighbor ($k$-NN) density estimate. The procedure identifies modal-sets by traversing the data from high to low density and tracking connected components in a $k$-NN graph.

Final clustering result of M-cores on a noisy 3D dataset containing three interlocking rings, demonstrating successful recovery of complex modal-sets.

The key innovation is the "Look-Down" Pruning mechanism. When a new potential mode appears as a separate connected component at a density level $\lambda$, the algorithm checks a slightly lower density level. If the component remains distinct at this lower level, it is accepted as a true modal-set. If it merges with an existing component, it is discarded as noise. This approach bridges the gap between topological data analysis and classical density estimation, providing a principled way to distinguish signal from noise.

Theoretical Consistency

The authors provide a formal proof that as the sample size $n \to \infty$, the estimated sets converge to the true modal-sets in terms of Hausdorff distance. For point-modes, M-cores achieves estimation rates matching known minimax lower bounds (up to a logarithmic factor), indicating near-optimal efficiency.

Experimental Evaluation

Synthetic and Benchmark Data

The algorithm was tested on a "three rings" dataset in 3D space, demonstrating its ability to capture non-point structures. On standard UCI benchmarks (e.g., Phonemes, Glass, Iris, and Wearable Computing), M-cores achieved Adjusted Mutual Information (AMI) and Adjusted Rand Index (ARI) scores competitive with or superior to DBSCAN and Mean-Shift.

Medical Imaging Application

M-cores was applied to identify capillary structures in Diabetic Retinopathy images. The goal was to automatically discover the proliferation of damaged blood vessels, which appear as locally high-density structures in the image data.

Segmentation of capillary structures in retinopathy images using M-cores, enabling the differentiation between healthy and diseased tissue based on density structures.

In this task, M-cores correctly identified significantly more capillary structures in unhealthy eyes (29) compared to healthy eyes (6), effectively capturing the disease pathology through density structures.

Stability and Practicality

A major advantage of M-cores is its stability. Unlike algorithms like DBSCAN, which are highly sensitive to hyperparameter tuning (e.g., $\epsilon$), M-cores maintains high-quality performance across a wide range of $k$ values. This "flat" performance profile makes it exceptionally practical for real-world applications where ground truth is unavailable.

Conclusion

By shifting the paradigm from point-modes to modal-sets, M-cores provides a more accurate reflection of manifold-structured data. Its combination of theoretical rigor, competitive performance, and remarkable stability makes it a powerful new tool for density estimation and clustering.

Summary updated

Abstract

We present a first procedure that can estimate -- with statistical consistency guarantees -- any local-maxima of a density, under benign distributional conditions. The procedure estimates all such local maxima, or $\textit{modal-sets}$, of any bounded shape or dimension, including usual point-modes. In practice, modal-sets can arise as dense low-dimensional structures in noisy data, and more generally serve to better model the rich variety of locally-high-density structures in data. The procedure is then shown to be competitive on clustering applications, and moreover is quite stable to a wide range of settings of its tuning parameter.
BibTeX
@inproceedings{jiang2017modal,
  author = {Heinrich Jiang and Samory Kpotufe},
  title = {{Modal-set estimation with an application to clustering}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2017},
  url = {https://openreview.net/forum?id=YrTlDYskS6M},
}
Figure