Skip to main content
Back

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.

Paper, Full Access
  • 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.

Comparison of Euclidean and mutual-reachability minimum spanning trees
Mutual reachability raises edge weights around sparse points, weakening chains between dense groups.

How Lumbermark chooses its cuts