聚类

聚类任务

「无监督学习」学习任务中，聚类（clustering）是研究最多、应用最广的。

「聚类」对应有监督学习中的「分类」任务。无监督学习任务还有「密度估计」，对应有监督学习中的「回归」任务。

聚类是将数据集中的样本划分为若干个不相交的子集，每个子集称为一个簇（cluster）。簇内的样本尽可能相似，而簇间的样本尽可能不同。

形式化地描述，假定样本集 $D = \left\lbrace \bm{x}_i \right\rbrace_{i=1}^m$ 包含 $m$ 个样本，每个样本 $\bm{x}_i = \left( x_{i1}; x_{i2}; \cdots; x_{in} \right)$ 是一个 $n$ 维特征向量。聚类算法将 $D$ 划分为 $k$ 个不相交的簇 $\left\lbrace C_l \right\rbrace_{l=1}^k$，其中 $C_l$ 是第 $l$ 个簇，$C_l \cap_{l \ne l'} C_{l'} = \empty$，且 $D = \bigcup_{l=1}^k C_l$。

相应地，用 $\lambda_{j} \in \left\lbrace 1, 2, \cdots, k \right\rbrace$ 表示样本 $\bm{x}_j$ 的簇标记，即 $\bm{x}_j \in C_{\lambda_j}$。于是聚类的结果可用包含 $m$ 个元素的簇标记向量 $\bm{\lambda} = \left( \lambda_1; \lambda_2; \cdots; \lambda_m \right)$ 表示。

性能度量

「聚类性能度量」，亦称聚类「有效性指标」（validity index），与监督学习中的性能度量作用相似。

直观上我们想要「物以类聚」，即同一簇的样本尽可能相似，不同簇的样本尽可能不同。换言之，聚类结果的「簇内相似度」（intra-cluster similarity）应高，而「簇间相似度」（inter-cluster similarity）应低。

聚类性能度量大致有两类：

• 外部指标：将聚类结果与某个「参考模型」（ground truth）进行比较
  • 如 Jaccard 系数、FM 指数、Rand 指数等。
• 内部指标：直接考察聚类结果而不利用任何参考模型，
  • 如 DB 指数、Dunn 指数等。

外部指标

对数据集 $D = \left\lbrace \bm{x}_i \right\rbrace_{i=1}^m$，假定通过聚类得到的簇划分为 $\mathcal{C} = \left\lbrace C_1, \cdots, C_k \right\rbrace$，参考模型给出的簇划分为 $\mathcal{C}^* = \left\lbrace C_1^*, \cdots, C_s^* \right\rbrace$。相应地，令 $\bm{\lambda}, \bm{\lambda}^*$ 分别表示聚类结果和参考模型给出的簇标记向量。

我们将样本两两配对考虑，定义

$$\left\lbrace\begin{aligned} a &= |SS|,\quad SS = \left\lbrace (\bm{x}_i, \bm{x}_j) \mid \lambda_i = \lambda_j, \lambda_i^* = \lambda_j^* , i < j\right\rbrace,\\ b &= |SD|,\quad SD = \left\lbrace (\bm{x}_i, \bm{x}_j) \mid \lambda_i = \lambda_j, \lambda_i^* \ne \lambda_j^* , i < j\right\rbrace,\\ c &= |DS|,\quad DS = \left\lbrace (\bm{x}_i, \bm{x}_j) \mid \lambda_i \ne \lambda_j, \lambda_i^* = \lambda_j^* , i < j\right\rbrace,\\ d &= |DD|,\quad DD = \left\lbrace (\bm{x}_i, \bm{x}_j) \mid \lambda_i \ne \lambda_j, \lambda_i^* \ne \lambda_j^* , i < j\right\rbrace. \end{aligned}\right.$$

$S$ 即在「相同」（same）簇中，$D$ 即在「不同」（different）簇中。

基于上面，可导出常用的聚类性能度量外部指标：

• Jaccard 系数（Jaccard coefficient, JC）：

  $$\mathrm{JC} = \frac{a}{a+b+c}$$

• FM 指数（Fowlkes and Mallows index, FMI）：

  $$\mathrm{FMI} = \sqrt{\frac{a}{a+b} \cdot \frac{a}{a+c}}$$

• Rand 指数（Rand index, RI）：

  $$\mathrm{RI} = \dfrac{a+d}{\binom{m}{2}} = \dfrac{2(a+d)}{m(m-1)}$$

这些指标的取值范围都是 $[0, 1]$，值越大表示聚类结果与参考模型越吻合。

内部指标

考虑聚类结果的簇划分 $\mathcal{C} = \left\lbrace C_1, \cdots, C_k \right\rbrace$，定义

$$\left\lbrace\begin{aligned} \operatorname{avg}(C) &= \dfrac{1}{\binom{|C|}{2}} \sum_{1 \le i < j \le |C|} \operatorname{dist}(\bm{x}_i, \bm{x}_j),\\ \operatorname{diam}(C) &= \max_{1 \le i, j \le |C|} \operatorname{dist}(\bm{x}_i, \bm{x}_j),\\ d_{\min}(C_i, C_j) &= \min_{\bm{x}_i \in C_i, \bm{x}_j \in C_j} \operatorname{dist}(\bm{x}_i, \bm{x}_j),\\ d_{\mathrm{cen}}(C_i, C_j) &= \operatorname{dist}(\bm{\mu}_i, \bm{\mu}_j). \end{aligned}\right.$$

• $\operatorname{avg}(C)$：簇 $C$ 中样本间的平均距离
• $\operatorname{diam}(C)$：簇 $C$ 中样本间的最远距离
• $d_{\min}(C_i, C_j)$：簇 $C_i$ 和 $C_j$ 最近样本间的距离
• $d_{\mathrm{cen}}(C_i, C_j)$：簇 $C_i$ 和 $C_j$ 中心点的距离

基于上面，可导出常用的聚类性能度量内部指标：

• DB 指数（Davies-Bouldin index, DBI）：

  $$\mathrm{DBI} = \dfrac{1}{k} \sum_{i=1}^k \max_{j \ne i} \left( \dfrac{\operatorname{avg}(C_i) + \operatorname{avg}(C_j)}{d_{\mathrm{cen}}(C_i, C_j)} \right)$$

  • DBI 越小越好
• Dunn 指数（Dunn index, DI）：

  $$\mathrm{DI} = \min_{1 \le i \le k} \left\lbrace \min_{j \ne i} \left( \dfrac{d_{\min}(C_i, C_j)}{\max\limits_{1\le l\le k} \operatorname{diam}(C_l)} \right) \right\rbrace$$

  • DI 越大越好

距离计算

函数 $\operatorname{dist}$ 作为一个「距离度量」（distance measure），需满足一些基本性质：

• 非负性：$\operatorname{dist}(\bm{x}_i, \bm{x}_j) \ge 0$
• 同一性：$\operatorname{dist}(\bm{x}_i, \bm{x}_j) = 0 \iff \bm{x}_i = \bm{x}_j$
• 对称性：$\operatorname{dist}(\bm{x}_i, \bm{x}_j) = \operatorname{dist}(\bm{x}_j, \bm{x}_i)$
• 直递性：$\operatorname{dist}(\bm{x}_i, \bm{x}_j) \le \operatorname{dist}(\bm{x}_i, \bm{x}_k) + \operatorname{dist}(\bm{x}_k, \bm{x}_j)$

给定样本 $\bm{x}_i = (x_{i1}; \cdots; x_{in}),\, \bm{x}_j = (x_{j1}; \cdots; x_{jn})$，最常用的是闵可夫斯基距离（Minkowski distance）：

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

其中 $p \ge 1$ 为「距离的阶」（order of distance）。

也可以写为 $\bm{x}_i - \bm{x}_{j}$ 的 $\mathrm{L}_p$ 范数，记为 $\left\lVert \bm{x}_i - \bm{x}_{j} \right\rVert_p$。

特别地，有

• 欧氏距离（Euclidean distance）：$p=2$

  $$\operatorname{dist}_{\mathrm{eu}}(\bm{x}_i, \bm{x}_j) = \left\lVert \bm{x}_i - \bm{x}_{j} \right\rVert_2 = \sqrt{\sum_{u=1}^n (x_{iu} - x_{ju})^2}$$

• 曼哈顿距离（Manhattan distance）：$p=1$

  $$\operatorname{dist}_{\mathrm{ma}}(\bm{x}_i, \bm{x}_j) = \left\lVert \bm{x}_i - \bm{x}_{j} \right\rVert_1 = \sum_{u=1}^n |x_{iu} - x_{ju}|$$

• 切比雪夫距离（Chebyshev distance）：$p=\infty$

  $$\operatorname{dist}_{\mathrm{ch}}(\bm{x}_i, \bm{x}_j) = \left\lVert \bm{x}_i - \bm{x}_{j} \right\rVert_\infty = \max_{1 \le u \le n} |x_{iu} - x_{ju}|$$

属性介绍：

• 连续属性（continuous attribute）：在定义域上有无穷多个可能的取值
• 离散属性（discrete attribute）：在定义域上有有限个可能的取值
• 有序属性（ordinal attribute）：在定义域上有序关系
  • 如定义域为 $\left\lbrace 1, 2, 3 \right\rbrace$ 的离散属性
• 无序属性（non-ordinal attribute）：在定义域上无序关系
  • 如定义域为 $\left\lbrace \text{red}, \text{green}, \text{blue} \right\rbrace$ 的离散属性
  • 不能直接在属性值上进行计算

对于无序属性，可使用 VDM(Value Difference Metrix)。

令 $m_{u, a}$ 表示在属性 $u$ 上取值为 $a$ 的样本数，$m_{u, a, i}$ 表示在第 $i$ 个样本簇中在属性 $u$ 上取值为 $a$ 的样本数，$k$ 为样本簇数，则属性 $u$ 上两个离散值 $a, b$ 之间的 VDM 距离为

$$\operatorname{VDM}_p(a, b) = \sum_{i=1}^k \left| \dfrac{m_{u, a, i}}{m_{u, a}} - \dfrac{m_{u, b, i}}{m_{u, b}} \right|^p$$

对于混合属性，可将闵可夫斯基距离和 VDM 结合得到 MinkovDM。

假定有 $n_c$ 个有序属性，$n - n_c$ 个无序属性，不失一般性，令有序属性排序在无序属性之前，有

$$\operatorname{MinkovDM}_p(\bm{x}_i, \bm{x}_{j}) = \left( \sum_{u=1}^{n_c} \left| x_{iu} - x_{ju} \right|^p + \sum_{u=n_c+1}^{n} \operatorname{VDM}_p(x_{iu}, x_{ju}) \right)^{\frac{1}{p}}$$

当样本空间中不同属性的重要性不同时，也可以使用「加权距离」（weighted distance），例如加权闵可夫斯基距离

$$\operatorname{dist}_{\mathrm{wmk}}(\bm{x}_i, \bm{x}_j) = \left( \sum_{u=1}^n w_u |x_{iu} - x_{ju}|^p \right)^{\frac{1}{p}}$$

其中 $w_u \ge 0$ 为第 $u$ 个属性的权重，通常 $\displaystyle \sum_{u=1}^n w_u = 1$。

通常我们是基于某种形式的距离来定义「相似度度量」（similarity measure），距离越大，相似度越小。然而用于相似度度量的距离未必满足距离度量的所有基本性质（尤其是直递性）。这样的距离称为「非度量距离」（non-metric distance）。

聚类的「好坏」不存在绝对标准。

老师拿来苹果和梨，让小朋友分成两份。
小明把大苹果大梨放一起，小个头的放一起，老师点头，恩，体量感。
小芳把红苹果挑出来，剩下的放一起，老师点头，颜色感。
小武的结果？不明白。小武掏出眼镜：最新款，能看到水果里有几个籽，左边这堆单数，右边双数。
老师很高兴：新的聚类算法诞生了。

常见的聚类方法：

• 原型聚类，亦称为「基于原型的聚类」（prototype-based clustering）
  • 假设：聚类结构能通过一组原型刻画
  • 过程：先对原型初始化，然后对原型进行迭代更新求解
  • 代表：$k$ 均值聚类，学习向量量化（LVQ），高斯混合聚类
• 密度聚类，亦称「基于密度的聚类」（density-based clustering）
  • 假设：聚类结构能通过样本分布的紧密程度确定
  • 过程：从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇
  • 代表：DBSCAN, OPTICS, DENCLUE
• 层次聚类（hierarchical clustering）
  • 假设：能够产生不同粒度的聚类结果
  • 过程：在不同层次对数据集进行划分，从而形成树形的聚类结构
  • 代表：AGNES（自底向上），DIANA （自顶向下）

原型聚类

$k$ 均值算法

给定样本集 $D = \left\lbrace \bm{x}_i \right\rbrace_{i=1}^m$，「$k$ 均值」（$k$-means）算法针对聚类所得簇划分 $\mathcal{C} = \left\lbrace C_1, \cdots, C_k \right\rbrace$ 最小化平方误差

$$E = \sum_{i=1}^{k} \sum_{\bm{x} \in C_i} \left\lVert \bm{x} - \bm{\mu}_i \right\rVert_2^2$$

其中 $\bm{\mu}_i = \displaystyle \dfrac{1}{|C_i|} \sum_{\bm{x} \in C_i} \bm{x}$ 为簇 $C_i$ 的均值向量。

$E$ 在一定程度上刻画了簇内样本围绕簇均值向量的紧密程度，$E$ 值越小则簇内样本相似度越高。

最小化 $E$ 的过程，找到它的最优解需考察样本集 $D$ 所有可能的簇划分，是一个 NP 难问题。

$k$ 均值算法采用贪心策略，通过迭代优化来近似求解最优化问题。流程如下图所示：

算法流程：

1. 第 1 行对均值向量进行初始化
2. 第 4 ~ 8 行与第 9 ~ 16 行依次对当前簇划分及均值向量迭代更新
3. 若迭代更新后聚类结果保持不变，则在第 18 行将当前簇划分结果返回
4. 否则继续迭代更新

一些在线模拟网站：

• K-Means Clustering Demo
• Visualizing K-Means Clustering

学习向量量化

学习向量量化（Learning Vector Quantization, LVQ）是一种原型聚类算法，与一般聚类算法不同的是，LVQ 假设数据样本带有类别标记，学习过程中利用样本的这些监督信息来辅助聚类。

给定样本集 $D = \left\lbrace (\bm{x}_i, y_i) \right\rbrace_{i=1}^m$，每个样本 $\bm{x}_{j}$ 是由 $n$ 个属性描述的特征向量 $\bm{x}_j = (x_{j1}; x_{j2}; \cdots; x_{jd})$，$y_{j} \in \mathcal{Y}$ 是样本 $\bm{x}_{j}$ 的类别标记。

LVQ 的目标是学得一组 $n$ 维原型向量 $\left\lbrace \bm{p}_1, \dots, \bm{p}_q \right\rbrace$，每个原型向量代表一个聚类簇，簇标记 $t_i \in \mathcal{Y}$。

LVQ 算法流程如下图所示：

算法流程：

1. 第 1 行先对原型向量进行初始化
   • 例如对第 $q$ 个簇，可从类别标记为 $t_q$ 的样本中随机抽取一个作为原型向量
2. 第 2 ~ 12 行对原型向量进行迭代优化：每一轮迭代中，算法随机选取一个有标记的训练样本，找出与其距离最近的原型向量，并根据两者的类别标记是否一致来对原型向量进行相应的更新
3. 第 12 行中，若算法的停止条件已满足（例如已达到最大迭代轮数，或原型向量更新很小甚至不再更新），则将当前原型向量作为最终结果返回

LVQ 的关键在于第 6 ~ 10 行，即如何更新原型向量。【暂略】

高斯混合聚类

高斯混合聚类（Gaussian Mixture Model, GMM）是一种基于概率模型的聚类方法，它假设数据是由多个高斯分布混合而成的。

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

$$p(\bm{x}) = \dfrac{1}{(2\pi)^{\frac{n}{2}} |\bm{\Sigma}|^{\frac{1}{2}}} \exp \left( -\dfrac{1}{2} (\bm{x} - \bm{\mu})^\intercal \bm{\Sigma}^{-1} (\bm{x} - \bm{\mu}) \right)$$

其中 $\bm{\mu}$ 是 $n$ 维均值向量，$\bm{\Sigma}$ 是 $n \times n$ 的协方差矩阵。

高斯分布完全由均值向量 $\bm{\mu}$ 和协方差矩阵 $\bm{\Sigma}$ 确定，为了明确这个依赖关系，概率密度函数记为 $p(\bm{x} \mid \bm{\mu}, \bm{\Sigma})$。

可以定义「高斯混合分布」

$$p_{\mathcal{M}} = \sum_{i=1}^{k} \alpha_i \cdot p(\bm{x} \mid \bm{\mu}_i, \bm{\Sigma}_i)$$

该分布由 $k$ 个混合成分组成，每个混合成分对应一个高斯分布。$\alpha_i > 0$ 为相应的「混合系数」（mixture coefficient），满足 $\displaystyle \sum_{i=1}^{k} \alpha_i = 1$。

假设样本的生成过程由高斯混合分布给出：首先根据 $\alpha_1, \cdots, \alpha_k$ 定义的先验分布选择高斯混合成分，其中 $\alpha_i$ 为选择第 $i$ 个混合成分的概率；然后根据被选择的混合成分的概率密度函数进行采样，从而生成相应的样本。

若训练集 $D = \left\lbrace \bm{x}_i \right\rbrace_{i=1}^m$ 由上述过程生成，令随机变量 $z_{j} \in \left\lbrace 1, \cdots, k \right\rbrace$ 表示生成样本 $\bm{x}_{j}$ 的高斯混合成分，其取值未知。则 $z_{j}$ 的先验概率 $P(z_{j} = i)$ 对应于 $\alpha_i$。根据贝叶斯定理，$z_{j}$ 的后验分布对应于

$$\begin{aligned} p_{\mathcal{M}}(z_{j} = i \mid \bm{x}_{j}) &= \dfrac{P(z_{j} i) \cdot p_{\mathcal{M}}(\bm{x}_{j} \mid z_{j} = i)}{p_{\mathcal{M}}(\bm{x}_{j})} \\ &= \dfrac{\alpha_i \cdot p(\bm{x}_{j} \mid \bm{\mu}_i, \bm{\Sigma}_i)}{\sum\limits_{l=1}^{k} \alpha_l \cdot p(\bm{x}_{j} \mid \bm{\mu}_l, \bm{\Sigma}_l)} \end{aligned}$$

简记为 $\gamma_{ji}$。

换言之，$p_{\mathcal{M}}(z_{j} = i \mid \bm{x}_{j})$ 给出了样本 $\bm{x}_j$ 由第 $i$ 个高斯混合成分生成的后验概率。

当高斯混合分布已知时，高斯混合聚类将把样本集 $D$ 划分为 $k$ 个簇，每个样本 $\bm{x}_{j}$ 的簇标记 $\lambda_{j}$ 如下确定：

$$\lambda_{j} = \argmax_{i \in \left\lbrace 1, \cdots, k \right\rbrace} \gamma_{ji}$$

从原型聚类的角度上看，高斯混合聚类是采用概率模型（高斯分布）对原型进行刻画，簇划分则由原型对应的后验概率确定。

模型参数 $\left\lbrace (\alpha_i, \bm{\mu}_i, \bm{\Sigma}_i) \mid 1 \le i \le k \right\rbrace$ 可以通过极大似然法进行估计，考虑最大化对数似然

$$\begin{aligned} LL(D) &= \ln \left( \prod_{j=1}^{m} p_{\mathcal{M}}(\bm{x}_{j}) \right) \\ &= \sum_{j=1}^{m} \ln \left( \sum_{i=1}^{k} \alpha_i \cdot p(\bm{x}_{j} \mid \bm{\mu}_i, \bm{\Sigma}_i) \right) \end{aligned}$$

常采用 EM 算法进行迭代优化求解：

• E 步：根据当前参数计算每个样本属于每个高斯成分的后验概率
• M 步：更新模型参数

令 $\dfrac{\partial LL(D)}{\partial \bm{\mu}_i}, \dfrac{\partial LL(D)}{\partial \bm{\Sigma}_i} = 0$，以及拉格朗日乘子法得

$$\left\lbrace\begin{aligned} \bm{\mu}_i &= \dfrac{\sum_{j=1}^{m} \gamma_{ji} \bm{x}_{j}}{\sum_{j=1}^{m} \gamma_{ji}},\\ \bm{\Sigma}_i &= \dfrac{\sum_{j=1}^{m} \gamma_{ji} (\bm{x}_{j} - \bm{\mu}_i) (\bm{x}_{j} - \bm{\mu}_i)^\intercal}{\sum_{j=1}^{m} \gamma_{ji}},\\ \alpha_i &= \dfrac{1}{m} \sum_{j=1}^{m} \gamma_{ji}. \end{aligned}\right.$$

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

密度聚类

使用 $k$ 均值方法对下图数据进行聚类，基于原型的聚类方法难以发掘到密度连接的信息，导致聚类结果同直观差异较大：

基于密度的聚类方法：从样本密度的角度考察样本的连接性，使密度相连的样本归结到一个簇，更符合直观认知：

密度聚类也称为「基于密度的聚类」（density-based clustering）。

此类算法假设聚类结构能通过样本分布的紧密程度来确定。

通常情况下，密度聚类算法从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇来获得最终的聚类结果。

DBSCAN 算法

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是一种典型的密度聚类算法，它基于一组「邻域」（neighborhood）参数 $(\epsilon, \mathrm{MinPts})$ 来刻画样本分布的紧密程度。

给定数据集 $D = \left\lbrace \bm{x}_i \right\rbrace_{i=1}^m$，定义：

• $\epsilon$-邻域：对 $\bm{x}_{j} \in D$，其 $\epsilon$-邻域包含样本集 $D$ 中与 $\bm{x}_{j}$ 的距离不大于 $\epsilon$ 的样本，即 $N_{\epsilon}(\bm{x}_{j}) = \left\lbrace \bm{x}_i \in D \mid \operatorname{dist}(\bm{x}_i, \bm{x}_{j}) \le \epsilon \right\rbrace$；
• 核心对象（core object）：若 $\bm{x}_{j}$ 的 $\epsilon$-邻域至少包含 $\mathrm{MinPts}$ 个样本，即 $|N_{\epsilon}(\bm{x}_{j})| \ge \mathrm{MinPts}$，则 $\bm{x}_{j}$ 是一个核心对象；
• 密度直达（density-reachable）：若 $\bm{x}_{j}$ 在 $\bm{x}_{i}$ 的 $\epsilon$-邻域中，且 $\bm{x}_{i}$ 是核心对象，则称 $\bm{x}_{j}$ 由 $\bm{x}_{i}$ 密度直达；
• 密度可达（density-reachable）：对 $\bm{x}_{i}$ 和 $\bm{x}_{j}$，若存在样本序列 $\left\lbrace \bm{p}_1, \cdots, \bm{p}_n \right\rbrace$，其中 $\bm{p}_1 = \bm{x}_{i}, \bm{p}_n = \bm{x}_{j}$，且 $\bm{p}_{u+1}$ 由 $\bm{p}_u$ 密度直达，则称 $\bm{x}_{j}$ 由 $\bm{x}_{i}$ 密度可达；
• 密度相连（density-connected）：对 $\bm{x}_{i}$ 和 $\bm{x}_{j}$，若存在 $\bm{x}_{k}$ 使 $\bm{x}_{i}$ 和 $\bm{x}_{j}$ 均由 $\bm{x}_{k}$ 密度可达，则称 $\bm{x}_{i}$ 和 $\bm{x}_{j}$ 密度相连。

直观显示：

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

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

• 连接性（connectivity）：$\bm{x}_i, \bm{x}_{j} \in C$ 能推出 $\bm{x}_i$ 和 $\bm{x}_{j}$ 密度相连；
• 最大性（maximality）：$\bm{x}_i \in C$ 与 $\bm{x}_{j}$ 由 $\bm{x}_{i}$ 密度可达能推出 $\bm{x}_{j} \in C$。

如何找出满足以上性质的聚类簇？实际上，若 $\bm{x}$ 为核心对象，，由 $\bm{x}$ 密度可达的所有样本组成的集合 $X = \left\lbrace \bm{x}' \in D \mid \bm{x}' \text{ 由 } \bm{x} \text{ 密度可达} \right\rbrace$ 即为满足连接性和最大性的簇。

DBSCAN 算法流程如下图所示：

算法流程：

1. 先任选数据集中的一个核心对象为「种子」（seed），再由此出发确定相应的聚类簇
2. 第 1 ~ 7 行中，算法根据给定的邻域参数找出所有核心对象
3. 第 10 ~ 24 行中，以任意核心对象为出发点，找出由其密度可达的样本生成聚类簇，直到所有核心对象均被访问过为止

在线模拟网站：Visualizing DBSCAN Clustering

层次聚类

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

AGNES 算法

AGNES (Agglomerative Nesting) 是一种采用自底向上聚合策略的层次聚类算法.它先将数据集中的每个样本看作一个初始聚类簇，然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并，该过程不断重复,直至达到预设的聚类簇个数。

这里的关键在于如何计算聚类簇之间的距离。因为每个簇实际上是一个样本集合，因此只需要采用关于集合的某种距离即可。

例如给定聚类簇 $C_i, C_{j}$，可通过以下式子计算距离：

• 最小距离 $d_{\min}(C_i, C_j) = \displaystyle \min_{\bm{x}_i \in C_i, \bm{x}_j \in C_j} \operatorname{dist}(\bm{x}_i, \bm{x}_j)$
• 最大距离 $d_{\max}(C_i, C_j) = \displaystyle \max_{\bm{x}_i \in C_i, \bm{x}_j \in C_j} \operatorname{dist}(\bm{x}_i, \bm{x}_j)$
• 平均距离 $\displaystyle \operatorname{avg}(C_i, C_j) = \dfrac{1}{|C_i| \cdot |C_j|} \sum_{\bm{x}_i \in C_i} \sum_{\bm{x}_j \in C_j} \operatorname{dist}(\bm{x}_i, \bm{x}_j)$

当聚类簇距离由以上三种距离之一确定时，AGNES 算法被相应地称为：

• 单链接（single-linkage）：$d(C_i, C_j) = d_{\min}(C_i, C_j)$
• 全链接（complete-linkage）：$d(C_i, C_j) = d_{\max}(C_i, C_j)$
• 均链接（average-linkage）：$d(C_i, C_j) = \operatorname{avg}(C_i, C_j)$

AGNES 算法流程如下图所示：

算法流程：

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