A Parallel Clustering Algorithm Implementation Based on Apache Mahout

摘要

K-means clustering is one of the most famous clustering algorithms. It is widely used in many practical applications. K-means clustering is the task of dividing a set of n data points in d-dimensional space into k clusters. The data points in the same cluster are much closer to each other than to those in other clusters according to certain criteria. Traditional k-means clustering proceeds by alternatively executing two steps: assignment step and update step. The assignment step assigns each data point to its nearest cluster. The Euclidean distance is commonly used to measure the distance. The update step calculates the new center of each cluster and updates them. For large-scale dataset, the k-means clustering spends most of its execution time on calculating distances between each data point and existing cluster centers. It is obvious that distance computation for each data point is irrelevant to the others. Therefore these distance calculations can be completed concurrently. In this paper, a simple and efficient implementation of a parallel k-means clustering algorithm is proposed based on the existing mahout API, in order to speed up clustering for large-scale dataset. In addition, the implementation was packaged and can be offered as an easy to use API for developers who can easily accomplish their task without any other configurations. Experimental results revealed a significant improvement in clustering speed for large-scale dataset. It demonstrates the effectiveness and efficiency of the proposed implementation.