The objective of the final project is to apply what you have learned in ENGR- 160 this semester to perform Unsupervised Machine Learning and digital image compression in MATLAB.

The project consists of the following components.

1.              Read through each page in this project statement carefully to understand the project requirements.

2.              Form a team with a peer student, develop and document a collaboration plan, using the attached TeamWorksheet.xlsx  template.

3.              Implement the K-means clustering algorithm, perform experiments and apply it to compress an image.

4.              Use  only  functions  contained  in  the  basic  MATLAB  installation;  do  not  use  functions  from optional toolboxes (e.g. machine learning toolbox, image processing toolbox, curve -fitting toolbox, optimization toolbox, etc.).

5.             Write a final project report that includes the following three sections.

a.     The result of K-mean clustering algorithm on the test datasets and for the image compression application.

b.     Research on recent machine learning applications in your (intended) major discipline. Give at least two specific examples, including:

i.    The problem statement (inputs, outputs)

ii.    References (of the original sources)

c.     Conclusion

i.    Reflect on what you have learned from the project.

ii.    Comment on your learning experience from this project compared to attending lectures, reading books, and any other learning activities in general.

iii.    Any comments/feedbacks on the project and the class.

Grading Rubrics: (30 pts)

1.     The three programs (kMeansCompute.m, labelsKMeans.m, imageCompress.m).                12 points

2.     Report/participation scores:                                                                                                                  18 points

a.     The final report (part a and b)                                                                                              8 Pts

b.     Conclusion/Individual reflections (part c)                                                                      4 Pts

c.     Teamwork and team worksheet                                                                                          4 Pts

d.     Posting questions and answers to the Brightspace discussion board.                 2 Pts

Files for submission (6 total):

•    kMeansCompute.m

•    labelsKMeans.m

•    imageCompress.m and its published PDF

•     TeamWorksheet.xlsx

•    Final project report (.pdf)

Part I:  k-Means Clustering

The k-Means Clustering algorithm is an unsupervised learning algorithm that classifies data into  k distinct clusters. Clustering is the task of grouping data together based on some measure of similarity. For example, we might cluster based on Euclidean distance:

Figure 1. Clusters of Data

InFigure 1, we see three clusters of data points centered at different locations. The closer together points are the more similar they are. Typically, clustering is done as a way of looking for possibly unknown patterns in a dataset. In this problem, we implement the k-means algorithm and apply it to a couple of example datasets.

In order to solve the clustering problem, you will be implementing the k-means algorithm. The basic idea of the k-means algorithm is to construct a collection of k means and the cluster the rest of the data based on these means. For now, we will use a generalized notion of “distance” to measure similarity. The “distance” is measured by some function on the two data points. If two vectors are closer together, they are more similar. Thus, we cluster the data based on what mean (or centroid) the piece of data is closest to:

Cluster of xi = {k | min||µk − xi ||}

k

where ||µk − xi || is the “distance” between the kth mean µ and the data point xi .

We can then use these clusters to update the centroids, so:

uk  =   xi

where Ck  is the set of examples that are assigned to centroid k . Putting it all together, we start by randomly picking data points from the matrix as the centroids. We then iterate, using the means to first cluster the data,

and then using the clusters as feedback on the centroids. We repeat this process for a fixed number of iterations. Please complete the two algorithms outlined below:

%%The   k -Means Algorithm : 

Initialization:    Pick k random data points from the data set and assign these to the initial centroids

defined as u

Repeat

1.  Set  uk(old)  = u

2.  Cluster the data based on these old means, i.e., assign each data point a number 1 to k corresponding to which mean it is closest to according to the 

3.  Take the average value of each of these clusters and assign them as the new mean values or uk(n)ew

Stop   when number of iteration (numIter) is reached or maxk ฮuk(n)ew − uk(old) ฮ < tol

The above function will have following inputs:

.  data - the data to be clustered. Should be an n×d matrix where each row should be a new data point in

the data set.

.  k - the number of clusters your algorithm is searching for. At the end, you will have k means that organize

the data into k clusters.

.  tol - the tolerance that we set to say the means have stopped updating. This is like the tolerance values

from the Newton-Raphson methods (see Zybook). Threshold based on the absolute difference between the means and the updated means, i.e. for all  k: ‖uk(n)+1 − uk(n)‖2 < tol. (Hint: use norm).

.  distFunc  -  the  distance  function  you  are  using  to  compare  the  data.  Should  take  two  row  vector

arguments and return a scalar. So something like: distFunc = @(a, b) norm(a - b) for the 2-norm distance. IT MUST TAKE A GENERAL FUNCTION HANDLE.

.  maxIter - the maximum number of iterations the algorithm will run for.

And the following outputs:

.  means - a k × d matrix. Each row should be one of the means (centroid) found by the k means algorithm.

.  clusters - a length n column vector with each giving the cluster the corresponding row in the data matrix

belongs to

.  iter - the number of iterations the algorithm ran for.

And:

%%Clustering a dataset given a set of means

For Each Data Point

1.     Find which of the means stored in  it is closest to based on  and store the appropriate label.

The above function has the following inputs:

.  means - the means to use for clustering. Should be a k × d array of data with each row representing a

different mean.

.  meansLabels - the labels of the means. Should be a k × 1 column array with each row giving the label of

the corresponding row in the means array.

.  data - the data to be clustered. Should be an N×d array of data with each row representing a different

data point.

.  distFunc - the distance function used to compare how close two values are. It should be a general function

handle of two 1 × d arrays and calculates the distance between them.

And the following outputs:

.  dataLabels - the labels of the means. Should be a N ×1 column array with each row giving the label of the

corresponding row in the data array.

Try using the 2-norm of the difference of the vectors as the distance:

‖a − b‖2  = √(ai  − bi )2

Recall, the 2-norm in MATLAB is just: norm(v) where v is the vector whose 2-norm we want to calculate. In order to test your algorithm, we have provided a couple of data sets to play around with:

1.  dataset1.mat - the toy dataset as shown inFigure 1.

2.  dataset2.mat – a second dataset for testing

The  above  datasets  are  accessible  through  Brightspace  along  with  a  MATLAB  function  plotDataPoints  for visualizing the data. Each of these datasets contains the following variables:

1.  dataTrain - n × d matrix of data points, organized so that each row is a new data point. This is the training data for your algorithm.

2.  labelsTrain - n × 1 column vector of labels that give the classification of each data point. These are the labels of the training data.

The labels here a meant to be used with the function mapLabels (provided). This function uses the mode of the labels in the  cluster to  relabel the  cluster based  on the labels in the  dataset.  Since  k-Means uses  random initialization, it is likely what we call cluster 1 does not correspond to label 1. This code does the mapping for you using the mode. You can thus check the accuracy of your k-Means algorithm on the training sets by first mapping the labels using mapLabels and comparing the result of labelKMeans with the labels provided in the dataset.

The first dataset is very well separated, in the sense that each mean has it’s own distinct cluster. We expect to have 100% accuracy in such a situation as we should be able to find a mean based at the center of each of the circular portions. The second dataset is not as well separated and in such a situation as we will not be able to find a mean for each of the clusters that results in 100% accuracy. You need to perform some experiments on both data sets. How many training iterations (e.g 2, 3, 5) did you set for the k-means algorithm? What is the obtained accuracy for different training iterations? What is a good tolerance value (e.g. 0.01) to set? Write up your experimental findings in the final report.

For the experiment, it is suggested that you create a script file that read in the data, set the k-means parameters, run the k-means algorithm, relabel the clusters and then compute accuracy. A snippet of the script is as follows:

%% Run K-mean algorithm on training dataset

[centroids, idx, itr] = kMeansCompute(dataTrain, K, distFunc, tol, max_iters);

%% Relabel the clusters

meanLabels = mapLabels(centroids, idx, labelsTrain);

idxTrain = labelKMeans(centroids, meanLabels, dataTrain, distFunc);

%% Prediction accuracy on training and test dataset

trainAccuracy = sum(idxTrain == labelsTrain)/length(idxTrain);

Note, although these labels are included in the dataset to give you some notion of the how well the algorithm is working, they are not ever used in the k-Means algorithm. That algorithm purely relies on the distance function provided with updates based on feedback from the clustering calculated by the distance function. In some sense the  labels  are  entirely  arbitrary  with  clusters  being  identified  by  which  means  they  are  closest  too.

plotDataPoint uses the labels to visualize the different clusters in the dataset as shown inFigure 1.

To receive credit, you must turn in kMeansCompute.m and labelsKMeans.m.

We will be applying the training process implemented in kMeansCompute to image compression in Part II of this project.

List of useful built-in MATLAB functions and provided MATLAB utilities for Part I of the project are:

•     norm, min, mean (built-in functions)

•     mapLabels.m

•    plotDataPoints.m

Note a template is given for kMeansCompute.m on Brightspace. The template has implemented the initialization process which picks k random points from the data set as starting points . Do not modify the given initialization part of the code. Your programs, kMeansCompute. m and labelsKMeans.m, will be checked by an autograder.

Part II:  Image compression with K-means

In Part II, you will apply K-means to image compression. PNG  (Portable Network Graphic) is a popular file format for storing uncompressed 24-bit color representation of an image, each pixel is represented as three 8- bit unsigned  integers  (ranging  from  0 to  255) that  specify the  red,  green,  and blue  intensity values. This encoding is often referred to as the RGB encoding. An image may contain thousands of colors, and in this part of the project, you will reduce the number of colors to 32 colors.

By making this reduction, it is possible to represent (compress) the photo in an efficient way. Specifically, you only need to store the RGB values of the 32 selected colors, and for each pixel in the image you now need to only store the index of the color at that location (where only 5 bits are necessary to represent 32 possibilities).

In  Part  II, you  will  use  the  K-means  algorithm  to  select the  32  colors  that will  be  used  to  represent the compressed image. Specifically, you will treat every pixel in the original image as a data example and use the K-means algorithm to find the 32 colors that best group (cluster) the pixels in the 3-dimensional RGB space. Once you have computed the cluster centroids on the image, you will then use the 32 colors to replace the pixels in the original image.

K-means on pixels

In Matlab, images can be read in as follows:

This creates a three-dimensional matrix A whose first two indices identify a pixel position and whose last index represents red, green, or blue. For example, A(50, 33, 3) gives the blue intensity of the pixel at row 50 and column 33.

The code inside imageCompress.m should first load the image, scale it, and then reshapes it to create an m × 3 matrix of pixel colors (where m = 16384 = 128 × 128), and calls your K-means function on it.

After finding the top K = 32 colors to represent the image, you can now assign each pixel position to its closest centroid using the kMeansCompute function. This allows you to represent the original image using the centroid assignments of each pixel. Notice that you have significantly reduced the number of bits that are required to describe the image. The original image required 24 bits for each one of the 128×128 pixel locations, resulting in total size of 128×128×24 = 393,216 bits. The new representation requires some overhead storage in the form of a dictionary of 32 colors, each of which require 24 bits, but the image itself then only requires 5 bits per pixel location. Determine the final number of bits used in the compressed image and the compression ratio and include them in the imageCompress.m (show the details of the calculation).