\documentclass[12pt]{article}
\usepackage{epsfig}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{epstopdf}
\usepackage{url}
\usepackage{verbatim}
\usepackage{moreverb}

\newcommand{\vek}[1]{{\bf {#1}}}



\title{K-Means Clustering on MapReduce}
\author{Prepared by Yanbo Xu}
\date{Out April 3, 2013\\
Due Wednesday, April 17 2013 via Blackboard}

\begin{document}

\maketitle

\section{Important Note}

{\bf You are expected to use Java for this assignment.}

Yanbo Xu (yanbox@cs.cmu.edu) is the contact TA for this homework. Please post clarification questions to the Google Group: 

machine-learning-with-large-datasets-10-605-in-spring-2013

\section{Overview}

K-Means iteratively improves the partition of the data into K sets:
\begin{itemize}
\item{} Predefine the number of clusters, K
\item{} Initialize K cluster centroids
\item{} Iteration until the centroids no longer change
\begin{itemize}
\item{} Associate each data instance with the closest centroid (we consider them in a Euclidean space in this assignment)
\item{} Recalculate centroids as an average of the associated data instances
\end{itemize}
\end{itemize}

\section{K-Means Clustering on MapReduce}
To parallelize K-Means on MapReduce, we are going to share some small information, i.e. the cluster centroids, across the iterations. This will result in a duplication, but very minimal comparing with the large amount of data.\\

Therefore, before starting, a file is created accessible to all processors (through FileSystem in Configuration()) that contains the initial K cluster centroids. This file will be updated after each iteration to contain the latest cluster centroids calculated by Reducer. Then\\

\begin{enumerate}
\item{} The {\bf Mapper} reads this file to get the centroids from last iteration. It then reads the input data and calculates the Euclidean distance to each centroid. It associates each instance with the closest centroid, and outputs (data instance id, cluster id).
\item{} Since this is a lot of data, we use a Combiner to reduce the size before sending it to Reducer. The {\bf Combiner} calculates the average of the data instances for each cluster id, along with the number of the instances. It outputs (cluster id, (intermediate cluster centroid, number of instances)).
\item{} The {\bf Reducer} calculates the weighted average of the intermediate centroids, and outputs (cluster id, cluster centroid).
\end{enumerate}

The {\bf main} function runs multiple iteration jobs using the above Mapper + Combiner + Reducer. You can use the following sample codes\footnote{\url{http://codingwiththomas.blogspot.com/2011/04/controlling-hadoop-job-recursion.html}} to implement the multiple iterations in {\bf main}:
\begin{verbatim}
   int iteration = 0;
   
   // counter from the previous running import job
   long counter = job.getCounters().findCounter(Reducer.
   Counter.CONVERGED).getValue();
 
   iteration++;
   while (counter > 0) {
      conf = new Configuration();
      conf.set("recursion.iter", iteration + "");
      job = new Job(conf);
      job.setJobName("KMeans " + iteration);
 
      //...
      // job.set Mapper, Combiner, Reducer...
      // ...
   
      // always take the output from last iteration as the input
      in = new Path("files/kmeans/iter_" + (iteration - 1) + "/");
      out = new Path("files/kmeans/iter_" + iteration);
 
      //...
      // job.set Input, Output...
      // ...
   
      // wait for completion and update the counter
      job.waitForCompletion(true);
      iteration++;
      counter = job.getCounters().findCounter(Reducer
      .Counter.CONVERGED).getValue();
   }
\end{verbatim}

Regarding the Counter, you can define an enum in {\bf Reducer}:

\begin{verbatim}
    public enum Counter{
       CONVERGED
    }
\end{verbatim}    

and then update the counter:

\begin{verbatim}
   context.getCounter(Counter.CONVERGED).increment(1);
\end{verbatim}  


\section{The Data}
We are going to cluster the Census data that was collected by the U.S. Census Bureau in 1990. Many of the less useful attributes in the original data set have been dropped, the few continuous variables have been discretized and the few discrete variables that have a large number of possible values have been collapsed to have fewer possible values. As a result, the data contains 68 categorical attributes. \\

The data appears at \url{/afs/cs.cmu.edu/project/bigML/census/}, and are also available in the public s3 bucket: \url{s3://bigml-shared/census}. The first row contains the list of attributes. The first attribute is a case id and should be ignored during analysis. The data is comma delimited with one case per row. Again, a small toy data is provided for debugging.

\begin{verbatim}
    USCensus1990.small.txt
    USCensus1990.full.txt
\end{verbatim}  

For the convenience of grading, the initial cluster centroids for K=8 and K=12 were already randomly generalized. Please use the following files as your starting points. Each row starts with a cluster id, and follows by the centroid's case id and values of the 68 attributes. Each row is still comma delimited.

\begin{verbatim}
    centroids8.small.txt
    centroids12.small.txt
    centroids8.full.txt
    centroids12.full.txt
\end{verbatim} 

\section{Deliverables}
Submit a compressed archive (zip, tar, etc) of your code, along with the controller and syslog files from AWS. Please include a pdf document with answers to the questions below.

\begin{enumerate}
\item Run K=8 and K=12 clusters on the small data, report the cluster centroids, the number of iterations for convergence, and the wall time respectively.
\item Run K=8 and K=12 clusters on the full data, report the cluster centroids, the number of iterations for convergence, and the wall time respectively.\\

For each iteration, we compared each instance to each possible centroid, which may result in a large computation cost. We can reduce the number of distance comparison by applying the Canopy Selection, described as in \url{www.kamalnigam.com/papers/canopy-kdd00.pdf}.

Please read the paper, and answer:
\item What distance metric would you choose for the canopy clustering? Why?
\item Can you implement the Canopy Selection on MapReduce? If yes, please describe the workflow.
\item Describe the workflow to combine the Canopy Selection with K-Means on MapReduce.
\end{enumerate}

BONUS question: Implement the Canopy Selection with K-Means on MapReduce. Run K=12 on both small and full data. Report the cluster centroids, the number of iterations for convergence, and the wall time respectively.

\section{Marking breakdown}
\begin{itemize}
\item Code correctness: {\bf [45 points]}.
\item Question 1, 2 {\bf [10+10 points]}
\item Question 3, 4, 5 {\bf [5 + 15 + 15 points]}
\item BONUS question:  {\bf [20 points]}
\end{itemize}

\end{document}

