聚类算法

概述

聚类（clustering）为无监督学习（unsupervised learning），试图将样本集划分为若干互不相交的子集，即样本簇。聚类既能作为单独过程用于寻找数据内在的分布结构，也可作为其他学习任务的前驱过程。
无监督学习，训练样本的标注信息未知，目标是通过对无标注训练样本的学习揭示数据的内在性质及规律。

性能度量

聚类性能度量也称聚类“有效性指标”（validity index），与监督学习中的性能度量作用相似，对聚类结果，我们需通过某种性能度量来评估其好坏；另一方面，若是明确最终使用的性能度量，则可直接将其作为聚类过程的优化目标。
聚类性能度量大致有两类。一类是将聚类结果与某个“参考模型”（reference model）进行比较，称为“外部指标”（external index）；另一类是直接考察聚类结果而不利用任何参考模型，称为“内部指标”（internal index）。

外部指标

对数据集 $x_i = (x_1, x_2, \cdots, x_m)$ ，假定聚类给出的簇划分为 $C = \{ C_1, C_2, \cdots, C_k \}$ ，参考模型给出的簇划分为 $C^* = \{ C_1^*, C_2^*, \cdots, C_k^* \}$ ，令 $\lambda$ 与 $\lambda^*$ 分别表示 $C$ 和 $C^*$ 的簇标记向量，定义：
$a = \mid SS \mid, SS = \{ (x_i, x_j) \mid \lambda_i = \lambda_j, \lambda_i^* = \lambda_i^*, i < j \},$
$b = \mid SD \mid, SD = \{ (x_i, x_j) \mid \lambda_i = \lambda_j, \lambda_i^* \neq \lambda_i^*, i < j \},$
$c = \mid DS \mid, DS = \{ (x_i, x_j) \mid \lambda_i \neq \lambda_j, \lambda_i^* = \lambda_i^*, i < j \},$
$d = \mid DD \mid, DD = \{ (x_i, x_j) \mid \lambda_i \neq \lambda_j, \lambda_i^* \neq \lambda_i^*, i < j \}.$ 理解： $a, b, c, d$ 表示在参考模型的簇下，两个不同样本是否同时属于同一簇。

由上述公式导出下面常用的聚类性能度量外部指标：

Jaccard系数（Jaccard Coefficient, JC）
$JC = \frac {a} {a + b + c}$
FM指数（Fowlkes and Mallows Index, FMI）
$FMI = \sqrt {\frac {a} {a + b} \cdot \frac {a} {a + c}}$
Rand指数（Rand Index, RI）
$RI = \frac {2 (a + d)} {m (m - 1)}$

内部指标

考虑聚类结果的簇划分 $C = \{ C_1, C_2, \cdots, C_k \}$ ，定义
$avg (C) = \frac {2} {\mid C \mid (\mid C \mid - 1)} \sum_{1 \leq i < j \leq \mid C \mid} dist(x_i, x_j),$
$diam (C) = \max_{1 \leq i < j \leq \mid C \mid} dist(x_i, x_j),$
$d_{min} (C_i, C_j) = \min_{x_i \in C_i, x_j \in C_j} dist(x_i, x_j),$
$d_{cen} (C_i, C_j) = dist(\mu_i, \mu_j)$
由上述公式导出下面常用的聚类性能度量内部指标：

DB指数（Davies-Bouldin Index, DBI）
$DBI = \frac {1} {k} \sum_{i=1}^k \max_{j \neq i} (\frac {avg(C_i) + avg(C_j) } {d_{cen} (\mu_i, \mu_j)})$
Dunn指数（Dunn Index, DI）
$DI = \min_{1 \leq i \leq k} \{ min_{j \neq i} (\frac {d_{min} (C_i, C_j))} {max_{1 \leq l \leq k} diam (C_l)}) \}$ 显然，DBI的值越小越好，而DI则相反，值越大越好。

距离度量

给定样本 $x_i = (x_{i1}, x_{i2}, \cdots, x_{in})$ 与 $x_j = (x_{j1}, x_{j2}, \cdots, x_{j3})$ ，最常用的是“闵可夫斯基距离”（Minkowski distance）
$dist_{mk} (x_i, x_j) = (\sum_{u = 1}^n \mid x_{iu} - x_{ju} \mid ^ p) ^ {\frac {1} {p}}$ 其中， $p \geq 1$

当p=2时，称为欧氏距离（Euclidean distance）
$dist_{ed} (x_i, x_j) = \parallel x_i - x_j \parallel_2 = \sqrt {\sum_{u = 1}^n \mid x_{iu} - x_{ju} \mid ^ 2}$
当p=1时，称为曼哈顿距离（Manhattan distance）
$dist_{man} (x_i, x_j) = \parallel x_i - x_j \parallel_1 = \sum_{u = 1}^n \mid x_{iu} - x_{ju} \mid$

上述距离公式针对的是“有序属性”（ordinal attribute），比如 $\{ 1, 2, 3, 4\}$ 可以直接在属性值上计算距离；而类似 $\{$ 飞机, 火车, 轮船 $\}$ 这样的离散属性无法计算距离，采用VDM（Value Difference Metric）
$VDM_p (a, b) = \sum_{i = 1}^k \mid \frac {m_{u, a, i}} {m_{u, a}} - \frac {m_{u, b, i}} {m_{u, b}}\mid$ 其中， $m_{u, a}$ 表示属性 $u$ 上取值为 $a$ 的样本数， $m_{u, a, i}$ 表示在第 $i$ 个样本簇中在属性 $u$ 上取值 $a$ 的样本数， $k$ 为样本簇数。（例如，属性“交通工具”中两个离散值“飞机”和“火车”之间的VDM距离表示，“飞机”和“火车”在各个簇中样本数分别标准化，即除以它们在全局上总数，而后绝对差值的 $p$ 次幂求和）

原型聚类

原型聚类也称“基于原型的聚类”，此类算法假设聚类结构能通过一组原型刻画。通常的流程：先对原型进行初始化，然后对原型进行迭代更新求解。

$k$ 均值算法

给定样本集 $D = \{ x_1, x_2, \cdots, x_m\}$ ， $k$ 均值算法（k-means）针对聚类所得簇划分 $C = \{ C_1, C_2, \cdots, C_k\}$ ，最小化平方误差
$E = \sum_{i=1}^k \sum_{x \in C_i} \parallel x - \mu_i \parallel_2^2$ 其中 $\mu_i = \frac {1} {\mid C_i \mid} \sum_{x \in C_i} x$ 是簇 $C_i$ 的均值向量。最小化 $E$ 不容易， $k$ 均值算法采用了贪心策略，通过迭代优化来得到近似解。
算法流程如下：
输入：样本集 $D = \{ x_1, x_2, \cdots, x_m\}$ ；聚类簇数 $k$
输出：簇划分 $C = \{ C_1, C_2, \cdots, C_k\}$

从 $D$ 中随机选择 $k$ 个样本作为初始均值向量 $\{ \mu_1, \mu_2, \cdots, \mu_k \}$
repeat
令 $C_i = \emptyset (1 \leq i \leq k)$
for $j = 1, 2, \cdots, m$ do
计算样本 $x_j$ 与各均值向量 $\mu_i (1 \leq i \leq k)$ 的距离： $d_{ji} = \parallel x_j - \mu_i \parallel_2$ ;
根据距离最近的均值向量确定 $x_j$ 的簇标记： $\lambda_j = \mathop {\arg \min} \limits_{i \in (1, 2, \cdots, k)} d_{ji}$ ;
将样本 $x_j$ 划入相应的簇： $C_{\lambda_j} = C_{\lambda_j} \cup \{ x_j \}$ ;
end for
for $i = 1, 2, \cdots, k$ do
计算新均值向量： $\mu_i^{'} = \frac {1} {\mid C_i \mid} \sum_{x \in C_i} x$ ;
if $\mu_i^{'} \neq \mu_i$ then
将当前均值向量 $\mu_i$ 更新 $\mu_i^{'}$
保持当前均值向量不变
end if
end for
until 当前均值向量均未更新

理解：根据给定聚类簇数，随机初始化均值向量；根据欧式距离对样本分簇；更新各簇的均值向量；重复上述步骤，直到均值向量均未更新。

学习向量量化

学习向量量化（Learning Vector Quantization, LVQ）假设样本数据带有类别标记，学习过程中利用样本的这些监督信息来辅助聚类。
算法流程如下：
输入：样本集 $D = \{ (x_1, y_1), (x_2, y_2), \cdots, (x_m, y_m) \}$ ；原型向量个数 $q$ ，各原型预设的类别标记 $\{ t_1, t_2, \cdots, t_q\}$ ；学习率 $\eta \in (0, 1)$ .
输出：原型向量 $\{ p_1, p_2, \cdots, p_q\}$

初始化一组原型向量 $\{ p_1, p_2, \cdots, p_q \}$
repeat
从样本集 $D$ 随机选取样本 $(x_j, y_j)$ ；
计算样本 $x_j$ 与 $p_i (1 \leq i \leq q)$ 的距离： $d_{ji} = \parallel x_j - p_i \parallel_2$ ；
找出与 $x_j$ 距离最近的原型向量 $p_{i^*}$ ， $i^* = \mathop {\arg \min} \limits_{i \in \{ 1, 2, \cdots, q \}} d_{ji}$ ；
if $y_j = t_{i^*}$ then
$p^{'} = p_{i^*} + \eta \cdot (x_j - p_{i^*})$
else
$p^{'} = p_{i^*} - \eta \cdot (x_j - p_{i^*})$
end if
将原型向量 $p_{i^*}$ 更新为 $p^{'}$
until 满足停止条件

理解：样本集存在标记，则已经可以通过标记将样本集划分成多个不相交的子集了。学习向量量化基于欧氏距离，通过 $\eta \cdot (x_j - p_{i^*})$ 使得最终聚类结果趋向于按照标记划分的子集。

高斯混合聚类

高斯混合聚类（Mixture-of-Gaussion）采用概率模型来表达聚类原型。
关于（多元）高斯分布的定义：对 $n$ 维样本空间 $\chi$ 中的随机向量 $x$ ，若 $x$ 服从高斯分布，其概率密度函数为
$p(x) = \frac {1} {(2 \pi)^{\frac {n} {2}} \mid \Sigma \mid^{\frac {1} {2}}} e^{- \frac {1} {2} (x - \mu)^T \Sigma^{-1} (x - \mu)}$ 其中 $\mu$ 是 $n$ 维均值向量， $\Sigma$ 是 $n \times n$ 的协方差矩阵。为了明确显示高斯分布与相应参数的依赖关系，将概率密度函数记为 $p(x \mid \mu, \Sigma)$ 。于是，定义高斯混合分布
$p_M (x) = \sum_{i=1}^k \alpha_i \cdot p(x \mid \mu_i, \Sigma_i)$ 该分布共由 $k$ 个混合成分组成，每个混合成分对应一个高斯分布，其中 $\mu_i$ 与 $\Sigma_i$ 是第 $i$ 个高斯混合成分的参数，而 $\alpha_i > 0$ 为相应的“混合系数”(mixture coefficient)， $\sum_{i=1}^k \alpha_i = 1$ 。
算法流程如下：
输入：样本集 $D = \{ x_1, x_2, \cdots, x_m \}$ ；高斯混合成分个数 $k$ .
输出：簇划分 $C = \{ C_1, C_2, \cdots, C_k \}$

初始化高斯混合分布的模型参数 $\{ (\alpha_i, \mu_i, \Sigma_{i}) \mid 1 \leq i \leq k \}$
repeat
for $j = 1, 2, \cdots, m$ do
计算 $x_j$ 由各混合成分生成的后验概率，即

$\gamma_{ji} = p_M (z_j = i \mid x_j) (1 \leq i \leq k) = \frac {P(z_j = i) \cdot p_M (x_j \mid z_j = i)} {p_M (x_j)} = \frac {\alpha_i \cdot p(x_j \mid \mu_i, \Sigma_{i})} {\sum_{l=1}^k \alpha_l \cdot p(x_j \mid \mu_l \Sigma_{l})}$

end for
for $i = 1, 2, \cdots, k$ do
计算新均值向量： $\mu_i^{'} = \frac {\sum_{j=1}^m \gamma_{ji} x_j} {\sum_{j=1}^m \gamma_{ji}}$ ；
计算新协方差矩阵： $\Sigma_{i}^{'} = \frac {\sum_{j=1}^m \gamma_{ji} (x_j - \mu_i^{'}) (x_j - \mu_i^{'})^T} {\sum_{j=1}^m \gamma_{ji}}$ ；
计算新混合系数： $\alpha_{i}^{'} = \frac {\sum_{j=1}^m \gamma_{ji}} {m}$ ；
end for
将模型参数 $\{ (\alpha_i, \mu_i, \Sigma_{i}) \mid 1 \leq i \leq k \}$ 更新为 $\{ (\alpha_i^{'}, \mu_i^{'}, \Sigma_{i}^{'}) \mid 1 \leq i \leq k \}$
until 满足停止条件
$C_i = \emptyset (1 \leq i \leq k)$
for $j = 1, 2, \cdots, m$ do
根据 $\lambda_j = \mathop {\arg \max} \limits_{i \in \{ 1, 2, \cdots, k\} } \gamma_{ji}$ 确定 $x_j$ 的簇标记 $\lambda_j$ ；
将 $x_j$ 划入相应的簇： $C_{\lambda_j} = C_{\lambda_j} \cup {x_j}$
end for