Iterative MapReduce reuses workers and data partitions across repeated MapReduce cycles. In k-means, mappers are configured with fixed point shards once, while each iteration passes only the current centroids. This avoids repeatedly distributing the full dataset. section 13.3
A typical iterative cycle proceeds as follows:
- Initialize point shards, mappers, reducers, and centroids. section 13.3
- Have each mapper classify its assigned points against the current centroids. section 13.3
- Have reducers collect points by cluster and compute new centers of mass. section 13.3
- Repeat until centroids stop changing or the maximum iteration count is reached. section 13.3
Listing 13.2 MapReduce k-means
function MRkmeans(points, numShards, numClusters, maxIter, T1, T2) #1
shards ← randomShard(points, numShards) #2
centroids ← MRcanopyCentroids(points, numClusters, T1, T2) #3
mappers ← initMappers(numShards, classifyPoints, shards) #4
reducers ← initReducers(numClusters, centerOfMass) #5
for i in {0, .., maxIter-1} do #6
newCentroids ← mapReduce(centroids, mappers, reducers) #7
if centroids == newCentroids then #8
break
else
centroids ← newCentroids #9
return combine(mappers, centroids) #10
Pseudocode shows initialization, centroid passing, repeated map-reduce execution, convergence testing, and final combination. section 13.3
