第9章：聚类 — 西瓜书学习笔记

本文是周志华《机器学习》（西瓜书）第9章 聚类（Clustering）的学习笔记，涵盖本章所有核心知识点，配有通俗类比与公式推导。

01. 聚类任务概述

什么是聚类？它能解决什么问题？

📌 核心定义

聚类（Clustering）是将数据集中的样本划分为若干个不相交的子集，
每个子集称为一个簇（Cluster）。聚类的目标是：

• 簇内相似性最大：同一簇内的样本应尽可能彼此相似
• 簇间差异性最大：不同簇的样本应尽可能不同

形式化表示：给定样本集 $D = \{x_1, x_2, \ldots, x_m\}$，聚类算法将 $D$
划分为 $k$ 个不相交的簇 $\{C_l \mid l = 1, 2, \ldots, k\}$，
满足 $C_i \cap C_j = \emptyset$（$i \neq j$）且 $\bigcup_{l=1}^k C_l = D$。
每个样本 $x_j$ 的簇标记为 $\lambda_j \in \{1, 2, \ldots, k\}$。

🍎 通俗理解

想象你去超市买东西，超市把所有商品摆放在不同的货架区域：
水果区、蔬菜区、零食区、饮料区……这就是聚类！
超市并没有人告诉机器”这是苹果，那是香蕉”，而是商品本身的相似性
（都是新鲜食品、都是甜的、都需要冷藏）决定了它们应该放在一起。

        聚类就是让算法自动完成这个"归类摆放"的过程，而且事先我们**不告诉算法**
        有哪些类别、每个样本属于哪类。

🔑 与分类的核心区别

分类（有监督）：训练数据有标签，模型学习”苹果→水果”的映射关系。

聚类（无监督）：训练数据没有标签，模型自己发现数据的自然分组结构。
聚类结果的”簇标记”是没有语义的，需要人来解释含义。

🌍 应用场景

• 👥 用户分群：将电商用户按购买行为自动分为不同群体，用于精准营销
• 🖼️ 图像分割：将图像中的像素按颜色或纹理聚类，实现前景背景分离
• 📰 文档聚类：把新闻文章自动归类为科技、体育、娱乐等主题
• 🧬 基因分析：发现具有相似表达模式的基因群组，辅助疾病研究
• 🔍 异常检测：偏离所有簇的样本往往是异常点（如信用卡欺诈）
• 🗺️ 地理分析：发现城市中的商业集聚区、居民区分布规律

02. 性能度量

如何评价聚类结果的好坏？

聚类性能度量（也叫聚类有效性指标）分为两大类：

📎 外部指标（External Index）

将聚类结果与某个参考模型进行比较。参考模型通常是由领域专家给出的”正确答案”。

📎 内部指标（Internal Index）

直接考察聚类结果，不依赖任何参考模型。评估簇的内聚性和分离性。

📐 外部指标：基础概念

设 $D$ 中包含 $m$ 个样本，设聚类结果的簇划分为 $\mathcal{C} = \{C_1, \ldots, C_k\}$，
参考模型的簇划分为 $\mathcal{C}^* = \{C_1^*, \ldots, C_s^*\}$。
考虑所有样本对 $(x_i, x_j)$，定义四个基本量：

📐 四个基本集合

• $a = |SS|$：在 $\mathcal{C}$ 中**同簇**，在 $\mathcal{C}^*$ 中也**同簇**的样本对数
• $b = |SD|$：在 $\mathcal{C}$ 中**同簇**，在 $\mathcal{C}^*$ 中**不同簇**的样本对数
• $c = |DS|$：在 $\mathcal{C}$ 中**不同簇**，在 $\mathcal{C}^*$ 中**同簇**的样本对数
• $d = |DD|$：在 $\mathcal{C}$ 中**不同簇**，在 $\mathcal{C}^*$ 中也**不同簇**的样本对数

显然有：$a + b + c + d = \dfrac{m(m-1)}{2}$（所有可能的样本对总数）

🍎 通俗理解

把同班同学按”兴趣”分组（$\mathcal{C}$），再和”宿舍楼层”（参考 $\mathcal{C}^*$）对比：

a：李明和王芳——兴趣相同 且 同楼层 ✅✅

b：李明和张强——兴趣相同 但 不同楼层 ✅❌

c：李明和赵丽——兴趣不同 但 同楼层 ❌✅

d：李明和陈伟——兴趣不同 且 不同楼层 ❌❌

        {% _internal_math_placeholder 383 %} 越大说明聚类结果和参考模型越一致！

三大外部指标

📐 Jaccard 系数（JC）

$$\text{JC} = \frac{a}{a + b + c}$$

取值范围 $[0, 1]$，越大越好。分子是”双方都同意归为同类”，分母是”至少有一方认为同类”。

📐 FM 指数（FMI）

$$\text{FMI} = \sqrt{\frac{a}{a+b} \cdot \frac{a}{a+c} }$$

取值范围 $[0, 1]$，越大越好。是精确率和召回率的几何平均，类似分类任务中的 F1 分数。

📐 Rand 指数（RI）

$$\text{RI} = \frac{2(a + d)}{m(m-1)}$$

取值范围 $[0, 1]$，越大越好。衡量”正确分配的样本对”占总样本对的比例。
直觉理解：聚类和参考模型达成一致的样本对越多，RI 越高。

📐 内部指标

内部指标不依赖参考模型，直接通过计算样本间的距离来衡量聚类质量。
先定义几个距离符号：

📐 基本距离符号

• $\text{avg}(C)$ = 簇 $C$ 内所有样本对的**平均距离**：$\text{avg}(C) = \dfrac{2}{|C|(|C|-1)} \sum_{1 \le i < j \le |C|} \text{dist}(x_i, x_j)$
• $\text{diam}(C)$ = 簇 $C$ 内样本间的**最大距离**（直径）：$\text{diam}(C) = \max_{1 \le i < j \le |C|} \text{dist}(x_i, x_j)$
• $d_{\min}(C_i, C_j)$ = 两簇间的**最近样本距离**：$d_{\min}(C_i, C_j) = \min_{x_i \in C_i, x_j \in C_j} \text{dist}(x_i, x_j)$
• $d_{\text{cen} }(C_i, C_j)$ = 两簇**中心点之间的距离**：$d_{\text{cen} }(C_i, C_j) = \text{dist}(\mu_i, \mu_j)$

📐 DB 指数（DBI）—— 越小越好

$$\text{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)$$

分子：两个簇各自的”内部松散程度”之和（簇内平均距离越大，说明簇越散）

        分母：两簇中心之间的距离（越远越好）

        理想情况：各簇紧凑（分子小）且相互远离（分母大），DBI 越小越好。

📐 Dunn 指数（DI）—— 越大越好

$$\text{DI} = \min_{1 \le i \le k} \left\{ \min_{j \neq i} \left( \frac{d_{\min}(C_i, C_j)}{\max_{1 \le l \le k} \text{diam}(C_l)} \right) \right\}$$

分子：任意两簇之间的最短距离（簇间最小距离）

        分母：所有簇中最大的直径（簇内最大分散程度）

        理想情况：簇间距离大、簇本身紧凑，DI 越大越好。

🍎 通俗理解 DBI vs DI

想象你在操场上划定了几个”兴趣小组”的活动区域（簇）：

DBI 评估的是：每个小组内部站得有多散 ÷ 小组间距离有多远。
好的分组是小组内抱团紧（分子小），不同小组间离得远（分母大），所以 DBI 越小越好。

DI 评估的是：不同小组之间最近的两个人有多远 ÷ 最大的那个小组直径多宽。
好的分组是不同组的人之间离得远，每个组本身面积小，所以 DI 越大越好。

03. 距离计算

如何量化两个样本之间的”相似度”？

📏 距离度量的基本性质

聚类中使用的距离函数 $\text{dist}(\cdot, \cdot)$ 需满足以下四条基本性质：

📐 距离公理

• 非负性：$\text{dist}(x_i, x_j) \ge 0$（距离不能为负数）
• 同一性：$\text{dist}(x_i, x_j) = 0$ 当且仅当 $x_i = x_j$（同一个点到自己距离为0）
• 对称性：$\text{dist}(x_i, x_j) = \text{dist}(x_j, x_i)$（A到B的距离等于B到A的距离）
• 直递性（三角不等式）：$\text{dist}(x_i, x_j) \le \text{dist}(x_i, x_k) + \text{dist}(x_k, x_j)$（直线最短）

⚠️ 注意

在某些聚类场景（如有序距离、相似度度量）中，三角不等式未必成立，
我们称之为**”非度量距离”**。不满足三角不等式也可以使用，
只是不叫”严格的距离度量”。

📏 有序属性：闵可夫斯基距离（Minkowski Distance）

当属性取值为连续的有序数值时（如身高、体重、温度），使用闵可夫斯基距离：

📐 闵可夫斯基距离

设样本 $x_i = (x_{i1}, x_{i2}, \ldots, x_{in})$，$x_j = (x_{j1}, x_{j2}, \ldots, x_{jn})$

$$\text{dist}_{\text{mk} }(x_i, x_j) = \left( \sum_{u=1}^{n} |x_{iu} - x_{ju}|^p \right)^{1/p}$$

📐 p=1：曼哈顿距离

$$\text{dist} = \sum_{u=1}^{n} |x_{iu} - x_{ju}|$$

也叫”出租车距离”——只能沿坐标轴方向走，如同城市街道。

📐 p=2：欧氏距离

$$\text{dist} = \sqrt{\sum_{u=1}^{n} (x_{iu} - x_{ju})^2}$$

日常最直觉的”直线距离”，就是尺子量出来的距离。

💡 p→∞：切比雪夫距离

$\text{dist} = \max_u |x_{iu} - x_{ju}|$，即各维度差值的最大值。用于象棋中国王走步的最少步数计算。

🍎 城市地图类比

两地之间的距离：
🔵 欧氏距离：直接挖隧道的直线距离
🟡 曼哈顿距离：只走横街竖巷，只能转直角
🔴 切比雪夫距离：国际象棋棋盘上国王的最少步数

        同样的两点，三种"距离"值通常不同！选哪种距离取决于你的应用场景。

📏 无序属性：VDM（Value Difference Metric）

对于离散无序属性（如性别、颜色、城市名），不能直接做减法，
需要用 VDM 来衡量两个取值之间的差异：

📐 VDM 距离

设 $m_{u,a}$ 是属性 $u$ 上取值为 $a$ 的样本数，$m_{u,a,i}$ 是第 $i$ 个簇中属性 $u$ 取值为 $a$ 的样本数，$k$ 是簇数，则：

$$\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$$

直觉：如果属性值 $a$ 和 $b$ 在各个簇中的”分布情况”越相似，则它们越接近。

🍎 通俗理解 VDM

假设要比较”颜色”属性中”红色”和”粉色”的差异：

        我们看红色样本中有多少比例在簇1、簇2、簇3……

        再看粉色样本中有多少比例在簇1、簇2、簇3……

        如果两者的"分布情况"很像（比如都主要分布在簇1），
        那就说明"红色"和"粉色"比较相似。

📏 混合属性处理

实际数据往往同时包含有序属性（数值型）和无序属性（类别型）。
设样本有 $n_c$ 个有序属性和 $n-n_c$ 个无序属性，则混合属性距离：

📐 混合属性闵可夫斯基距离

$$\text{dist}_{\text{mix} }(x_i, 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)^{1/p}$$

💡 小结

• 数值型属性 → 闵可夫斯基距离（欧氏、曼哈顿等）
• 类别型属性 → VDM
• 混合型 → 加权组合两者

04. k 均值算法（k-means）

最经典的原型聚类方法

⚡ 算法思想

k-means 是**原型聚类（Prototype-based Clustering）的代表算法。
它的核心思想是：用 $k$ 个原型向量（均值向量）**来代表各个簇，
通过迭代优化最小化每个样本到其所属簇中心的距离之和。

📐 优化目标（最小化平方误差）

$$E = \sum_{i=1}^{k} \sum_{x \in C_i} \|x - \mu_i\|_2^2$$

其中 $\mu_i = \dfrac{1}{|C_i|} \sum_{x \in C_i} x$ 是第 $i$ 个簇的均值向量（质心）

🍎 通俗理解

设想你要在城市里选 $k$ 个外卖仓库，让所有顾客到最近仓库的总距离最小。

        初始时随机放 {% _internal_math_placeholder 433 %} 个仓库，然后每个顾客"认领"最近的仓库；
        接着把每个仓库移动到它服务的所有顾客的中心位置；
        顾客重新认领，仓库再移动……如此反复，直到仓库位置不再变化。
        这就是 k-means！

⚡ 算法步骤

1. 初始化：从 $D$ 中随机选取 $k$ 个样本作为初始均值向量 $\{\mu_1, \mu_2, \ldots, \mu_k\}$
2. 分配步（E步）：对每个样本 $x_j$，计算它到所有均值向量的距离，
   将其分配到最近的那个簇：
   $\lambda_j = \arg\min_{i \in \{1,\ldots,k\} } \|x_j - \mu_i\|_2$
3. 更新步（M步）：重新计算每个簇的均值向量（质心）：
   $\mu_i' = \dfrac{1}{|C_i|} \sum_{x \in C_i} x$
4. 收敛判断：若所有均值向量都不再发生变化（$\mu_i' = \mu_i$），则停止；否则令 $\mu_i = \mu_i'$，返回第2步

k-means Algorithm
输入：数据集 D = {x₁,...,xₘ}，聚类数 k
输出：簇划分 {C₁, C₂, ..., Cₖ}

初始化：从 D 中随机选 k 个样本作为 μ₁, μ₂, ..., μₖ
repeat
  令 Cᵢ = ∅  (i = 1, 2, ..., k)
  for j = 1, 2, ..., m do
    计算 xⱼ 与每个 μᵢ 的距离 dᵢⱼ = ‖xⱼ - μᵢ‖₂
    找最近的簇：λⱼ = argmin dᵢⱼ
    将 xⱼ 加入簇 Cλⱼ
  end for
for i = 1, 2, ..., k do
    计算新均值：μᵢ' = (1/|Cᵢ|) Σ x
    if μᵢ' ≠ μᵢ then
      更新 μᵢ ← μᵢ'
    end if
end for
until 所有均值向量均未更新
return 簇划分 {C₁, ..., Cₖ}

k-means 迭代过程示意图（k=2）

⚡ 优缺点与注意事项

✅ 优点

• 算法简单，易于实现和理解
• 时间复杂度低，适合大规模数据：$O(mkT)$，$m$ 为样本数，$k$ 为簇数，$T$ 为迭代次数
• 可扩展性好，工业界广泛应用

❌ 缺点

• 必须预先指定 k 值，而 k 往往难以确定
• 对初始中心点敏感，不同初始值可能导致不同结果（可能陷入局部最优）
• 只能发现凸形（球形）簇，对非球形分布效果差
• 对**离群点（噪声）**很敏感
• 每个样本只属于一个簇（硬分配），不能处理模糊边界

🔑 理论保证

k-means 的目标函数 $E$ 单调不增，且 $E \ge 0$，因此算法一定会收敛（但不保证全局最优）。
实践中通常多次随机初始化，取 $E$ 最小的结果；或使用 k-means++ 改进初始化策略。

05. 学习向量量化（LVQ）

有标记信息辅助的原型学习

🔄 与 k-means 的区别

学习向量量化（Learning Vector Quantization，LVQ）也是原型聚类，
但它利用了样本的标记信息，使聚类过程可以受到监督信息的引导。
因此 LVQ 是一种介于无监督和有监督之间的学习方法，目的是学出一组
原型向量来覆盖整个样本空间。

k-means

• 无监督，无标记信息
• 原型 = 簇的均值
• 原型随着簇成员变化而更新

LVQ

• 有监督，利用标记信息
• 原型 = 代表各类的”典型样本”
• 根据标记的对错来更新原型

🔄 算法流程

📐 LVQ 核心更新规则

设样本 $x_j$ 的标记为 $y_j$，找到距 $x_j$ 最近的原型向量 $p^*$，其标记为 $t^*$：

• 若 $y_j = t^*$（标记相同）：原型向 $x_j$ 靠近：

$$p' = p^* + \eta \cdot (x_j - p^*)$$

• 若 $y_j \neq t^*$（标记不同）：原型向 $x_j$ 远离：

$$p' = p^* - \eta \cdot (x_j - p^*)$$

$\eta \in (0, 1)$ 为学习率

🍎 通俗理解

LVQ 的学习过程就像训练”班级代表”：

        每个班（类别）选一个代表（原型向量）。来了一个新同学，
        看他最像哪个代表：

        ➕ 如果这个代表和新同学是**同班的**，代表就往新同学方向走近一点（"你们确实像"）

        ➖ 如果代表和新同学**不同班**，代表就往反方向走（"你们不是一类，别搞混"）


        最终，每个代表都成了本班特征的"精华提炼"，同时和其他班的代表保持距离。

LVQ Algorithm
输入：样本集 D = {(x₁,y₁),...,(xₘ,yₘ)}, 原型向量个数 q, 各类原型向量数目 n₁,...,nN, 学习率 η
初始化：从各类样本中随机选取 nᵢ 个样本作为各类原型向量 {p₁,...,pq}
repeat
  从 D 中随机选取样本 (xⱼ, yⱼ)
  计算 xⱼ 与所有原型向量的距离 dᵢ = ‖xⱼ - pᵢ‖
  找最近的原型 p* = argmin dᵢ，其标记为 t*
  if yⱼ == t* then
    p' = p* + η·(xⱼ - p*)   // 靠近
else
    p' = p* - η·(xⱼ - p*)   // 远离
end if
  更新 p* ← p'
until 满足停止条件
return 原型向量集 {p₁, p₂, ..., pq}

💡 LVQ 的应用

LVQ 完成后，可以用学到的原型向量对新样本进行分类或聚类——
每个样本被分配到最近原型向量对应的类别。
每个原型向量 $p_i$ 定义了一个 Voronoi 区域（即比它更近的所有点的集合），
这些区域共同构成对样本空间的划分。

06. 高斯混合聚类（GMM）

概率视角下的软性聚类

🌊 核心思想

与 k-means 不同，高斯混合聚类（Gaussian Mixture Model，GMM）
从概率生成模型的角度看待聚类：
假设数据是由 $k$ 个高斯分布”混合”产生的，每个高斯分布对应一个簇。
输出的不再是”每个样本属于哪个簇”，而是”每个样本以多大概率属于哪个簇”（软聚类）。

🍎 通俗理解

想象一个校园里有两类人群：高个子（篮球队）和矮个子（体操队）。
身高分布像两座”山峰”叠在一起——
每座山峰是一个高斯分布，两个混合起来就是全校身高的分布。

        现在来了一个身高175cm的同学，
        GMM 不会硬性说"你是篮球队或体操队"，
        而是说"你有 60% 的概率是篮球队，40% 的概率是体操队"。
        这就是**软聚类**的魅力！

🌊 数学基础

📐 高斯分布（正态分布）

$n$ 维高斯分布的概率密度函数：

$$p(x) = \frac{1}{(2\pi)^{n/2} |\Sigma|^{1/2} } \exp\left( -\frac{1}{2}(x-\mu)^T \Sigma^{-1} (x-\mu) \right)$$

其中 $\mu$ 是均值向量，$\Sigma$ 是协方差矩阵（对称正定），记为 $p(x | \mu, \Sigma)$

📐 高斯混合分布

混合高斯模型定义为 $k$ 个高斯分布的加权和：

$$p_{\mathcal{M} }(x) = \sum_{i=1}^{k} \alpha_i \cdot p(x | \mu_i, \Sigma_i)$$

• $\alpha_i > 0$ 为第 $i$ 个高斯分量的**混合系数**，且 $\sum_{i=1}^k \alpha_i = 1$
• $\mu_i$ 为第 $i$ 个分量的**均值向量**
• $\Sigma_i$ 为第 $i$ 个分量的**协方差矩阵**

📐 后验概率（样本属于第 i 个分量的概率）

由贝叶斯定理，给定样本 $x_j$，其由第 $i$ 个高斯分量生成的后验概率为：

$$\gamma_{ji} = P(z_j = i | x_j) = \frac{\alpha_i \cdot p(x_j | \mu_i, \Sigma_i)}{\sum_{l=1}^{k} \alpha_l \cdot p(x_j | \mu_l, \Sigma_l)}$$

🌊 EM 算法求解 GMM

GMM 的参数 $\{(\alpha_i, \mu_i, \Sigma_i)\}$ 无法直接求解（因为每个样本”属于哪个分量”是隐变量），
需要用期望最大化（EM）算法迭代求解。

E步（期望步）

固定当前参数，计算每个样本属于每个分量的后验概率 $\gamma_{ji}$（责任度）。

M步（最大化步）

利用后验概率 $\gamma_{ji}$ 更新模型参数，使似然函数最大化。

📐 M步更新公式

令 $\hat{m}_i = \sum_{j=1}^m \gamma_{ji}$（第 $i$ 个分量的”等效样本数”），则：

$$\hat{\mu}_i = \frac{\sum_{j=1}^m \gamma_{ji} x_j}{\hat{m}_i}$$

$$\hat{\Sigma}_i = \frac{\sum_{j=1}^m \gamma_{ji} (x_j - \hat{\mu}_i)(x_j - \hat{\mu}_i)^T}{\hat{m}_i}$$

$$\hat{\alpha}_i = \frac{\hat{m}_i}{m}$$

Gaussian Mixture Model — EM Algorithm
初始化：随机设置 αᵢ, μᵢ, Σᵢ (i=1,...,k)
repeat
// ========= E 步 =========
for j = 1, ..., m do
for i = 1, ..., k do
      γⱼᵢ = αᵢ·p(xⱼ|μᵢ,Σᵢ) / Σₗ αₗ·p(xⱼ|μₗ,Σₗ)   // 后验概率
end for
end for
// ========= M 步 =========
for i = 1, ..., k do
    m̂ᵢ = Σⱼ γⱼᵢ
    μ̂ᵢ = (1/m̂ᵢ) Σⱼ γⱼᵢ·xⱼ           // 加权均值
    Σ̂ᵢ = (1/m̂ᵢ) Σⱼ γⱼᵢ·(xⱼ-μ̂ᵢ)(xⱼ-μ̂ᵢ)ᵀ  // 加权协方差
    α̂ᵢ = m̂ᵢ / m                      // 混合系数
end for
until 似然函数 log-likelihood 变化小于阈值 ε
return 参数 {(α̂ᵢ, μ̂ᵢ, Σ̂ᵢ)}

💡 GMM vs k-means

• k-means 是 GMM 的一个特殊情况：当所有协方差矩阵都是 $\sigma^2 I$ 且 $\sigma \to 0$ 时，GMM 退化为 k-means
• GMM 可以描述椭圆形的簇（通过协方差矩阵），而 k-means 只能描述球形簇
• GMM 提供软聚类（概率分配），k-means 是硬聚类
• GMM 最终聚类时，将样本分配给后验概率最大的分量：$\lambda_j = \arg\max_i \gamma_{ji}$

07. 密度聚类：DBSCAN

基于密度的空间聚类，能发现任意形状的簇

🌐 核心思想

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）
是基于密度的聚类算法，核心思想是：高密度区域连通形成簇，低密度区域是噪声。
与 k-means 完全不同，DBSCAN 不需要指定 $k$，并且可以发现任意形状的簇。

🍎 通俗理解

想象夜晚城市的卫星俯拍图：灯光密集的区域就是城市（簇），
灯光稀疏的地方是农村或荒野（噪声）。
你不需要事先知道有几个城市，只要规定”灯光密度超过某个阈值就算城市”，
然后把相邻的密集区域连起来，就找到了所有城市。
这就是 DBSCAN 的思路！

🌐 核心概念（必须掌握！）

DBSCAN 有两个关键参数：邻域半径 $\epsilon$ 和最小样本数 MinPts，以及以下核心概念：

📌 ε-邻域

对于样本 $x_j$，其 $\epsilon$-邻域包含所有与 $x_j$ 距离不超过 $\epsilon$ 的样本：

$N_\epsilon(x_j) = \{x_i \in D \mid \text{dist}(x_i, x_j) \le \epsilon\}$

🍎 类比

以某人为圆心、半径 $\epsilon$ 画一个圆，圆内的所有人就是它的 $\epsilon$-邻域。

📌 核心对象（Core Object）

若 $|N_\epsilon(x_j)| \ge \text{MinPts}$，即 $x_j$ 的 $\epsilon$-邻域内包含至少 MinPts 个样本，则称 $x_j$ 为核心对象。

🍎 类比

某个人周围（半径 $\epsilon$ 内）至少有 MinPts 个朋友，那他就是一个"人气王"（核心对象）。人气不够的就是边缘人或噪声。

📌 密度直达（Directly Density-Reachable）

若 $x_j \in N_\epsilon(x_i)$ 且 $x_i$ 是核心对象，则称 $x_j$ 由 $x_i$ 密度直达（$x_i \to x_j$）。

🍎 类比

人气王 $x_i$ 的朋友圈里有 $x_j$，则 $x_j$ 是 $x_i$ 的直接下属/朋友。注意：密度直达不一定是对称的（$x_j$ 不一定是核心对象）。

📌 密度可达（Density-Reachable）

若存在一个样本序列 $p_1, p_2, \ldots, p_n$，其中 $p_1 = x_i$，$p_n = x_j$，且 $p_{t+1}$ 由 $p_t$ 密度直达，则 $x_j$ 由 $x_i$ 密度可达。

🍎 类比

通过"朋友的朋友的朋友……"的链条能到达某人，就是密度可达。是传递闭包。

📌 密度相连（Density-Connected）

若存在 $x_k$ 使得 $x_i$ 和 $x_j$ 均由 $x_k$ 密度可达，则 $x_i$ 与 $x_j$ 密度相连。

🔑 核心定义

簇的定义：一个簇 $C$ 是满足以下条件的最大样本子集：
① 连通性：$C$ 中任意两点 $x_i, x_j$ 密度相连；
② 最大性：若 $x_i \in C$ 且 $x_j$ 由 $x_i$ 密度可达，则 $x_j \in C$。

🍎 类比

$x_i$ 和 $x_j$ 有一个共同的"人气王"朋友，就说他们密度相连——这是定义簇的基础！

🌐 DBSCAN 算法步骤

1. 找出所有核心对象，存入集合 $\Omega$
2. 从 $\Omega$ 中随机取一个核心对象 $o$，初始化一个新簇 $C = \{o\}$
3. 将 $o$ 的 $\epsilon$-邻域内所有样本加入队列 $Q$
4. 从 $Q$ 中取出一个样本 $q$，加入 $C$；若 $q$ 也是核心对象，将其 $\epsilon$-邻域未处理的样本加入 $Q$；重复直到 $Q$ 为空
5. 将核心对象 $o$ 从 $\Omega$ 中移除，输出簇 $C$；重复步骤2~5直到 $\Omega$ 为空
6. 未被任何簇包含的样本即为噪声点（离群点）

DBSCAN Algorithm
输入：数据集 D，邻域参数 (ε, MinPts)
输出：簇划分 C

// 第一步：找所有核心对象
Ω = {}  // 核心对象集合
for j = 1, ..., m do
if |Nε(xⱼ)| ≥ MinPts then
    Ω = Ω ∪ {xⱼ}
end for

k = 0; Γ = D  // k:簇数, Γ:未被访问的样本集合
while Ω ≠ ∅ do
  Γ_old = Γ
  从 Ω 随机选一个核心对象 o
  Q = {o}; Γ = Γ \ {o}
  while Q ≠ ∅ do
    取 Q 中的一个样本 q; Q = Q \ {q}
    if q 是核心对象 then
      Δ = Nε(q) ∩ Γ  // 邻域中尚未处理的样本
      Q = Q ∪ Δ; Γ = Γ \ Δ
  k = k+1; 簇 Cₖ = Γ_old \ Γ
  Ω = Ω \ Cₖ
return {C₁, C₂, ..., Cₖ}  // Γ 中剩余为噪声点

✅ DBSCAN 优点

• 可以发现任意形状的簇
• 能自动识别噪声点（离群点）
• 不需要预先指定 $k$
• 对大多数情况鲁棒性好

❌ DBSCAN 缺点

• 需要设置 $\epsilon$ 和 MinPts 两个参数，较敏感
• 对密度不均匀的数据效果差（密度差异大的簇难以用单一 $\epsilon$ 描述）
• 高维数据中密度难以定义
• 大数据集时计算开销较大

08. 层次聚类：AGNES

从底向上逐步合并，构建簇的层次结构

🌳 核心思想

**AGNES（AGglomerative NESting）**是自底向上的凝聚层次聚类算法。
它将每个样本视为一个独立的簇，然后不断合并最相似的两个簇，
直到满足停止条件（如簇数达到 $k$）。

🍎 通俗理解

想象生物分类学：每个物种最初都是独立的个体，然后按照亲缘关系逐步合并——
先合并为”属”，再合并为”科”、”目”、”纲”……最终所有生物汇聚到一棵树上。

        AGNES 就是不断地把"最像"的两组合并，直到剩下 {% _internal_math_placeholder 559 %} 组为止。
        整个过程形成一棵**树状图（Dendrogram）**，可以直观看到聚类的层次关系。

🌳 簇间距离的三种度量

AGNES 的关键在于如何定义两个簇之间的距离，这决定了每次合并哪两个簇：

📐 最小距离（单链接, Single Linkage）

$$d_{\min}(C_i, C_j) = \min_{x \in C_i, z \in C_j} \text{dist}(x, z)$$

两簇中最近的两个样本的距离。容易产生”链式效应”——把两个原本不相似的簇通过中间点串联起来。

📐 最大距离（全链接, Complete Linkage）

$$d_{\max}(C_i, C_j) = \max_{x \in C_i, z \in C_j} \text{dist}(x, z)$$

两簇中最远的两个样本的距离。倾向于产生大小相近的紧凑簇，但对离群点敏感。

📐 平均距离（均链接, Average Linkage）

$$d_{\text{avg} }(C_i, C_j) = \frac{1}{|C_i||C_j|} \sum_{x \in C_i} \sum_{z \in C_j} \text{dist}(x, z)$$

两簇中所有样本对的平均距离。综合了单链接和全链接，通常效果最好。

🍎 三种链接的直觉对比

两个城市（簇）之间的”距离”：

        🔵 **单链接**：两城最近的两栋楼的距离（最乐观估计）

        🔴 **全链接**：两城最远的两栋楼的距离（最悲观估计）

        🟢 **均链接**：两城所有楼两两配对的平均距离（综合估计）

🌳 算法步骤与树状图

AGNES Algorithm
输入：数据集 D，聚类数 k，距离度量类型
输出：簇划分 {C₁, ..., Cₖ}

// 初始化：每个样本自成一簇
for j = 1, ..., m do
  Cⱼ = {xⱼ}  // m 个初始簇
end for
// 计算所有簇对之间的距离矩阵 M
M[i][j] = dist(Cᵢ, Cⱼ) (初始 = dist(xᵢ, xⱼ))

q = m  // 当前簇数
while q > k do
  找距离最小的两个簇 Cᵢ*, Cⱼ* = argmin M[i][j]
  合并 Cᵢ* ∪ Cⱼ* → 新簇
  从 M 中删除 Cᵢ*, Cⱼ* 的行列，加入新簇的行列
  重新计算新簇与其他簇的距离
  q = q - 1
return 当前簇划分

🔑 树状图（Dendrogram）的使用

树状图是层次聚类的最大优势——它记录了所有合并过程。
只需在树状图的某个高度处横切，就可以得到对应数量的簇：
• 切得越低 → 簇数 $k$ 越大（更细的分组）
• 切得越高 → 簇数 $k$ 越小（更粗的分组）
• 不需要事先指定 $k$，事后按需选择！

✅ AGNES 优点

• 能生成完整的层次结构，可视化直观
• 不需要预先指定 $k$（事后截断）
• 能揭示数据的多尺度结构

❌ AGNES 缺点

• 时间复杂度高：$O(m^2 \log m)$（对大规模数据慢）
• 合并操作不可逆，错误合并无法纠正
• 对噪声和离群点敏感（尤其是单链接）

09. 算法对比总结

一表看懂所有聚类算法的特点与适用场景

算法	类型	是否需指定 k	输出类型	簇形状	噪声处理	适用场景
k-means	原型聚类	✅ 需要	硬聚类	球形（凸形）	❌ 敏感	数据规模大，簇形状近似球形
LVQ	原型聚类（半监督）	✅ 需要	硬聚类	Voronoi 区域	❌ 敏感	有部分标记信息，需要学习原型
高斯混合（GMM）	概率聚类	✅ 需要	软聚类（概率）	椭圆形	⚠️ 一般	数据符合混合高斯分布，需软分配
DBSCAN	密度聚类	❌ 不需要	硬聚类 + 噪声	任意形状	✅ 很好	任意形状的簇，数据中有噪声
AGNES	层次聚类	❌ 不需要（事后截断）	层次结构	取决于链接方式	⚠️ 一般	需要可视化层次关系，数据量较小

📊 思维导图：第九章知识体系

🎓 学习路线与重点提示

🔑 考试/面试高频考点

• 📌 k-means 算法流程：能手写伪代码，说清楚优缺点，理解”局部最优”问题
• 📌 DBSCAN 的核心概念：ε-邻域、核心对象、密度直达/可达/相连的定义与区别
• 📌 EM 算法在 GMM 中的应用：理解 E步（计算后验）和 M步（更新参数）
• 📌 外部指标 vs 内部指标：JC/FMI/RI 的公式含义；DBI/DI 的大小方向
• 📌 AGNES 的三种链接方式：单链接/全链接/均链接的区别和适用场景
• 📌 各算法的适用场景对比：在什么情况下选哪种算法

💡 最后的类比总结

🍽️ k-means：食堂打菜——每道菜只能选一个窗口（硬分配），
打菜员（质心）站在最中间的位置。

        🏫 **LVQ**：选班级代表——代表要真正"代表"这个班，
        和其他班的代表要不一样。


        🎨 **GMM**：颜料调色——数据是多种颜色的混合，
        每种颜色有一定比例（混合系数）和特征（均值/方差）。


        🌆 **DBSCAN**：卫星夜视图找城市——密集的灯光是城市（簇），
        孤立的灯是村庄（噪声）。


        🌳 **AGNES**：生物分类树——从物种不断往上合并，
        最终形成门纲目科属种的层级结构。