简单介绍一下DBSCAN算法

学习笔记 马富天 2016-05-28 17:17:14 83 0

【摘要】DBSCAN算法是一个比较典型的基于密度的聚类算法,可以在含有噪声的空间数据库中发现任意形状的聚类。本文参考原文:http://www.cnblogs.com/aijianiula/p/4339960.html

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

有如下几个优点:

(1)与K-means算法比起来,不需要预先输入划分的聚类个数。

(2)聚类形成的簇的形状可以是任意的。

(3)可以在需要的时候输入过滤噪声的参数。

了解DBSCAN算法需要了解的基本概念:

(1)ε-邻域:以对象O为中心,半径为ε的空间。

(2)MinPts(邻域密度阈值):对象O的ε-邻域内包含的其它对象的数量。

(3)核心对象:若对象O的ε-领域内至少包含了MinPts个对象,则称对象O是核心对象。

(4)直接密度可达:若对象p在核心对象q的ε-邻域内,则称对象p是从q直接密度可达的。

(5)密度可达:如下图所示,对象m是从对象p直接密度可达,而对象q是从对象m直接密度可达,则称q和p是密度可达的(或者叫做间接密度可达)

请输入图片名称

(6)密度相连:如上图所示,对象s和对象O是密度可达的,而对象O和对象r是密度可达的,则称对象s和对象r是密度相连的。

DBSCAN算法的聚类过程:

(1)初始状态,给出一个数据集D,并设置半径ε和MinPts,将D中的所有对象标记为"unvisited"(未被访问)

(2)随机从D中选取一个未被访问的对象p,并标记为"visited"(已被访问),检查p的ε-邻域内是否至少包含MinPts个对象(即p是否是核心对象),若不是,则将p标记为噪声点,否则,为p创建一个新的簇C,把p的ε-邻域中所有对象放入候选集合N中,并迭代的将N中不属于其它簇的对象加入到新簇C中,在这个过程中,将N中的"unvisited"的对象q标记为"visited",若q的ε-邻域是否至少包含MinPts个对象,则将q的ε-邻域中所有的对象加入到C中,直到C不再扩大,N为空的时候,此时簇C完成聚类,并输出。

(3)继续从D中随机选取未被访问的对象s,同样使用(2)中的聚类方法,直到对象集D中所有对象都被访问。

算法伪代码:

  1. 算法:DBSCAN,一种基于密度的聚类算法
  2. 输入:
  3. 	D:包含若干个对象的数据集
  4. 	ε:半径
  5. 	MinPts:密度邻域阈值
  6. 输出:簇的集合
  7. 方法:
  8. 	1.标记D中所有的对象为"unvisited";
  9. 	2.Do
  10. 	3.随机选择一个"unvisited"对象p;
  11. 	4.标记p为"visited";
  12. 	5.If p的ε-邻域至少含有MinPts个对象
  13. 	6.   创建一个新的簇C;
  14. 	7.   令N为p的ε-邻域对象的集合;
  15. 	8.   For N中的每个对象q
  16. 	9.       If q是"unvisited"
  17. 	10.          则标记q为"visited";
  18. 	11.          If q是核心对象
  19. 	12.              则将q的ε-邻域中的所有对象集合加到N中;
  20. 	13.          If q不属于其它簇
  21. 	14               则将q加入到簇C中;
  22. 	15.  End For;
  23. 	16.  输出C
  24. 	17.Else 标记p为噪声点
  25. 	18.Until D中所以对象都是"visited"

版权归 马富天PHP博客 所有

本文标题:《简单介绍一下DBSCAN算法》

本文链接地址:http://www.mafutian.net/133.html

转载请务必注明出处,小生将不胜感激,谢谢! 喜欢本文或觉得本文对您有帮助,请分享给您的朋友 ^_^

1

0

上一篇《 4个步骤教你如何提高电脑的上网速度 》 下一篇《 如何在Windows系统中运行Python文件(Python运行环境搭建) 》
分享到:

暂无评论

评论审核未开启
表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情 表情
验证码

TOP10

  • 浏览最多
  • 评论最多