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:
- Split an input dataset evenly between 1 and 2.
- Initialize $k$ centroids that are the same on both 1 and 2.
- Use $k$-means algorithm to find updated centroids.
- Find a new set of $k$ centroids by averaging the corresponding centroid from 1 and 2.
- 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.