DBSCAN聚类算法
1、算法原理
DBSCAN(Density-Based Spatial Clustering of Applications with Noise，具有噪声的基于密度的聚类方法)是一个有代表性的基于密度的空间聚类算法。它将类定义为密度相连的点的最大集合，通过在样本空间中不断寻找最大集合从而完成聚类。该算法在带噪声的样本空间中发现任意形状的聚类并排除噪声。
2、DBSCAN算法涉及的基本定义：
ϵ \epsilon ϵ 邻域：对于p i p_i p i ∈ \in ∈ D，其ϵ \epsilon ϵ邻域包含对象集合 D_中与 p i p_i p i 的距离不大于 ϵ \epsilon ϵ的子对象集，即N ϵ N_ϵN ϵ(p i p_i p i )={x j x_j x j ∈ \in ∈ _D| distance(x i x_i x i ,x j x_j x j )≤ \leq ≤ϵ \epsilon ϵ}，这个子对象集的个数记为 |N ϵ N_ϵN ϵ(p i p_i p i )|
核心点(Core point)：如果给定对象的ϵ \epsilon ϵ邻域内的样本点数大于设定的MinPts，则称该对象为核心点（核心对象）。
边界点(Border point)：若样本 p i p_i p i 的邻域内包含的样本数目小于MinPts，但是它在其它核心点的邻域内，则称样本点p i p_i p i 为边界点。
噪声点(Noise point)：既不是核心点也不是噪声点的点
直接密度可达：给定对象集合 D，如果对象 _p_在对象 _q_的ϵ \epsilon ϵ邻域内，且 _p_是 _D_的一个核心对象，则称为对象 _p_从对象 _q_出发是直接密度可达的。
密度可达：给定对象集合 D，如果存在一个对象链p 1 p_1 p 1 ,p 2 p_2 p 2 ,p 3 p_3 p 3 ,···,p n p_n p n ，p 1 p_1 p 1 =q，p n p_n p n =p，∀ \forall ∀p i p_i p i ∈ \in ∈ D(1 ≤ \leq ≤i ≤ \leq ≤n-1)都有p i + 1 p_{i+1}p i +1 与p i p_i p i 是直接密度可达的，则称对象 _p_从对象 _q_出发是密度可达的。
密度相连：如果存在对象 o ∈ \in ∈ _D_使得对象 _p_和对象 _q_都是从 _o_出发密度可达的，则称对象 _p_从对象 _q_出发是密度相连。
; 3、DBSCAN密度聚类思想
DBSCAN的聚类定义很简单：由密度可达关系导出的最大密度相连的样本集合，即为我们最终聚类的一个类别，或者说一个簇。
这个DBSCAN的簇里面可以有一个或者多个核心对象。如果只有一个核心对象，则簇里其他的非核心对象样本都在这个核心对象的ϵ-邻域里；如果有多个核心对象，则簇里的任意一个核心对象的ϵ-邻域中一定有一个其他的核心对象，否则这两个核心对象无法密度可达。这些核心对象的ϵ-邻域里所有的样本的集合组成的一个DBSCAN聚类簇。
那么怎么才能找到这样的簇样本集合呢？DBSCAN使用的方法很简单，它任意选择一个没有类别的核心对象作为种子，然后找到所有这个核心对象能够密度可达的样本集合，即为一个聚类簇。接着继续选择另一个没有类别的核心对象去寻找密度可达的样本集合，这样就得到另一个聚类簇。一直运行到所有核心对象都有类别为止。
在DBSCAN密度聚类思想中，有一下三点需要注意的地方：
1.样本中的异常样本点。这些点不在任何一个核心对象的周围，在DBSCAN中，我们一般将这些样本点标记为噪声点。
2.距离度量问题。即如何计算某样本和核心对象样本间的距离。在DBSCAN中，一般采用最近邻思想，采用某一种距离度量来衡量样本距离，比如欧氏距离，这和KNN分类算法的最近邻思想完全相同。对于少量样本，寻找最近邻可以直接去计算所有样本的距离，如果样本量较大，则一般采用KD树或者球树来快速的搜索最近邻。
3.某些样本可能到两个核心对象的距离都小于ϵ \epsilon ϵ，但是这两个核心对象由于不是密度直达，且也不属于同一个聚类簇，则对于这种样本，一般来说，此时DBSCAN采用先来后到，先进行聚类的类别簇会标记这个样本为该类别。也就是说DBSCAN算法不是完全稳定的算法。
4、算法实现
输入：样本集 D =(p 1 p_1 p 1 ,p 2 p_2 p 2 ,…,p n p_n p n ),邻域参数 (ϵ \epsilon ϵ,MinPts)，样本距离度量方式
输出：簇划分 C
步骤：
- 1.初始化核心对象集合Ω \Omega Ω=∅ \emptyset ∅，初始化聚类簇数k=0，初始化未访问样本集合Γ \Gamma Γ= D，簇划分 C=∅ \emptyset ∅
- 2.对于i=1,2,…,n，按下面的步骤找出所有的核心对象：
- (a)通过距离度量方式，找到样本x i x_i x i 的ϵ \epsilon ϵ邻域子样本集N ϵ N_ϵN ϵ(p i p_i p i )
- (b)如果子样本集样本个数满足 |N ϵ N_ϵN ϵ(p i p_i p i )|≥ \geq ≥ MinPts，则将样本x i x_i x i 加入核心对象样本集合：Ω \Omega Ω=Ω \Omega Ω⋃ \bigcup ⋃{x i x_i x i }
-
3.如果核心对象集合Ω \Omega Ω=∅ \emptyset ∅，则算法结束，否则转入步骤4.
-
4.在核心对象集合Ω \Omega Ω中，随机选择一个核心对象 o，初始化当前簇核心对象队列Ω c u r Ω_{cur}Ωc u r ={ o}，初始化类别序号k=k+1，初始化当前簇样本集合C k C_k C k ={ o},更新未访问样本集合Γ \Gamma Γ=Γ \Gamma Γ-{ o}
- 5.如果当前簇核心对象队列Ω c u r Ω_{cur}Ωc u r =∅ \emptyset ∅，则当前聚类簇C k C_k C k 生成完毕，更新簇划分C={C 1 C_1 C 1 ,C 2 C_2 C 2 ,…,C k C_k C k },更新核心对象集合Ω \Omega Ω=Ω \Omega Ω-C k C_k C k ，转入步骤3，否则更新核心对象集合Ω \Omega Ω=Ω \Omega Ω-C k C_k C k
- 6.在当前簇核心对象队列Ω c u r Ω_{cur}Ωc u r 中取出一个核心对象 o’ 通过邻域距离阈值ϵ \epsilon ϵ找出所有的ϵ \epsilon ϵ邻域子样本集N ϵ N_ϵN ϵ(o’)，令Δ \Delta Δ=N ϵ N_ϵN ϵ(o’)⋂ \bigcap ⋂Ω \Omega Ω，更新当前簇样本集合C k C_k C k =C k C_k C k ⋃ \bigcup ⋃Δ \Delta Δ，更新未访问样本集合Ω \Omega Ω=Ω \Omega Ω-Δ \Delta Δ，更新Ω c u r Ω_{cur}Ωc u r =Ω c u r Ω_{cur}Ωc u r ⋂ \bigcap ⋂(Δ \Delta Δ⋃ \bigcup ⋃Ω \Omega Ω)- o’，转入步骤5
- 7.最后输出结果为：簇划分C={C 1 C_1 C 1 ,C 2 C_2 C 2 ,…,C k C_k C k }
5、总结
优点：
1.可以对任意形状的稠密数据进行聚类，而K-Means之类的聚类算法一般只适用于球形簇；
2.可以在聚类的同时发现噪声点，对数据集中的噪声点不敏感；
3.聚类结果没有偏倚，而K-Means之类的聚类算法初始值对聚类结果有很大影响。
缺点：
1.如果样本集的密度不均匀，聚类间距差相差很大时，聚类质量较差，这时用DBSCAN聚类一般不合适；
2.如果样本集较大时，聚类收敛时间较长，此时可以对搜索最近邻时建立的KD树或者球树进行规模限制来改进；
3.调参相对于传统的K-Means之类的聚类算法稍复杂，主要需要对距离阈值ϵ \epsilon ϵ，邻域样本数阈值MinPts联合调参，不同的参数组合对最后的聚类效果有较大影响。
参考来源
https://www.cnblogs.com/pinard/p/6208966.html
Original: https://blog.csdn.net/weixin_44428995/article/details/117398249
Author: 我确也不知道
Title: 密度聚类之DBSCAN聚类算法
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/561472/
转载文章受原作者版权保护。转载请注明原作者出处！