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