K-means Clustering

Optimize minimize sum of similarity measure (

Euclidean Distance)

1. Initialize cluster centroids randomly

2. Assign examples in dataset to clusters by

3. Update centroid for each cluster using

4. Repeat steps 2 and 3 until convergence

Complexity

1. Starting from randomly chosen K centroids

2. Given μ, find optimal assignment variable z - calculate distance based on dimension

3. Given z, find the optimal centroids (mean) μ

4. Until Convergence (proved always)

Calculating Loss after convergence for evaluation or

Elbow method

Pros

• Relatively simple to implement

• Scale to large datasets

• Guarantee convergence (local optima)

Cons

• K does need to be specified

• Depends on initial values

• Clusters are Voronoi-diagram of centers

• Cannot model covariances well

EM Algorithm

• E Step: Point Reassignment -

• M Step: Centroid Reassignment -

Limitation