基于最小生成树的密度聚类算法研究

王 诚 ，高兴东

(南京邮电大学 通信与信息工程学院，江苏 南京 210003)

0 引 言

数据挖掘伴随着互联网数据产生速度的大幅提升，已经在越来越多的领域发挥作用。同时互联网中的数据大多为无标签数据，聚类算法的优势得以体现。聚类分析作为数据挖掘中至关重要的技术之一，目前已经在医疗、交通、电力、品质育种等领域得到了广泛应用。基于密度的聚类算法是目前应用较为广泛的聚类分析算法之一。其中典型的算法有DBSCAN算法、OPTICS算法等。文献[6]提出的DBSCAN算法对于Eps和MinPts敏感，同时二者为全局参数，虽然可以发现任何形状的簇，但在运算过程中参数无法更改，所以无法正确处理密度分布不均匀的样本。文献[7]提出了OPTICS算法，该算法并不直接得出结果簇，而是得出一个增广的簇排序，即得到基于任何参数Eps和MinPts组合的DBSCAN算法的聚类结果，在结果中选择聚类效果好的参数组合，该算法并没有在本质上解决如何选择参数的问题，且过程产生了不必要的运算量；同时这种排序导致低密度点与高密度点的相邻关系在映射时被分离。另外，文献[9]提出首先使用K-Means算法对数据集进行分析以确认输入参数再进行数据集的聚类；文献[10]提出可以利用绘制k-dist图的方式确认Eps的值进而确认MinPts的值；文献[11]通过分析数据集平均数等统计特性，运用多组数据之间的比较得以确定Eps参数；文献[12]提出KANN-DBSCAN算法利用

k

-近邻确定Eps候选集合，通过

k

的数学期望确定MinPts参数。文献[13]提出了一种基于局部特征的层次聚类算法，对不同密度样本分别处理，解决样本密度分布不均的聚类的问题。受上述研究启发，可以使用对于算法结果影响较小的参数降低原算法中对于参数的敏感程度。该文提出一种基于最小生成树的密度聚类算法。首先通过计算样本点之间的相互可达距离构建无向有权图并求解其最小生成树；再通过预设的最小簇对象数

n

对最小生成树进行剪枝，将最小生成树中的节点中，子孙节点数不大于最小簇对象数的节点及其子孙节点标记为噪声；最后，根据预设的簇的个数

k

分割最小生成树并对分割结果进行聚类，解决了传统算法对于参数敏感的问题(将该算法命名为MST-DBSCAN)。

1 DBSCAN算法

DBSCAN算法是一种经典的空间密度聚类算法，该算法可以聚类任何形状的簇并能够自动确定簇的数量，不需要人为设定具体的簇数。与其他聚类算法不同，该算法通过从随机的数据对象开始向外扩散的方式在数据集中进行对象的聚类。该算法在众多聚类算法中应用较为广泛且效果较好，其中主要定义如下：

定义1(Eps邻域)：在数据集样本中随机选择1个数据对象

p

，其邻域

N

(

p

)定义为以

p

为核心，Eps的值为半径的多维区域，即：

N

(

q

)={

q

∈

D

|dist(

p

,

q

)≤Eps}

(1)

其中，

D

为数据集中所有对象的集合，

q

为数据集中的对象，dist(

p

,

q

)表示

p

、

q

两对象之间的距离。定义2(核心点)：对于数据集中的对象

p

，如果在对象

p

的邻域内的对象数大于等于核心点阈值MinPts，则将对象

p

称为核心点。定义3(直接密度可达)：数据对象

p

、

q

关于Eps和MinPts直接密度可达当且仅当满足公式2、公式3。

p

∈

N

(

q

)

(2)

|

N

(

q

)|≥MinPts

(3)

其中，

q

为核心点。定义4(密度可达)：数据对象

p

、

q

，如果存在对象链路

p

,

p

,…,

p

,

q

，对于

p

+1和

p

关于Eps和MinPts直接密度可达，则称

p

、

q

关于Eps和MinPts密度可达。定义5(密度相连)：类比定义4，当对象链路上的所有对象关于Eps和MinPts密度可达，则称

p

、

q

关于Eps和MinPts密度相连。

定义6(噪声、簇)：从一个核心点出发，所有与当前核心点密度可达的点的集合构成一个簇；同理，所有核心点都密度不可达的对象称为噪声。

基于以上定义，DBSCAN算法核心思想为，将数据集中所有的对象按照密度是否可达划分为不同的簇，对于密度不可达的对象标记为噪声对象。其过程为：

(1)随机选取数据集中的一个对象，判断该对象是否为核心点。如果为核心点，则将该对象标记为核心点并作为簇的起点；如果不是核心点标记为非核心点；

(2)从(1)中选取的核心点出发，寻找所有和该对象密度可达的所有对象，加入当前核心点的簇中，并以核心点的簇中的对象为起始点继续迭代寻找更多的核心点放入核心点簇中；直至当前核心点簇中的所有核心点无法找到更多满足条件的密度可达的对象为止；

(3)重复过程(1)(2)，直到所有的密度可达的对象都聚类成簇。

DBSCAN算法使用欧氏距离表示对象和对象之间的距离，同时使用从核心点向外拓展寻找簇的方式，可以发现任意形状的簇。

2 MST-DBSCAN

传统DBSCAN算法存在几点弊端：第一，传统算法无法使用同一组参数将密度分布不均匀的数据集中的两种或多种密度的数据进行准确的聚类。第二，需要人为指定参数且参数对于算法结果的影响很大。在MinPts确定的情况下，选择的Eps参数越小，簇中对象和对象之间的距离越小，簇的密度越高。但如果选择了过小的Eps，使得对象的选择过于苛刻，会导致大多数的对象被错误标记为噪声，增加了噪声的数量导致算法准确性降低，同时原本为一个簇的对象也会被拆分为多个簇，将相似的对象簇进行了过度拆分；如果选择了过大的Eps会导致对象的选择条件降低，很多噪声被错误地归入簇，原本独立的各个簇也会被归为一类，降低了聚类的有效性。在Eps确定的情况下，选择的MinPts越大，同一簇中的将包含更多的对象簇的密度越高。选择了过小的MinPts会使得大量的对象被标记为核心点，同一个簇中从核心点出发会包含更多的噪声；过大的MinPts会导致核心点数量减少，使得一些边缘对象被错误舍弃。

针对以上弊端对算法进行改进，改进后的MST-DBSCAN算法定义如下参数：

定义7(簇的个数

k

)：对数据集聚类后期望得到簇的个数。定义8(最小簇对象数

n

)：数据集聚类期望得到簇中对象数的最小值。

改进算法的步骤如下：

Step1：距离计算。

传统算法中常使用欧氏距离表示对象与对象之间的距离，但考虑到数据集中对象的密度分布不均匀，而欧氏距离反映的是空间内的真实距离，对于分布不均的数据集的对象之间的距离无法归一化，密度大的区域的对象之间的距离和密度小的区域的对象之间的距离没有可比性，所以使用相互可达距离，如公式4，代替样本点之间的真实距离。经过距离替换后大密度区域的对象之间距离不受影响，小密度区域的对象之间的距离被放大，起到了归一化的作用，使得大密度区域和小密度区域的对象之间的距离可以进行比较，增加了聚类算法对散点的鲁棒性；同时使用相互可达距离代替欧氏距离可以使单链路聚类算法更加贴合地去拟合数据集中的密度分布。

d

(

p

,

q

)=max{core(

p

),core(

q

),

d

(

p

,

q

)}

(4)

其中，

k

表示距离当前对象第

k

近的对象，该参数对聚类结果影响不大，通常设置为

N

*0

.

02(

N

为数据集对象总数)；

d

(

p

,

q

)表示对象

p

、

q

之间的相互可达距离；

d

(

p

,

q

)表示二者之间的欧氏距离；core(

p

)表示对象

p

的核心距离，即与对象

p

与第

k

近的对象的距离，具体计算方法如下；core(

x

)=

d

(

x

,

N

(

x

))

(5)

其中，

N

(

x

)表示数据集中以

x

为中心第

k

近的对象。

Step2：构建最小生成树。

利用Step1中求解的相互可达距离构建距离加权无向图。构建该无向图的邻接矩阵：

(6)

其中，

d

表示数据集中对象

p

、

q

之间的相互可达距离。使用Prim算法计算当前邻接矩阵的最小生成树，建立数据集中所有对象之间的联系。该算法是图论中一种常用的求解最小生成树的算法，以权值最小的边为主导，再加权有向图中搜寻最小生成树，使得生成树的权最小，即：

(7)

其中，

W

(

T

)表示树

T

的权，

A

表示树

T

的边的集合，

d

表示有向图中点(

p

,

q

)之间的权。

算法步骤如下：

(1)初始化：定义图中的所有顶点集合为

V

，全部边的集合为

E

，选中的顶点的集合为

V

，选中的边的集合为

E

，将

V

及

E

初始化为

V

={}，

E

={}。随机在

V

中放入集合

V

中的任意节点

p

作为算法的起始节点，即

V

={

p

}；(2)构建树：在所有

p

∈

V

，

q

∈

V

-

V

的边(

q

,

p

)∈

E

中找到权值最小的边

e

=(

p

,

q

)放入集合

E

中，同时将

q

放入

V

中；(3)递归：重复步骤(2)中构建树的过程，直到所有的顶点都放入到

V

中为止，即

V

=

V

。此时

E

中存在

N

-1条边及

N

个点。将

E

中的所有边，按照起点-终点-权重的方式封装，并将封装后的结果放入列表PTList中。

Step3：簇的聚类。

通过Step2后生成的最小生成树，将数据集中的所有对象连接起来。通过切断节点和节点之间的边，将最小生成树切断成为多个独立的子树。具体步骤如下：

(1)将生成的PTList按照距离降序排序；

(2)依次选取步骤(1)排序后距离最大的边的两个节点

i

、

j

，将这两个节点之间的边断开，并计算节点

i

、

j

的所有子孙节点的个数，记为

N

、

N

，不妨设

N

≤

N

。如果某一个节点的子孙节点个数不小于最小簇对象数，即min(

N

,

N

)≥

n

，则将节点

N

及其所有子孙节点归为聚类的一个簇，放入队列

C

List中；否则将上述子孙节点全部标记为噪声节点；(3)重复步骤(2)，直到有

k

-1个簇被放入了

C

List中；(4)将没有被标记的节点组成标记为一个簇放入

C

List中。

3 实验及结果分析

为了对改进后算法的聚类有效性进行评估，进行以下对比实验。将该算法与DBSCAN算法、文献[12]提出的KANN-DBSCAN算法以及OPTICS算法在公开数据集上进行对比。

实验环境：Intel(R) Core(TM) i7-8565U CPU @1.80 GHz 1.99 GHz，软件环境：JDK1.8、IDEA。

该文使用的聚类算法的评价指标选择调整兰德指数(ARI)、归一化互信息(NMI)、完整性指标及同质性指标。

调整兰德指数(ARI)是一种衡量两个数据分布的吻合程度的指标。兰德指数(RI)对两个随机的划分上存在缺陷，使得RI结果不是一个接近0的常数。ARI解决了该问题，其指标的取值范围为[-1,1]，值越大表示其聚类结果越接近真实结果，且对于随机聚类的ARI都非常接近0，其计算方法如下：

(8)

其中，RI为兰德指数，计算方法如下：

(9)

归一化互信息(NMI)指标是对互信息的归一化，是信息论中的一种信息度量的方式，可以理解为一个随机事件中包含另外一个随机事件的信息量。可以通过随机时间发生的概率计算得到。

(10)

其中，

I

(

X

;

Y

)表示两随机事件的互信息，

p

(

x

,

y

)表示二者的联合分布概率，

p

(

x

)及

p

(

y

)分别表示两事件单独发生的概率。

NMI将互信息的取值归一化在[0,1]之间，其取值越接近0表示聚类结果越差，越接近1表示聚类结果越接近真实结果，计算公式如下：

(11)

完整性及同质性是一种基于条件熵的聚类评估方法。二者往往存在一定的负相关关系。其中，完整性(completeness)表示在真实结果中某一簇的所有成员，经过聚类后被分配到单一簇的程度；同质性(homogeneity)表示聚类结果中每一个簇包含单一类别的成员的程度。两个指标的取值范围为[0,1]，越接近0表示聚类后的结果分布松散，对数据集的错误聚类情况越多，越接近1表示聚类结果越准确。计算方法如公式12和公式13：

(12)

(13)

其中，

h

表示同质性，

c

表示完整性，

h

、

c

的取值范围为[0,1]；

H

(

C

|

K

)及

H

(

K

|

C

)是给定簇

C

和

K

的条件熵，

H

(

C

)及

H

(

K

)是簇的熵。

选用以上4个参数作为聚类结果的评价指标，可以从聚类结果与真实结果的吻合度、聚类结果的准确性及聚类程度等多方面衡量聚类算法的聚类效果。

实验分别选择UCI公开数据集中的5个常用数据集，数据集包含了不同维度、不同分类数的数据集，各个数据集中的具体参数如表1所示。

表1 UCI数据集

4种算法在UCI数据集上的评价指标对比如表2所示。

表2 4种算法在UCI数据集上的评价指标对比

将5个数据集在DBSACAN、OPTICS、KANN-DBSCAN、MST-DBSCAN算法中的各个性能指标绘制成折线图，如图1所示。

图1 改进前后各指标对比结果

通过以上对比结果可以看出，MST-DBSCAN算法在各个数据集中的评价指标相比于传统算法都有着不同程度的改进，相比其他改进算法，该算法在整体效果上优于其他算法。虽然在Iris数据集中OPTICS算法的NMI及完整性指标高于MST-DBSCAN；在Thyroid数据集中KANN-DBSCAN算法的ARI及完整性指标优于MST-DBSCAN算法等，但从整体效果对比来看，随着数据集的特征数增加，MST-DBSCAN算法的ARI、同质性等聚类评价指标明显高于其他聚类算法。

在密度分布不均匀的数据集及高维度数据集中，改进的算法体现了优越性。在处理密度分布不均匀的数据集时，如Glass及Wine数据集，其中Glass数据集的不平衡问题最为突出，通过对比图1可以发现，MST-DBSCAN算法在4种评价指标上的表现都优于其他算法，其中NMI指标最为明显。在处理高维度数据集时，如Breast Cancer数据集，该数据集的数据维度为32，从评价指标中可以看出，MST-DBSCAN算法的表现同样优于其他算法。尤其对于KANN-DBSCAN算法，在ARI及NMI指标上有明显优势。

通过上述比较发现，该文提出的MST-DBSCAN算法的聚类效果最好，在密度分布不均及高维度数据集上的表现较好，DBSCAN和OPTICS算法的效果一般，KANN-DBSCAN算法在数据维度高的数据集的聚类效果最不理想。

4 结束语

该文运用最小生成树思想，对数据集中的对象构建最小生成树，通过指定簇的个数及最小簇对象数进行剪枝，因为指定了簇的数目，使聚类结果更加接近真实结果。进一步优化了DBSCAN对Eps及MinPts敏感的问题，选择使用更加容易确定的参数代替较难确定的参数，省去了原算法中对于Eps及MinPts选择的过程。同时通过在对象之间使用相互可达距离代替DBSCAN中使用的欧氏距离在一定程度上避免了维度灾难问题，解决了DBSCAN算法对于密度分布不均与数据集聚类效果不理想的问题。实验结果表明，MST-DBSCAN算法可以完成对于密度分布不均匀的数据集的聚类；同时，对高维数据集的聚类效果优于原DBSCAN算法。但MST-DBSCAN算法在低维数据集聚类效果不稳定，同时算法增加了聚类的复杂度，对于规模较大的数据集消耗时间较长。接下来的工作将继续降低算法的时间复杂度及低维数据集的聚类稳定性，将算法的聚类效果最优化。