K-Means Clustering — Empty Clusters from Outlier Injection

Every major tech company uses unsupervised learning to find patterns nobody explicitly told them to look for. Spotify groups listeners by taste without knowing your favourite genre upfront. Netflix segments users into viewer personas without anyone labelling them. Retailers spot buying behaviour clusters before a single marketing email is sent. K-Means is the workhorse behind most of these — fast, interpretable, and battle-tested across decades of real deployments.

The core problem K-Means solves is deceptively simple: given a pile of unlabelled data, can we automatically discover natural groupings? Traditional supervised learning needs labels — someone has to say 'this email is spam' before the model learns. K-Means asks no such thing. You hand it raw data points and a number K, and it figures out the rest by minimising the distance between each point and its assigned group's centre.

By the end of this article you'll understand exactly how the algorithm moves through its update loop, why your choice of K matters enormously, how to pick a good K using the Elbow Method, and how to avoid the two mistakes that silently wreck most beginners' results. You'll also have complete, runnable Python code you can drop into a real project today.

How K-Means Clustering Actually Works

K-means clustering partitions n observations into k clusters by minimizing within-cluster variance. Each observation belongs to the cluster with the nearest mean (centroid). The algorithm iterates between assignment and update steps until convergence — typically O(n·k·d·i) where i is iterations, often < 100.

Initialization matters: random seeds can produce different results. The standard algorithm (Lloyd's) converges to a local optimum, not global. Empty clusters occur when no points are assigned to a centroid — common with outlier injection or poor initialization. Reinitializing the empty centroid to a distant point is a practical fix.

Use k-means when you need fast, scalable clustering on numeric data with spherical cluster shapes. It's the default for customer segmentation, image compression, and anomaly detection baselines. But it assumes equal cluster sizes and fails on non-convex shapes — know when to reach for DBSCAN or hierarchical methods instead.

The K-Means Algorithm: Assignment and Update

K-Means works in two repeating steps. First, assign each data point to the nearest centroid (using Euclidean distance). Second, recompute each centroid as the mean of all points assigned to it. Stop when assignments no longer change or after a fixed number of iterations.

This is a coordinate descent optimisation — it converges to a local minimum of the within-cluster sum of squares (inertia). The guarantee? Only local, not global. Different initial centroids lead to different results.

Here's a pure Python implementation that makes the loop explicit:

import numpy as np

def k_means(X, K, max_iters=100):
    n_samples, n_features = X.shape
    centroids = X[np.random.choice(n_samples, K, replace=False)]
    for _ in range(max_iters):
        distances = np.linalg.norm(X[:, np.newaxis] - centroids, axis=2)
        labels = np.argmin(distances, axis=1)
        new_centroids = np.array([X[labels == k].mean(axis=0) for k in range(K)])
        if np.allclose(centroids, new_centroids):
            break
        centroids = new_centroids
    return labels, centroids

Choosing K: Elbow Method vs Silhouette Score

The number of clusters K must be specified upfront — this is K-Means' biggest limitation. The Elbow Method runs the algorithm for a range of K values and plots inertia vs K. The 'elbow' is where the rate of decrease flattens — that's your best K.

But inertia always decreases as K increases. At K=N, inertia reaches zero. That's why the Elbow Method is subjective. A more rigorous alternative is the Silhouette Score, which measures how similar a point is to its own cluster compared to other clusters. Higher is better. Scores range from -1 to 1.

Neither method is perfect. Structural ground truth rarely exists in unsupervised problems — choose K based on business interpretability as much as metrics.

from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score
import numpy as np

inertias = []
scores = []
K_range = range(2, 11)
for k in K_range:
    km = KMeans(n_clusters=k, random_state=42, n_init=10)
    km.fit(X)
    inertias.append(km.inertia_)
    scores.append(silhouette_score(X, km.labels_))

# Plot both side by side
import matplotlib.pyplot as plt
fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(12,4))
ax1.plot(K_range, inertias, 'bo-')
ax1.set_xlabel('K'); ax1.set_ylabel('Inertia'); ax1.set_title('Elbow Method')
ax2.plot(K_range, scores, 'ro-')
ax2.set_xlabel('K'); ax2.set_ylabel('Silhouette Score'); ax2.set_title('Silhouette Analysis')

Initialization Methods: Random vs k-means++

Initial centroids determine which local minimum the algorithm converges to. Pure random initialization can produce empty clusters or long convergence time. k-means++ spreads out the initial centroids by sampling probabilistically — points farther from existing centroids are more likely to be chosen.

scikit-learn's init='k-means++' (default) uses this. It's a small overhead for dramatically better results. Never use pure random (init='random') unless you're running many seeds and picking the best.

Other initialization strategies: furthest-first (rare), or using a small subset of data (e.g., k-means|| for distributed systems).

from sklearn.cluster import KMeans

# k-means++ (default, recommended)
km_pp = KMeans(n_clusters=5, init='k-means++', random_state=42)

# Random init (needs many runs)
km_rand = KMeans(n_clusters=5, init='random', n_init=20, random_state=42)

# Compare inertia after fitting
km_pp.fit(X)
km_rand.fit(X)
print(f"k-means++ inertia: {km_pp.inertia_}")
print(f"Random (20 runs) inertia: {km_rand.inertia_}")

Feature Scaling: The Hidden Assumption

K-Means uses Euclidean distance internally. If one feature has a range 0–1000 and another is 0–1, the first feature dominates the distance calculation. This is the number one silent mistake beginners make.

Standardise (z-score) or min-max scale all features before clustering. Use StandardScaler unless you know your features should have different importance.

Categorical features are a bigger problem — one-hot encoding introduces many binary dimensions, making distances meaningless. Consider Gower distance or use K-Prototypes (mixed-type clustering) instead.

from sklearn.preprocessing import StandardScaler
from sklearn.cluster import KMeans

scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

km = KMeans(n_clusters=3, random_state=42)
km.fit(X_scaled)

# To interpret centroids in original scale:
centroids_original = scaler.inverse_transform(km.cluster_centers_)

Common Pitfalls and How to Avoid Them

Beyond scaling and initialization, K-Means has three more traps: (1) Outliers — a single extreme point can pull a centroid away from the true cluster. Use DBSCAN or remove outliers first. (2) Non-spherical clusters — K-Means assumes spherical clusters of similar size. If your data has elongated or interlocking shapes, K-Means will split them arbitrarily. (3) The 'curse of dimensionality' — Euclidean distance becomes less meaningful in high dimensions. Consider PCA first to reduce to 10–50 dimensions.

Production tip: never trust the cluster labels blindly. Plot them (using PCA/t-SNE) and inspect a sample of each cluster. The model's 'pattern' may be meaningless noise.

from sklearn.decomposition import PCA
import matplotlib.pyplot as plt

pca = PCA(n_components=2)
X_pca = pca.fit_transform(X_scaled)

plt.figure(figsize=(8,6))
plt.scatter(X_pca[:,0], X_pca[:,1], c=km.labels_, cmap='viridis', alpha=0.6)
plt.scatter(pca.transform(km.cluster_centers_)[:,0], pca.transform(km.cluster_centers_)[:,1], marker='X', s=200, c='red')
plt.title('Cluster Visualization with PCA')
plt.show()

Real-World Uses: Where K-Means Actually Earns Its Keep

K-Means isn't a toy. It's a workhorse you deploy when you need structure from chaos—fast. Customer segmentation is the classic: hand a marketing team five clusters of user behavior and watch them build campaigns that don't suck. But the real money is in production pipelines where latency matters.

Image compression. You take every pixel (R, G, B) as a point in 3D space. Run K-Means with K=16 or 256. Replace each pixel with its nearest centroid color. You just shrank a 24-bit image to 4 or 8 bits per pixel with surprisingly tolerable visual loss. That's not academic—that's how early web thumbnails worked.

Anomaly detection is another hidden gem. Points that land far from any centroid after convergence? Those are outliers. In fraud detection, that's your signal. In sensor data, that's the impending failure. K-Means clusters the normal, and the stragglers tell you something broke. It's not perfect—it assumes spherical clusters—but for a first pass at 10 million records? Unbeatable.

Bottom line: K-Means is your cheap, fast clustering hammer. Use it when you need answers in seconds, not after a neural net finishes training.

// io.thecodeforge — ml-ai tutorial

import numpy as np
from sklearn.cluster import KMeans
from PIL import Image

# Load image and flatten pixels
img = Image.open('workspace_photo.jpg')
pixels = np.array(img).reshape(-1, 3)

# Compress to 16 colors
k = 16
model = KMeans(n_clusters=k, random_state=42)
labels = model.fit_predict(pixels)

# Reconstruct from centroids
compressed = model.cluster_centers_[labels]
compressed = compressed.reshape(np.array(img).shape)
compressed_img = Image.fromarray(compressed.astype('uint8'))

print(f'Original size: {np.array(img).nbytes / 1024:.1f} KB')
print(f'Compressed size: {compressed.nbytes / 1024:.1f} KB')

Implementation: From Scratch So You Actually Understand the Math

Production libraries hide the brittle mechanics of convergence. Before you call KMeans(n_clusters=3), understand that the algorithm is just two loops: assign points to nearest centroid, then recompute centroids as the mean of their assigned points. That second step is why this works only for Euclidean distance — means minimize squared error. The real gotcha? Initialization. Random seeds cause empty clusters and local minima. The fix is k-means++: choose first centroid uniformly, then each subsequent centroid with probability proportional to squared distance from the nearest existing centroid. This dramatically improves both speed and final inertia. The code below implements vanilla k-means with k-means++ initialization. Watch for numerical instability when a cluster gets zero points — we log a warning and skip recomputation. That edge case isn't academic; it will crash a production pipeline if handled naively.

import numpy as np
import warnings

def kmeans(X, k, max_iters=100, tol=1e-4):
    n, d = X.shape
    # k-means++ initialization
    centroids = [X[np.random.randint(n)]]
    for _ in range(1, k):
        dists = np.min([np.linalg.norm(X - c, axis=1)**2 for c in centroids], axis=0)
        probs = dists / dists.sum()
        centroids.append(X[np.random.choice(n, p=probs)])
    centroids = np.array(centroids)

    for _ in range(max_iters):
        labels = np.argmin(np.linalg.norm(X[:, None] - centroids[None], axis=2), axis=1)
        new_centroids = []
        for j in range(k):
            mask = labels == j
            if mask.sum() == 0:
                warnings.warn(f"Cluster {j} empty — keeping previous centroid")
                new_centroids.append(centroids[j])
            else:
                new_centroids.append(X[mask].mean(axis=0))
        new_centroids = np.array(new_centroids)
        if np.linalg.norm(new_centroids - centroids) < tol:
            break
        centroids = new_centroids
    return labels, centroids

Why K-Means Fails on Categorical Data (And What to Do)

K-Means computes centroids by averaging coordinates, which only works for continuous numeric features. Categorical variables like color, country, or product category break the algorithm because mean is meaningless for labels. One-hot encoding creates a high-dimensional sparse space where Euclidean distance distorts similarity — two red apples and two blue cars appear equally distant. Instead, use K-Modes (replaces mean with mode) or Gower distance for mixed data. If you must use K-Means, apply dimensionality reduction like PCA after one-hot encoding, but expect degraded cluster quality. The hidden assumption: every feature must be numeric and ratio-scaled. When your data includes zip codes, gender, or yes/no fields, K-Means silently produces garbage clusters. Validate by examining cluster centroids — if they contain fractional values for binary features, your algorithm is lying to you. Always separate categorical preprocessing as a non-negotiable step before clustering.

// io.thecodeforge — ml-ai tutorial

import pandas as pd
from sklearn.cluster import KMeans
from sklearn.preprocessing import OneHotEncoder, StandardScaler

df = pd.DataFrame({"color": ["red","blue","red"], "size": [1,2,3]})
encoded = OneHotEncoder().fit_transform(df[["color"]]).toarray()
scaled = StandardScaler().fit_transform(df[["size"]])
import numpy as np
X = np.hstack([scaled, encoded])
kmeans = KMeans(n_clusters=2, random_state=0).fit(X)
print(kmeans.cluster_centers_)  # centroid has fractional one-hot

Scalability: Why K-Means Crashes on 100M Rows and How to Fix It

Standard K-Means loads all data into memory and iterates until convergence. At 100 million rows, this causes memory blowout and hours of training. The fix: Mini-Batch K-Means. It samples small random batches (e.g., 1000 rows) per iteration, updating centroids online with a learning rate. Convergence is faster (10x-100x) and memory stays constant. But there's a trade-off: centroids oscillate near the final solution instead of converging exactly. Set batch_size to 10% of data or 1000 (whichever is smaller). For true big data, use Spark MLlib's K-Means which distributes the assignment step across nodes. Another trick: reduce dimensionality first with random projection or PCA on 50M+ rows. Never run Elbow Method on full data — sample 1% to pick K, then train on the rest. The rule: if your dataset exceeds RAM, Mini-Batch K-Means is the only viable off-the-shelf option.

// io.thecodeforge — ml-ai tutorial

from sklearn.cluster import MiniBatchKMeans
from sklearn.datasets import make_blobs
import numpy as np

X, _ = make_blobs(n_samples=10_000_000, n_features=50, random_state=42)
mbk = MiniBatchKMeans(n_clusters=5, batch_size=1000, random_state=0)
mbk.fit(X)
print(f"Inertia: {mbk.inertia_:.2f}")
print(f"Iterations: {mbk.n_iter_}")

Evaluating Cluster Quality When You Have No Ground Truth

Without labels, you cannot use accuracy. Instead, rely on internal validation metrics. Silhouette Score (range -1 to 1) measures how similar a point is to its own cluster vs others — values above 0.5 indicate reasonable separation. Davies-Bouldin Index (lower is better) compares cluster similarity — below 1.0 suggests compact, well-separated clusters. Calinski-Harabasz Index (higher is better) is the ratio of between-cluster variance to within-cluster variance. All three have flaws: Silhouette favors spherical clusters, Davies-Bouldin gets unstable with many clusters, Calinski-Harabasz assumes equal-sized clusters. Never trust a single metric. Run all three, plus visual inspection via PCA or t-SNE if dimensionality allows. A production rule: if Silhouette < 0.3 or Davies-Bouldin > 1.5, re-examine your K and preprocessing. These metrics also help choose K — use the 'elbow' of the Silhouette curve or minimum Davies-Bouldin. But remember: good metrics don't guarantee actionable clusters. Always ground-truth check with domain experts.

// io.thecodeforge — ml-ai tutorial

from sklearn.metrics import silhouette_score, davies_bouldin_score, calinski_harabasz_score
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs

X, _ = make_blobs(n_samples=1000, n_features=10, centers=4, random_state=42)
kmeans = KMeans(n_clusters=4, random_state=0).fit(X)
print(f"Silhouette: {silhouette_score(X, kmeans.labels_):.3f}")
print(f"Davies-Bouldin: {davies_bouldin_score(X, kmeans.labels_):.3f}")
print(f"Calinski-Harabasz: {calinski_harabasz_score(X, kmeans.labels_):.1f}")