Hi,


I have a (symmetric) matrix $M$ that represents the distance between each pair of nodes. For example,



```

    A   B   C   D   E   F   G   H   I   J   K   L
A   0  20  20  20  40  60  60  60 100 120 120 120
B  20   0  20  20  60  80  80  80 120 140 140 140
C  20  20   0  20  60  80  80  80 120 140 140 140
D  20  20  20   0  60  80  80  80 120 140 140 140
E  40  60  60  60   0  20  20  20  60  80  80  80
F  60  80  80  80  20   0  20  20  40  60  60  60
G  60  80  80  80  20  20   0  20  60  80  80  80
H  60  80  80  80  20  20  20   0  60  80  80  80
I 100 120 120 120  60  40  60  60   0  20  20  20
J 120 140 140 140  80  60  80  80  20   0  20  20
K 120 140 140 140  80  60  80  80  20  20   0  20
L 120 140 140 140  80  60  80  80  20  20  20   0

```

Is there a method to extract clusters from $M$ (if needed, the number of clusters can be fixed), such that each cluster contains nodes with small distances between them. In the example, the clusters would be (A, B, C, D), (E, F, G, H) and (I, J, K, L).


Thanks a lot.



Nodes clusters with a distance matrix
The best answer is **distance threshold**. Look at the problem as defining an undirected graph based on a given distance matrix and trying to create subcomponents of the graph by selectively deleting edges based on the weight of each edge as defined by the distance.


If you make the assumption that the underlying metric space (which you have not clearly defined in this case) is Euclidean (linear and therefore homogeneous throughout, I believe), then one simple way of creating subsets of your elements from the distance matrix which you have available is the following.
(*edit*: No assumtion of homogeneity of the underlying metric space is actually required for this approach of selectively deleting edges.)



> 
> Given a distance matrix $M$ with elements $M\_{i,j}$ describing a distance between the elements $i$ and $j$ where $i\in S$ and $j\in S$, and $S$ is the set of items you are attempting to separate into subsets (hopefully disjunct)
> 
> 
> define a **binary matrix** which describes whether element $i$ is in the same subset as element $j$ by using a **distance threshold**, $d$.
> 
> 
> $D$ = the matrix with elements 
> 
> 
> $D\_{i,j}=0$ if $M\_{i,j}\ge d$ or if $i=j$, and 
> 
> 
> $D\_{i,j}=1$ if $M\_{i,j} < d$ and $i \ne j$
> 
> 
> use this binary matrix to draw a graph, and call each separate **connected component** of the graph a separate **cluster**
> 
> 
> 


If it is possible to separate the elements of your set $S$ into disjunct partitions, there is a minimum distance $d\_{min}$ that you can use.


For example, setting the distance threshold to $40$ allows the partitioning of $S$ into disjunct (non-intersecting) subsets:



```
0   1   1   1   0   0   0   0   0   0   0   0
1   0   1   1   0   0   0   0   0   0   0   0
1   1   0   1   0   0   0   0   0   0   0   0
1   1   1   0   0   0   0   0   0   0   0   0
0   0   0   0   0   1   1   1   0   0   0   0
0   0   0   0   1   0   1   1   0   0   0   0
0   0   0   0   1   1   0   1   0   0   0   0
0   0   0   0   1   1   1   0   0   0   0   0
0   0   0   0   0   0   0   0   0   1   1   1
0   0   0   0   0   0   0   0   1   0   1   1
0   0   0   0   0   0   0   0   1   1   0   1
0   0   0   0   0   0   0   0   1   1   1   0

```

Now, drawing the graph structure of this binary matrix leads to a three component graph composed of these three graphs (which all happen to be $K\_4$, the complete graph on 4 vertices) with vertex sets composed of 


* {A, B, C, D}
* {E, F, G, H}
* {I, J, K, L}




---


However, the binary matrix for the undirected graph "in the same cluster" using distance $d<50$ as the threshold results in



```
0   1   1   1   1   0   0   0   0   0   0   0
1   0   1   1   0   0   0   0   0   0   0   0
1   1   0   1   0   0   0   0   0   0   0   0
1   1   1   0   0   0   0   0   0   0   0   0
1   0   0   0   0   1   1   1   0   0   0   0
0   0   0   0   1   0   1   1   1   0   0   0
0   0   0   0   1   1   0   1   0   0   0   0
0   0   0   0   1   1   1   0   0   0   0   0
0   0   0   0   0   1   0   0   0   1   1   1
0   0   0   0   0   0   0   0   1   0   1   1
0   0   0   0   0   0   0   0   1   1   0   1
0   0   0   0   0   0   0   0   1   1   1   0

```

A distance threhold of 50 does not break the dataset into disjunct sets, as when you follow the linkages all of the elements are effectively connected by certain bridging elements. If you draw this as a graph structure, you will see that there are subgraphs


* {B,C,D}
* {F,G,H}
* {J,K,L}
* with bridging element A connecting {B,C,D} and E
* and bridging element F connects to bridging element I,
* etc.




---


For the example distance matrix which you have given, setting the threshold $20 \le d \lt 40$ will give you what looks like a correct result. Setting $d$ too low results in more isolated components to the graph, setting $d$ too high leads to larger components.



> 
> There is no guarantee that there will be a threhold $d\_{min}$ which will separate such a set into disjunct subsets.
> 
> 
> 


For example, if you set the distances between A and E to zero, and the distances between F and I to zero, there is no threshold which will separate the sets using only the distance matrix.


You may have to "manually" adjust the **distance threshold** to get the best separation of the set into disjunct subsets, if such a partitioning exists.


