K-Means is a classic unsupervised learning algorithm that partitions
N data points into K clusters. The goal is to minimize inertia, also known as the within-cluster sum of squared distances.At a high level, K-Means is an alternating optimization algorithm. It repeatedly performs two steps: assign each point to its nearest centroid, then update each centroid as the mean of the points assigned to it.
Core Concepts
- Centroids: The current centers of the clusters.
- Assignment Step: Assign each point to the nearest centroid using Euclidean distance.
- Update Step: Recompute each centroid as the mean of its assigned points.
- Inertia: The sum of squared distances from each point to its assigned centroid.
- Convergence: The algorithm stops when centroids no longer move significantly, or when the maximum number of iterations is reached.
Implementation
K-Means alternates between two steps. First, in the assignment step, each point is assigned to the nearest centroid. Second, in the update step, each centroid is recomputed as the mean of all points assigned to that cluster.
I use squared Euclidean distance instead of the actual Euclidean distance because the square root does not change the nearest-centroid ordering, so we can avoid unnecessary computation during distance comparisons.
I also handle empty clusters by keeping the previous centroid. Finally, I check convergence by measuring how much the centroids moved after an iteration. If the total movement is below a small tolerance threshold, the algorithm stops early.
Algorithmic Complexity
Let
n be the number of data points, d be the number of features, K be the number of clusters, and T be the number of iterations.- Time Complexity:
In each iteration, every point is compared with every centroid. Each distance computation costs .
- Space Complexity:
We store one label per point and
K centroids, each with d dimensions.FAQs
Q1: How do you choose the optimal value of K?
Common approaches include the Elbow Method, Silhouette Score, and downstream task evaluation. In practice,
K is often chosen by balancing clustering quality with product or system constraints.Q2: Does K-Means always find the global optimum?
No. K-Means converges, but not necessarily to the global optimum. The objective is non-convex, so the final result depends heavily on centroid initialization. This is why production implementations often use multiple random restarts or K-Means++ initialization.
Q3: When does K-Means fail?
K-Means works best when clusters are roughly spherical, similarly sized, and separable under Euclidean distance. It performs poorly on non-convex clusters, highly imbalanced densities, strong outliers, and high-dimensional spaces where Euclidean distance becomes less meaningful.
Q4: Why is feature scaling important?
K-Means is distance-based, so features with larger numeric ranges dominate the distance calculation. Before running K-Means, features should usually be standardized or normalized.
Q5: How does K-Means handle outliers?
K-Means is sensitive to outliers because centroids are computed using the mean. Extreme points can pull centroids away from dense regions. In practice, we can remove outliers during preprocessing or use more robust alternatives such as K-Medoids.
- Author:Fan Luo
- URL:https://fanluo.me/article/k-means-clustering
- Copyright:All articles in this blog adopt BY-NC-SA agreement. Please indicate the source!
上一篇
Building the Release Gate: A/B Testing Framework Design
下一篇
Logistic Regression from Scratch