一种基于网格密度的聚类算法

摘要：提出了一种基于网格密度的聚类算法（DGCA）。该算法主要利用网格技术去除数据集中的部分孤立点或噪声数据，对类的边缘节点使用一种边缘节点判断函数进行提取，最后利用相近值的方法进行聚类。实验表明，DGCA算法能够很好地识别出孤立点或噪声，聚类结果可以达到一个较高的精度。

关键词：网格聚类；边界点；网格密度

中图分类号：TP312文献标识码：A文章编号：1672-7800（2012）012-0056-02

0引言

聚类是把一组数据按照相似性归成若干类别，它的目的是使得属于同一类别的个体之间的距离尽可能地小而不同类别上的个体间的距离尽可能地大。聚类的结果可以得到一组数据对象的集合，称其为簇或类。簇中的对象彼此相似，而与其它簇中的对象相异。迄今为止，已经提出了许多聚类算法，大体上这些算法可以分为基于距离的方法、基于层次的方法、基于密度的方法、基于网格的方法和基于模型的方法等。

基于网格的聚类算法首先将d维数据空间的每一维平均分割成等长的区间段， 即把数据空间分割成一些网格单元。若一个网格单元中所含数据量大于给定的值，则将其定为高密度单元；否则将其视为低密度单元。如果一个低密度网格单元的相邻单元都是低密度的，则视这个低密度单元中的节点为孤立点或噪声节点。网格聚类就是这些相邻的高密度单元相连的最大集合。

1基本概念

1.1相近值

网格单元内节点之间的相近值是利用节点间的距离来计算的。节点间的相近值越大，它们就越相似。即对这些网格单元内的节点进行聚类时，它们属于同一个类的可能性就越大。

定义1节点集：设P=（U，K），我们用P表示n条记录的集合。

U={U1，U2，…，Un}代表网格单元内的节点集

K={K1，K2，…，Kr}代表网格单元内节点的属性

其中，i，i∈（1，2，…，n），kim，m∈（1，2，…，r）代表节点Ui的第m个属性Km，因此，用Km代表一个r维的向量（ki1，ki2，…，kir），i∈（1，2，…，n）。

定义 2 相异值：任意两个节点Ui与Uj之间的相异值定义如下：D（i，j）=∑rm=1|kim-kjm|，i， j=1，2，…，n（1）定义 3 相近值：任意两个节点Ui与Uj之间的相近值定义如下：S（i，j）=MaxDf-D（i，j）（2）其中，MaxDf=Max1≤i，j≤nD（i， j）代表网格单元中节点间的最大相异值。

1.2边缘节点判断函数

在传统的网格聚类算法中，将与高密度单元相邻的低密度单元中的节点作为孤立点或噪声数据丢弃，这样会丢失一些有用的边缘节点。为提高聚类的精度，在DGCA算法中引入边缘节点判断函数Minf（i），其定义如下：Minf（i）=（MaxSim1≤j≤n（i，j）+aveSim（i））/2（3）其中，MaxSim1≤j≤n（i，j）=max{j︱S（i，j），1≤j≤n}，aveSim（i）=1n∑nj=1S（i，j）

边缘节点函数Borderf（i），其定义如下：Borderf（i）=1hd∑hdi=1S（i，l）（4）其中，hd表示高密度单元中节点的个数。

边缘节点处理的方法是：如果一个高密度网格单元的相邻网格单元中有低密度单元，就使用边缘节点函数Borderf（i）检查这些低密度单元中的节点i，如果Borderf（i）的值大于等于设定的边缘节点判断函数值Minf（i），那么判定节点i是此高密度单元的边界点，即i与此高密度单元中的节点属于一类。这样就可以将有用的边缘节点提取出来，从而提高聚类的质量。

2DGCA聚类算法

DGCA聚类算法的基本思想：①将所有节点集U映射到数据空间相应的网格单元中；②根据用户输入的密度测试值MinPts判断每个网格单元是低密度还是高密度网格单元，如果是高密度网格单元，则对其相邻的低密度网格单元中的节点，利用Minf（i）判断各个节点是否为该高密度网格的边缘节点，如果是即提取边缘节点，如果不是就把该节点认为是孤立点或噪声数据；③根据用户输入的相近测试值MinSim，对去除孤立点或噪声数据后的节点，使用相近值方法进行聚类，即如果任意两个节点的相近值S（i， j）大于或等于给定的测试值MinSim，就把这两个数据对象视为同一个类中的数据。

DGCA算法如下：

输入：Z，MinPts，MinSim

输出：类，孤立点或噪声数据

步骤1：根据用户输入的Z值将整个数据空间X划分成Zr个网格单元。

步骤2：将节点集U映射到网格单元中。

步骤3：逐一扫描每个网格单元，并记录每个网格单元中的节点个数cell[q].count（1≤q≤Zr）。

步骤4：根据密度阈值将网格单元分为高密度单元和低密度单元。

步骤5：考虑每个高密度单元，如果其相邻网格单元有低密度的，利用边缘节点判断函数提取有用的边缘节点，低密度单元中剩余的节点作为孤立点或噪声数据丢弃。

步骤6：考虑高密度单元中的任意两个节点，如果其相似值大于给定的MinSim值，则将这两个对象归于一类。

3实验结果与分析

本实验所使用的PC具有1G内存，奔腾ⅣCPU 2.40GHz，使用的操作系统是Windows XP Professional，算法是用VC++进行编程设计的。

3.1精度对比（综合数据集）

实验中图1对应的节点数据集是来自于参考文献，此节点集含有5 034条记录，从该图中可以直观地看到，此节点集应该被分为5类。实验结果显示，算法DGCA的结果是5个类，由于使用了边缘节点判断函数，孤立点或噪声被有效地识别出来，使得DGCA算法的精度明显好于传统的网格聚类算法CLIQUE，DGCA算法中的参数：Z=100，MinPts=10，MinSim=198。

3.2时间对比

由于DGCA算法的时间复杂度是O（n2），所以该算法的时间效率还有待改进。

4结语

本文提出了一种基于网格密度的聚类算法（DGCA）。该算法主要利用网格技术去除节点数据集中的部分孤立点或噪声节点，对类的边缘节点使用一种边缘节点判断函数进行提取，最后利用相近值的方法进行聚类。实验表明，DGCA算法与传统的聚类方法相比，聚类的精度有了很大的提高。它不仅适用于综合节点数据集，而且对高维节点数据集也能够得到令人满意的聚类结果和聚类质量。

参考文献：

[1]罗静，刘宗歧.基于网格聚类算法的电力营销预测研究[J].科技信息，2012（3）.

[2]邱保志，沈钧毅.基于扩展和网格的多密度聚类算法[J].控制与决策，2006（9）.

[3]张鸿雁，刘希玉.一种网格聚类的边缘检测算法[J].控制与决策，2011（12）.

[4]邱保志，沈钧毅.网格聚类中的边界处理技术[J].模式识别与人工智能，2006（2）.

[5]LEVENT ERTOZ，MICHAEL STEINBACH，VIPIN KUMAR.Finding clusters of different sizes，shapes，and densities in noisy，high dimensional data[C].In SIAM International Conference on Data Mining，2003.