Comparison of K means Clustering Initialization Approaches with Brute Force Initialization
Data clustering is a basic data mining discipline that has been in center of interest of many research groups. This paper describes the formulation of the basic NP hard optimization problem in data clustering which is approximated by many heuristic methods. The famous k means clustering algorithm and its initialization is of a particular interest in this paper. A summary of the k means variants and various initialization strategies is presented. Many initialization heuristics tend to search only through a fraction of the initial centroid space. The final clustering result is usually compared only to some other heuristic strategy. In this paper we compare the result to the solution provided by a brute force experiment. Many instances of the k means can be executed in parallel on the high performance computing infrastructure, which makes brute force search for the best initial centroids possible. Solutions obtained by exact solvers [2, 11] of the clustering problem are used for verification of the brute force approach. We present progress of the function optimization during the experiment for several benchmark data sets, including sparse document term matrices.
ACSS