聚类算法之DBSCAN

42 sec read

K-Means算法Mean Shift算法都是基于距离的聚类算法,基于距离的聚类算法的聚类结果是球状的簇,当数据集中的聚类结果是非球状结构时,基于距离的聚类算法的聚类效果并不好。

与基于距离的聚类算法不同的是,基于密度的聚类算法可以发现任意形状的聚类。在基于密度的聚类算法中,通过在数据集中寻找被低密度区域分离的高密度区域,将分离出的高密度区域作为一个独立的类别。DBSCAN(Density-Based Spatial Clustering of Application with Noise)是一种典型的基于密度的聚类算法。

DBSCAN算法原理

DBSCAN(Density-Based Spatial Clustering of Applications with Noise,具有噪声的基于密度的聚类方法)是一种基于密度的空间聚类算法。该算法将具有足够密度的区域划分为簇,并在具有噪声的空间数据库中发现任意形状的簇,它将簇定义为密度相连的点的最大集合。

在DBSCAN算法中将数据点分为三类:

  • 核心点(Core point)。若样本x_i\varepsilon邻域内至少包含了MinPts个样本,即N_{\varepsilon }(X_i)\geq MinPts,则称样本点x_i为核心点。
  • 边界点(Border point)。若样本x_i\varepsilon邻域内包含的样本数目小于MinPts,但是它在其他核心点的邻域内,则称样本点x_i为边界点。
  • 噪音点(Noise)。既不是核心点也不是边界点的点

在这里有两个量,一个是半径Eps(\varepsilon),另一个是指定的数目MinPts。

在DBSCAN算法中,还定义了如下一些概念:

  • 密度直达(directly density-reachable):我们称样本点 p 是由样本点 q 对于参数 {Eps,MinPts} 密度直达的,如果它们满足 p∈NEps(q) 且 |NEps(q)|≥MinPts (即样本点 q 是核心点)
  • 密度可达(density-reachable):我们称样本点 p 是由样本点 q 对于参数{Eps,MinPts}密度可达的,如果存在一系列的样本点 p1,…,pn(其中 p1=q,pn=p)使得对于i=1,…,n−1,样本点 pi+1 可由样本点 pi 密度可达
  • 密度相连(density-connected):我们称样本点 p 与样本点 q 对于参数 {Eps,MinPts} 是密度相连的,如果存在一个样本点 o,使得 p 和 q 均由样本点 o 密度可达。

基于密度的聚类算法通过寻找被低密度区域分离的高密度区域,并将高密度区域作为一个聚类的“簇”。在DBSCAN算法中,聚类“簇”定义为:由密度可达关系导出的最大的密度连接样本的集合。

DBSCAN算法流程

在DBSCAN算法中,有核心对象出发,找到与该核心对象密度可达的所有样本形成“簇”。DBSCAN算法的流程为:

  • 根据给定的邻域参数Eps和MinPts确定所有的核心对象
  • 对每一个核心对象
    • 选择一个未处理过的核心对象,找到由其密度可达的的样本生成聚类“簇”
  • 重复以上过程

伪代码:

Python实现:

DBSCAN的参数选择

MinPts

这个参数建议根据数据量及具体的业务进行自行设定

Eps

《Python机器学习算法》这本书上给出了一个计算公式,但是没有解释中间的原因,并不清楚理论依据是什么,算法如下:

其他参考资料:

Scikit-learn中的DBSCAN的使用

主要函数介绍:

核心参数:

  • eps: float,ϵ-邻域的距离阈值
  • min_samples :int,样本点要成为核心对象所需要的 ϵ-邻域的样本数阈值

其他参数:

  • metric :度量方式,默认为欧式距离,可以使用的距离度量参数有:
  • algorithm:近邻算法求解方式,有四种:
    • “brute”蛮力实现
    • “kd_tree” KD树实现
    • “ball_tree”球树实现
    • “auto”上面三种算法中做权衡,选择一个拟合最好的最优算法。
  • leaf_size:使用“ball_tree”或“kd_tree”时,停止建子树的叶子节点数量的阈值
  • p:只用于闵可夫斯基距离和带权重闵可夫斯基距离中p值的选择,p=1为曼哈顿距离, p=2为欧式距离。如果使用默认的欧式距离不需要管这个参数。
  • n_jobs :CPU并行数,若值为 -1,则用所有的CPU进行运算

属性:

  • core_sample_indices_ : 核心点的索引,因为labels_不能区分核心点还是边界点,所以需要用这个索引确定核心点
  • components_:训练样本的核心点
  • labels_:每个点所属集群的标签,-1代表噪声点

使用示例:

执行结果:

DBSCAN优缺点总结

优点:

  • 相比K-Means,DBSCAN 不需要预先声明聚类数量
  • 可以对任意形状的稠密数据集进行聚类,相对的,K-Means之类的聚类算法一般只适用于凸数据集。
  • 可以在聚类的同时发现异常点,对数据集中的异常点不敏感。
  • 聚类结果没有偏倚,相对的,K-Means之类的聚类算法初始值对聚类结果有很大影响。

缺点:

  • 当空间聚类的密度不均匀、聚类间距差相差很大时,聚类质量较差,因为这种情况下参数MinPts和Eps选取困难。
  • 如果样本集较大时,聚类收敛时间较长,此时可以对搜索最近邻时建立的KD树或者球树进行规模限制来改进。
  • 在两个聚类交界边缘的点会视乎它在数据库的次序决定加入哪个聚类,幸运地,这种情况并不常见,而且对整体的聚类结果影响不大(DBSCAN*变种算法,把交界点视为噪音,达到完全决定性的结果。)
  • 调参相对于传统的K-Means之类的聚类算法稍复杂,主要需要对距离阈值eps,邻域样本数阈值MinPts联合调参,不同的参数组合对最后的聚类效果有较大影响。
打赏作者
微信支付标点符 wechat qrcode
支付宝标点符 alipay qrcode

K-近邻算法KNN学习笔记

什么是K-近邻算法? K近邻法(k-nearest neighbor, k-NN)是1967年由Cover T
2 min read

使用Prophet进行时间序列预测

Prophet是Facebook开源的预测工具,相比ARIMA模型,Prophet真的是非常的简单。只要读入两
1 min read

采用时间序列预测股价变化

时间序列简介 在数学上,随机过程被定义为一族时间随机变量,即{x(t),t∈T},其中T表示时间t的变动范围。
5 min read

One Reply to “聚类算法之DBSCAN”

  1. 博主您好,DBSCAN笑脸的动图,是怎么实现的?

发表评论

电子邮件地址不会被公开。 必填项已用*标注