第8章文本聚类：K-Means、层次聚类与模糊 C 均值

约 25 分钟 · 需要向量距离与加权平均

读完你能： 手算一轮 K-Means 的指派、中心更新与目标函数变化；区分单连接、全连接、平均连接、中心连接与 Ward 方法；计算模糊 C 均值（FCM）的隶属度与加权中心；结合轮廓系数与文本特征检查聚类结果。

1. 没有类别标签时，聚类在找什么

分类任务依赖事先标注好的类别标签，而聚类是在没有标签的情况下，按特征空间中的距离或相似度把文档分成若干簇（cluster）。需要清醒认识的是：算法把语料分成了三个簇，并不意味着自动发现了三个业务主题——如果特征里混入了篇幅长短、网页模板或语种差异，聚类完全可能按这些表面因素分组。

因此，动手聚类前要先定下三件事：

文本表示：用词频、TF-IDF、SVD/NMF 低维向量，还是句向量？
距离或相似度：用欧氏距离还是余弦相似度？
簇的形态：要求每个文档只属于唯一一个簇（硬聚类），还是允许同时对多个簇有不同归属度（软聚类/模糊聚类）？

当所有文档向量都先做过 L2 归一化（即 $\lVert x\rVert_2=\lVert y\rVert_2=1$ ）时，平方欧氏距离与余弦相似度满足确定关系：

\lVert x-y\rVert_2^2=\lVert x\rVert_2^2+\lVert y\rVert_2^2-2x^Ty=2(1-\cos(x,y)).

也就是说，在单位球面上“欧氏距离最小”等价于“余弦相似度最大”。不过需要注意，标准 K-Means 在更新簇中心时取的是算术平均，均值向量本身不再保持单位长度；若要求中心也始终落在单位球面上，需要额外对中心做归一化（即球面 K-Means）。

2. K-Means 的目标函数与两步交替

给定样本 $x_1,\dots,x_n$ 和预设簇数 $K$ ，K-Means 寻找各样本的簇指派 $z_i\in\{1,\dots,K\}$ 及簇中心 $\mu_1,\dots,\mu_K$ ，最小化簇内平方误差和（WCSS）：

J=\sum_{i=1}^{n}\lVert x_i-\mu_{z_i}\rVert_2^2.

标准算法从随机初始化的 $K$ 个中心出发，交替执行两步：

指派（Assignment）：固定簇中心 $\mu_1,\dots,\mu_K$ ，将每个样本 $x_i$ 分配给距离它最近的中心，即 $z_i=\arg\min_{k\in\{1,\dots,K\}}\lVert x_i-\mu_k\rVert_2^2$ 。
更新（Refitting）：固定指派结果，将每个簇的中心移动到该簇全体样本的算术平均，即 $\mu_k=\dfrac{1}{\lvert C_k\rvert}\sum_{i\in C_k}x_i$ 。
重复以上两步，直到所有样本的指派不再变化，或目标函数下降小于阈值。

指派步对每个样本挑最近中心，不会让 $J$ 变大；更新步用均值最小化二次平方和，也不会让 $J$ 变大。因此 $J$ 单调不增，算法一定在有限步内收敛。但由于目标函数非凸，收敛结果依赖初始中心位置，通常需要用不同随机种子（或 K-Means++ 初始化）多跑几次。若迭代中某个簇变成空集，实现中需约定将该中心重新指向最远样本或随机样本，避免除以 0。

3. 手算一轮 K-Means

设一维数据点为 $0, 2, 8, 10$ ，取 $K=2$ ，初始中心设为 $\mu_A=0$ 、 $\mu_B=8$ 。

第一步：指派。 计算每个点到两个初始中心的距离：

数据点 $x_i$	到 $\mu_A=0$ 的距离	到 $\mu_B=8$ 的距离	所属簇
0	0	8	A
2	2	6	A
8	8	0	B
10	10	2	B

此时簇 $A=\{0,2\}$ ，簇 $B=\{8,10\}$ ，初始平方误差为 $J_0=0^2+2^2+0^2+2^2=8$ 。

第二步：更新中心。

\mu_A^{\text{new}}=\frac{0+2}{2}=1,\qquad \mu_B^{\text{new}}=\frac{8+10}{2}=9.

用新中心重新计算距离： $0,2$ 到 $\mu_A=1$ 的距离都是 $1$ （到 $\mu_B=9$ 分别为 $9,7$ ）， $8,10$ 到 $\mu_B=9$ 的距离都是 $1$ ，指派保持不变，算法收敛。更新后的目标函数降为

J_1=(0-1)^2+(2-1)^2+(8-9)^2+(10-9)^2=1+1+1+1=4.

points = [0.0, 2.0, 8.0, 10.0]
centers = [0.0, 8.0]
labels = [min(range(2), key=lambda j: abs(x - centers[j])) for x in points]
updated = [sum(x for x, z in zip(points, labels) if z == j) /
           sum(z == j for z in labels) for j in range(2)]
assert updated == [1.0, 9.0]

在高维稀疏文本上运行 K-Means 后，可以查看每个簇中心向量里权重最高的十几个词以及离中心最近的代表文档，用来判断该簇是否有清晰的语义主题。

4. 层次聚类：自底向上合并与自顶向下拆分

层次聚类不需要预先固定唯一的簇数 $K$ ，而是构造一棵树状图（dendrogram）记录全部分合过程；需要几个簇，就在对应高度横切一刀。常见路线有两种：

凝聚式（Agglomerative，自底向上）：初始时每个样本自成一簇，每一步把当前最相近的两个簇合并，直到所有样本合为一个大簇；
分裂式（Divisive，自顶向下）：初始时全部样本在一个簇内，逐步把簇一分为二，直到拆到单个样本。

凝聚式聚类每一步“合并哪两个簇”，取决于如何定义两个簇 $A$ 与 $B$ 之间的距离（连接方式 linkage）：

连接方式	簇间距离或合并代价	结构特点
单连接（single / min linkage）	$\min_{x\in A,\,y\in B}d(x,y)$	只看最近点对，容易拉出细长“链状”簇
全连接（complete / max linkage）	$\max_{x\in A,\,y\in B}d(x,y)$	受最远点对制约，倾向形成直径紧凑的簇
平均连接（average linkage）	$\dfrac{1}{\lvert A\rvert\lvert B\rvert}\sum_{x\in A}\sum_{y\in B}d(x,y)$	折中单连接与全连接，兼顾所有点对
中心连接（centroid linkage）	$\lVert\mu_A-\mu_B\rVert_2$	直接量两簇均值中心的距离
Ward 方法	合并后簇内平方误差和的增量 $\Delta(A,B)$	倾向产生大小较均衡、方差紧凑的球状簇

其中 Ward 方法的平方误差增量可化简为两簇中心的加权平方距离：

\Delta(A,B)=\frac{n_An_B}{n_A+n_B}\lVert\mu_A-\mu_B\rVert_2^2.

可以看出，当两簇中心距离相同时，样本数更大的簇合并带来的方差增量也更大；此外，Ward 公式建立在欧氏平方误差之上，使用时特征空间应与欧氏几何相容。

5. 同一批数据，不同连接方式如何走出不同合并树

设一维四个点为 $A=0,\ B=2,\ C=5,\ D=9$ 。初始两两距离中， $d(A,B)=2$ 最小（ $d(B,C)=3$ ， $d(C,D)=4$ ），因此所有标准距离连接第一步都会先把 $A,B$ 合并为簇 $AB=\{0,2\}$ ，其均值中心为 $\mu_{AB}=1$ 。

第二步需要在三个簇 $\{AB, C, D\}$ 中挑一对合并，其中 $C$ 与 $D$ 的距离固定为 $d(C,D)=4$ 。对比不同连接方式下 $AB$ 与 $C$ 的距离或代价：

单连接（single）： $d_{\text{single}}(AB,C)=\min(\lvert 0-5\rvert,\lvert 2-5\rvert)=\min(5,3)=3<4$ ，因此第二步合并 $AB$ 与 $C$ ，得到 $\{A,B,C\}$ 。
全连接（complete）： $d_{\text{complete}}(AB,C)=\max(5,3)=5>4$ ，因此第二步转而合并 $C$ 与 $D$ ，得到 $\{A,B\}$ 和 $\{C,D\}$ 。
平均连接（average）： $d_{\text{avg}}(AB,C)=(5+3)/2=4=d(C,D)$ ，此时合并 $AB$ 与 $C$ 、或者合并 $C$ 与 $D$ 距离相同，需要按预设平局规则决定。
中心连接（centroid）： $d_{\text{centroid}}(AB,C)=\lvert 1-5\rvert=4=d(C,D)$ ，同样出现并列。
Ward 方法：合并 $AB$ 与 $C$ 的方差增量为 $\Delta(AB,C)=\dfrac{2\times 1}{2+1}(5-1)^2=\dfrac{32}{3}\approx10.67$ ；而合并单点 $C$ 与 $D$ 的增量为 $\Delta(C,D)=\dfrac{1\times 1}{1+1}(9-5)^2=8<10.67$ ，因此第二步先合并 $C$ 与 $D$ 。

这个例子直观展示了：同样四个点，仅把单连接换成全连接或 Ward，两簇切分就会从 $\{A,B,C\}+\{D\}$ 变成 $\{A,B\}+\{C,D\}$ 。

6. 模糊 C 均值（FCM）：允许一篇文档横跨多个簇

一篇新闻既谈科技又谈金融时，硬塞进唯一一个簇会丢失跨主题信息。模糊 C 均值（Fuzzy C-Means, FCM）为每个样本 $i$ 对每个簇 $k$ 赋予非负隶属度 $u_{ik}$ ，满足 $\sum_{k=1}^C u_{ik}=1$ ，并最小化带模糊指数 $m>1$ 的加权目标：

J_m=\sum_{i=1}^n\sum_{k=1}^C u_{ik}^{m}\lVert x_i-\mu_k\rVert_2^2,\qquad u_{ik}\ge0,\quad \sum_{k=1}^C u_{ik}=1.

当样本到各簇中心的距离均不为 0 时，用拉格朗日乘子法求得交替更新公式：

u_{ik}=\frac{1}{\sum_{j=1}^C\left(\dfrac{\lVert x_i-\mu_k\rVert_2}{\lVert x_i-\mu_j\rVert_2}\right)^{2/(m-1)}},\qquad \mu_k=\frac{\sum_{i=1}^n u_{ik}^{m}x_i}{\sum_{i=1}^n u_{ik}^{m}}.

每个簇中心 $\mu_k$ 就是全体样本以 $u_{ik}^m$ 为权重的加权平均。若某个样本恰好与某个中心重合（距离为 0），则将该样本对该重合中心的隶属度直接设为 1，其余簇设为 0。

例：设两个簇中心为 $\mu_1=0,\ \mu_2=10$ ，取常用模糊指数 $m=2$ （此时指数 $2/(m-1)=2$ ）。对数据点 $x_i=2$ ，它到两中心的距离分别为 $d_1=2$ 和 $d_2=8$ ，于是：

u_{i1}=\frac{1}{(2/2)^2+(2/8)^2}=\frac{1}{1+1/16}=\frac{16}{17}\approx0.9412,\qquad u_{i2}=\frac{1}{(8/2)^2+(8/8)^2}=\frac{1}{16+1}=\frac{1}{17}\approx0.0588.

两项之和恰好为 1，且因为 $x_i=2$ 离 $\mu_1=0$ 近得多，隶属度主要集中在第一簇。注意 $u_{ik}$ 是距离比决定的几何隶属度，虽然满足非负且和为 1，但并不是概率生成模型算出的后验概率。

7. 怎样评估聚类结果

没有外部人工标签时，常用轮廓系数（Silhouette Coefficient）衡量簇的内部紧凑度与簇间分离度。对样本 $i$ ：

令 $a(i)$ 为样本 $i$ 到同一簇内其他样本的平均距离（簇内越紧凑， $a(i)$ 越小）；
令 $b(i)$ 为样本 $i$ 到其他某一个簇全体样本的平均距离对所有其他簇取最小值（即离最近邻簇的平均距离， $b(i)$ 越大说明分离越清楚）；
定义样本 $i$ 的轮廓系数为：

s(i)=\frac{b(i)-a(i)}{\max(a(i),b(i))}\in[-1,1].

（若某簇只有 1 个样本，通常约定 $s(i)=0$ 。）例如某样本 $a(i)=2,\ b(i)=5$ ，则 $s(i)=(5-2)/5=0.6$ 。 $s(i)$ 越接近 $1$ ，说明簇内紧、簇间远；接近 $0$ 说明处在两簇边界；若为负数（ $a(i)>b(i)$ ），说明它离别的簇反而比离自己簇更近，很可能分错了簇。