聚类

1. 聚类任务

在无监督学习中，训练样本的标记信息是未知的，目标是通过对无标记训练样本的学习来揭示数据的内在性质和规律，为进一步的数据分析提供基础。此类学习任务中研究最多、应用最广的就是聚类。
聚类试图将数据集中的样本划分为若干个通常是不相交的子集，每个子集称为一个“簇”，通过这样的划分，每个簇可能对应于一些潜在的概念（类别）。这些概念对于聚类算法而言是事先未知的，聚类过程仅能自动形成簇结构，簇所对应的概念也需要使用者自己把握。
聚类能作为一个单独的过程，用于寻找数据内在的分布结构，也可作为分类等其他学习任务的前驱过程。例如在一些商业应用中需要对新用户的类型进行判别，但定义“用户类型”对商家来说不太容易，此时往往可先对用户数据进行聚类，根据聚类结果将每个簇定义为一个类，然后再基于这些类训练分类模型，用与判别新用户的类型。

2. 性能度量

聚类的性能度量也成为聚类的有效性指标，对于聚类结果，我们需要通过某种性能度量来评估其好坏；另一方面，若明确了最终将要使用的性能度量，则可直接将其作为聚类过程的优化目标，从而更好地得到符合要求的聚类结果。
聚类性能度量大致有两类：

将聚类结果与某个“参考模型”进行比较，称为“外部指标”；
直接考察聚类结果而不利用任何参考模型，称为“内部指标”。

对数据集\(D=\{\pmb{x}_1,\pmb{x}_2,\cdots,\pmb{x}_m\}\)，假设通过聚类给出的簇划分为\(C=\{C_1,C_2,\cdots,C_k\}\)，参考模型给出的簇划分为\(C^* = \{C_1^*,C_2^*,\cdots,C_s^*\}\)，相应的，令\(\lambda\)和\(\lambda^*\)分别表示与\(C\)和\(C^*\)对应的簇标记变量，将样本两两考虑，定义 \[\begin{equation} a = |SS|,\quad SS = \{(\pmb{x}_i,\pmb{x}_j)| \lambda_i = \lambda_j,\lambda_i^* = \lambda_j^*,i<j\} \nonumber \\ b = |SD|,\quad SD = \{(\pmb{x}_i,\pmb{x}_j)| \lambda_i = \lambda_j,\lambda_i^* \neq \lambda_j^*,i<j\} \nonumber \\ c = |DS|,\quad DS = \{(\pmb{x}_i,\pmb{x}_j)| \lambda_i \neq \lambda_j,\lambda_i^* = \lambda_j^*,i<j\} \nonumber \\ d = |DD|,\quad DD = \{(\pmb{x}_i,\pmb{x}_j)| \lambda_i \neq \lambda_j,\lambda_i^* \neq \lambda_j^*,i<j\} \nonumber \end{equation}\] 其中集合\(SS\)包含了在\(C\)中隶属于相同簇且在\(C^*\)中也隶属于相同簇的样本对，集合\(SD\)包含了在\(C\)中隶属于相同簇但在\(C^*\)中隶属于不同簇的样本对，\(DS\)和\(DD\)类似。由于每个样本对\((\pmb{x}_i,\pmb{x}_j)(i < j)\)仅能出现在一个集合里，因此有\(a+b+c+d=m(m-1)/2\)成立。
基于上面的定义，导出常用的聚类性能度量外部指标：
（1）Jaccard系数（JC）
\[JC = \frac{a}{a+b+c}\] （2）FM指数（FMI） \[FMI = \sqrt{\frac{a}{a+b}·\frac{a}{a+c}}\] （3）Rand指数（RI） \[RI = \frac{2(a+d)}{m(m-1)}\]

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

考虑聚类结果的簇划分\(C=\{C_1,C_2,\cdots,C_k\}\)，定义\(dist(·,·)\)用于表示两个样本之间的距离，\(\pmb{\mu}\)代表簇的中心点\(\pmb{\mu} = \frac{1}{|C|} \sum_{1 \leq i \leq|C|} \pmb{x}_i\)，并定义以下公式 \[avg(C) = \frac{2}{|C|(|C|-1)} \sum_{1 \leq i < j \leq |C|} dist(\pmb{x}_i,\pmb{x}_j)\] \(avg(C)\)表示簇\(C\)内样本之间的平均距离。
\[diam(C) = \max_{1 \leq i < j \leq |C|} dist(\pmb{x}_i,\pmb{x}_j)\] \(diam(C)\)对应于簇\(C\)内样本间的最远距离。
\[d_{min}(C_i,C_j) = \min_{\pmb{x}_i \in C_i,\pmb{x}_j \in C_j} dist(\pmb{x}_i,\pmb{x}_j)\] \(d_{min}(C_i,C_j)\)对应于簇\(C_i\)与簇\(C_j\)最近样本间的距离。
\[d_{cen}(C_i,C_j) = dist(\pmb{\mu}_i,\pmb{\mu}_j)\] \(d_{cen}(C_i,C_j)\)对应于簇\(C_i\)和簇\(C_j\)中心点间的距离。

基于上述公式可导出下面常用的聚类性能度量内部指标：
（1）DB指数（DBI）
\[DBI = \frac{1}{k} \sum_{i=1}^k \max_{j \neq i} (\frac{avg(C_i) + avg(C_j)}{d_{cen}(C_i,C_j)})\]

（2）Dunn指数（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则相反，值越大越好。

3. 距离计算

对于函数\(dist(·,·)\)，如果是一个“距离度量”，则需要满足一些基本性质：

非负性：\(dist(\pmb{x}_i,\pmb{x}_j) \geq 0\)；
同一性：\(dist(\pmb{x}_i,\pmb{x}_j) = 0\)当且仅当\(\pmb{x}_i = \pmb{x}_j\)；
对称性：\(dist(\pmb{x}_i,\pmb{x}_j) = dist(\pmb{x}_j,\pmb{x}_i)\)；
直递性：\(dist(\pmb{x}_i,\pmb{x}_j) \leq dist(\pmb{x}_i,\pmb{x}_k) + dist(\pmb{x}_k,\pmb{x}_j)\)。

给定样本\(\pmb{x}_i = (x_{i1},x_{i2},\cdots,x_{in})\)与\(\pmb{x}_j = (x_{j1},x_{j2},\cdots,x_{jn})\)，最常用的是“闵可夫斯基距离”（Minkowski distance）：
\[dist_{mk}(\pmb{x}_i,\pmb{x}_j) = (\sum_{u=1}^n |x_{iu} - x_{ju}|^p)^{\frac{1}{p}}\] （1）\(p=1\)时，为曼哈顿距离（Manhattan distance）：
\[dist_{man}(\pmb{x}_i,\pmb{x}_j) = ||\pmb{x}_i - \pmb{x}_j||_1 = \sum_{u=1}^n |x_{iu} - x_{ju}|\]
（2）\(p=2\)时，为欧氏距离（Euclidean distance）： \[dist_{ed}(\pmb{x}_i,\pmb{x}_j) = ||\pmb{x}_i - \pmb{x}_j||_2 = \sqrt{\sum_{u=1}^n |x_{iu} - x_{ju}|^2}\]
（3）\(p= \infty\)，为各个坐标距离的最大值： \[dist(\pmb{x}_i,\pmb{x}_j) = \max_{1 \leq u \leq n} |x_{iu} - x_{ju}|\]

在讨论距离计算时，将能直接在属性值上计算距离的属性称为有序属性，例如\(\{1,2,3\}\)；将不能直接在属性值上计算距离的称为无序属性，例如\(\{飞机，火车，轮船\}\)。闵可夫斯基距离可用于有序属性。
对于无序属性可采用VDM（Value Difference Metric）。令\(m_{u,a}\)表示在属性\(u\)上取值为\(a\)的样本数，\(m_{u,a,i}\)表示在第\(i\)个样本簇中在属性\(u\)上取值为\(a\)的样本数，\(k\)为样本簇数，则属性\(u\)上两个离散值\(a\)和\(b\)之间的VDM距离为 \[VDM_p(a,b) = \sum_{i=1}^k |\frac{m_{u,a,i}}{m_{u,a}} - \frac{m_{u,b,i}}{m_{u,b}}|^p\] 于是，可将闵可夫斯基距离和VDM结合用于处理混合属性。假设有\(n_c\)个有序属性，\(n-n_c\)个无序属性，不失一般性，令有序属性排列在无序属性之前，则 \[MinkovDM_p(\pmb{x}_i,\pmb{x}_j) = (\sum_{u=1}^{n_c}|x_{iu} - x_{ju}|^p + \sum_{u=n_c + 1}^n VDM_p(x_{iu},x_{ju}))^{\frac{1}{p}}\] 当样本空间中不同属性的重要性不同时，可使加权距离，以闵可夫斯基距离为例： \[dist_{wmk}(\pmb{x}_i,\pmb{x}_j) = (w_1·|x_{i1} - x_{j1}|^p + \cdots + w_n·|x_{in} - x_{jn}|^p)^{\frac{1}{p}}\] 其中权重\(w_i \geq 0 (i=1,2,\cdots,n)\)表征不同属性的重要性，通常\(\sum_{i=1}^n w_i = 1\)。

4. 原型聚类

原型聚类也称为“基于原型的聚类”，此类算法假设聚类结构能通过一组原型刻画，在现实聚类任务中极为常用。通常情形下，算法先对原型进行初始化，然后对原型进行迭代更新求解。采用不同的原型表示、不同的求解方式，将产生不同的算法。

4.1. \(k\)均值算法

给定样本集\(D = \{\pmb{x}_1,\pmb{x}_2,\cdots,\pmb{x}_m\}\)，\(k\)均值（k-means）算法针对聚类所得簇划分\(C=\{C_1,C_2,\cdots,C_k\}\)最小平方误差 \[E = \sum_{i=1}^k \sum_{\pmb{x} \in C_i} ||\pmb{x} - \pmb{\mu}_i||_2^2\] 其中\(\pmb{\mu}_i = \frac{1}{|C_i|} \sum_{\pmb{x} \in C_i} \pmb{x}\)是簇\(C_i\)的均值向量。直观来看，上式在一定程度上刻画了簇内样本围绕簇均值向量的紧密程度，\(E\)值越小则簇内样本相似度越高。
算法如下：

优点：

容易理解，聚类效果不错；
处理大数据集时，该算法可以保证较好的伸缩性和高效率；
当簇近似高斯分布时，效果非常不错。

缺点：

K值需要用户给定，在进行数据处理之前，K值是未知的，不同的K值也会得到不同的结果，可多选取几个K值，grid search选取几个指标评价效果；
对初始簇中心点是敏感的，可以多初始化几次，选取损失函数最小的；
属于硬聚类，每个样本点只属于一个类；
对异常值免疫能力差，可以进行一些调整（不取均值点、取离均值最近的样本点）；
对团壮数据点区分度好，对于带状效果不好（谱聚类、特征映射）。

缺失值问题：

离散特征：将缺失的样本作为单独一类，缺失特征过多的样本去掉；
连续特征：通过其他特征对缺失特征做回归；样本平均值填补；中位数填补。

对于初始值选取的问题，可用扩展的算法KMeans++，每次有权重的选取新的中心点。
为了使收敛速度加快，可以使用Mini-BatchKMeans，求梯度时用随机梯度下降，而不是批量梯度下降。

4.2. 学习向量量化

与\(k\)均值算法类似，学习向量量化（Learning Vector Quantization，LVQ）也是试图寻找一组原型向量来刻画聚类结构，但与一般聚类算法不同，LVQ假设数据样本带有类别标记，学习过程利用样本的这些监督信息来辅助聚类。
给定样本集\(D = \{(\pmb{x}_1,y_1),(\pmb{x}_2,y_2),\cdots,(\pmb{x}_m,y_m)\}\)，每个样本\(\pmb{x}_j\)是由\(n\)个属性描述的特征向量\((x_{j1},x_{j2},\cdots,x_{jn})\)，\(y_i \in \gamma\)是样本\(\pmb{x}_j\)的类别标记。LVQ的目标是学一组\(n\)为原型向量\(\{\pmb{p}_1,\pmb{p}_2,\cdots,\pmb{p}_q\}\)，每个原型向量代表一个聚类簇，粗标记\(t_i \in \gamma\)。

算法如下：

对样本\(\pmb{x}_j\)，如果最近的原型向量\(\pmb{p}_i^*\)与\(\pmb{x}_j\)的类别标记相同，则令\(\pmb{p}_i^*\)向\(\pmb{x}_j\)的方向靠拢，此时新原型向量为 \[\pmb{p}' = \pmb{p}_i^* + \eta·(\pmb{x}_j - \pmb{p}_i^*)\] \(\pmb{p}‘\)与\(\pmb{x}_j\)之间的距离为 \[\begin{align} ||\pmb{p}' - \pmb{x}_j||_2 &= ||\pmb{p}_i^* + \eta ·(\pmb{x}_j - \pmb{p}_i^*) - \pmb{x}_j||_2 \nonumber \\ &= (1 - \eta)·||\pmb{p}_i^* - \pmb{x}_j||_2 \nonumber \end{align}\] 令学习率\(\eta \in (0,1)\)，则原型向量\(\pmb{p}_i^*\)在更新为\(\pmb{p}'\)之后将更接近\(\pmb{x}_j\)。
类似的，若\(\pmb{p}_i^*\)与\(\pmb{x}_j\)的类别标记不同，则更新后的原型向量与\(\pmb{x}_j\)之间的距离将增大为\((1 + \eta)·||\pmb{p}_i^* - \pmb{x}_j||_2\)，从而远离\(\pmb{x}_j\)。
在学得一组原型向量\(\{\pmb{p}_1,\pmb{p}_2,\cdots,\pmb{p}_q\}\)后，即可实现对样本空间\(\mathscr{X}\)的簇划分，对任意样本\(\pmb{x}\)，它将被划入与其距离最近的原型向量所代表的簇中。即每个原型向量\(\pmb{p}_i\)定义了与之相关的一个区域\(R_i\)，该区域中每个样本与\(\pmb{p}_i\)的距离不大于它与其他原型向量\(\pmb{p}_{i'}(i' \neq i)\)的距离，即 \[R_i = \{\pmb{x} \in \mathscr{X}| ||\pmb{x} - \pmb{p}_i||_2 \leq ||\pmb{x} - \pmb{p}_{i'}||_2,i' \neq i\}\] 由此形成了对应样本空间\(\mathscr{X}\)的簇划分\(\{R_1,R_2,\cdots,R_q\}\)，该划分通常称为"Voronoi部分"（Voronoi tessellation）。

4.3. 高斯混合聚类

与\(k\)均值、LVQ用原型向量来刻画聚类结构不同，高斯混合（Mixture-of-Gaussian）聚类采用概率模型来表达聚类原型。
对\(n\)维样本空间\(\mathscr{X}\)中的随机向量\(\pmb{x}\)，若\(\pmb{x}\)服从高斯分布，其概率密度函数为 \[p(\pmb{x}) = \frac{1}{(2 \pi)^\frac{n}{2} |\pmb{\Sigma}|^{\frac{1}{2}}} e^{ - \frac{1}{2} (\pmb{x} - \pmb{\mu})^T \pmb{\Sigma}^{-1} (\pmb{x} - \pmb{\mu})} \tag{1}\] 其中\(\pmb{\mu}\)是\(n\)维均值向量，\(\Sigma\)是\(n \times n\)的协方差矩阵。有上式可以看出均值向量\(\pmb{\mu}\)和协方差矩阵\(\pmb{\Sigma}\)这两个参数决定。为了明确显示高斯分布于相应参数的依赖关系，将概率密度函数记为\(p(\pmb{x} | \pmb{\mu}, \pmb{\Sigma})\)。
定义高斯混合分布： \[p_{\mathscr{M}}(\pmb{x}) = \sum_{i=1}^k \alpha_i · p(\pmb{x}| \pmb{\mu}_i, \pmb{\Sigma}_i) \tag{2}\] 该分布共由\(k\)个混合成分组成，每个混合成分对应一个高斯分布。其中\(\pmb{\mu}_i\)与\(\pmb{\Sigma}_i\)是第\(i\)个高斯混合成分的参数，而\(\alpha_i > 0\)为相应的“混合系数”（mixture coefficient），\(\sum_{i=1}^k \alpha_i = 1\)。
假设样本的生成过程由高斯混合分布给出：

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

若训练集\(D = \{\pmb{x}_1, \pmb{x}_2, \cdots, \pmb{x}_m\}\)有上述过程产生，令随机变量\(z_j \in \{1,2,\cdots,k\}\)表示生成样本\(\pmb{x}_j\)的高斯混合成分，其取值未知。显然，\(z_j\)的先验概率\(P(z_j = i)\)对应于\(\alpha_i (i=1,2,\cdots,k)\)，根据贝叶斯定理，\(z_j\)的后验分布为： \[\begin{align} p_{\mathscr{M}}(z_j = i| \pmb{x}_j) &= \frac{P(z_j = i)·p_{\mathscr{M}}(\pmb{x}_j|z_j = i)}{p_{\mathscr{M}}(\pmb{x}_j)} \nonumber \\ &= \frac{\alpha_i · p(\pmb{x}_j | \pmb{\mu}_i, \pmb{\Sigma}_i)}{\sum_{l=1}^k \alpha_l · p(\pmb{x}_j| \pmb{\mu}_l, \pmb{\Sigma}_l)} \nonumber \end{align} \tag{3}\] \(p_{\mathscr{M}}(z_j = i|\pmb{x}_j)\)给出了样本\(\pmb{x}_j\)由第\(i\)个高斯混合成分生成的后验概率，为了方便叙述，将其简记为\(\gamma_{ji} (i=1,2,\cdots,k)\)。
当高斯混合分布\(p_{\mathscr{M}}(\pmb{x}) = \sum_{i=1}^k \alpha_i · p(\pmb{x}| \pmb{\mu}_i, \pmb{\Sigma}_i)\)已知时，高斯混合聚类吧样本集\(D\)划分为\(k\)个簇\(C = \{C_1,C_2,\cdots,C_k\}\)，每个样本\(\pmb{x}_j\)的簇标记\(\lambda_j\)如下确定： \[\lambda_j = \arg \max_{i \in \{1,2,\cdots,k\}} \gamma_{ji} \tag{4}\] 因此，从原型聚类的角度来看，高斯混合聚类是采用概率模型（高斯分布）对原型进行刻画，簇划分由原型对应后验概率确定。

下面是如何求解模型参数\(\{(\alpha_i,\pmb{\mu}_i, \pmb{\Sigma}_i)|1 \leq i \leq k\}\)。
给定样本集\(D\)，可采用极大似然估计，即最大化对数似然： \[\begin{align} LL(D) &= \ln(\prod_{j=1}^m p_{\mathscr{M}}(\pmb{x}_i)) \nonumber \\ &= \sum_{j=1}^m \ln(\sum_{i=1}^k \alpha_i·p(\pmb{x}_j|\pmb{\mu}_i,\pmb{\Sigma}_i)) \nonumber \end{align} \tag{5}\] 常采用EM算法进行迭代优化求解，下面是简单的推导：
若参数\(\{(\alpha_i,\pmb{\mu}_i,\pmb{\Sigma}_i)|1 \leq i \leq k\}\)能使对数似然函数最大化，则由\(\frac{\partial LL(D)}{\partial \pmb{\mu}_i} = 0\)有 \[\sum_{j=1}^m \frac{\alpha_i · p(\pmb{x}_j | \pmb{\mu}_i, \pmb{\Sigma}_i)}{\sum_{l=1}^k \alpha_l · p(\pmb{x}_j|\pmb{\mu}_l,\pmb{\Sigma}_l)} (\pmb{x}_j - \pmb{\mu}_i) = 0 \tag{6}\] 由式（3）以及\(\gamma_{ji} = p_{\mathscr{M}}(z_j = i | \pmb{x}_j)\)，有 \[\pmb{\mu}_i= \frac{\sum_{j=1}^m \gamma_{ji} \pmb{x}_j}{\sum_{j=1}^m \gamma_{ji}} \tag{7}\] 即各混合成分的均值可通过样本加权平均来估计，样本权重是每个样本属于该成分的后验概率。
在这一步的求导中，会用到下面两个知识点：

若\(\pmb{A}\)是\(n\)阶方阵，\(\pmb{x}\)是\(n\)维向量，则\(\frac{\partial (\pmb{x}^T \pmb{A} \pmb{x})}{\partial \pmb{x}} = (\pmb{A} + \pmb{A}^T) \pmb{x}\)，当\(\pmb{A}\)是\(n\)阶对称方阵时，即\(\pmb{A} = \pmb{A}^T\)，有\(\frac{\partial (\pmb{x}^T \pmb{A} \pmb{x})}{\partial \pmb{x}} = 2 \pmb{A} \pmb{x}\)；
如果\(n\)阶方阵\(\pmb{A}\)是可逆矩阵，\(\pmb{x}\)是\(n\)维列向量，那么方程\(\pmb{A} \pmb{x} = 0\)有且仅有平凡解（零解），即\(\pmb{x} = 0\)。

类似的，由\(\frac{\partial LL(D)}{\partial \pmb{\Sigma}_i} = 0\)可得 \[\pmb{\Sigma}_i = \frac{\sum_{j=1}^m \gamma_{ji}(\pmb{x}_j - \pmb{\mu}_i)(\pmb{x}_j - \pmb{\mu}_i)^T}{\sum_{j=1}^m \gamma_{ji}} \tag{8}\] 对于混合系数\(\alpha_i\)，除了需要最大化\(LL(D)\)，还需满足\(\alpha_i \geq 0\)，\(\sum_{i=1}^k \alpha_i = 1\)，考虑\(LL(D)\)的拉格朗日形式 \[LL(D) + \lambda (\sum_{i=1}^k \alpha_i - 1) \tag{9}\] 其中\(\lambda\)为拉格朗日乘子，由上式对\(\alpha_i\)的导数为0，有 \[\sum_{j=1}^m \frac{p(\pmb{x}_j|\pmb{\mu}_i, \pmb{\Sigma}_i)}{\sum_{l=1}^k \alpha_l · p(\pmb{x}_j | \pmb{\mu}_l, \pmb{\Sigma}_l)} + \lambda = 0 \tag{10}\] 两边同时乘以\(\alpha_i\)，有
\[\sum_{j=1}^m \frac{\alpha_i·p(\pmb{x}_j|\pmb{\mu}_i, \pmb{\Sigma}_i)}{\sum_{l=1}^k \alpha_l · p(\pmb{x}_j | \pmb{\mu}_l, \pmb{\Sigma}_l)} + \lambda·\alpha_i = \sum_{j=1}^m \gamma_{ji} + \lambda · \alpha_i = 0\] 对上式两边同时对\(i=1,2,\cdots,k\)求和,即
\[\sum_{i=1}^k[(\sum_{j=1}^m \gamma_{ji}) + \lambda · \alpha_i] = (\sum_{i=1}^k \sum_{j=1}^m \gamma_{ji}) + \lambda · \sum_{i=1}^k \alpha_i = m + \lambda = 0\] 可以得到\(\lambda = -m\)，所以有 \[\alpha_i = \frac{1}{m} \sum_{j=1}^m \gamma_{ji} \tag{11}\] 即每个高斯成分的混合系数由样本属于该成分的平均后验概率确定。

有上述推导可获得高斯混合模型的EM算法：

E步：在每步迭代中，先根据当前参数来计算每个样本属于每个高斯成分的后验概率\(\gamma_{ji}\)；
M步：根据式（7）、（8）和（11）更新模型参数\(\{(\alpha_i,\pmb{\mu}_i, \pmb{\Sigma}_i)|1 \leq i \leq k\}\)。

算法如下：

5. 密度聚类

密度聚类也称为“基于密度的聚类”（density-based clustering），此类算法假设聚类结构能通过样本分布的紧密程度确定。通常情形下，密度聚类算法从样本密度的角度来考察样本之间的可连接性，并基于可连接样本不断扩展聚类簇以获得最终的聚类结果。
DBSCAN是一种著名的密度聚类算法，它基于一组“邻域”参数\((\epsilon,MinPts)\)来刻画样本分布的紧密程度。给定数据集\(D = \{\pmb{x}_1, \pmb{x}_2,\cdots, \pmb{x}_m\}\)。定义下列概念：

\(\epsilon\)-邻域：对\(\pmb{x}_j \in D\)，其\(\epsilon\)-邻域包含样本集\(D\)中与\(\pmb{x}_j\)的距离不大于\(\epsilon\)的样本，即\(N_{\epsilon}(\pmb{x}_j) = \{\pmb{x}_i \in D | dist(\pmb{x}_i, \pmb{x}_j) \leq \epsilon\}\)；
核心对象（core object）：若\(\pmb{x}_j\)的\(\epsilon\)-邻域至少包含\(MinPts\)个样本，即\(|N_{\epsilon}(\pmb{x}_j)| \geq MinPts\)，则\(\pmb{x}_j\)是一个核心对象；
密度直达（directly density-reachable）：若\(\pmb{x}_j\)位于\(\pmb{x}_i\)的\(\epsilon\)-邻域中，且\(\pmb{x}_i\)是核心对象，则称\(\pmb{x}_j\)由\(\pmb{x}_i\)密度直达；
密度可达（density-reachable）：对\(\pmb{x}_i\)与\(\pmb{x}_j\)，若存在这样的序列\(\pmb{p}_1,\pmb{p}_2,\cdots,\pmb{p}_n\)，其中\(\pmb{p}_1 = \pmb{x}_i\)，\(\pmb{p}_n = \pmb{x}_j\)且\(\pmb{p}_{i+1}\)由\(\pmb{p}_i\)密度直达，则称\(\pmb{x}_i\)与\(\pmb{x}_j\)密度可达；
密度相连（density-connected）：对\(\pmb{x}_i\)与\(\pmb{x}_j\)，若存在\(\pmb{x}_k\)使得\(\pmb{x}_i\)与\(\pmb{x}_j\)均由\(\pmb{x}_k\)密度可达，则称\(\pmb{x}_i\)与\(\pmb{x}_j\)密度相连。

基于上述概念，DBSCAN将“簇”定义为：有密度可达关系导出的最大的密度相连样本集合。形式化地说，给定领域参数\((\epsilon,MinPts)\)，簇\(C \subseteq D\)是满足以下性质的非空样本子集：

连接性（connectivity）：\(\pmb{x}_i \in C, \pmb{x}_j \in C \Rightarrow \pmb{x}_i 与 \pmb{x}_j 密度相连\)
最大性（maximality）：\(\pmb{x}_i \in C, \pmb{x}_j 由\pmb{x}_i 密度可达 \Rightarrow \pmb{x}_j \in C\)

若\(\pmb{x}\)为核心对象，由\(\pmb{x}\)密度可达的所有样本组成的集合记为\(\pmb{X} = \{\pmb{x}' \in D| \pmb{x}'由\pmb{x}密度可达\}\)，则不难证明\(\pmb{X}\)即为满足连接性与最大性的簇。
\(D\)中不属于任何簇的样本被认为是噪声或异常样本。
算法如下：

6. 层次聚类

层次聚类（hierarchical clustering）试图在不同层次对数据集进行划分，从而形成树形的聚类结构。数据集的划分可采用“自底向上”的聚类策略，也可采用“自顶向下”的分拆策略。
AGNES是一种采用自底向上聚合策略的层次聚类方法。它先将数据集中的每个样本看做一个初始聚类簇，然后在算法运行的每一步中找出距离最近的两个聚类簇进行合并，该过程不断重复，直至达到预设的聚类簇个数。

给定聚类簇\(C_i\)和\(C_j\)，可通过下列公式计算距离：

最小距离：\(d_{min}(C_i,C_j) = \min_{\pmb{x} \in C_i, \pmb{z} \in C_j} dist(\pmb{x},\pmb{z})\)
最大距离：\(d_{max}(C_i,C_j) = \max_{\pmb{x} \in C_i, \pmb{z} \in C_j} dist(\pmb{x},\pmb{z})\)
平均距离：\(d_{avg}(C_i,C_j) = \frac{1}{|C_i||C_j|} \sum_{\pmb{x} \in C_i,\pmb{z} \in C_j} dist(\pmb{x},\pmb{z})\)

AGNES算法根据不同的距离计算公式被称为：

单链接算法（single-linkage）：最小距离由两个簇的最近样本决定；
全链接算法（complete-linkage）：最大距离由两个簇的最远样本决定；
均链接算法（average-linkage）：平均距离由两个簇的所有样本共同决定。

单链接算法易产生链化现象，全链接算法对离群点非常敏感。

算法如下：

层次聚类的优点：

可以通过设置不同的参数值，得到不同粒度上的多层次聚类结构；
对样本的输入顺序不敏感。

层次聚类的缺点：

算法的时间复杂度大；
层次聚类的结果依赖聚类合并点和分裂点的选择；
不可逆性，下一次聚类会在前一次聚类结果的基础上进行，一旦聚类结果形成，无法通过重新合并来优化聚类的性能；
聚类终止条件的不精确性。