DBSCAN聚类算法的原理、步骤和优缺点_dbscan聚类算法原理

1、DBSCAN聚类算法的原理

由密度可达关系导出最大密度相连的样本集合（聚类）。这样的一个集合中有一个或多个核心对象，如果只有一个核心对象，则簇中其他非核心对象都在这个核心对象的ε邻域内；如果是多个核心对象，那么任意一个核心对象的ε邻域内一定包含另一个核心对象（否则无法密度可达）。这些核心对象以及包含在它ε邻域内的所有样本构成一个类。

    那么，如何找到这样一个样本集合呢？一开始任意选择一个没有被标记的核心对象，找到它的所有密度可达对象，即一个簇，这些核心对象以及它们ε邻域内的点被标记为同一个类；然后再找一个未标记过的核心对象，重复上边的步骤，直到所有核心对象都被标记为止。

    算法的思想很简单，但是我们必须考虑一些细节问题才能产出一个好的聚类结果：

    首先对于一些不存在任何核心对象邻域内的点，再DBSCAN中我们将其标记为离群点（异常）；

    第二个是距离度量，如欧式距离，在我们要确定ε邻域内的点时，必须要计算样本点到所有点之间的距离，对于样本数较少的场景，还可以应付，如果数据量特别大，一般采用KD树或者球树来快速搜索最近邻，不熟悉这两种方法的同学可以找相关文献看看，这里不再赘述；

第三个问题是如果存在样本到两个核心对象的距离都小于ε，但这两个核心对象不属于同一个类，那么该样本属于哪一个类呢？一般DBSCAN采用先来后到的方法，样本将被标记成先聚成的类。

2、DBSCAN聚类算法的步骤

输入：数据集D={x1，x2，x3，...，xN}，邻域参数（ϵ，MinPts）

输出：簇划分C={C1,C2,...,Ck}

算法步骤如下： 

（1）初始化核心点集合为空集：Ω=空集

（2）寻找核心点：遍历所有的样本点xi, i=1,2,...,N，计算Nϵ(xi)，如果 

         |N(xi)|≥MinPts，则Ω=Ω ⋃{xi}

（3）迭代：以任一未访问过的核心点为出发点，找出有其密度可达的样本生成的聚类簇，直到所有的核心点都被访问为止。

sklearn中的DBSCAN主要参数：

eps：ϵ参数，用于确定邻域大小。

min_samples：MinPts参数，用于判断核心点。

具体如图：

 3、DBSCAN聚类算法的优缺点

优点：

1）可以对任意形状的稠密数据集进行聚类，相对的，K-Means之类的聚类算法一般只适用于凸数据集。

2）可以在聚类的同时发现异常点，对数据集中的异常点不敏感。

3）聚类结果没有偏倚，相对的，K-Means之类的聚类算法初始值对聚类结果有很大影响。

缺点：

1）如果样本集的密度不均匀、聚类间距差相差很大时，聚类质量较差，这时用DBSCAN聚类一般不适合。

2）如果样本集较大时，聚类收敛时间较长，此时可以对搜索最近邻时建立的KD树或者球树进行规模限制来改进。

3）调参相对于传统的K-Means之类的聚类算法稍复杂，主要需要对距离阈值ϵ，邻域样本数阈值MinPts联合调​​​​​​​