Exercises

Exercises

Conceptual

Exercise 1 Conceptual

We have six points with the following pairwise Euclidean distances.

	2	3	4	5	6
1	0.3	0.4	0.7	0.9	0.8
2		0.5	0.8	1.0	0.9
3			0.45	0.75	0.7
4				0.3	0.25
5					0.2

1. Apply hierarchical clustering with complete linkage. Draw the dendrogram with the merges at the correct heights.
2. Do the same with single linkage. Where do the two differ.
3. Cut the complete linkage dendrogram to get two clusters. Which points are together.

Exercise 2 Conceptual

About k-means.

1. Show that step (b) of the algorithm, moving each centroid to the mean, is the choice that minimizes \(W_k\) for fixed assignments.
2. Argue that the algorithm converges in a finite number of steps.
3. Why does it converge to a local and not a global minimum.
4. After convergence, is every point in exactly one cluster. Is every cluster non-empty.

Exercise 3 Conceptual

Explain in two sentences each.

1. Why does cross-validation on \(W_k\) not work for choosing \(k\).
2. Why is k-means a special case of a Gaussian mixture model.
3. Why can DBSCAN find clusters that k-means cannot.
4. Why does standardizing the data change the result of every method on this page.

Applied

Exercise 4 Applied

Cluster the iris data.

1. Load it and drop the class column. Standardize the four measurements.
2. Run k-means for \(k = 2\) to \(8\) and plot \(W_k\) and the silhouette score.
3. Which \(k\) would you choose from each of the two plots.
4. Compare the clustering at your chosen \(k\) to the true species with a confusion matrix. Note that the cluster numbers are arbitrary.

Exercise 5 Applied

The same data with hierarchical clustering.

1. Build the dendrogram with complete linkage and Euclidean distance.
2. Cut it to get three clusters and compare to the species.
3. Repeat with single, average and Ward linkage. Do the results change qualitatively.
4. Repeat without standardizing. How much does it matter here.

Exercise 6 Applied · optional

Cluster the MNIST digits with k-means and ten clusters.

1. Show five images from each cluster.
2. Compute the confusion matrix against the true labels.
3. Which digits end up in the same cluster, and can you say why from the images.

Exercise 7 Applied · optional

Generate data with no cluster structure at all, for example 500 points uniform on a square.

1. Run k-means for \(k = 2\) to \(8\) and plot the silhouette score.
2. Run it on data with three genuine clusters and plot the same curve.
3. Compare the two curves. How would you tell, from the curve alone, that the first data set has no clusters.