无监督学习（Unsupervised Learning）的目标是通过对无标记训练样本的学习，发掘和揭示数据集本身潜在的结构与规律，即不依赖于训练数据集的类标记信息。聚类（Clustering）是一种经典的无监督学习方法，试图将数据集的样本划分为若干个互不相交的簇（Cluster），每个簇对应一个潜在的类别。

Hyplus目录

0 聚类任务概述

假定样本集 $D={\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_m}$ 包含 $m$ 个无标记样本，其中 $\mathbf{x}_{i}=(x_{i1};x_{i2};\dots;x_{in})$ ，则聚类算法将样本集 $D$ 划分为 $k$ 个不相交的簇 $\{ C_l\mid l=1,2,\dots,k \}$ ，其中 $C_{l'}\cap_{l' \ne l} C_l = \empty$ 且 $D=\bigcup\limits_{l=1}^k C_l$ 。用 $\lambda_j\in \{1,2,\dots,k \}$ 表示样本 $\mathbf{x}_j$ 的簇标记（Cluster Label），即 $\mathbf{x}_j\in C_{\lambda_{j}}$ ，故聚类的结果可用包含 $m$ 个元素的簇标记向量 $\mathbf{\lambda}=(\lambda_1;\lambda_2;\dots;\lambda_m)$ 表示。

聚类既能作为一个单独过程，用于找寻数据内在的分布结构，亦可作为分类等其他学习任务的前驱过程。

本文首先介绍聚类算法涉及的两个问题，之后介绍常见的若干种聚类算法。

1 性能度量

聚类性能度量亦称聚类有效性指标（Validity Index）。直观上看，要使得聚类结果较好，则应同一簇的样本尽可能彼此相似，不同簇的样本尽可能不同，即“物以类聚”。换言之，聚类结果的簇内相似度（Intra-cluster Similarity）高且簇间相似度（Inter-cluster Similarity）低。

聚类性能度量大致有以下两类——

1.1 外部指标

外部指标（External Index）将聚类结果与某个参考模型（Reference Model）进行比较。对于数据集 $D=\{\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_m\}$ ，假定通过聚类给出的簇划分为 $\mathcal{C}=\{C_1,C_2,\dots,C_k\}$ ，参考模型给出的簇划分为 $\mathcal{C}^*=\{C_1^*,C_2^*,\dots,C_k^*\}$ ，令 $\mathbf{\lambda},\mathbf{\lambda}^*$ 分别表示 $\mathcal{C},\mathcal{C}^*$ 对应的簇标记向量。将样本两两配对考虑，定义

 $\begin{aligned} a&=|SS|,\ &SS=\{(\mathbf{x}_i,\mathbf{x}_j)\mid \lambda_i=\lambda_j,\lambda_i^*=\lambda_j^*,i\lt j\}\\ b&=|SD|,\ &SD=\{(\mathbf{x}_i,\mathbf{x}_j)\mid \lambda_i=\lambda_j,\lambda_i^*\ne \lambda_j^*,i\lt j\}\\ c&=|DS|,\ &DS=\{(\mathbf{x}_i,\mathbf{x}_j)\mid \lambda_i\ne \lambda_j,\lambda_i^*=\lambda_j^*,i\lt j\}\\ d&=|DD|,\ &SS=\{(\mathbf{x}_i,\mathbf{x}_j)\mid \lambda_i\ne \lambda_j,\lambda_i^*\ne \lambda_j^*,i\lt j\} \end{aligned}$

其中集合 $SD$ 包含了在 $\mathcal{C}$ 中隶属于相同簇但在 $\mathcal{C}^*$ 中隶属于不同簇的样本对，其他三个表示隶属情况的集合同理。由于每个样本对仅能出现在一个集合中，故有 $a+b+c+d=\dfrac{m(m-1)}{2}$ 成立。

基于如上四式可导出如下三种常用的聚类性能度量外部指标：

Jaccard系数（Jaccard Coefficient，JC）：

 $\begin{aligned} \text{JC}=\frac{a}{a+b+c} \end{aligned}$

FM指数（Fowlkes and Mallows Index，FMI）：

 $\begin{aligned} \text{FMI}=\sqrt{\frac{a}{a+b}\cdot \frac{a}{a+c}} \end{aligned}$

Rand指数（Rand Index，RI）：

 $\begin{aligned} \text{RI}=\frac{2(a+d)}{m(m-1)} \end{aligned}$

显然，上述性能度量的结果值均在 $[0,1]$ 区间，值越大越好。

1.2 内部指标

内部指标（Internal Index）直接考察聚类结果而不利用任何参考模型。考虑聚类结果的簇划分 $\mathcal{C}=\{C_1,C_2,\dots,C_k\}$ ，定义

 $\begin{aligned} \text{avg}(C) &= \frac{2}{|C|(|C|-1)}\sum\limits_{1\le i \lt j \le |C|} \text{dist}(\mathbf{x}_i,\mathbf{x}_j)\\ \text{diam}(C) &= \max\limits_{1\le i\lt j \le |C|} \text{dist}(\mathbf{x}_i,\mathbf{x}_j)\\ d_{\min}(C_i,C_j) &= \min\limits_{\mathbf{x}_i\in C_i,\ \mathbf{x}_j\in C_j} \text{dist}(\mathbf{x}_i,\mathbf{x}_j)\\ d_{\text{cen}}(C_i,C_j) &=\text{dist}(\mathbf{\mu}_i,\mathbf{\mu}_j) \end{aligned}$

其中 $\text{dist}(\cdot,\cdot)$ 用于计算两个样本之间的距离（见后述），簇 $C$ 的中心点 $\mu=\dfrac{1}{|C|}\sum\limits_{1\le i \le |C|}\mathbf{x}_i$ ； $\text{avg}(C)$ 为簇 $C$ 内样本间的平均距离， $\text{diam}(C)$ 为簇 $C$ 内样本间的最远距离， $d_{\min}(C_i,C_j)$ 为簇 $C_i,C_j$ 最近样本间的距离， $d_{\text{cen}}(C_i,C_j)$ 为簇 $C_i,C_j$ 中心点间的距离。

基于如上四式可导出如下两种常用的聚类性能度量内部指标：

DB指数（Davies-Bouldin Index，DBI）：

 $\begin{aligned} \text{DBI}=\frac1k \sum\limits_{i=1}^k \max\limits_{j\ne i} \left( \frac{\text{avg}(C_i)+\text{avg}(C_j)}{d_{\text{cen}}(C_i,C_j) } \right) \end{aligned}$

Dunn指数（Dunn Index，DI）：

 $\begin{aligned} \text{DI}=\min\limits_{1\le i \le k} \left\{ \min\limits_{j\ne i} \left( \frac{d_{\min}(C_i,C_j)}{\max\limits_{1\le l\le k}\text{diam}(C_l)} \right) \right\} \end{aligned}$

显然，DBI的值越小越好，而DI则相反，值越大越好。

2 距离度量

对于函数 $\text{dist}(\cdot,\cdot)$ ，若其是一个距离度量（Distance Measure），则满足以下基本性质：

非负性： $\text{dist}(\mathbf{x}_i,\mathbf{x}_j)\ge 0$
同一性： $\text{dist}(\mathbf{x}_i,\mathbf{x}_j)=0\Leftrightarrow \mathbf{x}_i=\mathbf{x}_j$
对称性： $\text{dist}(\mathbf{x}_i,\mathbf{x}_j)=\text{dist}(\mathbf{x}_j,\mathbf{x}_i)$
直递性： $\text{dist}(\mathbf{x}_i,\mathbf{x}_j)\le \text{dist}(\mathbf{x}_i,\mathbf{x}_k) + \text{dist}(\mathbf{x}_k,\mathbf{x}_j)$

给定样本 $\mathbf{x}_i=(x_{i1};x_{i2};\dots;x_{in}),\mathbf{x}_j=(x_{j1};x_{j2};\dots;x_{jn})$ ，最常用的距离度量方法为闵可夫斯基距离（Minkowski Distance），其中 $p \ge 1$ ：

 $\begin{aligned} \text{dist}_{\text{mk}}(\mathbf{x}_i,\mathbf{x}_j)=\left(\sum\limits_{u=1}^n |x_{iu}-x_{ju}|^p \right)^{\frac{1}{p}} \end{aligned}$

当 $p=2$ 时，闵可夫斯基距离即为欧氏距离（Euclidean Distance）：

 $\begin{aligned} \text{dist}_{\text{ed}}(\mathbf{x}_i,\mathbf{x}_j)=\left\| \mathbf{x}_i-\mathbf{x}_j \right \|_2=\sqrt{ \sum\limits_{u=1}^n |x_{iu}-x_{ju}|^2 } \end{aligned}$

当 $p=1$ 时，闵可夫斯基距离即为曼哈顿距离（Manhattan Distance）：

 $\begin{aligned} \text{dist}_{\text{man}}(\mathbf{x}_i,\mathbf{x}_j)=\left\| \mathbf{x}_i-\mathbf{x}_j \right \|_1=\sum\limits_{u=1}^n |x_{iu}-x_{ju}| \end{aligned}$

常将属性划分为连续属性（Continuous Attribute，又称数值属性，Numerical Attribute）和离散属性（Categorical Attribute，又称列名属性，Nominal Attribute）。对于连续属性，一般都可被学习器所用，有时会根据具体情形进行相应的预处理，例如归一化等；而对于离散属性，需根据有无序（Order）关系转化为连续值或向量的形式（详见“一元线性回归”子节开头）。

在进行距离度量时，易知连续属性和存在序关系的离散属性都可以直接参与计算，因为它们都可以反映一种程度，常统称为有序属性（Ordinal Attribute），而不存在序关系的离散属性常称为无序属性（Non-ordinal Attribute）。显然，闵可夫斯基距离仅适用于有序属性。

对于无序属性可采用VDM（Value Difference Metric）进行距离计算。令 $m_{u,a}$ 表示属性 $u$ 上取值为 $a$ 的样本数， $m_{u,a,i}$ 表示在第 $i$ 个样本簇中属性 $u$ 上取值为 $a$ 的样本数， $k$ 为样本簇数（样本类别已知时常设置为类别数），则属性 $u$ 上两个离散值 $a,b$ 之间的VDM距离为：

 $\begin{aligned} \text{VDM}_p(a,b)=\sum\limits_{i=1}^k \left | \frac{m_{u,a,i}}{m_{u,a}} -\frac{m_{u,b,i}}{m_{u,b}} \right |^p \end{aligned}$

故将闵可夫斯基距离和VDM结合即可处理混合属性。假定有 $n_\text{c}$ 个有序属性、 $n-n_{\text{c}}$ 个无序属性，不失一般性，令有序属性排列在无序属性之前，则

 $\begin{aligned} \text{MinkovDM}_p(\mathbf{x}_i,\mathbf{x}_j)=\left( \sum\limits_{u=1}^{n_{\text{c}}} |x_{iu}-x_{ju}|^p + \sum\limits_{u=n_{c}+1}^n \text{VDM}_p (x_{iu},x_{ju}) \right)^{\frac1p} \end{aligned}$

当样本空间中不同属性的重要性不同时，可使用加权距离（Weighted Distance）。设权重 $w_i\ge 0\ (i=1,2,\dots,n)$ 表示不同属性的重要性，且 $\sum\limits_{i=1}^n w_i=1$ ，则加权闵可夫斯基距离可表示为：

 $\begin{aligned} \text{dist}_{\text{wmk}}(\mathbf{x}_i,\mathbf{x}_j)=\left ( w_1\cdot |x_{i1}-x_{j1}|^p + \cdots + w_n \cdot |x_{in} - x_{jn}|^p \right )^{\frac1p} \end{aligned}$

注意通常是基于某种形式的距离来定义相似度度量（Similarity Measure），距离越大，相似度越小。然而用于相似度度量的距离未必一定要满足距离度量的所有基本性质，尤其是直递性，此时称这种距离为非度量距离（Non-metric Distance）。

本节介绍的距离计算式均为事先定义的，但在不少现实任务中，有必要基于数据样本来确定合适的距离计算式。可通过距离度量学习（Distance Metric Learning）来实现（详见“降维与度量学习”最后一章）。

3 原型聚类

原型聚类（Prototype-based Clustering，“基于原型的聚类”）假设聚类结构能通过一组原型刻画，其中原型指样本空间中具有代表性的点。通常情形下，算法先对原型进行初始化，然后对原型进行迭代更新求解，采用不同的原型表示、不同的求解方式，将产生不同的算法。

3.1 k-均值

k-均值（k-Means）算法的思想十分简单：首先随机指定类中心，根据样本与类中心的远近划分类簇，接着重新计算类中心，迭代直至收敛。给定样本集 $D=\{\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_m\}$ ，k-均值算法针对聚类所得簇划分 $\mathcal{C}=\{C_1,C_2,\dots,C_k\}$ 最小化平方误差

 $\begin{aligned} E=\sum\limits_{i=1}^k\sum\limits_{\mathbf{x}\in C_i} \left\| \mathbf{x}-\mathbf{\mu}_i \right\|_2^2 \end{aligned}$

其中 $\mu_i=\dfrac{1}{|C_i|}\sum\limits_{\mathbf{x}\in C_i}\mathbf{x}$ 是簇 $C_i$ 的均值向量。直观来看，上式在一定程度上刻画了簇内样本围绕簇均值向量的紧密程度， $E$ 值越小则簇内样本相似度越高。

最小化上式是一个NP难问题，因此k-均值算法采用了贪心策略，通过迭代优化来近似求解。k-均值算法流程如下所示：

输入：样本集 $D=\{\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_m\}$ ；聚类簇数 $k$
过程：
- 从 $D$ 中随机选择 $k$ 个样本作为初始均值向量 $\{\mathbf{\mu}_1,\mathbf{\mu}_2,\dots,\mathbf{\mu}_k\}$ 初始化
- repeat
  - 令 $C_i=\empty\ (1\le i \le k)$
  - for j=1,2,\dots,m do 迭代更新簇划分
    - 计算样本 $\mathbf{x}_j$ 与各均值向量 $\mathbf{\mu}_i\ (1\le i \le k)$ 的距离 $d_{ji}=\left\| \mathbf{x}_j-\mathbf{\mu}_i \right\|_2$
    - 根据距离最近的均值向量确定 $\mathbf{x}_j$ 的簇标记 $\lambda_j=\underset{i\in\{1,2,\dots,k\}}{\arg\min} d_{ji}$
    - 将样本 $\mathbf{x}_j$ 划入相应的簇 $C_{\lambda_j}\gets C_{\lambda_j}\cup \{\mathbf{x}_j \}$
  - end for
  - for i=1,2,\dots,k do 迭代更新均值向量
    - 计算新均值向量 $\mathbf{\mu}_{i}'=\dfrac{1}{|C_i|} \sum\limits_{\mathbf{x}\in C_i}\mathbf{x}$
    - if \mathbf{\mu}_i' \ne \mathbf{\mu}_i then
      - 更新当前均值向量 $\mathbf{\mu}_i\gets \mathbf{\mu}_i'$
    - else
      - 保持当前均值向量不变
    - end if
  - end for
- until 当前均值向量均未更新 为避免运行时间过长，通常设置一个最大运行轮数或最小调整幅度阈值，若达到最大轮数或调整幅度小于阈值，则停止运行
输出：簇划分 $\mathcal{C}=\{C_1,C_2,\dots,C_k\}$

k-均值算法示意图

3.2 学习向量量化

与k-均值算法不同，学习向量量化（Learning Vector Quantization，LVQ）使用样本真实类标记辅助聚类（可视为通过聚类来形成类别“子类”结构，每个子类对应一个聚类簇）。

LVQ根据样本的类标记，从各类中分别随机选出一个样本作为该类簇的原型，从而形成待学习的 $n$ 维原型向量组 $\{\mathbf{p}_1,\mathbf{p}_2,\dots,\mathbf{p}_q\}$ ，这 $q$ 个原型向量分别代表一个聚类簇，簇标记 $t_i\in \mathcal{Y}$ ；接着从样本集中随机挑选一个样本 $\mathbf{x}_j$ ，计算其与原型向量组中每个向量的距离，并选取距离最小的原型向量所在的类簇作为它的划分结果，再与其真实类标记 $y_j\in \mathcal{Y}$ 比较，更新原型向量。

LVQ算法流程如下所示：

输入：样本集 $D=\{\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_m\}$ ；原型向量个数 $q$ ，各原型向量预设的类别标记 $\{t_1,t_2,\dots,t_q\}$ ；学习率 $\eta\in (0,1)$
过程：
- 从各类中分别随机选择1个样本作为原型向量，初始化原型向量组 $\{\mathbf{p}_1,\mathbf{p}_2,\dots,\mathbf{p}_q\}$
- repeat
  - 从样本集 $D$ 随机选取样本 $(\mathbf{x}_j,y_j)$
  - 计算样本 $\mathbf{x}_j$ 与各原型向量 $\mathbf{p}_i\ (1\le i\le q)$ 的距离 $d_{ji}=\left\| \mathbf{x}_j-\mathbf{p}_i \right\|_2$
  - 找出与 $\mathbf{x}_j$ 距离最近的原型向量 $\mathbf{p}_{i^*},\ i^*=\underset{i\in \{1,2,\dots,q\}}{\arg \min} d_{ji}$
  - if y_j=t_{i^*} then 划分结果正确，则对应原型向量靠近该样本
    - $\mathbf{p}'=\mathbf{p}_{i^*}+\eta\cdot(\mathbf{x}_j-\mathbf{p}_{i^*})$
  - else 划分结果错误，则对应原型向量远离该样本
    - $\mathbf{p}'=\mathbf{p}_{i^*}-\eta\cdot(\mathbf{x}_j-\mathbf{p}_{i^*})$
  - end if
  - 更新原型向量 $\mathbf{p}_{i^*}\gets \mathbf{p}'$
- until 满足停止条件 例如达到最大迭代轮数
输出：原型向量组 $\{\mathbf{p}_1,\mathbf{p}_2,\dots,\mathbf{p}_q\}$

在学得原型向量组后，即可实现对样本空间 $\mathcal{X}$ 的簇划分。每个样本 $\mathbf{x}$ 被划入与其距离最近的原型向量所代表的簇中；换言之，每个原型向量 $\mathbf{p}_i$ 定义了一个与之相关的区域 $R_i$ ，该区域中每个样本与 $\mathbf{p}_i$ 的距离不大于其与其他原型向量 $\mathbf{p}_{i'}\ (i' \ne i)$ 的距离，即

 $\begin{aligned} R_i=\{\mathbf{x} \in \mathcal{X}\mid \left\| \mathbf{x}-\mathbf{p}_i \right\|_2 \le \left\| \mathbf{x}-\mathbf{p}_{i'} \right\|_2,\ i' \ne i \} \end{aligned}$

若将 $R_i$ 中样本全用原型向量 $\mathbf{p}_i$ 表示，则可实现数据的有损压缩（Lossy Compression），即向量量化（Vector Quantization）。

由此形成了对样本空间 $\mathcal{X}$ 的簇划分 $\{R_1,R_2,\dots,R_q\}$ ，该划分通常称为Voronoi划分（Voronoi Tessellation）。

LVQ算法示意图

3.3 高斯混合聚类

前述的k-均值与LVQ都试图以类中心作为原型指导聚类，而高斯混合（Mixture-of-Gaussian）聚类采用概率模型来表达聚类原型：若每个类簇中的样本都服从一个多维高斯分布，那么空间中的样本可以看作由多个多维高斯分布混合而成。

对于 $n$ 维样本空间 $\mathcal{X}$ 中的随机向量 $\mathbf{x}$ ，若 $\mathbf{x}$ 服从高斯分布（正态分布，Normal distribution），即 $\mathbf{x}\sim \mathcal{N}(\mathbf{\mu}, \mathbf{\Sigma})$ ，则其概率密度函数为

 $\begin{aligned} p(\mathbf{x}\mid \mathbf{\mu},\mathbf{\Sigma})=\frac{1}{(2\pi)^{\frac{n}{2}}|\mathbf{\Sigma}|^{\frac12}}\text{e}^{-\frac{1}{2}(\mathbf{x}-\mathbf{\mu})^\top \mathbf{\Sigma}^{-1} (\mathbf{x}-\mathbf{\mu}) } \end{aligned}$

其中 $\mathbf{\mu}$ 是 $n$ 维均值向量，对称正定矩阵 $\mathbf{\Sigma}$ 是 $n\times n$ 的协方差矩阵。据此可定义由 $k$ 个混合成分组成的高斯混合分布：

 $\begin{aligned} p_{\mathcal{M}}(\mathbf{x})=\sum\limits_{i=1}^k \alpha_i \cdot p(\mathbf{x}\mid \mathbf{\mu}_i,\mathbf{\Sigma}_i) \end{aligned}$

其中 $\alpha_i \gt 0$ 为第 $i$ 个高斯混合成分的混合系数（Mixture Coefficient）， $\sum\limits_{i=1}^k \alpha_i = 1$ 。则空间中样本的生成过程可由高斯混合分布给出：首先根据 $\alpha_1,\alpha_2,\dots,\alpha_k$ 定义的先验分布选择高斯混合成分（ $\alpha_i$ 就是选择第 $i$ 个混合成分的概率），然后根据被选混合成分的概率密度函数进行采样，从而生成对应的样本。

若训练集 $D=\{\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_m\}$ 由上述过程生成，令随机变量 $z_j\in \{1,2,\dots,k\}$ 表示生成样本 $\mathbf{x}_j$ 的高斯混合成分，则 $z_j$ 的先验概率 $P(z_j=i)=\alpha_i\ (i=1,2,\dots,k)$ 。根据贝叶斯定理， $z_j$ 的后验分布为

 $\begin{aligned} p_{\mathcal{M}}(z_j=i\mid \mathbf{x}_j) &= \frac{P(z_j=i)\cdot p_{\mathcal{M}}(\mathbf{x}_j\mid z_j=i)}{p_{\mathcal{M}}(\mathbf{x}_j)}\\ &= \frac{\alpha_i \cdot p(\mathbf{x}_j\mid \mathbf{\mu}_i,\mathbf{\Sigma}_i)}{\sum\limits_{l=1}^k \alpha_l \cdot p(\mathbf{x}_j\mid \mathbf{\mu}_l,\mathbf{\Sigma}_l)} \end{aligned}$

换言之， $p_{\mathcal{M}}(z_j=i\mid \mathbf{x}_j)$ 给出了样本 $\mathbf{x}_j$ 由第 $i$ 个高斯混合成分生成的后验概率，记 $\gamma_{ji}=p_{\mathcal{M}}(z_j=i\mid \mathbf{x}_j)\ (i=1,2,\dots,k)$ 。当高斯混合分布已知时，高斯混合聚类将把样本集 $D$ 划分为 $k$ 个簇 $\mathcal{C}=\{C_1,C_2,\dots,C_k\}$ ，每个样本 $\mathbf{x}_j$ 的簇标记 $\lambda_j$ 如下确定：

 $\begin{aligned} \lambda_j = \underset{i\in \{1,2,\dots,k\}}{\arg\max} \gamma_{ji} \end{aligned}$

对于模型参数 $\{(\alpha_i,\mathbf{\mu}_i,\mathbf{\Sigma}_i)\mid 1\le i\le k\}$ 的求解，给定样本集 $D$ ，可采用极大似然估计，即最大化对数似然

 $\begin{aligned} LL(D)=\ln \left(\prod\limits_{j=1}^m p_{\mathcal{M}}(\mathbf{x}_j) \right)=\sum\limits_{j=1}^m\ln \left( \sum\limits_{i=1}^k \alpha_i \cdot p(\mathbf{x}\mid \mathbf{\mu}_i,\mathbf{\Sigma}_i) \right) \end{aligned}$

由于缺少真实类标记，常采用EM算法（见“贝叶斯分类”篇之“EM算法”）进行迭代优化求解：首先对高斯分布的参数及混合系数进行随机初始化，计算出各 $\gamma_{ji}$ ，再最大化似然函数（即 $LL(D)$ 分别对 $\alpha_i,\mathbf{\mu}_i,\mathbf{\Sigma}_i$ 求偏导，解见算法流程），对参数进行迭代更新。详细证明过程略。

高斯混合聚类算法流程如下：

输入：样本集 $D=\{\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_m\}$ ；高斯混合成分个数 $k$
过程：
- 初始化高斯混合分布的模型参数 $\{(\alpha_i,\mathbf{\mu}_i,\mathbf{\Sigma}_i)\mid 1\le i\le k\}$
- repeat
  - for j=1,2,\dots,m do E步
    - 计算 $\mathbf{x}_j$ 由各混合成分生成的后验概率 $\gamma_{ji}=p_{\mathcal{M}}(z_j=i\mid \mathbf{x}_j)\ (1\le i \le k)$
  - end for
  - for i=1,2,\dots,k do M步
    - 计算新均值向量 $\mathbf{\mu}_i'=\dfrac{\sum\limits_{j=1}^m\gamma_{ji}\mathbf{x}_j}{\sum\limits_{j=1}^m\gamma_{ji}}$
    - 计算新协方差矩阵 $\mathbf{\Sigma}_i'=\dfrac{\sum\limits_{j=1}^m\gamma_{ji}(\mathbf{x}_j-\mathbf{\mu}_i')(\mathbf{x}_j-\mathbf{\mu}_i')^\top}{\sum\limits_{j=1}^m\gamma_{ji}}$
    - 计算新混合系数 $\alpha_i'=\dfrac{\sum\limits_{j=1}^m\gamma_{ji}}{m}$
  - end for
  - 更新模型参数 $\{(\alpha_i,\mathbf{\mu}_i,\mathbf{\Sigma}_i)\mid 1\le i\le k\}\gets \{(\alpha_i',\mathbf{\mu}_i',\mathbf{\Sigma}_i')\mid 1\le i\le k\}$
- until 满足停止条件 例如达到最大迭代轮数
- $C_i = \empty\ (1\le i \le k)$
- for j=1,2,\dots,m do
  - 确定 $\mathbf{x}_j$ 的簇标记 $\lambda_j = \underset{i\in \{1,2,\dots,k\}}{\arg\max} \gamma_{ji}$
  - 将 $\mathbf{x}_j$ 划入相应的簇 $C_{\lambda_j}\gets C_{\lambda_j}\cup \{\mathbf{x}_j\}$
- end for
输出：簇划分 $\mathcal{C}=\{C_1,C_2,\dots,C_k\}$

高斯混合算法

4 密度聚类

密度聚类（Density-based Clustering，“基于密度的聚类”）假设聚类结构能通过样本分布的紧密程度确定。通常情形下，密度聚类算法从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇以获得最终的聚类结果。

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种著名的密度聚类算法，基于一组邻域（Neighborhood）参数来刻画样本分布的精密程度。给定样本集 $D=\{\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_m\}$ ，定义如下几个概念：

ε-邻域：对于 $\mathbf{x}_j\in D$ ，其ε-邻域包含样本集 $D$ 中与 $\mathbf{x}_j$ 的距离不大于 $\varepsilon$ 的样本，即 $N_{\varepsilon}(\mathbf{x}_j)=\{\mathbf{x}_i\in D\mid \text{dist}(\mathbf{x}_i,\mathbf{x}_j)\le \varepsilon \}$ 。本节中距离函数均默认使用欧氏距离。
核心对象（Core Object）：若 $\mathbf{x}_j$ 的ε-邻域至少包含 $MinPts$ 个样本，即 $|N_{\varepsilon}|\ge MinPts$ ，则 $\mathbf{x}_j$ 是一个核心对象。
密度直达（Directly Density-reachable）：若 $\mathbf{x}_j$ 位于 $\mathbf{x}_i$ 的ε-邻域中，且 $\mathbf{x}_i$ 是核心对象，则称 $\mathbf{x}_j$ 由 $\mathbf{x}_i$ 密度直达。密度直达关系通常不满足对称性。
密度可达（Density-reachable）：对于 $\mathbf{x}_i,\mathbf{x}_j$ ，若存在样本序列 $\mathbf{p}_1,\mathbf{p}_2,\dots,\mathbf{p}_n$ ，其中 $\mathbf{p}_1=\mathbf{x}_i,\mathbf{p}_n=\mathbf{x}_j$ 且 $\mathbf{p}_{i+1}$ 由 $\mathbf{p}_i$ 密度直达，则称 $\mathbf{x}_j$ 由 $\mathbf{x}_i$ 密度可达。密度可达关系满足直递性，但不满足对称性。
密度相连（Density-connected）：对于 $\mathbf{x}_i,\mathbf{x}_j$ ，若存在 $\mathbf{x}_k$ 使得 $\mathbf{x}_i,\mathbf{x}_j$ 均由 $\mathbf{x}）k$ 密度可达，则称 $\mathbf{x}_i,\mathbf{x}_j$ 密度相连。密度相连关系满足对称性。

DBSCAN

据此，DBSCAN将簇定义为由密度可达关系导出的最大密度相连样本集合。数据集 $D$ 中不属于任何簇的样本被认为是噪声（Noise）或异常（Anomaly）样本。给定邻域参数 $(\varepsilon,MinPts)$ ，簇 $C \subseteq D$ 是满足以下性质的非空样本子集：

连接性（Connectivity）： $\mathbf{x}_i\in C,\ \mathbf{x}_k\in C \Rightarrow \mathbf{x}_i$ 与 $\mathbf{x}_j$ 密度相连
最大性（Maximality）： $\mathbf{x}_i\in C,\ \mathbf{x}_j$ 由 $\mathbf{x}_i$ 密度可达 $\Rightarrow \mathbf{x}_j \in C$

故DBSCAN的目标即为找出由核心对象 $\mathbf{x}$ 密度可达的所有样本组成的集合 $X=\{\mathbf{x}'\in D\mid \mathbf{x}'$ 由 $\mathbf{x}$ 密度可达 $\}$ ，易证其即为满足连接性与最大性的簇。首先从数据集中任选一个核心对象为种子（Seed），找出所有其密度可达的样本集合，形成一个密度相连的类簇，直至所有核心对象均遍历完为止。

DBSCAN算法流程如下所示：

输入：样本集 $D=\{\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_m\}$ ；邻域参数 $(\varepsilon,MinPts)$
过程：
- 初始化核心对象集合 $\Omega=\empty$
- for j=1,2,\dots,m do
  - 确定样本 $\mathbf{x}_j$ 的ε-邻域 $N_{\varepsilon}(\mathbf{x}_j)=\{\mathbf{x}_i\in D\mid \text{dist}(\mathbf{x}_i,\mathbf{x}_j)\le \varepsilon \}$
  - if |N_{\varepsilon}(\mathbf{x}_j)| \ge MinPts then
    - 将样本 $\mathbf{x}_j$ 加入核心对象集合 $\Omega \gets \Omega \cup \{\mathbf{x}_j\}$
  - end if
- end for
- 初始化聚类簇数 $k=0$
- 初始化未访问样本集合 $\Gamma=D$
- while \Gamma \ne \empty do
  - 记录当前未访问样本集合 $\Gamma_{\text{old}}=\Gamma$
  - 随机选取一个核心对象 $\mathbf{o}\in \Omega$ ，初始化队列 $Q=\left \langle \mathbf{o} \right \rangle$
  - $\Gamma \gets \Gamma \setminus \{\mathbf{o} \}$
  - while Q \ne \empty do
    - 取出队列 $Q$ 中的首个样本 $\mathbf{q}$
    - if |N_{\varepsilon}(\mathbf{q})| \ge MinPts then
      - 令 $\Delta=N_{\varepsilon}(\mathbf{q})\cap \Gamma$
      - 将 $\Delta$ 中的样本加入队列 $Q$
      - $\Gamma \gets \Gamma \setminus \Delta$
    - end if
  - end while
  - $k \gets k + 1$ ，生成聚类簇 $C_k=\Gamma_{\text{old}} \setminus \Gamma$
  - $\Omega \gets \Omega \setminus C_k$
- end while
输出：簇划分 $\mathcal{C}=\{C_1,C_2,\dots,C_k\}$

DBSCAN

5 层次聚类

层次聚类（Hierarchical Clustering）试图在不同层次对数据集进行划分，从而形成树形的聚类结构，数据集的划分可采用自底向上的聚合策略，也可采用自顶向下的分拆策略。

AGNES（Aglomerative Nesting）是一种自底向上的聚合策略，先将数据集中的每个样本看作一个初始聚类簇，然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并，该过程不断重复，直至达到预设的聚类簇个数。可见其中最关键的一步是计算聚类簇之间的距离。给定聚类簇 $C_i,C_j$ ，根据所选的距离度量方法，AGNES可分为：

单链接（Single-linkage）：取簇间最小距离 $d_{\min}(C_i,C_j)=\min\limits_{\mathbf{x}\in C_i,\mathbf{z}\in C_j}\text{dist}(\mathbf{x},\mathbf{z})$
全链接（Complete-linkage）：取簇间最大距离 $d_{\max}(C_i,C_j)=\max\limits_{\mathbf{x}\in C_i,\mathbf{z}\in C_j}\text{dist}(\mathbf{x},\mathbf{z})$
均链接（Average-linkage）：取簇间两两的平均距离 $d_{\text{avg}}(C_i,C_j)=\dfrac{1}{|C_i||C_j|}\sum\limits_{\mathbf{x}\in C_i}\sum\limits_{\mathbf{z}\in C_j} \text{dist}(\mathbf{x},\mathbf{z})$

显然，最小距离由两个簇的最近样本决定，最大距离由两个簇的最远样本决定，而平均距离则由两个簇的所有样本共同决定。

AGNES的算法流程如下所示：

输入：样本集 $D=\{\mathbf{x}_1,\mathbf{x}_2,\dots,\mathbf{x}_m\}$ ；聚类簇距离度量函数 $d$ （常选用 $d_{\min},d_{\max},d_{\text{avg}}$ 中其一）；聚类簇数 $k$
过程：
- for j=1,2,\dots,m do 初始化单样本聚类簇
  - $C_j=\{\mathbf{x}_j \}$
- end for
- for i=1,2,\dots,m do 初始化聚类簇距离矩阵
  - for j=1,2,\dots,m do
    - $M(i,j)=d(C_i,C_j)$
    - $M(j,i)=M(i,j)$
  - end for
- end for
- 设置当前聚类簇个数 $q=m$
- while q\gt k do
  - 找出距离最近的两个聚类簇 $C_{i^*},C_{j^*}\ (i^* \lt j^*)$
  - 合并两个聚类簇 $C_{i^*} \gets C_{i^*} \cup C_{j^*}$
  - for j=j^*+1,j^*+2,\dots,q do
    - 将聚类簇 $C_j$ 重编号为 $C_{j-1}$
  - end for
  - 删除距离矩阵 $M$ 的第 $j^*$ 行与第 $j^*$ 列
  - for j=1,2,\dots,q-1 do
    - $M(i^*,j)=d(C_{i^*},C_j)$
    - $M(j,i^*)=M(i^*,j)$
  - end for
  - $q \gets q-1$
- end while
输出：簇划分 $\mathcal{C}=\{C_1,C_2,\dots,C_k\}$

树状图

AGNES示意图

【拓展】实际上，每个簇就是一个样本集合。常采用豪斯多夫距离（Hausdorff Distance）作为计算同一样本空间中的集合 $X,Z$ 之间距离的通用方法，定义为：

 $\begin{aligned} \text{dist}_{\text{H}}(X,Z) =\max(\text{dist}_{\text{h}}(X,Z),\text{dist}_{\text{h}}(Z,X)) \end{aligned}$

其中

 $\begin{aligned} \text{dist}_{\text{h}} (X,Z) &= \max\limits_{\mathbf{x}\in X} \min\limits_{\mathbf{z}\in Z} \left\| \mathbf{x}-\mathbf{z} \right\|_2 \end{aligned}$

机器学习基础笔记（9）：聚类

0 聚类任务概述

1 性能度量

1.1 外部指标

1.2 内部指标

2 距离度量

3 原型聚类

3.1 k-均值

3.2 学习向量量化

3.3 高斯混合聚类

4 密度聚类

5 层次聚类

发表评论取消回复

0 聚类任务概述

1 性能度量

1.1 外部指标

1.2 内部指标

2 距离度量

3 原型聚类

3.1 k-均值

3.2 学习向量量化

3.3 高斯混合聚类

4 密度聚类

5 层次聚类

发表评论 取消回复

发表评论取消回复