有多种选择。

k-中心点聚类

首先，您可以尝试围绕中心点 (pam) 进行分区，而不是使用 k-means 聚类。这个更健壮，并且可以提供更好的结果。Van der Laan 重新设计了算法。如果您要自己实现它，他的文章值得一读。

对于大型数据集，有一个特定的 k-medoids 聚类算法。该算法在 R 中称为 Clara，并在“ 查找数据组：聚类分析简介”的第 3 章中进行了描述。Kaufman, L 和 Rousseeuw, PJ (1990)。

层次聚类

除了 UPGMA，您可以尝试其他一些层次聚类选项。首先，当你使用层次聚类时，一定要正确定义分区方法。这种划分方法本质上是如何计算观测值和聚类之间的距离。我主要使用 Ward 的方法或完整的链接，但其他选项可能是您的选择。

不知道您是否尝试过，但在系统发育应用中，单链接方法或邻居连接通常优于 UPGMA。如果你还没有尝试过，你也可以试一试，因为它通常会产生非常好的结果。

---

在 R 中，您可以查看包cluster。所有描述的算法都在那里实现。参见 ?pam, ?clara, ?hclust, ... 检查 ?kmeans 中算法的不同实现。有时选择另一种算法可以显着改善聚类。

---

编辑：只是想到了一些事情：如果您使用图形和节点等，您也应该看看马尔可夫聚类算法。例如，它用于根据爆炸相似性对序列进行分组，并且表现得非常好。它可以为你做聚类，或者给你一些关于如何解决你关注的研究问题的想法。事实上，在不知道任何事情的情况下，我想他的结果绝对值得一看。如果我可以这样说，我仍然认为 Stijn van Dongen 的这种方法是我遇到过的最好的聚类结果之一。

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

在距离矩阵上突出显示集群的一种方法是多维缩放。当在 2D 空间中投影个体（此处称为节点）时，它提供了与 PCA 相当的解决方案。这是无监督的，因此您将无法先验地指定聚类的数量，但我认为它可能有助于快速总结给定的距离或相似度矩阵。

以下是您将获得的数据：

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")

我在 x 和 y 坐标上添加了一个小的抖动，以便区分情况。如果您更喜欢处理不同之处，请替换tmp为1-tmp，但这会产生基本相同的图片。然而，这里是层次聚类解决方案，具有单一的聚集标准：

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

您可以根据树状图或更稳健的方法进一步细化集群的选择，例如参见这个相关问题：What stop-criteria for aagglomerative hierarchy clustering are used in practice？

您正在做的是尝试将彼此靠近的图或网络的节点聚集在一起。有一个专门研究这个问题的整个领域，有时称为网络中的社区检测。从这个角度来看你的问题可能会澄清一些事情。

您会发现许多专门解决此问题的算法，实际上其中一些基于与您相同的想法，即使用随机游走测量节点之间的距离。

该问题通常被表述为模块化优化[1]，其中集群的模块化衡量集群在密集连接的集群（即节点彼此靠近的集群）中分离网络的程度。

实际上，您可以证明模块化等于随机游走者在一步后停留在相同集群中的概率，而不是最初减去两个独立随机游走者的相同概率[2]。

如果您允许随机游走者的更多步骤，则您正在寻找更粗略的网络聚类。因此，随机游走的步数起到了分辨率参数的作用，它允许恢复集群的层次结构。在这种情况下，表示随机游走者在t步后停留在其初始集群中的趋势的量称为时间 t [2] 时分区的马尔可夫稳定性，它等效于t=1时的模块化。

因此，您可以通过找到在给定时间t优化稳定性的图形聚类来解决您的问题，其中t是分辨率参数（更大的t会给您更大的聚类）。优化稳定性（或具有分辨率参数的模块化）的最常用方法之一是Louvain 算法[3]。你可以在这里找到一个实现：https ://github.com/michaelschaub/generalizedLouvain 。

[1] Newman, MEJ & Girvan, M. 发现和评估网络中的社区结构。物理。修订版 E 69, 026113 (2004)。

[2] Delvenne, J.-C., Yaliraki, SN & Barahona, M. 图社区跨时间尺度的稳定性。过程。国家石油公司。学院派。科学。107, 12755–12760 (2010)。

[3] Blondel, VD, Guillaume, J.-L., Lambiotte, R. & Lefebvre, E. 大型网络中社区的快速展开。J.统计。机甲。理论实验。2008, P10008 (2008)。

谱聚类 [1] 需要一个亲和矩阵，聚类由$K$分解的第一特征函数

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

和$\textbf{A}$是数据的亲和矩阵，并且$\textbf{D}$是定义为的对角矩阵（编辑：抱歉不清楚，但您可以从距离矩阵生成亲和矩阵，前提是您知道最大可能/合理距离为$A_{ij}=1-d_{ij}/\max(d)$，尽管也存在其他方案）

$$\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.$$

\ textbf是的特征分解，特征函数堆叠为列，仅保留个最大特征向量，我们定义行归一化矩阵$\textbf{X}$$\textbf{L}$$K$$\textbf{X}$

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

的每一行都是中的一个点，可以用普通的聚类算法（如 K-means）进行聚类。$\textbf{Y}$$\mathbb{R}^{k}$

在此处查看我的答案以查看示例：https ://stackoverflow.com/a/37933688/2874779

---

_{[1] Ng, AY, Jordan, MI, & Weiss, Y. (2002)。关于谱聚类：分析和算法。神经信息处理系统的进展，2, 849-856。第2页}