基于距离矩阵的聚类

Question

我有一个表示每对节点之间距离的（对称）矩阵M。例如：

    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

是否有一种方法从M中提取聚类（如果需要，可固定聚类数量），以使每个聚类包含距离较小的节点。 在本例中，聚类将是(A,B,C,D)、(E,F,G,H)和(I,J,K,L)。

非常感谢 :)

- yassin

Answer 1

层次聚类 直接使用距离矩阵而不是实际观测值。如果您知道聚类数目，则已经知道了停止准则（当有k个聚类时停止）。这里的主要技巧将是选择适当的 链接方法。此外，这篇论文（pdf）提供了各种聚类方法的优秀概述。

- Björn Pollex

---

我已经尝试了UPGMA，但得到的聚类结果很糟糕。有什么想法吗？ - yassin

如果我正确理解了您的距离矩阵，那么您的聚类非常分离。在这种情况下，单链接和完全链接应该很有效。您可以尝试将此发布在http://stats.stackexchange.com上，那里有更专业的人员处理此类主题。 - Björn Pollex

Answer 2

另一种可能的方法是使用分割中心，通常称为K-Medoids。如果您查看R-clustering包，您将看到pam函数，它接收距离矩阵作为输入数据。

- NtsDK

Answer 3

嗯，可以在给定的相似度矩阵上执行K-means聚类，首先需要对矩阵进行居中处理，然后取出矩阵的特征值。最后且最重要的一步是将前两组特征向量乘以特征值的对角线平方根以获得向量，然后继续使用K-means。下面的代码展示了如何实现它。您可以更改相似度矩阵。fpdist是相似度矩阵。

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)

- user4959