文档介绍：一种基于网格密度的聚类算法
刘敏娟,于景茹,张西芝摘要:提出了一种基于网格密度的聚类算法(DGCA)。该算法主要利用网格技术去除数据集中的部分孤立点或噪声数据,对类的边缘节点使用一种边缘节点判断函数进行提取,最后利用相近值的方法进行聚axDf-D(i,j)(2)其中,MaxDf=Max1≤i,j≤nD(i, j)代表网格单元中节点间的最大相异值。
在传统的网格聚类算法中,将与高密度单元相邻的低密度单元中的节点作为孤立点或噪声数据丢弃,这样会丢失一些有用的边缘节点。为提高聚类的精度,在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 ,使用的操作系统是Windows XP Professional,算法是用VC++进行编程设计的。
(综合数据集)
实验中图1对