0
$\begingroup$

Below is a symmetric matrix $A$ with distances between observation $i$ and $j$.

$$ \begin{matrix} 0 & 9 & 8 & 6 & 3\\ 9 & 0 & 1 & 7 & 8\\ 8 & 1 & 0 & 6 & 9\\ 6 & 7 & 6 & 0 & 7\\ 3 & 8 & 9 & 7 & 0\\ \end{matrix} $$

My goal is to assign these into separate groups/clusters such the distance between observations within the group is minimized.

For example, the distance between observation 2 and 3 is 1 ($A_{23}$)

The distance between observation 1 and 5 is 3 ($A_{15}$)

According to that, observation 2 and 3 are likely to be part of the same "cluster". 1 and 5 also have a small distance of 3 between them, which also mean they should be part of the same "cluster". As you can see, observation 4 is very far from any other observation, which means it should be assigned to another "cluster".

The types of groups I initially trying to achieve according to the above example is as follows:

Cluster 1: observations 1, 5
Cluster 2: observations 2, 3
Cluster 3: observation 4

Do you know of an algorithm that can answer this kind of a problem?

Improve this question
$\endgroup$
6
  • $\begingroup$ cs.cmu.edu/~aarti/Class/10701/readings/Luxburg06_TR.pdf $\endgroup$
    – Sycorax ♦
    Nov 29 '17 at 14:46
  • $\begingroup$ This is not a distance matrix! The zeros at positions (2,5) and (5,2) indicate that the corresponding objects are co-located. Therefore they must exhibit identical distances to all other objects: this would be manifested as identical columns 2 and 5 and identical rows 2 and 5, but that's far from the case. Any attempt at clustering that assumes these are distances would therefore be invalid, in the off chance it actually succeeded. $\endgroup$
    – whuber ♦
    Nov 29 '17 at 16:00
  • $\begingroup$ @whuber indeed you're right, I did not think of that when I created this example. It is meant to be a distance matrix - I will change the distances to remove the co-located points at (2,5). $\endgroup$
    – Flika205
    Nov 29 '17 at 16:16
  • $\begingroup$ @whuber Also as far as that's relevant distance here is more conceptual. i.e. "distance between observations" not distance in the sense of kilometers on a 2d plane. $\endgroup$
    – Flika205
    Nov 29 '17 at 16:22
  • 1
    $\begingroup$ It's not valid to call it a distance unless it satisfies the triangle inequality. My previous comment provides a simple demonstration that your matrix violates the triangle inequality. Many clustering methods assume the triangle inequality is satisfied, so it's important to be clear concerning whether your actual problem concerns a true distance matrix or not. $\endgroup$
    – whuber ♦
    Nov 29 '17 at 16:39
1
$\begingroup$

Use hierarchical clustering.

This gives you the best control over how distances of groups are computed. Because there is more than one way of linking.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Hey Anony-Mousse, thank you for your suggestion, I'm currently looking at the documentation of it. May I ask to see an example of how this can be used with symmetric distance matrix? Thanks $\endgroup$
    – Flika205
    Nov 30 '17 at 9:26
  • $\begingroup$ You call agnes(X) $\endgroup$
    – Has QUIT--Anony-Mousse
    Dec 1 '17 at 1:13
  • $\begingroup$ The mentioned function is in R, right? I'm working on a project in Python, do you know what is the equivalent function in Python maybe? Thanks. $\endgroup$
    – Flika205
    Dec 1 '17 at 9:07
  • $\begingroup$ Yes, that also exist in scipy and takes about 10 second to find. $\endgroup$
    – Has QUIT--Anony-Mousse
    Dec 2 '17 at 10:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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