Lumbermark: Resistant Clustering by Chopping Up Mutual Reachability Minimum Spanning Trees
Authors: Marek Gagolewski
Organizations: Warsaw University of Technology, Faculty of Mathematics and Information Science, ul. Koszykowa 75, 00-662 Warsaw, Poland · Systems Research Institute, Polish Academy of Sciences, ul. Newelska 6, 01-447 Warsaw, Poland
We introduce Lumbermark, a robust divisive clustering algorithm capable of detecting clusters of varying sizes, densities, and shapes. Lumbermark iteratively chops off large limbs connected by protruding segments of a dataset's mutual reachability minimum spanning tree. The use of mutual reachability distances smoothens the data distribution and decreases the influence of low-density objects, such as noise points between clusters or outliers at their peripheries. The algorithm can be viewed as an alternative to HDBSCAN that produces partitions with user-specified sizes. A fast, easy-to-use implementation of the new method is available in the open-source 'lumbermark' package for Python and R. We show that Lumbermark performs well on benchmark data and hope it will prove useful to data scientists and practitioners across different fields.
Figures & tables
Figure 1: Three copies of an example dataset with four clusters: two horizontal segments and two Gaussian blobs connected by a point chain. Additionally, its Euclidean minimum spanning tree (left) as well as two 25-mutual reachability minimum spanning trees (centre, right) are depicted. Edge colour intensities correspond to the underlying distances with the darkest edge being the longest in each case. By increasing the smoothing parameter M , we make the blobs better separable but the close-lying segments become blended. There are many more possible minimum spanning trees for d25 and they can have very diverse topologies. In the current paper, we adjust the mutual reachability distance (Eq. ( 2 ); centre) so that forming edges between point pairs with smaller original (Euclidean) distances is preferred.
Lumbermark
K-Means
Gauss-
(*) HDBSCAN
Spec-
d
k
n
M=1
M=10
++
random
Mix
fast
std
Ward
tral
2
2
10,000
0.01
0.01
0.00
0.02
0.02
0.05
0.15
1.37
11.86
100,000
0.07
0.09
0.02
0.09
0.12
0.66
2.27
1,000,000
1.23
1.33
0.16
0.59
1.04
21.18
10
10,000
0.01
0.01
0.01
0.04
0.05
1.36
12.27
100,000
0.10
0.11
0.05
0.20
0.69
Table 1: Run times in seconds (6 threads), medians of 5: Detecting k clusters in random datasets with n points in Rd .
<.8
≥.95
Med
Mean
<.8
≥.95
Med
Mean
Third-party labels only (25)
All labels (61 instances)
Lumbermark_f0.25_M5
4
15
0.98
0.91
11
41
1.00
0.89
Lumbermark_f0.25_M1
6
12
0.94
0.89
14
37
1.00
0.88
Genie_G0.3_M3
7
12
0.95
0.86
16
38
0.99
0.87
Genie_G0.3_M1
7
12
0.94
0.85
18
35
0.99
0.85
Spectral
8
13
0.96
0.83
30
24
0.86
0.69
Table 2: Aggregated adjusted Rand indices for different algorithms.
Figure 2: Proportion of datasets with AR ≥0.95 and <0.8 and the average AR as a function of min_cluster_factor f and smoothing parameter M in the case of the Lumbermark algorithm on 47 datasets. Datasets with imbalanced and balanced reference cluster counts are studied separately.
Figure 3: Proportion of datasets with AR ≥0.95 and <0.8 and the average AR as a function of the Gini index threshold G and smoothing parameter M in the case of the Genie algorithm on 47 datasets. Datasets with imbalanced and balanced reference cluster counts are studied separately.
1UHasselt, Data Science Institute (DSI) · 2Tutte Institute for Mathematics and Computing · 3KU Leuven, Augmented Intelligence for Data Analytics Lab, Department of Biosystems
School of Computer Science, University of Auckland, New Zealand. · Department of Mathematics and Computer Science, University of Southern Denmark, Denmark.