ISSN 1000-1239 CN 11-1777/TP

计算机研究与发展 ›› 2019, Vol. 56 ›› Issue (5): 977-991.doi: 10.7544/issn1000-1239.2019.20170979

• 人工智能 • 上一篇    下一篇



  1. (哈尔滨理工大学计算机科学与技术学院 哈尔滨 150080) (
  • 出版日期: 2019-05-01
  • 基金资助: 

Uncertain Data Clustering Algorithm Based on Voronoi Diagram in Obstacle Space

Wan Jing, Cui Meiyu, He Yunbin, Li Song   

  1. (College of Computer Science and Technology, Harbin University of Science and Technology, Harbin 150080)
  • Online: 2019-05-01

摘要: 为了有效解决障碍空间中的不确定数据聚类的问题,引入计算几何中的Voronoi图对数据空间进行划分,提出障碍空间中基于Voronoi图的不确定数据聚类算法.根据Voronoi图的性质,提出4项聚类规则.利用KL距离进行相似性度量.根据障碍集合是否发生变化,提出了静态障碍环境下和动态障碍环境下的不确定数据聚类算法.理论研究和实验表明:静态障碍物环境中的不确定精炼聚类算法(简称STAO_RVUBSCAN算法)、障碍物动态增加情况下的不确定聚类算法(简称DYNOC_VUBSCAN算法)、障碍物动态减少情况下的不确定聚类算法(简称DYNOR_VUBSCAN算法)和障碍物动态移动情况下的不确定数据聚类算法(简称DYNOM_VUBSCAN算法)都具有较高的效率.

关键词: 静态障碍, 动态障碍, KL距离, 不确定数据, Voronoi图

Abstract: In order to solve the problem of the uncertain data clustering in obstacle space, the Voronoi diagram in computational geometry is introduced to divide the data space, and an uncertain data clustering algorithm based on Voronoi diagram in obstacle space is proposed. According to the properties of Voronoi diagram, four clustering rules are proposed. In order to consider the probability distribution between data, the KL distance is used as the similarity measure between data objects. Because obstacles can not always remain static in real life, and space obstacles often change dynamically. Then, according to whether the set of obstacles is changed, an uncertain data clustering algorithm in static obstacle environment and dynamic obstacle environment is proposed. Theoretical studies and experiments show that the uncertain refining clustering algorithm in the static obstacles environment(STAO_RVUBSCAN), the uncertain clustering algorithm of the dynamic increase of obstacles(DYNOC_VUBSCAN), the uncertain clustering algorithm of the dynamic reduction of obstacles(DYNOR_VUBSCAN) and the uncertain clustering algorithm of the dynamic movement of obstacles (DYNOM_VUBSCAN) have extremely high efficiency.

Key words: static obstacles, dynamic obstacles, Kullback-Leibler divergence, uncertain data, Voronoi diagram