知识框架
聚类是无监督学习任务，目标是在无类别标记时按相似性把样本划分为簇。本章重点包括聚类性能度量、距离计算、k-means、LVQ、高斯混合聚类、DBSCAN 和层次聚类。
聚类任务与度量
给定无标记样本集
\[
D=\{\mathbf{x}_1,\mathbf{x}_2,\ldots,\mathbf{x}_m\},
\]
聚类算法将其划分为 $k$ 个不相交簇
\[
\mathcal{C}=\{C_1,C_2,\ldots,C_k\}.
\]
分类使用已知标记训练模型；聚类没有标记，依赖距离、密度或分布假设发现结构。
外部指标
若有参考划分，可统计样本对关系：同簇同类 $a$、同簇异类 $b$、异簇同类 $c$、异簇异类 $d$。
\[
JC=\frac{a}{a+b+c},
\]
\[
FMI=\sqrt{\frac{a}{a+b}\cdot\frac{a}{a+c}},
\]
\[
RI=\frac{2(a+d)}{m(m-1)}.
\]
内部指标
内部指标只使用样本和聚类结果。常见思想：簇内距离小、簇间距离大。DB 指数越小越好，Dunn 指数越大越好。
距离计算
闵可夫斯基距离：
\[
d_p(\mathbf{x},\mathbf{z})=
\left(\sum_{j=1}^{d}|x_j-z_j|^p\right)^{1/p}.
\]
特殊情形：
\[
p=1 \text{ 为曼哈顿距离},\qquad p=2 \text{ 为欧氏距离}.
\]
马氏距离：
\[
d_{\mathbf{\Sigma}^{-1}}(\mathbf{x},\mathbf{z})=
\sqrt{(\mathbf{x}-\mathbf{z})^\top\mathbf{\Sigma}^{-1}(\mathbf{x}-\mathbf{z})}.
\]
无序离散属性可用 VDM，属性重要性不同可用加权距离。
k-means
k-means 最小化簇内平方误差：
\[
E=\sum_{\ell=1}^{k}\sum_{\mathbf{x}\in C_\ell}
\|\mathbf{x}-\mathbf{\mu}_\ell\|_2^2.
\]
算法步骤：
- 初始化 $k$ 个中心。
- 分配：把每个样本分到最近中心。
- 更新：令每个中心为对应簇样本均值。
- 重复直到中心或分配不再变化。
局限：需预设 $k$，对初始中心和异常点敏感，偏好球形、规模相近、密度相近的簇。
LVQ 与高斯混合聚类
LVQ 使用带类别标记的原型向量，按样本与原型的关系移动原型。
高斯混合模型假设数据由多个高斯成分混合生成：
\[
p(\mathbf{x})=\sum_{i=1}^{k}\alpha_i
\mathcal{N}(\mathbf{x}\mid \mathbf{\mu}_i,\mathbf{\Sigma}_i),
\qquad
\sum_i \alpha_i=1.
\]
责任度：
\[
\gamma_{ji}=
\frac{\alpha_i\mathcal{N}(\mathbf{x}_j\mid \mathbf{\mu}_i,\mathbf{\Sigma}_i)}
{\sum_{\ell=1}^{k}\alpha_\ell\mathcal{N}(\mathbf{x}_j\mid \mathbf{\mu}_\ell,\mathbf{\Sigma}_\ell)}.
\]
EM 更新：
\[
\mathbf{\mu}_i=\frac{\sum_j\gamma_{ji}\mathbf{x}_j}{\sum_j\gamma_{ji}},
\]
\[
\mathbf{\Sigma}_i=
\frac{\sum_j\gamma_{ji}(\mathbf{x}_j-\mathbf{\mu}_i)(\mathbf{x}_j-\mathbf{\mu}_i)^\top}
{\sum_j\gamma_{ji}},
\]
\[
\alpha_i=\frac{1}{m}\sum_j\gamma_{ji}.
\]
DBSCAN
核心概念：
- $\epsilon$ 邻域：距离样本不超过 $\epsilon$ 的样本集合。
- 核心对象：$\epsilon$ 邻域内样本数不少于 MinPts。
- 密度直达、密度可达、密度相连：描述由核心对象扩展出的连通关系。
DBSCAN 从核心对象出发扩展簇，并把不能归入任何簇的点视为噪声。$\epsilon$ 太小会产生过多噪声，太大会合并簇；MinPts 太大也会使簇更难形成。
层次聚类
AGNES 是自底向上的凝聚层次聚类：
- 初始每个样本为一簇。
- 计算簇间距离。
- 合并距离最近的两簇。
- 更新距离矩阵，直到满足停止条件。
簇间距离可用最短距离、最长距离、平均距离。不同距离定义会影响合并顺序和聚类形状。
常见问法
- 给一维或二维数据和初始中心，手算 k-means 两轮迭代。
- 比较不同初始化方案，说明 k-means 对初始化敏感的原因。
- 给 GMM 参数和样本，计算各成分责任度和责任度比值。
- 解释高斯方差变大时责任度变化与重叠问题。
- 给 $\epsilon$ 和 MinPts，判断 DBSCAN 中核心点、边界点和噪声点。
- 根据距离矩阵执行层次聚类前几步。