2
$\begingroup$

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
Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ 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? $\endgroup$
    – gung - Reinstate Monica
    May 9, 2019 at 15:20
  • $\begingroup$ Thank you, it is indeed called "Leader clustering" (as in github.com/talegari/aleader). $\endgroup$
    – isarandi
    May 9, 2019 at 15:39
  • $\begingroup$ @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. $\endgroup$
    – Has QUIT--Anony-Mousse
    May 9, 2019 at 21:10
  • $\begingroup$ 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. $\endgroup$
    – gung - Reinstate Monica
    May 10, 2019 at 1:29
  • $\begingroup$ 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. $\endgroup$
    – Has QUIT--Anony-Mousse
    May 10, 2019 at 6:20
0
$\begingroup$

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 !

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.