Short note: K-means clustering

K-means is the most popular partitioning clustering algorithm. It divides n objects into k clusters so that each object belongs to the cluster with the nearest mean (the centroid), and the sum of squared errors SSE = Σᵢ Σ_{x∈Cᵢ} ‖x − cᵢ‖² is minimised.

Algorithm

1. Choose k and select k initial centroids (random objects).
2. Repeat
   a. Assign each object to the nearest centroid
      (Euclidean distance) -> k clusters.
   b. Recompute each centroid as the mean of its cluster.
3. Until no object changes cluster (centroids stable).

Example

Points 1, 2, 9, 10, with k = 2 and initial centroids 1 and 2. Iteration 1: clusters {1} and {2, 9, 10}, so the new centroids are 1 and 7. Iteration 2: point 2 moves to the first cluster, giving {1, 2} and {9, 10} with centroids 1.5 and 9.5. Iteration 3 changes nothing, so these are the final clusters.

Features

• Simple and fast: complexity O(n·k·t) for t iterations, and t is usually small.
• Needs k in advance; depends on the initial centroids; converges to a local optimum (so it is run several times).
• Sensitive to noise and outliers because the mean is used; finds convex, spherical clusters of similar size; works only on numeric data.