# K-Means Clustering

K-Means Clustering is an unsupervised machine learning algorithm that partitions n observations into k clusters, each assigned to the nearest cluster centroid, minimizing within-cluster variance.

K-Means Clustering is a method of vector quantization, originally from signal processing, that partitions a set of observations into k clusters, where each observation belongs to the cluster with the nearest mean, known as the cluster centroid. This results in a partitioning of the data space into Voronoi cells. The algorithm is widely used in [machine-learning](https://www.wikiprompt.org/wiki/machine-learning) for tasks such as customer segmentation, image compression, and pattern recognition, and it is a foundational technique in [artificial-intelligence](https://www.wikiprompt.org/wiki/artificial-intelligence) and data analysis.

The objective of k-means is to minimize the within-cluster sum of squares (WCSS), which is the sum of squared Euclidean distances between each point and its cluster centroid. This is equivalent to minimizing the pairwise squared deviations of points within the same cluster. However, k-means minimizes squared Euclidean distances, not regular Euclidean distances; the latter would require solving the more difficult Weber problem. For Euclidean distance minimization, alternatives like k-medians or k-medoids are more appropriate.

The problem of finding the optimal k-means clustering is computationally difficult (NP-hard), but efficient heuristic algorithms converge quickly to a local optimum. The most common approach is Lloyd's algorithm, which iteratively assigns points to the nearest centroid and then updates centroids to the mean of assigned points. This iterative refinement is similar to the expectation-maximization algorithm used for Gaussian mixture models, but k-means tends to find clusters of comparable spatial extent, while Gaussian mixtures allow different shapes.

## Algorithm and Implementation

The standard k-means algorithm begins with an initial set of k centroids, which can be chosen randomly or using methods like k-means++ to improve convergence. The algorithm repeats two steps until convergence: assignment, where each observation is assigned to the cluster with the nearest centroid, and update, where each centroid is recalculated as the mean of all points in its cluster. Convergence is typically detected when assignments no longer change or when the WCSS improvement falls below a threshold.

Several variants exist, including mini-batch k-means for large datasets and spherical k-means for text data. The choice of k is often determined using the elbow method, silhouette analysis, or gap statistic. The algorithm's time complexity is roughly O(n*k*d*i), where n is the number of observations, d is the dimensionality, and i is the number of iterations.

## Relationship to Other Methods

K-means is an unsupervised algorithm, meaning it does not require labeled data. It has a loose relationship to the k-nearest neighbor (k-NN) classifier, a supervised technique. Applying the 1-nearest neighbor classifier to the cluster centers obtained by k-means classifies new data into existing clusters; this is known as the nearest centroid classifier or Rocchio algorithm. This connection highlights how unsupervised clustering can support supervised tasks.

K-means is also related to Gaussian mixture models (GMMs). Both use cluster centers to model data, but GMMs allow clusters to have different shapes and sizes, while k-means assumes spherical clusters of similar variance. Consequently, k-means is simpler and faster but less flexible.

## Applications and Limitations

K-means is used across many domains. In [amazon-web-services](https://www.wikiprompt.org/wiki/amazon-web-services) and [google-cloud](https://www.wikiprompt.org/wiki/google-cloud), it is a common tool for analyzing user behavior and optimizing resource allocation. In [computer-vision](https://www.wikiprompt.org/wiki/computer-vision) (not in slug list, but relevant), it is used for image segmentation and color quantization. In marketing, it segments customers based on purchasing patterns. The algorithm is also a building block for more complex methods, such as [deep-learning](https://www.wikiprompt.org/wiki/deep-learning) feature extraction and [generative-ai](https://www.wikiprompt.org/wiki/generative-ai) data preprocessing.

However, k-means has limitations. It requires the number of clusters k to be specified in advance, which is not always known. It is sensitive to initial centroid selection, though k-means++ mitigates this. It assumes clusters are convex and isotropic, which may not hold for real-world data. Outliers can distort centroids, and the algorithm may converge to local optima. Despite these issues, its simplicity and efficiency make it a popular choice.

## Historical Context and Development

The k-means algorithm was first proposed by Hugo Steinhaus in 1956 and later refined by Stuart Lloyd in 1957 at Bell Labs (though not published until 1982). The name "k-means" was coined by James MacQueen in 1967. Since then, numerous improvements have been developed, including k-means++ for better initialization and the mini-batch variant for scalability. The algorithm remains a staple in [machine-learning](https://www.wikiprompt.org/wiki/machine-learning) curricula and is implemented in major libraries such as scikit-learn and TensorFlow.

## See Also

- [machine-learning](https://www.wikiprompt.org/wiki/machine-learning)
- [artificial-intelligence](https://www.wikiprompt.org/wiki/artificial-intelligence)
- [deep-learning](https://www.wikiprompt.org/wiki/deep-learning)
- [data-augmentation](https://www.wikiprompt.org/wiki/data-augmentation)

---
Source: https://www.wikiprompt.org/wiki/k-means
License: CC BY-SA 4.0 (https://creativecommons.org/licenses/by-sa/4.0/)
Last updated: 2026-09-09T02:00:34.785227+00:00