Description
Theme: K-means algorithm
Question 1 (Problem 6 – Final Exam )
Consider the K-means algorithm. Let K = 2 and let D be a dataset consisting of four data points
with D = {0, 0.5, 0.5 + ∆, 1.5 + ∆}, where ∆ ≥ 0 is a problem parameter. All data points lie on the
real line.
(a) For this part, let ∆ = 0.5 and initialize K-means by initializing the two cluster centers at
µ1[0] = 1 and µ2[0] = 2. Run K-means till convergence. For each iteration l until convergence,
describe your set membership {B1[l], B2[l]} and cluster centers {µ1[l], µ2[l]}. Make sure you
identify the final values of the cluster centers and set membership at convergence.
(b) For this part, find a condition that ∆ must satisfy, such that ∆ has a small positive value,
and K-means (initialized in the same manner as in part (a), i.e., µ1[0] = 1 and µ2[0] = 2)
converges to a different solution from that obtained in part (a). In your solution, describe,
(i) What is this condition on ∆ and explain your reasoning/derivation.
(ii) As in part (a), run the cluster algorithm, describe the values of cluster centers and set
membership for each iteration until convergence.
1
