The k-means algorithm and its objective
Clustering groups unlabelled points that are similar: market segments, similar news, DNA patterns, astronomical data.
K-means
pick K centroids μ₁..μ_K (randomly, from the training points)
repeat:
# 1. assign
for each point i: c⁽ⁱ⁾ = index of the closest centroid (min ‖x⁽ⁱ⁾ − μ_k‖²)
# 2. move
for each k: μ_k = mean of the points assigned to k
(If a cluster gets no points, drop it or re-initialize it.)
The cost it minimizes (distortion)
J(c, μ) = (1/m) Σᵢ ‖x⁽ⁱ⁾ − μ_c⁽ⁱ⁾‖²
Step 1 minimizes J over the assignments, step 2 over the centroids, so J never goes up. If it does, there's a
bug. It converges, but to a local minimum.
Initialization and choosing K
- Run k-means 50 to 1,000 times with different random starts; keep the lowest
J. (k-means++ picks spread-out starts and is the scikit-learn default.) - Choosing K: the elbow method is often unclear. Better: choose by the downstream purpose (T-shirt sizes S/M/L vs XS-XL: what does the business need?).
Going further
- K-means assumes round, similar-size clusters and needs scaled features. For odd shapes use DBSCAN; for soft assignments, Gaussian mixture models.
- Silhouette score is a common way to compare K when there's no downstream measure.