[读书笔记]《西瓜书》第九章 聚类

第九章 聚类

---

聚类这一章在西瓜书中的地位主要是作为无监督学习的开篇，这一部分西瓜书中主要介绍了两部分的内容：聚类（本章节）和降维（第十章节）。而就目前我自己狭窄的知识面看来，无监督学习也主要是围绕着这两大主题开展的，此外还有一部分需要补充的：规则挖掘（频繁项集）和自编码器（Autoencoders）—— 这也仅仅是基于自己的理解。鉴于聚类这一部分的内容也同样相比前面其他章节来说容易理解的多，因此这部分的内容也就三篇文章（知识点总结、谱聚类补充、无监督学习）就可以涵盖了。OK，老惯例，继续我们的知识整理~

9.1 聚类任务

无监督学习（unsupervised learning）

定义：训练样本的标记信息是未知的，目的是通过对无标记训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础

常见学习任务：

• 密度估计（density estimation）
• 异常检测（anomaly detection）

等。

PS：我理解的这里的学习任务并不是指无监督学习的研究方向，而是指其应用领域（application）

聚类（clustering）

定义

将数据集中的样本划分为若干个通常是不想交的子集，这里的子集称之为"簇"（cluster）。

• 训练过程仅能自动形成簇结构
• 簇所对应的概念语义需要人为定义

---

数学定义

参数设定：

假定样本集 $D=\{ \boldsymbol{x}_1,\boldsymbol{x}_2,…,\boldsymbol{x}_m \}$ 包含 $m$ 个无标记样本，每个样本 $\boldsymbol{x}_i=\{ x_{i1};x_{i2};…;x_{in} \}$ 是一个 $n$ 维特征向量，聚类算法将样本集划分为 $k$ 个不相交的簇 $\{ C_l|l=1,2,…,k \}$ ，用 $\lambda_j \in \{ 1,2,…,k \}$ 表示样本 $\boldsymbol{x}_j$ 的“簇标记”。

则存在以下公式

• 簇不相交：$C_{l'}\cap_{l' \neq l}C_l = \varnothing$
• 并集为样本集：$D=\cup_{l=1}^kC_l$
• 聚类结果：$\boldsymbol{\lambda} = (\lambda_1;\lambda_2;…;\lambda_m)$

---

基本问题

聚类算法一般研究两个基本问题：

• 性能度量
• 距离计算

PS：这里抛出了两个基本问题，然后分成了两个小节展开进行叙述~

9.2 性能度量

性能度量亦称聚类“有效性指标”（validity index）

主要用途

• 对聚类的结果的好坏进行评估
• 作为聚类过程的优化目标

“物以类聚”

两个方向进行衡量：簇内相似度（intra-cluster similarity）高 和 簇间相似度（inter-cluster similarity）低

度量方式

外部指标（external index）

将聚类结果于某个“参考模型”（reference model）进行比较

参数定义

数据集 $D=\{ \boldsymbol{x}_1,\boldsymbol{x}_2,…,\boldsymbol{x}_m \}$ ，聚类的划分结果为 $\mathcal{C}=\{ C_1, C_2,…,C_k \}$，参考模型划分结果为 $\mathcal{C}^* = \{ C_1^*,C_2^*,…,C_s^* \}$ ，$\boldsymbol{\lambda}$ 和$\boldsymbol{\lambda}^*$ 分别表示聚类和参考模型的簇标记向量。

度量定义：

• $a = |SS|, \quad SS = \{ (\boldsymbol{x}_i,\boldsymbol{x}_j)|\lambda_i = \lambda_j, \quad \lambda_i^* = \lambda_j^*, \quad i < j \}$

  表示两两样本在聚类结果和参考模型中都属于相同的簇

• $b=|SD|, \quad SD = \{ (\boldsymbol{x}_i,\boldsymbol{x}_j) | \lambda_i = \lambda_j, \quad \lambda_i^* \neq \lambda_j^*, \quad i < j \}$

  表示样本对中在聚类结果中属于相同簇但在参考模型中不属于相同的簇

• $c=|DS|, \quad DS = \{ (\boldsymbol{x}_i,\boldsymbol{x}_j) | \lambda_i \neq \lambda_j, \quad \lambda_i^* = \lambda_j^*, \quad i < j \}$

  表示样本对中在聚类结果中不属于相同簇但在参考模型中属于相同簇

• $d = |DD|, \quad DD = \{ (\boldsymbol{x}_i,\boldsymbol{x}_j) | \lambda_i \neq \lambda_j, \quad \lambda_i^* \neq \lambda_j^*, \quad i < j \}$

  表示两两样本在聚类结果和参考模型中都不属于相同的簇

常见的聚类性能度量外部指标

Jaccard 系数（Jaccard Coefficient，简称JC）： $$ JC=\frac{a}{a+b+c} $$ FM 指数（Fowlkes and Mallows Index，简称FMI）： $$ \text{FMI}=\sqrt{\frac{a}{a + b} · \frac{a}{a + c}} $$ Rand 指数（Rand Index，简称RI）： $$ \text{RI} = \frac{2(a + d)}{m(m - 1)} $$ 这些值得结果值在 $[0, 1]$ 之间，越大越好

内部指标（internal index）

直接考察聚类结果而不利用任何参考模型

参数定义

聚类的划分结果为 $\mathcal{C} = \{ C_1, C_2,…,C_k \}$ ，簇 $C_i$ 的中心点 $\boldsymbol{\mu}i = \frac{1}{|C_i|}\sum{1 \le k \le |C|} \boldsymbol{x}_{i_k}$

度量定义:

• $\text{avg}(C) = \frac{2}{|C|(|C| - 1)} \sum_{1 \le i < j \le |C|} \text{dist}(\boldsymbol{x}_i,\boldsymbol{x}_j)$

  对应于簇内样本间的平均距离

• $\text{diam}(C) = \max_{1 \le i < j \le |C|} \text{dist}(\boldsymbol{x}_i, \boldsymbol{x}_j)$

  簇内样本间的最远距离

• $d_{\min}(C_i,C_j) = \min_{\boldsymbol{x}_i \in C_i, \boldsymbol{x}_j \in C_j} \text{dist}(\boldsymbol{x}_i, \boldsymbol{x}_j)$

  簇间最近样本的间距

• $d_{\text{cen}}(C_i,C_j) = \text{dist}(\boldsymbol{\mu}_i, \boldsymbol{\mu}_j)$

  簇间中心点的间距

常用的聚类性能度量内部指标

DB 指数（Davies-Bouldin Index，简称DBI）： $$ DBI = \frac{1}{k}\sum_{i=1}^k\max_{j \neq i}\left( \frac{\text{avg}(C_i) + \text{avg}(C_j)}{d_{\text{cen}}(C_i, C_j)} \right) $$

这里是值越小越好

Dunn 指数（Dunn Index，简称DI）： $$ DI = \min_{1 \le i \le k} \{ \min_{j \neq i} \left( \frac{d_{\min}(C_i, C_j)}{\max_{1 \le l \le k} \text{diam}(C_l)} \right) \} $$

这里是值越大越好

9.3 距离度量

距离函数 $\text{dist}(·,·)$

定义：它是一个距离度量（distance measure）

基本性质

• 非负性：$\text{dist}(\boldsymbol{x}_i,\boldsymbol{x}_j) \ge 0$
• 同一性：$\text{dist}(\boldsymbol{x}_i,\boldsymbol{x}_j) = 0$ 当且仅当 $\boldsymbol{x}_i = \boldsymbol{x}_j$
• 对称性：$\text{dist}(\boldsymbol{x}_i,\boldsymbol{x}_j) = \text{dist}(\boldsymbol{x}_j, \boldsymbol{x}_i)$
• 直递性：$\text{dist}(\boldsymbol{x}_i,\boldsymbol{x}_j) \le \text{dist}(\boldsymbol{x}_i,\boldsymbol{x}_k) + \text{dist}(\boldsymbol{x}_k,\boldsymbol{x}_j)$

这些性质也可以用来检测一个函数是否可以用来作为距离度量函数

• 通常基于某种形式的距离来定义“相似度度量”（similarity measure），距离越大，相似度越小
• 但是一定条件下可以不满足所有的基本性质，尤其是直递性
  • 在一些特殊情况下可以使三角结构中不相似的距离边达到一定程度的大小突破直递性的性质
  • 这种距离成为“非度量距离”（non-metric disttance）
• 此外也可以基于数据样本来确定合适的距离计算公式——距离度量学习（distance metric learning）

属性划分

• 连续属性（continuous attribute）
• 离散属性（categorical attribute）
  • 有序属性（ordinal attribute）
  • 无序属性（non-ordinal attribute）

闵可夫斯基距离（Minkowski distance）

公式定义： $$ \text{dist}{mk}(\boldsymbol{x}i,\boldsymbol{x}j) = \left( \sum{u=1}^n |x{iu} - x{ju}|^p \right)^{\frac{1}{p}} $$ 也称为 $\boldsymbol{x}_i - \boldsymbol{x}_j$ 的 $\text{L}_p$ 范数 ${\Vert \boldsymbol{x}_i - \boldsymbol{x}_j \Vert}_p$

常见变形：

• 曼哈顿距离（Manhattan distance）—— $\text{L}_1$ 范数： $$ \text{dist}_{ed}(\boldsymbol{x}_i, \boldsymbol{x}_j) = {\Vert \boldsymbol{x}_i - \boldsymbol{x}_j \Vert}_2 = \sqrt{\sum_{u=1}^n{|x_{iu} - x_{ju}|}^2} $$

• 欧氏距离（Euclidean distance） —— $\text{L}_2$ 范数： $$ \text{dist}_{man}(\boldsymbol{x}_i, \boldsymbol{x}_j) = {\Vert \boldsymbol{x}_i - \boldsymbol{x}_j \Vert}_1 = \sum_{u=1}^n{|x_{iu} - x_{ju}|} $$

• 切比雪夫距离（Chebyshev distance）—— $\text{L}_{\infty}$ 范数： $$ \text{dist}_{che} = {\Vert \boldsymbol{x}_i - \boldsymbol{x}_j \Vert}_{\infty} = \max_{u=1}^n{(|x_{iu} - x_{ju}|)} $$

适用有序属性，当属性重要性不同时，可适用”加权距离“（weighted distance）

VDM（Value Difference Metric）

公式定义： $$ \text{VDM}_p(a,b) = \sum_{i=1}^k {\left| \frac{m_{u,a,i}}{m_{u,a}} - \frac{m_{u,b,i}}{m_{u,b}} \right|}^p $$ 参数说明：

• $m_{u,a}$ 表示在属性 $u$ 上取值为 $a$ 的样本数
• $m_{u,a,i}$ 表示在第 $i$ 个样本簇中在属性 $u$ 上取值为 $a$ 的样本数
• $k$ 为样本簇数

适用无序属性，当属性重要性不同时，可适用”加权距离“（weighted distance）

---

将两者结合到一起 $$ \text{MinkovDM}_p(\boldsymbol{x}_i,\boldsymbol{x}_j) = \left( \sum_{u=1}^{n_{c}} |x_{iu} - x_{ju}|^p + \sum_{u = n_c + 1}^n \text{VDM}_p(x_{iu}, x_{ju}) \right)^{\frac{1}{p}} $$

PS：了解完聚类任务的定义和性能度量指标，然后就是按照聚类算法的类型划分整理了~

9.4 原型聚类

很自然的一个问题：什么是原型聚类？

定义：“原型”（prototype）是指样本空间中具有代表性的点

以 西瓜数据集4.0 为例子书中介绍了三种原型聚类算法：$k$-均值算法（k-means）、学习向量化（LVQ）和 高斯混合聚类（GMM）。

$k$-均值算法

算法定义

给定样本集 $D = \{\boldsymbol{x}_1，\boldsymbol{x}_2, …, \boldsymbol{x}_m \}$，“$k$ - 均值” （k-means）算法针对聚类所得簇划分 $C = \{C_1, C_2,…, C_k \}$ 最小化平方误差 $$ E = \sum_{i=1}^k\sum_{\boldsymbol{x} \in C_i} \Vert \boldsymbol{x} - \boldsymbol{\mu}_i \Vert_2^2 $$ 其中 $\boldsymbol{\mu}_i = \frac{1}{|C_i|} \sum_{\boldsymbol{x} \in C_i} \boldsymbol{x}$ 是簇 $C_i$ 的均值向量。

最小化上式并不容易，找到它的最优解需考察样本集 $D$ 所有可能的簇划分，这是一个 NP 难问题[Aloise et al., 2009]。

算法描述

训练结果

PS：$k$ - 均值算法应该算是聚类算法中特别好理解和掌握的一种了，因此书上也没有详细的介绍其内容。

学习向量量化（Learning Vector Quantization，简称LVQ）

算法定义

同样是试图找到一组原型向量来刻画聚类结构，不同的是 LVQ 假设数据样本带有类别标记，学习过程中利用样本的这些监督信息来辅助聚类。

给定样本集 $D=\{ (\boldsymbol{x}_1,y_1), (\boldsymbol{x}_2,y_2),…,(\boldsymbol{x}_m,y_m) \}$，$y_j \in \mathcal{Y}$ 是样本 $\boldsymbol{x}_j$ 的类别标记，LVQ 目标是学得一组 $n$ 维原型向量 $\{ \boldsymbol{p}_1, \boldsymbol{p}_2, …, \boldsymbol{p}_q \}$，

每个原型向量代表一个聚类簇，簇标记 $t_i \in \mathcal{Y}$。

---

引发一个问题：向量是如何划分空间的？

对任意样本，它将被划入与其距离最近的原型向量所代表的的簇中。

每个原型向量 $\boldsymbol{p}_i$ 定义了一个与之相关的一个区域 $R_i$ ，该区域中每个样本与 $\boldsymbol{p}_i$ 的距离不大于它与其他原型向量之间的距离 $$ R_i = \{ \boldsymbol{x} \in \mathcal{X} | {\Vert \boldsymbol{x} - \boldsymbol{p}_i \Vert}_2 \le {\Vert \boldsymbol{x} - \boldsymbol{p}_{i'} \Vert}_2, i' \neq i \} $$ 即完成了对样本空间 $\mathcal{X}$ 的簇划分 $\{R_1,R_2,…,R_q \}$

该划分通常称为“Voronoi剖分”（Voronoi tessellation）

---

算法描述

其中第七行和第九行都是源自 $\boldsymbol{p}'$ 与 $\boldsymbol{x}_j$ 之间的距离推导 ${\Vert \boldsymbol{p}' - \boldsymbol{x}_j \Vert}_2$

• 当类别标记相同时 $$ \boldsymbol{p}' = \boldsymbol{p}_{i^*} + \eta ·(\boldsymbol{x}_j - \boldsymbol{p}_{i^*}) $$

  $$ {\Vert \boldsymbol{p}' - \boldsymbol{x}_j \Vert}_2 = {\Vert \boldsymbol{p}_{i^*} + \eta ·(\boldsymbol{x}_j - \boldsymbol{p}_{i^*}) - \boldsymbol{x}_j \Vert}_2 = (1 - \eta)·{\Vert \boldsymbol{p}_{i^*} - \boldsymbol{x}_j \Vert}_2 $$

• 当类别标记不同时 $$ \boldsymbol{p}' = \boldsymbol{p}_{i^*} - \eta ·(\boldsymbol{x}_j - \boldsymbol{p}_{i^*}) $$

  $$ {\Vert \boldsymbol{p}' - \boldsymbol{x}_j \Vert}_2 = {\Vert \boldsymbol{p}_{i^*} - \eta ·(\boldsymbol{x}_j - \boldsymbol{p}_{i^*}) - \boldsymbol{x}_j \Vert}_2 = (1 + \eta)·{\Vert \boldsymbol{p}_{i^*} - \boldsymbol{x}_j \Vert}_2 $$

最终学得一组原型向量 $\{ \boldsymbol{p}_1, \boldsymbol{p}_2,…,\boldsymbol{p}_q \}$ 后，即可实现对样本空间 $\mathcal{X}$ 的簇划分。

训练结果

学习目的是找到5个原型向量 $\boldsymbol{p}_1,\boldsymbol{p}_2,\boldsymbol{p}_3,\boldsymbol{p}_4,\boldsymbol{p}_5$

其分别对应的类别标记假定为 $c_1, c_2, c_2, c_1, c_1$，其中 $c_1$ 为好瓜， $c_2$ 为坏瓜

高斯混合聚类

高斯混合（Mixture-of-Gaussian）聚类采用概率模型来表达聚类原型

• 高斯混合聚类是采用概率模型对原型进行刻画
• 簇划分则由原型对应后验概率确定

多元高斯分布的定义

• $\boldsymbol{\mu}$ 是 $n$ 维均值向量
• $\boldsymbol{\Sigma}$ 是 $n \times n$ 的协方差矩阵

多元高斯高斯分布由这两个参数确定

概率密度记为：$p(\boldsymbol{x}|\boldsymbol{\mu}, \boldsymbol{\Sigma})$

为了凸显相应参数的依赖关系

高斯混合分布

$$ p_{\mathcal{M}} = \sum_{i=1}^k \alpha_i · p(\boldsymbol{x}|\boldsymbol{\mu}_i,\boldsymbol{\Sigma}_i) $$

参数说明

• 该分布由 $k$ 个混合成分组成，每个成分对应一个高斯分布
• $\boldsymbol{\mu}_i$ 与 $\boldsymbol{\Sigma}_i$ 是第 $i$ 个高斯混合成分的参数
• $\alpha_i > 0$ 为相应的“混合系数” （mixture coefficient）， $\sum_{i=1}^k \alpha_i = 1$

算法过程

训练集生成方式

首先，根据 $\alpha_1,\alpha_2,…,\alpha_k$ 定义的先验分布选择高斯混合成分，其中 $\alpha_i$ 为选择第 $i$ 个混合成分的概率，然后，根据被选择的混合成分的概率密度函数进行采样，从而生成相应的样本。

高斯混合成分生成的后验概率确定

令随机变量 $z_j \in \{ 1,2,…,k \}$ 表示生成样本 $\boldsymbol{x}_j$ 的高斯混合成分，其取值未知，显然，$z_j$ 的先验概率 $P(z_j=i)$ 对应于 $\alpha_i(i=1,2,…,k)$，根据贝叶斯定理，$z_j$ 的后验概率分布对应于 $$ p_{\mathcal{M}}(z_j=i|\boldsymbol{x}_j) = \frac{P(z_j=i)·p_{\mathcal{M}}(\boldsymbol{x}_j|z_j=i)}{p_{\mathcal{M}}(\boldsymbol{x}_j)} = \frac{\alpha_i·p(\boldsymbol{x}_i|\boldsymbol{\mu}_i,\boldsymbol{\Sigma}_i)}{\sum_{l=1}^k\alpha_l·p(\boldsymbol{x}_j|\boldsymbol{\mu}_l,\boldsymbol{\Sigma}_l)} $$ 记为 $\gamma_{ji}(i=1,2,…,k)$

簇标记确定

当高斯混合分布已知时，高斯混合聚类将把样本集 $D$ 划分为 $k$ 个簇 $\mathcal{C}=\{ C_1,C_2,…,C_k \}$

每个样本 $\boldsymbol{x}_j$ 的簇标记 $\lambda_j$ 如下确定 $\lambda_j = \underset{i \in \{1,2,…,k \}}{\arg\max} \gamma_{ji}$

参数求解

给定样本集 $D$，可采用极大似然估计，即最大化（对数）似然 $$ LL(D) = \ln\left( \prod_{j=1}^m p_{\mathcal{M}}(\boldsymbol{x}_j) \right) = \sum_{j=1}^m \ln \left( \sum_{i=1}^k\alpha_i · p(\boldsymbol{x}_j|\boldsymbol{\mu}_i,\boldsymbol{\Sigma}_i) \right) $$

EM算法求解:

• 根据当前参数来计算每个样本属于每个高斯成分的后验概率（E步）
• 再根据极大似然估计极值条件，更新参数（M步）

PS：这一部分在前面章节贝叶斯分类器中介绍过~

算法描述

训练结果

9.5 密度聚类

密度聚类亦称“基于密度的聚类”（density-based clustering），此类算法假设聚类结构能通过样本分布的紧密程度确定。

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）

最著名的密度聚类算法

PS：这里算法名字中 密度 是基于 Spatial（空间上）的，而另一种 谱聚类（Spectral Clustering）算法 是基于 Spectral（频谱上）的。

原理简单总结就是：基于一组“邻域”参数 $(\epsilon,MinPts)$ 来刻画样本分布的紧密程度

概念定义

$\epsilon$ - 领域：

对 $\boldsymbol{x}_j \in D$，其 $\epsilon$ - 领域包含样本集 $D$ 中与 $\boldsymbol{x}_j$ 的距离不大于 $\epsilon$ 的样本，即 $N_{\epsilon}(\boldsymbol{x}_j) = \{ \boldsymbol{x}_i \in D | \text{dist}(\boldsymbol{x}_i, \boldsymbol{x}_j) \le \epsilon \}$

核心对象：

若 $\boldsymbol{x}_j$ 的 $\epsilon$ - 领域至少包含 $MinPts$ 个样本，即 $|N_{\epsilon}(\boldsymbol{x}_j)| \ge MinPts$ ，则 $\boldsymbol{x}_j$ 是一个核心对象

---

对于结点间关系的定义：

密度直达（directly density-reachable）：

若 $\boldsymbol{x}_j$ 位于 $\boldsymbol{x}_i$ 的 $\epsilon$ - 领域中，且 $\boldsymbol{x}_i$ 是核心对象，则称 $\boldsymbol{x}_j$ 由 $\boldsymbol{x}_i$ 密度直达

密度直达关系通常不满足对称性：核心对象有交集的情况比较特殊

密度可达（density-reachable）：

对 $\boldsymbol{x}_i$ 与 $\boldsymbol{x}_j$ ，若存在样本序列 $\boldsymbol{p}_1,\boldsymbol{p}_2,…,\boldsymbol{p}_n$ ，其中 $\boldsymbol{p}_1=\boldsymbol{x}_i,\boldsymbol{p}_n=\boldsymbol{x}_j$ 且 $\boldsymbol{p}_{i+1}$ 由 $\boldsymbol{p}_i$ 密度直达，则称 $\boldsymbol{x}_j$ 由 $\boldsymbol{x}_i$ 密度可达

密度可达关系满足直递性，但不满足对称性：同样因为有核心对象的参与

密度相连（density-connected）：

对 $\boldsymbol{x}_i$ 与 $\boldsymbol{x}_j$ ，若存在 $\boldsymbol{x}_k$ 使得 $\boldsymbol{x}_i$ 与 $\boldsymbol{x}_j$ 均由 $\boldsymbol{x}_k$ 密度可达，则称 $\boldsymbol{x}_i$ 与 $\boldsymbol{x}_j$ 密度相连

密度相连关系满足对称性

---

$D$ 中不属于任何簇的样本被认为是噪声（noise）或异常（anomaly）样本

簇的定义

由密度可达关系导出的最大的密度相连样本集合

形式化定义

给定领域参数 $(\epsilon,MinPts)$，簇 $C \subseteq D$ 是满足以下性质的非空样本子集

应满足性质:

• 连接性（connectivity）：$\boldsymbol{x}_i \in C，\boldsymbol{x}_j \in C \Rightarrow \boldsymbol{x}_i$ 与 $\boldsymbol{x}_j$ 密度相连
• 最大性（maximality）：$\boldsymbol{x}_i \in C，\boldsymbol{x}_j$ 由 $\boldsymbol{x}_i$ 密度可达 $\Rightarrow \boldsymbol{x}_j \in C$

算法描述

训练结果

9.6 层次聚类

层次聚类（hierarchical clustering）试图在不同层次对数据集进行划分，从而形成树形的聚类结构。

两种策略方式：

• “自底向上”的聚合策略
• “自顶向下”的分拆策略

AGNES（AGglomerative NESting）

著名的自底向上聚合策略的层次聚类算法

核心思想

它先将数据及中的每个样本看做一个初始聚类簇，然后再算法运行的每一步中找出距离最近的两个聚类簇进行合并，该过程不断重复，知道达到预设的聚类簇个数

常用的距离计算

• 最小距离 $$ d_{min}(C_i,C_j)=\underset{\boldsymbol{x} \in C_i, \boldsymbol{z} \in C_j}{\min} \text{dist}(\boldsymbol{x},\boldsymbol{z}) $$

  AGNES称为“单链接”（single-linkage）

• 最大距离 $$ d_{max}(C_i,C_j) = \underset{\boldsymbol{x} \in C_i, \boldsymbol{z} \in C_j}{\max}\text{dist}(\boldsymbol{x}, \boldsymbol{z}) $$

  AGNES称为“全链接”（complete-linkage）

• 平均距离 $$ d_{\text{avg}}(C_i,C_j) = \frac{1}{|C_i||C_j|}\sum_{\boldsymbol{x} \in C_i} \sum_{\boldsymbol{z} \in C_j} \text{dist}(\boldsymbol{x}, \boldsymbol{z}) $$

  AGNES称为“均链接”（average-linkage）

算法描述

训练结果