Optimized Number of Reverse Neighbor Clustering Algorithm by Voronoi Diagram in Obstacle Space

Abstract

In order to solve the problem that the existing obstacle space clustering algorithm needs to select the clustering center and set the threshold value manually, OBRK-means (obstacle based on nearest K-means) clus-tering algorithm based on Voronoi diagram is proposed. The algorithm is discussed and analyzed from three aspects: the selection of cluster center, the selection of outliers and the generalized coverage circle. Firstly, Voronoi diagram is introduced to calculate the reverse nearest neighbor number to determine the cluster center. Secondly, Voronoi diagram and density of sample points are used to screen and prune outliers in the dataset. Finally, the generalized covering circle is introduced to carry out the initial clustering, and the inner and outer boundary points are proposed to solve the problem that the initial clustering results are not accurate. The exclusion points and expansion points are calculated respectively from the inner and outer boundary points to improve the accuracy of clustering. Theoretical research and experimental results show that the algorithm has higher efficiency in processing data in obstacle space and gets better clustering results.

Keywords

• |clustering|voronoi diagram|obstacle space|number of reverse neighbor