Successive Binary Partition K-means Method for Clustering with Less Cluster Size Bias

We propose a clustering algorithm with less cluster size bias. Conventional clustering algorithms, such as the K-means method, aim to minimize the mean square error between the centroid of the cluster and the samples in the cluster, which may lead to a biased number of samples in the resulting clusters. In response to this, several algorithms have been proposed for optimization, such as the balanced k-means method, which gives equal-sized clusters as a result. However, it has a drawback of slow speed. This paper proposes a relatively fast heuristic algorithm with less bias in the number of samples in the clusters. This method successively divides clusters with large cluster sizes into two parts, and when the desired number of clusters is reached, the centroid is optimized again. The last optimization allows us to adjust the bias and error of the clusters. Two experiments were conducted for evaluation. In the first experiment, we applied the proposed method and the k-means, k-means++, and balanced k-means methods to the generated data and measured the computation time. The results showed that the proposed method was slower than the k-means method but faster than the other methods. In the second experiment, the image data from CIFAR-100 were clustered and compared with k-means. We measured the error and cluster size bias, and the results showed that we could control the trade-off between error and cluster size bias.