现有的基于网格聚类算法在付出较小的时间复杂度的同时,牺牲了聚类的质量,得到的往往并不是最理想的聚类结果,尤其是在簇边缘可能出现数据点聚类不准现象。本文提出了一种将网格化空间中位于簇边缘的网格进行精度进一步细化处理的算法,将这些边缘网格中的这些不确定的点重新

一个好的聚类算法应该满足如下的条件：（1）好的时间效率、（2）处理任意形状的簇、

（3）区分噪声、（4）与数据点的顺序无关、（5）对用户输入参数的依赖最小[13]。目前来看，主流的基于密度的方法和基于网格的方法很难在质量和时间上取得很好的平衡，而且都需要设置若干个参数。在没有先验知识的情况下，人为地确定这些参数是十分困难的[11]，不同的参数设置可能导致差距较大的聚类结果；同时由于在部分数据集上产生的聚类结果可能不能直观地被评估，根据聚类结果调整需要输入的参数也是不现实的。所以，应该尽量降低聚类算法对输入参数的依赖，自动参数的选取是十分必要和有意义的。在SIGDD2001上，

Rakash和Agrawal等人就将算法参数的自动选取列为当前数据挖掘研究的一项重要课题[12]。

本文提出了一种基于网格和密度的簇边缘精度增强聚类算法（GDCAP, Grid and Density based Clustering Algorithm with Pricise cluster boundaries）。GDCAP首先将数据空间划分为若干个互不相交的网格单元，以网格单元的计算代替数据点的计算。一般来说网格单元的数量是远远小于数据点数量的，从而将处理规模大大减小。根据数据点在网格单元中的密度信息，利用全局网格密度差最大化方法对网格单元做出最优二划分，从而获得簇的骨架。然后将剩余非空网格中的数据点按照聚类隶属度函数值进行下一步聚类过程。最后得到的是由簇骨架和簇边缘皮肤所构成的簇结果，并且将噪音标记出来。GDCAP算法继承了在大数据集上网格化算法的高效性，同时利用了数据集的密度等信息，在必要的时候还原这些数据点所具有的信息，克服了单纯网格划分后可能出现的簇边缘划分不准的情况，提高了聚类结果的质量。

本文首先提出了相关定义并对GDCAP的算法框架进行了描述，然后分析了算法的时间度。最后利用实验结果证明了算法的有效性。

2 基于网格的簇边缘平滑聚类算法

2.1 相关定义

定义1：设P={p1,p2,...,pn}是一个数据集，其中数据点pi∈P是数据集P中的数据点。聚类就是将数据集P划分为子集C={C1,C2,...,Ck}，使得对于 i,j∈{1,2,...,k},∪Ci=P,Ci∩Cj= 的过程。这时，Ci∈P就是数据集P的一个簇。

i=1k

定义2：S=A1×A2×...×Ad为一个定义在d维上的数据空间，其中属性Ai∈A为数据空间S上的一个属性，且对于维度Ai来说，[Aimin,Aimax]为其取值范围。根据网格分辨率

参数γ，将数据空间划分为若干互不相交的超方体，即网格单元。

n

这样，数据空间S上的网格数目为：m=

理。 ∏(Ai=1imax Aimin)，计算过程中经过上取整处γd

定义3：网格密度den(ci)，为网格ci中所包含的数据点数。随着数聚集的维度的增大，网格数目也随d呈指数增长。为了提高时空性能，仅存储那些den(ci)>0的网格单元。那么，簇可定义为满足核心网格约束条件的网格与周边满足内聚函数最大值的数据点的最大集合。