Lumbermark Beats HDBSCAN and k-means on 61 Clustering Benchmarks
A new divisive clustering algorithm chops up mutual reachability spanning trees to detect clusters of varying densities, shapes, and sizes while beating HDBSCAN and Genie on benchmarks.
- Lumbermark is a new divisive clustering algorithm that chops limbs off mutual reachability spanning trees.
- It beats HDBSCAN and Genie on 61 benchmark datasets with median AR of 0.98 on third-party labels.
- Unlike HDBSCAN, it accepts a user-specified cluster count k while remaining robust to outliers.
- Core trick: strip leaves from the MST, then cut longest edges only if components stay above a min size.
- Open source lumbermark package available in Python and R with scikit-learn API.
- Fast on low-dim data (1.3s for 1M points in 2D) but suffers in high dimensions due to MST cost.
Developers choosing a clustering method often trade an exact cluster count for flexible boundaries. k-means accepts k but favors compact, roughly spherical groups. HDBSCAN handles nonconvex clusters and labels noise, but its density hierarchy does not guarantee a requested count. Single linkage accepts k and arbitrary shapes, yet a sparse chain of points can join groups that should remain separate.
Marek Gagolewski introduces Lumbermark in a paper that combines a requested cluster count with density-aware tree cutting. The divisive algorithm builds a mutual-reachability minimum spanning tree, removes peripheral vertices from the split calculation, and makes k - 1 size-constrained cuts. In the author’s 61-dataset evaluation, its strongest configuration outperformed established methods including HDBSCAN and Genie.
Why cut a minimum spanning tree?
A minimum spanning tree, or MST, connects every point using n - 1 edges with the lowest possible total weight. Edges within a cluster tend to be shorter than edges between clusters. Deleting the k - 1 longest edges produces the same partition as single linkage clustering, including its sensitivity to chains of noisy or sparsely distributed points.
Lumbermark replaces raw Euclidean edge weights with mutual-reachability distance. For points x and y, the distance is d_M(x, y) = max(d(x, y), c_M(x), c_M(y)), where c_M is the distance to a point’s Mth nearest neighbor. Sparse points have larger core distances, which raises the weights of their incident edges and reduces their ability to bridge dense groups.
This story is for Pro members
You've reached the end of the free preview. Upgrade to AlphaSignal Pro to read the full article - and everything else behind the paywall.
Comments
