DBSCAN聚类算法

背景

如果有车队在某一片区域经常规律性作业，现在要让你来绘制这一片的路网，你会选择让一辆车从头到尾把所有路网跑一遍还是基于历史轨迹点通过技术手段构建出路网出来？

前者就像我们的智能穿戴设备记录你晨跑的轨迹，可能绘制出来的路网更加干净，但是、需要另行安排车辆跑路会影响工程进度，如果是自有车辆还好，如果是无车承运人，车子就不受控，在具体跑路的时候为了避免相同路段不重复记录还需要及时插拔车载设备；后者更多像文科生利用已有的素材来做事，更符合数学科学家的身份和做事风格，可能会用到DBScan算法，下面重点介绍一下DBSCAN算法。

DBSCAN算法

DBSCAN是Density-Based Spatial Clustering of Applications with Noise的简称，从名字来看其是专门用来处理空间数据的，并且能够处理噪声点，与k-means算法不同，DBSCAN算法可以处理任意形状分布的数据。DBSCAN算法依赖下面的基本概念

• eps

样本点辐射半径（epsilon,一下简称eps），如果样本点的相互距离小于或等于指定的eps，那么它们在同一邻域。

• MinPts

样本点辐射半径里包含其他样本点的最小数目(MinPts)；

• 核心点

以该点为圆心，如果给定半径eps内含有不少于MinPts数目的点，那么该点就是核心点。

• 边界点

以该点为圆心，如果给定半径eps内含有不超过MinPts数目的点，并且落在核心点的eps半径内。

• 噪声点

不是核心点也不是边界点的点。

• 密度直达

如果P为核心点，Q在P的邻域内，那么称P到Q密度直达。反之不一定成立，即此时不能说Q到P密度直达，除非Q也是核心点，即密度直达不满足对称性。

• 密度可达

如果存在核心点P1,P2,P3,…,Pn，并且P到P密度直达，P1到P2密度直达，…,Pn-1到Pn密度直达，Pn到Q密度直达，则P到Q密度可达。密度可达也不具备对称性。

• 密度相连

如果存在核心点S，使得S到P和Q都密度可达，则P和Q密度相连。密度相连具有对称性，如果P和Q密度相连，那么Q和P也一定密度相连。

DBSCAN算法原理

DBSCAN聚类是将所有样本点分为核心点，边界点和噪声点三类，然后从核心点出发通过密度可达的方式按广度优先(BFS)去索引非噪声点，这定义了一个密度可达的关系，我们知道在数学里的线性空间定义一个关系就可以找一个划分，现在就可以把所有样本点进行划分了，有这种密度可达的关系划分为一簇，这样就聚好类了。

DBSCAN算法基本步骤

1，指定一个半径eps和最小样本点数MinPts，遍历所有数据点，确定其是核心点，边界点还是噪声点；
2，从核心点出发按照密度可达的关系（广度优先搜索（BFS））去搜索，标记所有半径范围内的样本点；
3，对所有核心点循环执行上述操作；

DBSCAN算法调优

• 半径eps和最小样本点数MinPts

作为DBSCAN两个超参，可以结合业务来定，这里给出初始值的确定逻辑，比如在厂内其实不容许跑60km/h的，按这个速度计算一秒钟的路程d，以这个d作为超参半径eps，在计算边长为d的正方形与所有样本点分布的平面四至范围S对比按下面公式来估算超参MinPts，也就是按比例计算这么小方格平均会散落多少个样本点

$$d^2:S=MinPts:N$$

其中，$d^2$为边长为d的正方形面积，S表示所有样本点分布的平面四至范围大小，N为所有样本点数。

确定了初始值之后，以轮廓系数silhouette_score为目标进行gridSearch。

• 轮廓系数

轮廓系数silhouette_score它结合簇内聚集度和簇间的分离度两种因素。对于样本点i来说，

计算 a(i) = average(样本i到所有它属于的簇中其它点的距离)

计算 b(i) = min (样本i到某一不包含它的其他簇最小距离)

那么样本 i 轮廓系数就为：

S ( i ) = b ( i ) − a ( i ) m a x { b ( i ) , a ( i ) } S(i) = \frac{b(i) - a(i)}{max\{b(i) , a(i)\}} S(i)=max{b(i),a(i)}b(i)−a(i)​

可见轮廓系数的值是介于 [-1,1] ，越趋近于1代表内聚度和分离度都相对较优。将所有点的轮廓系数求平均，就是该聚类结果总的轮廓系数。

DBSCAN算法优缺点

• 优点

（1）聚类速度快且能够有效处理噪声点和发现任意形状的空间聚类；

（2）与K-means比较起来，不需要输入要划分的聚类个数,且不要求样本凸分布；

• 缺点

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

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

（3）算法聚类效果依赖与距离公式选取，实际应用中常用欧式距离，对于高维数据，存在“维数灾难”。

参考文献

1，DBSCAN的sklearn官网
https://scikit-learn.org/stable/modules/clustering.html#dbscan

2，认识DBSCAN
https://www.cnblogs.com/sbb-first-blog/p/16514003.html

3，基于DBACAN的道路轨迹点聚类
https://blog.csdn.net/zengbowengood/article/details/131180609

4，DBSCAN聚类算法原理总结
https://mp.weixin.qq.com/s?__biz=MzU1MjY4MTA1MQ==&mid=2247615480&idx=4&sn=a7789b16571c3fbab240b5c1fa5898cf&chksm=fbfd28cccc8aa1da4d4064be011563c5f82f885083b9fbecd97144c245e06ac1b1b495764ef5&scene=27