博主辛苦了，我要打赏银两给博主，犒劳犒劳站长。
【摘要】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中所有对象都被访问。
算法伪代码：
算法：DBSCAN，一种基于密度的聚类算法
输入：
D:包含若干个对象的数据集
ε:半径
MinPts:密度邻域阈值
输出：簇的集合
方法：
1.标记D中所有的对象为"unvisited";
2.Do
3.随机选择一个"unvisited"对象p;
4.标记p为"visited";
5.If p的ε-邻域至少含有MinPts个对象
6. 创建一个新的簇C;
7. 令N为p的ε-邻域对象的集合;
8. For N中的每个对象q
9. If q是"unvisited"
10. 则标记q为"visited";
11. If q是核心对象
12. 则将q的ε-邻域中的所有对象集合加到N中;
13. If q不属于其它簇
14 则将q加入到簇C中;
15. End For;
16. 输出C
17.Else 标记p为噪声点
18.Until D中所以对象都是"visited"
版权归 马富天个人博客 所有
本文标题：《简单介绍一下DBSCAN算法》
本文链接地址：http://www.mafutian.com/133.html
转载请务必注明出处，小生将不胜感激，谢谢! 喜欢本文或觉得本文对您有帮助，请分享给您的朋友 ^_^
顶1
踩0
| 评论审核未开启 |
|
||
|