DBSCAN聚类原理

DBSCAN（Density-Based Spatial Clustering of Applications with Noise）聚类算法，它是一种基于高密度连通区域的、基于密度的聚类算法，能够将具有足够高密度的区域划分为簇，并在具有噪声的数据中发现任意形状的簇。

基本概念：

minPts = 3

基于密度的聚类中的密度可达和密度相连性

由上图可看出m,p,o.r 都是核心对象，因为他们的内都只是包含3个对象。

1.对象q是从m直接密度可达的。对象m从p直接密度可达的。

2.对象q是从p（间接）密度可达的,因为q从m直接密度可达，m从p直接密度可达。

3.r和s是从o密度可达的，而o是从r密度可达的，所有o,r和s都是密度相连的。

DBSCAN聚类算法原理的基本要点：

1.DBSCAN算法需要选择一种距离度量，对于待聚类的数据集中，任意两个点之间的距离，反映了点之间的密度，说明了点与点是否能够聚到同一类中。由于DBSCAN算法对高维数据定义密度很困难，所以对于二维空间中的点，可以使用欧几里德距离来进行度量。

2.DBSCAN算法需要用户输入2个参数：一个参数是半径（Eps），表示以给定点P为中心的圆形邻域的范围；另一个参数是以点P为中心的邻域内最少点的数量（MinPts）。如果满足：以点P为中心、半径为Eps的邻域内的点的个数不少于MinPts，则称点P为核心点。

3.DBSCAN聚类使用到一个k-距离的概念，k-距离是指：给定数据集P={p(i); i=0,1,…n}，对于任意点P(i)，计算点P(i)到集合D的子集S={p(1), p(2), …, p(i-1), p(i+1), …, p(n)}中所有点之间的距离，距离按照从小到大的顺序排序，假设排序后的距离集合为D={d(1), d(2), …, d(k-1), d(k), d(k+1), …,d(n)}，则d(k)就被称为k-距离。也就是说，k-距离是点p(i)到所有点（除了p(i)点）之间距离第k近的距离。对待聚类集合中每个点p(i)都计算k-距离，最后得到所有点的k-距离集合E={e(1), e(2), …, e(n)}。

4.根据经验计算半径Eps：根据得到的所有点的k-距离集合E，对集合E进行升序排序后得到k-距离集合E’，需要拟合一条排序后的E’集合中k-距离的变化曲线图，然后绘出曲线，通过观察，将急剧发生变化的位置所对应的k-距离的值，确定为半径Eps的值。

5.根据经验计算最少点的数量MinPts：确定MinPts的大小，实际上也是确定k-距离中k的值，DBSCAN算法取k=4，则MinPts=4。

6.另外，如果觉得经验值聚类的结果不满意，可以适当调整Eps和MinPts的值，经过多次迭代计算对比，选择最合适的参数值。可以看出，如果MinPts不变，Eps取得值过大，会导致大多数点都聚到同一个簇中，Eps过小，会导致一个簇的分裂；如果Eps不变，MinPts的值取得过大，会导致同一个簇中点被标记为离群点，MinPts过小，会导致发现大量的核心点。

我们需要知道的是，DBSCAN算法，需要输入2个参数，这两个参数的计算都来自经验知识。半径Eps的计算依赖于计算k-距离，DBSCAN取k=4，也就是设置MinPts=4，然后需要根据k-距离曲线，根据经验观察找到合适的半径Eps的值，下面的算法实现过程中，我们会详细说明。

对于算法的实现，首先我们概要地描述一下实现的过程：

1.解析样本数据文件

2.计算每个点与其他所有点之间的欧几里德距离

3.计算每个点的k-距离值，并对所有点的k-距离集合进行升序排序，输出的排序后的k-距离值

4.将所有点的k-距离值，在Excel中用散点图显示k-距离变化趋势

5.根据散点图确定半径Eps的值

6.根据给定MinPts=4，以及半径Eps的值，计算所有核心点，并建立核心点与到核心点距离小于半径Eps的点的映射

7.根据得到的核心点集合，以及半径Eps的值，计算能够连通的核心点，并得到离群点

8.将能够连通的每一组核心点，以及到核心点距离小于半径Eps的点，都放到一起，形成一个簇

9.选择不同的半径Eps，使用DBSCAN算法聚类得到的一组簇及其离群点，使用散点图对比聚类效果

算法流程

缺点：

（1）当数据量增大时，要求较大的内存支持I/O消耗也很大；

（2）当空间聚类的密度不均匀、聚类间距差相差很大时，聚类质量较差。

内容来源：

1.http://shiyanjun.cn/archives/1288.html

2.http://www.cnblogs.com/aijianiula/p/4339960.html