K-means is a widely used clustering algorithm that partitions a dataset into K clusters. The value of K must be selected before the algorithm is run. Initially, K centroids are selected, often using the K-means++ initialization method. Each observation is assigned to the nearest centroid according to a chosen distance measure, commonly Euclidean distance. The algorithm then recalculates each centroid as the mean of the observations assigned to that cluster. Assignment and centroid-update steps are repeated until the assignments stop changing, the centroids move very little, or a maximum number of iterations is reached. K-means is computationally efficient for many numerical datasets, but it can be sensitive to initialization, outliers, feature scales, and the selected value of K. It works best when clusters are reasonably compact and approximately spherical.
K-Means Clustering
K-means is a partition-based unsupervised learning algorithm that divides observations into a predefined number of clusters by minimizing within-cluster squared distances.
J = Σₖ₌₁ᴷ Σₓᵢ∈Cₖ ||xᵢ - μₖ||²
Explanation
Variables
| Symbol | Meaning |
|---|---|
J | K-means clustering objective |
K | Number of clusters |
Cₖ | Set of observations assigned to cluster k |
xᵢ | Observation i |
μₖ | Centroid of cluster k |
Example or application
A retailer applies K-means to customer purchase data with K = 3. The algorithm repeatedly assigns customers to the nearest of three centroids and updates those centroids until the groups stabilize.
Text
K-means repeatedly assigns observations to the nearest centroid and updates each centroid until the clustering stabilizes.
Key Points
K-means requires the number of clusters K in advance.
Each observation is assigned to its nearest centroid.
Centroids are updated using the mean of assigned observations.
The algorithm minimizes within-cluster squared distances.
K-means can converge to a local optimum.
Initialization and feature scaling influence the results.
Applications
Customer segmentation
Image color quantization
Document clustering
Market analysis
Exploratory data analysis
Learning Outcomes
Explain the K-means algorithm.
Describe centroid initialization and updating.
Understand the role of K.
Identify limitations of K-means clustering.
Practice Questions
What does K represent in K-means?
How is a centroid calculated?
Why does K-means repeat assignment and update steps?
What are the limitations of K-means?
Related Concepts
Clustering
Centroid
Euclidean Distance
K-Means++
Elbow Method
Common Mistakes
Assuming K-means automatically discovers the best number of clusters.
Ignoring feature scaling before calculating distances.
Using K-means without considering outliers.
Assuming every clustering run produces the same result.
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- MacQueen, J. (1967). Some Methods for Classification and Analysis of Multivariate Observations.
- Arthur, D., and Vassilvitskii, S. (2007). k-means++: The Advantages of Careful Seeding.
Suggest a correction or source · More in Artificial Intelligence & Machine Learning