方法概述

关于层次凝聚聚类分析（HAC）的一些链接方法的简短参考。

HAC算法的基本版本是一种通用的；它相当于在每一步通过称为 Lance-Williams 公式的公式更新新兴（两个合并）集群与迄今为止存在的所有其他集群（包括单例对象）之间的接近度。存在不使用 Lance-Williams 公式的实现。但是使用起来很方便：它可以让一个人用同一个模板编写各种链接方法。

递归公式包括几个参数（α、β、γ）。根据链接方法，参数设置不同，因此展开公式获得特定视图。许多关于 HAC 的文本都显示了该公式、其特定于方法的观点并解释了这些方法。我会推荐 Janos Podani 的文章非常详尽。

不同方法的空间和需求源于这样一个事实，即两个集群之间或一个集群与一个单一对象之间的接近度（距离或相似性）可以用许多不同的方式来表述。HAC在每一步合并两个最接近的簇或点，但是在输入接近矩阵仅在单例对象之间定义的情况下，如何计算上述接近度是需要制定的问题。

因此，这些方法在每一步如何定义任意两个集群之间的接近度方面有所不同。“碰撞系数”（聚集时间表/历史中的输出并在树状图上形成“Y”轴）只是在给定步骤合并的两个集群之间的接近度。

• 单联动或最近邻法。两个簇之间的接近度是它们两个最近的物体之间的接近度。该值是输入矩阵的值之一。这种集群构建的概念隐喻，它的原型，是频谱或链。链条可以是直的或曲线的，也可以是“雪花”或“变形虫”视图。与两个最相似的集群成员相比，两个最不相似的集群成员可能恰好非常不同。单链接方法仅控制最近邻相似性。

• 完全联动或最远邻居的方法。两个集群之间的接近度是它们两个最远的物体之间的接近度。该值是输入矩阵的值之一。这种集群构建的隐喻是圆形（在某种意义上，通过爱好或情节），其中两个彼此最远的成员不能比其他完全不同的对（如圆形）更加不同。这样的簇的边界是“紧凑”的轮廓，但它们内部不一定是紧凑的。

• 组间平均联系法（UPGMA）。两个簇之间的接近度是一侧的一个对象与另一侧的另一个对象之间的所有接近度的算术平均值。这种集群构建的隐喻非常笼统，只是团结的阶级或紧密结合的集体；该方法在层次聚类包中经常设置为默认方法。可以产生各种形状和轮廓的簇。

• 简单平均，或平衡组间平均关联法(WPGMA) 是修改前的方法。两个簇之间的接近度是一侧的一个对象与另一侧的另一个对象之间的所有接近度的算术平均值；而这两个集群中的每一个最近合并的子集群对这种接近度的影响是相等的——即使子集群的对象数量不同。

• 组内平均联系法（MNDIS）。两个簇之间的邻近度是它们联合簇中所有邻近度的算术平均值。此方法是 UPGMA 的替代方法。它通常会在集群密度方面输给它，但有时会发现 UPGMA 不会发现的集群形状。

• 质心法（UPGMC）。两个集群之间的接近度是它们几何质心之间的接近度：它们之间的[平方]欧几里得距离。这种集群构建的隐喻是平台（政治）的接近性。就像在政党中一样，这样的集群可以有小部分或“派别”，但除非他们的核心人物彼此分开，否则联盟是一致的。集群的轮廓可以是不同的。

• 中值或平衡质心法 (WPGMC) 是修改前的方法。两个簇之间的接近度是它们几何质心之间的接近度（它们之间的[平方]欧几里得距离）；而质心的定义是为了使这两个集群中的每一个最近合并的子集群对其质心具有均衡的影响——即使子集群的对象数量不同。名称“中位数”部分具有误导性，因为该方法不使用数据分布的中位数，它仍然基于质心（均值）。

• Ward 的方法，或最小平方和(MISSQ) 增加，有时被错误地称为“最小方差”方法。两个集群之间的接近度是其联合集群中的平方和将大于这两个集群中的组合平方和的大小：$SS_{12}-(SS_1+SS_2)$. （在两个单例对象之间，这个数量 = 平方欧几里得距离 /$2$.) 这种集群构建的隐喻是type。直观地说，一个类型是一个更密集的云，在它的中间更同心，而边缘点很少，可以相对自由地散布。

一些不太为人所知的方法（参见 Podany J. New combinatorial clustering methods // Vegetatio, 1989, 81: 61-77.）[也由我实现为在我的网页上找到的 SPSS 宏]：

• 最小平方和法(MNSSQ)。两个集群之间的接近度是它们联合集群中的平方和：$SS_{12}$. （在两个单例对象之间，这个数量 = 平方欧几里得距离 / $2$.)

• 最小方差增加法(MIVAR)。两个集群之间的接近度是其联合集群中的均方大于这两个集群中加权（按对象数量）平均均方的幅度： $MS_{12}-(n_1MS_1+n_2MS_2)/(n_1+n_2) = [SS_{12}-(SS_1+SS_2)]/(n_1+n_2)$. （在两个单例对象之间，这个数量 = 平方欧几里得距离 /$4$.)

• 最小方差法(MNVAR)。两个集群之间的接近度是它们联合集群中的均方：$MS_{12} = SS_{12}/(n_1+n_2)$. （在两个单例对象之间，这个数量 = 平方欧几里得距离 /$4$.)。

还有其他方法表示一些专门的设置距离。HAC 算法可以基于它们，但不能基于通用的 Lance-Williams 公式；这些距离包括：Hausdorff 距离和点质心交叉距离（我已经基于这些实现了 SPSS 的 HAC 程序。）

所描述的前 5 种方法允许任何邻近测量（任何相似性或距离），结果自然取决于所选的测量。

接下来描述的 6 种方法需要距离；完全正确的是只使用平方欧几里得距离，因为这些方法计算欧几里得空间中的质心。因此，为了几何正确性，距离应该是欧几里得（这6种方法统称为几何链接方法）。在最坏的情况下，您可能会输入其他指标在承认更多启发式、不那么严格的分析方面的距离。现在关于那个“平方”。质心及其偏差的计算在数学/编程上最方便地在平方距离上执行，这就是为什么 HAC 包通常需要输入并调整为处理平方距离的原因。但是，存在基于非平方距离输入并需要这些实现的实现——完全等效但稍慢一些；例如，参见Ward 方法的“Ward-2”实现。您应该查阅聚类程序的文档，以了解它在输入“几何方法”时期望的距离（平方或非平方），以便正确执行。

方法 MNDIS、MNSSQ 和 MNVAR 除了仅更新 Lance-Williams 公式外，还需要一些步骤来存储集群内统计信息（这取决于方法）。

在研究中最常使用的方法是预计集群是或多或少是实心的圆形云，它们是平均连接方法、完全连接方法和沃德方法。

Ward 的方法在性质和效率上最接近 K-means 聚类；它们共享相同的目标函数——“最终”最小化聚集的集群内 SS。当然，K-means（是迭代的，如果提供了不错的初始质心）通常比 Ward 更适合最小化它。然而，在我看来，Ward 在揭示物理尺寸不均匀（方差）的集群或非常不规则地在空间中抛出的集群方面比 K-means 更准确一些。MIVAR 方法对我来说很奇怪，我无法想象什么时候可以推荐它，它不会产生足够密集的集群。

方法质心、中位数、最小方差增加 - 有时可能会产生所谓的反转：在某个步骤合并的两个集群看起来比之前合并的集群对更接近彼此的现象。那是因为这些方法不属于所谓的超度量。这种情况很不方便，但理论上是可以的。

单链接和质心的方法属于所谓的空间收缩，或“链接”。这意味着 - 粗略地说 - 他们倾向于将对象一个一个地附加到集群，因此他们展示了曲线“集群对象的百分比”相对平滑的增长。相反，完全链接、Ward、平方和、方差增加和方差的方法通常即使在早期步骤中也能获得相当大的对象集群份额，然后继续合并那些——因此它们的曲线“集群对象的百分比” ”从第一步开始就很陡峭。这些方法称为空间膨胀。其他方法介于两者之间。

灵活的版本。通过将附加参数添加到 Lance-Willians 公式中，可以使方法在其步骤上变得特别自调整。该参数对正在计算的集群间接近度进行校正，这取决于集群的大小（去紧凑度的量）。该参数的含义是它使集聚方法比标准方法注定要具有更多的空间膨胀或空间收缩。迄今为止，最广为人知的灵活性实现是平均链接方法 UPGMA 和 WPGMA（Belbin, L. et al. A Comparison of Two Approaches to Beta-Flexible Clustering // Multivariate Behavioral Research, 1992, 27, 417–433。 ）。

树状图。在树状图“Y”轴上，通常显示的是合并集群之间的接近度 - 正如上述方法所定义的那样。因此，例如，在质心方法中，通常测量平方距离（最终，它取决于封装及其选项）——一些研究人员没有意识到这一点。此外，按照传统，使用基于非密度增量的方法，例如 Ward 的方法，通常显示在树状图上是累积的价值 - 出于方便的原因，它比理论上的更快。因此，（在许多包中）Ward 方法中的绘制系数代表了在给定步骤的时刻观察到的所有集群中的总体平方和。不要错过阅读您的软件包的文档，以了解特定程序在其树状图上以何种形式显示碰撞系数（簇距离）。

人们应该避免通过比较树状图的外观来判断哪种连接方法对他的数据“更好”：不仅因为当你改变你在那里绘制的系数的修改时外观会发生变化 - 正如刚刚描述的那样 - 而是因为即使在没有集群的数据上，外观也会有所不同。

选择“正确”的方法

没有单一的标准。这个答案和其中的整个线程概述了一些如何选择聚类分析方法（包括HAC中的链接方法作为特例）的一些指导方针。

距离矩阵和共生距离之间的相关性是帮助评估选择哪个聚类链接的一个指标。来自?cophenetic：

可以说，如果原始距离和共生距离之间的相关性很高，则树状图是某些数据的适当汇总。

在这个小插图cor(dist,cophenetic(hclust(dist)))的 pg 38 中引用了这种用作链接选择度量的用法。vegan

请参见下面的示例代码：

# Data
d0=dist(USArrests)

# Hierarchical Agglomerative Clustering
h1=hclust(d0,method='average')
h2=hclust(d0,method='complete')
h3=hclust(d0,method='ward.D')
h4=hclust(d0,method='single')

# Cophenetic Distances, for each linkage
c1=cophenetic(h1)
c2=cophenetic(h2)
c3=cophenetic(h3)
c4=cophenetic(h4)

# Correlations
cor(d0,c1) # 0.7658983
cor(d0,c2) # 0.7636926
cor(d0,c3) # 0.7553367
cor(d0,c4) # 0.5702505

# Dendograms
par(mfrow=c(2,2))
plot(h1,main='Average Linkage')
plot(h2,main='Complete Linkage')
plot(h3,main='Ward Linkage')
plot(h4,main='Single Linkage')
par(mfrow=c(1,1))

我们看到 和 的相关性average非常complete相似，并且它们的树状图看起来非常相似。的相关性ward类似于average，complete但树状图看起来完全不同。single联动正在做自己的事情。来自主题专家的最佳专业判断，或对感兴趣领域中某个链接的优先级可能会覆盖来自cor().