刘宏凯 张继福

(太原科技大学计算机科学与技术学院 山西 太原 030024)

0 引 言

作为数据挖掘和机器学习的主要研究分支之一，聚类分析是一种广泛使用的无监督学习技术。聚类分析[1]在没有使用任何先验知识情况下，侧重于将数据集中的数据对象聚到簇中，目的是使簇内的数据对象相似性最大，并使不同簇间的数据对象相似性最小。基于密度的聚类算法[2]是一种典型聚类分析方法，其具有处理和识别噪声的能力，发现具有任意形状的簇和自动识别簇的能力等优点，并广泛地应用于化学[3]、模式识别[4]、图像处理[5]、机器学习[6]和生物学[7]等领域。

DBSCAN(Density-Based Spatial Clustering of Applications with Noise)作为一类有代表性的密度聚类分析方法，具有聚类速度快、预设参数对聚类结果的影响小和有效识别噪声对象等优点[8]。但其在聚类簇扩展过程中，由于核心对象的K近邻与逆近邻并集中包含的其他核心对象[8]可能属于不同密度的相邻聚类簇，并将原本属于不同密度簇的核心对象聚到同一个聚类簇中，从而造成在聚类簇扩展过程中，无法区分不同密度的相邻聚类簇，未能有效地体现真实的数据分布。本文采用逆近邻和影响空间相结合的思想，提出了一种密度聚类分析方法。该方法利用了逆近邻和影响空间形成聚类簇，数据对象与其影响空间中其他核心对象的邻域关系是对称的，从而保证了同一影响空间中核心对象属于同一密度的聚类簇，能够较好地估计邻域密度分布，并识别出不同密度的相邻聚类簇。

1 相关工作

聚类分析是数据挖掘、机器学习等领域中主要研究内容之一，可划分为基于统计[9]、基于分层[10]、基于模型[11]、基于密度、基于网格[12]和基于子空间[13-16]的方法等。基于密度的聚类分析是将密度大于预设阈值的区域定义为密集区域，并通过连接密集区域形成聚类簇。

密度聚类作为一类聚类分析方法，具有能够发现任意形状的聚类簇，可以很好地描述真实的数据分布特征，不需要预先设置要形成聚类簇的数量，数据集中数据对象的顺序与聚类结果无关等优点。Ester等[17]提出了著名的DBSCAN算法。此算法在聚类簇的密度不均匀、簇间距相差大时，聚类质量较差；对于高维数据，存在“维数灾难”问题。Vadapalli等[18]提出了RECORD算法。该算法无须输入任何预设参数，可以很好地反映数据集分布特征，但当一个离群点距离两个聚类簇的距离相等时，此算法对离群点簇标签的分配是不确定的。王晶等[19]提出了密度最大值聚类算法(MDCA)。其使用密度而不是初始数据对象作为考察簇归属情况的依据，能够发现任意形状的聚类簇并且不依赖初始数据对象的选择，但此算法需要在聚类前确定密度阈值；不适合数据集密度差异较大或整体密度基本相同的情况。夏鲁宁等[20]提出了可以自动确定Eps和minPts参数的SA-DBSCAN算法，但其对于密度不同的相邻聚类簇聚类效果较差。Cassisi等[21]提出了ISDBSCAN算法。此算法进行离群点检测阶段会错误地将核心对象识别为噪声对象除去，并且引入了第二个参数，降低了聚类精度。He等[22]提出了MR-DBSCAN并行算法，此算法在严重偏斜的数据环境中也能实现理想的负载平衡。Rodriguez等[23]提出了密度峰值聚类算法(DPC),其能快速发现任意数据集的聚类簇中心，并能高效地进行聚类与离群点去除，但该算法在数据集规模小时，主观选择的截断距离对聚类结果影响较大。Lü等[24]提出了ISBDBSCAN算法。其在ISDBSCAN算法的基础上，提出了非核心对象聚类的方法，但当两个核心对象到一个非核心对象的距离相等时，此算法对非核心对象簇标签的分配是不确定的。Bryant等[8]提出了RNNDBSCAN算法，该算法只需要一个预设参数，但由于采用K近邻与逆近邻的并集进行聚类簇扩展无法识别不同密度的相邻聚类簇，降低了聚类精度，并且聚类簇扩展过程中占用内存过大，降低了聚类效率。Parmar等[25]提出了基于残差的密度峰值聚类算法(REDPC)，采用残差计算来测量邻域内的局部密度，为聚类簇质心的识别提供了更好的决策图。

综上所述，密度聚类分析方法存在着当数据集大时，时间复杂度高；“维度灾难”，无法适用于高维数据集；识别边界点的簇标签不确定；当各个聚类簇的密度不均匀或聚类簇间的距离相差很大时，未能有效地识别或区分不同密度的相邻聚类簇等缺点，从而影响了聚类分析的精度和效率。

2 相关定义

2.1 K近邻与逆近邻

K近邻[26]是一种基本分类与回归方法，其目的是查找数据对象在数据集D的K密度聚类个最近邻数据对象。K近邻可以应用于分类、聚类、离群点检测、模式识别和入侵检测等领域中。逆近邻是在K近邻的基础上提出来，其含义就是在数据集D中找出将给定数据对象y作为其K近邻的数据对象集合。数据对象的逆近邻是基于全局的角度来检查它的邻域，数据分布的改变会导致每个数据对象的逆近邻发生改变，并且不会像K近邻一样随着维数的增加会出现“维数灾难”问题。

定义1(K近邻) 数据对象x的NNK(x)表示为距离x最近的K个数据对象的集合，其满足以下条件：

∀y∈D/{x,NNK(x)},z∈NNK(x):dist(x,z)

定义2(逆近邻) 数据对象x的RNN(x)表示为某些数据对象的K近邻中包含数据对象x的数据对象集合，其满足以下条件：

∀x,y∈D:x∈NNK(y),y∈RNN(x)

2.2 密度聚类

对于任意给定数据集D，其所包含的数据对象数为n=|D|，任意数据对象x∈D含有d维属性，RNN(x)表示数据对象x的逆近邻集，NNK(x)表示数据对象x的K近邻集，dist(x,y)表示数据对象x和y之间的欧氏距离。参照文献[8]，相关概念定义如下：

定义3(相似性距离度量) 在数据集D中，数据对象x和y的相似性度量dist(x,y)定义如下：

(1)

定义4(核心对象、边界对象、噪声对象) 在数据集D中，如果数据对象x的逆近邻|RNN(x)|≥K，则称x为核心对象。如果数据对象x的逆近邻|RNN(x)|

定义5(直接密度可达性) 如果数据对象y直接密度可达数据对象x，则其满足以下条件：

∀x,y∈D:x∈NNK(y)Λ|RNN(y)|≥K

因为数据对象的K近邻集关系是非对称的，所以核心对象之间的直接密度可达性是非对称的。因为核心对象与非核心对象之间的直接密度可达性也是非对称的，所以非核心对象不具有直接密度可达性。

定义6(密度可达性) 密度可达性是直接密度可达性的扩展，如果数据对象y密度可达数据对象x，则其满足以下条件：存在数据对象序列x1,x2,…,xm，xm可由xm-1直接密度可达，其中:

∃x1,x2,…,xm:x1=yΛxm=xΛ|RNN(y)|≥K

定义7(密度连接) 如果存在数据对象z，使得数据对象x和y可从数据对象z密度可达，则数据对象x和y是密度连接的。密度连接对于所有的数据对象都具有对称性。

定义8(聚类簇) 如果数据集D中存在非空聚类簇C，则满足条件：(1) 对于数据对象x和y，若数据对象x∈C且x密度可达数据对象y，则数据对象y∈C;(2) 对于数据对象x和y，有x∈C，y∈C，则x是密度连接于y。

2.3 影响空间

定义9(影响空间[18]) 在数据集D中，将数据对象x∈D的逆近邻集RNN(x)与K近邻集NNK(x)的交集定义为x的影响空间IsK(x)，且满足以下条件：

IsK(x)=RNN(x)∩NNK(x)

3 基于逆近邻和影响空间的密度聚类

3.1 影响空间与聚类簇扩展

在文献[8]中，RNNDBSCAN算法采用了K近邻与逆近邻的并集进行扩展聚类簇。由定义1和定义2可知，由于数据对象K近邻的邻域关系和逆近邻的邻域关系都不具有对称性，因此，数据对象与其K近邻和逆近邻并集中数据对象的邻域关系也不具有对称性。由定义5可知，数据对象与其K近邻和逆近邻并集中数据对象的直接密度可达性是非对称的，不能保证数据对象与其K近邻与逆近邻并集中的数据对象同属于相同密度的聚类簇。在密度聚类分析中，采用K近邻与逆近邻的并集进行聚类簇扩展无法区分不同密度的相邻聚类簇，从而造成聚类效果无法真实地反映数据对象的分布特征。

由定义5可知，因数据对象的K近邻关系是非对称的，则数据对象间的直接密度可达是非对称的。由定义9可知，任意数据对象x∈D与其影响空间中的其他数据对象间互为K近邻，则数据对象x与其影响空间中数据对象的邻域关系具有对称性。存在数据对象y∈D为核心对象(|RNN(y)|≥K)，由于核心对象y与其影响空间中的任意核心对象间互为K近邻，使其K近邻关系具有对称性，保证了核心对象y与其影响空间中核心对象的直接密度可达具有对称性。由定义7和定义8可知，核心对象y∈D的影响空间中任意数据对象是密度连接的，保证了核心对象和其影响空间中其他的核心对象属于相同密度的聚类簇。因此，数据对象x∈D可进行聚类簇扩展，应满足的条件重新描述如下：

|RNN(x)|>kΛIsK(x)≠NULL

(2)

在文献[8]中，RNNDBSCAN算法利用数据对象的K近邻和逆近邻的并集进行聚类簇扩展，因该并集中的数据对象可能属于不同密度的相邻聚类簇，造成了聚类算法无法识别不同密度的相邻聚类簇这一问题。在使用影响空间进行聚类簇扩展过程中，对于核心对象y的影响空间IsK(y)，若IsK(y)=NULL，由式(2)可知，y不满足聚类簇扩展的条件，因此无法从核心对象y进行聚类簇扩展，可暂且将核心对象y标识为“候选噪声对象”，并在噪声处理过程中，利用其K近邻关系将其与真正的噪声对象区分开；若IsK(y)≠NULL，由式(2)可知，y满足聚类簇扩展的条件。由定义9可知，因核心对象y与其影响空间IsK(y)中的任意核心对象互为K近邻，保证了核心对象y与其影响空间IsK(y)中的任意核心对象属于相同密度的聚类簇，提高了聚类算法区分不同密度簇的能力和聚类精度。由定义9可知，影响空间是K近邻和逆近邻的交集，影响空间中数据对象数明显少于RNNDBSCAN算法进行聚类簇扩展中使用的K近邻和逆近邻的并集，有效地降低了聚类算法在聚类簇扩展中对内存的压力，提高了聚类效率。

综上所述，式(2)给出的聚类簇扩展条件，避免了候选噪声数据对象参与到聚类簇扩展过程之中，有效地克服了RNNDBSCAN算法无法区分不同密度的相邻聚类簇问题,提高了密度聚类分析精度和效率。

3.2 KRDBSCAN聚类分析算法

根据3.1节，利用逆近邻和影响空间的思想，给出一种新颖的密度聚类算法KRDBSCAN。其聚类分析的基本步骤为：首先，为全部数据对象添加未聚类标签，并计算数据对象的K近邻NNK和逆近邻RNN；其次，从数据集中随机选择一个数据对象x∈D，如果数据对象x的逆近邻|RNN(x)|

算法1KRDBSCAN(KNN-RNN-DBSCAN)

输入：数据集D，近邻个数K。

输出：聚类簇CLUSTERS。

1.∀x∈D:x=UNCLASSIFIED;

//添加未聚类标签

2.cluster=1;

//初始化簇标签

3.NNK(∀x∈D),RNN(∀x∈D)

//计算K近邻与逆近邻

4.FOR(∀x∈D) DO

//随机选取数据对象x

5.IFx=UNCLASSIFIEDTHEN

6.IF EXPANSION(x,K,NNK(x),RNN(x),cluster) THEN

7.cluster=cluster+1;

//聚类簇扩展过程

8.END IF

9.END IF

10.END FOR

11.PROCESSING-NOISE(x,K,NNK(x));

//噪声处理

12.returnCLUSTERS;

//输出聚类簇

13.END KRDBSCAN

算法2EXPANSION(x,K,NNK(x),RNN(x),cluster)

输入：任意数据对象x∈D，近邻数K，簇标签cluster，K近邻集NNK(x)，逆近邻集RNN(x)。

输出：TRUE/FALSE

1.IsK(x∈D)=NNK(x∈D)∩RNN(x∈D);

//计算数据对象x的影响空间

2.IFRNN(x∈D)

3.x=NOISE;

//噪声对象(有可能是边界对象)

4.return FALSE;

5.ELSE

6.queue=NULL;

//初始化队列

7.IFIsK(x)=NULL THEN

8.x=NOISE;

//候选噪声对象

9.returnFALSE;

10.ELSE

11.queue.enqueue(IsK(x));

//将影响空间进队

12.assign[x+queue]=cluster;

//添加簇标签

13.WHILEqueue≠∅ DO

//广度优先遍历过程

14.y=queue.dequeue();

15.IFRNN(y∈D)≥KTHEN

16.FOR(z∈IsK(y)) DO

17.IFz=UNCLASSIFIED THEN

18.queue.enqueue(z);

19.z=cluster;

20.ELSE IFz=NOISE;THENz=cluster;

21.END IF

22.END FOR

23.END IF

24.END WHILE

25.return TRUE;

//聚类簇扩展完成

26.END IF

27.END EXPANSION

3.3 KRDBSCAN算法效率分析

在KRDBSCAN中，其算法的时间复杂度主要依赖于K近邻和逆近邻的求解。在算法1中,计算数据集中每个数据对象的K近邻，其时间复杂度是O(k×n2)；其次，计算数据集中每个数据对象的逆近邻，其时间复杂度是O(n2)；在算法2中,随机选择一个数据对象，采用影响空间进行聚类簇扩展，其时间复杂度是O(n2)；在算法3中,利用K近邻进行噪声处理，其时间复杂度是O(n)。因此，KRDBSCAN算法的时间复杂度是O(k×n2+n2+n2+n)≈O(k×n2)。

4 实验与结果分析

实验环境：Inter Core i5-7300HQ 2.50 GHz，16 GB内存，Windows 10操作系统，开发平台为Eclipse和Rstudio。使用Java语言和R语言实现了KRDBSCAN算法。实验数据采用UCI真实数据集和人工数据集。

为了验证KRDBSCAN算法聚类精度和聚类效率，实验采用Wireless、Act-Rec、Image、optdigits、avila和letter UCI真实数据集。UCI数据集如表1所示。

表1 UCI数据集

为了验证KRDBSCAN算法抗噪性，实验采用了Ari1、Ari2和Ari3人工数据集。Ari1是维度30、数据量为20 000条的高维数据集，其分为3个聚类簇，每个簇的方差为1.0、10.0和4.0。Ari2是维度50、数据量为50 000条的高维数据集，其分为4个聚类簇，每个簇的方差为1.0、5.0、6.0和10.0。Ari3是维度为40、数据量为30 000条的高维数据集，其分为5个聚类簇，每个聚类簇的方差为1.0、3.0、8.0、14.0和17.0。人工数据集如表2所示。

表2 人工数据集

为了验证KRDBSCAN算法的聚类精度与聚类效率，实验采用了标准化互信息(NMI)、调整兰德指数(ARI)和V-Measure度量指标。NMI是衡量聚类结果与真实簇标签间一致性的重要指标，能客观地评价出聚类结果与真实标签相比的准确度。ARI是衡量聚类结果和真实簇标签之间相似性的函数，忽略了聚类结果的排列顺序。V-measure是同质性和完整性之间的调和平均值。簇的同质性是指聚类结果中的数据对象都来自真实簇标签中单个聚类簇的数据对象的指数。簇的完整性是指能够将真实簇标签中属于相同聚类簇的数据对象聚为相同簇的指数。

为了实验验证本文算法KRDBSCAN在聚类精度、聚类效率和抗噪性的优越性，采用了当前具有代表性的密度聚类方法RNNDBSCAN[8]、ISDBSCAN[18]和RECORD[15]作为本文的对比算法。

4.1 聚类精度

在采用相同参数的情况下，标准化互信息的比较实验结果如图1所示，在UCI数据集中，KRDBSCAN算法的标准化互信息要高于其他密度聚类算法。KRDBSCAN算法在扩展聚类簇过程中使用了核心对象的影响空间，因为核心对象与其影响空间中的其他数据对象具有相互直接密度可达性，并且影响空间中数据对象是密度连接的，所以确保了核心对象与其影响空间中的其他数据对象属于相同密度的聚类簇，能够更好地估计邻域密度分布，显著提高了聚类结果的精度和质量。其中KRDBSCAN算法明显优于RECORD算法。其原因可能是RECORD算法引入了第二个预定参数，增加了人为因素对于聚类结果的影响，并对噪声对象的判断过于严格。在采用相同参数的情况下，调整兰德指数的比较实验结果如图2所示，在低维数据集Wireless和高维数据集optdigits中，KRDBSCAN算法的调整兰德指数要远远优于RNNDBSCAN、ISDBSCAN和RECORD算法，说明KRDBSCAN算法同时适用于高维数据和低维数据。其原因是在聚类簇扩展过程中引入了影响空间，而不是只考虑了K近邻，有效避免了在高维数据中易发生的“维数灾难”问题。在采用相同参数的情况下，V-Measure的比较实验结果如图3所示。在UCI数据集中，KRDBSCAN算法的V-Measure要远远优于ISDBSCAN和RECORD算法，并略高于RNNDBSCAN算法。其原因是KRDBSCAN与RNNDBSCAN算法使用数据对象的逆近邻识别核心对象。逆近邻是基于全局的角度来检查它的邻域，数据分布的改变会使每个数据对象的逆近邻发生改变。其可以更好地反映数据的分布特征。KRDBSCAN与RNNDBSCAN算法都采用一个预设参数，减少了人为因素对聚类结果的影响。

图1 标准化互信息

图2 调整兰德指数

图3 V-Measure

4.2 聚类分析效率

为了验证KRDBSCAN算法的聚类效率，实验在UCI数据集上将KRDBSCAN算法与RNNDBSCAN、ISDBSCAN和RECORD算法进行运行时间的比较。为了保证评估的准确性，实验采用5次运行时间取均值的方法进行聚类效率的比较，其实验结果如表3所示。KRDBSCAN算法的聚类效率略高于RNNDBSCAN和RECORD算法，并且其聚类效率远远高于ISDBSCAN算法。KRDBSCAN算法虽然需要计算影响空间，但其在聚类簇扩展过程中因减少了入队的数据对象而大大缩短了运行时间。而RNNDBSCAN算法在聚类簇扩展过程中需将数据对象的K近邻与逆近邻的并集入队，增加了算法的运行时间。总体上，KRDBSCAN算法的运行效率要优于RNNDBSCAN、ISDBSCAN和RECORD算法。

表3 聚类效率比较 单位:s

4.3 抗噪性

为了验证KRDBSCAN算法的抗噪性，实验中采用EXCEL工具中的数据生成器，生成噪声对象集，并在Ari1、Ari2和Ari3人工数据集上添加5%、10%和15%的噪声对象，实验比较标准化互信息、调整兰德指数和V-measure的变化情况。由图4、图5和图6可知，随着人工数据集中噪声对象数比例的增大，标准化互信息、调整兰德指数和V-measure都呈现降低的趋势。其原因是随着噪声对象的增多，KRDBSCAN算法将一部分噪声对象当作边界对象聚到聚类簇中，造成了评估指标的降低。但KRDBSCAN算法在数据集中每增加5%的噪声对象，评估指标降低约0.02到0.05之间，噪声对象对聚类结果影响并不大，KRDBSCAN算法在有噪声的数据集下依然具有很高的聚类质量，说明KRDBSCAN算法具有良好的抗噪性。

图4 Ari1抗噪性

图5 Ari2抗噪性

图6 Ari3抗噪性

5 结 语

针对密度聚类算法RNNDBSCAN中存在的无法识别不同密度的相邻聚类簇问题，本文给出一种新的基于逆近邻和影响空间的密度聚类算法KRDBSCAN，与传统的基于密度的算法相比，KRDBSCAN算法在三个方面都优于当前流行的密度聚类算法。首先，数据对象的逆近邻是基于全局的角度来检查它的邻域，数据分布的改变会导致每个数据对象的逆近邻发生改变，该算法采用逆近邻能真实地反映数据集中数据的分布特征。其次，KRDBSCAN算法采用逆近邻与影响空间相结合的思想，重新描述了聚类簇扩展的条件(|RNN(x)|>K∩Isk(x)≠NULL)，并在其扩展过程中，采用了影响空间中的数据对象，实现聚类簇的迭代扩展；由于影响空间中数据对象的直接密度可达性是对称的，保证了数据对象与其影响空间中的数据对象，同属于相同密度的聚类簇，因而可有效地区分不同密度的相邻聚类簇，使KRDBSCAN算法对局部密度变化高度敏感，能够更好地估计邻域密度分布，提高了聚类精度。最后，KRDBSCAN算法可以随机选择数据对象进行聚类，聚类结果与选取数据对象的顺序无关。实验结果表明，KRDBSCAN算法具有良好的聚类精度、聚类效率与抗噪性，并能很好地适用于高维数据集的聚类问题。下一步的研究工作是使用Spark平台并行化KRDBSCAN算法，使其适用于大数据分析。