合肥网站建设百姓网,延安免费做网站公司,电商运营培训班,网站建设的报价方案目录 背景DBSCAN算法DBSCAN算法原理DBSCAN算法基本步骤DBSCAN算法调优DBSCAN算法优缺点参考文献 背景
如果有车队在某一片区域经常规律性作业#xff0c;现在要让你来绘制这一片的路网#xff0c;你会选择让一辆车从头到尾把所有路网跑一遍还是基于历史轨迹点通过技术手段构… 目录 背景DBSCAN算法DBSCAN算法原理DBSCAN算法基本步骤DBSCAN算法调优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 M i n P t s : N d^2: S MinPts:N d2:SMinPts:N
其中 d 2 d^2 d2为边长为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算法聚类效果依赖与距离公式选取实际应用中常用欧式距离对于高维数据存在“维数灾难”。
参考文献
1DBSCAN的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
4DBSCAN聚类算法原理总结 https://mp.weixin.qq.com/s?__bizMzU1MjY4MTA1MQmid2247615480idx4sna7789b16571c3fbab240b5c1fa5898cfchksmfbfd28cccc8aa1da4d4064be011563c5f82f885083b9fbecd97144c245e06ac1b1b495764ef5scene27
