K-means clustering: grouping data points around centroids
K-means is an unsupervised learning algorithm that partitions unlabeled data into a chosen number of clusters by minimizing the distance between each point and its cluster's centroid. It iteratively assigns points to the nearest centroid, recomputes centroids, and repeats until convergence. The algorithm is simple and scales well to large datasets, but it requires the number of clusters to be set in advance and is sensitive to initialization and outliers.
What k-means clustering is
K-means is an unsupervised learning algorithm that partitions unlabeled data points into clusters. It is an exclusive or hard clustering method, meaning each data point belongs to exactly one cluster. As IBM's k-means overview explains, the algorithm iteratively groups similar data points based on the distance between their centroids.
Clustering discovers patterns in data without predefined labels. According to NVIDIA's glossary entry, k-means is used in applications such as customer segmentation, document clustering, image compression, and anomaly detection.
How k-means works
The algorithm begins with a user-chosen number of clusters k. It then randomly selects k centroids, assigns each data point to the nearest centroid, recomputes each centroid as the mean of its assigned points, and repeats this process. As Google's k-means overview describes, the steps continue until assignments no longer change, and for large datasets the algorithm can stop early based on other criteria.
Because the initial centroids are random, different runs can produce different results. Running k-means multiple times and keeping the output with the best quality metrics is a common strategy to mitigate this variability.
The objective is to minimize the sum of squared distances from each point to its assigned centroid. This is achieved by the iterative reassignment and centroid update steps.
Evaluating and tuning k-means
K-means aims to minimize the inertia, or within-cluster sum of squares, which measures how coherent the clusters are. The scikit-learn clustering guide states that inertia assumes clusters are convex and isotropic, which is not always the case, and that lower values are better, with zero being optimal.
The number of clusters k must be specified in advance, and the algorithm scales well to large numbers of samples. The same guide notes that k-means can be seen as a special case of Gaussian mixture models with equal covariance per component.
In high-dimensional spaces, Euclidean distances tend to become inflated, an instance of the curse of dimensionality. Running PCA before clustering can help alleviate this issue, as noted in the same source.
The table below compares common clustering algorithms from the scikit-learn overview.
Advantages and limitations
K-means is relatively simple to implement, scales to large datasets, always converges, and allows warm-starting of centroid positions. These advantages are listed on the Google advantages and disadvantages page.
A primary disadvantage is that k must be chosen manually, and results depend on the initial centroid values. The same page notes that for low k, running several times and picking the best result helps, while higher k needs better seeding methods.
Outliers can drag centroids or get their own cluster, and the algorithm struggles with clusters of varying sizes and densities. Removing or clipping outliers before clustering is recommended, and generalization can handle some non-uniform cluster shapes.
Use cases
Clustering is a fundamental technique in unsupervised machine learning. The Google clustering introduction describes clustering use cases, similarity measures, and evaluation of clustering results.
Because of its simplicity and efficiency, k-means is often the first algorithm tried when grouping unlabeled data. It is well suited to large datasets and serves as a baseline in many clustering tasks.
| Method | Key parameter | Scalability | Typical use case |
|---|---|---|---|
| K-Means | Number of clusters | Very large n_samples, medium n_clusters with MiniBatch | General-purpose, even cluster size, flat geometry |
| Affinity propagation | Damping, sample preference | Not scalable with n_samples | Many clusters, uneven size, non-flat geometry |
| Mean-shift | Bandwidth | Not scalable with n_samples | Many clusters, uneven size, non-flat geometry |
| Spectral clustering | Number of clusters | Medium n_samples, small n_clusters | Few clusters, even size, non-flat geometry |
| Ward hierarchical | Number of clusters or distance threshold | Large n_samples and n_clusters | Many clusters, possibly connectivity constraints |
| Agglomerative | Number of clusters, linkage type, distance | Large n_samples and n_clusters | Many clusters, non-Euclidean distances |
| DBSCAN | Neighborhood size | Very large n_samples, medium n_clusters | Non-flat geometry, uneven sizes, outlier removal |
| HDBSCAN | Minimum cluster membership, minimum point neighbors | Large n_samples, medium n_clusters | Non-flat geometry, uneven sizes, outlier removal, hierarchical |
| OPTICS | Minimum cluster membership | Very large n_samples, large n_clusters | Non-flat geometry, uneven sizes, variable density |
| Gaussian mixtures | Many | Not scalable | Flat geometry, density estimation |
| BIRCH | Branching factor, threshold, optional global clusterer | Large n_clusters and n_samples | Large dataset, outlier removal, data reduction |
| Bisecting K-Means | Number of clusters | Very large n_samples, medium n_clusters | General-purpose, even size, flat geometry, no empty clusters |
Frequently asked questions
What does k-means minimize during clustering?
K-means minimizes the inertia, or within-cluster sum of squares, which is the sum of squared distances between each point and its cluster centroid, as explained in the scikit-learn guide.
Why does k-means produce different results across runs?
Initial centroids are chosen randomly, so different starting points can lead to different final clusters. Running the algorithm multiple times and selecting the result with the best quality metrics is recommended.
What are typical applications of k-means?
Common uses include customer segmentation, document clustering, image compression, and anomaly detection, as listed in the NVIDIA glossary.
What are the main drawbacks of k-means?
The user must specify k in advance, results depend on initialization, outliers can distort centroids, and the algorithm assumes roughly spherical clusters of similar size.
How does the curse of dimensionality affect k-means?
In high-dimensional spaces, distance-based measures become less effective. Using PCA to reduce dimensionality or spectral clustering can help, as described in the Google advantages page.