  K-means is a popular clustering method used in data mining area. To work with
large datasets, researchers propose PKMeans, which is a parallel k-means on
MapReduce. However, the existing k-means parallelization methods including
PKMeans have many limitations. PKMeans can't finish all its iterations in one
MapReduce job, so it has to repeat cascading MapReduce jobs in a loop until
convergence. On the most popular MapReduce platform, Hadoop, every MapReduce
job introduces significant I/O overheads and extra execution time at stages of
job start-up and shuffling. Even worse, it has been proved that in the worst
case, k-means needs $2^{{\Omega}(n)}$ MapReduce jobs to converge, where n is
the number of data instances, which means huge overheads for large datasets.
Additionally, in PKMeans, at most one reducer can be assigned to and update
each centroid, so PKMeans can only make use of limited number of parallel
reducers. In this paper, we propose an improved parallel method for k-means,
IPKMeans, which has a parallel preprocessing stage using k-d tree and can
finish k-means in one single MapReduce job with much more reducers working in
parallel and lower I/O overheads than PKMeans and has a fast post-processing
stage generating the final result. In our method, both k-d tree and the new
improved parallel k-means are implemented using MapReduce and tested on Hadoop.
Our experiments show that with same dataset and initial centroids, our method
has up to 2/3 lower I/O overheads and consumes less amount of time than PKMeans
to get a very close clustering result.
