# Clustering symmetric distance matrix

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?

– Sycorax
Nov 29, 2017 at 14:46
• 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.
– whuber
Nov 29, 2017 at 16:00
• @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). Nov 29, 2017 at 16:16
• @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. Nov 29, 2017 at 16:22
• 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.
– whuber
Nov 29, 2017 at 16:39