K-means

Optimize minimize sum of similarity measure (

Euclidean Distance)

1. Initialize cluster centroids $\mu_1 \dots \mu_k \in R^m$ randomly

2. Assign examples in dataset $S$ to clusters $c_1\dots c_k$ by $c(x_i) = \argmin_j||x_i - \mu_j||^2$

3. Update centroid $\mu_j$ for each cluster $c_j$ using $\mu_j :=\frac{\sum_{x_i\in c_j}x_j}{|c_j|}$

4. Repeat steps 2 and 3 until convergence

Complexity

1. Starting from randomly chosen K centroids

2. Given μ, find optimal assignment variable z $O(KND)$ - calculate distance based on dimension

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

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

Limitation