分布式处理与计算：聚类分析

聚类，就是在一堆没有标签的数据中，把长得像的（特征相似的）数据自动挑出来，揉成一团，分成几个“簇”。在分组时遵循：

簇内越相似越好（放在同一堆里的东西，长得必须尽可能像）
簇间越不同越好（这堆和那堆之间，差别必须尽可能大）

衡量“像不像”通常用距离。在坐标系里，两个点靠得越近，就认为它们越相似，就越应该被分到同一个“簇”里。

一、距离的定义

聚类的基础是"相似 = 距离近"。设两个观测 $x$ 、 $y$ ,它们在第 $k$ 个变量上的差别记为 $x_k - y_k$ ,距离 $d(x,y)$ 是把这些差别综合起来的一个度量。

一个合格的距离要满足三个条件:

对称性: $d(x, y) = d(y, x)$ ;
非负性: $d(x, y) \ge 0$ ,当且仅当 $x = y$ 时取等号;
三角不等式: $d(x, z) \le d(x, y) + d(y, z)$ 。

常用距离

数值数据(设 $p$ 个变量):

欧氏距离: $d(x,y) = \sqrt{\sum_{k=1}^{p}(x_k - y_k)^2}$ ;
绝对距离(曼哈顿距离): $d(x,y) = \sum_{k=1}^{p}|x_k - y_k|$ ;
切氏距离(切比雪夫距离): $d(x,y) = \max_{k}|x_k - y_k|$ ;
明氏距离(闵可夫斯基距离): $d(x,y) = \Big(\sum_{k=1}^{p}|x_k - y_k|^q\Big)^{1/q}$ ,是前三者的统一形式( $q=2$ 为欧氏、 $q=1$ 为绝对、 $q\to\infty$ 为切氏);
马氏距离(马哈拉诺比斯距离): $d(x,y) = \sqrt{(x-y)^{\top}\Sigma^{-1}(x-y)}$ ,用协方差矩阵 $\Sigma$ 消除量纲和相关性影响。

次序数据:观察值虽用文本或数字表示,但只有次序有用(如成绩 A、B、C)。此时先把数据量化(如 A=1、B=2、C=3),再套用数值距离。

属性数据(分类数据):观察值只有分类意义、不存在任何次序时,可以定义简单匹配距离——按两个观测取值不同的变量个数占比来算:

$d(x, y) = \frac{\text{取值不同的变量个数}}{p}$

二、聚类算法

系统聚类(层次聚类)步骤

设有 $n$ 个样品、 $p$ 个变量(Q 型聚类对样品分类, $n$ 个个体起步;R 型聚类对变量分类, $p$ 个变量起步):

先将每个个体各看成一类,共 $n$ 类;
找出最相似(距离最近)的两类,合并成一个新类,得 $n-1$ 类;
再找出最相似的两类合并,得 $n-2$ 类;
以此类推,直到把所有类合并成一大类。

整个过程自底向上逐层合并,可以画成一棵谱系图(树状图),在任意高度横切就得到相应数目的簇。

K-Means 聚类

算法思想:

初始化:令迭代次数 $t=0$ ,随机选择 $K$ 个样本点作为初始聚类中心 $\{m_1, \dots, m_K\}$ ;
对样本进行聚类:对固定的类中心 $m_k$ (第 $k$ 类的中心),计算每个样本到各类中心的距离,把每个样本指派到与其最近的中心所在的类,构成聚类结果 $C$ ;
计算新的类中心:对聚类结果 $C$ ,计算当前各类中样本的均值,作为新的类中心;
如果迭代收敛或符合停止条件,输出结果;否则令 $t \leftarrow t+1$ ,返回步骤 2。

性质可以保证在有限步数内收敛(目标函数单调不增且下有界)。

优化问题:假设 $K$ 个中心 $m_k$ 和指派 $C$ ,用欧氏距离考虑

$\min_{C, \{m_k\}}\ \sum_{k=1}^{K}\sum_{x_i \in C_k}\|x_i - m_k\|^2$

它通过交替优化求解:

固定中心 $m_k$ ,优化指派 $C$ :把每个样本分到最近的中心(第 2 步);
固定指派 $C$ ,优化中心 $m_k$ :令 $m_k$ 等于该类样本的均值(第 3 步,均值使类内平方和最小)。

优点:

容易理解,聚类效果不错——虽然只是局部最优,但往往局部最优就够用了;
处理大数据集时有较好的伸缩性;
当簇近似高斯分布时效果非常好;
算法复杂度低。

三、隐狄利克雷分布(LDA)模型

*作用:对给定的文本集合,学习到每个文本的话题分布以及每个话题的单词分布。LDA 是一个典型的三层贝叶斯主题模型。

多项分布

若多元离散随机变量 $X = (X_1, \dots, X_k)$ 的概率质量函数为

$P(X_1 = n_1, \dots, X_k = n_k) = \frac{n!}{n_1!\cdots n_k!}\prod_{i=1}^{k}p_i^{n_i}, \qquad \sum_i n_i = n,\ \sum_i p_i = 1$

则称 $X$ 服从参数为 $(n, p)$ 的多项分布,记作 $X \sim \text{Mult}(n, p)$ 。

狄利克雷分布

狄利克雷分布是多项分布参数 $p$ 的分布(定义在概率单纯形上)。令参数为 $\alpha = (\alpha_1, \dots, \alpha_k)$ ,其密度函数可以写成

$p(\theta \mid \alpha) = \frac{\Gamma\big(\sum_i \alpha_i\big)}{\prod_i \Gamma(\alpha_i)}\prod_{i=1}^{k}\theta_i^{\alpha_i - 1}, \qquad \theta_i \ge 0,\ \sum_i \theta_i = 1$

记作 $\theta \sim \text{Dir}(\alpha)$ 。前面那个归一化系数常记作 $\frac{1}{B(\alpha)}$ 。

共轭先验

把样本数据记为 $D$ ,目标是计算在数据 $D$ 给定条件下参数的后验概率。对于给定样本,似然函数是多项分布形式;假设参数 $\theta$ 服从狄利克雷先验 $\text{Dir}(\alpha)$ ,根据贝叶斯规则,后验分布是

$p(\theta \mid D) \propto p(D \mid \theta)\, p(\theta \mid \alpha)$

关键结论:狄利克雷分布是多项分布的共轭先验——先验是狄利克雷、似然是多项,则后验仍是狄利克雷,只是参数从 $\alpha$ 更新为 $\alpha + n$ (把观测计数加上去)。这个共轭性正是 LDA 能高效推断的原因。

*LDA 文本生成算法

LDA 假设每篇文档是这样"生成"出来的:

对于每个话题 $k$ :生成一个多项分布参数 $\varphi_k \sim \text{Dir}(\beta)$ ,作为该话题的单词分布;
对于每篇文本 $m$ :生成一个多项分布参数 $\theta_m \sim \text{Dir}(\alpha)$ ,作为该文本的话题分布;
对于文本 $m$ 中的每个单词位置 $n$ :
1. 先从文档的话题分布中抽一个话题 $z_{m,n} \sim \text{Mult}(\theta_m)$ ,作为该单词对应的话题;
2. 再从该话题的单词分布中抽一个单词 $w_{m,n} \sim \text{Mult}(\varphi_{z_{m,n}})$ 。

也就是"先按文档选话题、再按话题选词"两级抽样。观测到的只有单词 $w$ ,话题 $z$ 是隐变量;LDA 的任务就是反过来,根据观测的词推断出各文档的话题分布 $\theta$ 和各话题的单词分布 $\varphi$ 。

总结

距离三条件:对称性、非负性(=0 当且仅当同点)、三角不等式。
常用数值距离:欧氏(平方和开根)、绝对(绝对值和)、切氏(最大差)、明氏(统一 q 次)、马氏(带 Σ⁻¹ 去量纲/相关)。次序数据先量化,属性数据用匹配距离。
系统聚类:每个个体一类起步,反复合并最相似两类,直到并成一大类(谱系图)。
K-Means 四步:随机选 K 个中心 → 样本归到最近中心 → 中心更新为类内均值 → 收敛否则迭代;有限步收敛;交替优化(固定中心优化指派 / 固定指派优化中心);优点是简单、伸缩性好、近高斯簇效果佳、复杂度低。
LDA 作用:学出每篇文档的话题分布和每个话题的单词分布。
共轭:狄利克雷是多项分布的共轭先验,后验仍是狄利克雷(参数 α+计数)。
LDA 生成过程:每话题一个词分布(Dir(β))、每文档一个话题分布(Dir(α)),每个词位置先选话题再选词。