Clustering K-means

Given the samples X1 = {1, 0}, X2 = {0, 1}, X3 = {2, 1}, and X4 = {3, 3}. 

Suppose that samples are randomly clustered into two clusters C1 = {X1, X3} and C2 = {X2, X4}.

a)      Apply one iteration of K-means partitional clustering algorithm, and find a new distribution of samples in clusters. What are the new centroids? How you can prove that the new distribution of samples is better than the initial one?

b)      What is the change in a total square error?

c)      Apply the second iteration of K-means algorithm and discuss the changes in clusters.

Answer:

a)         M1 = { (1+2)/2, (0+1)/2} = {1.33, 0.5}

            M2 = { (0+3)/2,(1+3)/2} = { 1.33, 2}

within cluster variation after initial random distribution of samples

e₁^{2 =}  =.33² + .5² + .66² + .5² = 1.0445

e₂² =1.33² + 1² + 1.66² + 1² = 6.5245

E² = e₁²  + e₂²    = 7.569

Redistribution :-

d(M1,X1) = {( 1-1.33)2 + (.5)2 } ½  = .599 

d(M2,X1)= {(1-1.33)2 + (2)2 } ½ = 2.02

d(M1,X2) = {( 1.33)2 + (.5)2 } ½  = 1.42 

d(M2,X2)= {(1.33)2 + (1)2 } ½ = 1.66

d(M1,X3) = {( 2-1.33)2 + (.5)2 } ½  = .6828 

d(M2,X3)= {(.66)2 + (1)2 } ½ = 1.198

d(M1,X4) = {( 3-1.33)2 + (3-.5)2 } ½ = 3.00 

d(M2,X4)={(3-1.33)2 + (3-2)2 }1/2 =1.937

implies:            X1 Î C1

                                    X2 Î C1

                                    X3 Î C1

                                    X4 Î C2

New cluster are: C1 = { X1, X2, X3} and C2 = {X4}

And  new centroid s are:

M1 = (1, 0.66)

M2 = (3, 3)

b)         e₁²= [0²+ .66²+ 1²+ .33² + 1²+ .33²] = 2.65                

e₂² = 0

E² = e₁² + e₂²    = 2.65

Total error is significantly smaller than the one in the first iteration. We may conclude that the distribution of samples is better than initial one.

c)         After second iteration there are no changes in clusters and their centroids. Therefore, we may conclude that C1 = {X1, X2, X3} and C2 = {X4} is the final clustering result.