Title: A new clustering algorithm based on Voronoi diagram

Authors: Damodar Reddy; Prasanta K. Jana

Addresses: Department of Computer Science and Engineering, Indian School of Mines, Dhanbad 826 004, India ' Department of Computer Science and Engineering, Indian School of Mines, Dhanbad 826 004, India

Abstract: 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.

Keywords: cluster prototypes; clustering algorithms; Voronoi diagram; dynamic validity index; DVI; data mining; biological data; outliers.

DOI: 10.1504/IJDMMM.2014.059977

International Journal of Data Mining, Modelling and Management, 2014 Vol.6 No.1, pp.49 - 64

Published online: 02 Jul 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article