Understanding k-Means Clustering
k-means seeks a partition of the data into k groups minimizing the total squared distance from each point to the centre of its assigned group. Searching all possible partitions is infeasible, so the algorithm uses an iterative refinement that is simple and fast.
Two steps alternate. Given current centroids, assign every point to the nearest one. Given those assignments, recompute each centroid as the mean of its members. Each step can only decrease, or leave unchanged, the total within-cluster squared distance, and since there are finitely many possible assignments the procedure must terminate.
Convergence, however, is to a local optimum. A poor initialization can produce a genuinely bad partition, so implementations run the algorithm several times from different starting points and keep the best result. The k-means++ initialization scheme improves matters by spreading the initial centroids apart rather than choosing them uniformly at random.
The objective encodes strong assumptions that are easy to overlook. Minimizing squared Euclidean distance to a centre favours clusters that are round, similarly sized, and of similar density. Elongated, nested, or very unequally sized clusters are systematically mis-partitioned, and because the algorithm always returns exactly k clusters, it will happily split a single genuine group or merge two if k is wrong.
How to Calculate
minimize Σₖ Σ_{i ∈ Cₖ} ‖xᵢ − μₖ‖²
where
- Cₖ
- the set of observations assigned to cluster k
- μₖ
- the centroid of cluster k, the mean of its members
- ‖xᵢ − μₖ‖²
- squared Euclidean distance from a point to its centroid
Example of k-Means Clustering
For customer segmentation on spending and visit frequency with k = 3, the algorithm starts from three arbitrary centres, assigns each customer to the nearest, then moves each centre to the mean of the customers assigned to it, and repeats until assignments stop changing.
Choosing k is the harder problem. The elbow method plots total within-cluster variance against k: it always falls as k rises, but the rate of improvement typically drops sharply at some point, and that bend suggests a reasonable value. James and colleagues use exactly this kind of visual elbow criterion when deciding how many components to retain in principal component analysis.
The criterion is a heuristic, not a test. On data with no genuine cluster structure the algorithm still returns k tidy-looking groups, and the elbow may be ambiguous or absent. Cluster structure should be checked against domain knowledge rather than accepted because the algorithm produced it.
Frequently Asked Questions
How should k be chosen?
There is no purely statistical answer. The elbow method and the silhouette score are the usual heuristics, but the choice normally has to be informed by what the clusters will be used for. Different values of k can each be defensible for different purposes.
Why do different runs give different results?
The algorithm converges to a local optimum determined by its initial centroids. Different random starts land in different optima, which is why implementations default to multiple restarts and why k-means++ initialization is generally preferred.
Does the scale of features matter?
Very much. The objective is Euclidean distance, so a feature measured in large units dominates the distance calculation and effectively determines the clustering. Features should be standardized unless their relative scales are deliberately meaningful.
The Bottom Line
k-means is fast, simple, and guaranteed to converge, but only to a local optimum, and it imposes spherical, similarly sized clusters whether or not the data has them. Standardize the features, restart several times, and treat the resulting clusters as a hypothesis rather than a finding.