Improved K-means Clustering Algorithm for Biological Data using Voronoi Diagram#

Abstract

As a simple clustering method K-means is known as an algorithm of choice for many clustering challenges due to its performance of clustering large data sets. However, it has two major drawbacks, the random selection of initial cluster centers and the pre estimation of ‘K’ value in advance. Here, we propose a method that overcomes these problems with the help of Voronoi diagram. To resolve the random selection of initial cluster centers, we use Voronoi diagram. The vertices in the Voronoi diagram are located first and then merged iteratively to converge to ‘k’ number of points which can be treated as initial cluster centers for K-means. The second problem of inputting ‘K’ value in advance is enhanced by taking a limit on the radius of Voronoi circle. The experimental results carried out on various synthetic and biological data sets are proved the efficiency of the proposed method..