Abstract:

There is widespread uncertainty in the process of data collection, and there may be obstacles as barriers between uncertain data which are in reality geographical space. In order to solve the problem of clustering uncertain data in space with obstacles, we propose an approximate backbone guided Heuristic clustering algorithm for uncertain data with obstacles (APPGCUO), which includes three processes: using the Rtree node minmax method to propose the Rtree pruning techniquecure for uncertain data with obstacles (RPTOUCure), which is able to generate local optimal solution and improves its efficiency; then utilizing the theory of the approximate skeleton to present the  generate  initialization based on approximate backbone with obstacles (GIABO) which is in a position to generate the initial solution based on the local optimal solution, meanwhile can avoid the shortage of random initial solution of the partition clustering algorithm; finally combining the pruning features of the Voronoi diagram to present the Voronoi pruning techniqueKMediods (VPTKMediods) which can reduce the integral computation of uncertain data. Experimental results show that the APPGCUO algorithm has high clustering efficiency and quality.

Key words: uncertain data, clustering;obstacle;Rtree;Voronoi diagram