K-Means Algorithm

Most clustering tutorials start with a definition. This one starts with a failure.

A retail analytics team ran k-means on their customer data: 80,000 records, six behavioral features. The algorithm returned three clusters. The clusters looked reasonable in a scatter plot. Someone put them in a PowerPoint. A director signed off on a segmentation strategy built around those three groups. Six months later, the campaign performance was flat. When a data scientist finally dug into it, the problem was obvious: two of the “clusters” were actually the same type of customer, split down the middle by the algorithm because the spending data hadn’t been scaled before clustering. The age variable, ranging from 18 to 75, was getting crushed by annual spend values in the tens of thousands. K-means had been dividing customers by how much they spent and nothing else.

The algorithm wasn’t broken. It was being used wrong.

That’s the gap this article fills. You’ll get a clear explanation of how the k-means algorithm works step by step, with the why behind each step rather than just the procedure. You’ll get working Python code. And you’ll get the section no other tutorial includes: the three specific situations where k-means will give you wrong answers, and what to use instead.

What Is the K-Means Algorithm? (The One-Minute Version)

K-means is an unsupervised machine learning algorithm that groups unlabeled data points into clusters based on similarity. You tell it how many groups you want (that’s the k), and it figures out which points belong together by minimizing the distance between each point and its cluster’s center.

Simple enough. But here’s a texture detail that changes how you think about it.

Stuart Lloyd developed the mathematical foundation of this algorithm at Bell Labs in 1957. He wasn’t building a machine learning tool. He was working on signal quantization: the problem of representing a continuous analog signal using a limited set of discrete values. His goal was compression, not clustering. The algorithm was designed for signals that follow smooth, symmetric distributions in low-dimensional space.

That origin matters because every limitation of k-means flows directly from it. The algorithm assumes your clusters are roughly spherical. It assumes they’re about the same size. It assumes your data lives in a space where Euclidean distance is a meaningful similarity measure. Those were reasonable assumptions for 1957 Bell Labs signal data. They’re often wrong for 2026 business data.

Knowing where the algorithm came from is the fastest way to know when not to use it.

How the K-Means Algorithm Works — Step by Step

There are four steps. Each one is straightforward. The interesting part is what can go wrong at each step, and why.

Step 1: Choose k and Place Initial Centroids

You start by choosing k, the number of clusters you want. Then the algorithm randomly places k centroids (cluster centers) somewhere in your data space.

Honestly, this is where most of the trouble starts.

Random placement means two runs of k-means on identical data can produce completely different clusters. Try it yourself: run KMeans(n_clusters=3) on the same dataset twice without setting a random seed, and you’ll get different results. Sometimes dramatically different. This isn’t a bug. It’s a direct consequence of random initialization, and it’s one of the most misunderstood aspects of the algorithm.

The Forgy initialization method picks k actual data points at random as starting centroids, which tends to spread them out. The Random Partition method assigns each data point to a random cluster first, then computes the centroid of each. Both are still random, and both can land your algorithm in a bad starting position.

You’ll see how to fix this in a moment. For now: the starting position of your centroids has a huge impact on where you end up.

Step 2: Assign Each Point to Its Nearest Centroid

Once the centroids are placed, every data point gets assigned to whichever centroid is closest. Distance is almost always Euclidean: the straight-line distance between two points in your feature space.

Geometrically, what this creates is a Voronoi diagram. Each centroid “owns” a region of space, and every point in that region gets assigned to that centroid. It’s a useful way to picture the assignment step: you’re carving the data space into territories, one per cluster.

Step 3: Recalculate the Centroids

After every point is assigned to a cluster, the algorithm recalculates each centroid as the mean of all the points currently in that cluster. The centroid moves to the middle of its current group.

This is the step that makes k-means iterative. Move the centroids, reassign the points, move the centroids again. Each iteration, the algorithm is minimizing the WCSS: the Within-Cluster Sum of Squares, which is the total squared distance between every point and its assigned centroid.

Here’s what most articles don’t tell you: k-means will always converge. The WCSS decreases or stays flat with every iteration, so the algorithm will always stop. But “always converges” does not mean “always finds the best solution.” It converges to a local minimum, not necessarily the global minimum. Whether that local minimum is any good depends heavily on where the centroids started.

Step 4: Repeat Until Convergence

The algorithm keeps repeating Steps 2 and 3 until either (a) the centroids stop moving, meaning no data point switches clusters between iterations, or (b) it hits the maximum number of iterations you’ve set.

At that point, you have your clusters. Whether they’re good clusters is a separate question, and one you need to answer before trusting the output.

The Local Minimum Problem (And How to Fix It)

Let’s make the local minimum problem concrete.

Picture a dataset with three natural groups: three obvious blobs. Now imagine placing two of your initial centroids inside the same blob by chance. The algorithm won’t fix that mistake by jumping one centroid across to the lonely third blob. It’ll just divide the crowded blob into two sub-clusters and misassign points from the other two. You end up with three clusters that don’t match the three real groups at all.

Two fixes exist. Use both.

Fix 1: K-Means++ Initialization

David Arthur and Sergei Vassilvitskii introduced k-means++ in 2007. Instead of placing all centroids randomly, k-means++ places the first centroid randomly, then chooses each subsequent centroid with probability proportional to its squared distance from the nearest already-chosen centroid. In plain terms: it deliberately spreads the starting centroids apart, making the “two centroids in the same blob” problem far less likely.

And the result is faster convergence and meaningfully better cluster quality. The downside is a slightly more expensive initialization step, but in practice you’ll almost never notice it.

Fix 2: The n_init Parameter

Sklearn’s KMeans runs the entire algorithm n_init times, each time with a different random initialization, and keeps the run that produced the lowest WCSS. The default is n_init=10 in many sklearn versions.

So when you run KMeans(n_clusters=3), you’re not running the algorithm once. You’re running it ten times and keeping the best result. That’s why sklearn’s output is more reliable than a bare-bones single-run implementation.

Always use init=’k-means++’ and keep n_init at 10 or higher for any dataset you actually care about.

How to Choose k: Three Methods Compared

Picking k is the hardest part of k-means. The algorithm can’t tell you how many clusters exist in your data; you have to decide, and then it will find k clusters whether or not k is the right number.

Here are three methods, ranked from most accessible to most statistically rigorous.

The Elbow Method

Plot the WCSS on the y-axis against different values of k on the x-axis. As k increases, WCSS drops: more clusters means points are closer to their centroids. At some point, adding another cluster stops making a meaningful difference. That bend in the curve is the “elbow,” and it’s your suggested k.

In practice though, the elbow is often unclear. Real-world datasets frequently produce gradual bends rather than sharp ones. When that happens, the elbow method gives you a range rather than an answer. Use it as a starting point, not a final decision.

import matplotlib.pyplot as plt

from sklearn.cluster import KMeans

wcss = []

for i in range(1, 11):

    kmeans = KMeans(n_clusters=i, init='k-means++', random_state=42)

    kmeans.fit(X_scaled)

    wcss.append(kmeans.inertia_)

plt.plot(range(1, 11), wcss)

plt.title('The Elbow Method')

plt.xlabel('Number of clusters')

plt.ylabel('WCSS (Inertia)')

plt.show()

The Silhouette Score

The silhouette score measures, for each data point, how similar it is to its own cluster compared to the next-closest cluster. Scores range from -1 to +1.

A score near +1 means the point fits well in its cluster and is far from neighboring clusters. Near 0 means the point is on the boundary between two clusters. Negative means it might actually belong somewhere else.

As a rough guide: scores above 0.5 suggest reasonable clustering, and above 0.7 suggests strong separation. The advantage over the elbow method is that silhouette scores can be computed for each value of k and compared directly. The k with the highest average silhouette score is usually your best choice.

from sklearn.metrics import silhouette_score

# Calculate silhouette score for k=3

kmeans = KMeans(n_clusters=3, init='k-means++', random_state=42)

cluster_labels = kmeans.fit_predict(X_scaled)

silhouette_avg = silhouette_score(X_scaled, cluster_labels)

print(f"The average silhouette_score is : {silhouette_avg:.4f}")

The Gap Statistic

The gap statistic is the most statistically rigorous of the three. It compares your actual WCSS to the expected WCSS from a random reference distribution: basically, it asks whether your clustering is meaningfully better than random. The k that maximizes the gap between real clustering and random clustering is the answer.

It’s computationally expensive because it requires generating many random reference datasets. For most work, the silhouette score gets you close enough without the cost. But if you’re doing publishable research, the gap statistic is worth the extra compute time.

[VISUAL: Side-by-side comparison: elbow curve, silhouette scores, and gap statistic, all computed on the same dataset]

Python Implementation: Two Ways

The sklearn Version (What You’ll Actually Use)

This is the implementation you want in production. Sklearn handles k-means++ initialization, multiple restarts, and convergence checks internally.

python

import numpy as np

import matplotlib.pyplot as plt

from sklearn.cluster import KMeans

from sklearn.preprocessing import StandardScaler

from sklearn.datasets import make_blobs

# Generate sample data

X, _ = make_blobs(n_samples=500, n_features=2, centers=3, random_state=42)

# Step 1: Always scale your data before clustering

scaler = StandardScaler()

X_scaled = scaler.fit_transform(X)

# Step 2: Fit k-means

# init='k-means++' uses smart initialization

# n_init=10 runs the algorithm 10 times, keeps the best result

# random_state=42 makes results reproducible

kmeans = KMeans(

    n_clusters=3,

    init='k-means++',

    n_init=10,

    max_iter=300,

    random_state=42

)

kmeans.fit(X_scaled)

# Step 3: Get results

labels = kmeans.labels_

centroids = kmeans.cluster_centers_

inertia = kmeans.inertia_

print(f"WCSS (inertia): {inertia:.2f}")

print(f"Cluster sizes: {np.bincount(labels)}")

# Step 4: Visualize

plt.scatter(X_scaled[:, 0], X_scaled[:, 1], c=labels, cmap='viridis', alpha=0.6)

plt.scatter(centroids[:, 0], centroids[:, 1], c='red', marker='X', s=200, label='Centroids')

plt.title('K-Means Clustering Result')

plt.legend()

plt.show()

Three parameters most tutorials never explain:

n_init=10 runs the algorithm 10 times with different starting centroids and keeps the run with the lowest WCSS. Setting it to 1 makes your results unreliable.

init=’k-means++’ uses smart centroid placement instead of random. It’s almost always better and the extra initialization cost is negligible.

random_state=42 makes results reproducible. Without it, two identical calls can return different clusters.

From Scratch in 25 Lines (So You Understand What’s Happening)

Don’t use this in production. It runs once, uses random initialization, and has no protection against local minima. But reading through it once makes the sklearn version much easier to reason about.

python

import numpy as np

def kmeans_scratch(X, k, max_iter=100, seed=42):

    np.random.seed(seed)

    # Randomly pick k starting centroids from the data

    idx = np.random.choice(len(X), k, replace=False)

    centroids = X[idx].copy()

    for _ in range(max_iter):

        # Assign each point to the nearest centroid

        distances = np.linalg.norm(X[:, None] - centroids[None, :], axis=2)

        labels = np.argmin(distances, axis=1)

        # Recalculate centroids as the mean of assigned points

        new_centroids = np.array([X[labels == i].mean(axis=0) for i in range(k)])

        # Stop if centroids didn't move

        if np.allclose(centroids, new_centroids):

            break

        centroids = new_centroids

    return labels, centroids

# Usage

X_example = np.random.randn(200, 2)

labels, centroids = kmeans_scratch(X_example, k=3)

The np.allclose check is the convergence test. When centroids stop moving, the algorithm stops. That’s all convergence means.

Data Scaling: The Step Everyone Skips

Back to the story at the start. The retail team’s clusters were wrong because they didn’t scale their data first.

Here’s why scaling matters. Say you’re clustering customers using two features: age (ranging from 20 to 65) and annual spend (ranging from $500 to $200,000). Euclidean distance treats both features equally in the formula. But in practice, a difference of 45 years in age produces a distance of 45. A difference of $199,500 in spend produces a distance of 199,500.

The spend variable will dominate cluster assignment completely. Age becomes irrelevant. You’re not clustering by customer behavior; you’re clustering almost entirely by spend level, regardless of what you intended.

The fix is one line: StandardScaler().fit_transform(X). This rescales each feature to a mean of 0 and a standard deviation of 1, so a “large” difference in age carries the same weight as a “large” difference in spend.

Always scale before clustering. No exceptions.

K-Means Applications: What They Actually Look Like in Practice

Five application areas come up in every k-means tutorial. Most get described in one vague sentence. Here’s what they look like when you’re actually building them.

Customer Segmentation Using RFM

The most common business use. An e-commerce company clusters customers by Recency (days since last purchase), Frequency (number of orders), and Monetary value (total spend). K-means on those three features typically produces distinct groups: high-value loyalists, occasional buyers, and dormant accounts. Each group gets a different re-engagement campaign. Worth noting: k-means doesn’t tell you what the groups mean. You have to look at each centroid’s values and interpret them yourself.

Image Compression and Color Quantization

This is the application closest to the algorithm’s original purpose. Take an image with millions of unique pixel colors. Run k-means with k=16, grouping pixels by their RGB values. Replace every pixel with the color of its nearest centroid. You’ve gone from millions of colors to 16, which is roughly how early GIF compression worked and how Photoshop’s “Index Color” mode works today. The image looks nearly identical to the human eye but stores as a fraction of the original size.

Document Clustering

Google News doesn’t hand-label each article. It uses clustering to group similar stories together. Feed articles into a text vectorizer like TF-IDF, run k-means on the resulting vectors, and similar articles end up in the same cluster. The challenge: text data is high-dimensional, which is one of the cases where k-means starts to struggle. More on that in the next section.

Anomaly Detection as a Baseline

K-means isn’t designed for anomaly detection, but it’s often used as a first-pass filter. Points that are very far from any centroid get flagged as potential outliers. It’s not as precise as dedicated anomaly detection methods, but it’s fast and gives you something to start with before investing in more complex approaches.

Medical Image Segmentation

Researchers use k-means to identify tissue boundaries in MRI scans by clustering pixels by intensity value. A brain scan clustered into k=4 groups might separate white matter, gray matter, cerebrospinal fluid, and background. The clusters aren’t anatomically perfect; k-means doesn’t know what brain tissue is. But they give radiologists a useful starting point for annotation.

When NOT to Use K-Means

Most articles on k-means get this section exactly wrong. They bury the limitations in a brief bullet list at the end, after you’ve already decided to use the algorithm. The limitations should come first, because they determine whether k-means is the right tool at all.

Three situations where k-means will reliably produce wrong results.

Failure 1: Non-Spherical or Non-Convex Clusters

K-means draws cluster boundaries based on distance to centroids. That works perfectly when your clusters are round blobs. It fails completely when they’re not.

Classic examples: two crescent shapes facing each other, or a ring of points surrounding a central cluster. K-means will cut right through both shapes because it can only create convex boundaries. It will assign points in the outer ring to the same cluster as the inner points, based purely on centroid distance.

What to use instead: DBSCAN (Density-Based Spatial Clustering of Applications with Noise). DBSCAN identifies clusters as dense regions separated by lower-density areas. It can find crescents, rings, and irregular shapes that k-means completely misses. And you don’t need to specify k in advance.

Failure 2: Clusters of Very Different Sizes or Densities

K-means implicitly assumes all clusters are roughly the same size and density. When one cluster has 5,000 points and another has 50, the algorithm tends to split the large cluster to balance assignments, pulling centroids toward each other.

And outliers cause real damage here. A single extreme point far from any cluster will pull a centroid toward it, distorting the whole cluster assignment. K-means averages all points in a cluster to find the centroid; one extreme value moves the mean a lot.

What to use instead: Gaussian Mixture Models (GMM). GMM is the “soft” version of k-means. Instead of hard assignment where each point belongs to exactly one cluster, GMM assigns each point a probability of belonging to each cluster. It handles clusters of different sizes and densities because it models each cluster as a Gaussian distribution with its own mean and covariance. If you need not just which cluster a point belongs to, but how confident that assignment is, GMM is the right tool.

Failure 3: High-Dimensional Data

Euclidean distance breaks down in high-dimensional spaces. This is known as the curse of dimensionality. As the number of features grows, the distances between all points start to converge: everything becomes roughly equidistant from everything else. When that happens, “nearest centroid” stops being a meaningful concept, and k-means clusters start reflecting noise rather than real structure.

A rough threshold: k-means tends to work well with up to around 10 to 15 features. Beyond that, dimensionality reduction first is almost always a better path.

What to do: PCA first, then k-means. Run Principal Component Analysis to compress your features into a smaller set of components that still capture most of the variance. Then run k-means on those components. Sklearn’s PCA and KMeans chain together cleanly:

python

from sklearn.decomposition import PCA

from sklearn.cluster import KMeans

from sklearn.pipeline import Pipeline

pipeline = Pipeline([

    ('pca', PCA(n_components=10)),

    ('kmeans', KMeans(n_clusters=5, init='k-means++', n_init=10, random_state=42))

])

pipeline.fit(X_high_dim)

labels = pipeline.named_steps['kmeans'].labels_

K-Means Advantages and Disadvantages

Feature	Advantage	When It Becomes a Problem
Simplicity	Easy to understand; one library call in Python	Oversimplification hides real structure in complex data
Speed	Scales to millions of points; time complexity roughly O(n·k·i·d)	Slows with high k, high dimensions, or many iterations
Interpretability	Centroid values are human-readable cluster summaries	Meaningless for non-convex shapes; centroid may not represent any real data point
Hard assignment	Every point belongs to exactly one cluster	Wrong for data where points genuinely overlap between groups
Requires k upfront	Forces you to state your hypothesis about structure	You’re committed to k clusters whether or not k is the right number

One thing worth saying plainly: k-means is not a black box that tells you the truth about your data. It will always return k clusters. Whether those clusters reflect real patterns or just the algorithm’s geometric assumptions is something you have to validate, with silhouette scores, domain knowledge, and some visual inspection of the results.

Frequently Asked Questions

Closing

K-means has been running inside production systems for close to 70 years. It’s fast, it’s simple, and it works well enough often enough that it became the default starting point for clustering problems across industries.

But “default starting point” is the right framing. Not “default answer.”

The algorithm was built for signal data at Bell Labs, and it carries those assumptions into every problem you handle. When your data fits those assumptions, compact and roughly spherical clusters of similar size in a manageable number of dimensions, k-means is genuinely hard to beat. When your data doesn’t fit them, the algorithm will still return k clusters. They just won’t mean what you think they mean.

Run the decision flowchart before you run the algorithm. Scale your data. Use k-means++. Check your silhouette scores. And if the elbow curve looks more like a ski slope than a bent arm… try DBSCAN.