Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
add comment

5 Answers 5

up vote 1 down vote accepted

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.

share|improve this answer
add comment

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

share|improve this answer
    
Thanks for your answer. I've already tried k-means, but the resulting clusters are not so good. Could you please give me more information about the spectral methods? Thanks again. –  Yassin Ezbakhe Sep 15 '10 at 20:26
    
A major practical difference is the scaling parameter $\sigma$ offered by spectral clustering. The following paper is a very quick read. On Spectral Clustring: Analysis and an algorithm –  dls Sep 16 '10 at 2:30
1  
not to be picky, but the matrix as defined by the OP is actually a distance matrix, not a similarity matrix. –  Suresh Venkat Sep 16 '10 at 5:20
add comment

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

share|improve this answer
    
Looks very good. I'm sorry I can't give you a +1 (I don't have enough reputation) –  Yassin Ezbakhe Sep 17 '10 at 9:04
add comment

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.

share|improve this answer
    
The distances are the average steps a random walker would take to go from node $A$ to node $B$ ($\= A$) and go back to node $A$. It's guaranteed that $\sqrt{M}$ is a metric. To run $k$-means, I don't use the centroid. I define the distance between node $n$ and cluster $c$ as the average distance between $n$ and all nodes in $c$. (Is this correct?) Thanks! –  Yassin Ezbakhe Sep 16 '10 at 8:59
    
@Yassin Ezbakhe, exactly what program or algorithm are you using to iterate your k-means calculations? While you have a distance metric between pairs of entries, what is the origin of the value being measured? The actual value of the item is the vector in the space which will have the distance metric. What are the original descriptors of these items? Understanding that might help in answering this type of question. –  sleepless in beantown Sep 16 '10 at 12:15
add comment

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?

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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