Clustering with a distance matrix

Question

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 any 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).

I've already tried UPGMA and k-means but the resulting clusters are very bad.

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 M^1/2 is a metric. To run k-means, I don't use the centroid. I define the distance between node n cluster c as the average distance between n and all nodes in c.

Thanks a lot :)

Answer 1

There are a number of options.

k-medoids clustering

First, you could try partitioning around medoids (pam) instead of using k-means clustering. This one is more robust, and could give better results. Van der Laan reworked the algorithm. If you're going to implement it yourself, his article is worth a read.

There is a specific k-medoids clustering algorithm for large datasets. The algorithm is called Clara in R, and is described in chapter 3 of Finding Groups in Data: An Introduction to Cluster Analysis. by Kaufman, L and Rousseeuw, PJ (1990).

hierarchical clustering

Instead of UPGMA, you could try some other hierarchical clustering options. First of all, when you use hierarchical clustering, be sure you define the partitioning method properly. This partitioning method is essentially how the distances between observations and clusters are calculated. I mostly use Ward's method or complete linkage, but other options might be the choice for you.

Don't know if you tried it yet, but the single linkage method or neighbour joining is often preferred above UPGMA in phylogenetic applications. If you didn't try it yet, you could give it a shot as well, as it often gives remarkably good results.

---

In R you can take a look at the package cluster. All described algorithms are implemented there. See ?pam, ?clara, ?hclust, ... Check also the different implementation of the algorithm in ?kmeans. Sometimes chosing another algorithm can improve the clustering substantially.

---

EDIT : Just thought about something: If you work with graphs and nodes and the likes, you should take a look at the markov clustering algorithm as well. That one is used for example in grouping sequences based on blast similarities, and performs incredibly well. It can do the clustering for you, or give you some ideas on how to solve the research problem you're focusing on. Without knowing anything about it in fact, I guess his results are definitely worth looking at. If I may say so, I still consider this method of Stijn van Dongen one of the nicest results in clustering I've ever encountered.

http://www.micans.org/mcl/

Answer 2

One way to highlight clusters on your distance matrix is by way of Multidimensional scaling. When projecting individuals (here what you call your nodes) in an 2D-space, it provides a comparable solution to PCA. This is unsupervised, so you won't be able to specify a priori the number of clusters, but I think it may help to quickly summarize a given distance or similarity matrix.

Here is what you would get with your data:

tmp <- matrix(c(0,20,20,20,40,60,60,60,100,120,120,120,
                20,0,20,20,60,80,80,80,120,140,140,140,
                20,20,0,20,60,80,80,80,120,140,140,140,
                20,20,20,0,60,80,80,80,120,140,140,140,
                40,60,60,60,0,20,20,20,60,80,80,80,
                60,80,80,80,20,0,20,20,40,60,60,60,
                60,80,80,80,20,20,0,20,60,80,80,80,
                60,80,80,80,20,20,20,0,60,80,80,80,
                100,120,120,120,60,40,60,60,0,20,20,20,
                120,140,140,140,80,60,80,80,20,0,20,20,
                120,140,140,140,80,60,80,80,20,20,0,20,
                120,140,140,140,80,60,80,80,20,20,20,0),
              nr=12, dimnames=list(LETTERS[1:12], LETTERS[1:12]))
d <- as.dist(tmp)
mds.coor <- cmdscale(d)
plot(mds.coor[,1], mds.coor[,2], type="n", xlab="", ylab="")
text(jitter(mds.coor[,1]), jitter(mds.coor[,2]),
     rownames(mds.coor), cex=0.8)
abline(h=0,v=0,col="gray75")

I added a small jittering on the x and y coordinates to allow distinguishing cases. Replace tmp by 1-tmp if you'd prefer working with dissimilarities, but this yields essentially the same picture. However, here is the hierarchical clustering solution, with single agglomeration criteria:

plot(hclust(dist(1-tmp), method="single"))

You might further refine the selection of clusters based on the dendrogram, or more robust methods, see e.g. this related question: What stop-criteria for agglomerative hierarchical clustering are used in practice?

Answer 3

What you're doing is trying to cluster together nodes of a graph, or network, that are close to each other. There is a entire field of research dedicated to this problem which is sometimes called community detection in networks. Looking at your problem from this point of view can probably clarify things.

You will find many algorithms dedicated to this problem and in fact some of them are based on the same idea that you had, which is to measure distances between nodes with random walks.

The problem is often formulated as modularity optimization [1] where the modularity of a clustering measures how well the clustering separates the network in densely connected clusters (i.e. clusters where nodes are close to each others).

Actually, you can show that the modularity is equal to the probability that a random walker stays, after one step, in the same clusters than initially minus the same probability for two independent random walkers [2].

If you allow for more steps of the random walkers, you are looking for a coarser clustering of the network. The number of steps of the random walk plays therefore the role of a resolution parameter that allows to recover a hierarchy of clusters. In this case, the quantity that expresses the tendency of random walkers to stay in their initial cluster after t steps is called the Markov stability of a partition at time t [2] and it is equivalent to the modularity when t=1.

You can therefore solve your problem by finding the clustering of your graph that optimizes the stability at a given time t, where t is the resolution parameter (larger t will give you larger clusters). One of the most used method to optimize the stability (or modularity with a resolution parameter) is the Louvain Algorithm [3]. You can find an implementation here: https://github.com/michaelschaub/generalizedLouvain.

[1] Newman, M. E. J. & Girvan, M. Finding and evaluating community structure in networks. Phys. Rev. E 69, 026113 (2004).

[2] Delvenne, J.-C., Yaliraki, S. N. & Barahona, M. Stability of graph communities across time scales. Proc. Natl. Acad. Sci. 107, 12755–12760 (2010).

[3] Blondel, V. D., Guillaume, J.-L., Lambiotte, R. & Lefebvre, E. Fast unfolding of communities in large networks. J. Stat. Mech. Theory Exp. 2008, P10008 (2008).

Answer 4

Spectral Clustering [1] requires an affinity matrix, clustering being defined by the $K$ first eigenfunctions of the decomposition of

$$\textbf{L} = \textbf{D}^{-1/2} \textbf{A} \textbf{D}^{-1/2}$$

With $\textbf{A}$ being the affinity matrix of the data and $\textbf{D}$ being the diagonal matrix defined as (edit: sorry for being unclear, but you can generate an affinity matrix from a distance matrix provided you know the maximum possible/reasonable distance as $A_{ij}=1-d_{ij}/\max(d)$, though other schemes exist as well)

$$\left\{\begin{matrix}\begin{align}&\textbf{D}_{i,i}=\sum_{j}{\textbf{A}_{i,j}}\\ &\textbf{D}_{i \neq j}=0\end{align}\end{matrix}\right.$$

With $\textbf{X}$ being the eigendecomposition of $\textbf{L}$, with eigenfunctions stacked as columns, keeping only the $K$ largest eigenvectors in $\textbf{X}$, we define the row normalized matrix

$$\textbf{Y}_{ij}=\frac{\textbf{X}_{ij}}{\left(\sum_{j}{\left( \textbf{X}_{ij} \right)^{2}}\right)^{1/2}}$$

Each row of $\textbf{Y}$ is a point in $\mathbb{R}^{k}$ and can be clustered with an ordinary clustering algorithm (like K-means).

Look at my answer here to see an example: https://stackoverflow.com/a/37933688/2874779

---

_{[1] Ng, A. Y., Jordan, M. I., & Weiss, Y. (2002). On spectral clustering: Analysis and an algorithm. Advances in neural information processing systems, 2, 849-856. Pg.2}

Answer 5

Well, It is possible to perform K-means clustering on a given similarity matrix, at first you need to center the matrix and then take the eigenvalues of the matrix. The final and the most important step is multiplying the first two set of eigenvectors to the square root of diagonals of the eigenvalues to get the vectors and then move on with K-means . Below the code shows how to do it. You can change similarity matrix. fpdist is the similarity matrix.

mds.tau <- function(H)
{
  n <- nrow(H)
   P <- diag(n) - 1/n
   return(-0.5 * P %*% H %*% P)
  }
  B<-mds.tau(fpdist)
  eig <- eigen(B, symmetric = TRUE)
  v <- eig$values[1:2]
#convert negative values to 0.
v[v < 0] <- 0
X <- eig$vectors[, 1:2] %*% diag(sqrt(v))
library(vegan)
km <- kmeans(X,centers= 5, iter.max=1000, nstart=10000) .
#embedding using MDS
cmd<-cmdscale(fpdist)

Answer 6

Co-clustering is one of the answers I think. But Im not expert here. Co-clustring isn't newborn method, so you can find some algos in R, wiki shows that concepts in good way. Another method that isnt menthioned is graph partitioning (but I see that graph wouldnt be sparse,graph partitioning would be useful if your matrix would be dominated by values meaning=maximum distance=no similarity between the nodes).

Answer 7

Look into AFFINITY PROPAGATION, This technique takes as input the similarity matrix and produces an optimal number of clusters along with a representative example for each cluster.

Answer 8

You can also use the Kruskal algorithm for finding minimum spanning trees, but ending as soon as you get the three clusters. I tried this way and it produces the clusters you mentioned: {ABCD}, {EFGH} and {IJKL}.

Answer 9

Before you try running the clustering on the matrix you can try doing one of the factor analysis techniques, and keep just the most important variables to compute the distance matrix. Another thing you can do is to try use fuzzy-methods which tend to work better (at least in my experience) in this kind of cases, try first Cmeans, Fuzzy K-medoids, and Specially GKCmeans.