什么是分层聚类

聚类是一种无监督机器学习技术，用于数据分析中，以检测和分组相似的对象。层次簇分析 (HCA)，或层次聚类，将对象分组到一个簇层次结构中，而不强制要求其中的线性顺序。生物学、图像分析和社会科学等许多学科都使用层次聚类方法来深入了解和识别数据集中的模式。用例包括临床研究中对人群进行分类、客户细分以及检测网络模型中的节点社区。

层次聚类分为两种类型：

- 凝聚型或自下而上的方法¹，这种方法反复将簇合并成更大的簇，直到形成一个单个簇。

- 分裂型或自上而下的方法²，这种方法从单个簇中的所有数据开始，然后继续划分连续的簇，直到所有的簇都是单一簇。

层次聚类分析的计算成本很高。虽然使用堆可以减少计算时间，但内存需求会增加。分裂型聚类和凝聚型聚类都是“贪婪”的，这意味着算法在过程的每个阶段都会做出局部最优选择，从而决定合并或拆分哪些簇。还可以应用停止标准，即当算法达到预定的簇数目时停止聚合或拆分簇。

树状图（或称树枝图）³常用于可视化簇的层次结构。它显示簇的合并或分割顺序，并显示数据点之间的相似性或距离。树枝图也可以理解为具有属性的嵌套式列表⁴。

层次聚类算法利用相异度矩阵的概念决定要聚合或分割哪些簇。相异度是指通过所选的连锁准则方法测量的两个数据点之间的距离。相异度矩阵中的值表示：

- 一个集合中的单个点之间的距离⁵，例如欧几里得距离

- 一种连锁准则聚类标准，它将相异度指定为跨集合的点的间距的一个函数

让我们深入了解最常用的欧几里得距离连锁准则方法。可以使用的其他距离指标的示例包括 Minkowski、Hamming、Mahalanobis、Hausdorf 和 Manhattan 距离。请注意，每种连锁准则方法都会从同一个数据集生成不同的簇。选择适当的连锁准则聚类方法取决于多种因素，例如要聚类的数据类型、数据密度、簇形状以及数据集中是否存在异常值或噪声。

单一连锁准则方法会分析两个簇中的项之间的间距，然后使用簇之间的最小距离。最小方法可以很好地处理非椭圆的簇形状，但会受到噪声和异常值的影响。它具有一个被称为连锁效应的局限性⁶。在簇对之间创建桥梁的几个点可能会导致两个簇合并为一个。最小连锁准则可表示为：

mina∈A,b∈Bd(a,b)

其中的 A 和 B 是两组观测值，d 是一个距离函数。

簇距离也可以基于彼此最远的数据点来计算。与最小距离法相比，最大距离法对噪声和异常值的敏感度较低，但在存在球状或较大簇时，使用最大距离法可能会导致结果偏差。最大连锁准则通常比最小连锁准则产生更接近球形的簇。最大连锁准则可以用以下公式表示：

maxa∈A,b∈Bd(a,b)

其中的 A 和 B 是两组观测值，d 是距离。

这些方法由 Sokal 和 Michener 提出⁷，它们会将簇之间的距离定义为簇中所有点对中的对之间的平均距离。这种算法可以是具有算术平均值的未加权对组方法 (UPGMA)，也可以是具有算术平均值的加权对组方法 (WPGMA)。这里的“未加权”意味着所有距离对每个平均值的贡献相等。

UPGMA 用如下公式表示

1∣A∣·∣B∣∑a∈A∑b∈Bd(a,b)

其中的 *A* 和 *B* 是两组观测值，*d* 是距离。

WPGMA 用如下公式表示

d(i∪j,k)=d(i,k)+d(j,k)2

其中 i 和 j 是在每一步中被合并的最近簇，用于形成 i 和 j 的联合新簇。然后，我们可以计算到另一个簇 k 的距离，该距离是簇 k 与 i 之间的数据点平均距离以及簇 k 与 j 之间的数据点平均距离的算术平均值。

在这里，我们使用簇中心或质心之间的距离。质心之间的距离通过一个距离函数计算得出：

∥μA-μB∥2

其中的 μ_A 是 A 的质心，μ_B 是 B 的质心。

Joe H. Ward 在 20 世纪 60 年代引入了平方和最小增量 (MISSQ) 方法⁸。每个数据点都从自己的簇中开始。这种方法意味着数据点之间的平方和最初为零，然后随着我们合并簇而增加。Ward 方法在合并簇时将点与簇中心之间的平方距离之和最小化。对于定量变量来说，Ward 方法是一个不错的选择⁹，它受噪声或异常值的影响较小。它可以表示为：

 ∣A∣·∣B∣A∪B∥μA-μB∥2=∑x∈A∪B∥x-μA∪B∥2-∑x∈A∥x-μA∥2-∑x∈B∥x-μB∥2

其中的 A 的平均值和 B 的平均值分别是 A 和 B 的质心，x 是属于 A 和 B 的并集的数据点

Ward 最小方差法可以通过 Lance-Williams 算法进行改进。这些算法使用一个递归公式更新簇距离，并找到最佳的最近簇对进行合并。

在凝聚型层次聚类（也称为凝聚型嵌套 (AGNES)）中，每个数据点都作为一个簇开始。该算法基于不相似性矩阵，使用选定的聚类连锁准则来决定合并哪一对簇。这种算法在层次结构中向上移动，并持续配对簇，直到所有内容都链接在一起，从而创建一系列分层的嵌套簇。大致说来，凝聚型聚类步骤¹⁰ 如下所示：

1. 使用特定的距离指标计算相异度矩阵。

2. 将每个数据点分配给一个簇。

3. 根据簇之间的相似度的连锁准则合并簇。

4. 更新距离矩阵。

5. 重复第 3 步和第 4 步，直到剩余单个簇或满足任何停止条件。

分裂型层次聚类背后的原则由 Macnaughton-Smith 等人¹¹ 于 1964 年制定，Kaufman 和 Rousseeuw 在 1990 年利用他们的 DIANA（分裂型分析聚类）算法¹² 进一步深入探索了分裂型层次聚类。分裂型聚类采用与凝聚型聚类相反的方法。所有数据点都从单个簇开始，然后不断分裂成多个簇。持续进行划分，直到其余的所有簇都是单一簇或满足停止条件（例如预定义的簇数量）。分裂型方法更擅长识别大型簇¹³，并且可能比凝聚型方法更准确，因为这种算法从这一过程开始时就考虑到整个数据集分布。

为了提高效率，分裂型方法使用扁平聚类算法（例如 k 均值）将数据集划分成簇。必须预先指定簇的数量。k 均值算法通过最小化簇内质心点之间的平方和来划分簇。这被称为惯性准则¹⁴。分裂型聚类步骤¹⁵为：

1. 从一个簇中的数据集大小为 N (d1, d2, d3 ... dN) 的所有数据点开始。

2. 使用扁平聚类方法（例如 k 均值算法）将簇划分成两个相异或异构的簇。

3. 重复第 2 步，选择要划分的最佳簇，并在每次迭代之后从内聚力最小的簇中移除异常值。

4. 当每个示例都在它们各自的单个簇中时停止，否则重复第 3 步。

簇的结果通常以树状图（二叉树结构）的形式呈现。树状图中的 x 轴表示数据点，y 轴（即线条的高度）表示簇合并时彼此之间的距离。

您可以使用树状图来决定最终聚类模型中将有多少个簇¹⁶。一种策略是确定树枝图中的树枝变小和变长的自然分界点。或者，簇的数量由水平线切割树枝图时穿过的垂直线的数量决定。

在此处显示的示例图像中，水平线 H1 切割两条垂直线。这表明在这一过程中，此时存在两个簇，一个带有点 5、8 和 2 的簇，另一个带有其余点的簇。水平线在不切割树枝图中的其他水平线的情况下向上或向下移动得越远，选择这一数量的簇就越适合您的聚类模型。在以下示例中，水平线 H2 选择四个簇。H2 在切割其他水平线之前无法上下移动 H1 那么远。这一场景表明，双簇选择 (H1) 可能更适合您的聚类模型。

强大的聚类模型¹⁷会创建类间相似度高和类间相似度低的簇。不过可能难以定义簇质量，而且您选择的连锁准则和簇数量可能对结果产生重大影响。因此，当构建聚类模型时，请尝试不同的选项，并选择最能帮助您深入了解和揭示数据集内的模式的选项，以便为将来考虑。需要考虑的因素¹⁸包括：

- 对数据集来说，实用或合理的簇数量（考虑到数据集大小、簇形状、噪声等因素）

- 统计数据，例如每个簇的平均值、最大值和最小值

- 要应用的最佳相异度指标或连锁准则

- 任何异常值或结果变量的影响

- 任何特定的领域或数据集知识

可以帮助确定最佳簇数量¹⁹的其他方法包括：

- 肘部法，也就是绘制簇内平方和与簇数量的关系图，并确定“肘部”（即绘图趋于平稳的点）

- 差距统计，也就是将实际簇内平方和与空参考分布的预期簇内平方和进行比较，并找出最大差距。

层次聚类为数据科学家提供了对数据集内的结构和关系的洞察，并且可应用于各种用例。

层次聚类可以帮助分析趋势和细分客户数据，例如按产品选择、人口统计、购买行为、风险状况或与社交媒体的互动进行分组。

用于临床研究的患者队列可能多达数千个。层次聚类有助于使用诊断标准、生理反应或 DNA 突变等依据，将混合群体分成更同质化的群组²⁰。它还可以按生物学特征对物种进行分组，以了解进化发展。

层次聚类用于基于图像的文本识别应用程序中，以便按形状对手写字符进行分组。它还可以使用某些标准来存储和检索信息，或者对搜索结果进行分类。

Python 和 R 编程语言都广泛应用于数据科学领域。Python 非常灵活，可以处理多种任务。此外，R 专为统计计算而设计，并提供了丰富的选项用于可视化层次聚类分析。

Python 提供了 AgglomerativeCluster 函数²¹（参见 sklearn 上的凝聚型聚类示例²²），而 SciPy 提供了绘制树状图的函数²³。诸如 dendextend²⁴ 之类的包增强了 R 的树状图功能，提高了灵敏度分析能力，并使您能够比较和操作不同的树状图。想要动手实践，请查看我们的分步教程：在 Python 中实现层次聚类的方法和在 R 中实现层次聚类的方法。