Clusters based on distance

Question

Here is my problem: I have a list of villages. For each village I computed the path distance between them and prepared a distance matrix. Now I want to identify clusters of villages which are close to each other.

I use Python 2.7 and I already used hierarchical clustering (provided by scypy) to cluster the distance matrix. By looking at it as a human being, I can identify the nearest villages, but I need to automate it. I need to get the elements which belong to each cluster.

Where does "word distance" come into play here?!? Are you really looking into clusters? Because your description reads as if you want to find the nearest neighbors instead. — Has QUIT--Anony-Mousse
I have made a mistake in the topic. Thanks for pointing it out. I simply need to cluster set of points based on distance. — user2650936
So you tried hierarchical clustering. What was wrong with the result? — Has QUIT--Anony-Mousse
Yes it gives me a diagram with hierarchical clustering. But I need to retrieve the elements belong to each cluster. — user2650936

amquack amquack · Accepted Answer · 2019-06-25T18:18:05

I was also wondering how to retrieve the clusters once I had created and cut the dendrogram. Since this is unanswered and may come up for others with a similar question, I'll answer according to what I was looking for, making some assumptions since this is an old question.

The first step is that you need to determine where to cut the dendrogram. You can do this a variety of ways, but I'll assume you already know how to do this, since you're looking at the dendrogram and seem to have satisfied yourself that you have clustered the data. If you don't know where to cut, you could start with something simple like cutting at the max distance. But really, where to cut is a different, very long discussion which I will assume you have figured out how to do (since I had done so at this point in my search).

Now I assume you have a dendrogram, and you know where to cut it, and maybe you even have it plotted with the cut line. But you want to do something more with the clusters, so you need to label the points you clustered. This can be done using the flat cluster (fcluster()) function in scipy.

from scipy.cluster.hierarchy import fcluster

clusters=fcluster(Z,distance,criterion='distance')
print(clusters)

Z is the hierarchical linkage matrix (as from scipy's linkage() function) which I assume you had already created. distance is the distance at which you are cutting the dendrogram (but there are other ways to cut the dendrogram, see source for how to do this with fcluster).

This returns a numpy array denoting which observation is in which cluster. Now you can append this to your data as a new column and go to town (or village) with it.

Clusters based on distance

1 Answers