k-Means Clustering
An unsupervised learning algorithm that partitions data into k clusters by iteratively assigning points to the nearest centroid.
k-means is the most widely used clustering algorithm: it partitions a dataset into k groups such that each point belongs to the cluster whose center (centroid) is nearest. It is unsupervised — the data come without labels, and the algorithm discovers structure rather than learning from examples. Applications include customer segmentation, image compression (representing colors by k representative palette colors), document grouping, and the first exploratory step in almost any data analysis.
The algorithm, due to Lloyd (1957, published 1982), alternates two steps. Initialization picks k starting centroids. The assignment step assigns each point to the nearest centroid. The update step recomputes each centroid as the mean of its assigned points. The two steps repeat until assignments stop changing. The objective minimized is the sum of squared distances from points to their centroids — within-cluster variance — and each iteration is guaranteed not to increase it, so k-means always converges, though to a local optimum that depends on initialization.
initialize k centroids
repeat:
assign each point to the nearest centroid
recompute each centroid as the mean of its points
until assignments are stable
Practical issues are well understood. The result depends on initialization: the k-means++ heuristic (1994) seeds centroids far apart and dramatically improves both speed and solution quality, and running the algorithm several times with different seeds and keeping the best objective is standard. Choosing k is a modeling decision — the elbow method plots within-cluster variance against k and looks for a bend, but there is no universally correct answer. Clusters are assumed to be roughly spherical and of similar size, because the objective is based on Euclidean distance; data with elongated or nested shapes need other methods (DBSCAN, hierarchical clustering).
k-means is fast — O(n·k·d) per iteration — which is why it scales to enormous datasets, including via mini-batch variants. Its relationship to k-nearest neighbors is instructive: k-NN is supervised and uses labeled neighbors for prediction, while k-means is unsupervised and finds groupings without labels; both are built on the same geometry of distances, and both serve as indispensable baselines in machine learning.
Tags
clustering k-means machine learning unsupervised learning