聚类分析

介绍

在无监督学习中，训练样本的标记信息是未知的，目标是通过对无标记训练样本的学习来揭示数据的内在性质及规律，为进一步的数据分析提供基础。此类学习任务中研究最多、应用最广的是“聚类”（clustering）。

常见的无监督学习任务还有密度估计、异常检测等。

聚类试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集称作一个“簇”。

形式化地，假定样本集 $D = \left\{\boldsymbol{x}_1,\boldsymbol{x}_2, \dots,\boldsymbol{x}_m\right\}$ 包含 $m$ 个无标记样本，每个样本 $\boldsymbol{x}_i = \left(x_{i1};x_{i2};\dots;x_{in}\right)$ 是一个 $n$ 维特征向量，则聚类算法将样本集 $D$ 划分为若干个不相交的簇 $\left\{C_l \mid l = 1, 2, \dots, k\right\}$，其中 $C_{l'} \bigcap_{l' \neq l} C_l = \varnothing$ 且 $D = \bigcup_{l=1}^{k}{C_l}$。

令 $\lambda_j \in \left\{1, 2,\dots, k\right\}$ 表示样本 $\mathbf{x}_j$ 的簇标记，即 $\mathbf{x}_j \in \lambda_j$，则聚类的结果可用包含 $m$ 个元素的簇标记向量 $\vec\lambda = \left(\lambda_1; \lambda_2;\dots;\lambda_k\right)$ 表示。

对于聚类的结果，我们希望“簇内相似度”高，而“簇间相似度”低。下面是一些常用的聚类性能度量的内部指标：

• DB 指数：

$$\operatorname{DBI} = \dfrac 1k \sum\limits_{i=1}^k{\max_{j \neq i}\left(\dfrac{\operatorname{avg}(C_i) + \operatorname{avg}(C_j)}{d_{\text{cen}}(\mu_i, \mu_j)}\right)}$$

• Dunn 指数：

$$\operatorname{DI} = \min_{1 \leq i \leq k}\left\{\min_{j \neq i}\left(\dfrac{d_{\min}(C_i, C_j)}{\max\limits_{1 \leq l \leq k}\operatorname{diam}(C_l)}\right)\right\}$$

其中，$\operatorname{avg}(C)$ 表示簇 $C$ 内样本间的平均距离，$\operatorname{diam}(C)$ 表示簇 $C$ 内样本间的最远距离，$d_{\min}(C_i, C_j)$ 表示簇 $C_i$ 和 $C_j$ 最近样本间的距离，$d_{\text{cen}}(C_i, C_j)$ 表示簇 $C_i$ 和 $C_j$ 中心点间的距离，$\mu_i$ 表示簇 $C$ 的中心点，上述所有量下述公式得到：

$$\begin{aligned} \mu &= \dfrac 1{|C|}\sum\limits_{1 \leq i \leq |C|} \boldsymbol{x}_i \\ \operatorname{avg}(C) &= \dfrac{2}{|C|(|C|-1)} \sum\limits_{1 \leq i < j \leq |C|} \operatorname{dist}(\boldsymbol{x}_i, \boldsymbol{x}_j) \\ \operatorname{diam}(C) &= \max_{1 \leq i < j \leq |C|} \operatorname{dist}(\boldsymbol{x}_i, \boldsymbol{x}_j) \\ d_{\min}(C_i, C_j) &= \min_{\boldsymbol{x}_i \in C_i, \boldsymbol{x}_j \in C_j} \operatorname{dist}(\boldsymbol{x}_i, \boldsymbol{x}_j) \\ d_{\text{cen}}(C_i, C_j) &= \operatorname{dist}(\mu_i, \mu_j) \end{aligned}$$

从上述公式中我们可以发现，寻找一个计算距离的函数 $\operatorname{dist}(\cdot, \cdot)$ 是十分必要的。

距离测量

给定样本 $\boldsymbol{x}_i = \left(x_{i1};x_{i2};\dots;x_{in}\right)$ 和 $\boldsymbol{x}_j = \left(x_{j1};x_{j2};\dots;x_{jn}\right)$，衡量距离时最常用的是“闵可夫斯基距离”：

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

同时，上式即为 $\boldsymbol{x}_i - \boldsymbol{x}_j$ 的 $\boldsymbol{L}_p$ 范数 $||\boldsymbol{x}_i - \boldsymbol{x}_j||_p$。

当 $p = 1$ 时，闵可夫斯基距离即为曼哈顿距离

$$\operatorname{dist}_{\text {man }}\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|_{1}=\sum_{u=1}^{n}\left|x_{i u}-x_{j u}\right|$$

当 $p = 2$ 时，闵可夫斯基距离即为欧几里得距离

$$\operatorname{dist}_{\mathrm{ed}}\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|_{2}=\sqrt{\sum_{u=1}^{n}\left|x_{i u}-x_{j u}\right|^{2}}$$

原型聚类

原型聚类亦称为“基于原型的聚类”，此类算法假设聚类结构能通过一组原型刻画，在现实聚类任务中极为常用。通常情况下，算法先对原型进行初始化，再对原型进行迭代更新求解。

Kmeans 算法

给定样本集 $D = \left\{\boldsymbol{x}_1, \boldsymbol{x}_2, \dots, \boldsymbol{x}_m\right\}$，Kmeans 算法针对聚类所得簇划分 $\mathcal{C} = \left\{C_1, C_2, \dots, C_k\right\}$ 最小化平方误差

$$E = \sum\limits_{i=1}^k{\sum\limits_{\boldsymbol{x} \in C_i} ||\boldsymbol{x} - \mu_i||_2^2}$$

其中 $\mu_i = \frac 1{|C_i|}\sum_{\boldsymbol{x} \in C_i} \boldsymbol{x}$ 是簇 $C_i$ 的均值向量。$E$ 值在一定程度上刻画了簇内样本围绕簇均值向量的紧密程度，$E$ 值越小，则簇内样本相似度越高。

密度聚类

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

DBSCAN 算法

DBSCAN 算法是一种著名的密度聚类算法，它基于一组“邻域”参数 $(\epsilon, MinPts)$ 来刻画样本分布的紧密程度。

给定数据集 $D = \left\{\boldsymbol{x}_1, \boldsymbol{x}_2, \dots, \boldsymbol{x}_m\right\}$，定义下面几个概念：

• $\epsilon$-邻域：对 $\boldsymbol{x}_j \in D$，其 $\epsilon$-邻域包含样本集 $D$ 中与 $\boldsymbol{x}_j$ 的距离不大于 $\epsilon$ 的样本，即 $N_{\epsilon}\left(\boldsymbol{x}_{j}\right)=\left\{\boldsymbol{x}_{i} \in D \mid \operatorname{dist}\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \leqslant \epsilon\right\}$；
• 核心对象：若 $\boldsymbol{x}_j$ 的 $\epsilon$-邻域至少包含 $MinPts$ 个样本，即 $\left|N_\epsilon(\boldsymbol{x}_j)\right| \geq MinPts$，则 $\boldsymbol{x}_j$ 是一个核心对象；
• 密度直达：若 $\boldsymbol{x}_j$ 在 $\boldsymbol{x}_i$ 的 $\epsilon$-邻域中，且 $\boldsymbol{x}_i$ 是核心对象，则称 $\boldsymbol{x}_j$ 由 $\boldsymbol{x}_i$ 密度直达；
• 密度可达：对 $\boldsymbol{x}_i$ 与 $\boldsymbol{x}_j$，若存在样本序列 $\boldsymbol{p}_1, \boldsymbol{p}_2, \dots, \boldsymbol{p}_n$，其中 $\boldsymbol{p}_1 = \boldsymbol{x}_i$，$\boldsymbol{p}_n = \boldsymbol{x}_j$ 且 $\boldsymbol{p}_{i+1}$ 由 $\boldsymbol{p}_i$ 密度直达，则称 $\boldsymbol{x}_j$ 由 $\boldsymbol{x}_i$ 密度可达；
• 密度相连：对 $\boldsymbol{x}_i$ 和 $\boldsymbol{x}_j$，若存在 $\boldsymbol{x}_k$ 使得 $\boldsymbol{x}_i$ 与 $\boldsymbol{x}_j$ 均由 $\boldsymbol{x}_k$ 密度可达，则称 $\boldsymbol{x}_i$ 与 $\boldsymbol{x}_j$ 密度相连。

DBSCAN 将“簇”定义为：有密度可达关系导出的最大的密度相连样本集合。

形式化地，给定邻域参数 $(\epsilon, MinPts)$，簇 $C \subseteq D$ 是满足以下性质的非空样本子集：

• 连接性：$\boldsymbol{x}_i \in C$，$\boldsymbol{x}_j \in C \Longrightarrow$ $\boldsymbol{x}_i$ 和 $\boldsymbol{x}_j$ 密度相连
• 最大性：$\boldsymbol{x}_i \in C$，$\boldsymbol{x}_j$ 由 $\boldsymbol{x}_i$ 密度可达 $\Longrightarrow$ $\boldsymbol{x}_j \in C$

实际上，若 $\boldsymbol{x}$ 为核心对象，则 $\boldsymbol{x}$ 密度可达的所有样本的集合记为 $X = \left\{\boldsymbol{x}' \in D \mid \boldsymbol{x}' \text{由}\boldsymbol{x}\text{密度可达}\right\}$，则 $X$ 即为满足连接性和最大性的簇。

1-7 行中，算法先根据给定的邻域参数找出所有核心对象；10-24 行中，以任一核心对象为出发点，找出由其密度可达的样本生成聚类簇，直到所有核心对象均被访问过为止。

层次聚类

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

AGNES 算法

AGNES 算法是一种采取自底向上聚合策略的层次聚类算法。

首先，将样本中的每一个样本看做一个初始聚类簇，然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并，该过程不断重复，直到达到预设的聚类簇的个数。

两个聚类簇 $C_i$ 和 $C_j$ 之间的距离可通过下面的公式得到：

• 最小距离：$d_{\min}(C_i, C_j) = \min\limits_{\boldsymbol{x} \in C_i, \boldsymbol{z} \in C_j} \operatorname{dist}(\boldsymbol{x}, \boldsymbol{z})$；
• 最大距离：$d_{\max}(C_i, C_j) = \max\limits_{\boldsymbol{x} \in C_i, \boldsymbol{z} \in C_j} \operatorname{dist}(\boldsymbol{x}, \boldsymbol{z})$；
• 平均距离：$\displaystyle d_{\text {avg}}\left(C_{i}, C_{j}\right)=\frac{1}{\left|C_{i}\right|\left|C_{j}\right|} \sum_{\boldsymbol{x} \in C_{i}} \sum_{\boldsymbol{z} \in C_{j}} \operatorname{dist}(\boldsymbol{x}, \boldsymbol{z})$。

当聚类簇距离由 $d_{\min}$，$d_{\max}$ 或 $d_{\text{avg}}$ 计算时，AGNES 算法被相应地称为“单链接”、“全链接”或“均链接”算法。

1-9 行，算法先对仅含一个样本的初始聚类簇和相应的距离矩阵进行初始化；11-23 行，AGNES 不断合并距离最近的聚类簇，并对合并得到的距离矩阵进行更新；上述过程不断重复，直到达到预设的聚类簇数。

ps: 这个 $\mathcal{O}(n^2)$ 的算法过于朴素…是否存在优化？