Chapter 12 聚类

一、没有标签的分组

疾旋鼬收集了 1000 个西瓜的数据，但没有好坏标签。它想：能不能让机器自动把"比较像"的西瓜分成几堆？

聚类 (Clustering)：无监督学习中研究最多、应用最广的任务。目标：将数据划分为若干不相交的"簇" (cluster)，使得簇内相似度高，簇间相似度低。

聚类既可以作为独立过程（找寻数据内在分布结构），也可作为分类等其他学习任务的前驱过程。

聚类的"好坏"没有绝对标准

老师让小朋友把苹果和梨分成两堆。小明按大小分，小芳按颜色分，小武按籽数分。老师很高兴：新的聚类算法诞生了。

聚类也许是机器学习中"新算法"出现最多、最快的领域——总能找到一个新的"标准"，使以往算法对它无能为力。

二、距离度量

闵可夫斯基距离

\[\text{dist}_p(x, z) = \left(\sum_{k=1}^d |x_k - z_k|^p\right)^{1/p}\]

\(p = 2\)：欧氏距离——最常用
\(p = 1\)：曼哈顿距离——城市街区距离
\(p \to \infty\)：切比雪夫距离——各维度差值的最大值

距离度量需满足的性质： 1. 非负性：\(\text{dist}(x, z) \geq 0\) 2. 同一性：\(\text{dist}(x, z) = 0\) 当且仅当 \(x = z\) 3. 对称性：\(\text{dist}(x, z) = \text{dist}(z, x)\) 4. 直递性（三角不等式）：\(\text{dist}(x, z) \leq \text{dist}(x, y) + \text{dist}(y, z)\)

非度量距离

有些距离不满足直递性，如"人→马→马车→车"的距离不等于"人→车"的距离。

VDM 距离 (Value Difference Metric)

对无序离散属性，可用 VDM：

\[\text{VDM}_p(a, b) = \sum_{k=1}^K \left|\frac{m_{k,a}}{m_a} - \frac{m_{k,b}}{m_b}\right|^p\]

其中 \(m_{k,a}\) 为第 \(k\) 个簇中属性取值为 \(a\) 的样本数。

混合属性距离

对同时包含数值和离散属性的数据，可使用 MinkovDM：在数值属性上用闵可夫斯基距离，在离散属性上用 VDM，再加权组合。

三、性能度量

外部指标

将聚类结果与"参考模型"比较： - Jaccard 系数：\(J = \frac{|A \cap B|}{|A \cup B|}\)，\(A\) 和 \(B\) 分别是聚类结果和参考模型中"同一簇"的样本对集合 - FM 指数 (Fowlkes-Mallows)：\(\text{FM} = \sqrt{\frac{TP}{TP+FP} \cdot \frac{TP}{TP+FN}}\) - Rand 指数：\(\text{RI} = \frac{TP + TN}{TP + TN + FP + FN}\)

内部指标

直接考察聚类结果，不用参考模型： - DB 指数 (Davies-Bouldin)：\(\text{DB} = \frac{1}{k}\sum_{i=1}^k \max_{j \neq i}\frac{\text{avg}(C_i) + \text{avg}(C_j)}{\text{dist}(\mu_i, \mu_j)}\)，越小越好 - Dunn 指数：\(\text{DI} = \frac{\min_{i \neq j}\text{dist}(C_i, C_j)}{\max_i \text{diam}(C_i)}\)，越大越好

基本想法：簇内相似度（intra-cluster similarity）高，且簇间相似度（inter-cluster similarity）低。

四、原型聚类

\(k\)-means

每个簇以该簇中所有样本的均值表示。

算法： 1. 随机选取 \(k\) 个样本点作为簇中心 \(\mu_1, \ldots, \mu_k\) 2. 将每个样本分配到最近的簇：\(C_j = \{x^{(i)} : j = \arg\min_l \|x^{(i)} - \mu_l\|^2\}\) 3. 更新各簇中心：\(\mu_j = \frac{1}{|C_j|}\sum_{x \in C_j} x\) 4. 若所有簇中心未改变，停止；否则执行 Step 2

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

\[E = \sum_{j=1}^k \sum_{x \in C_j} \|x - \mu_j\|^2\]

性质： - 收敛性：每轮 \(E\) 单调递减（可以证明），故一定收敛 - 但可能收敛到局部最优，对初始值敏感 - 时间复杂度：\(O(m \cdot k \cdot d \cdot T)\)，\(T\) 为迭代次数

变种： - \(k\)-medoids：用距簇中心最近的样本点代替均值，对异常值更鲁棒

高斯混合聚类 (GMM)

用概率模型表达聚类原型。假设数据由 \(k\) 个高斯分布的混合生成：

\[P(x) = \sum_{j=1}^k \alpha_j \cdot \mathcal{N}(x \mid \mu_j, \Sigma_j)\]

其中 \(\alpha_j\) 为第 \(j\) 个混合成分的先验概率（\(\sum \alpha_j = 1\)）。

生成过程： 1. 根据 \(\alpha_1, \ldots, \alpha_k\) 选择一个高斯成分 2. 从该成分的概率密度函数中采样

用 EM 算法求解。引入隐变量 \(\gamma_{ij} \in \{0, 1\}\) 表示样本 \(x^{(i)}\) 是否由第 \(j\) 个成分生成。

E 步：计算后验概率（"责任"）：

\[\gamma_{ij} = \frac{\alpha_j \cdot \mathcal{N}(x^{(i)} \mid \mu_j, \Sigma_j)}{\sum_{l=1}^k \alpha_l \cdot \mathcal{N}(x^{(i)} \mid \mu_l, \Sigma_l)}\]

M 步：更新参数（用拉格朗日乘子法处理约束 \(\sum \alpha_j = 1\)）：

\[\mu_j = \frac{\sum_i \gamma_{ij} x^{(i)}}{\sum_i \gamma_{ij}}, \quad \Sigma_j = \frac{\sum_i \gamma_{ij}(x^{(i)} - \mu_j)(x^{(i)} - \mu_j)^T}{\sum_i \gamma_{ij}}, \quad \alpha_j = \frac{\sum_i \gamma_{ij}}{m}\]

GMM 是软聚类——每个样本以一定概率属于每个簇。

五、密度聚类

DBSCAN

核心思想：簇是数据空间中密度高的区域，被密度低的区域分隔。

关键概念： - \(\epsilon\)-邻域：\(N_\epsilon(x) = \{y \mid \text{dist}(x, y) \leq \epsilon\}\) - 核心对象：\(|N_\epsilon(x)| \geq \text{MinPts}\) - 密度直达：\(y \in N_\epsilon(x)\) 且 \(x\) 是核心对象 - 密度可达：存在一条密度直达链 \(x_1 \to x_2 \to \cdots \to x_n\) - 密度相连：存在核心对象 \(o\)，使得 \(x\) 和 \(y\) 都从 \(o\) 密度可达

算法： 1. 找到所有核心对象 2. 从任意未访问的核心对象出发，找出所有密度可达的样本，形成一个簇 3. 重复直到所有核心对象都被访问

优点： - 能发现任意形状的簇（不限于球形） - 能识别噪声点（不属于任何簇的样本） - 不需要预先指定簇数

缺点： - 对参数 \(\epsilon\) 和 MinPts 敏感 - 密度不均匀时效果不好

六、层次聚类

AGNES (AGglomerative NESting)

自底向上的层次聚类：

将每个样本初始化为一个簇
合并距离最近的两个簇
重复直到所有样本在一个簇中

簇间距离的定义： - 最小距离 (single-linkage)：\(d_{\min}(C_i, C_j) = \min_{x \in C_i, y \in C_j} \text{dist}(x, y)\)——倾向于产生"链状"簇 - 最大距离 (complete-linkage)：\(d_{\max}(C_i, C_j) = \max_{x \in C_i, y \in C_j} \text{dist}(x, y)\)——倾向于产生"球状"簇 - 平均距离 (average-linkage)：\(d_{\text{avg}}(C_i, C_j) = \frac{1}{|C_i||C_j|}\sum_{x \in C_i, y \in C_j} \text{dist}(x, y)\)

层次聚类的结果是一棵树状图 (dendrogram)，可以在不同层次"切割"得到不同粒度的聚类结果。

聚类方法对比

方法	类型	需指定 \(k\)？	任意形状？	对噪声鲁棒？
\(k\)-means	原型	是	否（球形）	否
GMM	原型（概率）	是	否（椭球）	较好
DBSCAN	密度	否	是	是
AGNES	层次	否	取决于距离定义	较好

2026.06