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

5.4.3.1　相关定义

（1）设S＝｛a1，a2，…，an｝是一个数据集，聚类就是将数据集S划分为子集C｛C1，C2，…，Cm｝，使得对于

的过程。这时，Ci⊂S就是数据集S的一个簇。

（2）S＝A1×A2×…×Ap为一个定义在p维上的数据空间，其中属性Ak∈A为数据空间S上的一个属性，且对于属性Ak来说，［Akmin，Akmax］为其取值范围，将属性Ak的取值区间分为Pk个子区间，每个子区间按取值从小到大排序，并赋予一个序号，即1，2，…，Pk。根据网格分辨率参数γ，将数据空间划分为若干互不相交的超方体，即网格单元。

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

计算过程中经过上取整处理。

（3）网格密度den（Ci），为网格Ci中所包含的数据点数。

随着数聚集的维度的增大，网格数目也随p呈指数增长。为了提高时空性能，仅存储那些den（Ci）＞0的网格单元。那么，簇可定义为满足核心网格约束条件的网格与周边满足内聚函数最大值的数据点的集合。

（4）两个网格Ci，Cj是相邻的，仅当如下表达成立时：

其中，分别为网格Ci第k和k′属性的取值序号。

（5）将所有网格划分高密度的网格和低密度的网格，区分的基准称为密度阈值，记为DT。

（6）网格密度大于DT的网格，叫作稠密网格。

（7）网格密度小于DT并且不为0的网格，即网格的属性目前还不确定的网格，叫作待定网格。

5.4.3.2　密度阈值DT的选取方法

计算网格密度期望

并记为mean＿nop。这里nop（celli）为有效（非空）网格celli的密度。从mean＿nop开始，计算前面部分与后面部分的差，即

并记录diff的最大值。之所以从均值开始比较而不是从一开始比较，是因为大于密度均值的网格一定是高密度网格，并且一个数据集中，形成聚类的数据数目往往占据大多数。因而，从均值开始扫描可以节省部分计算量。这样，后到的使diff的最大值所对应的nopl即为所求之DT。这样做的好处是：避免在实际操作中用户对数据集的不甚了解而在参数选择上产生偏差。参数选择过大，聚类的纯度降低；参数选择过小，导致大量孤立簇碎片。

5.4.3.3　“待定网格”中的数据点的处理

网格方法对数据集有很好的扩展性。不过，用对网格的计算取代了对点的计算，在换取速度的同时丢失了大部分点的信息，导致聚类质量有所下降。如图5.7所示，图5.6中A2和C2的数据点很可能被当作噪声来处理，而图5.7中两个簇的边缘网格B2的存在很可能误将两个簇当作一个簇来看待。

图5.6　边缘聚类不准现象（a）

通过实验发现，待定网格中的数据点往往是高密度区域与低密度区域的分界处，也可能是两个或多个靠得很近的簇的分界处，图5.7显示了正是这些区域往往容易出现数据点分配不准的现象。这些待定网格中的点究竟是划分到哪一个簇中，使用距离来度量隶属度。若该点在网格中处于靠近核心网格的一侧，则将它划分到核心网格隶属的簇中；反之，将之看作噪声处理。

算法步骤：(www.daowen.com)

算法：GDCAP。

输入：数据集DS。

输出：带有集群标签的数据对象。

（1）用输入的间隔并对数据空间进行网格划分。

图5.7　边缘聚类不准现象（b）

（2）For each对象pi。

（3）将对象pi映射到网格空间中。

（4）删除空白网格。

（5）计算所有有效网格的平均密度，即网格密度均值。

（6）计算密度阈值TD。

（7）For each有效的网格celli。

（8）If网格celli密度大于DT。

（9）标记该单元格为稠密网格CC。

（10）Else。

（11）标记该单元格为待定网格SC。

（12）将所有的稠密网格CC合并成集群如果，它们是相邻的。

（13）For each SCi。

（14）If SCi不与稠密网格CC邻居。

（15）标记SCi作为噪声网格。

（16）Else。

（17）For each对象pi存在待定网格SCi中。

（18）计算对象pi和它的邻居网格之间的距离，标记最近的稠密网格CC。

（19）if最近的网格是稠密网格CC。

（20）标记对象pi为邻近稠密网格集群。

（21）Else标记对象pi为噪音。

（22）打印集群结果。

（23）End