Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP4702/COMP7703 - Machine Learning

Homework W5 - Clustering

Questions

1.  (2 marks) k-means clustering can be viewed as a method for compression via a set of codebook vectors.  In the book [Bishop 2006], he discusses the compression acheived for the images shown in his Fig. 9.3 (see also this week’s lecture). Using the same calculation method, how many bits would be required to transmit one of his images for (K = 6) and what is the corresponding compression ratio?

2.  (3 marks) The k-means algorithm performs optimisation on an objective function which Alpaydin calls the “reconstruction error”.  [Bishop 2006] (p.424) calls it a “distortion measure”.  In Fig.9.2, Bishop shows the reduction of error as the k-means algorithm runs on the Old Faithful dataset.  If this experiment was repeated with the cluster centres starting at different points, describe the shape of the error curve (approx. 1-2 sentences). In particular, would the new curve start and/or finish at the same points and why (approx. 1-2 sentences)?

3.  (2 marks) In Fig.7.5 of Alpaydin, the Euclidean distance metric has been used (single-link hierarchical clustering).  How would the dendrogram change if the city-block (aka Manhattan) distance metric was used instead?

4.  (4 marks) The python scikit-learn toolbox contains implementations of many different clustering algorithms.  A nice illustration comparing some of the algorithms on some 2-D datasets is shown here: https://scikit-learn.org/stable/modules/clustering.html

Think about why  these particular example datasets (i.e.  each row of subplots) might have been chosen for this illustration. Describe the most important properties of the datasets in rows 2, 4 and 6 (at most two sentences for each dataset).

5.  (3 marks) The method for initializing the k-means algorithm discussed in lectures (and in Alpaydin) is known as the Forgy  approach.  [Pena 1999] compares this with three other techniques.  Refer to the top two plots in Figure 5 of this paper (available on the course website). Based on these results only, would you use the RANDOM or the Forgy (FA) technique?  Explain why in no more than 4 sentences.