基于动态的网格相对密度差聚类算法研究

钱雪忠+韩利钊+罗靖

摘要：现有大多数多密度聚类算法存在参数依赖性较高、精确度较低的问题。提出一种基于网格相对密度差的扩展聚类算法（ECRGDD）的改进算法，即基于动态的网格相对密度差聚类算法（CDGRDD）。CDGRDD针对ECRGDD对于中心密度大、边缘密度稀疏的类聚类效果差的问题，把初始单元网格密度定义为动态，在密度相似相邻的网格合并时加入一个距离判断条件，由此减少盲目合并的可能性。实验表明，CDGRDD能有效对多密度、任意形状的数据进行聚类。

关键词：动态初始单元；多密度聚类；网格相对密度差；模糊函数

DOIDOI：10.11907/rjdk.171164

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2017）006-0032-05

0 引言

聚类分析是数据挖掘的重要研究内容之一。聚类是把数据分成类或簇的过程，使同一类中的数据尽量相似，不同类之间的数据尽量相异[1]。传统聚类算法大致分为划分方法、层次方法、基于密度的方法、基于网格的方法、基于模型的方法，在这5类方法中，学者对基于密度和基于网格的聚类算法进行了大量研究，两者各有优点与不足[2-6]。

目前已有很多经典聚类算法，如K-MEANS、CLARANS、DBSCAN、CURE、CLIQUE和SNN等算法[7-11]，以及在这些经典算法基础上改进的算法，如周水庚等[12]提出的基于密度的快速聚类算法 （FDBSCAN）、黄红伟等[13]提出的基于网格相对密度差的扩展聚类算法 （ECRGDD）、冯振华[14]针对多密度提出的贪婪聚类算法 （GDBSCAN）等。

基于网格的聚类算法将数据空间划分成有限个单元网格，所有处理都在网格单元上进行。这种方法的优点是聚类结果与数据点的输入顺序无关，算法复杂度仅依赖于空间网格的数量（远小于数据点总数），具有较高的运算效率，且能识别任意形状的簇。但是，现有的基于网格的聚类算法，通常只有在数据集分布较为均匀的情况下才能得到较好的聚类效果，对于多密度数据集并不能达到令人满意的聚类结果。

1 扩展聚类算法

1.1 算法简介

针对基于网格的聚类算法对于多密度数据集聚类效果不理想的问题，黄红伟等提出了基于网格相对密度差的扩展聚类算法（ECRGDD），该算法结合基于密度和基于网格思想的优点，采用数据空间网格化方法节省运算时间，根据网格间的密度关系展开聚类，并给出边界提取方法，以便提高聚类质量。

ECRGDD算法思想简单表述为：首先根据统计的网格密度选取密度最大值g0作为初始单元；然后按照广度优先遍历原则，采用相对密度差公式，逐层计算初始单元g0与其相邻网格之间的相对密度差。若两者密度相近，则将相邻网格单元与初始单元归为一类，继续向外扩展，直到当前聚类的网格密度与初始单元网格密度相差较大，不满足相对密度差公式时聚类结束；然后在剩余未被聚类的网格单元里找到密度最大者，重复上述步骤，直到剩下的数据点集不能再聚类时为止。

1.2 ECRGDD算法存在的问题

由于ECRGDD算法初始单元网格g0一直是本类中密度最大的网格，所以对于中心密、边缘稀疏的类，如果相对密度差参数设置较小，类边缘的网格就不满足密度差公式。把这种类分成多个类，如果相对密度差参数设置比较大，噪声点就会吸收到本类中；另一方面，ECRGDD算法只要满足相对密度差公式就合并网格，合并存在盲目性。如果两个类距离较近，不同类中的两个网格正好是相邻网格，密度又相近，这两个类就会合并成一个类。如图1所示，网格g1与网格g2是相邻网格，且密度相近；g3与g4相邻且密度相似，图中的3个类就合并成一个类。

3.2 实验结果及分析

本文通过Matlab工具实现CDGRDD算法并处理实验结果，试验环境：CPU为Intel i3 3.7GHz；内存为4G；OS为Windows7。通过3个不同类型和规模的多密度数据分别与ECRGDD算法、DBSCAN算法、GDBSCAN算法进行比较。

说明：所有实验结果中的‘×为噪声点。

实验1：数据Jain[16]是图形比较规则，密度有较大差异的两个类，共有408个数据对象，CDGRDD和ECRGDD中的两个参数分别为з=0.53，uλ=0.1；DBSCAN算法中的两个参数分别为Eps=2.5，Minpts=10；GDBSCAN算法中Mintps=10；聚類结果如图3所示。

由上述实验结果可知，ECRGDD聚类算法由于采用固定的初始单元密度，使得左上部分与右上部分分离，且聚类不精确；DBSCAN算法由于采用全局变量Eps、Mintps，对于多密度聚类，容易顾此失彼，密度高的聚类效果好，密度低的聚类效果差；GDBSCAN聚类算法整体聚类效果较好，但仔细观察，此算法对个别数据存在瑕疵点；CDGRDD聚类成功识别了两个不同密度的簇，且噪声点识别较为准确。

实验2：数据Compound[16]图形比较复杂且具有多个类，共有418个数据对象，CDGRDD和ECRGDD中的两个参数分别为з=0.55，uλ=0.1；DBSCAN算法中的两个参数分别为Eps=1.5，Minpts=10；GDBSCAN算法中Mintps=5。聚类结果如图4所示。

从图4（a）可以看出，ECRGDD聚类算法在一个簇结束之前，都用固定的初始网格单元，使得公式（2）中的den（g0）是固定的，因此对于左上角这种中心密边缘稀疏聚类效果不理想，噪声偏多；另一方面在聚类过程中网格的合并没有距离限制，使得左下角环形类中的一些网格是环形中心网格的相邻网格且满足密度差公式，所以被合并成了一个类，边界点处理不理想；GDBSCAN算法出于数据输入顺序的原因，使得左上角两个分类模糊，且分类个数不正确；CDGRDD算法成功识别了不同形状、不同密度的5个簇，噪声点检测十分准确。

实验3：数据Sizes5[17]高密度簇与低密度簇相邻，有临界点干扰情况且中心边缘稀疏更为明显，数据量也相对较大，共有1026个数据对象，CDGRDD和ECRGDD中的两个参数分别为з=0.53，uλ=0.1；DBSCAN算法中的两个参数分别为Eps=1，Minpts=5；GDBSCAN算法中Mintps=9。聚类结果如图4所示。

ECRGDD聚类算法由于采用固定的初始单元密度，使得类边缘的数据满足不了公式（2），右上角的类被分成多个类。从图4（b）中可以看出，虽然DBSCAN可以识别任意形状的簇，但对于多密度聚类效果并不理想，密度大的类，吸收了较多的噪声点，密度低的类丢失了较多的本该属于本类的数据，且靠近密度大的稀疏类容易被吸收到密度大的类中；图4（c）中显示出GDBSCAN算法对中心密边缘稀疏的类聚类效果也不理想，且存在瑕疵点（明显属于该类，却被当成噪声点）；CDGRDD算法准确识别出了4个相邻、密度不同的类，且吸收了少量的噪声点到簇中。

下面对实验结果进行定量分析，DS1、DS2实验结果见表1、表2。

由于DS3的边界点无确定分类，第3组实验采用有10 000个数据的DS4[18]，DS4图形如图6所示，实验结果见表3。

由以上实验可以看出，在处理多密度数据中，本文提出的CDGRDD聚类效果优于其它算法。对于密度相对均匀的DS4，其它聚类算法效果也不错。

4 结语

实验证明，本文提出的CDGRDD聚类算法，针对中心边缘稀疏的数据，利用动态的网格单元密度den（g0）计算相对密度差，对网格合并加入距离限制，在不增加时间复杂度的基础上有效提高了算法对各种数据的适应性和准确性，对于不规则的多密度数据集有较为准确的聚类效果。但当维数d增加时，划分的网格数将以指数级增长，因此下一步的研究重点是如何减少网格数量的处理。

参考文献：

[1]JACOB M，HELLSTRM T.Policy understanding of science，public

trust and the BSE-CJD crisis[J].Journal of Hazardous Materials，2000，78（1）：303-317.

[2]HUANG J，ZHANG J.Fuzzy C-means clustering algorithm with spatial constraints for distributed WSN data stream[EB/OL].http：//med.wanfangdata.com.cn/Paper/Detail？id=PeriodicalPaper_JJ025372934 2011.

[3]GUHA S，RASTOGI R，SHIM K.Cure： an efficient clustering algorithm for large databases[J].Information Systems，1998，26（1）：35-58.

[4]ESTER M，KRIEGEL H P，SANDER J，et al.A density-based algorithm for discovering clusters in large spatial databases with noise[J].Kdd，1996，96（34）： 226-231.

[5]AGRAWAL R，GEHRKE J，GUNOPULOS D，et al.Automatic subspace clustering of high dimensional data for data mining applications[M].ACM，1998.

[6]YOUSRI N A，KAMEL M S，ISMAIL M A.A distance-relatedness dynamic model for clustering high dimensional data of arbitrary shapes and densities[J].Pattern Recognition，2009，42（7）： 1193-1209.

[7]WU J，LIU H，XIONG H，et al.A theoretic framework of K-means-based consensus clustering[C].IJCAI，2013.

[8]何童.不確定性目标的CLARANS聚类算法[J].计算机工程，2012，38（11）：56-58.

[9]HU BO-LEI，TAN JIAN-HAO.Clustering algorithm based on cumulative average density[J].Computer Engineering & Science，2013，35（1）：155-159.

[10]XU HONG-BO，HAO ZHONG-XIAO.Grid-partition Clustering Algorithm Based on Hilbert Curve[J].Journal of Chinese Computer Systems，2010，31（10）：1979-1983.

[11]ERTOZ L，STEINBACH M，KUMAR V.A new shared nearest neighbor clustering algorithm and its applications[C].Workshop on Clustering High Dimensional Data and its Applications at 2nd SIAM International Conference on Data Mining.2002： 105-115.

[12]周水庚，周傲英，曹晶，等.一种基于密度的快速聚类算法[J].计算机研究与发展，2000，37（11）：1287-1292.

[13]黄红伟，黄天民.基于网格相对密度差的扩展聚类算法[J].计算机应用研究，2014，31（6）：1702-1705.

[14]冯振华，钱雪忠，赵娜娜.Greedy DBSCAN：一种针对多密度聚类的DBSCAN改进算法[J].计算机应用研究，2016，33（9）：1522-1529.

[15]PIEGL L A，TILLER W.Algorithm for finding all k，nearest neighbors[J].Computer-Aided Design，2002，34（2）：167-172.

[16]Clustering datasets[EB/OL].http：//cs.joensuu.fi/sipu/datasets/.

[17]Read pudn[EB/OL].http：//www.pudn.com/downloads219/sou rcecode/math/detail1 030717.html.

[18]KHALID S，RAZZAQ S.TOBAE：a density-based agglomerative clustering algorithm[J].Journal of Classification，2015，32（2）：241-267.

（责任编辑：杜能钢）