Data Algorithms

Chapter 12. K-Means Clustering

This chapter will provide a MapReduce solution for the K-Means clustering algorithm. The K-Means clustering algorithm is interesting and different from other MapReduce algorithms. It is an iterative algorithm (that is, it requires multiple MapReduce phases) that you execute many times with different centroids until it converges (meaning that K optimal clusters are found after many iterations of the same MapReduce job).

But what is clustering? And what is K-Means? In a nutshell, we can say that, given K > 0 (where K is the number of clusters) and a set of N d-dimensional objects to be clustered:

• Clustering is the process of grouping a set of N d-dimensional (2-dimensional, 3-dimensional, etc.) objects into K clusters of similar objects.

• Objects should be similar to one another within the same cluster and dissimilar to those in other clusters.

K-Means is a distance-based clustering algorithm. K-Means clustering has many useful applications. For example, it can be used to find a group of consumers with common behaviors, or to cluster documents based on the similarity of their contents. The first question is: how do we determine the value of K as the number of groups or clusters we want to generate from our input data? Selection of K is specific to the application or problem domain. There is no magic formula to find K.

An example of a K-Means for K = 3 is given in Figures 12-1 and 12-2. Figure 12-1 shows the raw data, whereas Figure 12-2 shows ...