层次聚类的相关原理

之前归纳和梳理的学习笔记，希望分享出来能帮助有缘人更好地理解层次聚类的逻辑和原理。

原理部分

聚类问题中，既然某些点能被看成一类，要么它们距离近，要么它们或多或少有共同的特征。拿到数据集后，直接根据特征或指标来将样本分类的做法，其实更加适合业务能力比较强或者有十分明确指标（如男女各一类等硬性要求）的场景。本篇主要对层次聚类进行详细说明。

层次聚类是按数据分层建立簇，形成一棵以簇为节点的树，称为聚类图。层次聚类主要分为以下两种方法：

• 自下而上聚合： 称为凝聚的层次聚类，由分散的点逐渐合并成类。开始时把每个对象作为一个单独的簇，然后逐次对各个簇进行适当合并，直到满足某个终止条件。这是最常用的方法，也是本文的重点。
• 自上而下分解： 称为分裂的层次聚类，由合并的类逐渐拆分成分散的点。开始时将所有对象置于同一个簇中，然后逐次将簇分为更小的簇，直到满足某个终止条件。

推导与距离计算

距离

假设有两个观测，其属性用向量进行表示，则该两个观测之间的距离可由以下方式计算：

• 欧式距离的缺陷： 受量纲的影响明显；未考虑各变量方差的不同；容易受异常值影响；没有考虑指标之间的相关性。作为改进，可以考虑将数据进行标准化或者归一化后再计算距离。
• 闵可夫斯基距离的缺陷： 与各指标量纲有关；没考虑各个变量之间的相关性与重要性。
• 最包罗万象的距离： 闵可夫斯基距离。因为 q 分别取 1 和 2 的时候，就分别表示绝对值距离和欧氏距离。

点与点的距离很好求，我们一般用的都是欧氏距离，即初中学习的直角三角形三边关系（ab² + bc² 后开根号）。

至于类和类之间的距离求法，经过了一个演变，目前的主流方式是平均链接（Average linkage），以两类为例，即用两类中所有点之间距离的均值来代表这两类的距离。其缺点是对异常值很敏感（可以采用中位数链接以摆脱异常值的影响）。

除了 Average linkage，还有下述几个主流方式：

• Average linkage： 最小化成对聚类间平均样本的距离值。
• Ward： 最小化了所有群集内的平方差总和。这是方差最小化的优化方法，类似于 K-means 目标函数的优化方法，但采用了凝聚分层的方法。
• Maximum 或 Complete linkage： 最小化成对聚类间最远样本的距离。
• Single linkage： 最小化成对聚类间最近样本的距离值。

• 重心法： 以两类的重心（均值向量）之间的距离作为两类间距离的一种系统聚类法，类似 K-means 法的基础原理。

它们各自对结果的差异可以从下图中看出（忽略重心法）：

目前来说，平均链接和重心法已经较少使用了，现在大多采用较少受异常值影响且在不知数据分布情况下依然能有较好表现的 Ward 法。

Ward 法理论与示例

Ward 法与方差分析相似，都是通过组间距离来定夺点与点、点与类、类与类之间的距离。

当合并成三个集群时（如 AB、CD、E），联合组内 SS = 1 + 4 + 0 = 5。当两个点被聚为一类时，这一类的组内差异 SS 便是其中一点的某一坐标与另外的所有坐标进行计算的结果。

以 5 个点聚为 4 类为例，意味着其中两个点会被聚在一起，剩下的三个点各自为一类，所以总共会出现 10 种情况，每种情况如下图所示：

同理，5 个点聚成 3、2、1 类的情况如下图所示：

需要注意的是，聚成两类后（如 AB 被归为一类），在后续的分类过程中，A 和 B 就作为一个整体参与后续的分类，不会再出现 A 和 B 分开的局面。结合上述情况，有如下结论：

• 如果需要被聚成 4 类，AB 为一类，剩下 3 个点各为一类最好（SS 最小）
• 如果需要被聚成 3 类，AB、DE 为一类，剩下的 C 单独为一类最好
• 如果需要被聚成 2 类，AB、CDE 各为一类最好
• 如果需要被聚成 1 类，没有什么分析的必要

代码项目注意部分

开始之前的注意点：

原始数据通常需要经过处理才能用于分析：

• 缺失值处理
• 异常值处理（极大或极小）
• 分类变量需要转化为哑变量（0/1数值）
• 分类变量类别不宜过多

需要对数据进行标准化： 避免由于变量量纲的不同引起计算距离的偏差。同时不同的统计方法对数据有不同的要求：

• 决策树和随机森林允许缺失值和异常值
• 聚类分析和回归模型不支持缺失值

处理数据时，也有两个问题值得关注：

1. 聚类的时候，所有的 X 必须都是连续变量，因为分类变量无法计算距离。如某个变量表示性别、教育程度，那各个个体之间的距离就会难以计算。故做聚类分析时尽可能不使用分类变量。
2. 分类变量的价值并不是无法利用的。可以先根据其他连续变量进行聚类，而后对分出来的类做描述性统计分析。或者一开始就可以用上分类变量进行一定的分类，再进行后续的聚类，需结合实际业务需求。

以市场客户调研为例，就”客户的需求与态度”问题展开调研。目的是依据调查问卷结果针对需求进行数据分群。如果问卷结果中不少问题一般都是以”是”或”否”为答案，这时候就可以通过合并多个问题回答的结果将多个分类变量组合，生成一个连续的变量。

分类变量之间还可以通过计算 Cos 相似度直接把分类变量设成距离，总之分类变量在聚类过程中一定需要处理。

常见问题解答

为什么说层次树是层次聚类法独有的聚类结果图？

树形图的横坐标会将每一个样本都标出来并展示聚类结果。几十个样本的时候，树形图就已经看不清楚了，成百上千样本更是难以观察。

层次树如何建立？

层次树的建立过程表示的就是聚类的过程，只不过通过层次树我们可以看出类之间的层次关系（这一类与另一类相差多远），同时还可以通过层次树决定最佳的聚类个数和看出聚类的方式（聚类的先后顺序）。基本步骤：

1. 计算两两个观测之间的距离
2. 将最近的两个观测聚为一类，并将其看作一个整体，计算与其他观测（类）之间的距离
3. 一直重复上述过程，直至所有的观测被聚为一类

如何从层次树中看出聚类的过程？

• 当两个点被分为 1 类时，从横坐标出发向上延伸，后形成一条横杠
• 当两个类被分为 1 类时，是横杠中点向上延伸
• 横杠的数量就表示了当所有的点到被聚为 1 类的过程中，经过了多少次聚类的过程

• 可以通过横杠的高度判断聚类的顺序，通过横杠的宽度判断聚类的数量

• 整个层次树由一个个小树构成，每个小树代表了一个类。小树的高度即为两个点或两个类之间的距离，如果两个点之间的距离越近，这棵树就应该越矮。

从最矮高度 d1 说起，d1 即为类（1,3）中两个孤立的点 1 和 3 之间的距离；同理，d2 为类（2,5）中点 2 和 5 之间的距离。至于 d3、d4、d5 这三个距离，它们并不像 d1 和 d2 那般表示的是一棵完整的树的高度，更像是”延伸的枝干”：d3 是从类 2,5 横杠的中点往上延伸的，表示会与另外的类聚成一起并形成一棵更大的树（类 2,5 和点 4 聚成新的类 2,5,4）。同理，d4 表示类 2,5,4 与类 1,3 聚成新类 1,3,2,5,4；d5 表示类 1,3,2,5,4 与点 6 聚成全量类。

如何从层次树中看出聚类的情况？

可以通过纵轴分界线来决定这些数据到底是分成几类。

这里有一个问题就是，最好不要分成 3 组：13、254、6。因为树的高度表示两个点之前的距离，4 到类 25 的距离，只比类 13 之间的距离多一点点，如下图所示。把 4 跟 25 分成一类有点牵强，这种牵强的分类方式可能会让我们忽略掉 4 这个点单独的价值，所以我们不如把 4 看成单独的一类。