Explain the complete K-means algorithm. Discuss its objective function, convergence criterion, and major limitations.

Question

Accepted Answer

## K-means clustering

K-means partitions data into $K$ clusters by minimizing within-cluster squared distance:

$$J=\sum_{k=1}^{K}\sum_{x_i\in C_k}\lVert x_i-\mu_k\rVert^2$$

**Algorithm:** (1) choose $K$ initial centroids; (2) assign each point to the nearest centroid; (3) recompute each centroid as the mean of assigned points; (4) repeat assignment and update until assignments/centroids stop changing or a maximum iteration count is reached.

```mermaid
flowchart TD
A[Choose K and initialize centroids] --> B[Assign points to nearest centroid]
B --> C[Recompute cluster means]
C --> D{Converged?}
D -->|No| B
D -->|Yes| E[Return clusters]
```

Each iteration does not increase the objective, so the algorithm converges to a local optimum. Limitations: must choose K, sensitive to initialization and outliers, favors roughly spherical similarly scaled clusters, and requires numeric distance-compatible features.

K-means clustering

Similar questions

Pocketly on Android