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