钱雪忠+韩利钊+罗靖

摘要：现有大多数多密度聚类算法存在参数依赖性较高、精确度较低的问题。提出一种基于网格相对密度差的扩展聚类算法（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）等。

基于网格的聚类算法将数据空间划分成有限个单元网格，所有处理都在网格单元上进行。这种方法的优点是聚类结果与数据点的输入顺序无关，算法复杂度仅依赖于空间网格的数量（远小于数据点总数），具有较高的运算效率，且能识别任意形状的簇。……