本文参考自：基于密度聚类的DBSCAN和kmeans算法比较

根据各行业特性，人们提出了多种聚类算法，简单分为：基于层次、划分、密度、图论、网格和模型的几大类。

相比其他的聚类方法，基于密度的聚类方法可以在有噪音的数据中发现各种形状和各种大小的簇。DBSCAN（Ester, 1996）是该类方法中最典型的代表算法之一（DBSCAN获得2014 SIGKDD Test of Time Award）。

1. 算法原理

下图展示了DBSCAN的工作过程。详细原理请移步：基于密度的聚类方法 Density-based clustering。

1. 首先，发现密度较高的点，然后把相近的高密度点逐步都连成一片，进而生成各种簇。算法实现上就是，以每个数据点为圆心，以eps为半径画个圈（称为邻域eps-neigbourhood），然后数有多少个点在这个圈内，这个数就是该点密度值；
2. 接着，选取一个密度阈值MinPts，如圈内点数小于MinPts的圆心点为低密度的点，而大于或等于MinPts的圆心点高密度的点（称为核心点Core point）。如果有一个高密度的点在另一个高密度的点的圈内，我们就把这两个点连接起来，这样我们可以把好多点不断地串联出来；
3. 如果有低密度的点也在高密度的点的圈内，把它也连到最近的高密度点上，称之为边界点；
4. 所有能连到一起的点构成了一个簇，而不在任何高密度点的圈内的低密度点就是异常点。

2. 场景分析

2.1 场景一

假设有如下图的一组数据。

 

用密度聚类DBSCAN方法，可以看到聚类效果如下：

同样，请读者看下k-means的聚类效果。

由此可见：对于簇形状不规则的数据，像k-means（聚类分析: k-means算法）这种基于划分的方法就不再适用了，因为划分方法（包括层次聚类算法）都是用于发现“球状簇”的。

2.2 场景二

 假设有如下一组数据。

用k-means聚类效果如下。

用dbscan算法聚类效果如下。

注意观察两个算法的不同之处：

1. dbscan是基于密度计算聚类的，会剔除异常（噪声点）。如上图中的类别0，就是dbscan算法聚类出的噪声点（不是核心点且不再核心点的邻域内）。
2. k-means需要指定k值，并且初始聚类中心对聚类结果影响很大。
3. k-means把任何点都归到了某一个类，对异常点比较敏感。

所以，不同的数据集和场景，需要运用不同的聚类算法。

3. 算法实现

其中，DBSCAN方法对参数eps和MinPts敏感。  

在这个算法框架中，NEps(x, D)表示数据集D中包含在对象x的Eps-邻域范围内的所有子对象。card(N)表示集合N的基数，即集合N中包含的元素的个数。在簇扩展过程中采用了栈结构，用于压栈当前对象x的所有邻居对象，再递归地判断栈成员是否满足核心对象条件，从而决定是否进一步扩展。