Abstract
We present a 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, which can be points, curves, or complex surfaces, without requiring prior knowledge of their dimension or shape.
Introduction
In data analysis, identifying regions of high concentration—known as "modes"—is fundamental for clustering and structure discovery. Traditional methods like Mean-Shift typically assume that clusters are centered around single points. However, modern high-dimensional datasets often exhibit density structures that are far more complex, such as the 1D curves of blood vessels in medical imaging or the manifolds formed by human speech. These structures are better described as "modal-sets": connected regions of high density that can take any shape or dimension.
Existing approaches often struggle with these complex geometries, frequently over-segmenting a single structure or requiring restrictive assumptions about the data's underlying dimensionality. This paper introduces M-cores (Modal-cores), a robust algorithm designed to consistently estimate these high-density structures without a priori assumptions.
Methodology: The M-cores Algorithm
The M-cores procedure identifies modal-sets through a graph-based approach that leverages local density estimates. The algorithm follows four primary steps:
- Density Estimation: A $k$-Nearest Neighbor ($k$-NN) approach is used to estimate the density at every data point.
- Graph Construction: A "mutual $k$-NN graph" is built, connecting points that are spatially close and share high estimated density.
- Top-Down Traversal: Points are sorted by density. As the algorithm traverses from high to low density, it identifies new connected components in the graph as potential clusters.
- Adaptive Pruning: To distinguish true modal-sets from random noise, the algorithm employs a "lookup" distance. It checks if a potential mode at density level $\lambda$ remains a distinct, salient structure at a slightly lower density level ($\lambda - \text{offset}$).
A key innovation of M-cores is its reliance on the Hausdorff distance to measure the convergence of estimated shapes to the true underlying structures. Unlike many traditional methods, M-cores does not require the density function to be differentiable, making it highly versatile for various data types.
Experimental Results
The authors evaluated M-cores across diverse benchmarks, ranging from synthetic 3D structures to real-world medical and sensor data.
Medical Imaging
In a diabetic retinopathy detection task, M-cores was used to identify capillary structures in high-resolution retinal images. The algorithm successfully delineated 29 capillary structures in an unhealthy eye compared to only 6 in a healthy eye, demonstrating its ability to prune noise while preserving thin, complex manifolds.
Clustering Benchmarks
On standard UCI Machine Learning Repository datasets (e.g., Glass, Seeds, Iris), M-cores achieved performance competitive with or superior to industry standards like DBSCAN and Mean-Shift. A significant advantage observed was the algorithm's stability. While DBSCAN and Mean-Shift are highly sensitive to hyperparameter tuning, M-cores maintains peak performance across a broad range of $k$ values, creating a "performance plateau" that simplifies practical application.
Conclusion
M-cores provides a theoretically rigorous yet practical framework for modal-set estimation. By generalizing the concept of a mode from a point to a set, it captures the rich variety of structures present in modern data. Future work will focus on optimizing the computational complexity of $k$-NN graph construction for large-scale datasets and exploring automated methods for selecting the initial parameter $k$.
Summary updated