CS178 - Machine Learning & Data Mining - Homework 5 - Clustering - Solved

In this problem, you will experiment with two clustering algorithms implemented in the updated mltools package: k-means and agglomerative clustering.

1.    Load the standard Iris dataset, select the first two features, and ignore the class (or target) variables. Plot the data and see for yourself how “clustered” you think it looks. Include the plot, say how many clusters you think exist, and briefly explain why. (There are multiple reasonable answers to this question.) (5 points)

ml.plotClassify2D(None,X,z)
2.     
Run k-means on the first two features of the Iris data, for k = 2, k = 5, and k = 20. Try multiple (at least 5) different initializations for each k, and check to see whether they find the same solution; if not, pick the one with the best score. For the best clustering for each candidate k, create a plot with the data colored by assignment, and the cluster centers. You can plot the points colored by cluster assignments z using . (You will need to also plot the cluster centers yourself.) (15 points)

ml.cluster.agglomerative
3.    Run agglomerative clustering on the first two features of the Iris data, first using single linkage and then again using complete linkage, using the algorithms implemented infrom

cluster.py
). For each linkage criterion, plot the data colored by their assignments to 2, 5, and 20 clusters. (Agglomerative clustering does not require an initialization, so there is no need to run methods multiple times.) (15 points)

4.    Briefly discuss similarities and differences in the outputs of the agglomerative clustering and k-means algorithms. (5 points)

Problem 2: EigenFaces (50 points)
In class, we discussed how PCA has been applied to faces, and showed some example results. Here, you’ll explore this representation yourself. First, load the data and display a few faces to better understand the data format:

1

2

3

4

X = np.genfromtxt("data/faces.txt", delimiter=None) # load face dataset plt.figure()

# pick a data point i for display

img = np.reshape(X[i,:],(24,24)) # convert vectorized data to 24x24 image patches plt.imshow( img.T , cmap="gray",vmin=0,vmax=255)              # display image patch; you may have to

, squint
5 →

1.    Subtract the mean of the face images (X0 = X −µ) to make your data zero-mean. (The mean should be of the same dimension as a face, 576 pixels.) Plot the mean face as an image. (5 points)

scipy.linalg.svd
2.    Useto take the SVD of the data, so that

3.    For K = 1, . . . , 10, compute the approximation to X0 given by the first K eigenvectors (or eigenfaces):

np.mean( (X0                     Xˆ0)**2 )
                       Xˆ0 = W[:, : K] · Vh[: K, :].                         For each K, compute the mean squared error in the SVD’s approximation,

                                               −                         . Plot these MSE values as a function of K. (10 points)

2*np.median(np.abs(W[:,j]))
4.    Display the first three principal directions of the data, by computing µ+α V[j,:] and µ-α V[j,:], where α is a scale factor (we suggest setting α to, to match the scale of the data).

These should be vectors of length 242 = 576, so you can reshape them and view them as “face images” just like the original data. They should be similar to the images in lecture. (10 points)

5.    Choose any two faces and reconstruct them using the first K principal directions, for K = 5, 10, 50, 100. Plot the reconstructed faces as images. (5 points)

6.    Methods like PCA are often called “latent space” methods, as the coefficients can be interpreted as a new geometric space in which the data are represented. To visualize this, choose 25 of the faces, and display them as images with the coordinates given by their coefficients on the first two principal components:

idx = ...                                                                           # pick some data (randomly or otherwise); an array of integer indices

import mltools.transforms coord,params = ml.transforms.rescale( W[:,0:2] ) # normalize scale of "W" locations plt.figure(); for i in idx:

# compute where to place image (scaled W values) & size loc = (coord[i,0],coord[i,0]+0.5, coord[i,1],coord[i,1]+0.5)

                       img = np.reshape( X[i,:], (24,24) )                                             # reshape to square

plt.imshow( img.T , cmap="gray", extent=loc, vmin=0,vmax=255 ) # draw each image

                    plt.axis( (-2,2,-2,2) )                                                                           # set axis to a reasonable scale
1

2

3

4

5

6

7

8

9

 
10

11

This plot is a good way to gain intuition for what the PCA latent representation captures. (10 points)