基于spark的dbscan算法实现

算法

通过dbscan算法对定位数据进行聚簇处理。关于dbscan算法有如下详细的解释：https://www.cnblogs.com/pinard/p/6208966.html

实验

在没有找到dbscan算法与使用spark时，有一种实现方式：遍历所有的定位数据，根据之前设定的点距值，将满足点距的点进行聚合形成簇，同时在遍历下一个点的时候先对已有的簇进行运算，满足则放入，不满足则放入新簇，最后则会形成许多簇，这样的簇可以通过二次点距运算计算再进行过滤，或者直接进行过滤则找出了所有的聚簇。此算法的核心就是通过不断聚合由大到小的点距形成的簇，由大簇分离成更加精细的小簇，从而找到满足要求的簇群
*代码已放入源码的spark目录中，文件名为eairlv.py

优化

之前的个人算法在聚簇时核心仅为点距，并且使用“满足则放入，不满足则放入新簇”的规则的情况下，因为簇与簇之间没有动态的合并聚合，这样会因为遍历点的顺序的不一致出现不同的结果，因为当各个簇中的点不断增多并向周边扩散的时候，在满足一定的条件下，簇与簇之间应该合并成一个新簇，于是在“满足则放入”后增加“并对比其他簇，如果此点也在另一个簇中，则将这两个簇进行合并，形成一个新簇”。但是这样的合并方法，仅凭一个点就将两个簇进行了合并，这样离散的点（类似道路运动轨迹），很有可能会出现聚集在同一簇中，另外，簇中的点无法区分其密度关系，为了能够更合理的控制合并方法与更明确的簇密度，就寻找了dbscan算法，具体原理请详见第一段

流程设计

dbscan调度器接收需要计算的定位数据，并将数据以文件方式放入spark的运行环境中，然后发送shell命令启动spark，并由spark的脚本文件将计算结果通过http放回给dbscan调度器

环境

安装docker的spark(sequenceiq/spark)，并将dbscan调度器安装至相同的宿主机，保证spark环境与调度器的指令与数据的互通

改进

在上线后，发现当spark返回数据量过大时，返回数据无法接收完全导致程序卡死，于是将返回方式从http改成了文件方式

代码

https://gitee.com/eairlv/project/tree/master/dbscan

优化

使用dbscan算法后，生成的聚簇数据需要精简，于是就想了一个聚簇描边算法（滚雪球算法）：

• 通过dbscan算法对定位点进行聚簇运算

• 将聚簇结果进行描边优化

  • 制定描边初始点及方向（默认寻找最低点，并以坐标轴四象限0度至360度且基于聚簇算法的距离阈值进行扫描）
  • 找到扫描出的第一个的点，再以上一点连接此点的坐标角度加上180度作为此点起始扫描角度进行扫描，之后重复此步骤，直到首尾均为同一个点
    由于向量的夹角只能0-180度，因此要实现0-360扫描需要通过确定的当前圆心点与前一点连线的斜率判断所有扫描点位于连线的上方或下方（待确定点投影在当前圆心点与前一点连线上，为上方），如果位于上方则需要用360减去计算出的角度（意味着不仅仅需要计算与扫描点的角度还需要计算其向量方向，因为向量夹角最大只有180度）