DBSCAN(Density-Based Spatial Clustering of Applications with Noise)基于密度的聚类算法
admin
2023-07-30 20:12:47
0

DBSCAN是一种非常著名的基于密度的聚类算法。其英文全称是 Density-Based Spatial Clustering of Applications with Noise,意即:一种基于密度,对噪声鲁棒的空间聚类算法。直观效果上看,DBSCAN算法可以找到样本点的全部密集区域,并把这些密集区域当做一个一个的聚类簇。

简单来讲,给定一组点,DBSCAN将彼此距离(欧几里得距离)很近的点聚成一类,同时它还将低密度区域中的点标记为异常值(outlier)。

DBSCAN使用了两个参数:半径eps和密度阈值Minpts。DBSCAN需要由用户主观来选择参数,参数的选择决定了最终的聚类结果。在计算复杂度方面,如果采用空间索引,DBSCAN的计算复杂度是O(nlog(n)),其中n是对象数,否则计算复杂度为O(n2)。

DBSCAN聚类算法

    下面我们对DBSCAN聚类算法的流程做一个总结。

    输入:样本集D=(x1,x2,…,xm)(x1,x2,…,xm),邻域参数(ϵ,MinPts)(ϵ,MinPts), 样本距离度量方式

    输出: 簇划分C. 

    1)初始化核心对象集合Ω=∅Ω=∅, 初始化聚类簇数k=0,初始化未访问样本集合ΓΓ = D,  簇划分C = ∅∅

    2) 对于j=1,2,…m, 按下面的步骤找出所有的核心对象:

      a) 通过距离度量方式,找到样本xjxj的ϵϵ-邻域子样本集Nϵ(xj)Nϵ(xj)

      b) 如果子样本集样本个数满足|Nϵ(xj)|≥MinPts|Nϵ(xj)|≥MinPts, 将样本xjxj加入核心对象样本集合:Ω=Ω∪{xj}Ω=Ω∪{xj}

    3)如果核心对象集合Ω=∅Ω=∅,则算法结束,否则转入步骤4.

    4)在核心对象集合ΩΩ中,随机选择一个核心对象oo,初始化当前簇核心对象队列Ωcur={o}Ωcur={o}, 初始化类别序号k=k+1,初始化当前簇样本集合Ck={o}Ck={o}, 更新未访问样本集合Γ=Γ−{o}Γ=Γ−{o}

    5)如果当前簇核心对象队列Ωcur=∅Ωcur=∅,则当前聚类簇CkCk生成完毕, 更新簇划分C={C1,C2,…,Ck}{C1,C2,…,Ck}, 更新核心对象集合Ω=Ω−CkΩ=Ω−Ck, 转入步骤3。

    6)在当前簇核心对象队列ΩcurΩcur中取出一个核心对象o′o′,通过邻域距离阈值ϵϵ找出所有的ϵϵ-邻域子样本集Nϵ(o′)Nϵ(o′),令Δ=Nϵ(o′)∩ΓΔ=Nϵ(o′)∩Γ, 更新当前簇样本集合Ck=Ck∪ΔCk=Ck∪Δ, 更新未访问样本集合Γ=Γ−ΔΓ=Γ−Δ, 转入步骤5.

    输出结果为: 簇划分C={C1,C2,…,Ck}{C1,C2,…,Ck}

DBSCAN 算法最初有 Ester 等人在1996年最初提出,DBSCAN 自发表后受到了学界的一直推崇,众多科学文献引用该算法,同时DBSCAN 算法也是 PreDeCon 和 SUBCLU 等聚类算法中的一部分,1998年,Sander 和 Ester 提出了适用性更加广泛的 GDBSCAN 算法。 2014年的时候,DBSCAN 算法获得了2014 SIGKDD Test of Time Award, 2007年 Birant 提出了一种名为 ST-DBSCAN 的算法,该算法最显著的优势在于可以用于时空数据的处理。2010年,Kisilevich 等人提出了通过地理标记照片数据从而挖掘地点和事件的算法 P-DBSCAN。

DBSCAN 作为密度聚类最常见的方法之一,其应用也越来越多,很多其他的算法与之结合是未来该算法甚至整个聚类研究的一个方向,目前已知的 DBSCAN 和层次聚类有很多的交叉应用。其次,对于 MinPts 和 e 的选择一直是 DBSCAN 研究的关键。

相关内容

热门资讯

玻璃硬盘原理图 玻璃硬盘原理 玻璃硬盘,又称为磁头悬浮硬盘(Magnetic Head Flying Disk,MHFD),是一种...
家里监控最长能保存多少天的记录... 家里监控一般保存多久 随着科技的发展,家庭监控系统已经成为了许多家庭的必备设备,它不仅可以帮助我们...
QQ音乐提示代理模式可能无法正... QQ音乐提示代理模式可能无法正常访问,如上图所示,是怎么回事呢? 这个可能和你的网络设置有关系,首先...
闲鱼搜索规则与技巧 闲鱼最新特... 在闲鱼这个二手交易平台上,有很多用户都希望能够找到一些特殊的东西,比如一些罕见的收藏品、独特的手工艺...
别人打电话听不见我说话怎么回事... 当我们在使用手机时,可能会遇到别人打电话过来听不见声音的情况,这种情况可能是由多种原因导致的,下面我...
华为tag有用吗 华为tag-... 华为Tag是华为手机中的一种功能,它可以帮助用户更好地管理自己的手机数据和应用,通过使用华为Tag,...
frp内网穿透配置 HTTP ... HTTP 类型的代理相比于 TCP 类型,不仅在服务端只需要监听一个额外的端口 vhost_http...
ps5手柄可用手机快充充电吗 ... PS5手柄,即PlayStation 5的DualSense手柄,是索尼公司为PlayStation...
广电4k机顶盒怎么连接 广电网... 四广电网络,即四家主流的广播电视网络运营商,包括中国电信、中国移动、中国联通和中国广电,这些运营商为...
hwid是永久激活吗 hwid... HWID,全称Hardware ID,是硬件识别码的缩写,它是计算机硬件制造商为了区分每一台设备而分...