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

常用距离#

数值数据(设 $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$ 个变量起步):

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

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

K-Means 聚类#

算法思想:

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

优点:

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

多项分布#

若多元离散随机变量 $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 假设每篇文档是这样”生成”出来的:

1. 对于每个话题 $k$:生成一个多项分布参数 $\varphi_k \sim \text{Dir}(\beta)$,作为该话题的单词分布;
2. 对于每篇文本 $m$:生成一个多项分布参数 $\theta_m \sim \text{Dir}(\alpha)$,作为该文本的话题分布;
3. 对于文本 $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$。