Description

Yao Xie
1 Clustering. [100 points total. Each part is 25 points.]
[a-b] Given N data points xn(n = 1,…,N), K-means clustering algorithm groups them into K clusters by minimizing the distortion function over {rnk,µk}
N K
J = XXrnkkxn − µkk2,
n=1k=1
where rnk = 1 if xn belongs to the k-th cluster and rnk = 0 otherwise.
(a) Prove that using the squared Euclidean distance kxn − µkk2 as the dissimilarity function and minimizing the distortion function, we will have
.
That is, µk is the center of k-th cluster. [5 pts]
(b) Prove that K-means algorithm converges to a local optimum in finite steps. [5 pts]
[c-d] In class, we discussed bottom-up hierarchical clustering. For each iteration, we need to find two clusters {x1,x2,…,xm} and {y1,y2,…,yp} with the minimum distance to merge. Some of the most commonly used distance metrics between two clusters are:
• Single linkage: the minimum distance between any pairs of points from the two clusters, i.e.
i=1min,…,m kxi − yjk
j=1,…,p
• Complete linkage: the maximum distance between any parts of points from the two clusters, i.e.
i=1max,…,m kxi − yjk
j=1,…,p
• Average linkage: the average distance between all pair of points from the two clusters, i.e.

1
(c) When we use the bottom up hierarchical clustering to realize the partition of data, whichof the three cluster distance metrics described above would most likely result in clusters most similar to those given by K-means? (Suppose K is a power of 2 in this case). [5 pts]
(d) For the following data (two moons), which of these three distance metrics (if any) wouldsuccessfully separate the two moons? [5 pts]

2