A new clustering algorithm based on Voronoi diagram

Clustering is a widely used data mining tool that has been paid enormous attention by the research community. We introduce here a new clustering algorithm which is based on Voronoi diagram. The biggest advantage of using Voronoi diagram is that it provides a natural means of partitioning space into sub-regions and therefore facilitates data clustering. In our approach, we exploit largest empty Voronoi circles to locate closer points represented by the Voronoi vertices referred as cluster prototypes. The points represented by these prototypes are then efficiently amalgamated by constructing new Voronoi diagram iteratively to produce the desired clusters. We perform excessive experiments on the synthetic as well as biological data, namely iris, wine, statlog heart, breast tissue, pima-Indians-diabetes, cloud, blood transfusion and yeast. The experimental results are compared with some standard clustering techniques. It is shown that the proposed algorithm performs better in discovering the complex clusters and able to detect the outliers.