An Improved K-means Method with Density Distribution Analysis

College of Science, China Agricultural University, Tsinghua East Road, Beijing, China

Abstract

In this paper, a novel K-means clustering algorithm is proposed. Before running the traditional Kmeans, the cluster centers should be randomly selected, which would influence the time cost and accuracy. To solve this problem, we utilize density distribution analysis in the traditional K-means. For a reasonable cluster, it should have a dense inside structure which means the points in the same cluster should tightly surround the center, while separated away from other cluster canters. Based on this assumption, two quantities are firstly introduced: the local density of cluster center ρi and its desperation degree δi, then some reasonable cluster centers candidates are selected from the original data. We performed our algorithm on three synthetic data and a real bank business data to evaluate its accuracy and efficiency. Comparing with Traditional K-means and K-means++, the results demonstrated that the improved method performs better.