K-Means Clustering
K-Means is an unsupervised machine learning algorithm that partitions a dataset into K clusters by iteratively assigning points to the nearest cluster centroid and recomputing centroids until the assignments stabilize.
Definition
K-Means is an unsupervised machine learning algorithm that partitions a dataset into K clusters by iteratively assigning points to the nearest cluster centroid and recomputing centroids until the assignments stabilize.
Overview
K-Means clustering groups unlabeled data into K clusters by minimizing the within-cluster sum of squared distances between points and their assigned cluster centroid. The algorithm typically begins by randomly initializing K centroids (with smarter initialization strategies like K-Means++ improving reliability), then alternates between two steps until convergence: an assignment step, where each data point is assigned to the nearest centroid, and an update step, where each centroid is recomputed as the mean of all points currently assigned to it. Because K-Means only guarantees convergence to a local optimum, results depend on initialization, and it's common practice to run the algorithm multiple times with different random starts and keep the best result by total within-cluster variance. Choosing the number of clusters K is itself a key decision, commonly guided by heuristics like the elbow method (plotting within-cluster variance against K and looking for a bend) or the silhouette score, which measures how well-separated clusters are. K-Means assumes clusters are roughly spherical and similarly sized in the feature space, and it is sensitive to the scale of input features, so standardizing or normalizing features before clustering is standard practice. It struggles with clusters of irregular shape, varying density, or significantly different sizes, where algorithms like DBSCAN (density-based) or Gaussian Mixture Models (which allow elliptical, probabilistic cluster assignment) tend to perform better. Despite these limitations, K-Means remains one of the most widely used clustering algorithms due to its simplicity, computational efficiency, and interpretability, making it a standard first tool for exploratory data analysis, customer segmentation, and as a preprocessing step (e.g. for vector quantization or initializing other algorithms) in larger machine learning pipelines.
Key Concepts
- Partitions data into K clusters by minimizing within-cluster squared distance
- Iterative two-step process: assign points to nearest centroid, then recompute centroids
- K-Means++ initialization improves reliability over pure random start points
- Only guarantees convergence to a local, not global, optimum
- Elbow method and silhouette score help choose the number of clusters K
- Assumes roughly spherical, similarly sized clusters
- Sensitive to feature scaling — standardization is standard preprocessing
- Computationally efficient and scales well to large datasets