Symmetric repositioning of bisecting K-means centers for increased reduction of distance calculations for big data clustering

Clustering is one of the fundamental data mining procedures. Bisecting K-means (BKM) clustering has been studied to have higher computing efficiency and better clustering quality when compared with the basic Lloyd version of the K-means clustering. Elkan's method of utilizing triangle inequality significantly reduces distance calculations, and is applicable to each K-means iteration without affecting the clustering result of the iteration. Thus, it is natural to think of using the Elkan method to further improve the efficiency of the already efficient bisecting K-means. In this paper, we find that the bisecting K-means allows the repositioning of the two centers of a to-be-bisected cluster to further reduce distance calculations. Based on our heuristic analysis we investigate a repositioning strategy with a set of repositioning parameters, and incorporated the repositioning techniques into the Elkan method for bisecting K-means algorithms. We tested these new algorithms on three big datasets with millions of data points and compared with the straightforwardly combined Elkan-BKM without center repositioning. The experimental results show that the center-repositioned algorithms have fewer distance calculations than the Elkan-BKM algorithms without center repositioning in almost all cases. While our repositioning parameters produced good results for the tested datasets, these parameter sets are derived based on our intuitive thinking and hence they are by no means optimal. The experimental data presented in this paper suggest the potential of achieving higher efficiency if better repositioning parameters can be discovered.