Modified global kk-means algorithm for minimum sum-of-squares clustering problems

kk-Means algorithm and its variations are known to be fast clustering algorithms. However, they are sensitive to the choice of starting points and inefficient for solving clustering problems in large data sets. Recently, a new version of the kk-means algorithm, the global kk-means algorithm has been developed. It is an incremental algorithm that dynamically adds one cluster center at a time and uses each data point as a candidate for the kk-th cluster center. Results of numerical experiments show that the global kk-means algorithm considerably outperforms the kk-means algorithms. In this paper, a new version of the global kk-means algorithm is proposed. A starting point for the kk-th cluster center in this algorithm is computed by minimizing an auxiliary cluster function. Results of numerical experiments on 14 data sets demonstrate the superiority of the new algorithm, however, it requires more computational time than the global kk-means algorithm.