Machine Learning with MapReduce K-Means Clustering 3 How to MapReduce K-Means? Given K, assign the first K random points to be the initial cluster centers Assign subsequent points to the closest cluster using the supplied distance measure Compute the centroid of each cluster and iterate the previous step until the cluster centers converge within delta Run a final pass over the points to cluster them for output K-Means Map/Reduce Design Driver Runs multiple iteration jobs using mapper+combiner+reducer Runs final clustering job using only mapper Mapper Configure: Single file containing encoded Clusters Input: File split containing encoded Vectors Output: Vectors keyed by nearest cluster Combiner Input: Vectors keyed by nearest cluster Output: Cluster centroid vectors keyed by “cluster” Reducer (singleton) Input: Cluster centroid vectors Output: Single file containing Vectors keyed by cluster Mapper - mapper has k centers in memory. Input Key-value pair (each input data point x). Find the index of the closest of the k centers (call it iClosest). Emit: (key,value) = (iClosest, x) Reducer(s) – Input (key,value) Key = index of center Value = iterator over input data points closest to ith center At each key value, run through the iterator and average all the Corresponding input data points. Emit: (index of center, new center) Improved Version: Calculate partial sums in mappers Mapper - mapper has k centers in memory. Running through one input data point at a time (call it x). Find the index of the closest of the k centers (call it iClosest). Accumulate sum of inputs segregated into K groups depending on which center is closest. Emit: ( , partial sum) Or Emit(index, partial sum) Reducer – accumulate partial sums and Emit with index or without EM-Algorithm What is MLE? Given A sample X={X1, …, Xn} A vector of parameters θ We define Likelihood of the data: P(X | θ) Log-likelihood of the data: L(θ)=log P(X|θ)