当前位置:   article > 正文

DBSCAN聚类算法原理总结

dbscan聚类算法

点击上方“小白学视觉”,选择加"星标"或“置顶

重磅干货,第一时间送达

DBSCAN是基于密度空间的聚类算法,在机器学习和数据挖掘领域有广泛的应用,其聚类原理通俗点讲是每个簇类的密度高于该簇类周围的密度,噪声的密度小于任一簇类的密度。如下图簇类ABC的密度大于周围的密度,噪声的密度低于任一簇类的密度,因此DBSCAN算法也能用于异常点检测。本文对DBSCAN算法进行了详细总结 。

5c34e5692087958c169c76f61594d2af.png

目录


1. DBSCAN算法的样本点组成

2. DBSCAN算法原理

3. DBSCAN算法的参数估计

4. DBSCAN算法实战

5  DBSCAN算法的优缺点

1. DBSCAN算法的样本点组成

DBSCAN算法处理后的聚类样本点分为:核心点(core points),边界点(border points)和噪声点(noise),这三类样本点的定义如下:

核心点:对某一数据集D,若样本p的d23207918fc21c16cf679e734a3d70f8.png-领域内至少包含MinPts个样本(包括样本p),那么样本p称核心点。

即:

65c23b67c56dabe3bbeb86ae5a3104ec.png

称p为核心点,其中3054395ff60731d5cfb9324ded0a82e7.png-领域373b88e15a68187d082d2910d9e17f40.png的表达式为:

198a16c7d00ea6b1d1f6770e267448f1.png

边界点:对于非核心点的样本b,若b在任意核心点p的6c90ee4dfacf958189897c7d1b5b8efb.png-领域内,那么样本b称为边界点。

即:

52c62b8c2da611463beaac15dff3bd02.png

称b为边界点。
噪声点:对于非核心点的样本n,若n不在任意核心点p的725f64da78788059f1b0460e376fd126.png-领域内,那么样本n称为噪声点。

即:

d0d272f6e69c147a739b1f3636c1aaea.png

称n为噪声点。

假设MinPts=4,如下图的核心点、非核心点与噪声的分布:

bf2e9df986d97fd9dae7ed5096d73026.jpeg

2. DBSCAN算法原理

由上节可知,DBSCAN算法划分数据集D为核心点,边界点和噪声点,并按照一定的连接规则组成簇类。介绍连接规则前,先定义下面这几个概念:

密度直达(directly density-reachable):若q处于p的90f416482abff9ea02e7072acd382eae.png-邻域内,且p为核心点,则称q由p密度直达;

密度可达(density-reachable):若q处于p的615b40843fabcdcda01d1da8b331dfc7.png-邻域内,且p,q均为核心点,则称q的邻域点由p密度可达;

密度相连(density-connected):若p,q均为非核心点,且p,q处于同一个簇类中,则称q与p密度相连。

下图给出了上述概念的直观显示(MinPts):

5678d373c9eb4fda232538b31b4e4149.jpeg

其中核心点E由核心点A密度直达,边界点B由核心点A密度可达,边界点B与边界点C密度相连,N为孤单的噪声点。

DBSCAN是基于密度的聚类算法,原理为:只要任意两个样本点是密度直达或密度可达的关系,那么该两个样本点归为同一簇类,上图的样本点ABCE为同一簇类。因此,DBSCAN算法从数据集D中随机选择一个核心点作为“种子”,由该种子出发确定相应的聚类簇,当遍历完所有核心点时,算法结束。

DBSCAN算法的伪代码:

  1. # DB为数据集,distFunc为样本间的距离函数
  2. # eps为样本点的领域,MinPts为簇类的最小样本数
  3. DBSCAN(DB,distFunc,eps,minPts){
  4. C = 0 # 初始化簇类个数
  5. # 数据集DB被标记为核心点和噪声点
  6. for each point P in database DB{ # 遍历数据集
  7. if label(P) != undefined then continue # 如果样本已经被标记了,跳过此次循环
  8. Neighbors N = RangeQuery(DB,distFunc,P,eps) # 计算样本点P在eps邻域内的个数,包含样本点本身
  9. if |N| < minPts then { # 密度估计
  10. label(P) = Noise # 若样本点P的eps邻域内个数小于MinPts,则为噪声
  11. continue
  12. }
  13. C = C + 1 # 增加簇类个数
  14. label(P) = C # 初始化簇类标记
  15. Seed set S = N \{P} # 初始化种子集,符号\表示取补集
  16. for each point Q in S{
  17. if label(Q) = Noise then label(Q) = C # 核心点P的邻域为噪声点,则该噪声点重新标记为边界点
  18. if label(Q) != undefined then continue # 如果样本已经被标记了(如上次已经被标记的噪声),跳过此次循环
  19. label(Q) = C # 核心点P的邻域都标记为簇类C
  20. Neighbors N = RangeQuery(DB,distFunc,Q,eps) # 计算样本Q的邻域个数
  21. if N >= minPts then{ # 密度检测,检测Q是否为核心样本
  22. S = S.append(N) # 邻域Q样本添加到种子集
  23. }
  24. }
  25. }
  26. }

其中计算样本Q邻域个数的伪代码:

  1. # 计算样本Q的eps邻域集
  2. RangeQuery(DB,distFunc,Q,eps){
  3. Neighbors = empty list # 初始化Q样本的邻域为空集
  4. for each point P in database DB{
  5. if distFunc(Q,P) <= eps then {
  6. Neighbors = Neighbors.append(Q) # 若Q在P的eps邻域内,则邻域集增加该样本
  7. }
  8. }
  9. return Neighbors
  10. }

其中计算样本P与Q的距离函数dist(P,Q)不同,邻域形状也不同,若我们使用的距离是曼哈顿(manhattan)距离,则邻域性状为矩形;若使用的距离是欧拉距离,则邻域形状为圆形。

DBSCAN算法可以抽象为以下几步:

1)找到每个样本的3b964d0a53c3e16dc9e922a2c1cfe90c.png-邻域内的样本个数,若个数大于等于MinPts,则该样本为核心点;

2)找到每个核心样本密度直达和密度可达的样本,且该样本亦为核心样本,忽略所有的非核心样本;

3)若非核心样本在核心样本的b8876afd895c629d0eb1955c7e92e9ae.png-邻域内,则非核心样本为边界样本,反之为噪声。 

3.  DBSCAN算法的参数估计

由上一节可知,DBSCAN主要包含两个参数:

81fc9ea6edbb4a6ce21d2f810d57076f.png:两个样本的最小距离,它的含义为:如果两个样本的距离小于或等于值edd9b457b3ce0e728185ca6e59ebbdac.png,那么这两个样本互为邻域。

MinPts:形成簇类所需的最小样本个数,比如MinPts等于5,形成簇类的前提是至少有一个样本的313952f2a3639f083866b429b3c73eae.png-邻域大于等于5。

092ed63a8262b9d218844a6057b72690.png参数和MinPts参数估计:

如下图,如果5d7ec04cd701fec44412a0eb65344acc.png值取的太小,部分样本误认为是噪声点(白色);f65accee706641bb3f728ea8419de0d8.png值取的多大,大部分的样本会合并为同一簇类。

edc20db82875c39ef1bc4a8ee18a3143.jpeg

同样的,若MinPts值过小,则所有样本都可能为核心样本;MinPts值过大时,部分样本误认为是噪声点(白色),如下图:

4e37935f8bbd46ec2f8d95dc54398e34.png   661ffc43fc51efb5fff2dfcdb9889166.png   224cfd73754a3b06510f5acf1177f298.png

根据经验,minPts的最小值可以从数据集的维数D得到,即0c37c4b19d7efa5e799b12cd6ad7273e.png。若minPts=1,含义为所有的数据集样本都为核心样本,即每个样本都是一个簇类;若minPts≤2,结果和单连接的层次聚类相同;因此minPts必须大于等于3,因此一般认为minPts=2*dim,若数据集越大,则minPts的值选择的亦越大。

3d1f4989d4a41a7aa340382ed7f036f1.png值常常用k-距离曲线(k-distance graph)得到,计算每个样本与所有样本的距离,选择第k个最近邻的距离并从大到小排序,得到k-距离曲线,曲线拐点对应的距离设置为423712833dc9d2103873d35bcee53a78.png,如下图:

eeb31db74d6bee9c5e3ff53193e8d559.png


由图可知或者根据k-距离曲线的定义可知:样本点第k个近邻距离值小于c70cbe93df96d45456cf4181064a88a8.png归为簇类,大于fef8a17f624ea30d648f02b574d5a09e.png的样本点归为噪声点。根据经验,一般选择1040458196eb7fbace0e1a326f03e469.png值等于第(minPts-1)的距离,计算样本间的距离前需要对数据进行归一化,使所有特征值处于同一尺度范围,有利于9c9da8f1e902d8975e5e868e1f0de661.png参数的设置。

如果(k+1)-距离曲线和k-距离曲线没有明显差异,那么minPts设置为k值。例如k=4和k>4的距离曲线没有明显差异,而且k>4的算法计算量大于k=4的计算量,因此设置MinPts=4。

4. DBSCAN算法实战

k-means聚类算法假设簇类所有方向是同等重要的,若遇到一些奇怪的形状(如对角线)时,k-means的聚类效果很差,本节采用DBSCAN算法以及简单的介绍下如何去选择参数064663c2cdee2216293f54eb56d4998c.png和MinPts。

随机生成五个簇类的二维数据:

  1. import numpy as np
  2. import matplotlib.pyplot as plt
  3. from sklearn.datasets import make_blobs
  4. from sklearn.cluster import DBSCAN
  5. from sklearn.preprocessing import StandardScaler
  6. # 生成随机簇类数据
  7. X, y =make_blobs(random_state=170,n_samples=600,centers=5)
  8. rng = np.random.RandomState(74)
  9. # 数据拉伸
  10. transformation = rng.normal(size=(2,2))
  11. X = np.dot(X,transformation)
  12. # 绘制延伸图
  13. plt.scatter(X[:,0],X[:,1])
  14. plt.xlabel("Feature 0")
  15. plt.ylabel("Feature 1")
  16. plt.show()

散点图为:

3441caff4d277c75638b82f923dbce0a.png

k-means聚类结果:

be3cfef44df59696018cfe36017b9f77.jpeg

按照经验MinPts=2*ndims,因此我们设置MinPts=4。

为了方便参数1c6c76203299e19a38f84770ad72b789.png的选择,我们首先对数据的特征进行归一化:

  1. #特征归一化
  2. scaler = StandardScaler()
  3. X_scaled = scaler.fit_transform(X)

假设57cf28ed1ae86c622f532f219dcec71b.png=0.5:

  1. # dbscan聚类算法
  2. t0=time.time()
  3. dbscan = DBSCAN(eps=0.12,min_samples = 4)
  4. clusters = dbscan.fit_predict(X_scaled)
  5. # 绘制dbscan聚类结果
  6. plt.scatter(X[:,0],X[:,1],c=clusters,cmap="plasma")
  7. plt.xlabel("Feature 0")
  8. plt.ylabel("Feature 1")
  9. plt.title("eps=0.5,minPts=4")
  10. plt.show()
  11. t1=time.time()
  12. print(t1-t0)

查看聚类结果:

1b45400e738f6cd0f2bb1582d7a6a652.png

由上图可知,所有的样本都归为一类,因此812730f5fddd1339009844d21f559ff3.png设置的过大,需要减小e5f63a812176f4de0193929a5adbcf76.png

设置c1ad7861c9fc75f6b856eed919e5778e.png=0.2的结果:

cc39bfd5f4de95ea2cc69f325cdc328b.png

由上图可知,大部分样本还是归为一类,因此1909847cb80e49169c80f912443be94f.png设置的过大,仍需要减小cc007a56c6dd1e08e37e5afde605edaf.png

设置16a65f23ad4dfb1401ac2face3ca1f98.png=0.12的结果:

6c415ddfdc665665826ae4d6127f6661.png

结果令人满意,看看聚类性能度量指数:

  1. # 性能评价指标ARI
  2. from sklearn.metrics.cluster import adjusted_rand_score
  3. # ARI指数
  4. print("ARI=",round(adjusted_rand_score(y,clusters),2))
  5. #>
  6. ARI= 0.99

由上节可知,为了较少算法的计算量,我们尝试减小MinPts的值。
设置MinPts=2的结果:

69ee29b5babe15df6b79cdce17c9e8d5.png

其ARI指数为:0.99

算法的运行时间较minPts=4时要短,因此我们最终选择的参数:8236e50c645f48801a557ef939a30503.png=0.12,minPts=4。

这是一个根据经验的参数优化算法,实际项目中,我们首先根据先验经验去设置参数的值,确定参数的大致范围,然后根据性能度量去选择最优参数。 

5  DBSCAN算法的优缺点

优点:

1)DBSCAN不需要指定簇类的数量;

2)DBSCAN可以处理任意形状的簇类;

3)DBSCAN可以检测数据集的噪声,且对数据集中的异常点不敏感;

4)DBSCAN结果对数据集样本的随机抽样顺序不敏感(细心的读者会发现样本的顺序不一样,结果也可能不一样,如非核心点处于两个聚类的边界,若核心点抽样顺序不同,非核心点归于不同的簇类);

缺点:

1)DBSCAN最常用的距离度量为欧式距离,对于高维数据集,会带来维度灾难,导致选择合适的65a4d55c8ae6ca1a063b3a4e4d489ea8.png值很难;

2)若不同簇类的样本集密度相差很大,则DBSCAN的聚类效果很差,因为这类数据集导致选择合适的minPts和7c322a918588c03f99e9e2f61c1b2afa.png值非常难,很难适用于所有簇类。

 
 

好消息!

小白学视觉知识星球

开始面向外开放啦

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/811031
推荐阅读
相关标签