K-Means Clustering

K-means partitions data into k clusters by alternately assigning points to the nearest center and recomputing centers.

The objective

K-means partitions n points into k clusters, minimizing the within-cluster sum of squared distances to each cluster's mean (centroid). You choose k in advance. The algorithm is a workhorse for its speed and simplicity, though it assumes roughly spherical, similarly sized clusters.

Lloyd's algorithm

• Initialize k centroids (k-means++ spreads them out for a better start).
• Assign each point to its nearest centroid.
• Recompute each centroid as the mean of its assigned points.
• Repeat the last two steps until assignments stop changing.

from sklearn.cluster import KMeans
km = KMeans(n_clusters=4, n_init=10, random_state=0)
labels = km.fit_predict(X)
centers = km.cluster_centers_

Choosing k

Since k is not learned, pick it with the elbow method (plot inertia versus k and look for the bend) or the silhouette score (how well points fit their cluster versus the next-nearest). Neither is definitive; domain knowledge should confirm the count.

Limits

K-means converges only to a local optimum, so run it several times with different seeds. It struggles with elongated or nested shapes, uneven cluster sizes, and outliers, which drag centroids. When clusters are non-convex or of unknown number, prefer DBSCAN or hierarchical clustering. Always scale features first, since k-means uses Euclidean distance.

It is part of the broader clustering toolkit for finding structure in unlabeled data.

The objective it minimizes, total within-cluster variance, always decreases or stays flat at each iteration, which guarantees convergence but only to a local minimum that depends on the starting centroids. The k-means++ initialization mitigates this by choosing initial centers that are spread apart with probability proportional to squared distance, so a good start is often worth more than extra iterations.