BH-centroids: A New Efficient Clustering Algorithm

Abstract

The k-means algorithm is one of most widely used method for discovering clusters in data; however one of the main disadvantages to k-means is the fact that you must specify the number of clusters as an input to the algorithm. In this paper we present an improved algorithm for discovering clusters in data by first determining the number of clusters k, allocate the initial centroids, and then clustering data points by assign each data point to one centroid. We use the idea of Gravity, by assuming each data point in the cluster has a gravity that attract the other closest points, this leads each point to move toward the nearest higher gravity toward the nearest higher gravity point to have at the end one point for each cluster, which represent the centroid of that cluster. The measure of gravity of point (X) determined by its weight, which represent the number of points that use point X as the nearest point. Our algorithm employ a distance metric based (eg, Euclidean) similarity measure in order to determine the nearest or the similar point for each point. We conduct an experimental study with real-world as well as synthetic data sets to demonstrate the effectiveness of our techniques.