层次聚类方法 - HAC's Blog

假设我们有 $n$ 个可区分的对象，我们要将它们划分成 $k$ 个非空、不编号的簇，一共有多少种分法？

第二类斯特林数（Stirling numbers of the second kind）给出了答案：

S(n,k)=k \cdot S(n-1, k)+S(n-1, k-1)=\frac{1}{k!}\sum_{i=0}^k(-1)^{k-i}\begin{pmatrix}k \\ i\end{pmatrix}i^n

可以想象，当对象非常多时，我们几乎不可能考虑所有的分组配置。这就引出了下面我们要介绍的主题——层次聚类方法。

Info

本篇节选自我的课程笔记，因此标题序号沿用了原笔记中的排列（~~懒得改~~）。

4. 层次聚类方法（Hierarchical clustering methods）#

层次聚类方法无需考察所有可能的分组配置，就能找到较为合理的簇。

即使拥有强大而快速的计算机，也很少会考察所有的分组可能。
层次聚类技术要么通过一系列相继的合并、要么通过一系列相继的分裂来进行。

凝聚法（Agglomerative method）：

凝聚法是一种自下而上的构建过程。

每个对象最初各自作为一个簇。
相近的簇或个体逐渐被合并。
该过程持续进行，直到所有个体被归入一个大簇。

分裂法（Divisive method ）：

分裂法是一种自上而下的拆分过程。

它从一个包含全部个体的簇开始。
最不相似的观测被逐步分裂出去。
该过程持续进行，直到每个观测各自成为一个簇。

上述技术的结果可以用一种称为谱系图（树状图，dendrogram）的二维图形来展示：

从左往右是凝聚，从右往左是分裂。

4.1 连结方法（Linkage methods）#

连结方法是凝聚型的层次聚类程序。

4.1.1 一般步骤#

从 $N$ 个簇开始，每个簇只含一个个体，并有一个 $N\times N$ 的对称距离矩阵或相似性矩阵

D=\{d_{ik}\}.

在距离矩阵中搜索距离最近（或最相似）的簇对。设最相似的簇 $U$ 与 $V$ 之间的距离为

d_{UV}.

合并簇 $U$ 和 $V$ ，并将新形成的簇标记为 $(UV)$ 。

按以下方式更新距离矩阵：
- 删除对应于 $U$ 和 $V$ 的行与列，并且
- 添加一行一列，包含 $(UV)$ 与其余各簇之间的距离。
重复第 2、3 步共 $N-1$ 次。

终止时，所有对象都归入一个簇。

记录：
- 被合并簇的标识，以及
- 合并发生时的距离或相似性水平。

4.1.2 单连结（Single linkage）#

簇间距离由两个最接近的对象（各来自一个簇）之间的距离定义。

对于合并后的簇 $(UV)$ 和另一个簇 $W$ ，

d_{(UV)W} = \min\{d_{UW},d_{VW}\}.

这里，

$d_{UW}$ 是簇 $U$ 与 $W$ 的最近邻之间的距离。
$d_{VW}$ 是簇 $V$ 与 $W$ 的最近邻之间的距离。

单连结例子#

五个对象两两之间的距离为：

D=\{d_{ik}\} = \begin{bmatrix} 0 & 9 & 3 & 6 & 11\\ 9 & 0 & 7 & 5 & 10\\ 3 & 7 & 0 & 9 & 2\\ 6 & 5 & 9 & 0 & 8\\ 11 & 10 & 2 & 8 & 0 \end{bmatrix}.

也即：

第 1 阶段#

五个簇，每个簇只含一个观测（observation）。

第 2 阶段#

对象 5 与 3 合并成簇 $(35)$ ，最近距离为

d_{53}=2.

于是

d_{(35)1} = \min\{d_{31},d_{51}\} = \min\{3,11\} = 3,

d_{(35)2} = \min\{d_{32},d_{52}\} = \min\{7,10\} = 7,

且

d_{(35)4} = \min\{d_{34},d_{54}\} = \min\{9,8\} = 8.

新的距离矩阵为

D_{(35)} = \begin{bmatrix} 0 & 9 & 6 & 3\\ 9 & 0 & 5 & 7\\ 6 & 5 & 0 & 8\\ 3 & 7 & 8 & 0 \end{bmatrix},

对应簇 $1,2,4,(35)$ ，也就是：

第 3 阶段#

将簇 $(1)$ 与簇 $(35)$ 合并得到簇 $(135)$ ，最近距离为

3.

于是

d_{(135)2} = \min\{d_{(35)2},d_{12}\} = \min\{7,9\} = 7,

且

d_{(135)4} = \min\{d_{(35)4},d_{14}\} = \min\{8,6\} = 6.

新的距离矩阵为

D_{(135)} = \begin{bmatrix} 0 & 7 & 6\\ 7 & 0 & 5\\ 6 & 5 & 0 \end{bmatrix},

对应簇 $(135),2,4$ ，也就是

第 4 阶段#

将对象 4 与 2 合并得到簇 $(24)$ ，最近距离为

5.

于是

d_{(135)(24)} = \min\{d_{(135)2},d_{(135)4}\} = \min\{7,6\} = 6.

距离矩阵变为

D_{(135)(24)} = \begin{bmatrix} 0 & 6\\ 6 & 0 \end{bmatrix}.

也就是：

第 5 阶段#

簇 $(135)$ 与 $(24)$ 合并成唯一的簇

(12345)

合并时的距离为

6.

上述 6 个阶段可以用下面的谱系图表示：

右边数字表示对象，下面的数字表示距离。

4.1.3 完全连结（Complete linkage）#

簇间距离由两个相距最远的元素（各来自一个簇）之间的距离决定。

对于簇 $(UV)$ 和另一个簇 $W$ ，

d_{(UV)W} = \max\{d_{UW},d_{VW}\}.

%% 如何证明上式成立？ %% 这里，

$d_{UW}$ 是簇 $U$ 与 $W$ 中相距最远的成员之间的距离。
$d_{VW}$ 是簇 $V$ 与 $W$ 中相距最远的成员之间的距离。

完全连结例子#

使用同一原始距离矩阵：

D = \begin{bmatrix} 0 & 9 & 3 & 6 & 11\\ 9 & 0 & 7 & 5 & 10\\ 3 & 7 & 0 & 9 & 2\\ 6 & 5 & 9 & 0 & 8\\ 11 & 10 & 2 & 8 & 0 \end{bmatrix}.

第 1 阶段#

五个簇，每个簇只含一个观测。

第 2 阶段#

对象 3 与 5 在距离

2.

处合并成簇 $(35)$ 。

于是

d_{(35)1} = \max\{d_{31},d_{51}\} = \max\{3,11\} = 11,

d_{(35)2} = \max\{d_{32},d_{52}\} = 10,

且

d_{(35)4} = \max\{d_{34},d_{54}\} = 9.

新的距离矩阵为

D_{(35)} = \begin{bmatrix} 0 & 9 & 6 & 11\\ 9 & 0 & 5 & 10\\ 6 & 5 & 0 & 9\\ 11 & 10 & 9 & 0 \end{bmatrix},

对应簇 $1,2,4,(35)$ ：

第 3 阶段#

对象 2 与 4 合并成簇 $(24)$ ，距离为

5.

于是

d_{(24)(35)} = \max\{d_{2(35)},d_{4(35)}\} = \max\{10,9\} = 10,

且

d_{(24)1} = \max\{d_{21},d_{41}\} = 9.

新的距离矩阵为

D = \begin{bmatrix} 0 & 10 & 11\\ 10 & 0 & 9\\ 11 & 9 & 0 \end{bmatrix},

对应簇 $(35),(24),1$ ：

第 4 阶段#

将簇 $(24)$ 与对象 1 合并成簇 $(124)$ ，距离为

9.

于是

d_{(124)(35)} = \max\{d_{1(35)},d_{(24)(35)}\} = \max\{11,10\} = 11.

因此，

D = \begin{bmatrix} 0 & 11\\ 11 & 0 \end{bmatrix}.

也即：

第 5 阶段#

簇 $(35)$ 与 $(124)$ 合并成簇

(12345)

合并时的距离为

11.

Important

单连结与完全连结的差别体现在对象 1 的归属上。

上述过程的谱系图表示：

4.1.4 平均连结（Average linkage）#

簇间距离由一个簇中所有个体到另一个簇中所有个体的平均距离定义。

对于簇 $(UV)$ 和另一个簇 $W$ ，

d_{(UV)W} = \frac{ N_Ud_{UW}+N_Vd_{VW} }{ N_U+N_V }.

这里， $N_U$ 和 $N_V$ 分别是簇 $U$ 和 $V$ 中对象的个数。

4.1.5 重心连结（Centroid linkage）#

簇间距离由各簇的重心（质心）之间的距离定义。

设 $d_{ij}$ 为对象 $i$ 与 $j$ 之间的平方欧氏距离。

用下式更新距离矩阵：

d_{(UV)W} = \frac{ N_Ud_{UW}+N_Vd_{VW} }{ N_U+N_V } - \frac{ N_UN_Vd_{UV} }{ (N_U+N_V)^2 }.

%%该更新公式中两项的含义？%%

4.2 连结的意义#

连结法的意义在哪？

既然最后所有的簇都要被聚类为一个簇，那我们中间这些步骤的意义在哪？不直接一开始就说它们是一个簇就完了吗？

连结法的意义并不在于最终的“一个大簇”，而恰恰在于中间的步骤。就像我们在开头提到的，层次聚类最大的优势是：你不需要事先决定分几类。做完树状图后，想分几类就切几刀：

1
高度 ──────────────────────────
2
     │                    ← 在这里切一刀 → 得到 1 个簇（没意义，不用）
3
     │               ╭──── 在这里切 → 得到 2 个簇（通常有意义！）
4
     │          ╭────╯
5
     │     ╭────╯
6
     │  ╭──╯
7
     │  3  5  1  2  4

我们不妨再回顾一下单连结例子中 5 个对象的合并记录：

次序	合并	距离
1	$\{3\},\{5\}$	2
2	$\{35\},\{1\}$	3
3	$\{4\},\{2\}$	5
4	$\{135\},\{24\}$	6

注意最后一步合并距离是 6，而前几步只有 2、3、5——这个距离跳变就是信息！它说明：

对象 3、5、1 彼此很接近（距离 2~3 就合并了）；
对象 2、4 也彼此接近（距离 5 合并）；
但这两组之间相距 6，明显比组内距离大。

所以如果我们在距离 5 和 6 之间切一刀，就得到两个有意义的簇： $\{135\}$ 和 $\{24\}$ 。这比”一个大簇”有用得多，而且不用事先指定 ——是数据自己告诉我们”大概分两组比较自然”。

从上面的表格也能看出，对于层次聚类：合并得越早（距离越小）的对象越相似，合并得越晚（距离越大）越疏远。

4.3 Ward 法（Ward’ s method）#

Ward 法将簇内平方和定义为

ESS = \sum_K \sum_{i\in K} \sum_{j=1}^{p} \left( x_{ijK} - \bar{x}_{.jK} \right)^2.

这里，

$x_{ijK}$ 是簇 $K$ 中第 $i$ 个观测的第 $j$ 个变量的取值。
$\bar{x}_{.jK}$ 是簇 $K$ 中第 $j$ 个变量的样本均值。

在每一阶段，都要在由上一阶段的两个簇合并所得的所有划分中，使簇内 $ESS$ 最小化。

设 $d_{ij}$ 为对象 $i$ 与 $j$ 之间的平方欧氏距离。

用下式更新距离矩阵：

d_{(UV)W} = \frac{ (N_W+N_U)d_{UW} + (N_W+N_V)d_{VW} - N_Wd_{UV} }{ N_U+N_V+N_W }.

其中：

$N_W$ ：簇 $W$ 里包含多少个对象， $N_U, N_V$ 以此类推。

4.3.1 Ward 法例子#

五个对象两两之间的平方欧氏距离为

D = \begin{bmatrix} 0 & 9 & 3 & 6 & 11\\ 9 & 0 & 7 & 5 & 10\\ 3 & 7 & 0 & 9 & 2\\ 6 & 5 & 9 & 0 & 8\\ 11 & 10 & 2 & 8 & 0 \end{bmatrix}.

第 1 阶段#

五个簇，每个簇只含一个观测。

第 2 阶段#

对象 3 与 5 在距离

2.

处合并成簇 $(35)$ 。

对于对象 1，

d_{(35)1} = \frac{ (N_1+N_3)d_{31} + (N_1+N_5)d_{51} - N_1d_{35} }{ N_3+N_5+N_1 }.

由于所有簇的大小均为 1，

d_{(35)1} = \frac{ (1+1)3+(1+1)11-1\times2 }{ 1+1+1 } = 8.6667.

类似地，

d_{(35)2} = \frac{ (1+1)7+(1+1)10-1\times2 }{ 1+1+1 } = 10.6667,

且

d_{(35)4} = \frac{ (1+1)9+(1+1)8-1\times2 }{ 1+1+1 } = 10.6667.

新的距离矩阵为

D = \begin{bmatrix} 0 & 8.6 & 10.6 & 10.6\\ 8.6 & 0 & 9 & 6\\ 10.6 & 9 & 0 & 5\\ 10.6 & 6 & 5 & 0 \end{bmatrix},

对应簇 $(35),1,2,4$ ：

第 3 阶段#

对象 2 与 4 合并成簇 $(24)$ ，距离为

5.

于是

d_{(24)(35)} = \frac{ (N_{35}+N_2)d_{2(35)} + (N_{35}+N_4)d_{4(35)} - N_{35}d_{24} }{ N_2+N_4+N_{35} }.

代入数值，

d_{(24)(35)} = \frac{ (2+1)(10.6667) + (2+1)(10.6667) - 2\times5 }{ 1+1+2 } = 13.5.

另外，

d_{(24)1}=8.333.

新的距离矩阵为

D = \begin{bmatrix} 0 & 13.5 & 8.6667\\ 13.5 & 0 & 8.333\\ 8.6667 & 8.333 & 0 \end{bmatrix},

对应簇 $(35),(24),1$ ：

第 4 阶段#

将簇 $(24)$ 与对象 1 合并成簇 $(124)$ ，距离为

8.333.

于是

d_{(124)(35)} = \frac{ (N_{35}+N_1)d_{1(35)} + (N_{35}+N_{24})d_{(24)(35)} - N_{35}d_{1(24)} }{ N_1+N_{24}+N_{35} }.

代入数值，

d_{(124)(35)} = \frac{ (2+1)(8.667) + (2+2)(13.5) - 2(8.333) }{ 1+2+2 } = 12.6667.

因此，

D = \begin{bmatrix} 0 & 12.6667\\ 12.6667 & 0 \end{bmatrix}.

第 5 阶段#

簇 $(35)$ 与 $(124)$ 合并成

(12345)

合并时的距离为

12.6667.

上述步骤的谱系图表示：

音乐

音乐

4. 层次聚类方法（Hierarchical clustering methods）#

4.1 连结方法（Linkage methods）#

4.1.1 一般步骤#

4.1.2 单连结（Single linkage）#

单连结例子#

第 1 阶段#

第 2 阶段#

第 3 阶段#

第 4 阶段#

第 5 阶段#

4.1.3 完全连结（Complete linkage）#

完全连结例子#

第 1 阶段#

第 2 阶段#

第 3 阶段#

第 4 阶段#

第 5 阶段#

4.1.4 平均连结（Average linkage）#

4.1.5 重心连结（Centroid linkage）#

4.2 连结的意义#

4.3 Ward 法（Ward’ s method）#

4.3.1 Ward 法例子#

第 1 阶段#

第 2 阶段#

第 3 阶段#

第 4 阶段#

第 5 阶段#

文章分享

评论区

音乐