前言

最近工作忙起来了，看书的进度都拉下了……

第九章

在本章之前，我们所有的训练方式都是有监督的训练，本章我们将接触到无监督学习的一种——聚类任务

9.1 聚类与度量

在现实世界中，获取大量的已标记数据通常是昂贵且耗时的过程，甚至需要依赖专业人士进行标注；相比之下，未标记的数据在自然界和工业场景中非常普遍且容易获取。这些未标记的数据可以通过聚类算法自动发现数据中潜在的模式或规律，从而实现对样本的自动分类。这种分类结果既可以作为其他机器学习任务的预处理步骤，也能帮助识别那些不属于任何类别的异常样本（通常被视为噪声）。

聚类分析的核心目标是：在完全没有先验知识（即没有任何标记信息）的条件下，自动将数据集划分为若干个具有明确意义的子集（簇）。这些子集需要满足以下特性：同一簇内的样本应当尽可能相似，而不同簇之间的样本应当尽可能不同。

在聚类任务中，我们需要明确以下数学表示：

1. 将划分得到的子集称为簇（cluster），用符号表示为Cl,l∈{1,2,…,k}C_{l}, \quad l \in \{1,2,\dots,k\}Cl​,l∈{1,2,…,k}其中$k$表示簇的总数。
2. 样本集（不含任何标记）记为D={x1,x2,…,xm}D = \{\mathbf{x}_{1}, \mathbf{x}_{2}, \dots, \mathbf{x}_{m}\}D={x1​,x2​,…,xm​}其中每个样本$${\mathbf{x}}_i=(x_{i1},x_{i2},\dots ,x_{in}{)}^T$$用一个$n$维特征向量表示其属性。
3. 使用簇标记来表示样本与簇的归属关系：对于样本${\mathbf{x}}_j$，若它属于簇$C_{{\lambda }_j}$，则其簇标记为λj∈{1,2,…,k}\lambda_{j} \in \{1,2,\dots,k\}λj​∈{1,2,…,k}例如，若样本${\mathbf{x}}_5$被划分到第8个簇，则记为$${\mathbf{x}}_5\in C_8$$此时${\lambda }_5=8$

和有监督任务类似，我们需要性能度量来评估我们的模型，之前的2.1节中我们主要介绍的都是有监督的性能度量，对于无监督任务，我们一般分为$2$大类：外部指标和内部指标。

外部指标
外部指标的核心思想是：将聚类算法给出的结果与一个已知的“真实”或“理想”的划分进行比较。 这个“真实划分”通常被称为参考模型 或 真实类别信息。只有当这样的参考模型存在时，我们才能使用外部指标。

例如，假设我们有一批客户数据，并且已经通过人工标注或业务规则将这些客户划分为“高价值客户”、“潜力客户”、“一般客户”和“流失风险客户”四个类别（即参考模型）。现在，我们使用一个新的聚类算法对这些客户进行聚类，也得到了四个簇。外部指标的作用就是量化评估算法生成的簇划分与参考模型之间的匹配程度，从而判断聚类结果的准确性。

为了比较聚类模型和参考模型之间的差异，我们需要对同一组样本进行双重划分：

• 设聚类算法给出的簇划分为 C={C1,C2,…,Ck}C = \{C_1, C_2, \dots, C_k\}C={C1​,C2​,…,Ck​}
• 参考模型的簇划分为 C∗={C1∗,C2∗,…,Cs∗}C^* = \{C_1^*, C_2^*, \dots, C_s^*\}C∗={C1∗​,C2∗​,…,Cs∗​}

对于任意两个样本 $({\mathbf{x}}_i,{\mathbf{x}}_j)$，可以通过对比它们在 $C$ 和 $C^{\ast }$ 中的归属关系，得到以下四种情况：

1. SS（Same-Same）：${\mathbf{x}}_i$ 和 ${\mathbf{x}}_j$ 在 $C$ 中属于同一个簇，且在 $C^{\ast }$ 中也属于同一个簇。
2. SD（Same-Different）：${\mathbf{x}}_i$ 和 ${\mathbf{x}}_j$ 在 $C$ 中属于同一个簇，但在 $C^{\ast }$ 中属于不同簇。
3. DS（Different-Same）：${\mathbf{x}}_i$ 和 ${\mathbf{x}}_j$ 在 $C$ 中属于不同簇，但在 $C^{\ast }$ 中属于同一个簇。
4. DD（Different-Different）：${\mathbf{x}}_i$ 和 ${\mathbf{x}}_j$ 在 $C$ 中属于不同簇，且在 $C^{\ast }$ 中也属于不同簇。

统计满足以上四种情况的样本对数量，分别记为 $a$（SS）、$b$（SD）、$c$（DS）、$d$（DD）。由于每一对样本只能属于其中一种情况，因此有：
$$a+b+c+d=\frac{m(m-1)}{2}$$
其中 $m$ 是样本总数。

下面说明常见的外部指标

1. Jaccard 系数（JC）

   • 公式：$$JC=\frac{a}{a+b+c}$$
   • 分母 $a+b+c$ 表示在聚类结果或参考模型中至少有一个模型将样本对划分为同簇的总对数，分子 $a$ 表示两个模型均正确划分为同簇的对数。因此，JC 衡量的是聚类结果与参考模型在同簇判断上的一致性比例。
   • 取值范围：$[0,1]$，值越大表示聚类结果与参考模型越吻合。

2. Fowlkes-Mallows 指数（FMI）

   • 公式：$$FMI=\sqrt{\frac{a}{a+b}\cdot \frac{a}{a+c}}$$
   • 解释：
     • 第一项 $\frac{a}{a+b}$ 是精准率，表示聚类结果中同簇的样本对有多少在参考模型中也同簇。
     • 第二项 $\frac{a}{a+c}$ 是召回率，表示参考模型中同簇的样本对有多少在聚类结果中也同簇。
     • FMI 是两者的几何平均数，综合衡量聚类结果的精确性和完整性。
   • 取值范围：$[0,1]$，值越大表示聚类结果与参考模型的一致性越高。

3. Rand 指数（RI）

   • 公式：$$RI=\frac{a+d}{a+b+c+d}=\frac{2(a+d)}{m(m-1)}$$
   • 解释：RI 计算的是所有样本对中，聚类结果与参考模型判断一致的比例（包括同簇和不同簇）。可以理解为聚类结果的“整体准确率”。
   • 取值范围：$[0,1]$，值越大表示聚类结果越准确。

内部指标
接下来讨论在没有参考模型的情况下如何评估聚类效果，这时我们需要定义一个关键函数 $dist$，它能够计算两个样本（向量）之间的距离，这种函数称为距离度量。关于距离度量的具体细节会在下一节展开，这里先定义几个重要的量：

簇内平均距离 $avg(C_l)$
该变量用于衡量簇 $C_l$ 内所有样本距离的均值，即所有样本两两之间的距离求和再除以样本对的总数。这里需要注意样本对的计算方式：对于大小为 $|C_l|$ 的簇，共有 $\frac{|C_l|(|C_l|-1)}{2}$ 个不同的样本对。其数学表达式为：
$$avg(C_l)=\frac{{\sum }_{1⩽i<j⩽|C_l|}dist({\mathbf{x}}_i,{\mathbf{x}}_j)}{|C_l|(|C_l|-1)/2}=\frac{2}{|C_l|(|C_l|-1)}\sum _{1⩽i<j⩽|C_l|}dist({\mathbf{x}}_i,{\mathbf{x}}_j)$$

直径 $diam(C_l)$
该变量用于衡量簇 $C_l$ 内最远的两个样本之间的距离，即所有样本对距离的最大值。其数学表达式为：
$$diam(C_l)=\underset{1\le i<j\le |C_l|}{\max }dist({\mathbf{x}}_i,{\mathbf{x}}_j)$$

簇间最短距离 $d_{min}(C_i,C_j)$
该变量用于衡量两个不同簇 $C_i$ 和 $C_j$ 之间最近的样本对距离，即从两个簇中各取一个样本，找到它们之间距离的最小值。其数学表达式为：
$$d_{min}(C_i,C_j)=\underset{{\mathbf{x}}_i\in C_i,{\mathbf{x}}_j\in C_j}{\min }dist({\mathbf{x}}_i,{\mathbf{x}}_j)$$

中心点 ${\mu }_i$
定义为簇 $C_i$ 所有样本的向量均值（类比质心），其数学表达式为：
$${\mu }_i=\frac{1}{|C_i|}\sum _{{\mathbf{x}}_i\in C_i}{\mathbf{x}}_i$$

两簇中心点的距离 $d_{cen}(C_i,C_j)$
直接计算两个簇中心点之间的距离：
$$d_{cen}(C_i,C_j)=dist({\mu }_i,{\mu }_j)$$

也可以用中心点来定义簇内平均距离：$avg(C_l)=\frac{1}{|C_l|}{\sum }_{\mathbf{x}\in C_l}dist(\mathbf{x},{\mu }_l)$，但这种定义方式和上述定义并不等价，原因在于dist函数不一定具有线性性质

借助上述变量，我们可以定义常见的性能度量：

Davies-Bouldin 指数 (DBI)
其数学表达式为：
$$DBI=\frac{1}{k}\sum _{i=1}^k\underset{j\ne i}{\max }\left(\frac{avg(C_i)+avg(C_j)}{dist({\mu }_i,{\mu }_j)}\right)$$
DBI 衡量的是每个簇的内部紧密度与其最相似簇的分离度之间的比值。具体来说：

• 如果一个簇内部很分散（即 $avg(C_i)$ 较大），或者它离某个其他簇很近（即 $dist({\mu }_i,{\mu }_j)$ 较小），都会导致 DBI 增大。
• DBI 的值越小越好，0 是理论上的最优值，取值范围为 $[0,\infty )$。

Dunn 指数 (DI)
其数学表达式为：
$$\text{DI}=\underset{1⩽i⩽k}{\min }\left\{\underset{j\ne i}{\min }\left(\frac{d_{\min }(C_i,C_j)}{{\max }_{1⩽l⩽k}\text{diam}(C_l)}\right)\right\}$$
DI 的计算过程可以分解为以下几步来理解：

1. ${\max }_{1⩽l⩽k}\text{diam}(C_l)$：遍历所有的 $k$ 个簇，找出其中最大的那个簇直径，这代表了整个聚类结果中最分散的簇的规模。
2. ${\min }_{j\ne i}\left(\frac{d_{\min }(C_i,C_j)}{{\max }_{1⩽l⩽k}\text{diam}(C_l)}\right)$：对于簇 $C_i$ 而言，这个值反映了它与它“最近的”或“最难区分的”邻居簇 $C_j$ 之间的分离情况（以全局最大直径为参照）。如果一个簇 $C_i$ 即便与它最难区分的邻居簇相比，分离度仍然很高，那么这个最小值就会比较大。
3. 最后，取所有簇的上述值中的最小值作为 DI 的最终结果。

• DI 的值越大，聚类效果越好，理论上没有上限。较大的 DI 值表示簇间分离度较好且簇内紧密度较高。

9.2 距离计算

上一章我们通过距离函数定义了几个内部指标，现在我们就来仔细研究一下这个距离函数的具体定义和性质。

在高中的时候，我们已经学过如何计算两个向量（样本）${\mathbf{x}}_i$和${\mathbf{x}}_j$之间的距离，最常用的计算方式是欧式距离（Euclidean distance），其公式为：
$$dist({\mathbf{x}}_i,{\mathbf{x}}_j)=\sqrt{\sum _{k=1}^n(x_{ik}-x_{jk}{)}^2}$$
其中$n$表示向量的维度，$x_{ik}$和$x_{jk}$分别表示第$i$个和第$j$个向量在第$k$维上的取值。

但欧式距离只是距离函数的一种特例，实际上向量之间的距离可以有多种不同的计算方式。要成为一个合法的距离函数，必须满足以下四个基本性质：

1. 非负性：任意两个向量的距离必须大于等于零，即$dist({\mathbf{x}}_i,{\mathbf{x}}_j)\ge 0$。这个性质保证了距离值是有意义的正数。
2. 同一性：当且仅当两个向量完全相同时，它们的距离为零，即$dist({\mathbf{x}}_i,{\mathbf{x}}_j)=0⟺{\mathbf{x}}_i={\mathbf{x}}_j$。这个性质保证了距离函数能够区分不同的向量。
3. 对称性：两个向量之间的距离与计算顺序无关，即$dist({\mathbf{x}}_i,{\mathbf{x}}_j)=dist({\mathbf{x}}_j,{\mathbf{x}}_i)$。这个性质符合我们对距离的直观理解。
4. 三角不等式：对于任意三个向量，两边之和大于第三边，即$dist({\mathbf{x}}_i,{\mathbf{x}}_j)\le dist({\mathbf{x}}_i,{\mathbf{x}}_k)+dist({\mathbf{x}}_k,{\mathbf{x}}_j)$。这个性质保证了距离函数在几何上的合理性。

任何满足距离函数四个基本条件的函数都可以作为有效的距离度量。在机器学习领域，最常用的距离函数是闵可夫斯基距离，其数学表达式为：
$$dis{t}_{mk}({\mathbf{x}}_i,{\mathbf{x}}_j)={\left(\sum _{k=1}^n|x_{ik}-x_{jk}{|}^p\right)}^{\frac{1}{p}}$$

这里需要特别注意的是参数 $p$ 的取值：

1. 当 $p=2$ 时，闵可夫斯基距离退化为欧氏距离，这是最常用的几何距离形式。
2. 当 $p=1$ 时，距离公式变为曼哈顿距离（也称为城市街区距离）：
   $$dis{t}_{man}({\mathbf{x}}_i,{\mathbf{x}}_j)=||{\mathbf{x}}_i-{\mathbf{x}}_j|{|}_1=\sum _{k=1}^n|x_{ik}-x_{jk}|$$

关于 $p$ 值的影响需要特别注意：

• 当 $p$ 取较小值（如 $p=1$）时，距离计算会对少数差异较大（取值范围大）的维度更加敏感。这意味着如果两个向量在少数维度上有显著差异，即使其他维度很相似，也会产生较大的距离值。
• 当 $p$ 取较大值时，距离计算会更关注多个维度上的整体差异。此时，在多个维度上都有中等差异的向量对距离的贡献会更明显。
• 随着 $p$ 增大，距离计算会越来越由差异最大的那个维度主导，其他维度的差异对最终距离的影响会相对减弱。

我们之前讨论过离散属性的数值化方法，其中提到对于有序离散属性，可以通过简单的数值映射来保持其顺序关系，这样仍然可以使用闵氏距离进行计算。但对于无序离散属性（比如颜色、品牌等类别数据），则需要采用其他方法，其中最常用的就是VDM（Value Difference Metric）方法。

在VDM方法中，我们定义以下统计量：

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

对于某个特定类别 $i$，属性 $u$ 取值为 $a$ 和 $b$ 的条件概率可以表示为：
$$P(i|a)=\frac{m_{u,a,i}}{m_{u,a}},P(i|b)=\frac{m_{u,b,i}}{m_{u,b}}$$

VDM的核心思想是：如果两个不同的属性值在不同类别上的分布相似，则认为它们在距离度量上是"接近的"。例如，"瓜蒂蜷缩"和"瓜蒂稍蜷"如果在"好瓜"和"坏瓜"的分类中表现出相似的统计规律，那么它们的VDM距离就会很小；反之，如果它们的统计分布差异很大，VDM距离就会很大。

因此VDM距离的数学定义如下：
$$VD{M}_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$$
其中 $p$ 是一个可调参数，通常取$1$或$2$。当 $p=1$ 时为曼哈顿距离形式，$p=2$ 时为欧氏距离形式。于是可以和闵氏距离结合处理所有样本。

假设一个样本前$n_c$个属性都是有序的，那么有：
$$minkovD{M}_p({\mathbf{x}}_i,{\mathbf{x}}_j)={\left(\sum _{u=1}^{n_c}|x_{iu}-x_{ju}{|}^p+\sum _{u=n_c+1}^{n}VD{M}_p(x_{iu},x_{ju})\right)}^{\frac{1}{p}}$$

另外，如果不同属性的重要程度不同的话，可以加上权重$w_i$，通常要求权重满足归一化条件$\sum w_i=1$。

此时公式可以表示为：
$$weightedMinkovD{M}_p({\mathbf{x}}_i,{\mathbf{x}}_j)={\left(\sum _{u=1}^{n_c}{w}_u\cdot |x_{iu}-x_{ju}{|}^p+\sum _{u=n_c+1}^n{w}_u\cdot VD{M}_p(x_{iu},x_{ju})\right)}^{\frac{1}{p}}$$

最后，我们通常通过距离函数来定义相似度度量，这种情况下距离值越大表示相似度越小。然而相似度度量也可以不依赖于传统的距离函数，此时虽然我们仍然使用"距离"这个术语来描述相似程度，但这类距离被称为非度量距离。在实际应用中，合适的距离计算方式可以通过距离度量学习的方法，根据具体的数据样本来自动确定。

9.3 原型聚类

现在我们进入聚类方法的学习，在现实聚类任务中，极为常用的一种聚类方法就是原型聚类。它的核心思想是：假设每个簇都可以通过一个“原型” (Prototype) 来代表。采用不同的原型表示，不同的求解方式将产生不同的算法，下面介绍几个常见算法：

9.3.1 k均值算法

给定一个包含 $m$ 个样本的数据集 D={x1,x2,…,xm}D = \{\boldsymbol{x}_1, \boldsymbol{x}_2, \dots, \boldsymbol{x}_m\}D={x1​,x2​,…,xm​}，其中每个样本 ${\mathbf{x}}_i$ 都是一个 $d$ 维的实数向量。我们的目标是将这些样本划分成 $k$ 个簇 $C_1,C_2,\dots ,C_k$
K均值算法的核心思想是通过均值向量（即簇中心）来表征每个簇的特征。对于簇$C_i$，其均值向量的数学定义为：
$${\mathbf{\mu }}_i=\frac{1}{|C_i|}\sum _{\mathbf{x}\in C_i}\mathbf{x}$$
该算法的目标是找到$k$个均值向量，并将每个数据样本分配到与之欧式距离最近的均值向量对应的簇中。这一过程实质上是最小化平方误差目标函数：
$$E=\sum _{i=1}^k\sum _{\mathbf{x}\in C_i}||\mathbf{x}-{\mathbf{\mu }}_i|{|}_2^2$$
需要特别说明的是：

1. 这里使用的距离度量是$L_2$范数（$p=2$）**，平方操作是为了简化求导计算
2. 该问题本质是NP难问题，因此实际采用贪心迭代策略求近似解

具体迭代流程如下：

1. 初始化阶段：从数据集$D$中随机选取$k$个样本作为初始均值向量 ${\mathbf{\mu }}_1,{\mathbf{\mu }}_2,\dots ,{\mathbf{\mu }}_k$
2. 迭代阶段：
   1. 簇分配：对每个样本${\mathbf{x}}_i$，计算其与所有均值向量的平方欧式距离$||{\mathbf{x}}_i-{\mathbf{\mu }}_j|{|}_2^2$，将其归入距离最小的簇$C_j$
   2. 原型更新：重新计算每个簇的均值向量${\mathbf{\mu }}_j$，更新为当前簇内所有样本的几何中心
   3. 终止判断：当满足以下任一条件时停止迭代：
      1. 均值向量变化量小于预设阈值$ϵ$：${\max }_j||{\mathbf{\mu }}_j^{(t)}-{\mathbf{\mu }}_j^{(t-1)}||<ϵ$
      2. 达到最大迭代次数$T_{max}$
      3. 目标函数$E$的变化率低于阈值$\delta$

9.3.2 学习向量化

与k均值聚类算法类似，学习向量量化（Learning Vector Quantization, LVQ）也是通过一组原型向量来表示数据特征。但区别在于：LVQ要求训练样本必须带有预先标注的类别标签，这使其本质上属于有监督学习范畴。

LVQ的工作机制是在k均值算法框架基础上，利用样本标签信息来动态调整原型向量的位置。其调整策略具有明确的分类导向性：

• 当某样本被当前原型向量正确分类时，该原型向量会向样本方向移动
• 当出现分类错误时，原型向量则会主动远离误分类样本
  这种基于标签反馈的迭代机制使得最终得到的原型向量能够同时满足两个目标：

1. 作为各类别的典型代表（类似聚类中心）；
2. 在特征空间中形成最优分类边界

我们假设有一个训练数据集 $D=\{({\mathbf{x}}_1,y_1),({\mathbf{x}}_2,y_2),\dots ,({\mathbf{x}}_m,y_m)\}$，其中 ${\mathbf{x}}_i$ 是一个 $d$ 维特征向量，$y_i$ 是其对应的类别标签。我们的目标是学习 $q$ 个原型向量，构成原型向量集合 P={p1,p2,…,pq}P = \{\mathbf{p}_1, \mathbf{p}_2, \dots, \mathbf{p}_q\}P={p1​,p2​,…,pq​}，其中每个原型向量 ${\mathbf{p}}_i$ 都对应着一个预设的真实类别。这里的 $q$ 通常与真实类别数相关，可能存在两种关系：

1. 一一对应：$q$ 等于类别数，此时每个预设类别 $t_i$ 严格对应一个原型向量。
2. 多对一：$q$ 是类别数的倍数，此时多个原型向量（如 $t_i,t_j,\dots$）可能对应同一个真实类别，用于表示该类别的内部复杂结构或子类。

具体实现步骤如下：

1. 初始化原型向量：从训练数据中为每个类别随机选择若干样本作为初始的原型向量，并为它们打上对应的类别标签。
2. 迭代学习过程：
   1. 寻找最近的原型向量：随机选取一个样本 ${\mathbf{x}}_i$，计算它与所有当前原型向量 ${\mathbf{p}}_j$（$j=1,\dots ,q$）之间的距离（通常使用欧式距离），找到距离最小的原型向量，称为胜出原型向量 ${\mathbf{p}}_{j^{\ast }}$。
   2. 更新胜出的原型向量 ${\mathbf{p}}_{j^{\ast }}$：
   • 类别匹配（$y_i=t_{j^{\ast }}$）：说明 ${\mathbf{p}}_{j^{\ast }}$ 能够正确代表样本 ${\mathbf{x}}_i$ 的类别。此时，我们希望拉近原型向量与样本的距离，增强其代表性。更新公式为：$${\mathbf{p}}_{j^{\ast }}^{\text{new}}={\mathbf{p}}_{j^{\ast }}^{\text{old}}+\eta \cdot ({\mathbf{x}}_i-{\mathbf{p}}_{j^{\ast }}^{\text{old}})$$
   • 类别不匹配（$y_i\ne t_{j^{\ast }}$）：说明 ${\mathbf{p}}_{j^{\ast }}$ 错误地吸引了样本 ${\mathbf{x}}_i$。此时，我们希望推远原型向量与样本的距离，减少未来错误。更新公式为：$${\mathbf{p}}_{j^{\ast }}^{\text{new}}={\mathbf{p}}_{j^{\ast }}^{\text{old}}-\eta \cdot ({\mathbf{x}}_i-{\mathbf{p}}_{j^{\ast }}^{\text{old}})$$
   • 其中，$\eta$ 是熟悉的学习率，取值范围为 $(0,1)$，并会随着迭代轮数逐渐衰减。
   3. 终止条件：迭代过程在以下情况之一满足时停止：
      • 达到预设的最大迭代轮数 $T_{\text{max\_epochs}}$。
      • 原型向量的位置变化非常小，或学习率 $\eta$ 衰减到足够小的阈值。

在LVQ（学习向量量化）算法训练完成后，我们会得到一组优化后的原型向量 {p1,…,pq}\{\mathbf{p}_1, \dots, \mathbf{p}_q\}{p1​,…,pq​}，以及它们对应的类别标签 {t1,…,tq}\{t_1, \dots, t_q\}{t1​,…,tq​}。当需要对一个新的未标记样本 ${\mathbf{x}}_{\text{new}}$ 进行分类时，需要按照以下步骤操作：

1. 计算距离：首先，需要计算 ${\mathbf{x}}_{\text{new}}$ 与每一个原型向量 ${\mathbf{p}}_j$ 之间的距离。这里的距离通常可以是欧氏距离
2. 寻找最近原型：在所有计算得到的距离中，找到与 ${\mathbf{x}}_{\text{new}}$ 距离最近的原型向量 ${\mathbf{p}}_{j^{\ast }}$
3. 分配类别标签：最后，将 ${\mathbf{x}}_{\text{new}}$ 的预测类别直接赋值为 ${\mathbf{p}}_{j^{\ast }}$ 对应的类别标签 $t_{j^{\ast }}$。这一步的本质是基于最近邻原则进行分类，即认为样本的类别由其最近的原型向量决定。

这种决策与K均值共享了相同的几何基础，即Voronoi剖分：

• 每个原型向量 ${\mathbf{p}}_j$ 在样本空间 $\chi$ 中定义了与其相关的一个区域 $R_j$，该区域内的所有点在分类时都会被赋予原型 ${\mathbf{p}}_j$ 的类别标签 $t_j$。具体来说，区域 $R_j$ 可以表示为：
  Rj={x∈χ∣d(x,pj)≤d(x,pk),∀k≠j}R_j = \{\mathbf{x} \in \chi \mid d(\mathbf{x}, \mathbf{p}_j) \leq d(\mathbf{x}, \mathbf{p}_k), \forall k \neq j\}Rj​={x∈χ∣d(x,pj​)≤d(x,pk​),∀k=j}
• 这些区域具有以下性质：
  • 不重叠性：任意两个不同的区域 $R_j$ 和 $R_k$（$j\ne k$）的交集为空，即 $R_j\cap R_k=\varnothing$。这确保了分类结果的唯一性，避免了重叠区域中样本类别归属不明确的问题。
  • 全覆盖性：所有区域的并集覆盖整个样本空间 $\chi$，即 ${\bigcup }_{j=1}^q{R}_j=\chi$。这意味着样本空间中的每一个点都必然属于某个原型向量的区域，不会出现未被覆盖的区域。
    因此，Voronoi剖分实际上是对样本空间 $\chi$ 的一种完整且无重叠的划分。

注意，虽然假设了一簇的样本点按照圆分布，但划分的区域边界不是圆而是一系列超平面组成的多面体。可以以$2$个均值向量为例，展开上述不等式后得到一个线性不等式。

9.3.3 高斯混合聚类

与前者聚类方法不同，高斯混合聚类(GMM) 的核心思想是基于概率建模。这种概率化的原型表示能更好地描述现实中的复杂数据分布情况：

第一，现实数据中不同簇可能具有完全不同的分布形态。比如某些簇可能呈现椭圆形分布（而非标准的球形分布），此时传统的均值法使用的线性决策边界就难以准确描述这种复杂形状。高斯混合模型通过协方差矩阵 $\Sigma$ 可以灵活地刻画不同方向的分布差异。

第二，实际场景中簇与簇之间往往存在概率化重叠。在重叠区域内的样本点并非绝对属于某个簇，而是以一定概率分属不同簇（例如一个样本40%概率属于小说爱好者，60%概率属于电视剧爱好者，不是说该样本只能喜欢小说或者电视剧）。相比之下，均值法的硬划分会丢失这种不确定性信息。

高斯混合模型正是为了克服这些限制而提出的。核心思想是假设观测到的数据点是由若干个高斯分布的混合生成的。每一个高斯分布就对应一个簇。
我们假设有 $K$个高斯分布，每个高斯分布对应一个权重系数（混合系数）${\pi }_k$，这些权重满足概率归一化条件 ${\sum }_{k=1}^K{\pi }_k=1$。生成数据的过程分为两步：首先以概率 ${\pi }_k$ 选择第 $k$ 个高斯分布，然后从该分布中采样生成数据点 ${\mathbf{x}}_i$。每个高斯分布由均值向量 ${\mu }_k$ 和 协方差矩阵 ${\mathbf{\Sigma }}_k$ 完全定义：

• ${\mu }_k$ 决定了该高斯分布的中心位置，即数据点最可能出现的区域。
• ${\mathbf{\Sigma }}_k$ 控制了分布的形状、方向和离散程度

因此，整个数据集可以看作是这 $K$ 个高斯分布的加权混合（混合模型）。对于任意一个数据点 ${\mathbf{x}}_i$，其概率密度函数可以表示为所有高斯分布的加权和：
$$\begin{array}{rl}p({\mathbf{x}}_i|\pi ,\mu ,\mathbf{\Sigma })& =\sum _{k=1}^K{\pi }_k\mathcal{N}({\mathbf{x}}_i|{\mu }_k,{\mathbf{\Sigma }}_k)\\ & =\sum _{k=1}^K{\pi }_k\frac{1}{(2\pi {)}^{\frac{n}{2}}|{\mathbf{\Sigma }}_k{|}^{\frac{1}{2}}}{e}^{\left(-\frac{1}{2}({\mathbf{x}}_i-{\mu }_k{)}^T{\mathbf{\Sigma }}_k^{-1}({\mathbf{x}}_i-{\mu }_k)\right)},\end{array}$$
模型的学习目标是通过训练数据 D={x1,x2,…,xN}D = \{\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_N\}D={x1​,x2​,…,xN​} 估计参数 ${\pi }_k$、${\mu }_k$ 和 ${\mathbf{\Sigma }}_k$。这里采用极大似然估计法，即最大化对数似然函数（假设数据点独立同分布）：
$$\ln P(X|\pi ,\mu ,\mathbf{\Sigma })=\sum _{i=1}^N\ln \left(\sum _{k=1}^K{\pi }_k\mathcal{N}({\mathbf{x}}_i|{\mu }_k,{\mathbf{\Sigma }}_k)\right).$$
由于直接对该函数求导难以得到解析解，因此采用EM算法进行迭代求解（详细内容可参考7.5节）。

初始化阶段：首先需要初始化一组参数 $(\pi ,\mu ,\mathbf{\Sigma })$。初始化方法可以是随机初始化，也可以先使用k均值算法得到$K$个簇，然后用这些簇的中心和协方差作为初始值。

迭代过程分为E步和M步，具体如下：

• E步：根据当前第$t$轮迭代的参数估计 $({\pi }^{(t)},{\mu }^{(t)},{\mathbf{\Sigma }}^{(t)})$，计算每个数据点 ${\mathbf{x}}_i$ 由第 $k$ 个高斯分量生成的后验概率，记为 $\gamma (z_{ik})$。具体计算基于贝叶斯定理：
  $$\gamma (z_{ik}{)}^{(t+1)}=P(z_{ik}=1|{\mathbf{x}}_i;{\pi }^{(t)},{\mu }^{(t)},{\mathbf{\Sigma }}^{(t)})=\frac{{\pi }_k^{(t)}\mathcal{N}({\mathbf{x}}_i|{\mu }_k^{(t)},{\mathbf{\Sigma }}_k^{(t)})}{{\sum }_{j=1}^K{\pi }_j^{(t)}\mathcal{N}({\mathbf{x}}_i|{\mu }_j^{(t)},{\mathbf{\Sigma }}_j^{(t)})}.$$
  其中，$z_{ik}=1$ 是一个指示变量，表示数据点 ${\mathbf{x}}_i$ 由第 $k$ 个高斯分量生成。

-M步：利用E步计算得到的 $\gamma (z_{ik}{)}^{(t+1)}$，重新估计模型参数 $(\pi ,\mu ,\mathbf{\Sigma })$，以最大化期望的对数似然函数。具体更新步骤如下：

1. 更新混合系数 ${\pi }_k$：新的 ${\pi }_k$ 反映第 $k$ 个高斯分量“负责”的数据点的比例。首先计算“有效点数”：
   $$N_k^{(t+1)}=\sum _{i=1}^N\gamma (z_{ik}{)}^{(t+1)},$$
   然后更新：
   $${\pi }_k^{(t+1)}=\frac{N_k^{(t+1)}}{N},\text{其中}N=\sum _{k=1}^K{N}_k^{(t+1)}.$$
2. 更新均值 ${\mu }_k$：新的均值是所有数据点 ${\mathbf{x}}_i$ 的加权平均，权重为 $\gamma (z_{ik}{)}^{(t+1)}$：
   $${\mu }_k^{(t+1)}=\frac{{\sum }_{i=1}^N\gamma (z_{ik}{)}^{(t+1)}{\mathbf{x}}_i}{N_k^{(t+1)}}.$$
3. 更新协方差矩阵 ${\mathbf{\Sigma }}_k$：新的协方差矩阵是所有数据点 ${\mathbf{x}}_i$ 相对于新均值 ${\mu }_k^{(t+1)}$ 的加权协方差：
   $${\mathbf{\Sigma }}_k^{(t+1)}=\frac{{\sum }_{i=1}^N\gamma (z_{ik}{)}^{(t+1)}({\mathbf{x}}_i-{\mu }_k^{(t+1)})({\mathbf{x}}_i-{\mu }_k^{(t+1)}{)}^T}{N_k^{(t+1)}}.$$

终止条件：迭代过程会在达到预设的最大轮次或参数变化小于某个阈值时终止。

9.4 密度聚类

密度聚类是一种基于样本分布密度进行分类的算法，其将簇定义为数据空间中被低密度区域分隔开的高密度区域。其中最著名的算法是 DBSCAN（Density-Based Spatial Clliustering of Applications with Noise），它通过分析数据点的局部密度分布来实现聚类，无需预先指定簇的数量（与K-Means等算法不同）。
DBSCAN的工作原理依赖于两个关键参数：

1. $ϵ$（邻域半径）：对于任意点 ${\mathbf{x}}_i$，其 $ϵ$-邻域定义为所有与 ${\mathbf{x}}_i$ 的距离不超过 $ϵ$ 的点集，即 Nϵ(xi)={xj∈D∣dist(xi,xj)≤ϵ}N_{\epsilon}(\mathbf{x}_{i}) = \{\mathbf{x}_{j} \in D \mid \text{dist}(\mathbf{x}_{i}, \mathbf{x}_{j}) \le \epsilon\}Nϵ​(xi​)={xj​∈D∣dist(xi​,xj​)≤ϵ} 其中 $D$ 是数据集，$\text{dist}(\cdot )$ 是距离度量。
2. MinPts（最小点数）：判断一个点是否为核心点的密度阈值。

根据这两个参数，DBSCAN将数据点分为三类：

• 核心点 (Core Point)：满足 $|N_{ϵ}({\mathbf{x}}_i)|\ge \text{MinPts}$ 的点 ${\mathbf{x}}_i$。这类点位于簇的高密度区域，是簇形成的"种子"。例如，若 $\text{MinPts}=5$，则一个点的 $ϵ$ 邻域内至少需要包含5个点（含自身）才能成为核心点。

• 边界点 (Border Point)：不满足核心点条件，但落在某个核心点的 $ϵ$-邻域内的点 ${\mathbf{x}}_j$。这类点位于簇的边缘区域，其密度不足以独立形成簇，但仍属于某个簇。数学表示为：$$|N_{ϵ}({\mathbf{x}}_j)|<\text{MinPts}\text{and}\exists {\mathbf{x}}_i\text{（核心点）},{\mathbf{x}}_j\in N_{ϵ}({\mathbf{x}}_i)$$

• 噪声点 (Noise Point)：既非核心点也非边界点的点 ${\mathbf{x}}_k$。这类点位于低密度区域，不被任何簇包含，通常对应异常值或噪声。判断条件为：$$|N_{ϵ}({\mathbf{x}}_k)|<\text{MinPts}\text{and}\forall {\mathbf{x}}_i,{\mathbf{x}}_k\notin N_{ϵ}({\mathbf{x}}_i)$$
  点与点之间的关系可以总结为：

• 密度直达：当 ${\mathbf{x}}_i$ 是一个核心点且 ${\mathbf{x}}_j$ 位于 ${\mathbf{x}}_i$ 的 $ϵ$-邻域内（即满足 $\text{dist}({\mathbf{x}}_i,{\mathbf{x}}_j)\le ϵ$）时，称 ${\mathbf{x}}_j$ 从 ${\mathbf{x}}_i$ 密度直达。需要注意的是，这个关系不一定是对称。具体来说，如果 ${\mathbf{x}}_i$ 是核心点，${\mathbf{x}}_j$ 在其邻域内，那么 ${\mathbf{x}}_j$ 可以从 ${\mathbf{x}}_i$ 直接密度可达；但如果 ${\mathbf{x}}_j$ 不是核心点（例如是一个边界点），则 ${\mathbf{x}}_i$ 不一定能从 ${\mathbf{x}}_j$ 直接密度可达。

• 密度可达：点 ${\mathbf{x}}_j$ 从点 ${\mathbf{x}}_i$ 密度可达，是指存在一个点的序列 ${\mathbf{x}}_{i1},{\mathbf{x}}_{i2},\dots ,{\mathbf{x}}_{im}$，其中 ${\mathbf{x}}_{i1}={\mathbf{x}}_i$ 且 ${\mathbf{x}}_{im}={\mathbf{x}}_j$，并且对于序列中的每一对相邻点 ${\mathbf{x}}_{ik}$ 和 ${\mathbf{x}}_{i(k+1)}$，${\mathbf{x}}_{i(k+1)}$ 都是从 ${\mathbf{x}}_{ik}$ 直接密度可达的。可以形象地理解为从核心点 ${\mathbf{x}}_i$ 开始，通过一系列核心点的接力传递，最终到达点 ${\mathbf{x}}_j$。需要注意的是，密度可达关系也不一定是对称的。

• 密度相连：两个点 ${\mathbf{x}}_i$ 和 ${\mathbf{x}}_j$ 是密度相连的，是指存在一个核心点 ${\mathbf{x}}_o$，使得 ${\mathbf{x}}_i$ 和 ${\mathbf{x}}_j$ 都从 ${\mathbf{x}}_o$ 密度可达。与密度直达和密度可达不同，密度相连关系是对称的。

基于以上概念，DBSCAN将簇定义为：由密度可达关系导出的最大密度相连样本集合。形式化地说，给定参数$ϵ$和$MinPts$，簇$C\subseteq D$是满足以下两个性质的非空子集：

1. 连接性：对于任意两个点${\mathbf{x}}_i\in C$和${\mathbf{x}}_j\in C$，它们必须是密度相连的。

2. 最大性：如果点${\mathbf{x}}_i\in C$，并且${\mathbf{x}}_j$可以从${\mathbf{x}}_i$密度可达，那么${\mathbf{x}}_j$也必须属于$C$。这保证了簇的完整性，即所有密度可达的点都必须被包含在同一个簇中。

DBSCAN算法的流程可以详细描述如下：

首先，需要选择合适的$ϵ$和$MinPts$值。这两个参数对聚类结果有重要影响：$ϵ$决定了邻域的大小，而$MinPts$定义了核心点的最小邻域点数要求。

基于广度优先遍历思想，算法从数据集中任意选择一个尚未被访问的点$\mathbf{p}$开始处理。这里需要检查$\mathbf{p}$是否满足核心点的条件：

• 如果$\mathbf{p}$是核心点（即$|N_{ϵ}(\mathbf{p})|\ge MinPts$）：

  1. 创建一个新簇$C$，并将$\mathbf{p}$加入其中，同时标记$\mathbf{p}$为已访问。
  2. 通过邻域扩展（或称种子集扩展）过程来生长这个簇：
     • 将$\mathbf{p}$的$ϵ$-邻域$N_{ϵ}(\mathbf{p})$中的所有点放入一个种子集合（队列）中。
     • 当种子集合不为空时：
       • 取出一个点$\mathbf{q}$，如果$\mathbf{q}$未被访问过：
         • 标记$\mathbf{q}$为已访问
         • 将$\mathbf{q}$加入当前簇$C$
         • 检查$\mathbf{q}$是否也是核心点（$|N_{ϵ}(\mathbf{q})|\ge MinPts$）：
           • 如果是，将其$ϵ$-邻域中所有未被访问或未分配的点加入种子集合
       • 如果$\mathbf{q}$已被访问但未分配（可能是之前标记的噪声点）：
         • 将其加入当前簇$C$（此时它成为边界点）
  3. 当种子集合为空时，簇$C$的生长完成。

• 如果$\mathbf{p}$不是核心点（$|N_{ϵ}(\mathbf{p})|<MinPts$）：

  • 暂时将$\mathbf{p}$标记为噪声点
  • 标记$\mathbf{p}$为已访问
  • 注意：这个点可能在后续处理中被重新分配，如果发现它可以从其他核心点密度可达

算法会继续选择下一个未访问的点，重复上述过程，直到所有点都被访问过。最终：

• 所有被分配到某个簇的点构成聚类结果
• 仍然标记为噪声的点就是最终的噪声

9.5 层次聚类

在聚类算法中，原型聚类（如K-means）需要预先设定簇的数量k，而密度聚类（如DBSCAN）需要预设邻域半径$ϵ$和最小样本数$MinPts$。这些参数的选择极其关键，因为不当的参数会导致模型效果不佳甚至无法收敛。相比之下，层次聚类完全不需要预设参数，它通过树状结构的构建过程自动形成聚类结果，称为“谱系图”或“树状图”。

层次聚类的基本思想是通过对簇进行一系列的合并（自底向上）或分裂（自顶向下）操作来构建聚类结构。具体有两种实现方式：

1. 凝聚型层次聚类（AGNES）
   采用自底而上的策略：

   • 初始阶段将每个数据点视为独立簇
   • 每次迭代合并距离最近的两个簇（通过特定的簇间距离度量）
   • 重复合并直到所有点聚为一个簇，或达到终止条件

2. 分裂型层次聚类（DIANA）
   采用自顶而下的策略：

   • 初始阶段将所有数据点视为一个簇
   • 每次迭代选择最不紧密的簇进行分裂
   • 重复分裂直到每个点成为独立簇，或满足停止条件

实践中自顶向下方法较少使用，因为大簇的分裂策略较难设计，因此AGNES更为常用。在层次聚类过程中，需要特别关注簇间距离的计算方法，主要有以下四种定义方式：

1. 单连接（最小距离）
   $$d_{min}(C_i,C_j)=\underset{\mathbf{x}\in C_i,\mathbf{z}\in C_j}{\min }dist(\mathbf{x},\mathbf{z})$$
   取两簇中最近样本对的距离，我们在之前见过。

2. 质心连接
   $$d_{cen}(C_i,C_j)=dist({\mu }_i,{\mu }_j)$$
   通过簇中心点（均值向量）的距离计算，我们之前也见过

3. 全连接（最大距离）
   $$d_{max}(C_i,C_j)=\underset{\mathbf{x}\in C_i,\mathbf{z}\in C_j}{\max }dist(\mathbf{x},\mathbf{z})$$
   取两簇中最远样本对的距离

4. 均连接（平均距离）
   $$d_{avg}(C_i,C_j)=\frac{1}{|C_i||C_j|}\sum _{\mathbf{x}\in C_i}\sum _{\mathbf{z}\in C_j}dist(\mathbf{x},\mathbf{z})$$
   计算两簇所有样本对距离的平均值
   不同的聚类算法在合并簇时有明显不同的特性：

• 单连接：容易受到噪声和异常值的影响。它的合并规则是基于两个簇中最近点之间的距离，因此少数几个接近的噪声点可能导致本应分离的簇过早合并，这种现象称为“链式效应”**，最终可能生成不合理的拉长形簇。
• 全连接：对异常值同样敏感，但表现方式不同。它基于两个簇中最远点之间的距离，如果一个簇的边缘存在远离中心的异常点，该簇与其他簇的距离会被人为拉大，导致本应合并的大簇被错误地拆分。
• 平均连接：是单连接和全连接的折衷方案。通过计算两簇间所有点对的平均距离，对噪声和异常值的敏感度显著降低，且倾向于生成大小和方差更均匀的簇，结果通常更稳定。
• 质心连接：可能引发倒置问题。由于合并后的新簇质心位置可能更接近其他簇，导致后续合并距离比之前更小（即谱系图出现交叉分支），破坏距离单调性，影响结果的可解释性。

现在我们来看整个算法步骤
假设数据集包含 $N$ 个点，记为 X={x1,x2,…,xN}X = \{\mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_N\}X={x1​,x2​,…,xN​}，具体流程如下：

1. 初始化阶段：

   • 将每个数据点 ${\mathbf{x}}_i$ 视为独立簇，即 Ci={xi}C_i = \{\mathbf{x}_i\}Ci​={xi​}。
   • 构建距离矩阵：选择上述合适的算法计算所有初始簇对之间的距离，生成 $N\times N$ 的对称矩阵，矩阵元素 $D_{ij}$ 表示簇 $C_i$ 与 $C_j$ 的距离。

2. 迭代合并阶段：

   • 寻找最近簇对：遍历距离矩阵，找到当前距离最小的两个簇 $C_A$ 和 $C_B$。
   • 合并操作：生成新簇 $C_{AB}=C_A\cup C_B$。
   • 更新距离矩阵：
     • 删除 $C_A$ 和 $C_B$ 对应的行与列。
     • 重新计算新簇 $C_{AB}$ 与其他簇 $C_k$ 的距离（根据所选连接方式，如单连接取最小距离，全连接取最大距离等）。
   • 重复上述步骤，直到仅剩一个簇或满足终止条件（如预设簇数量或距离阈值）。

最后我们就得到了一个谱系图

• 谱系图通过树状结构记录了整个合并过程
• 叶子节点对应原始数据点。
• 内部节点表示合并生成的中间簇。
• 通过水平切割谱系图，可一次性获得从 $N$ 个簇（最底层）到 $1$ 个簇（最顶层）的所有可能划分。例如，在高度 $h$ 处切割会得到对应 $K$ 个簇的结果，无需重新运行算法。这种层次化展示是谱系聚类的主要优势。