本文介绍了无监督分类器的设计原理和方法。不同于前面章节介绍的分类器，无监督分类器旨在没有类别标签的情况下完成样本的分类。由于样本的类别标签位置，无监督分类器具有一定的学习能力，因此相关分类方法又被称为无监督学习。聚类（Clustering）分析是最典型的无监督学习方法。
1. 聚类
聚类是一种无监督学习方法，其在没有预先指定可能的类别，事先不知道所考虑问题应该分为几类，更不知道观测到的个体的具体分类的情况下，寻找样本数据潜在的自然分组结构和内在规律。聚类的目标是将样本集中的样本划分为不同的类别或簇，使得同一类别内的样本具有较高的相似度，而不同类别样本之间具有较高的相异性。
在执行聚类时，针对包含大量未知类别样本的样本集，采用距离或相似性度量来计算样本之间的相似性，利用聚类算法根据计算的相似性把样本集划分为若干子集或簇，并使某种表示聚类质量的准则函数达到最优。因此
- 相似性测度：衡量两个数据（样本）之间的相似程度；
- 聚类准则函数：用于指导聚类算法的优化过程，或衡量不同聚类结果的优劣；
- 聚类算法
称为聚类的三要素。
1.1. 相似性测度
「相似性测度」又被称为「相似性度量」或直接简称为「相似度」，一种典型的相似性度量方式是根据不同样本在特征空间中的距离，利用「同类样本相互靠近、异类样本相互远离」的策略进行聚类。假设两个样本的特征向量为 $\boldsymbol{x}^{(1)},\boldsymbol{x}^{(2)}\in\mathbb{R}^d$，可分别定义如下相似度。
1.1.1. 闵可夫斯基距离
闵可夫斯基距离（Minkowski distance，明式距离）是指两个样本在特征空间中的一类距离的统称，定义如下
\[M(\boldsymbol{x}^{(1)}, \boldsymbol{x}^{(2)}) = \left(\sum_{i=1}^d |x^{(1)}_{i} - x^{(2)}_{i}|^p\right)^\frac{1}{p}\quad p\geq 1\]1.1.1.1. 曼哈顿距离
当明式距离中的参数 $p=1$ 时，又称为曼哈顿距离（Manhattan distance，曼哈顿距离）或 $L_1$ 范数：
\[M(\boldsymbol{x}^{(1)}, \boldsymbol{x}^{(2)}) = \sum_{i=1}^d |x^{(1)}_{i} - x^{(2)}_{i}| = \Vert\boldsymbol{x}^{(1)} - \boldsymbol{x}^{(2)}\Vert_1\]曼哈顿距离的命名原因是从规划为方型建筑区块的城市（如曼哈顿）间，最短的行车路径而来。对于一个具有正南正北、正东正西方向规则布局的城镇街道，从一点到达另一点的距离正是在南北方向上旅行的距离加上在东西方向上旅行的距离，因此，曼哈顿距离又称为出租车距离。
在早期的计算机图形学中，屏幕是由像素构成，是整数，点的坐标也一般是整数。当计算两个像素点之间的距离时，如果直接使用AB的欧氏距离，则必须要进行浮点运算，但浮点运算很昂贵，很慢而且有误差。如果使用曼哈顿距离，则只要计算加减法即可，这就大大提高了运算速度，而且不管累计运算多少次，都不会有误差。
思考：二维特征空间中，采用曼哈顿距离定义「圆」的图案是什么？
1.1.1.2. 欧几里得距离
当明式距离中的参数 $p=2$ 时，又称为欧几里得距离（Euclidean distance，欧氏距离）或 $L_2$ 范数：
\[D = \sqrt{\sum_{i=1}^d (x^{(1)}_{i} - x^{(2)}_{i})^2} = \Vert\boldsymbol{x}^{(1)} - \boldsymbol{x}^{(2)}\Vert_2\]1.1.1.3. 切比雪夫距离
当明式距离中的参数 $p=\infty$ 时，又称为切比雪夫距离（Chebyshev distance）或 $L_\infty$ 范数：
\[D = \max_{i=1,\ldots,d} |x^{(1)}_{i} - x^{(2)}_{i}| = \Vert\boldsymbol{x}^{(1)} - \boldsymbol{x}^{(2)}\Vert_\infty\]证明如下：
假设两个样本的特征向量各维度的绝对差为 $d_i = \vert x^{(1)}{i} - x^{(2)}{i} \vert$，闵科夫斯基距离写成如下形式：
\[D = \left(\sum_{i=1}^d d_i^p\right)^\frac{1}{p}\]假设绝对差的最大值为 $d_{\max} = \max_i d_i$，将其提到求和符号外面，有
\[D = \left(\sum_{i=1}^d d_i^p\right)^\frac{1}{p} = d_{\max} \left(\sum_{i=1}^d \left(\frac{d_i}{d_{\max}}\right)^p\right)^\frac{1}{p}\]注意到，对于所有 $i$ 有 $\frac{d_i}{d_{\max}} \leq 1$，因此当 $p\to \infty$ 时，有
\[\begin{aligned} \left(\frac{d_i}{d_{\max}}\right)^p\to 0,\quad d_i < d_{\max}\\ \left(\frac{d_i}{d_{\max}}\right)^p\to 1,\quad d_i = d_{\max} \end{aligned}\]因此，求和项中只有最大项会保留（注意最大项可能不止一个！），假设最大项有 $k$ 个，则
\[\sum_{i=1}^d \left(\frac{d_i}{d_{\max}}\right)^p \to k\]则
\[D = d_{\max}\cdot k^{1/p}\]对于有限常数 $k$，$p\to \infty$ 时，有 $k^{1/p}\to 1$，得证。
1.1.2. 马氏距离
马氏距离（Mahalanobis Distance）是由马哈拉诺比斯（P. C. Mahalanobis）提出的，表示数据的协方差距离。它是一种有效的计算两个未知样本集的相似度的方法。马氏距离也可以定义为两个服从同一分布并且其协方差矩阵为 $\Sigma$ 的随机变量之间的差异程度。
\[M = \left( (\boldsymbol{x}^{(1)}-\boldsymbol{x}^{(2)})^\top\Sigma^{-1}(\boldsymbol{x}^{(1)}-\boldsymbol{x}^{(2)}) \right)^{1/2}=\sqrt{\sum_{i=1}^d \frac{(x^{(1)}_{i} - x^{(2)}_{i})^2}{\sigma_i^2}}\]如果协方差矩阵为单位矩阵，那么马氏距离就简化为欧氏距离；如果协方差矩阵为对角阵，各特征完全相互独立。
马氏距离可以克服欧氏距离的一些缺点。欧氏距离将样品的不同特征之间的差别独立且等同看待，这一点有时不能满足实际要求，如身高和体重是有相关性的。
马氏距离通过除以方差矩阵，将各个分量之间的方差除掉了，消除了量纲影响，如下图所示。
1.1.3. 相关系数
「距离」衡量的是两个数据点在空间中的绝对位置差异，强调的是“远近”关系。而相关系数衡量的是两个变量之间的线性相关程度，强调的是“变化趋势”的一致性。相比于距离，相关系数从另一个角度来衡量两个变量之间的关系。
1.1.3.1. 角度相关系数
角度相关系数表征两个向量的夹角余弦，又被称为余弦相似度。两个向量越相似（正相关），该值越接近 $1$；无线性关系，值等于零；越不相似（越负相关），该值越接近 $-1$。
\[\cos(\boldsymbol{x}^{(1)},\boldsymbol{x}^{(2)}) = \frac{\boldsymbol{x}^{(1)}{}^\top \boldsymbol{x}^{(2)}}{\Vert\boldsymbol{x}^{(1)}\Vert_2\Vert\boldsymbol{x}^{(2)}\Vert_2}\]余弦相似度只比较向量的夹角，与模长无关。例：文本相似性中，文档长度不影响结果。
1.1.3.2. 皮尔逊相关系数
皮尔逊相关系数（Pearson’s $r$）用于衡量两个连续变量之间的线性相关性，取值范围为 $[−1,1]$ 。
\[\begin{aligned} r &= \frac{\text{Cov}(\boldsymbol{x}^{(1)},\boldsymbol{x}^{(2)})}{\sigma_{\boldsymbol{x}^{(1)}} \sigma_{\boldsymbol{x}^{(2)}}} = \frac{ (\boldsymbol{x}^{(1)} - \bar{\boldsymbol{x}}^{(1)})^{\top} (\boldsymbol{x}^{(2)} - \bar{\boldsymbol{x}}^{(2)}) }{ \|\boldsymbol{x}^{(1)} - \bar{\boldsymbol{x}}^{(1)}\| \cdot \|\boldsymbol{x}^{(2)} - \bar{\boldsymbol{x}}^{(2)}\| }\\ &= \frac{\sum_{i=1}^n (x^{(1)}_i - \bar{x}^{(1)})(x^{(2)}_i - \bar{x}^{(2)})}{\sqrt{\sum_{i=1}^n (x^{(1)}_i - \bar{x}^{(1)})^2} \sqrt{\sum_{i=1}^n (x^{(2)}_i - \bar{x}^{(2)})^2}}\\ \end{aligned}\]皮尔逊相关系数类似余弦相似度，但数据已中心化（均值归一化）。
1.2. 聚类准则函数
聚类的准则函数用来评价聚类效果，比如采用不同的聚类方法可以计算相应的准则函数，取准则函数较优的聚类方法为最优聚类方法。又比如相同的聚类方法可以采用不同的算法参数（如 K-均值 聚类的初始类别数），然后计算相应的准则函数，取准则函数较优的算法参数为最优算法参数。
1.2.1. 误差平方和准则
误差平方和（Sum of Squared Errors, SSE）是聚类分析中最常用的准则函数之一，用于衡量类内数据的紧致性。其核心思想是：最小化每个数据点与其所属簇中心（质心）的距离的平方和。一般而言，这里的距离使用的是「欧几里得距离」。
假设将样本划分为 $k$ 个簇，每个簇的质心（均值）为 $\boldsymbol{\mu}_i$，则 SSE 定义为：
\[SSE = \sum_{i=1}^k \sum_{x\in w_i} \Vert x - \boldsymbol{\mu}_i\Vert^2\]一个好的聚类方法应该能使每一个簇中的所有向量与其均值向量的 “误差” 的平方和 最小。使得误差平方和最小的聚类也被称为最小方差聚类。该方法的优缺点如下：
优点：
- 计算简单：仅需计算欧氏距离的平方和，易于实现和优化；
- 可解释性强：直接反映类内数据的聚集程度，值越小说明簇内数据越紧密；
- 适用于凸形簇：对球形或凸形分布的数据聚类效果良好；
缺点：
- 适用性有限：对于非凸形状的分布，聚类效果不好；
- 对异常值敏感：平方项会放大离群点的影响，导致质心偏移（可改用绝对误差或中位数）；
- 依赖初始质心：聚类结果与初始质心位置有关，随机初始化可能导致局部最优解；
- 需要预先指定簇数：聚类结果与簇数有关，需要预先指定。
1.2.2. 离散度准则
离散度准则采用离散度矩阵来刻画。离散度矩阵不仅反映同类样本的聚合程度，而且也反映不同类之间的分离程度，因此可以对聚类的质量进行全面的描述和评价。
假设聚类为 $k$ 类，类内离散度矩阵和类间离散度矩阵可参考 模式识别（LDA和PCA） - 多分类LDA 定义如下：
类内离散度矩阵：
\[\boldsymbol{S}_w = \sum_{i=1}^k \boldsymbol{S}_{wi}=\sum_{i=1}^k \sum_{\boldsymbol{x}\in w_i}(\boldsymbol{x}-\boldsymbol{\mu}_i)(\boldsymbol{x}-\boldsymbol{\mu}_i)^\top\]类间离散度矩阵，为度量每类均值点相对于样本中心的散列情况，并用每类样本个数进行加权，即
\[\boldsymbol{S}_b= \sum_{i=1}^k N_i(\boldsymbol{\mu}_i-\boldsymbol{\mu})(\boldsymbol{\mu}_i-\boldsymbol{\mu})^\top\]定义总离散度矩阵为
\[\boldsymbol{S}_t = \boldsymbol{S}_w + \boldsymbol{S}_b = \sum_{i=1}^C \sum_{\boldsymbol{x}\in w_i}(\boldsymbol{x}-\boldsymbol{\mu})(\boldsymbol{x}-\boldsymbol{\mu})^\top\]上述定义式可以通过展开后分析（交叉项为零）证明。
总离散度矩阵反映数据整体的变异性，是类内和类间离散的总和。为了更准确地度量类内离散度和类间离散度，可以引入一个标量来衡量离散度矩阵的“大小”———矩阵的迹和矩阵的行列式。
-
离散度矩阵迹准则
如果单独使用类内离散度矩阵的迹，注意到这与「误差平方和准则」完全一致
\[\min \; \text{tr}\boldsymbol{S}_w = \sum_{i=1}^C \sum_{\boldsymbol{x}_{ij}\in w_i}\Vert\boldsymbol{x}_{ij}-\boldsymbol{\mu}_i\Vert^2\]当然也可以单独使用类间离散度矩阵的迹，即
\[\min \; \text{tr}\boldsymbol{S}_b = \sum_{i=1}^C N_i\Vert\boldsymbol{\mu}_i-\boldsymbol{\mu}\Vert^2\]还可以同时考虑类内和类间离散度矩阵，设计迹准则
\[\max \; \text{tr}(\boldsymbol{S}_w^{-1}\boldsymbol{S}_b)\]该准则与 LDA 的优化目标函数
\[\max \; J(\boldsymbol{w}) = \frac{\boldsymbol{w}^\top\boldsymbol{S}_b\boldsymbol{w}}{\boldsymbol{w}^\top\boldsymbol{S}_w\boldsymbol{w}}\]等价，因为 LDA 的优化问题可转化为求矩阵 $\boldsymbol{S}_w^{-1}\boldsymbol{S}_b$ 的特征值 $\lambda$ 和特征向量 $\boldsymbol{w}^{\star}$。对于二分类 LDA 问题，最佳投影方向是矩阵 $\boldsymbol{S}_w^{-1}\boldsymbol{S}_b$ 的最大特征值对应的特征向量。对于多分类 LDA 问题，最佳投影矩阵的列是 $\boldsymbol{S}_w^{-1}\boldsymbol{S}_b$ 的前 $d$ 个最大特征值对应的特征向量。
而根据迹的定义有
\[\text{tr}(\boldsymbol{S}_w^{-1}\boldsymbol{S}_b) = \sum_{i=1}^d \lambda_i\]当 LDA 目标函数最优（最大）时，前 $d$ 个最大特征值的和自然也最大。
-
离散度矩阵行列式准则
与离散度矩阵迹准则类似，可以采用行列式设计准则函数，如
\[\max \; \vert \boldsymbol{S}_w^{-1}\boldsymbol{S}_b \vert\]1.2.3. SD 有效性函数
SD有效性函数（SD Validity Function）是一种用于评估聚类结果质量的准则函数，它综合考虑了聚类的平均散布性和聚类间的总体分离性。这种方法确实是在2000年左右被提出并广泛应用于聚类分析中。
-
平均散布性（Average Scattering）
设样本总方差和各个聚类的方差分别为 $\sigma(\Omega)$ 和 $\sigma(\omega_i)$，则平均散布性定义为：
\[\text{Scat}(C)=\frac{1}{C}\sum_{i=1}^C\frac{\Vert\sigma(\omega_i)\Vert}{\Vert\sigma(\Omega)\Vert}\]一个好的聚类具备较大的样本总方差和较低的各个聚类方差，因此平均散布性越小，聚类效果越好。
-
总体分离性（Total Separation）
假设 $D_{\max}$ 和 $D_{\min}$ 分别表示聚类中心间的最大和最小距离，则总体分离性定义为：
\[\text{Dis}(C) = \frac{D_{\text{max}}}{D_{\text{min}}} \sum_{i=1}^{C} \left( \sum_{i=1}^{C} \|\boldsymbol{\mu}_i - \boldsymbol{\mu}_j\| \right)^{-1}\]一个好的聚类中各类别中心间的最大和最小距离应该较为接近，且不同类别的均值的差较大，此时总体分离性会较低。
综上，我们希望最小化如下定义的 SD 有效性函数：
\[\min \; \text{SD}(C) = \alpha\cdot \text{Dis}(C) + \text{Var}(C)\]该准则函数越小表明聚类效果越好。
1.3. 聚类方法
聚类方法设计的核心大多都是围绕初始类别（或聚类中心）的选取来展开，如：
- 基于层次的聚类方法：假设初始每个样本都是一个类别，或者所有类别都属于一个类别；
- 基于划分的聚类方法：随机或凭借经验选择若干个初始聚类中心，并设计初始类别；
1.3.1. 基于层次的聚类
层次聚类（Hierarchical Clustering）又被称为分级聚类，是最常见的聚类分析算法之一。给定 $d$ 维特征空间中由 $N$ 个数据点所构成的样本集 $D={x_1,x_2,\cdots,x_N}$，若需要将样本集聚类为 $C$ 个类别，假设类别与类别之间没有重合的数据点，那么可以选择以下两种层次聚类方向之一开始聚类。
1.3.1.1. 层次聚类方向
-
自下而上聚合
- 将所有样本点都视为一个类别，即 $C=N$，每个类别的样本点个数为 $N$；
- 将相似性最强的两个类别合并，得到 $C-1$ 个聚类，即 $C=N-1$。
- 重复第二步，直到聚类的类别数目达到预期。
-
自上而下分解
- 创建一个初始类别，即 $C=1$，该类别的样本点个数为 $N$；
- 将最不相似的两个类别分离，得到 $C+1$ 个聚类，即 $C=N+1$；
- 重复第二步，直到聚类的类别数目达到预期。
可以看出，不论是自下而上还是自上而下，在聚类过程中都需要直接计算某个相似性测度，评估两个类别的相似性，进而进行类别合并或分离。
1.3.1.2. 测度计算方法
前述迭代聚类过程中，首先需要计算两个类别的相似性测度来决定哪两个类别进行合并或分离。根据具体任务需求，这里可以选择前面介绍过的任意相似性测度。
其次，对于包含多个样本的类别，即使选择了特定的相似性测度，其具体计算也存在多样性。比如，选择欧氏距离作为相似性测度，那么可以采用以下三种计算方法：
- 最小距离法：将两类别中最「近」的两个数据点之间的欧氏距离作为测度；
- 最大距离法：将两类别中最「远」两个数据点之间的欧氏距离作为测度；
- 均值距离法：将两个类别的均值的欧式距离作为测度；
- 组平均距离法：将两个类别之间所有点对距离的平均值作为类别相似性测度。相比于最小距离法和最大距离法，组平均距离法可以有效避免类内特殊点带来的不利影响；
- 沃德距离法：将两个类别合并/拆分时带来的平方和误差（SSE）的变化量作为测度。
1.3.1.3. 小结
基于层次的聚类方法是一种较为简单的聚类方法，只需要通过一轮迭代即可完成聚类，原理简单易于实现，且相似性测度采用欧氏距离，该测度是具有真实意义的，但选取不同的计算方法可能会导致聚类结果的差异。
1.3.2. 基于划分的聚类
基于划分的聚类方法是一种自顶向下的方法，对于给定的由 $N$ 个样本数据组成的数据集 $X$，将该数据集划分为 $C$ 个分区，其中每个分区代表一个簇。
给定要构建的分区数 $C$，首先创建一个初始划分，然后采用迭代重定位技术，通过把对象从一个组移动到另一个组来改进划分。一个好的划分准则是：同一个簇中的相关对象尽可能相互“接近”或相关，而不同簇中的对象尽可能地“远离”或不同。
1.3.2.1. K-均值聚类（K-means）
最经典的基于划分的聚类方法是 「K-means 聚类」。其核心思想是指定聚类中心，再通过迭代的方式更新聚类中心。
- 第一步：样本集初始划分
（1）选择代表点
- 方式1：凭经验从数据中找出从合适的代表点；
- 方式2：将全部数据随机地分成 $C$ 类，计算每类均值作为每类代表点；
- 方式3：用前 $C$ 个样本点作为代表点。
以上选择代表点的方法都是带有启发性的，不同的方法得到不同的初始代表点，它将直接影响到聚类的结果。
（2）选择相似性测度
不同的相似性测度选择也直接影响聚类的结果，一般而言常用的选择包括前面介绍的 欧几里得距离、闵科夫斯基距离、马氏距离、相关性测度等。
- 第二步：相似性测度选择和迭代计算
确定相似性测度后，遍历所有待分类的样本 $x_i$，计算该样本与每个聚类中心（代表点）的距离，按照最小距离原则将样本划分到 $C$ 类中的某一类。这里有两种不同的遍历方式：
-
方式1：将其余样本点按照与代表点距离最近原则，划分到相应类中（代表点保持不变）；
-
方式2：每个代表点自成一类，将样本依顺序归入与其最近的代表点那一类，并立即重新计算该类的均值以代替原来的代表点（代表点进行动态更新）。然后再计算下一个样本的归类，直至所有的样本都归到相应的类为止。
两种方式各有利弊，方式 1 的计算量少，但收敛速度比较慢；方式 2 的计算量大，但收敛速度快。
如此反复迭代并更新聚类中心，直至所有类的聚类中心都不再发生变化，聚类结束。
- 类别数的确定
如果初始确定的聚类类别数是凭借经验确定的，那么这一步可以不进行。
但是，凭借经验确定的类别数不一定是最优的。除了凭借经验确定类别数外，还可以通过计算不同类别数下的聚类准则（SSE、离散度、SD有效性）来选择最合适的类别数。
一般情况下，我们可以绘制出聚类准则函数值随类别数的变化曲线，然后选取曲线拐点的个数作为聚类类别数。
1.3.2.2. K-Means++ 算法
前述 K-Means 方法中，随机的初始中心选择对计算结果和迭代次数有较大的影响，一种改进方法被称为 K-Means++。K-means++ 按照如下的思想选取 $C$ 个初始聚类中心：
- 第 $n=1$ 个聚类中心通过随机的方法选取；
- 从第 $n=2$ 初始聚类中心开始，距离当前 $n$ 个聚类中心越远的点会有更高的概率被选为第 $n+1$ 个聚类中心。
K-Means++ 保证了初始聚类中心之间的相互距离要尽可能的远，可有效解决随机初始中心选择的问题。但是，对于聚类数量的预先设定，在 K-Means++ 中也没有很好的解决。
1.3.2.3. 迭代自组织数据分析方法（ISODATA）
迭代自组织数据分析方法（Iterative Self-Organizing Data Analysis Techniques Algorithm，ISODATA）在 K-Means 算法基础上增加对聚类结果的「合并」和「分裂」：
-
聚类合并：当两个聚类中心之间距离值小于某个阈值时，将两个聚类中心合并成一个；
-
聚类分裂：当某个聚类的类别其样本方差大于一定的阈值且该聚类内样本数量超过一定阈值时，将该聚类分裂为两个聚类。
经过以上两个操作，可有效解决聚类数量需要设定的问题。
ISODATA 需要指定以下几个参数：
- 预期的类别数目 $C$
虽然在ISODATA运行过程中类别数目是可变的，但还是需要由用户指定一个参考标准。事实上，该算法的聚类中心数目变动范围也由 $C$ 决定。具体地，最终输出的聚类中心数目范围是 $[C/2, 2C]$。
- 每个类所包含的最少样本数目 $N_{\min}$
用于判断当某个类别所包含样本分散程度较大时是否可以进行分裂操作。如果分裂后会导致某个子类别所包含样本数目小于 $N_{\min}$ ，就不会对该类别进行分裂操作。
- 最大方差阈值 $\Sigma$
用于衡量某个类别中样本的分散程度。当样本的分散程度超过这个值时，则有可能进行分裂操作（注意同时需要满足 $N_{\min}$ 条件）;
- 类间最小距离阈值 $d_{\min}$
如果两个类别靠得非常近（一般使用聚类中心之间的欧几里得距离衡量），则需要对这两个类别进行合并操作。是否进行合并的阈值由 $d_{\min}$ 决定。
1.3.2.4. 小结
基于划分的聚类方法主要包括：K-Means 聚类、K-Means++ 聚类、ISODATA 聚类。三个方法是逐步递进完善的关系：
- K-Means：简单快速，适用于大数据集，但需要预先指定 $K$ 值，对初始条件敏感。
- K-Means++：改进了 K-Means 的初始聚类中心选择，提高了结果的稳定性，但仍需指定 K 值。
- ISODATA：动态调整聚类数目，使用更多的参数来控制迭代过程，但计算复杂度较高。
选择哪种算法取决于具体的应用场景和数据特性。
1.3.3. 基于密度的聚类
1.3.3.1. DBSCAN
DBSCAN（Density-Based Spatial Clustering of Applications with Noise）是比较有代表性的基于密度的聚类算法。其将簇（类）定义为「密度相连的点的最大集合」，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类。该算法不需要确定聚类的数量，而是基于数据推测聚类的数目，能够针对任意形状产生聚类。
DBSCAN 算法涉及到以下几个定义：
-
密度：以每个数据点为圆心，以 $\epsilon$ 为半径画个圈（称为 $\epsilon$-邻域），然后数有多少个点在这个圈内，这个数就是该点密度；
-
核心点：一个点 $x$ 的密度大于等于某个阈值 $m$ 则被称为核心点；
-
边界点：一个点 $x$ 的密度小于某个阈值 $m$，但是位于某核心点的邻域内的点，则被称为边界点；
-
噪声点：既不是核心点也不是边界点的点。
如图示，假设 $m=5,\epsilon$ 如图，三个点分别为：
- 点 $A$ 是核心点，因为 $A$ 的 $\epsilon$-邻域内包含 7 个点；
- 点 $B$ 是边界点，因为 $B$ 的 $\epsilon$-邻域内包含 3 个点，但位于核心点 $A$ 的邻域内；
- 点 $C$ 是噪声点，因为 $C$ 的 $\epsilon$-邻域内包含 3 个点，且没有任何核心点落在其邻域内。
基于上述定义，我们可以进一步延伸出以下概念：
- 密度直达（Directly Density-Reachable）：如果点 $q$ 在核心点 $p$ 的 $\epsilon$-邻域内，则称 $p$ 密度直达 $q$；注意起点必须是核心点；
- 密度可达（Density-Reachable）：对于点链 $p_1\to p_2\to \cdots\to p_n$，若 $p_{i}$ 密度直达点 $p_{i+1}$，则称点 $p_1$ 密度可达 $p_n$，或者称点 $p_n$ 由 $p_i$ 密度可达；
- 密度相连（Density-Connected）：如果对于样本点 $p$ 和 $q$，存在一个样本点 $k$，使得 $p$ 和 $q$ 都由 $k$ 密度可达，那么我们说 $p$ 和 $q$ 密度相连。换句话说，如果 $p$ 和 $q$ 可以通过一系列密度可达的核心点连接起来，那么它们是密度相连的；
- 密度聚类簇（Density-Cluster）：由一个核心点和所有与其密度可达的点（包括核心点和边界点）构成的集合称为一个密度聚类簇。这意味着一个密度聚类簇可以包含核心点、边界点以及通过密度可达关系连接的所有其他点。
根据上述定义和概念，对下图的三个点进行分析：
图(a)中，点 $A$ 为核心点，点 $B$ 为边界点。$A$ 密度直达 $B$，但 $B$ 不密度直达 $A$（因为 $B$ 不是一个核心点）。
图(b)中，点 $C$ 和 $A$ 为核心点。$C$ 密度直达 $A$，$A$ 密度直达 $B$，所以 $C$ 密度可达 $B$。$A$ 密度直达 $C$，但是 $B$ 不密度直达 $A$，所以 $B$ 不密度可达 $C$（也即密度可达不具备对称性）。但是 $B$ 和 $C$ 密度相连（$A$ 密度直达 $B$，$A$ 密度直达 $C$）。
DBSCAN 根据密度可达来进行聚类，具体流程如下：
- 找寻数据集中的核心点，形成集合 $\Omega_1$；
- 如果 $\Omega_1 \neq \text{null}$:
- 从 $\Omega_1$ 中任意选取核心点作为种子点，找出由该核心点密度可达的所有样本点，形成一个簇；
- 将在该簇中的核心点从 $\Omega_1$ 中清除；
- 再从更新后的 $\Omega_1$ 中随机选取一个核心点作为种子点，找出由该核心点密度可达的所有样本点，生成下一个簇；
- 重复以上步骤，直至 $\Omega_1$ 为空。
下图展示了使用 DBSCAN 算法的一个聚类过程示意：
下面的网站链接可以通过交互设置动态展示 DBSCAN 聚类算法的过程和结果。
https://www.naftaliharris.com/blog/visualizing-dbscan-clustering/
1.3.3.2. 小结
以 DBSCAN 算法为代表的基于密度的聚类方法具备以下优点：
- 不用人为设定簇的个数；
- 可以在聚类的同时发现异常点，对数据集中的异常点不敏感；
- 能发现任意形状的空间聚类，如能识别 “非球形” 的簇，而 K-Means 算法这种基于距离的聚类方法只能找出球状的簇；
- 聚类结果不依赖于遍历的初值选取，而 K-Means 算法的初始值对聚类结果有很大影响。