Exercises

Exercises

Exercise 1

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

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

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.

Exercise 4

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.