K Means Clustering Explained: How It Works, With Python Code
K means clustering groups unlabelled data into k clusters by repeatedly assigning points to the nearest centre and moving each centre to the middle of its points. Learn the algorithm, code it from scratch in NumPy, choose k with the elbow method and silhouette score, avoid bad starts with k-means++, and see where it fails.
- K means clustering is unsupervised: it finds groups without labels by minimising the squared distance from points to their cluster centre.
- Our from-scratch NumPy version recovered three customer segments in 3 iterations.
- Both the elbow method and the silhouette score (0.783) pointed to k = 3 on that data.
- On a harder six-cluster dataset, random starts found the best solution only 3 times in 10, while k-means++ found it 10 times in 10.
Customer segments, product categories, image colour palettes, groups of similar support tickets: many problems start with “these items fall into a few natural groups, but nobody has labelled them”. K means clustering is the classic algorithm for that job. It is fast, easy to understand and available in every data library, yet it has a few assumptions that, if ignored, give confident but meaningless clusters.
Every number below comes from code we ran with Python 3.13.6 and NumPy 2.5.5 on synthetic data generated with fixed seeds. We implemented k-means, k-means++ and the silhouette score ourselves; scikit-learn was not used. For the supervised cousin of this algorithm, see k nearest neighbors.
What is k-means clustering?
K-means partitions data into k groups. Each group is represented by its centroid, the average of its points. Every point belongs to the cluster whose centroid is nearest. The algorithm searches for centroids that make the total squared distance from points to their centroids as small as possible. That total is called inertia, or the within-cluster sum of squares.
The k-means algorithm step by step
- Choose k, the number of clusters.
- Initialise k centroids, for example by picking k random points.
- Assign each point to its nearest centroid.
- Update each centroid to the mean of the points assigned to it.
- Repeat steps 3 and 4 until the centroids stop moving or a maximum number of iterations is reached.
This loop, known as Lloyd’s algorithm, always converges, because each step can only lower the inertia. But it converges to a local minimum, which may not be the best possible clustering, a point we test below.
Our dataset: three customer segments
We generated 300 synthetic customers with two features: annual spend in thousands of rupees and store visits per month. They came from three hidden groups of 100 each: occasional low spenders (about 20 thousand and 2 visits), frequent mid spenders (60 thousand and 8 visits) and rare big spenders (110 thousand and 4 visits), with random spread around each centre.
K-means from scratch in NumPy
import numpy as np
def kmeans(X, k, seed=0, iters=100):
rng = np.random.default_rng(seed)
C = X[rng.choice(len(X), k, replace=False)] # random initial centroids
for i in range(iters):
d = ((X[:, None] - C[None]) ** 2).sum(-1) # squared distances, n x k
lab = np.argmin(d, axis=1) # assign to nearest
newC = np.array([X[lab == j].mean(0) if np.any(lab == j) else C[j]
for j in range(k)]) # move to the mean
if np.allclose(newC, C):
break
C = newC
inertia = ((X - C[lab]) ** 2).sum()
return C, lab, inertia, i + 1
Broadcasting computes all point-to-centroid distances at once, and the loop alternates assignment and update. The guard if np.any(lab == j) keeps a centroid in place if it ever ends up with no points, a corner case real implementations must handle. The version we ran also supports k-means++ initialisation, described below.
The result
k=3 centroids (spend, visits): [[20.5, 2.1], [61.2, 8.1], [110.1, 3.9]]
iterations: 3 inertia: 16909.9
cluster sizes: [102, 98, 100]
The algorithm found centroids almost exactly at the hidden centres, in only three iterations, and split the 300 customers into groups of 102, 98 and 100. Two customers on the border between the low and mid groups were assigned to the low group, which is expected when clusters overlap slightly. Each centroid is directly interpretable, a big reason k-means is popular for segmentation: “frequent mid spenders average 61,200 rupees a year over 8.1 visits a month”.
Inertia: what k-means minimises
Inertia is the sum of squared distances from each point to its centroid. Lower is tighter. It always decreases as k grows, because more centroids mean shorter distances, reaching zero when every point is its own cluster. That is why you cannot choose k by minimising inertia alone.
Choosing k with the elbow method
| k | Inertia |
|---|---|
| 1 | 424,788 |
| 2 | 100,629 |
| 3 | 16,910 |
| 4 | 13,721 |
| 5 | 9,278 |
| 6 | 6,252 |
Going from 1 to 2 clusters cut inertia by 76 percent, and from 2 to 3 by another 83 percent. After that, each extra cluster helped only a little. The “elbow” at k = 3 suggests three natural groups. On real data the elbow is often less obvious, so combine it with another measure and with domain sense.
Choosing k with the silhouette score
silhouette: k=2 0.690 | k=3 0.783 | k=4 0.675 | k=5 0.596
The silhouette score measures, for each point, how close it is to its own cluster compared with the nearest other cluster, from -1 (wrong cluster) to +1 (well separated). The average was highest at k = 3, agreeing with the elbow. Unlike inertia, the silhouette score does not automatically improve with more clusters, which makes it a fairer guide. Our implementation computed all pairwise distances, fine for 300 points but too slow for large datasets, where a sample is used instead.
Initialisation and k-means++
On our well-separated segments, every one of 10 random starts reached the same inertia of 16,910, so initialisation did not matter. To test a harder case we generated six clusters arranged in a grid and ran 10 seeds each way:
random init inertia: [2981, 555, 3091, 2803, 5610, 2805, 2819, 555, 3127, 555]
k-means++ inertia: [555, 555, 555, 555, 555, 555, 555, 555, 555, 555]
Random initialisation reached the best solution (inertia 555) only 3 times out of 10. The other runs got stuck with two centroids sharing one true cluster and another centroid covering two, giving inertia up to ten times worse. k-means++ picks the first centroid at random and each next one with probability proportional to its squared distance from the centroids chosen so far, spreading the starts out. It found the best solution in all 10 runs. Libraries also run several initialisations and keep the lowest inertia; scikit-learn uses k-means++ by default, according to its documentation.
Tip: always use k-means++ and run several initialisations, keeping the result with the lowest inertia. A single random start can quietly give you a poor clustering.
Feature scaling
K-means uses distances, so a feature with larger numbers dominates. In our data, spend ranged over about 100 units while visits ranged over about 10. Standardising both features (subtract the mean, divide by the standard deviation) changed the cluster of only 0.7 percent of customers, agreeing on 99.3 percent, because the groups differ strongly in spend anyway. On data where the important feature has the smaller scale, skipping scaling can produce completely different clusters, so standardise by default, then check whether it changes the story. The same lesson appeared in our KNN article.
Where k-means fails
# two concentric rings: radius 1 and radius 3, 300 points each
rings accuracy: 0.5
We generated two rings, one inside the other, and asked for two clusters. K-means scored 0.5, no better than a coin flip: it cut the picture into two halves, because it can only draw straight boundaries between centroids. K-means assumes clusters are roughly round, similar in size and similar in density. It struggles with:
- Rings, crescents and other non-convex shapes; use DBSCAN or spectral clustering.
- Clusters of very different sizes or spreads; consider Gaussian mixture models, which give each point a probability for every cluster instead of a hard label, much as the softmax function turns scores into probabilities.
- Outliers, which pull centroids away; remove them first or use k-medoids.
- Categorical data, where means are meaningless; use k-modes.
We did not run those alternatives here.
Assigning new points
new = np.array([[58, 7.5]])
C[np.argmin(((new - C) ** 2).sum(1))] # [61.2, 8.1] the frequent mid spender segment
Once trained, k-means can label a new customer instantly by finding the nearest centroid. That makes it practical for routing new tickets, tagging new products or assigning new users to a segment, with periodic retraining as data drifts.
How fast is k-means?
Each iteration costs roughly n times k times the number of features. Our plain NumPy version clustered 100,000 points with 8 features into 8 clusters, running the full 20 iterations we allowed, in 1.56 seconds. Optimised libraries are faster, and mini-batch k-means updates centroids from small random samples to handle millions of points.
Real-world uses of k-means
- Customer segmentation for marketing and pricing.
- Colour quantisation, reducing an image to k representative colours.
- Grouping documents by clustering their text embeddings, usually after normalising them so distance reflects cosine similarity.
- Vector search indexes, where inverted-file (IVF) indexes use k-means centroids to split millions of vectors into searchable buckets; see our vector database guide.
- Anomaly hints: points far from every centroid are worth a look.
Final thoughts
K means clustering is simple: assign points to the nearest centroid, move centroids to the mean, repeat. Our from-scratch version recovered three hidden customer segments in three iterations, and the elbow and silhouette methods agreed on k = 3. Use k-means++ with several restarts, scale your features, and remember that k-means sees the world as round blobs. When your clusters are rings or irregular shapes, reach for another algorithm.
Frequently asked questions
How does k means clustering work?
It picks k starting centroids, assigns every point to the nearest centroid, moves each centroid to the mean of its points, and repeats until the centroids stop moving.
How do I choose the number of clusters k?
Plot inertia for several values of k and look for the elbow where improvement slows, and compare silhouette scores, choosing the k with the highest average. Business meaning should also guide the choice.
Is k means supervised or unsupervised?
It is unsupervised. It needs no labels and finds groups purely from the structure of the data.
What is k-means++?
It is a smarter way to choose starting centroids that spreads them apart, choosing each new centroid with probability based on its distance from those already picked. It greatly reduces the chance of a poor local solution.
What is the difference between k means and KNN?
K means is unsupervised clustering that groups unlabelled data around k centroids. KNN is supervised and predicts the label of a new point from its k nearest labelled neighbours.
Keep learning
Need help with testing, WordPress or SEO?
We help teams ship better software and grow their sites. Tell us what you are working on and we will suggest a clear next step.