Nodes clusters with a distance matrix

Question

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.

Answer 1

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.

Answer 2

Your matrix is called a "similarity matrix" in the literature. There are numerous algorithms that generate clusters. To begin, maybe review the relatively straightforward k-means and spectral methods. Wikipedia has a good overview.

http://en.wikipedia.org/wiki/Cluster_analysis

Answer 3

You can try affinity propagation, which doesn't require any assumptions about data living in vector spaces or the similarities coming from some metric. Code is available in a variety of languages: http://www.psi.toronto.edu/index.php?q=affinity%20propagation

Answer 4

Where do the distances in $M$ come from ? this is somewhat important. for example, is it guaranteed that $M$ is a metric (i.e satisfies triangle inequality) ? Further, are the distances simple Euclidean distances ? As an aside, how can you even run $k$-means ? $k$-means requires a vector space, so that centroids are well defined. In your example, you appear to be considering a discrete distance space.

While $k$-means and spectral clustering (which is really spectral dimensionality reduction followed by $k$-means) are fine algorithms, possibly a more important question to ask is: what kind of measure do you want to optimize ? $k$-means tries to (but doesn't) minimize the sum of squared distances between points in a cluster and their centroid.

In your example, you could ask for the $k$-clustering that minimizes the maximum radius of a cluster, where the radius is defined as $r = \min_{p \in C} \max_{q \in C} d(p,q)$. This is easy to approximate within a factor of 2 by picking $k$ maximally separated points.

Answer 5

Note, that in using a similarity matrix, you only find those elements that are connected to i. If you want to find the complete subset, you have to loop over the elements of the i-th subset and add unique components within d of those elements.

An example (in one dimension): Assume our elements are the integers I = [0, 1, 2, 3, 4, 5] if d >= 1 then there is one set: the original set. If d < 1 then there are 5 subsets. Note, when finding the similarity measure for 0, only 1 is appended (so the subset is S = [0,1]). you then have to append with the similarity measure for elements in S[0], namely, [1], so this adds 2 (and 0, but we only add unique elements). So S = unique(S union [0,1,2]), etc.

Taking this into consideration, I would like to see an efficient way of keeping track of elements in S to loop over (and removing them from I) so we can find all elements of our subsets.

Any efficient algorithms out there?