Gradient-k: Improving the performance of K-Means using the density gradient

Abstract

We introduce Gradient-k, an upgrade of the k-means algorithm that improves clustering accuracy and reduces the number of iterations required for convergence. This is achieved by correcting the distance used in the k-means algorithm by a factor based on the angle between the density gradient and the direction to the cluster center. We show that this correction allows the algorithm to go beyond the traditional tessellation obtained by k-means, enabling the creation of nonlinear separation boundaries. The correction also provides the ability to distinguish clusters having non-normal shapes and of varying densities. Furthermore, Gradient-k has a lower computational complexity for datasets with many samples. We compare the performance of Gradient-k with that of k-means and of DBSCAN on several benchmark datasets, as well as on a more realistic dataset in the context of neural spike sorting.