使用距离矩阵进行聚类

Question

我有一个（对称）矩阵

M

，表示每对节点之间的距离。例如，

 A B C D E F G H I J K L
0 20 20 20 40 60 60 60 100 120 120 120
乙 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
高 60 80 80 80 20 20 20 0 60 80 80 80
我 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
长 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)

。

Answer 1

层次聚类直接使用距离矩阵而不是实际观测值。如果你知道簇的数量，你就已经知道你的停止标准（当有 k 个簇时停止）。这里的主要技巧是选择合适的链接方法。此外，本文(pdf) 很好地概述了各种聚类方法。

Answer 2

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

Answer 3

嗯，可以对给定的相似度矩阵进行K均值聚类，首先需要将矩阵居中，然后取矩阵的特征值。最后也是最重要的一步是将前两组特征向量乘以特征值对角线的平方根以获得向量，然后继续使用 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)