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.
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.
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