高级检索
    万静, 崔美玉, 何云斌, 李松. 障碍空间中基于Voronoi图的不确定数据聚类算法[J]. 计算机研究与发展, 2019, 56(5): 977-991. DOI: 10.7544/issn1000-1239.2019.20170979
    引用本文: 万静, 崔美玉, 何云斌, 李松. 障碍空间中基于Voronoi图的不确定数据聚类算法[J]. 计算机研究与发展, 2019, 56(5): 977-991. DOI: 10.7544/issn1000-1239.2019.20170979
    Wan Jing, Cui Meiyu, He Yunbin, Li Song. Uncertain Data Clustering Algorithm Based on Voronoi Diagram in Obstacle Space[J]. Journal of Computer Research and Development, 2019, 56(5): 977-991. DOI: 10.7544/issn1000-1239.2019.20170979
    Citation: Wan Jing, Cui Meiyu, He Yunbin, Li Song. Uncertain Data Clustering Algorithm Based on Voronoi Diagram in Obstacle Space[J]. Journal of Computer Research and Development, 2019, 56(5): 977-991. DOI: 10.7544/issn1000-1239.2019.20170979

    障碍空间中基于Voronoi图的不确定数据聚类算法

    Uncertain Data Clustering Algorithm Based on Voronoi Diagram in Obstacle Space

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

       

      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.

       

    /

    返回文章
    返回