障碍空间中不确定数据聚类算法*
曹科研+，王国仁，韩东红，袁野，胡雅超，齐宝雷
东北大学信息科学与工程学院，沈阳110819
Clustering Algorithm of Uncertain Data in Obstacle Space
CAO Keyan +,WANG Guoren,HAN Donghong,YUAN Ye,HU Yachao,QI Baolei
College of Information Science and Engineering,Northeastern University,Shenyang 110819,China
+Corresponding author:E-mail:caokeyan@https://www.doczj.com/doc/9f13062803.html,
CAO Keyan,WANG Guoren,HAN Donghong,et al.Clustering algorithm of uncertain data in obstacle space.Journal of Frontiers of Computer Science and Technology,2012,6(12)：1087-1097.
Abstract:In recent years,uncertain data is generated widely in location data due to the inaccuracy of measurement instruction or the data attributes itself.The existence of obstacles in space brings the new challenges to spatial uncertain data clustering.This paper proposes OBS-U K -means (obstacle uncertain K -means)algorithm to cluster uncertain data in obstacle space,and also proposes two pruning strategies based on R-tree and V oronoi diagram and the shortest distance area concept,that greatly reduces the calculations.Finally,the experiment demonstrates that the efficiency and accuracy of the OBS-U K -means algorithm,and the pruning approach can improve the efficiency of the clustering algorithm,meanwhile,it doesn ’t damage the cluster effectiveness.
Key words:clustering;uncertain data;obstacle space
摘要：近些年，由于数据采集的不精确和数据本身的不确定性，使不确定性在位置数据中普通存在。在障碍空间中，聚类不确定数据面临新的挑战。提出了障碍空间中聚类不确定数据的OBS-U K -means （obstacle uncertain K -means ）算法，并提出了分别基于R 树和V oronoi 图的两种剪枝策略和最近距离区域的概念，大大减少了计算量。通过实验验证了OBS-U K -means 算法的高效性和准确性，同时证明了剪枝策略在不损害聚类有效性的情况下，能够有效地提高聚类效率。
关键词：聚类；不确定数据；障碍空间
文献标识码：A 中图分类号：TP311
*The National Natural Science Foundation of China under Grant Nos.61025007,60933001,61100024,61173029(国家自然科学基金);the Fundamental Research Funds for the Central Universities of China under Grant No.N110404011(中央高校基本科研业务费专项资金).Received 2012-04,Accepted 2012-06.ISSN 1673-9418CODEN JKYTA8
Journal of Frontiers of Computer Science and Technology 1673-9418/2012/06(12)-1087-11DOI:10.3778/j.issn.1673-9418.2012.12.003E-mail:fcst@https://www.doczj.com/doc/9f13062803.html, https://www.doczj.com/doc/9f13062803.html, Tel:
+86-10-51616056