基于累积平均密度的聚类方法＊

胡博磊，谭建豪

（湖南大学电气与信息工程学院，湖南 长沙 410082）

1 引言

聚类分析［1］是根据事物本身的特性研究个体的一种方法，它将数据分类到不同的类或组，并使得同一个组内的数据具有较大的相似性，而不同组中的数据则具有较大的相异性。作为数据挖掘中的一个重要研究课题，聚类分析被广泛应用于社会的各个领域，如图像分割、网络安全、统计分析和市场研究等。有关的聚类方法主要有：划分的方法、分层的方法、基于密度的方法、基于网格的方法和基于模型的方法。DBSCAN［2］是一种典型的基于密度的空间聚类方法，它通过不断生长足够高密度区域来进行聚类，能够从含有噪声的空间数据库中发现任意形状的聚类。但是，它需要用户输入参数，聚类结果严重依赖于用户参数的合理选择；并且它使用了一个全局密度阈值Minpts，对于存在多个不同密度的簇相连的数据集，聚类效果不佳。Minpts过高，会导致低密度簇被遗漏；Minpts过低，会导致高密度的簇被相邻的低密度的簇包含。国内外许多学者针对DBSCAN算法做了改进研究。冯少荣［3］等把智能计算理论引入到聚类研究中，提出了一种基于遗传算法的DBSCAN改进方案，提高了聚类效果。周董［4］等针对密度不均匀数据集，提出了一种改进算法，能够发现不同密度的簇。李光强［5］等根据邻近目标间空间局部密度变化情况来进行聚类，使算法能够自动适应空间位置的局部密度变化。武佳薇［6］等通过考察核心对象的邻域平衡性来有效地排除边界稀疏噪声对象，从而提高聚类精度。储岳中［7］等利用贝叶斯信息测度来优化聚类结果，从而很好地解决了合适的聚类半径选取问题。黎韶光［8］等对扩展空间对象的聚类进行了研究，并提出了相应的算法。

综上所述，对于簇相连的变密度数据集，现有大部分聚类算法要么不支持，要么聚类效果不理想。本文在现有的基于密度的聚类方法的基础上，引入累积平均密度的概念，设计算法时考量对象的区域相似性，使其能够对簇相连的变密度数据集进行有效的聚类分析。

2 DBSCAN算法

DBSCAN算法是基于中心的密度聚类方法，需要两个用户输入参数：半径ε和密度阈值Minpts。算法把密度定义为数据集中以某个给定对象为圆心、以给定ε为半径的空间区域中的对象的个数。并通过给定密度阈值Minpts把对象划分为核心对象、边界对象和噪声对象。密度不小于Minpts的对象称为核心对象，在至少一个核心对象的ε半径范围内且自身不是核心对象的对象称为边界对象，其余的对象称为噪声对象。算法将一个聚类定义为一组“密度互连”的对象的集合。其中密度互连相关的定义如下：

（1）给定对象集D，p，q∈D，若p属于q的ε－邻域，且q为核心对象，那么就说p从q直接密度可达。

（2）给定对象集D，若存在对象链p1，p2，…，pn∈D，p1＝p，pn＝q，对于pi，若pi＋1从pi直接密度可达，则称q从p关于ε和Minpts密度可达，其中1≤i≤n。

（3）给定对象集D，p，q∈D，若存在对象o，使得对象p和q都从o关于ε和Minpts密度可达，则称p和q是密度互连的。

DBSCAN算法的主要步骤为：首先从数据集中找到一个未被处理的核心对象，创建一个包含该对象的新类；然后根据这个核心对象，找到从其直接密度可达的对象，对它们设置类标记，并把它们加入到种子列表；接着，算法对种子列表中的核心对象进行扩展查询，找到核心对象的直接密度可达对象，将其设置类标记后加入到种子列表，并从种子列表中移除该核心对象，重复这个过程，直到没有新的对象加入到种子列表，则这个类的聚类过程完成。重复上述步骤，直到没有新的对象加入各个类时，整个聚类过程结束。

那些不属于任何类的对象被标记为噪声。DBSCAN可以从含有噪声的数据集中发现任意形状的聚类。

3 基于累积平均密度的聚类方法

针对DBSCAN算法的参数敏感性和不能区分相连的不同密度的簇等情况，本文提出了一种对DBSCAN的改进算法。算法先按照密度对数据集排序，然后用累积平均密度作为依据进行聚类，提升聚类质量。

3.1 累积平均密度有关概念

假设数据集为D，使用欧氏距离作为距离度量，这里，我们引入一些有关定义。

定义1 对象p的ε－邻域［1］：以p为圆心、ε为半径的空间区域，记作Nε（p）。

定义2 对象p的密度［1］：对象p的ε－邻域包含的对象的个数，记作d（p）。

定义3 中心对象：当前未被标识类标记的对象中密度最大的对象。

在整个聚类过程中，中心对象是阶段取值的。取一个中心对象，然后进行聚类，这个类的聚类过程完成后，取下一个中心对象，再进行聚类，依次进行，直至整个聚类过程结束。

定义4 对象p的累积平均密度：若p未被标识类标记，则p的累积平均密度为p的密度；若p已被标识了类标记，则p的累积平均密度为该类当前所包含的所有对象密度的算术平均值。记作c（p），其公式如下：

其中，p1，p2，…，pk是当前已被标识了p所在类标记的对象。

由定义可知，累积平均密度在聚类过程中是不断变化的，起始时，它等于中心对象的密度，然后每加入一个数据对象到中心对象所在的类，需要重新计算一次。

定义5 对象p对于对象q的容纳因子：假设q∈Nε（p），对象p对于对象q的容纳因子记作fp（q），公式如下：

表示的是q的密度和对象p的累积平均密度的相似度，fp（q）值越小，表示两者越相似，则q可以被容纳进p所在的类；fp（q）值越大，表示两者差距越大，则q不能被容纳进p所在的类。

定义6 核心对象：给定容纳阈值δ＞0，p∈D且p为中心对象或核心对象，q∈Nε（p），若fp（q）≤δ且d（p）≥Minpts，则称q为核心对象。

显然，这个概念的定义是递归的，初始时，只有中心对象，可以根据中心对象找出其邻域的核心对象，然后再根据这些核心对象寻找到其它核心对象。

直接密度可达、密度可达和密度互连以及聚类的定义与DBSCAN算法中的定义相同。

3.2 算法原理及描述

DBSCAN算法中只设置了一个密度下限，然后根据这个密度下限来收集直接密度可达对象进行聚类。而本文首次提出了累积平均密度的概念，并用它来考量密度的相似度（通过容纳因子来反映）。聚类过程中不但要考虑密度下限，还要考虑密度的相似性，只有密度相似度达到一定程度的对象才能聚为一类，降低了聚类的笼统性和随机性，增加了聚类的适应性和稳定性。首先找出密度最大的对象，然后收集和其密度相似的对象形成一个聚类，然后再找出剩下数据中密度最大的对象，重复上述过程直到所有数据都被归类，则得到聚类的最终结果。显然，对于相连的不同密度的簇，可以通过密度相似性把高密度的簇和低密度的簇区分开来。

算法需要三个输入参数：半径ε、密度阈值Minpts和容纳阈值δ。基本步骤如下：

Step 1 计算数据集中各个数据对象的密度并对其进行排序。

Step 2 确定中心对象。选取当前未被标识类标记对象中密度最大的对象作为中心对象p，若p的密度不小于Minpts，则对其设置类标记并创建一个包含对象p的新类；否则聚类结束。

Step 3 构建种子列表。把中心对象p的直接密度可达对象加入种子列表。

Step 4 类扩展。对于种子列表中的对象q，若满足条件fp（q）≤δ且d（q）≥Minpts，说明对象q是核心对象，则应对对象q设置类标记，把对象q的直接密度可达对象加入种子列表，并从种子列表中移除对象q；否则，说明对象q不是核心对象，则应把对象q从种子列表中移除。

Step 5 重复Step 4直至种子列表为空。表示完成了一个类的聚类过程。

Step 6 重复Step 2～Step 5直至整个聚类过程结束。

需要指出的是，在Step 4中弱化了密度阈值Minpts在合并簇的过程中的作用，Minpts主要被用来抑制噪声，簇的合并更多地依赖于容纳因子。在半径ε相同时，改进算法的密度阈值要比DBSCAN算法中的密度阈值小很多。因此，在某种意义上降低了算法对输入参数的敏感性。

4 实验及性能分析

通过实验分析改进算法的性能，并与DBSCAN算法进行比较。实验环境为Windows XP SP2操作系统，Intel（R）Pentium（R）Dual处理器，1GB内存，Eclipse 3.7和MATLAB 7.0开发环境。

4.1 处理时间

算法运行时间主要集中在以下两个步骤：Step 1的初始密度计算和Step 4的类扩展。Step 1的时间主要由邻域搜索时间和密度排序时间组成，Step 4的时间主要为邻域搜索时间。另外，可以在运行Step 1的时候记录下相关数据供Step 4使用，做到一次计算多次查询，从而省去Step 4中邻域搜索的时间消耗。程序中，密度排序采用归并排序算法实现，时间复杂度为O（nlogn）；邻域搜索的时间复杂度为O（n2）。在不使用空间索引的情况下，DBSCAN算法的时间复杂度为O（n2）［9］。因此，改进算法和DBSCAN算法相比，在时间复杂度上属于同阶，没有明显的差异。

4.2 实验

为了方便说明，我们使用两个二维数据集来对算法进行聚类实验。实验分为两步：（1）对簇不相连的数据集进行聚类实验，验证该情况下改进算法的正确性；（2）对簇相连的数据集进行聚类实验，验证该情况下改进算法对聚类质量的提升。

4.2.1 簇不相连的数据集聚类实验

实验使用的数据集A有1 600条记录，分为四类，大小和形状各不相同，并包含有噪声数据。

用改进算法对数据集A进行聚类，参数设置为ε＝0.47，Minpts＝5，δ＝0.17时，聚类结果如图1所示。图1中，不同的类用不同的灰度颜色表示，散乱的黑色点表示噪声，可以看出，数据集被标记为四个不同形状和大小的类，噪声数据被有效地识别，类的数目和形状都和数据集的先验知识相吻合，验证了在簇不相连的数据集下改进算法的正确性。

Figure 1 Clustering result1of dataset A by improved algorithm图1 改进算法对数据集A的聚类结果1

另外，实验过程发现，在参数取值为δ＝0.17，Minpts∈［5，9］，ε∈［0.47，0.50］时，聚类效果都很不错。图2显示的是参数设置为ε＝0.5，Minpts＝9，δ＝0.17时的聚类结果。可以看出，数据集被聚为四类，与图1中基本一致，表明在一定范围内，参数的变化对聚类的结果影响不大，说明改进算法在一定程度上降低了参数敏感性。

Figure 2 Clustering result2of dataset A by improved algorithm图2 改进算法对数据集A的聚类结果2

4.2.2 簇相连的数据集聚类实验

实验使用的数据集B有5 000条记录，分为四类，包含有噪声数据，且密度分布不均匀，左边部分密度最大，右边部分次之，然后是上边部分，下边部分密度最小，并且类之间紧密相连。

用DBSCAN算法对该数据集进行聚类，参数设置为ε＝0.15，Minpts＝9时，聚类结果如图3所示。从结果可以看出，数据集被聚为一个类，与先验知识不符，说明对于簇相连的数据集，DBSCAN算法不能达到很好的聚类效果。

Figure 3 Clustering result of dataset B by DBSCAN algorithm图3 DBSCAN算法对数据集B的聚类结果

用改进算法对该数据集进行聚类，参数设置为ε＝0.2，Minpts＝5，δ＝0.2时，聚类结果如图4所示。由结果可以看出，改进算法把数据集标记为四类，如实地反映了数据集的真实分布情况，很好地达到了预期效果，说明对于簇相连的数据集，改进算法能够把相连的簇区分开来，能提升该情况下聚类的质量。

Figure 4 Clustering result of dataset B by improved algorithm图4 改进算法对数据集B聚类结果

5 结束语

本文提出了累积平均密度的概念，并在此基础上提出了一种基于DBSCAN算法的改进算法。实验表明，改进算法具有以下特点：能够提升对簇相连数据集的聚类质量；弱化了密度阈值的作用，在一定程度上降低了参数敏感性；能够发现任意形状的聚类；能够有效地处理噪声数据；能够向高维扩展。

本文中的累积平均密度是用算术平均值来计算的，对簇合并的控制可能不够精细，未来考虑使用方根的算术平均值等其它方式来计算。另外，为了提高对高维大数据集的聚类效率，算法的并行实施和数据的存储结构设计也是下一步的研究方向。

［1］ Zhu Ming.Data mining［M］.Hefei：University of Science and Technology of China Press，2008.（in Chinese）

［2］ Ester M，Kriegel H P，Sander J.A density－based algorithm for discovering clusters in large spatial databases with noise［C］∥Proc of the 2nd International Conference on Knowledge Discovery and Data Mining，1996：226－231.

［3］ Feng Shao－rong，Xiao Wen－jun.A new method to improve the clustering quality of DBSCAN algorithm［J］.Journal of Xi’an Electronic and Science University：Natural Science Edition，2008，35（3）：523－529.（in Chinese）

［4］ Zhou Dong，Liu Peng.VDBSCAN：Variable density based clustering algorithm［J］.Computer engineering and Applications，2009，45（11）：137－141.（in Chinese）

［5］ Li Guang－qiang，Deng Min，Liu Qi－liang，et al.A spatial clustering method adaptive for local density changes［J］.Journal of Surveying and Mapping，2009，38（3）：255－263.（in Chinese）

［6］ Wu Jia－wei，Li Xiong－fei，Sun Tao，et al.A clustering algorithm based on neighborhood density balanced［J］.Journal of Computer Research and Development，2010，47（6）：1044－1052.（in Chinese）

［7］ Chu Yue－zhong，Xu Bo.Research on the optimization of clustering algorithm based on dynamic nearest neighbor［J］.Computer Engineering and Design，2011，32（5）：1687－1690.（in Chinese）

［8］ Li Shao－guang，Zhou Ju－suo，Xie Yu－bo，et al.An extended object oriented spatial density clustering algorithm［J］.Computer Engineering and Applications，2011，47（13）：166－168.（in Chinese）

［9］ Han Jia－wei，Kamber M.Data mining：Concepts and techniques［M］.Translated by Fan Ming，Meng Xiao－feng.Beijing：China Machine Press，2007.（in Chinese）

［10］ Hinneburg A，Keim D A.An efficient approach to clustering in large multimedia databases with noise［C］∥Proc of the 4th International Conference on Knowledge Discovery and Data mining，1998：58－65.

［11］ Liu Qing－bao，Deng Su，Zhang Wei－ming.Relative density based clustering algorithm［J］.Computer Science，2007，34（2）：192－195.（in Chinese）

［12］ Chen Zhi－ping，Wang Lei，Li Zhi－cheng.Research of clustering algorithm based on density gradient［J］.Computer Application，2006（10）：2389－2392.（in Chinese）

［13］ Qiu Bao－zhi，Xu Min.Research of non parameter clustering boundary detection algorithm［J］.Computer Engineering，2011，37（15）：23－26.（in Chinese）

附中文参考文献：

［1］ 朱明.数据挖掘［M］.合肥：中国科学技术大学出版社，2008.

［3］ 冯少荣，肖文俊.一种提高DBSCAN聚类算法质量的新方法［J］.西安电子科技大学学报：自然科学版，2008，35（3）：523－529.

［4］ 周董，刘鹏.VDBSCAN：变密度聚类算法［J］.计算机工程与应用，2009，45（11）：137－141.

［5］ 李光强，邓敏，刘启亮，等.一种适应局部密度变化的空间聚类方法［J］.测绘学报，2009，38（3）：255－263.

［6］ 武佳薇，李雄飞，孙涛，等.邻域平衡密度聚类算法［J］.计算机研究与发展，2010，47（6）：1044－1052.

［7］ 储岳中，徐波.动态最近邻聚类算法的优化研究［J］.计算机工程与设计，2011，32（5）：1687－1690.

［8］ 黎韶光，周巨锁，谢玉波，等.一种面向扩展空间对象的密度聚类算法［J］.计算机工程与应用，2011，47（13）：166－168.

［9］ 韩家炜，坎伯.数据挖掘概念与技术［M］.范明，孟小峰，译.北京：机械工业出版社，2007.

［11］ 刘青宝，邓苏，张维明.基于相对密度的聚类算法［J］.计算机科学，2007，34（2）：192－195.

［12］ 陈治平，王雷，李志成.基于密度梯度的聚类算法研究［J］.计算机应用，2006（10）：2389－2392.

［13］ 邱保志，许敏.无参数聚类边界检测算法的研究［J］.计算机工程，2011，37（15）：23－26.