How does K-Means Clustering work?

K-Means Clustering is a Machine Learning method that automatically splits data into K groups, where each item belongs to the group whose center is closest to it. It finds these groups on its own, without anyone telling it the correct answers.

In this blog, we will learn about how K-Means Clustering works. We will also see what clustering means, what a centroid is, the four steps that K-Means repeats with a full example with numbers, how to pick the right value of K using the elbow method, the common problems like bad starting points and unscaled data, and where it works well and where it fails.

We will cover the following:

• What is clustering?
• What is K-Means Clustering?
• What is a centroid?
• How do we measure closeness?
• How does K-Means work? The four steps
• A step-by-step example with numbers
• Seeing it in code
• How to choose the value of K?
• Common problems and how to fix them
• Where K-Means works well and where it fails

I am Amit Shekhar, Founder @ Outcome School, I have taught and mentored many developers, and their efforts landed them high-paying tech jobs, helped many tech companies in solving their unique problems, and created many open-source libraries being used by top companies. I am passionate about sharing knowledge through open-source, blogs, and videos.

I teach AI and Machine Learning at Outcome School.

Let's get started.

What is clustering?

Clustering is the task of putting similar items into the same group, and different items into different groups.

Each group is called a cluster. Clustering is unsupervised learning, which means we give the machine only the data, with no correct answers, and it must find the groups on its own.

Let's say a shop has 10,000 customers. For each customer, the shop knows two things: how often they visit and how much they spend. The shop wants to understand its customers better. But nobody has labeled the customers as "big spenders" or "rare visitors".

If we cluster the customers, we can get groups like below:

• Customers who visit often and spend a lot.
• Customers who visit often but spend little.
• Customers who visit rarely but spend a lot when they come.

Now, the shop can send different offers to each group. This is called customer segmentation, and it is one of the most common uses of clustering.

To learn Supervised and Unsupervised Learning and the rest of the Machine Learning Fundamentals, check out our AI and Machine Learning Program at Outcome School.

What is K-Means Clustering?

K-Means Clustering is a clustering method that divides the data into exactly K clusters, where each cluster is represented by its center point, and every item belongs to the cluster with the nearest center.

K-Means = K + Means.

• K is the number of clusters we want. We choose it before we start. If we want 3 groups, K = 3.
• Means is the plural of mean, and a mean is an average. Each cluster's center is calculated as the average of all the items in that cluster.

What is a centroid?

A centroid is the center point of a cluster. It is the average position of all the items in that cluster.

Suppose we have three houses on a straight road at positions 2, 4, and 9 kilometers from the start.

Centroid = (2 + 4 + 9) / 3 = 5

So, the centroid of these three houses is at 5 kilometers. If we want to build one common shop for these three houses, position 5 is the balance point.

When each item has two numbers, like (visits, spending), we take the average of each number separately. For example, the centroid of (1, 2) and (3, 6) is ((1 + 3) / 2, (2 + 6) / 2) = (2, 4).

How do we measure closeness?

K-Means keeps asking one question: "Which centroid is this item closest to?" So, we need a way to measure distance.

K-Means uses the normal straight-line distance that we measure with a ruler. It is called the Euclidean distance.

We have a detailed blog on Cosine Similarity that compares it with Euclidean Distance and explains when to use each one.

For two points (x1, y1) and (x2, y2), it is calculated as below:

Distance = sqrt((x2 - x1)^2 + (y2 - y1)^2)

For example, the distance between (1, 1) and (4, 5) is:

Distance = square root of ((4 - 1)^2 + (5 - 1)^2)
         = square root of (9 + 16)
         = square root of 25
         = 5

Smaller distance means the two points are more similar.

How does K-Means work? The four steps

Now that we have learned about clusters, centroids, and distance, it's time to learn how K-Means actually works.

K-Means follows four steps:

Step 1: Choose K. Decide how many clusters we want.

Step 2: Place K centroids. Put K starting centroids somewhere. The simplest way is to pick K random items from the data and use them as the starting centroids.

Step 3: Assign every item to its nearest centroid. For each item, calculate the distance to every centroid, and put the item in the cluster of the closest one.

Step 4: Move each centroid to the center of its cluster. For each cluster, calculate the average of all the items inside it. That average becomes the new centroid.

Then, we repeat Step 3 and Step 4 again and again. We stop when the items stop changing their clusters. At that point, the centroids also stop moving. We say that the algorithm has converged, which means it has settled down.

   Choose K
      |
      ↓
   Place K centroids
      |
      ↓
 +--> Assign each item to the nearest centroid
 |    |
 |    ↓
 |    Move each centroid to the average of its items
 |    |
 |    ↓
 |    Did any item change its cluster?
 |    |                 |
 |   Yes                No
 |    |                 |
 +----+                 ↓
                       Stop

Let's think of it like a party. Suppose there are K snack tables placed randomly in a hall. Every guest walks to the nearest table. Then, each table is moved to the middle of the guests standing around it. Now, some guests find that another table is nearer, so they walk to it. The tables move again. After a few rounds, nobody needs to switch, and every table sits in the middle of its own crowd.

This is how K-Means works.

Planning your move into AI?

No matter which tech domain you work in today, with your effort, you can transition to these roles:

• AI Engineer
• Forward Deployed Engineer
• AI Agent Engineer
• Harness Engineer
• Voice AI Engineer
• AI Architect
• LLM Engineer
• LLM Inference Engineer
• Gen AI Engineer
• MLOps Engineer
• ML Engineer
• Deep Learning Engineer

Our AI and Machine Learning Program at Outcome School takes you there.

A step-by-step example with numbers

The best way to learn this is by taking an example. We have 6 points, and we want K = 2 clusters.

A = (1, 1)    B = (2, 1)    C = (1, 2)
D = (8, 8)    E = (9, 8)    F = (8, 9)

  y
 9 |                       F
 8 |                       D  E
 7 |
 . |
 2 |  C
 1 |  A  B
   +---------------------------- x
      1  2  .  .  .  .  .  8  9

Just by looking, we can see two groups. But the computer cannot "look". It must use the four steps.

Round 1: We pick the starting centroids.

For the sake of understanding, let's say we start with a bad choice: we pick A and B as the two starting centroids. Both are in the bottom-left corner.

Centroid 1 = (1, 1)
Centroid 2 = (2, 1)

Round 1: We assign each point to its nearest centroid.

So, Cluster 1 has A and C. Cluster 2 has B, D, E, and F.

Here, we can notice that B, which clearly belongs with A and C, has landed in the wrong cluster. K-Means will fix this on its own.

Round 1: We move the centroids.

Centroid 1 = average of A, C       = ((1 + 1) / 2, (1 + 2) / 2)
           = (1, 1.5)

Centroid 2 = average of B, D, E, F = ((2 + 8 + 9 + 8) / 4, (1 + 8 + 8 + 9) / 4)
           = (6.75, 6.5)

Centroid 2 has moved a lot, towards the top-right group.

Round 2: We assign each point again.

Now, B has moved to Cluster 1. The mistake is fixed.

Round 2: We move the centroids again.

Centroid 1 = average of A, B, C = ((1 + 2 + 1) / 3, (1 + 1 + 2) / 3) = (1.33, 1.33)
Centroid 2 = average of D, E, F = ((8 + 9 + 8) / 3, (8 + 8 + 9) / 3) = (8.33, 8.33)

Round 3: We assign each point again.

A, B, and C are still closest to Centroid 1. D, E, and F are still closest to Centroid 2. No point changed its cluster.

So, K-Means stops. Our final clusters are:

Cluster 1: A, B, C    with centroid (1.33, 1.33)
Cluster 2: D, E, F    with centroid (8.33, 8.33)

Even with a bad start, K-Means found the two natural groups in just a few rounds.

A quick note for you

No matter which tech domain you work in, get familiar with these topics:

• LLM
• RAG
• MCP
• Agent
• Fine-tuning
• Quantization

We put it all together in one video:

AI Engineering Explained: LLM, RAG, MCP, Agent, Fine-Tuning, and Quantization

No need to stop reading - bookmark it and watch later when you get time. Future you will thank you.

Now, let's get back to the topic.

Seeing it in code

Now, let's see the same example in Python using the scikit-learn library.

import numpy as np
from sklearn.cluster import KMeans

points = np.array([[1, 1], [2, 1], [1, 2],
                   [8, 8], [9, 8], [8, 9]])

kmeans = KMeans(n_clusters=2, n_init=10, random_state=0)
kmeans.fit(points)

print("Group of each point:", kmeans.labels_)
print("Centroids:", kmeans.cluster_centers_.round(2).tolist())
print("New point [2, 2] goes to group:", kmeans.predict([[2, 2]]))

Here, we have done the following:

• We have created our 6 points.
• n_clusters=2 sets K = 2.
• n_init=10 tells K-Means to run 10 times with different starting centroids and keep the best result. We will see why this matters soon.
• random_state=0 fixes the random choices, so that we get the same result every time.
• fit runs the four steps until the clusters stop changing.
• labels_ gives the cluster number of each point, and cluster_centers_ gives the final centroids.
• predict puts a new point into the cluster with the nearest centroid.

This will print the following:

Group of each point: [1 1 1 0 0 0]
Centroids: [[8.33, 8.33], [1.33, 1.33]]
New point [2, 2] goes to group: [1]

Here, we can see that A, B, and C are in one group, and D, E, and F are in the other. The centroids are exactly what we calculated by hand. The cluster numbers 0 and 1 are just names. They have no meaning on their own.

How to choose the value of K?

Till now, we have chosen K ourselves. But in real data, we do not know how many groups exist. Now, the question is: how do we pick K?

First, we need a way to measure how good the clusters are. K-Means uses a number called inertia. Inertia is the sum of the squared distances of every item from its own centroid. Smaller inertia means the items are packed tightly around their centroids.

But, if we keep increasing K, the inertia always goes down. If K is equal to the number of items, every item is its own centroid, and the inertia becomes 0. But that is useless.

So, here comes the Elbow Method to the rescue. We run K-Means for K = 1, 2, 3, and so on, and note the inertia each time.

from sklearn.datasets import make_blobs
from sklearn.cluster import KMeans

X, _ = make_blobs(n_samples=300, centers=3, random_state=42)

for k in range(1, 7):
    kmeans = KMeans(n_clusters=k, n_init=10, random_state=0).fit(X)
    print(f"K={k}  inertia={kmeans.inertia_:.0f}")

Here, make_blobs creates 300 sample points that naturally form 3 groups. We pretend that we do not know this, and we try K from 1 to 6. For each K, inertia_ gives us the inertia of the final clusters.

This will print the following:

K=1  inertia=20402
K=2  inertia=5763
K=3  inertia=567
K=4  inertia=497
K=5  inertia=426
K=6  inertia=361

Let's draw it:

Inertia
20402 |  *
      |
      |
 5763 |       *
      |
  567 |            *----*----*----*
      +--+----+----+----+----+----+--- K
         1    2    3    4    5    6
                   ^
                 elbow

Here, we can see that the inertia drops a lot from K = 1 to K = 2, and again from K = 2 to K = 3. After K = 3, adding more clusters helps very little. The curve bends like an elbow at K = 3. So, K = 3 is a good choice, and the data really had 3 groups.

Note: In real data, the elbow is not always this clear. Another popular way is the Silhouette Score, which checks how close each item is to its own cluster compared to the nearest other cluster. A higher score means better separated clusters. And sometimes, K comes from the business need, like "we want 4 customer groups for 4 offers".

Stay updated: Subscribe to our newsletter to get our latest AI and Machine Learning blogs straight to your inbox.

Common problems and how to fix them

Most of the time, we do mistakes while using K-Means because of the following problems.

Problem 1: Bad starting centroids.

K-Means always settles down, but it does not always find the best clusters. If the starting centroids are very unlucky, it can get stuck in a poor result. This is called getting stuck in a local minimum, which means a result that looks best nearby but is not the best overall.

Solution: Use a better start called K-Means++. It picks the first centroid at random, and then picks each next centroid far away from the ones already picked. This spreads the starting centroids out. Also, run K-Means many times with different starts and keep the result with the lowest inertia. In scikit-learn, K-Means++ is the default, and n_init controls how many times it runs.

Problem 2: Features on different scales.

Suppose one feature is age, from 18 to 70, and another is yearly income, from 2,00,000 to 50,00,000. The income numbers are so big that the distance is decided almost fully by income. Age gets ignored.

Solution: Scale the features before clustering, which means bringing all of them to a similar range. A common way is StandardScaler in scikit-learn, which makes every feature have an average of 0 and a similar spread.

Problem 3: Outliers.

An outlier is an item that is very far from all the others, like one customer who spends 100 times more than everyone. Since centroids are averages, one outlier can pull a centroid towards itself.

Solution: Find and remove clear outliers before clustering, or use a method that is less affected by them.

Where K-Means works well and where it fails

K-Means works well when:

• The groups are roughly round, like blobs.
• The groups are of similar size.
• We have a rough idea of how many groups we want.
• The data is large and we need speed. K-Means is simple and fast.

K-Means fails when:

• The groups have strange shapes, like two moons or rings inside rings. K-Means always draws straight boundaries between centroids, so it cuts such shapes in the wrong way.
• The groups have very different sizes or very different spreads.
• The data is full of outliers.

For such cases, other clustering methods like DBSCAN, which finds groups based on how crowded an area is, work better.

Some real-world uses of K-Means are:

• Grouping customers for marketing.
• Grouping similar news articles or documents.
• Reducing the number of colors in an image, by grouping similar colors and replacing each one with its centroid color.
• Finding unusual items, which are the ones far from every centroid.

We have a detailed blog on Approximate Nearest Neighbor (ANN) Search that covers how vector search groups vectors into clusters to find similar items fast.

Now we must have understood how K-Means Clustering works.

Frequently Asked Questions

What is K-Means++?

K-Means++ is a better way to pick the starting centroids. It picks the first centroid at random, and then picks each next centroid far away from the ones already picked. This spreads the starting centroids out and lowers the chance of getting stuck in a poor result. In scikit-learn, K-Means++ is the default.

Does K-Means always find the best clusters?

No. K-Means always settles down, but it does not always find the best clusters. With very unlucky starting centroids, it can get stuck in a local minimum, which is a result that looks best nearby but is not the best overall. Running it many times with different starts and keeping the result with the lowest inertia helps.

What is inertia in K-Means?

Inertia is the sum of the squared distances of every item from its own centroid. Smaller inertia means the items are packed tightly around their centroids. Inertia always goes down as K increases, so we use it with the Elbow Method to pick K instead of simply choosing the K with the lowest inertia.

Why should we scale features before using K-Means?

We should scale features because K-Means groups items by distance. If one feature has much bigger numbers than another, like yearly income compared to age, the distance is decided almost fully by that feature. Scaling, for example with StandardScaler, brings all features to a similar range so that each one counts.

That's it for now.

Thanks

Amit Shekhar
Founder @ Outcome School

You can connect with me on:

• X
• LinkedIn
• GitHub

Follow Outcome School on:

• X
• YouTube
• LinkedIn
• GitHub

Read all of our high-quality blogs here.