基于网格密度方向的聚类簇边缘精度加强算法  

An Enhancement Algorithm of Cluster Boundaries Precision Based on Grid's Density Direction

作　　者：余灿玲[1] 王丽珍[1] 张元武[1] 

机构地区：[1]云南大学信息学院计算机科学与工程系,昆明650091

出　　处：《计算机研究与发展》2010年第5期815-823,共9页Journal of Computer Research and Development

基　　金：国家自然科学基金项目(60463004)~~

摘　　要：现有的基于网格聚类算法在获得较高效率的同时,却是以牺牲聚类的质量为代价的,特别是在簇与簇相互邻近的情况下,因为簇边缘聚类的不准确这种现象尤为突出.为解决此类问题,提出了一种基于网格密度方向的聚类预处理方法,该方法的思想来源于牛顿的万有引力普遍规律,即物体之间的距离越小质量越大,则吸引力越大,簇内的密度比簇边缘的密度大,即吸引力大,故如果一个网格单元密度同时出现反方向递增时,即挤压的情况,则需要对该单元进行进一步的细分处理,判断该单元是不是簇的边缘单元,并准确地判断边缘单元中对象的挤压方向.实验显示该算法可以有效地加强聚类簇边缘的精度,具有较高的簇识别率,因此,作为聚类的预处理算法是理想的.The grid-based clustering approach uses a multi-resolution grid data structure.It quantizes the object space into a finite number of cells that form a grid structure on which all of the operations for clustering are performed.Existing grid-based clustering algorithms are efficient,but the clustering quality is not very good,especially when dealing with the objects in fringes,the clustering results are not accurate.In order to resolve such problems,a preprocess algorithm based on grid density direction is proposed in this paper.The method is derived from Newton＇s universal law of gravitation,that is,the smaller the distance between objects,the larger their quality,the more attractive.Similarly,the density inside a cluster is larger than its boundary.That is to say that there is larger gravitation inside a cluster.Therefore,if a grid＇s density increases at the opposite directions synchronously（that is the case of the extrusion）,the grid need to be further refined,which is to determine whether the grid is the edge of cluster grids,and determine the extrusion directions of the objects in the edge of cluster grids.The experimental results show that the new method can enhance cluster boundaries precision effectively and has a higher cluster recognition rate,so it is very useful as a preprocess algorithm of a clustering.

关 键 词：网格密度方向 挤压 反方向 主方向 主单元 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]