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

A clustering algorithm of uncertain data with obstacles based on Voronoi diagram

数据采集过程中普遍存在不确定性,并且在现实地理空间中,不确定数据之间可能存在障碍物间隔。为解决障碍空间中不确定数据的聚类问题,提出APPGCUO算法,该算法包括三个过程:在障碍物约束下采用R树节点最小最大值方法提出的RPT-OUCure算法,用以生成局部最优解,提高生成局部最优解的效率;继而利用近似骨架的理论提出GIABO算法,以局部最优解生成有效初始解,避免划分聚类算法中任意初始解的不足;最后结合Voronoi图的特性提出VPT-KMediods算法,减少不确定数据的积分运算量。实验结果表明,APPGCUO算法具有较高的聚类效率和质量。

There is widespread uncertainty in the process of data collection, and there may be obsta- cles 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 rain-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 im- proves its efficiency; then utilizing the theory of the approximate skeleton to present the generate initial- ization based on approximate backbone with obstacles （GIABO） which is in a position to generate the in- itial solution based on the local optimal solution, meanwhile can avoid the shortage of random initial so- lution of the partition clustering algorithm~ finally combining the pruning features of the Voronoi dia- gram to present the Voronoi pruning technique-KMediods （VPT-KMediods） which can reduce the inte- gral computation of uncertain data. Experimental results show that the APPGCUO algorithm has high clustering efficiency and quality.