【高中生讲机器学习】19. 各种经典聚类算法，一篇带你过完！（上）

创建时间：2024-09-11
首发时间：2024-09-23
最后编辑时间：2024-09-23
作者：Geeker_LStar

你好呀~这里是 Geeker_LStar 的人工智能学习专栏，很高兴遇见你~
我是 Geeker_LStar，一名高一学生，热爱计算机和数学，我们一起加油~！
⭐(●’◡’●) ⭐

嗯…之前三篇一直在讲非常让人头大的主成分分析 PCA（）上一篇的末尾我说这一篇要讲一些简单的东西…so 我们来讲聚类吧（（（）感觉它是最简单的无监督学习算法了（）

（虽然这篇刚开始写，但是我已经在想下一篇了，下一篇我要上强度（（~~（什么玩意（~~

那我们开始吧!!

文章目录

聚类算法概述
距离和相似性度量
原型聚类
层次聚类
密度聚类

聚类算法概述

嗯，由于我不知道怎么开场 so 先放个图：（（

聚类结果

可以看到，这个图上的数据按照距离的远近被分到了不同的类。
这种按照数据间的距离或相似性将数据分到不同的簇的算法就是聚类算法。

注意啦，聚类和分类不一样，聚类算法是无监督学习算法（而分类算法是监督学习算法），聚类算法的数据是没有标签的。

聚类算法是一个蛮笼统的称呼，它下面有很多具体的分支，比如：

原型聚类
层次聚类
密度聚类
谱聚类
模型聚类

这篇文章会讲前三个聚类类型，谱聚类我会在下一篇或下下一篇讲!! 模型聚类的代表 GMM 也会单开一篇讲~！
（哦对了，如果你看过这个系列之前几篇的话，我要告诉你一个 “不幸” 的消息是，上一篇中刚刚被我们送走的 EVD 在谱聚类中又会回来找我们（）（））

距离和相似性度量

嗯，前面都说了，聚类算法的核心就是数据间的距离或相似性，那么，我们显然需要一个指标来衡量数据间的距离或相似性，不同的衡量方式可能会带来不同的结果。

另外，距离和相似性通常是反向变化的，即距离越大，相似性越小。
关于距离和相似性的度量方法，我在前面的文章中已经有了比较详细的介绍，下面是链接：

这篇里面讲了距离度量的方法：诶嘿（）

这篇里面讲了相似性度量的方法（相关系数）：诶嘿嘿嘿嘿（）

（好吧，主要是我最近太忙了，我之前说过要专门写一篇讲距离和相似性度量的来着（（（）（放心会写的!!!）

但是，注意了，为什么说距离 / 相似性度量的方法的选择在聚类中如此重要，这是因为，选择不同的度量方法有可能不同的结果，甚至是相反的结果。
for example，下图：

相反的结果

（噗哈哈哈其实是我画的（（（）

在这个图中，如果计算距离，那么 A 和 B 距离更近，即 A 和 B 更相似；但是如果计算相关系数，那么 A 和 C 相关系数更大，即 A 和 C 更相似。

so，在聚类算法中，距离 / 相似性度量的选择真的很重要！

（啊，不过，先透露一下，虽然计算方式很多，但是最常用的依然是欧氏距离（）

豪嘟，那么我们来看具体的聚类算法吧！

原型聚类

诶嘿（）或许说起聚类算法，你脑子里第一个蹦出来就是 kmeans，没错它就是原型聚类的代表!

好吧，要讲原型聚类，或许我们先搞明白原型聚类里面这个 “原型” 是什么东西（）
原型聚类，英文 prototype clustering，emm prototype 翻译过来就是原型的意思，我们貌似不能从英文释义中得到更加 makes sense 的 interpretation。so 还是直接说吧（（

原型，是指原型聚类中每个类的中心点或代表点。或者说，原型聚类就是利用这些中心点/代表点（也就是原型）来进行聚类，每个待聚类的样本点都会被聚到距它最近那个原型所代表的那个类。

其实原型聚类真的很简单，so 我们直接来看算法好吧，kmeans 启动!!

firstly，最开始我们就说过了，聚类算法的一大目标就是 “使类内距离之和最小，类间距离之和最大”。kmeans 算法主要 “遵照” 前半句话，通过最小化类内距离之和来进行聚类。

你可能会想，这不简单嘛，直接暴力计算距离不就可以了嘛（）啊没错这其实是一种思路，不过我们先来看看，如果从纯数（暴）学（力）的角度看 “最小化类内距离之和”，会发生什么（）
（提前说明，可不只是时间开销大那么简单喔~

我们先来规定一些 notation（以防后面我滥用符号（doge））：
给定 $N$ 个样本的集合 $X=\{x_1, x_2, ..., x_n\}$ ，每个样本由一个 $m$ 维的向量表示（即有 $m$ 个特征），kmeans 的目的是把这 $N$ 个样本聚到 $k$ 个不同的类中（显然 $k < N$ ）。
我们前面说过，kmeans 是一种硬聚类模型，即每一个样本只能严格属于一个类。so 最终分成的 $k$ 个类 $G_1, G_2, ..., G_k$ 可以表示为： $G_i \cap G_j = \varnothing, \cup_{i=1}^{k}G_i=X$ ，即每个数据点都属于且仅属于一个类。

豪德，我们要干什么来着的，哦，我们要让所有类的类内距离之和（就是类内距离之和的和）最小。

首先我们需要确定使用哪种距离度量函数，嗯虽然前面讲了很多，但是其实用的最多的还是欧几里得距离，就是我们最熟悉的那种。kmeans 用的也是欧式距离，只不过加了个平方（相当于没有欧氏距离里开根号那步），so 在 kmeans 中，两个数据点的距离计算方式如下：
$d(x_i, x_j)= \parallel x_i-x_j \parallel^2$

嗯，然后，kmeans 计算的是 “类内距离” 是指类中的每个数据点到类的原型，或者说质心（也就是类内所有数据点的坐标的均值构成的那个点）的距离。对于 kmeans 中的原型（质心）先理解到这就可以，后面还会提到。

因为要让类内距离之和的和最小嘛，so 我们来表示一下这个和：
$\sum_{l=1}^{k}\sum_{C(i)=l}\parallel x_i-\mu_l\parallel^2$

其中， $C$ 聚类函数（或者说一种聚类方案）， $C (i)$ 给出数据点 $i$ 属于的类， $l$ 代表一个类，一共有 $k$ 个。内层的 sigma 表示某一个类内的类内距离，也就是类内所有点到类的原型（质心）的距离，二外层的 sigma 表示把所有类的类内距离加起来，也就是求全局（所有类）的类内距离。

这就是我们要最优化的式子。或者说，我们要做的就是求解下面这个最优化问题：
$\underset{C}{\text{arg min}}\sum_{l=1}^{k}\sum_{C(i)=l}\parallel x_i-\mu_l\parallel^2$

嗯，从纯数学角度来讲，当最相似的样本被聚到同类时，损失函数的值最小，所以直接最小化这个函数肯定是可以找到最优解的。
但是，回到开始的那个问题，为什么直接（利用纯数学方法）最优化是行不通的呢？

okay，或许我们得先观察一下这个式子。
这个式子中的每一个值都会因为聚类方案（映射函数） $C$ 的变换而变换，so 我们没有办法直接通过偏导等方式求出最优解（因为 $C$ 不是一个连续的函数，它只是代表一种从数据点到类别的映射），我们只能遍历所有的情况，挨个比较，最终找到让整个函数值最小的 $C$ 。

好吧，那就算呗（） $N$ 个样本分到 $k$ 个类，类内的顺序不重要。
这是啥，这其实是…第二类斯特林数…（）（啊对，不是组合数）
不过我们暂时先不管这个东西（我记得它在信息奥赛还是哪里出现过，蛮有趣的，但是不是这里的重点）。

一共的分法数量如下：
$\frac{1}{k!}\sum_{l=1}^k(-1)^{k-l}( \ ^k_l \ )l^n$

嗯，豪德，现在指数出现了（）指数的出现通常不是什么好兆头（（（

确切的说，因为一共的分法数量是用指数来表示的，而我们需要遍历完所有的分法才能确定最终要选择哪个，所以我们也需要遍历指数多种分法，再深入一点就是，我们需要的时间复杂度是指数级别的。

嗯。。。《非多项式级别的时间复杂度》
显然，这玩意已经不是一个 P 问题了，确切的说，这玩意是一个 NP-hard 问题。

豪德（）对于这个问题，我们显然是不可能在多项式时间内找到它的解了。
并且，由于它是一个 NP-hard 问题，所以我甚至不确定我们能否在多项式时间内验证它的解。

嗯。。。这下就回答了前面那个问题了。
显然，纯数学上的优化是行不通了，所以我们必须通过迭代来求解这个问题。

不过，迭代可就不能保证我们找到最优解了。

那我们来看看迭代的解法吧！

首先，kmeans 需要我们告诉它，一共需要把原始的 $N$ 个数据点聚成几个类（显然类的个数需要小于等于原始数据点的个数），比如说就 $k$ 个吧。（这块和上面说的一样

then，kmeans 在原始的 $N$ 个数据点中任意选择 $k$ 个，作为最初的原型。或者说，这 $k$ 个点（原型）就代表着 $k$ 个类。

豪德，接下来到了计算距离的步骤了，依然是计算欧式距离的平方。

so 我们计算剩下的 $N - k$ 个点和 $k$ 个原型之间的欧氏距离，并且把它们和距离最近的原型标记为同一类。

到现在为止都很好理解吧，没事后面也会很好理解（）

豪德现在所有的数据点都已经有类别了，或者说，每个数据点都已经被分到了由一个原始的原型所代表的类中。

and then??

yes，现在我们得到的只是一个初始聚类的结果，但是这个结果大概率不具有太多的科学性（）因为我们的初始原型只是随便选的。所以显然，我们需要进一步更新我们的聚类结果。

well，怎么更新捏（）显然我们需要选择新的原型，让新的原型可以更好地刻画每一个类的特征。

前面说了，kmeans 的思路是让 “类内距离最小化”，这其实已经告诉我们应该怎么更新原型了。
——让原型的坐标等于原型所代表的类中所有点的坐标的平均值。

Ok，虽然这看起来比较 make sense 但是我们还是需要放一个证明在这里。

啊现在每个类里面的数据都是已知的，假设这个类中共有 $p$ 个数据（坐标点），那我们要做的就是，求出到这 $p$ 个点的距离之和最小的那个点的坐标，设为 $x_c$ 。

ok，我们首先写出距离之和的式子：
$\sum_{i=1}^{p}\parallel x_i-x_c \parallel^2$

well，不要被这个字母 $x$ 迷惑了，它不是一个值，它是一个坐标向量。

我们要求出让这个式子最小的 $x_c$ 的值，这个式子只有一个极值点，即它的全局最小值，so 我们直接对 $x_c$ 求偏导并让偏导等于 0 就可以了。

$\frac{dL}{d\mu} = \sum_{i=1}^{n} 2(x_i - x_c)(-1) = -2 \sum_{i=1}^{n} (x_i - x_c)$

让偏导等于 0，得到：
$\sum_{i=1}^{n} (x_i - x_c) = 0 \\ \sum_{i=1}^{n} x_i - nx_c = 0$

最终得到使得类内距离之和最小的点的坐标 $x_c$ ：
$nx_c = \sum_{i=1}^{n} x_i \quad \Rightarrow \quad x_c = \frac{1}{n} \sum_{i=1}^{n} x_i.$

注意，在 kmeans 中，原型只是一个 “代表”，它不一定要是真实的数据点（或者说按照上面说的更新原型的方法计算出来，它很大概率都不会是一个真实的数据点），它只是代表某个类的平均情况（所以叫中心点嘛）。

豪德，现在我们已经更新了原型，然后捏（）
更新原型之后，一些数据点所属的类很可能会发生变换（因为最初的原型是随机选择的，所以聚类也没有什么依据），so 我们需要按照新的原型重新对这些数据点进行聚类。也就是说，看所有的数据点到新的原型的欧式距离，并把它们分到距离最近的那个原型所代表的类中。

然后，一直重复【按照新的聚类结果计算新的原型——按照新的原型对数据点重新聚类】这个步骤，直到所有的数据点所属的类别都不再发生变化。

嗯！这个就是 kmeans 算法的流程图！

kmeans 算法流程

嗯…你或许对 kmeans “为什么有用” 有很多疑问，它看起来挺 make sense 的，可是没有严格的数学证明来证明它的有效性。

没错，的确是这样的，kmeans 算法是一种迭代式的方法，通过减小簇内平方和来逐步迭代优化聚类结果，但是没有严格的数学证明来表示它一定能找到令人满意的结果，这主要是由三点原因决定的：

第一，聚类数量的不确定性。其实在 kmeans 中，最重要的因素就是它的聚类数量，这个数量是需要人为规定的，如果这个数量规定得恰好和实际的类的数量一样，那或许最终的结果会不错；但是如果这个数量设置的不太对，那最终的结果也会受到不小的影响（比如有两个明显不同的类被分到了一起，因为人为指定的聚类数量太少）。
针对这个问题，其实没有什么特别好的解决办法。有一个叫做 scree plot 的东西可以稍稍帮助一下，但是这会导致比较大的时间开销（）（）。

第二，初始原型选择的随意性。
在 kmeans 中，初始原型的选择是很随意的，或者说这个选择很难给我们带来什么有用的信息。但是 kmeans 还偏偏就非常依赖这些原型，所以如果初始原型选择的好（比如说比较分散，正好分别落在几个类中），那最终的聚类结果会比较好，甚至迭代一次就收敛了；但是如果初始原型选择的不好（比如都聚集在一个类里面），那么可能需要迭代很多次，甚至收敛后的结果也不会太好。
针对这个问题，有人提出了一种叫做 kmeans++ 的算法，后面会简单提一下。

第三，对原始数据形状的要求。
先上图！

kmeans 算法对聚类形状的要求

图中展示了 kmeans 算法对不同形状数据集的聚类结果，可以看到，kmeans 只有对倒数第二行（近似于圆形）的数据的聚类结果较好，而对其它形状的数据集的聚类效果都不理想。

没错，kmeans 算法只有在原始数据是凸的、对称的且近似于圆形的时候才能取得较好的性能，这点其实能从它更新聚类中心的式子中看出来。kmeans 将聚类中心更新为类中所有点的坐标的平均值，这个计算方式只有在类的形状是对称的的时候才是有效的（如果类的形状是接近对称的，这个点就可以看作类的几何中心），而如果类的形状不是对称的，这个点在几何上就没有任何意义了，也就不太能反映真实的类的分布了（因为其实聚类可以看作是寻找几何上的连续性）。
还有一个点，kmeans 算法在处理非圆形数据集的时候，最终的聚类结果也会接近于圆形，图中也有体现。

So，对于非凸的或具有不规则形状的数据集，我们一般使用 DBSCAN 算法来处理，这个算法会在后面讲到。（哦对了，这个图其实有个完整版，我会放在最后面。

豪嘟那我们现在来说一说 scree plot 选择 $k$ 值以及 kmeans++ 选择初始原型。

其实 scree plot 在前一篇主成分分析里面有讲过，大概是这样一个图：

原型聚类 scree plot

嗯，这个图的横坐标代表了类的数量，纵坐标代表了所有类的类内距离之和（忽略那个 eigenvalue）。

我们只需要找到这个图上的 “拐点” 在哪里，就可以了，拐点对应的类的数量通常就是最佳的类的数量。比如对于这个图，虽然没有那么明显的拐点，但是可以看到在 7-8 个类的时候方差已经开始收敛了，so 可能 7-8（或者再往后两个）就是比较合适的聚类数量，当然也可以多找几个试试。

嗯…听起来好对的样子，但是为什么？
这应该很 make sense 吧，在到达最佳的类（或者说实际的类）数之前，总会有一些点被分到不属于的类，或者说被分到距离较远的类，导致类内距离之和较大；而在到达最佳的类数时，每个点都被分到属于的类，类内距离减小；而当我们继续增加类的数量的时候，会有一些本来属于一个类的点再次被细分为两个类，类内距离进一步减小；最极端的情况，当类数等于样本数时，每个样本都是一个类，最终类内距离之和为 0.

当然，上面这只是一种最为理想的情况。之前说过，kmeans 算法对初始聚类中心的选择非常敏感，所以如果选择了错误的聚类中心，可能不管分成几类结果都不好，so 我们接下来看一下 kmeans++ 算法，它通过一种启发式的方法寻找初始聚类中心。

（哦对了，总是看到 “启发式的方法” 这个词，但是不清楚到底是什么意思，so 我去查了一下：启发式方法是一种解决问题的策略，它通过应用经验法则、直觉或近似规则，以有效地找到足够好的解决方案，而不是寻求最优解。它通常用于复杂或不确定性高的问题，如 NP-hard 问题，启发式方法可以加速求解过程并降低计算资源的消耗。——上面这段来自 GPT 4o mini((（（（

豪德，那我们继续回到 kmeans++ 算法。

嗯，想让初始条件尽量好，那显然应该让初始的聚类中心相互之间尽量远，这样能够比较好的捕捉潜在的不同类的关系，so kmeans++ 算法其实是在初始聚类中心的选择方法上做了改进（不再是 kmeans 的纯随机了），而后续的步骤和 kmeans 完全一致。

具体来说…
我们假设聚类数量为 $k$ ，样本数量为 $N$ .
首先 kmeans++ 在 $N$ 个点中随机选择一个点作为第一个类的初始中心。
然后，对于剩下的 $N - 1$ 个点，计算它们与第一个点之间的欧氏距离。我们记第 $m$ 个点与第一个点之间的距离为 $D_m$ 。

好的，接下来，kmeans++ 为每一个点（这里以第 $m$ 个点为例）赋予一个权重 $D_m^2$ ，没错就是它到第一个点的欧式距离的平方。

这个权重反映的就是第 $m$ 个点被选为第二个聚类中心点的概率。
换言之，在剩下的 $N - 1$ 个点中，到第一个聚类中心最远的点最有可能成为第二个聚类中心。

嗷但是注意嗷，不是说 kmeans++ 就选择最远的那个，只是最远的那个有最大的权重，所以最可能被选中，这在一定程度上可以保证结果的多样性。

豪德，那么我们继续来看第三个。
第三个点（还是以剩下的 $N - 2$ 个点中的第 $m$ 个点为例）的选择和第二个点很像。首先我们计算 $D_m = \text{min}(D_{m1}, D_{m2})$ ，嗯对，就是这个点到第一个聚类中心和第二个聚类中心的最小距离。然后我们赋给它权重 $D_m^2$ ，反映它成为第三个聚类中心的概率。

okay，这样以此类推到第 $k$ 个，我们就获得了所有初始聚类中心。

和 kmeans 的纯随机选择不同，kmeans++ 的选择方式考虑了距离的影响，它倾向于选择距离较远的点作为初始聚类中心，但同时基于权重的选择方式又保留了一定的多样性，可以通过多次运行找出最优结果。

豪德！那这些就是关于原型聚类的两个（or 一个半？）经典算法！

now 我们来看看针对于原型聚类 “聚类数量不好确定” 的问题，有没有什么可以带给我们一点启发的方法，so 第二部分，层次聚类，启动！

层次聚类

刚刚讲完，kmeans 聚类的初始聚类数量不好确定，选择的聚类数量稍有差别就可能带来完全不同的结果。但是，如果我想直观地看出选择不同的聚类数量时候聚类的结果（并且尝试从这些结果中挖掘一些数据分布的信息），我该怎么办捏（（

豪德，层次聚类就是干这个的（）先不详细解释，先看看下面这张图，这是一个层次聚类的结果。

啊先在这里说一下，层次聚类分为聚合法和分解法，二者的思想是一致的，只是在细节上稍有区别。我们以聚合法作为例子。（下面这张是聚合法的示意图）

层次聚类结果可视化

嗯…看完这张图你是否明白了些什么？~~（那我是不是就不用写了（（（doge doge doge~~

好吧好吧，这张图作为一个引入，讲完你就懂了（）

我们从图的最底部开始看，也就是坐标轴下面。
坐标轴下面的那些文字其实是一个个数据点，它们具有一些特定的特征，我们要对它们进行聚类。

在最开始的时候，每个数据点都是一个类，层次聚类算法每次按照特征合并【距离最近】的两个类（问题 1）。
注意，如果在合并的时候，两个数据点被合并了，那么它们就由两个类合并成为一个类，并在下一次合并的时候作为一个类参与和其它类的距离计算（问题 2）。

层次聚类按照上述规则，不断对距离最近的两个类进行合并，直到满足终止条件（问题 3）。

上面的解释大概描述了层次聚类（聚合法）的流程，我标注了三个问题，如下。

first，用什么距离度量方式？
second，在确定距离度量方式的情况下，“两个类之间的距离” 是什么意思？是指类中心之间的距离，还是最近的距离，还是最远的距离，还是 sth else?
third，终止条件是什么？所有类之间的距离都小于某个值？还是达到特定的聚类数目？

可以说，这三个问题是聚合法层次聚类的三个核心问题，确定了这三个问题的答案，具体的层次聚类流程也就确定了。

well，当然，这三个问题的答案都不唯一，或者说，我在问题后面给出的 choices 都是可以的。在这里我们选择一种，作为示例。

first，我们选择欧式距离作为距离度量方式（啊这个基本上是确定的，基本上都用它）。
second，我们选择两个类之间的最短距离作为两个类之间的距离。
third，我们的终止条件是所有数据点聚为一类（嗯因为这样我们可以看出类数为任意数量时对应的聚类结果）。

豪嘟，现在我们的算法细节已经确定了，我们来看一个例子吧。

层次聚类例子

在这个例子中，我们有六个数据点 ABCDEF，它们是初始的六个类。
经过计算（六个类两两之间比较一次，一共 15 次），B 和 C 之间的距离最小，so 我们首先合并 BC，将它俩看成一个类，现在我们类的数量由六个减少到了五个。

接下来，我们将这五个类两两比较一次，发现 D 和 E 之间的距离最小，so 我们合并 DE，将它俩堪称一个类，现在我们的类的数量由五个减少到了四个。
（注意咯，举个例子，在计算 A 和 BC 类的距离的时候，我们分别计算 A 和 BC 类中的两个点 B、C 的距离，然后选择最小的那个作为 A 和 BC 类的距离，对于后续的计算，也是如此。）

我们目前有 A、BC、DE、F 这四个类，按照前面的计算方法，我们计算出 BC 类和 DE 类之间的距离最小（这个距离是 B 和 D 之间的，B 和 E 之间的，C 和 D 之间的，C 和 E 之间的距离的最小值）。

好的，我觉得现在你应该已经非常明白详细的计算方法了，一直这么计算，直到所有的数据点合并为一类，也即达到终止条件。

好的！现在你已经理解了层次聚类聚合法的详细流程！对于分解法，流程也是一样的。或者说，对于分解法，把上面那张图反过来看就可以了。

一言以蔽之，聚合法层次聚类在【上一次聚类得到的结果】的基础之上进行聚类，每次聚类都遵照相同的步骤和条件，直到终止。

嗯，和原型聚类相似，我们也探讨一下层次聚类的优缺点。
优点在上面的介绍中已经说的差不多了，层次聚类不需要事先指定聚类类数，并且可以给出任意聚类类数下的结果，有助于我们发现数据中存在的层次关系。
同时，层次聚类也可以作为原型聚类的预处理步骤，根据层次聚类的结果选择原型聚类的类别数也是一种思路。
andand，层次聚类因为没有 “更改聚类中心” 的过程，也就不涉及到对于原始数据形状（kmeans 的近似圆形）的要求，层次聚类可以比较好地处理非凸的形状不规则的数据。

这是聚合层次聚类的结果（和 kmeans 用的是一样的数据集）：

聚合层次聚类结果

（哈哈哈哈是不是看着比 kmeans 那个好很多（（）

well，层次聚类的缺点也很显然——它具有很高的时间复杂度，确切的说是 $O(n^3)$ ，这导致它在面对大数据集的时候耗时很长；另外，层次聚类对那三个【核心问题】的答案的选择很敏感（和 kmeans 对给定的聚类数量敏感一样），选择不同的初始条件可能会导致不同的聚类结果。

（嗯，插一句，一般算法对于超参数或类似超参数的条件都是敏感的，包括我们下面要讲到的密度聚类也是）

好的，那我们来看看密度聚类吧！（我感觉我一般比较喜欢用它？）

密度聚类

好好好，我最 pick 的一个算法来了（）
对于它，我打算首先放效果：

DBSCAN 算法结果

怎么说呢（）就是说我觉得它的性能真的很好，而且时间复杂度也没有那么高，而且而且也不用选择初始聚类数量，而且而且而且…。

weeeell 当然我们还是不要带入过多的个人偏好了（）

来讲讲这个算法！

顾名思义，密度聚类，就是按照数据点的密度进行聚类呗（）~~（好的说了约等于没说~~

那么，重点来了，数据点的密度怎么衡量？~~用眼睛吗？~~ （哇我感觉我今天非常 aggressive 啊（（不是），这好像不太好衡量啊…

——so，DBSCAN 非常聪明地把难以量化的密度转换成了容易计算的距离。具体来说，它基于一组邻域参数 $(\epsilon, MinPts)$ 来刻画样本分布的紧密程度。

记住这句话，下面我们来看看 DBSCAN 中的一些重要概念。
先放一下所有的概念以防一会不清楚：

$\epsilon$ 邻域
核心对象、边缘对象、噪声对象
密度直达
密度可达
密度相连

ok，然后我们定义数据集 $D = \{x_1, x_2, ..., x_m\}$ ，来给上面的概念做详细定义。

首先是 $\epsilon$ 邻域。对于某个数据 $x_j \in D$ ，它的 $\epsilon$ 邻域中包含了数据集 $D$ 中与它的距离不大于 $\epsilon$ 的样本，这里我们默认距离使用欧式距离。
举个例子，如果 $\epsilon=1.5$ ，D 中有四个样本 1、2、3、4，那么 3 的 $\epsilon$ 邻域中就包含 2 和 4，因为 3 和它们的距离（都是 1）小于 1.5。

then，三种对象，这三个都很好理解。
firstly，核心对象。如果 $x_j$ 的 $\epsilon$ 邻域中包含的点的数量大于 $M in Pt s$ ，那么 $x_j$ 就是一个核心对象。
说简单点，就是 $x_j$ 周围有没有足够数量的点，如果有，就是核心对象。
secondly，边缘对象。边缘对象是那些自己的 $\epsilon$ 邻域中点的数量少于 $M in Pt s$ 但是在任意一个核心对象的 $\epsilon$ 邻域中的。就是说我们不能通过它再去扩展了，但是它是可以被扩展到的（后面我们会看到，类的扩展是从核心对象开始，到边缘对象结束的）。
thirdly，噪声对象。噪声对象是那些既不属于任意核心对象邻域内的，自己的 $\epsilon$ 邻域内也没有 $M in Pt s$ 个点的。或者说就是既不能被扩展到，也不能自己扩展出去的。

（后面有一张图里面展示了这三种对象）

嗯，然后，下面说的是这些对象之间的关系。

然后，密度直达。这一条涉及到两个点 $x_i$ 和 $x_j$ 。
具体来说，如果 $x_j$ 是一个核心对象（条件 1）且 $x_i$ 在 $x_j$ 的 $\epsilon$ 邻域中，那么就称 $x_i$ 由 $x_j$ 密度直达（条件 2）。
就是说得在核心点的邻域内。

接下来，密度可达。可以把它看作密度直达关系的传递。
对于两个数据点 $x_j$ 与 $x_i$ ，如果存在一条路径
就是说，如果从 $x_j$ 到 $x_i$ 可以用密度直达关系串起来，那么就说 $x_i$ 是由 $x_j$ 密度可达的。
注意嗷，密度可达关系不是对称的，也就是说， $x_i$ 由 $x_j$ 密度可达不代表 $x_j$ 由 $x_i$ 密度可达，比如说 $x_j$ 是核心点但是 $x_i$ 不是核心点的情况。

最后，密度相连，可以把它看作密度可达的扩展。
如果两个数据点 $x_i$ 和 $x_k$ 都由 $x_j$ 密度可达，那么 $x_i$ 和 $x_k$ 密度相连。
密度相连关系是对称的且没有方向的。

豪德，是时候放一张图了（）

DBSCAN 核心概念

（不是这图怎么这么大）

这个图的 $M in Pt s = 3$ （邻域大小未知），也就是说邻域内至少有 3 个数据点的点才算核心对象。
在图中，红色的点是核心对象；黄色的点是边缘对象；蓝色的点是噪声对象。

图中双向的黑色箭头表示双向的密度直达，单向的黑色箭头表示单向的密度直达；从一个箭头出发，顺着箭头方向的一连串都叫密度可达；图中所有红色和黄色的点都是密度相连的。

okay!!! 现在我们已经讲完了所有的核心概念，距离理解 DBSCAN 只差一点点了！

我们来看看 DBSCAN 是怎么做的吧（）其实真的超简单（而且拥有超低时间复杂度）!!!

首先设定 $\epsilon$ 和 $M in Pt s$ 这两个超参数，嗯关于这两个超参数的选择对聚类结果的影响后面会说，现在先不管，就假设我们选到了两个非常完美的超参数。

然后，根据这两个超参数和核心对象的定义，找出所有的核心对象。

现在，我们随机选择一个核心对象，比如 $x_j$ ，对它进行以下操作，我们就获得了第一个类！

all_key_points = [x_k1, x_k2, ..., x_km]    # 存储所有核心点（已经获得）
all_points = []    # 存储类中的所有数据点
key_points = []    # 定义核心点
key_points.append(x_j)    # 在所有核心点中随机选择一个作为开始
for x in key_points:if x not in all_points:    # 如果这个核心点还没有被访问过for neighbor in nhood_dicts{x}:    # 遍历核心点邻域内的所有对象if neighbor in all_key_points:    # 如果邻域内的点是核心点key_points.append(neighbor)    # 加入到核心点列表中，后续遍历else:    # 如果不是核心点（即是边缘点）all_points.append(neighbor)    # 加入到类中所有数据点列表all_points.append(x)    # 操作之后将这个核心点标记为已经访问过，加入到类中所有数据点列表print(all_points)

最终得到的就是第一个类中的所有数据点!!

好了（）光看伪代码是不是感觉还没那么清楚（）我用自然语言描述一下吧（（

首先，对于一个类，我们新建一个 list（list A）存储这个类中的所有点，新建另一个 list（list B）存储这个类中所有需要进一步遍历的点。
now，我们已经有了所有核心点的信息，我们在所有核心点中随机选出一个。
然后，遍历它的邻域，如果它的邻域中有核心点，那么把它邻域内的所有核心点加入遍历清单；如果它的邻域中有非核心点（即边缘点），那么直接把它邻域内的所有边缘点加入 list A. 然后，等到遍历完这个核心点的所有邻域，也把这个核心点加入 list A，再继续遍历 list B 中的其它核心点。重复上述操作，直到 list B 中的所有点都被遍历过。

啊啊啊怎么这么绕（）（）我们简化一下，用一句话来概括就是，DBSCAN 将 “类” 定义为：由密度可达关系导出的最大密度相连样本集合。

这句话怎么理解呢？
首先，为什么要进一步寻找一个核心点的邻域中的其它核心点的邻域，直到到达边缘点？
这不就是在寻找 “密度可达” 关系嘛！（根据定义，由密度直达关系串起来，直到不能再往外串）
then，为什么是最大的密度相连样本集合？
呃因为按照密度可达关系串下去，最终在串上的所有点都是密度相连的（也是根据定义）。

豪德，现在我们就找到了第一个类。

那么怎么找第二个呢？
第二个和第一个大差不差，所以伪代码我就不写了，直接自然语言处理一下就行（（（直接 NLP（

最终，当所有的核心点都被遍历之后，还不属于任何类的点，就被标记为边缘点。

这一套丝滑且相对（层次聚类来讲）快速的流程走下来，就得到了 DBSCAN 优秀的结果！

嗯，但是显然一个算法是必定有缺点的，DBSCAN 的缺点也很明显——它对超参数 $\epsilon$ 和 $M in Pt s$ 选择非常敏感，如果这两个参数出现一点问题，那整个算法就完了（）

enmmm 但是，这两个参数怎么选？

其实都可以参考 scree plot，也可以通过交叉验证的方式（说白了就是多试几次（（（），在这里就不细说啦~

豪德！！！现在这篇中要讲的三个聚类算法都讲完了，是时候把最终的图放出来了！

所有聚类算法结果对比