Name of this trivially simple clustering algorithm

Is there a name for the following (extremely simple) threshold-based clustering algorithm?

It does a pass over the data and creates a new cluster when no previous cluster is within a given distance threshold. Otherwise it assigns the point to the first close-enough cluster.

It's good enough if the data is already very well grouped and the within-cluster distances are only due to some tiny noise.

def cluster(data_points, threshold):
cluster_prototypes = []
labels = []
for p in data_points:
label = None
for i, c in enumerate(cluster_prototypes):
if distance(p, c) < threshold:
label = i
break
if label is None:
label = len(cluster_prototypes)
cluster_prototypes.append(p)
labels.append(label)
return labels


Looks like a trivial reformulation of Leader clustering to me.

An unlabeled point begins a new cluster, and all neighbors within a radius r are labeled. Repeat until everything is labeled.

• This seems like the nub of a decent idea. But it would be much more susceptible to the initial seed than k-means is. You would get very different results based on which point is labeled first w/i the data space. Is there any way to pick the right starting point or make the algorithm more robust to a poor starting point? May 9, 2019 at 15:20
• Thank you, it is indeed called "Leader clustering" (as in github.com/talegari/aleader). May 9, 2019 at 15:39
• @gung well, they differ by at most the radius r in distance to the representative, so this can work as data reduction / quantization technique like k-means with large k. I am a bit reluctant to call it a clustering, as I don't see a notion of "structure discovery" in this method. But it is in the Hartigan clustering book of 1975 if I am not mistaken. May 9, 2019 at 21:10
• If I understand the algorithm correctly, consider a case with 3 points in a line w/ distances just less than the radius. If the 1st point considered is the near end, the center would be w/i the radius & would be grouped w/ it, but the last point wouldn't (this 2 points in cluster 1, & 1 point in cluster 2). If the 1st point considered were the far end, you'd get 1 pattern in cluster 1, and 2 points in cluster 2. OTOH, if the middle point were the 1st considered, both the near & far ends would be grouped w/ it, leading to 1 cluster w/ 3 patterns. That seems pretty unstable to me. May 10, 2019 at 1:29
• Many clustering algorithms can have such instabilities, HAC with average linkage on (1,2,3) for example. I agree that Leader is worse though. But what I'd be more concerned is what to use it for. What is the semantics of the result, what conclusions can you draw from it? I don't think it gives a lot of insight into the data (I'd argue a random sample is better). And if you want to reduce the data size there are better approaches IMHO. May 10, 2019 at 6:20

It's slightly idffernet from k-means but instead of fixing the number of clusters at the beginning, you specify this rule :

creates a new cluster when no previous cluster is within a given distance threshold

which is not robust because the value of this threshold is fixed at the beginning. Moreover, depending on the initialization, it can change a lot the final classification ie if you shuffle your data, it won't be the same...

To reach the same goal, you should use the Elbow method that specifies the optimal number of clusters...

Hope it helps !