LM Data Mining and Machine Learning (2024)

Lab 2 – Clustering and PCA

Objectives

The objective of this lab is to use the methods described in lectures to discover the structure of a particular data set. At the end of the lab your task is to write down an intuitive textual description of the data.  The techniques that you should apply are clustering and PCA.

What you will need

All of the files that you will need are in the zip archive lab2-2024.zip which is on the Canvas page.

The Data

The data is stored in a text file called lab2Data (contained in the lab2-2024.zip file).  The data consists of 1050 points in 6 dimensional space.  Each point appears as a row in the data file – have a look at the file to see its structure.  There is a ‘header’ at the top of the file that specifies the number of columns and rows.

Part 1: Clustering

Your first task is to use clustering to try to determine whether there are natural clusters in the data, and if there are, how many.  To do this you need to apply clustering to the data.  You need two C programs agglom.c and k-means.c.  Use the provided .exe files (or compile these two source C programs if needed).

The  program  agglom.c is  an   implementation  of  the  agglomerative  clustering  algorithm described in lecture material.  You should apply this to the data set to obtain a set of K initial centroids  for  k-means  clustering  (see  the  lecture  notes  to  understand  how).     Then  use k-means.c to locally optimize the centroids.   As well as producing a locally optimized set of centroids,  k-means.c returns the distortion for that set of centroids relative to the data.   I recommend 15 iterations of k-means clustering.

Usage of agglom program:      agglom dataFile centFile numCent

Runs  agglomerative  clustering  on  the  data  in  dataFile  until  the  number  of  centroids  is

numCent.  Writes the centroid coordinates to centFile.

Usage of k-means program:   k-means dataFile centFile opFile numIter

Runs  numIter iterations  of  k-means  clustering  on  the  data  in  dataFile starting  with  the centroids in centFile.  After each iteration writes distortion and new centroids to opFile.

You should use agglom.c and k-means.c to plot a graph of distortion as a function of K, the number of clusters.  Plot distortion for values of K between 1 and 12.  To clarify:

for K=1 to 12

•    Apply agglom.c to the data set to obtain K initial centroids

•    Apply 15 iterations of k-means clustering.  A list of 15 numbers will appear on the screen. What are they?  For each K make a note of the final number.

Plot a graph of these 12 final numbers against K.   Note that to analyse data structure, it might sometimes be useful to plot the distortion in a log-scale or to plot the ratio of the distortion for K clusters to the distortion for K+1 clusters.

Conclusion to Part 1:  What does the graph tell you about the structure of the data?

Part 2: Principle Components Analysis (PCA)

To apply PCA to the data you will need to use MATLAB.  MATLAB will complain about the header at the start of the data file lab2Data.  Therefore I have created a version of this file without the header, called lab2Data-Matlab.  Use this file with MATLAB.

The procedure for applying and interpreting PCA is described in lecture material.   In  brief, the stages are as follows:

1. Load the data into a matrix, X say, in MATLAB.

2. Compute the covariance matrix of the data. You can either do this by implementing the formula for covariance given in the lectures, or you can simply use the MATLAB cov function:

>> C = cov(X)

3. Apply eigenvector/eigenvalue decomposition to the covariance matrix: >> [U,D] = eig(C)

Conclusion to  Part  2:   Write  down  the  eigenvalues.    What  does  the  eigenvector/eigenvalue decomposition of the covariance matrix C  tell you about the structure of the data set?

Explain how your Part 2 conclusion is likely to change if each sample in the dataset was modified by adding the value of 15 in the dimension 1 and value of 30 in the dimension 4 (e.g., considering original data sample was [1, 3, 5, 0, 2, 3], the new data sample would be [16, 3, 5, 30, 2, 3]).

Finally: Your summary

Summarize your findings (with a support for your arguments).