第9章 聚类

🎯 学习目标

• 理解聚类的基本概念和无监督学习的特点
• 掌握K-means算法的原理和实现
• 了解层次聚类和密度聚类的思想
• 理解聚类性能评估指标

9.1 聚类任务

🎯 什么是聚类

聚类（Clustering） 是一种无监督学习任务，目标是将数据集中的样本划分为若干个组（簇），使得：

• 簇内相似度高：同一簇内的样本尽可能相似
• 簇间相似度低：不同簇之间的样本尽可能不同

聚类与分类的区别：分类有已知的类别标签（监督学习），而聚类没有预先定义的类别（无监督学习），需要自动发现数据中的内在结构。

聚类的性能度量

聚类性能度量分为两类：

📊 外部指标（External Index）

将聚类结果与参考模型（真实标签）比较：

• Jaccard系数（JC）：$JC=\frac{a}{a+b+c}$
• FM指数（FMI）：$FMI=\sqrt{\frac{a}{a+b}\cdot \frac{a}{a+c}}$
• Rand指数（RI）：$RI=\frac{2(a+d)}{m(m-1)}$

其中 a: 同簇同类, b: 同簇不同类, c: 不同簇同类, d: 不同簇不同类

📊 内部指标（Internal Index）

不依赖外部参考，直接考察聚类结果：

• DB指数（Davies-Bouldin Index）：簇内距离小、簇间距离大
• Dunn指数（DI）：簇间最小距离 / 簇内最大距离
• 轮廓系数（Silhouette Coefficient）：$[-1,1]$，越接近1越好

9.2 原型聚类

🎯 k均值算法（k-means）

k均值算法 是最常用的聚类算法，基于原型的划分方法：

算法步骤：

1. 随机选择 $k$ 个样本作为初始簇中心 ${\mu }_1,{\mu }_2,\dots ,{\mu }_k$
2. 计算每个样本到各簇中心的距离，划分到最近的簇
3. 根据划分结果，重新计算每个簇的中心（簇内样本均值）
4. 重复步骤2-3，直到簇中心不再变化或达到最大迭代次数

目标函数（最小化平方误差）：

$$E=\sum _{i=1}^k\sum _{x\in C_i}\parallel x-{\mu }_i{\parallel }^2$$

• 优点：简单高效、易于实现、适合大规模数据
• 缺点：需要预先指定k、对初始中心敏感、只能发现凸形簇、对噪声敏感

学习向量量化（LVQ）

LVQ（Learning Vector Quantization） 是一种有监督的原型聚类方法，结合了聚类和分类：

LVQ算法流程：

1. 初始化一组原型向量 $\{p_1,p_2,\dots ,p_q\}$
2. 随机选取样本 $x_j$，找到最近的原型向量 $p_{i^{\ast }}$
3. 如果 $x_j$ 和 $p_{i^{\ast }}$ 类别相同，将 $p_{i^{\ast }}$ 向 $x_j$ 靠近：$p_{i^{\ast }}\leftarrow p_{i^{\ast }}+\eta (x_j-p_{i^{\ast }})$
4. 如果类别不同，将 $p_{i^{\ast }}$ 远离 $x_j$：$p_{i^{\ast }}\leftarrow p_{i^{\ast }}-\eta (x_j-p_{i^{\ast }})$
5. 重复2-4直到满足停止条件

其中 $\eta \in (0,1)$ 是学习率。LVQ的关键：利用样本的类别标签信息来调整原型向量，使得同类原型更接近、异类原型更远离。

高斯混合聚类（GMM）

高斯混合模型（Gaussian Mixture Model, GMM） 采用概率模型进行聚类：

混合模型定义：

$$p(x)=\sum _{i=1}^k{\alpha }_i\cdot \mathcal{N}(x\mid {\mu }_i,{\mathrm{\Sigma }}_i)$$

其中 ${\alpha }_i$ 是混合系数（$\sum {\alpha }_i=1$），$\mathcal{N}$ 是高斯分布。

💡 EM算法求解GMM

迭代执行两步：

• E步：根据当前参数计算每个样本属于各簇的后验概率 ${\gamma }_{ji}$
• M步：根据后验概率更新模型参数（${\mu }_i,{\mathrm{\Sigma }}_i,{\alpha }_i$）

GMM相比k-means的优势：能够捕捉簇的形状和大小（协方差矩阵），输出样本属于各簇的概率（软划分）。

k-means聚类交互演示

通过交互式可视化理解k-means算法的迭代过程，观察质心如何移动以及簇如何形成。

簇数量 (K): 3

26

迭代次数0

簇内平方和-

数据点（按簇着色）

质心（簇中心）

K-means算法步骤：

1. 初始化：随机选择K个点作为初始质心（使用K-means++改进初始化）
2. 分配：将每个点分配到最近的质心，形成K个簇
3. 更新：计算每个簇的均值，更新质心位置
4. 重复：重复步骤2-3直到质心不再移动（收敛）

9.3 密度聚类

🎯 DBSCAN算法

DBSCAN（Density-Based Spatial Clustering of Applications with Noise） 基于密度的聚类方法，能发现任意形状的簇并识别噪声点。

核心概念：

• ε-邻域：$N_{\epsilon }(x)=\{x^{\prime }\in D\mid dist(x,x^{\prime })\le \epsilon \}$
• 核心对象：若 $|N_{\epsilon }(x)|\ge MinPts$，则 $x$ 是核心对象
• 密度直达：若 $x^{\prime }$ 在 $x$ 的 ε-邻域内且 $x$ 是核心对象
• 密度可达：存在样本序列使得密度直达传递
• 密度相连：存在核心对象 $o$ 使得 $x$、$x^{\prime }$ 均密度可达于 $o$

DBSCAN算法步骤：

1. 标记所有核心对象
2. 随机选取一个未访问的核心对象，生成新簇
3. 找到所有与该核心对象密度相连的样本，加入当前簇
4. 重复步骤2-3，直到所有核心对象都被访问
5. 将未被划入任何簇的样本标记为噪声点

• 优点：能发现任意形状的簇、能识别噪声点、不需要预先指定簇数量
• 缺点：参数 ε 和 MinPts 难以确定、对不同密度的簇效果不佳、高维数据性能下降

9.4 层次聚类

层次聚类（Hierarchical Clustering） 在不同层次上对数据集进行划分，形成树形的聚类结构（树状图/dendrogram）。

📊 凝聚层次聚类（AGNES）

自底向上的策略：

1. 初始：每个样本作为一个簇
2. 找到距离最近的两个簇
3. 合并这两个簇
4. 重复2-3直到达到预设簇数

📊 分裂层次聚类（DIANA）

自顶向下的策略：

1. 初始：所有样本在一个簇
2. 选择某个簇进行分裂
3. 将该簇分为两个子簇
4. 重复2-3直到达到预设簇数

簇间距离计算

• 最小距离（单链接）：$d_{min}(C_i,C_j)=min\{dist(x,x^{\prime })\mid x\in C_i,x^{\prime }\in C_j\}$
• 最大距离（全链接）：$d_{max}(C_i,C_j)=max\{dist(x,x^{\prime })\mid x\in C_i,x^{\prime }\in C_j\}$
• 平均距离：$d_{avg}(C_i,C_j)=\frac{1}{|C_i||C_j|}\sum _{x\in C_i}\sum _{x^{\prime }\in C_j}dist(x,x^{\prime })$

优势：不需要预先指定簇数量，可以通过树状图选择合适的层次。劣势：计算复杂度高（$O(n^2)$ 或 $O(n^3)$），不适合大规模数据。

9.5 谱聚类

谱聚类（Spectral Clustering） 从图论角度进行聚类，将聚类问题转化为图的划分问题，利用图的谱（特征值和特征向量）进行聚类。

🎯 核心步骤

1. 构建相似度图：计算样本间相似度，构建相似度矩阵 $W$
2. 计算拉普拉斯矩阵：$L=D-W$（$D$ 是度矩阵）
3. 特征分解：计算 $L$ 的前 $k$ 个最小特征值对应的特征向量
4. k-means聚类：对特征向量矩阵的行进行k-means聚类

常用的拉普拉斯矩阵

• 未归一化：$L=D-W$
• 对称归一化：$L_{sym}=D^{-1/2}L{D}^{-1/2}=I-D^{-1/2}W{D}^{-1/2}$
• 随机游走归一化：$L_{rw}=D^{-1}L=I-D^{-1}W$

💡 为什么有效？

谱聚类在降维后的特征空间中进行聚类，能够发现非凸形状的簇。拉普拉斯矩阵的特征向量保留了图的连通性信息，使得同簇样本在特征空间中更接近。

• 优点：能处理任意形状的簇、只需要相似度矩阵、对初始值不敏感
• 缺点：计算复杂度高、需要预先指定簇数、相似度矩阵构建方式影响结果

📝 本章小结

总结

• ✅ 聚类是无监督学习的核心任务，通过簇内相似度高、簇间相似度低来划分数据
• ✅ K-means是最常用的聚类算法，通过迭代更新质心实现划分
• ✅ DBSCAN基于密度聚类，能发现任意形状的簇并识别噪声
• ✅ 层次聚类形成树形结构，可以自底向上或自顶向下
• ✅ 谱聚类从图论角度出发，利用拉普拉斯矩阵的特征向量进行聚类