基于变化密度的自适应空间聚类方法研究

杨亚军，张坤龙，杨晓科

(天津大学计算机科学与技术学院，天津 300072)

1 概述

聚类是一种十分重要的数据挖掘方法。它的目标是将数据对象进行分组，使得组内对象之间的相似性比组间对象之间的相似性大。聚类具有广泛的用途，它既可以用于理解客观世界，同时也可以作为其他数据挖掘方法的预处理，例如可以用于孤立点检测等［1］。许多学者对聚类进行了研究，他们提出了大量聚类算法，包括分层聚类、划分聚类、基于密度的聚类、基于格的聚类、基于模型的方法和一些比较新的方法，例如核聚类、谱聚类、蚁群聚类等。其中基于密度的聚类比较优秀，它可以聚类任意形状和大小的簇。

DBSCAN (Density Based Spatial Clustering of Applications with Noise)［2］是基于密度聚类的基础。它认为簇是由稀疏部分隔开的稠密区域，因此可以通过扩展密度大的点即核点来发现簇。DBSCAN 能够聚类任意形状和大小的簇，并且不受孤立点的影响。但是当数据集的各个簇的密度不同，并且簇之间没有被稀疏部分隔开时DBSCAN 就会遇到困难，无法产生正确的聚类结果。许多算法针对变化密度进行 改 进，如SNN(Shared Nearest Neighbor)［3］和VDBSCAN(Varied Density Based Spatial Clustering of Application with Noise)［4］等，它们虽然可以发现不同密度的簇，但在某些情况下无法产生正确的结果，并且选择合适的参数是十分困难的。

针对参数不易选择和无法处理变化密度的问题，本文对DBSCAN 算法进行了改进，并提出了一种自适应的基于变化密度的空间聚类方法(SAVDBSCAN)。算法以点到其第k 个最邻近邻居的距离作为密度，若一个点的密度与其k 个最邻近邻居中的每个点的密度相似，则将该点作为核点进行扩展。对于相似性判断，首先由用户给定一个阈值，然后算法在每次加入一个核点后进行自适应，得到一个更合适的值。

2 相关研究

DBSCAN［2］是基于密度聚类的奠基，它认为簇是由稀疏或者空白区域隔开的稠密区域。DBSCAN 引入了密度的概念，定义一个点的密度为以该点为圆心用户指定大小Eps 为半径的圆内的数据点的个数，并将密度大于用户给定阈值MinPts 的点定义为核点。算法通过扩展相通的核点来发现簇。DBSCAN 可以发现任意形状和大小的簇，并且不受孤立点的影响。DBSCAN 的算法复杂性为O(N2)，如果存在空间索引，其算法复杂性为O(NlogN)。但是当簇的密度有显著的变化并且簇之间没有被空白或稀疏区域隔开，DBSCAN 无法产生正确的结果，并且选择合适的参数Eps 和MinPts 是很困难的。

OPTICS［5］针对DBSCAN 无法处理变化密度的问题进行了改进。OPTICS 并不显式的进行簇标记，而是分析生成一个有序对象列表。从这个排序的列表中可以得到任意参数Eps 和MinPts 的DBSCAN 的聚类结果。

SNN(Shared Nearest Neighbour)［3］使用2 个节点共享邻居的个数来度量相似性。算法利用稀疏化的相似矩阵来构建共享邻居图，并利用共享邻居图计算出每个点的SNN 密度。然后利用DBSCAN 的方法进行聚类。SNN 算法可以有效地聚类不同大小、形状和密度的簇，但是算法复杂性高，并且参数的选择也比较麻烦。

VDBSCAN［4］是另外一个对DBSCAN 进行改进的算法。VDBSCAN 利用k 邻居距离图得到一系列局部Eps 值，并从最小的局部Eps 开始依次对未标记的数据对象应用DBSCAN，直到所有的局部Eps值都已处理完，则算法结束。VDBSCAN 可以处理不同密度的聚类，但是算法比较复杂，需要先绘制k 邻居距离图，并且有的时候k 邻居距离图无法明显的反映出局部Eps 值，k 的选择也是比较困难的。

此外，文献［6-11］对DBSCAN 不能处理变化密度的问题提出了改进，其中，文献［7-8］提出了参数自适应的思想，试图在算法运行的过程中自动对参数进行选择。

以上提到的各种聚类算法都尝试解决不同形状、大小和密度的聚类问题。尽管有的算法可以取得相当好的聚类效果，例如SNN，但它们都存在一个相同的问题，即算法对参数十分敏感，并且选择合适的参数是十分困难的。

3 DBSCAN 算法

3.1 算法基本思想

DBSCAN 之所以不能聚类变化密度的簇，是因为它有2 个全局的参数Eps 和MinPts，在算法开始时给定参数的值，并且运行时不会改变。当簇的密度发生变化时，一个全局的参数无法对所有的簇都适用，因此必须能够针对不同的簇合理的给出密度，并且这个密度在不同的簇之间是可以变化的。

对空间数据的特征进行研究，发现同一个簇内的点到其第k 个最邻近邻居的距离大致是相同的，而来自不同密度的簇中的点到其第k 个最邻近邻居的距离有显著的差异［4］。这个结论可以通过绘制k邻居距离图来证明。k 邻居距离图是将所有点按照到第k 个最邻近邻居的距离升序排列，然后以点在排序中的位置为横坐标，以该点到第k 个最近邻居的距离为纵坐标绘制而成。因此，以点到其第k 个最邻近邻居的距离作为密度就可以满足同一簇中的密度相似，而不同密度簇中的点密度存在差异。

有了密度的定义之后，需要对数据点进行遍历，将那些相通的密度相似的点聚类到同一个簇中，并且要识别出簇边界，停止当前簇的扩展。根据密度的定义，簇的边界就是点的密度发生显著变化的地方。因此，只有当一个点的k 个最邻近邻居的密度与该点相似时，该点才作为核点进行扩展，并且依次扩展它的k 个邻居。

例如图1 为一个包含18 个点的数据集A 的散点图，这个数据集包括2 个簇，每个簇分别有9 个点，该数据集的2 邻居距离图如图2 所示。其中，9 个点到第2 个最邻近邻居的距离为1，它们都属于簇1。有7 个点到第2 个最邻近邻居的距离为2，它们属于簇2。还有2 个点a 和b 到第2 个最邻近邻居的距离为1.41，它们属于簇2，但是位于簇2 和簇1 的交界处。若算法首先处理d 点，其最邻近2 邻居为c 和f，由于c 和f 的密度与d 相似，则d 为核点，标记为簇1，然后依次处理c 和f。先将c 标记为簇1，然后判断c 的二邻居为a 和g。由于a 的密度与c有显著差异，则c 不作为核点，接下来用同样的方法处理其余的点。这样可以识别出簇边界，并且停止当前簇的扩展。

图1 数据集A 散点图

图2 数据集A 的2 邻居距离示意图

当多个点之间的距离相同的时候，会出现一个问题，称之为封闭集团。一个封闭集团是一个点的集合，并且该集合内的所有点的k 个最邻近邻居也在该集合内。例如图1 中的{d，f，e，g}即为一个封闭集团，其中，d 的邻居为e 和f，f 的邻居为d 和g，g的邻居为e 和f，e 的邻居为d 和g。这样在扩展簇1的时候一旦进入这个封闭集团就无法出来，不能产生正确的结果。为了克服这个问题，计算一个点的最邻近邻居的时候，首先计算k 个最邻近邻居，然后将到该点的距离与第k 个最邻近邻居到该点距离相同的点也加入到邻近邻居集合中，并且进行核点判断的时候，只要最邻近邻居中有不少于k 个邻居的密度与当前扩展点的密度相似，就将该点作为核点扩展。

此外，算法可以在运行的时候根据已经处理的点的性质，动态更新参数的值，使之趋向于真实的值。

3.2 算法描述

在介绍改进算法之前，需要对DBSCAN 中的一些定义进行修改，并且增加一些新的定义，其中，2 个点p 和q 的欧几里德距离用dist(p，q)表示，D 表示聚类数据集，它是d 维空间Rd中点的集合。

定义1(density(p)) 一个点p 的密度为p 到其第k 个最邻近邻居的距离。其中，k 为用户给定的参数。

定义2(N(p)) 一个点p 的N(p)表示点p 的最邻近邻居的集合，首先是将p 的k 个最邻近邻居加入到N(p)中，然后将那些到p 的距离与p 的第k 个最邻近邻居到p 的距离相似的点也加入到N(p)。即当所有的邻居到p 的距离不同时，N(p)的势为k，否则N(p)的势可能大于k。

定义3(cdensity(p)) 一个点p 的cdensity (p)表示p 所属的簇中当前已经扩展的核点的density 的平均值。

定义4(similar-neighbor(p，q)) 如果p 的邻居q 是p 的相似邻居，当且仅当式(1)成立，α 为用户指定的参数。

定义5(核点) 一个点p 称之为核点，当且仅当它的最邻近邻居中至少有k 个是p 的相似邻居。

定义6(边界点) 一个点p 为边界点，当且仅当它是一个核点的相似邻居，但是它不是核点。

定义7(孤立点) 一个点p 为孤立点，当且仅当p 既不是核点也不是边界点。

用包含4 个字段的结构体表示空间中的每个点，4 个字段为:该点的坐标，簇标号字段Cp，最邻近邻居数组(用来保存最邻近邻居)和密度density。初始时，Cp=-1，density=-1。一个点有3 种状态:已处理，候选处理和未处理。

定义8(已处理) 若一个点p 的状态为已处理，则该点的density(p)已经计算得出，它的最邻近邻居中的任意一点q 的density(q)也已计算出，并且簇标记Cp 不等于-1。

定义9(候选处理) 若一个点p 的状态为候选处理，则该点的density(q)已经计算得出，Cp 不等于-1，但是它的最邻近邻居中至少存在一点q 的density(q)未计算出。

定义10(未处理) 若一个点p 的状态为未处理，则该点的Cp 值为-1，该点的density (q)也为-1。

此外，算法还需要一个队列corequeue 和一个全局变量current-cluster-id。其中corequeue 用来保存候选扩展的核点，current-cluster-id 保存当前簇的簇标号，初始值为0。

算法从未处理的点中选择一个点p，计算它的密度density(p)，并且计算它的最邻近邻居中所有点q的密度density(q)，同时判断q 是否为p 的相似邻居。若p 的最邻近邻居中至少有k 个是它的相似邻居，那么p 就是一个核点，即说明发现了一个新的簇，此时应该将current-cluster-id 的值加1，并且将点p 加入到corequeue 中。若corequeue 非空，则从中弹出一个核点curcore，将其簇标号Cp 设置为current_cluster_id 的值，并且依次处理它的最邻近邻居。对于每一个邻居q，首先将q 的Cp 值设置为currentcluster-id 的值，然后计算q 的密度变化率是否小于α，并且判断q 的最邻近邻居中是否至少有k 个是q的相似邻居，若是则q 为核点，将q 加入到队列corequeue 中，然后再从corequeue 弹出一个点，按上述方式处理，直到corequeue 为空，则表示一个簇已经扩展完成，算法再从剩下的未处理的点中找一个点重复上述过程，直到所有的点都已经处理完毕。算法的伪代码如下:

函数isCore 用来判断一个点是否为核点。传入参数p 为要判断的点，c 为当前簇的平均密度，α为密度变化阈值，D 为数据集。若一个点的最邻近邻居中至少有k 个是它的相似邻居，那么该点就是核点。对于簇的起始核点和扩展核点的处理存在差异。簇的起始核点的最邻近邻居必须是没有簇标号的，即它的最邻近邻居中至少有k 个没有簇标号的邻居是它的相似邻居，那么该点才作为簇起始点。

update cdensity 是对当前簇的簇密度进行更新，update α 是对密度的变化阈值进行更新，这2 个方法将在3.3 节详细介绍。

3.3 自适应机制

空间数据中同一个簇中的点的密度大致相同，它们近似服从高斯分布［7］，算法用已扩展核点的密度的平均值作为均值。基于这个思想，在对p 的邻居q 进行相似邻居判断的时候，用当前簇中已处理过的核点(包含点p)的密度的平均值cdensity(p)来代替density(p)，则相似邻居的判定公式就变为式(2):

cdensity(p)的值在每次从corequeue 中弹出一个核点的时候按式(3)更新:

其中，n 为包括p 在内的当前簇中已扩展的核点个数;cdensity(p)'是不包含点p 的簇密度平均值。这样用均值代替某个点可以避免个别特殊点引起的聚类错误。

密度的波动为方差，方差在［0，α)区间内，其中，α 为波动范围的上界。对于α，首先由用户指定一个阈值，然后算法在运行的过程中，根据每次弹出核点密度偏离中心的程度对α 的值进行动态更新。具体的，当从corequeue 中弹出一个核点p 时，根据式(4)计算它偏离中心的程度d。

然后根据式(5)对α 进行自适应。当d 的值小于α/2 时，需要对α 进行缩减。当d 的值大于α/2时，需要增加α 的值。缩减的比例小于增加的比例。这是因为α 是偏离中心程度的上限，根据高斯分布的特征，大部分数据集中在中心值周围，若缩减的过快，就会因为这些值的影响，而将α 减小到一个比较小的值，从而不能发现那些d 较大但是满足相似邻居的点。这个缩减比例是经过大量实验之后确定的一个相对比较优的值。

3.4 算法分析

算法需要处理所有的数据点，即需要在所有点上执行一次迭代，时间复杂度为O(N)，对于迭代中的每一个点，首先需要计算它的k 个最邻近邻居，如果没有空间索引，计算k 个最邻近邻居需要扫描一遍数据集中的所有点，需要的时间为O(N)，若存在空间索引R 树，根据R 树查找最邻近邻居的时间复杂度是O(logN)。然后是在核队列上进行循环，循环与N 无关，所以时间复杂度为O(1)，对于核队列中的每个点，需要处理它的k 个邻居，这个与N 无关，所以时间复杂度也为O(1)。因此，若没有空间索引，算法的时间复杂度为O(N2)。若存在空间索引，聚类的时间复杂度为O(NlogN)，建树的时间复杂度也为O(NlogN)，并且两者不相关，所以算法的时间复杂度也为O(NlogN)。

综上所述，若不存在空间索引，算法的时间复杂度为O(N2)，若存在空间索引R 树，算法的时间复杂度为O(NlogN)。由此可见，本文提出的算法的时间复杂度和DBSCAN 相同。

3.5 参数选择

算法有3 个输入参数:dataset，k 和α。其中，dataset 是聚类的输入数据集，这个参数对于所有聚类算法都一样，在这里不做讨论。第2 个参数k 是要计算的最邻近邻居的个数，类型为整数。k 的选择偏小会将一个自然簇分裂成若干个，k 的选择偏大，可能会合并自然簇。根据大量的实验，k 一般选择8～16之间的整数可以取得比较好的聚类效果。α是度量相似邻居的阈值，即允许密度变化率的最大值。若α 选择过大，则会合并自然簇，若α 的选择偏小，则会将一个自然簇分裂。因为算法有自适应功能，所以α 一般选择0～1 之间的一位小数即可，算法运行过程中可以自适应到合适的值。由此可见，本文提出的算法的参数空间是比较小的，因此较容易选择合适的参数。

4 实验分析

这一部分评估了SAVDBSCAN 算法，并且与CHAMELEON［12］和SNN 的结果进行了比较。用Java 实现了SAVDBSCAN 算法，在一个双核，主频为2.6 GHz，内存2 GB，安装有Linux 操作系统的机器上进行了实验。

4.1 实验数据

本文在4 个数据集上测试了算法的聚类效果。其中前2 个数据集是来自CHAMELEON 算法的实验数据，分别是t7.10k.dat 和t8.8k.dat。另外2 个是自己产生的数据集，包括dataset1 和dataset2。其中，dataset1 是一个由6 000 个点组成的3 个嵌套的同心圆，每个圆环里有2 000 个点，最里边的圆的密度最大，向外密度依次降低，如图3 所示。dataset2 是一条由5 400 个点组成的“鱼”，眼睛的密度最高，尾巴的密度最低，如图4 所示。

图3 dataset1 散点图

图4 dataset2 散点图

4.2 结果分析

CHAMELEON 数据集的聚类结果如图5(a)和图5(b)所示。不同的形状代表不同的簇，孤立点已经被消除。具体地，图5(a)为t7.10.dat 的结果，其中，k 为11，α 为0.7。图5(b)为t8.8k.dat 的聚类结果，k 为14，α 为0.6。算法的聚类结果与SNN 算法和CHAMELEON 算法的聚类结果相似，不同之处在于对边界和孤立点的处理存在微小差异，SNN 和CHAMELEON 的结果可参照相关文献。算法可以准确地发现自然簇，并且识别出孤立点，而且参数设置更简单，相同的结果可以有多种参数选择，具体如表1 所示。

dataset1 的聚类结果如图5(c)所示，k 取16，α为0.9，算法准确地发现了3 个簇，分别用3 种不同的颜色标记。而且在边界上的聚类也很准确，比较光滑，没有出现锯齿。图5(d)为dataset2 的聚类结果，k 为16，α 为0.4。从图上可以看出算法能够准确地识别出“鱼”的各个部分。

图5 聚类结果

表1 参数设置

实验结果表明，算法可以准确地聚类任意形状、大小和密度的簇，并且识别出孤立点，可以取得与CHAMELEON 和SNN 相同的聚类结果。此外，通过自适应，参数的设置也变得十分容易，同样的结果可以有多种参数设置。

5 结束语

本文针对DBSCAN 不能处理变化密度的缺点，提出一个改进的算法SAVDBSCAN。算法基于同一个簇中的点到其第k 个邻居的距离比不同簇中的点相似的思想，将一个点到其第k 个最邻近邻居的距离作为密度的度量，并且引入了相似邻居的概念，若一个点p 的邻居q 的密度与p 的密度变化率小于用户给定的阈值，则q 为p 的相似邻居。然后重新定义核点，一个点的最邻近邻居中至少有k 个相似邻居，则该点为核点。在修改后运用DBSCAN 算法进行聚类。为了取得更好的聚类效果，算法进行了参数的自适应，主要有2 个方面:(1)在计算一个点的相似邻居时，以该点所在的簇当前已扩展核点的密度的平均值代替该点的密度;(2)在进行相似邻居判断时，自适应变化阈值α。通过自适应机制，本文算法可以在运行时根据数据的分布情况，自动调整参数的值，从而更好地发现自然簇。实验结果表明，SAVDBSCAN 可以发现任意形状、大小和密度的簇，并且有效地检测出孤立点。此外，可以取得和SNN 以及CHAMELEON相似的聚类效果，并且参数空间更小，取得合适的参数比较容易。下一步工作将根据数据的特性，自动选择合适的k 值，使得不同密度簇中的点到第k 个最邻近邻居的距离有明显的差异。

［1］Xu R，Wunsch D.Survey of Clustering Algorithms［J］.IEEE Transactions on Neural Networks，2005，16(3):645-678.

［2］Ester M，Kriegel H P，Sander J，et al.A Density-based Algorithm for Discovering Clusters in Large Spatial Databases with Noise［C］//Proc.of Conference on Knowledge Discovery and Data Mining.Portland，USA:AAAI Press，1996:216-224.

［3］Ertoz L，Steinbach M，Kumar V.Finding Clusters of Different Sizes，Shapes，and Densities in Noisy，High Dimensional Data［C］//Proc.of SIAM International Conference on Data Mining.Chicago，USA:［s.n.］，2003:333-341.

［4］Liu P，Zhou D，Wu N.Varied Density Based Spatial Clustering of Application with Noise［C］//Proc.of International Conference on Service Systems and Service Management.Chengdu，China:［s.n.］，2007:123-129.

［5］Ankerst M，Breunig M M，Kriegel H P，et al.OPTICS:Ordering Points to Identify the Clustering Structure［J］.ACM SIGMOD Record，1999，28(2):49-60.

［6］马 帅，王腾蛟，唐世渭，等.一种基于参考点和密度的快速聚类算法［J］.软件学报，2003，14(6):1089-1095.

［7］陈 刚，刘秉权，吴 岩.一种基于高斯分布的自适应DBSCAN 算法［J］.微电子学与计算机，2013，30(3):27-30.

［8］夏鲁宁，荆继武.SA-DBSCAN:一种自适应基于密度聚类算法［J］.中国科学院研究生院学报，2009，26(4):530-538.

［9］于亚飞，周爱武.一种改进的DBSCAN 密度算法［J］.计算机技术与发展，2011，21(2):30-33.

［10］欧阳佳，林丕源.基于DBSCAN 算法的网页正文提取［J］.计算机工程，2011，37(3):64-66.

［11］蔡 岳，袁津生.基于改进DBSCAN 算法的文本聚类［J］.计算机工程，2011，37(12):50-52.

［12］Karypis G，Han E H，Kumar V.Chameleon:Hierarchical Clustering Using Dynamic Modeling［J］.Computer，1999，32(8):68-75.