Taking the first three values (2, 3, 6) as initial centroids, K-Means converges to the clusters {2, 3}, {6, 8, 9, 12} and {15, 18, 22}, with centroids 2.5, 8.75 and 18.33.
K-Means algorithm
- Choose \(k\) and pick \(k\) initial centroids (randomly or the first \(k\) points).
- Assign every point to the nearest centroid (Euclidean distance; in 1-D, \(|x - m|\)).
- Recompute each centroid as the mean of the points in its cluster.
- Repeat steps 2–3 until no point changes cluster (centroids stop changing).
It minimises the within-cluster sum of squared distances \(\sum_{i}\sum_{x\in C_i}(x - m_i)^2\).
Solution for {2, 3, 6, 8, 9, 12, 15, 18, 22}, \(k = 3\):
| Iteration | Centroids used | C1 | C2 | C3 | New centroids |
| 1 | 2, 3, 6 | {2} | {3} | {6, 8, 9, 12, 15, 18, 22} | 2, 3, 12.86 |
| 2 | 2, 3, 12.86 | {2} | {3, 6} | {8, 9, 12, 15, 18, 22} | 2, 4.5, 14 |
| 3 | 2, 4.5, 14 | {2, 3} | {6, 8, 9} | {12, 15, 18, 22} | 2.5, 7.67, 16.75 |
| 4 | 2.5, 7.67, 16.75 | {2, 3} | {6, 8, 9, 12} | {15, 18, 22} | 2.5, 8.75, 18.33 |
| 5 | 2.5, 8.75, 18.33 | {2, 3} | {6, 8, 9, 12} | {15, 18, 22} | no change |
Sample checks: in iteration 2, point 8 is 5 from 3 but 4.86 from 12.86, so it stays in C3; in iteration 4, point 12 is 4.33 from 7.67 but 4.75 from 16.75, so it moves to C2.
Final clusters: C1 = {2, 3}, C2 = {6, 8, 9, 12}, C3 = {15, 18, 22}.
Advantages: simple and easy to implement; fast, about \(O(nkt)\) for \(n\) points, \(k\) clusters and \(t\) iterations; scales to large data; works well for compact, roughly spherical clusters.
Limitations: \(k\) must be chosen in advance; the result depends on the initial centroids (starting from 2, 12, 22 here gives {2, 3, 6}, {8, 9, 12, 15}, {18, 22}); sensitive to outliers and noise; works only with numeric data where a mean exists; poor for clusters of very different sizes, densities or non-convex shapes.