聚类(DBSCAN)算法原理

DBSCAN(Density-Based Spatial Clustering of Applications with Noise,具有噪声的基于密度的聚类方法)是一种很典型的密度聚类算法,和K-Means,BIRCH这些一般只适用于凸样本集的聚类相比,DBSCAN既可以适用于凸样本集,也可以适用于非凸样本集。下面我们就对DBSCAN算法的原理做一个总结。

更多精彩内容请看 web前端中文站
www.lisa33xiaoq.net 可按Ctrl + D 进行收藏

基于密度的聚类算法主要的目标是寻找被低密度区域分离的高密度区域。与基于距离的聚类算法不同的是,基于距离的聚类算法的聚类结果是球状的簇,而基于密度的聚类算法可以发现任意形状的聚类,这对于带有噪音点的数据起着重要的作用。

聚类(DBSCAN)算法原理

密度聚类原理

DBSCAN(Density-Based Spatial Clustering of Application with Noise)是一种典型的基于密度的聚类算法,在DBSCAN算法中将数据点分为一下三类:

  • 核心点。在半径Eps内含有超过MinPts数目的点
  • 边界点。在半径Eps内点的数量小于MinPts,但是落在核心点的邻域内
  • 噪音点。既不是核心点也不是边界点的点

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

  • Eps邻域。简单来讲就是与点聚类(DBSCAN)算法原理的距离小于等于Eps的所有的点的集合,可以表示为聚类(DBSCAN)算法原理
  • 直接密度可达。如果聚类(DBSCAN)算法原理在核心对象聚类(DBSCAN)算法原理的Eps邻域内,则称对象聚类(DBSCAN)算法原理从对象聚类(DBSCAN)算法原理出发是直接密度可达的。
  • 密度可达。对于对象链:聚类(DBSCAN)算法原理聚类(DBSCAN)算法原理是从聚类(DBSCAN)算法原理关于Eps和MinPts直接密度可达的,则对象聚类(DBSCAN)算法原理是从对象聚类(DBSCAN)算法原理关于Eps和MinPts密度可达的。

DBSCAN算法优点:

  • 与K-means算法比起来,不需要预先输入划分的聚类个数。
  • 聚类形成的簇的形状可以是任意的。
  • 可以在需要的时候输入过滤噪声的参数。

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)算法原理

下面是该算法的伪代码:

 算法: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"

【注:本文源自网络文章资源,由站长整理发布】

0
如无特殊说明,文章均为原作者原创,转载请注明出处

该文章由 发布

这货来去如风,什么鬼都没留下!!!
发表我的评论

Hi,请填写昵称和邮箱!

取消评论
代码 贴图 加粗 链接 删除线 签到