Matlab

COMP3032 COURSEWORK DATA REPRESENTATION AND CLUSTERING

USING GRAPH LAPLACIANS

SRINANDAN DASMAHAPATRA

1. Representing data using nearest-neighbour graphs

For a given dataset D = {x1, . . . , xN}, where each x ∈ RD is a D-dimensional vector, with each vector xi containing D real valued entries xi,k for k = 1, . . . , D, you can use the Euclidean distance d(i, j) between pairs of points

d(i, j) := ||xi −xj||2 = D∑

k=1

(xi,k −xj,k) 2

to define a neighbourhood around each point xi. For each i sort the distances {d(i, j)}j=1,...,N , and take the first k among the N − 1. These are the k nearest neighbours of i and performing this task for each point xi ∈D is called the k near- est neighbours algorithm.

1.1. Task 1. Construct the k-nearest neighbour graph G∗k of the data set in the file circles3d.mat. This is a file that can be opened by calling

• load(’circles3d’) in MATLAB • scipy.io.loadmat(’circles3d.mat’) in python.

This file contains some 3-dimensional data labelled by X for which you should con- struct a weighted adjacency matrix W∗G with entries w∗ij between nodes i and j in the k-nearest neighbour graph. The weights w∗ij are calculated using the Euclidean distance:

wij =

{ exp

( −d(i,j)

`

) , if i and j are connected in G∗k

0 otherwise

where ` is a scale factor. Construct the corresponding Laplacian matrix L∗. Find the eigenvalues of the Laplacian L∗. Why are the eigenvalues not all real?

1.2. Task 2. Construct a modified weighted adjacency graph by taking the graph G∗k generated in Task 1 and sharing the weight wij between node i and its neighbour j and the weight wji between nodes j and i.

Date: November 5, 2013. 1

2 SRINANDAN DASMAHAPATRA

2. Embedding the data and clustering using the eigenvectors of the Laplacian

2.1. Task 3. Construct the Laplacian matrix L∗ corresponding to matrix W∗ in Task 1 and the Laplacian L corresponding to the modified weighted adjacency matrix W in Task 2. Why does one of the Laplacians have real, and the other, complex eigenvalues? What can you verify about the relationship between the eigenvectors in each case?

2.2. Task 4. To each data point xi ∈ D, where D = X the data in the file circles3d.mat, associate the corresponding entries in the first 3 non-trivial eigen- vectors v1, v2, v3. (You should know what this means.) This step provides a repre- sentation of the data: xi 7→ xLi := (v1(i), v2(i), v3(i)). (In general we could choose any number of eigenvectors, but here just use 3.) Provide a visualisation of the result of this step.

2.3. Task 5. Perform a k means clustering on the data represented as xLi for i = 1, . . . , N. Use k = 2 clusters. Do not get confused between the k-nearest neighbour algorithm in Task 1 and the k-means clustering algorithm required here.

Explore how the results of the clustering depends on the number of neighbours in the k-nearest neighbour graph and in the choice of the scale parameter ` used to define wij. You will find that for certain choices, you get a clear separation between the two clusters. Explain why that is the case.

The binary entries of the array y in the data file circles3d.mat are the cluster- membership values: for each index i, X(i) is the data vector and y(i) is the cluster it belongs to. Use these values to colour the points and compare with the results of the clustering.

2.4. Task 6. Use the code you have written to perform a clustering of the data in file cluster.mat. Once again, explore the range of values of ` and the size k of the neighbourhood in the graph Gk. Comment on what you did and found.

3. Submission

You should submit a 3-page document (you may go up to the 4th page, if you must, but you will be heavily penalised if the report is any longer the 4 pages) answering the questions and reporting on your results. For every claim that you make, you have to provide backing evidence. You should find the best way of presenting the evidence, whether it is with tables, graphs or code snippets. This will determine the marks you receive.

You should upload the document and code as a .zip or tar.gz file to the C-Bass hand-in site by December 5, 2013.