parallelizing $k$-means

Question

I'm having trouble thinking about the following. If we have two machines 1 and 2 that evenly split a set of data points, does $k$-means separately, then averages the result, does this agree with just $k$-means on one machine?

To be more specific, consider the following routine:

1. Split an input dataset evenly between 1 and 2.
2. Initialize $k$ centroids that are the same on both 1 and 2.
3. Use $k$-means algorithm to find updated centroids.
4. Find a new set of $k$ centroids by averaging the corresponding centroid from 1 and 2.
5. Loop over 2.

Will this agree with just running $k$-means? I think that it is the averaging part that might work, but then I'm not sure if this routine finishes running.

Answer 1

Short answer is yes, you can parallelize $k$-means, essentially as you described.

First, on each processor, you assign points to the centroids closest to them. This part is trivial as long as each processor knows the locations of the centroids.

Next, you compute the new location of the centroids on each processor, and then combine them. But as Raphael pointed out in his comment, you have to weight the centroids from machine 1 and machine 2.

Let's consider a simple example, and only look at 5 points assigned to one of the centroids $C$. Suppose that machine 1 has points $x_1$ and $x_2$ and machine 2 has points $x_3, x_4$ and $x_5$. If we were dealing with the standard (single processor) version of $k$-means, then the new location of $C$ would be $$ C' = \frac{1}{5} \sum_{i=1}^5 x_i $$

The contribution from machine 1 is $$C_1 = \frac{1}{2} \sum_{i=1}^2 x_i$$

and the contribution from machine 2 is $$ C_2 = \frac{1}{3} \sum_{i=3}^5 x_i $$

In order to properly combine the results from the two machines, you just do the algebra: $$ C' = \frac{1}{5}(2C_1 + 3C_2) $$

Your stopping condition should be the same as in the standard version of $k$-means.