基于MCMC的DBSCAN改进算法

李建伏，巴建军

(中国民航大学 计算机科学与技术学院，天津 300300)

0 引 言

目前已有多种聚类算法，主要分为划分聚类、层次聚类和基于密度的聚类算法[1]。其中，由于能发现任意形状的簇，且能很有效地处理噪声数据，基于密度的聚类算法得到了广泛应用。基于密度的聚类有很多实现算法，其中DBSCAN[2,3]算法(density based clustering of application with noise)最为流行。然而，DBSCAN的一个缺点是其时间复杂度较高，文献[4,5]证明了DBSCAN算法的时间复杂度为O(n2)，其中n为待聚类对象个数。这限制了其处理大规模数据的能力，尤其是在大数据时代，算法的运行时间变得尤为重要[6]。

为了降低算法的运行时间，人们已提出多种策略改进DBSCAN。第一类改进思路是通过借助一定的策略来加速对象的邻域查询操作，如文献[7-9]。第二类加快DBSCAN算法的方法是采用并行化的策略，如文献[10-12]。第三类改进策略是选择性地扩展部分核心对象。导致DBSCAN算法时间复杂度高的主要原因在于其需要对所有核心对象进行逐一扩展。而实际上，核心对象的邻域之间存在着大量的重叠，没有必要对所有核心对象进行扩展。因此，选择性地扩展部分核心对象是提高DBSCAN效率的一个有效途径。基于不同的核心对象选择方法形成了不同的改进算法。如文献[13]选择核心对象邻域的边界对象作为待扩展对象；文献[14]随机选择处于以当前核心点为圆心，介于半径为ε和2ε两个圆之间的环状区域内的对象作为下一个扩展对象；文献[15]首先利用一个快速的聚类算法将原始数据划分为多个簇，然后将这些簇的代表节点作为待扩展节点。

本文提出一种基于部分核心对象扩展策略的DBSCAN改进算法，称为DBSCAN++。DBSCAN++的基本思想是优先扩展拓展能力较强的核心对象，其中核心对象的拓展能力通过从密度和与已经扩展过的对象的最短距离两个角度来衡量，即密度越高且距离已扩展过的对象越远的对象的拓展能力越强。实际上，按照以上两个角度来确定当前拓展能力最强的节点是一个双目标优化问题，求解该双目标优化问题非常耗时，且不一定能够找到满足条件的解。本文借助MCMC采样策略来选择当前扩展对象。

1 基础知识

1.1 DBSCAN

DBSCAN算法借助ε和MinPts两个参数、利用簇的密度连通特性来发现簇，其中涉及的关键术语定义如下。

邻域：与对象p的距离不大于ε的对象集合，称为p的邻域，表示为Nε(p)={q|dis(p,q)≤ε}。

密度：对象p的密度Dε(p)=|Nε(p)|。

核心对象：如果对于对象p，有 |Nε(p)|≥MinPts，则p被称为核心对象，反之称为非核心对象。

直接密度可达：对于核心对象p，如果对象q∈Nε(p)，则称q相对于p是直接密度可达的或q是p的直接可达对象。

密度可达：对于对象p和q，如果存在一系列的对象p1=q，p2，…，pn=p，使得pi+1相对于pi是密度可达的，则称p相对于q是密度可达的，p1，p2，…，pn都称为p的密度可达对象。

对象扩展操作：对于核心对象p，对其进行扩展操作即为确定其邻域Nε(p)。

DBSCAN的基本思想是将所有密度可达对象作为一个簇，基本处理过程是从某一个核心对象p开始，首先对p进行扩展，接着对Nε(p) 中的每个核心对象进行扩展，不断进行以上对象扩展操作直至p的所有密度可达节点都被遍历一次，将p与所有这些密度可达节点标记为同一簇；然后再从其它某一个没被标记的核心对象q开始，寻找q的所有密度可达节点；按照以上步骤，直至所有核心节点都被标记为某一类簇为止。其伪代码如算法1所示。

算法1： 基本DBSCAN算法

输入： 待聚类对象集S，参数ε、MinPts

输出： 每个对象的簇编号

(1)For each pointpinSdo

(2)label(p)←-1

(3)c←0

(4)for each pointpinSdo

(5) if(label(p)≠-1) thencontinue

(6)Nε(p)←Expand(S,p,ε)

(7) if(|Nε(p)|

(8)label(p)←noise

(9)continue

(10)c←c+1

(11)label(p)←c

(12)D←Nε(p)(〗p}

(13) whileDis not empty

(14) for eachqinDdo

(15) if(lable(q)==noise) thenlable(q)←c

(16) if(label(q)==-1)

(17)Nε(q)←Expand(S,q,ε)

(18)label(q)←c

(19) if(|Nε(q)|≥MinPts) thenD←D∪Nε(q)

(20)Output label(p) for everyp∈S.

通过算法1可以看出DBSCAN算法耗时的原因在于无论采用什么样的顺序，都要对数据集中的每个核心对象进行一次扩展操作。对于节点p，扩展节点意味着要计算其邻域，计算邻域需要的时间为O(nQ)，其中n为数据集大小，Q为计算两个对象之间距离的时间复杂度。如对于欧式距离，Q为O(nd)，其中d为欧式空间的维数，则整个DBSCAN算法的时间复杂度Q为O(dn2)，即O(n2)。

1.2 MCMC技术

MCMC是一类采样方法，主要用于对分布复杂的数据采样，其中比较流行的是Metropolis-hastings采样。

Metropolis-hastings的基本思路是从样本空间X中随机选择一个样本作为初始状态x0，然后按照以下迭代过程构建马尔可夫链：在第j次迭代过程中，随机选择一个样本作为候选采样点y，并按式(1)计算y的接受概率π

π=min{1,p(y)/p(xj-1)}

(1)

其中，p(y)和p(xj-1)分别表示y和xj-1的出现概率。候选采样点y会以π的概率被接受作为xj。

当设定马尔可夫链长度为m时，按照以上过程迭代m次，得到的采样点即为xj。

在应用Metropolis-hastings在求解实际问题时，往往根据需要来定义接受概率π。

2 DBSCAN++

2.1 算法思想

DBSCAN++算法遵循了基本DBSCAN算法的框架，即从某个核心对象p开始，通过不断地扩展核心对象直至p的所有密度可达对象都被找到；然后再从其它某一个没被标记的核心对象q开始，寻找q的密度可达节点；按照以上步骤，直至所有核心节点都被标记为某一簇为止。

DBSCAN++与基本的DBSCAN算法最大的不同是DBSCAN需要把所有核心对象都扩展一次，而DBSCAN++只需要扩展部分核心对象。其基本思路是采用MCMC方法优先扩展拓展能力较强的核心对象直至当前被扩展对象的拓展能力低于非常低时，算法终止本类簇密度可达对象的寻找，从而开始从另一个核心对象q开始另一类簇的发现。

2.2 基于MCMC的对象选择方法

按照DBSCAN++的基本思路，利用Metropolis-hastings采样方法从当前所有待扩展对象中选择拓展能力最强的核心对象作为下一个扩展对象。如前所述，本文通过密度和与已经扩展过的对象的最短距离两个角度来衡量对象拓展能力。由于计算对象的密度比较耗时(O(n))，为了尽量减少计算对象密度的次数，本文在选择节点时采用文献[16]中的可达距离来近似对象的密度，只有当某对象被选择作为当前扩展对象时再计算其密度。

根据文献[16]，结合本文的需要，对象x的可达距离rd(x)，定义如式(2)所示

rd(x)=max{d(p,x),cd(p)|x∈Nε(p)}

(2)

其中，x∈Nε(p)，d(p,x) 为p和x之间的距离，cd(p) 为核心对象p的核心距离，定义如式(3)所示

(3)

通过式(2)和式(3)可以看出，对象x距离核心对象p的可达距离越小，x越接近于p。根据核心对象的定义，与核心对象距离越近的对象成为核心对象的可能性越高，即处于高密度区域的可能性越高，拓展能力越强。

除此之外，对于两个待扩展对象p和q，如果d(p,A)

综合以上对可达距离和与已扩展对象的距离的分析，具有更小的可达距离且与已扩展对象距离越远的对象的拓展能力越强。

按照Metropolis-hastings，当选择一个候选采样点时，需要计算该采样点的接受概率π。DBSCAN++中将候选采样点的接受概率的定义如式(4)所示

(4)

其中，d(yj,A) 和d(xj-1,A) 分别为yj和xj-1到集合A中对象的最短距离。

DBSCAN++算法利用MCMC技术选择扩展对象的伪代码如算法2所示，其中，OPEN表用来存储所有待扩展对象，CLS表用来存储所有已被扩展核心对象。由于OPEN表中最多有n个对象(n为所有聚类对象个数)，因此，当采样次数为m次时，MCMC(OPEN,m) 的时间复杂为O(mn)。

算法2： MCMC(OPEN,m)

输入：OPEN,CLS，m

输出： 采样点

(1)x←OPEN.get(0)

(2)If(OPEN.size()>=2)

(3)d(x,CLS)←argminu∈CLSdis(x,u)

(4) for(intj=1;j

(5)s←rand[1,OPEN.size()-1]

(6)y←OPEN.get(s)

(7)d(y,CLS)←argminu∈CLSdis(y,u)

(8)π←min{1,d(y,CLS)*rd(x)/(d(x,CLS)*rd(y))}

(9)if(π>rand(0,1))

(10)x←y

(11)d(x,CLS)←d(y,CLS)

(12)returnx.

2.3 DBSCAN++提前终止策略

DBSCAN++中，当当前被扩展对象的拓展能力低于非常低时，DBSCAN++算法终止本类簇密度可达节点的寻找。

如前所述，在扩展节点之前通过可达距离和与已扩展对象的距离两方面来预判节点的拓展能力，当节点p被扩展之后，可以通过扩展p新发现的对象数来衡量其拓展能力。

DBSCAN++，核心节点p的拓展能力Expan(p)可以通过式(5)来计算

Exp(p)=|{x|x∈Nε(p),label(x)=-1}|

(5)

在DBSCAN++中，当Expan(p)为0时，p节点的拓展能力被认为非常弱，算法停止本类簇密度可达节点的寻找。

2.4 DBSCAN++算法描述

整个DBSCAN++算法伪代码如算法3所示。

算法3： DBSCAN++算法

输入： 数据集S，参数ε、MinPts，m

输出： 每个对象的簇编号

(1)For each pointpinSdo

(2)label(p)←-1

(3)c←0

(4)for each pointpinSdo

(5) if(label(p)≠-1) thencontinue

(6)Nε(p)←Expand(S,p,ε)

(7) if(Nε(p) is empty)

(8)label(p)←noise

(9)continue

(10)c←c+1

(11)label(p)←c

(12)OPEN←OPEN+Nε(p)(〗p}；CLS←CLS+{p}

(13) whileOPENis not empty

(14)q←MCMC(OPEN,m)

(15)OPEN←OPEN-{q}

(16) if(label(q)==noise) thenlabel(q)←c

(17) if(label(q)==-1)

(18)label(q)←c

(19)Nε(q)←Expand(S,q,ε)

(20) if(Exp(q)==0) break;

(21)OPEN←OPEN+Nε(q)

(22)CLS←CLS+{q}

(23)Output label(p) for everyp∈S.

从伪代码可以看出，算法最耗时的部分在于第(13)步，即从当前所有待扩展对象中不断选择对象并扩展直至当前被扩展节点的扩展能力为0。其中最耗时的部分在于(14)步和(19)步。其中(14)步的时间复杂度为O(mn)；(19)步的主要功能为扩展当前核心对象q，其伪代码如算法4所示,时间复杂度为O(n)。

算法4： Expand(S,p,ε,Minpts)

输入： 数据集S，参数ε和Minpts

输出：N

(1)N←Φ,DIS←-1

(2) for(i=0;i<|S|;i++)

(3) if(d(p,S[i])<ε)

(4)N←N+{S[i]}

(5)DIS←DIS+{d(p,S[i])}

(6)if(|N|

(7) returnΦ

(8)newDis←DIS中第Minpts小的距离

(9)cd(p)←newDis

(10)for(i=0;i<|N|;i++)

(11)N[i].cd←min(cd(p),DIS[i]) //式(2)

(12)returnN.

所以，从理论上讲，整个DBSCAN++算法的时间复杂度是O(n2)，与DBSCAN算法相同。

3 实验部分

为了验证算法的有效性，本文通过实验将BSCAN++算法与DBSCAN和OPTICS两种算法从运行时间和聚类准确性两个角度进行了对比。在实验中，DBSCAN++、DBSCAN和OPTICS都采用Java语言编程实现，所有实验都在同样的软硬件环境下完成。

测试数据为7个来自于UCI数据库的数据集，每个数据集中对象个数、属性个数和簇个数见表1，其中“簇个数”列给出了该数据集中包含簇的数量。

表1 7个数据集

实验中，DBSCAN++、DBSCAN和OPTICS3种算法在不同的数据集上的ε和MinPts的取值情况见表2。另外，DBSCAN++中的参数m的取值为5。

3种算法在7个数据集上的运行时间见表3，其中“百分比”列表示DBSCAN++相对于当前算法运行时间的提高百分比，即(当前算法运行时间-DBSCAN++运行时间)/当前算法运行时间*100%。通过表3可以看出：

表2 DBSCAN、OPTICS、DBSCAN++在不同

(1)在7个数据集上，DBSCAN++最快，DBSCAN次之，OPTICS最慢；

(2)在不同的数据集上，DBSCAN++相对于DBSCAN和OPTICS运行时间提高百分比不同；且，在数据规模较大的数据集上，DBSCAN++的加速效果更加明显。如在data5、data6和data7这3个数据集上，DBSCAN++相对于DBSCAN和OPTICS的提高百分比均在80%以上；

表3 DBSCAN、OPTICS、DBSCAN++

(3)在7个数据集上，DBSCAN++相对于DBSCAN的平均提高百分比为60.7，相对于OPTICS的平均提高百分比为70.2。可见，从运行时间看，DBSCAN++是高效的。

为了评价聚类准确性，本文采用了V-measure、ARI、NMI作为评价指标。图1～图3分别给出了3种算法在每个数据集上的聚类准确性对比直方图。

图1 以V-measure为评价指标下3种算法在7个数据集上的聚类准确性

图2 以ARI为评价指标下3种算法在7个数据集上的聚类准确性

图3 以NMI为评价指标下3种算法在7个数据集上的聚类准确性

通过图1～图3可以看出：

(1)在V-measure、ARI、NMI的任何一种评价指标下，没有一种算法在所有数据集上都比其它算法好。如data1上，DBSCAN和OPTICS的准确性略高于DBSCAN++；在data2，data3，data4，data6上，3种指标中可以看出DBSCAN++均高于DBSCAN和OPTICS；而在data5上，OPTICS的准确性明显高于DBSCAN和OPTICS；

(2)从V-measure评价指标看，在data2，data3，data4和data6上，DBSCAN++的准确性明显高于DBSCAN和OPTICS；在data1上，DBSCAN++的准确性略低于DBSCAN和OPTICS；在data5上，OPTICS最准确，其次是DBSCAN++，DBSCAN的准确性最差；

(3)从ARI评价指标看，在data2，data3，data4，data6和data7上，DBSCAN++的准确性明显高于DBSCAN和OPTICS；在data1上，DBSCAN++的准确性略低于DBSCAN和OPTICS；在data5上，OPTICS最准确，其次是DBSCAN++，DBSCAN的准确性最差；

(4)从NMI评价指标看，在data2，data3，data4和data6上，DBSCAN++的准确性明显高于DBSCAN和OPTICS；在data1上，DBSCAN++的准确性略低于DBSCAN和OPTICS；在data5和data7上，OPTICS最准确，其次是DBSCAN++，DBSCAN的准确性最差；

(5)综上所述，在data2，data3，data4和data6上，在任何一种评价指标下，DBSCAN++的准确性明显高于DBSCAN和OPTICS；在data1上，DBSCAN++的准确性略低于DBSCAN和OPTICS；在data5上，OPTICS最准确，其次是DBSCAN++，DBSCAN的准确性最差。对于data7，在不同的评价指标下，3种算法的准确性不一样，从ARI看，DBSCAN++最准确；从V-measure和NMI看，OPTICS最准确，其次是DBSCAN++，DBSCAN最差。

结合以上运行时间和聚类有效性的分析，DBSCAN++算法不仅保证了聚类效果，而且运行时间上DBSCAN++比DBSCAN平均降低了60.7%，比OPTICS平均降低了70.2%，这说明了本文算法DBSCAN++较DBSCAN、OPTICS有显著的优势。

4 结束语

本文针对DBSCAN算法时间复杂度高的问题，提出了一种基于MCMC的DBSCAN改进算法——DBSCAN++。本文创新之处在于引入密度和与已经扩展过的对象的最短距离两个角度来衡量核心对象的拓展能力，并借助Metro-polis-hastings采样方法实现具有较强的拓展能力的核心对象的选取。虽然从理论上看，DBSCAN++与DBSCAN具有相同的时间复杂度，但是实验结果表明，DBSCAN++的实际运行时间明显优于DBSCAN和OPTICS，且算法的准确性并没有变差。因此，DBSCAN++算法是有效的。