K-Means Clustering

K-Means Clustering

Welcome to Module 5 — Unsupervised Learning. Up to now every algorithm you've studied has relied on labelled training data: you told the model which rows were fraudulent, which emails were spam, which scores counted as 'high'. Unsupervised learning removes that luxury. You hand the algorithm raw, unlabelled data and ask it to find hidden structure on its own. This mirrors how a scout analyses thousands of match clips without pre-existing categories — the patterns emerge from the data itself.

K-Means is the most widely used clustering algorithm. Its goal is deceptively simple: partition N data points into K groups such that each point belongs to the cluster whose centre (centroid) is nearest. The algorithm iterates — moving centroids, reassigning points — until assignments stabilise. Despite its simplicity, K-Means underpins customer segmentation, image compression, document grouping, and player profiling in sports analytics.

The K-Means Algorithm Step by Step

The algorithm runs in four repeating steps. (1) Initialise: randomly place K centroids in the feature space. (2) Assign: label every point with the index of its nearest centroid using Euclidean distance. (3) Update: recompute each centroid as the mean of all points currently assigned to it. (4) Repeat steps 2–3 until no point changes cluster (convergence) or a maximum iteration count is reached. The result depends on the initial centroid placement, which is why scikit-learn runs the algorithm multiple times (`n_init`) and keeps the best result.

Convergence is guaranteed but not to a global optimum — K-Means finds a local minimum of the inertia (sum of squared distances from each point to its centroid). The smart initialisation strategy `k-means++` (scikit-learn's default) seeds centroids far apart to reduce the chance of a bad local minimum. It picks the first centroid uniformly at random, then each subsequent centroid with probability proportional to the squared distance from the nearest existing centroid.

Inertia and the Elbow Method

Inertia measures cluster tightness: the lower, the better. However, inertia always decreases as K increases — at K=N every point is its own cluster with zero inertia. The Elbow Method plots inertia vs K and looks for a 'kink' where the rate of decrease flattens. This kink suggests a reasonable K. Silhouette score provides a complementary view: it measures how similar a point is to its own cluster vs the next nearest cluster, ranging from −1 (wrong cluster) to +1 (perfect fit), with values near 0 indicating overlapping clusters.

import numpy as np
import matplotlib.pyplot as plt
from sklearn.cluster import KMeans
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
from sklearn.metrics import silhouette_score

# ── Synthetic cricket delivery dataset ───────────────────────────────────────
# Features: [speed_kmh, line_deg, length_m, lateral_movement_cm]
X, _ = make_blobs(n_samples=400, centers=4, cluster_std=1.2, random_state=42)
X = StandardScaler().fit_transform(X)   # always scale before K-Means

# ── Elbow + Silhouette sweep ─────────────────────────────────────────────────
inertias, sil_scores = [], []
K_range = range(2, 10)

for k in K_range:
    km = KMeans(n_clusters=k, init='k-means++', n_init=10, random_state=42)
    km.fit(X)
    inertias.append(km.inertia_)
    sil_scores.append(silhouette_score(X, km.labels_))

fig, axes = plt.subplots(1, 2, figsize=(12, 4))
axes[0].plot(K_range, inertias, 'bo-')
axes[0].set(xlabel='K', ylabel='Inertia', title='Elbow Method')
axes[1].plot(K_range, sil_scores, 'rs-')
axes[1].set(xlabel='K', ylabel='Silhouette Score', title='Silhouette Score')
plt.tight_layout(); plt.show()

# ── Fit final model ──────────────────────────────────────────────────────────
best_k = 4
km_final = KMeans(n_clusters=best_k, init='k-means++', n_init=10, random_state=42)
labels = km_final.fit_predict(X)
print(f"Cluster sizes: {np.bincount(labels)}")
print(f"Inertia: {km_final.inertia_:.2f}")
print(f"Silhouette Score: {silhouette_score(X, labels):.4f}")

Fitting K-Means in Scikit-learn

K-Means follows the familiar scikit-learn API: `KMeans(n_clusters=K).fit(X)`. Key hyperparameters are: `n_clusters` (K — the most important choice), `init` (`k-means++` or `random`), `n_init` (number of random restarts, default 10), `max_iter` (maximum EM iterations per run, default 300), and `tol` (convergence tolerance). After fitting, `km.labels_` contains the cluster index for each training point, `km.cluster_centers_` holds the K centroid coordinates, and `km.inertia_` is the total within-cluster sum of squares. To assign new points, call `km.predict(X_new)`.

from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
import numpy as np

# Simulated IPL batting stats: [strike_rate, boundary_pct, dot_ball_pct, avg]
np.random.seed(0)
batting = np.random.randn(200, 4)
batting = StandardScaler().fit_transform(batting)

# Fit K-Means
km = KMeans(n_clusters=3, init='k-means++', n_init=10,
            max_iter=300, random_state=42)
km.fit(batting)

# Inspect results
print("Cluster centres (scaled):")
print(np.round(km.cluster_centers_, 3))

print(f"\nLabel distribution: {np.bincount(km.labels_)}")

# Assign new unseen batters
new_batter = np.array([[0.8, 1.2, -0.5, 0.3]])   # already scaled
cluster = km.predict(new_batter)
print(f"\nNew batter assigned to cluster: {cluster[0]}")

Limitations and When K-Means Fails

K-Means has important assumptions baked in. It assumes clusters are (1) roughly spherical, (2) similarly sized, and (3) of similar density. When these assumptions break down — think crescent-shaped clusters, or one tiny tight cluster next to a vast diffuse one — K-Means produces misleading results. It is also sensitive to outliers because a single extreme point can pull a centroid far from the true group centre. Always scale features before clustering, since K-Means uses Euclidean distance which is dominated by features with the largest numeric range.

K-Means also requires you to specify K in advance, which is not always obvious. The Elbow and Silhouette methods help but do not always yield a clean answer. When the true cluster structure is unknown, it is good practice to compare K-Means results with at least one alternative (hierarchical clustering, DBSCAN) before committing to an interpretation. You will encounter those in the next two lessons.

Mini-Batch K-Means for Large Datasets

Standard K-Means loads the entire dataset into memory each iteration, making it slow for millions of rows. `MiniBatchKMeans` processes random subsets (mini-batches) each iteration, giving approximate centroids much faster. The API is identical to `KMeans`. Inertia is slightly higher than exact K-Means but the speed gain is dramatic. For datasets above ~100 K rows, prefer `MiniBatchKMeans`.

from sklearn.cluster import MiniBatchKMeans
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
import time

X_large, _ = make_blobs(n_samples=200_000, centers=5, random_state=42)
X_large = StandardScaler().fit_transform(X_large)

t0 = time.time()
mb_km = MiniBatchKMeans(n_clusters=5, batch_size=1024,
                         n_init=3, random_state=42)
mb_km.fit(X_large)
print(f"MiniBatchKMeans time: {time.time()-t0:.2f}s  |  Inertia: {mb_km.inertia_:.0f}")

Practical Pipeline: Clustering Customer Segments

import pandas as pd
import numpy as np
from sklearn.cluster import KMeans
from sklearn.preprocessing import StandardScaler
from sklearn.pipeline import Pipeline
from sklearn.metrics import silhouette_score

# Simulated e-commerce customer features
np.random.seed(7)
n = 300
df = pd.DataFrame({
    'recency_days':    np.random.exponential(30, n),
    'frequency':       np.random.poisson(5, n),
    'monetary_value':  np.random.lognormal(6, 1.2, n),
    'avg_session_min': np.random.gamma(3, 5, n),
})

X = df.values

# Build pipeline: scale → cluster
pipe = Pipeline([
    ('scaler', StandardScaler()),
    ('kmeans', KMeans(n_clusters=4, n_init=10, random_state=42))
])
pipe.fit(X)
df['segment'] = pipe.named_steps['kmeans'].labels_

# Profile segments
print(df.groupby('segment').agg({
    'recency_days': 'mean',
    'frequency': 'mean',
    'monetary_value': 'mean',
    'avg_session_min': 'mean'
}).round(1))

X_scaled = pipe.named_steps['scaler'].transform(X)
print(f"\nSilhouette: {silhouette_score(X_scaled, df['segment']):.4f}")

• K-Means partitions data into K clusters by iterating between centroid assignment and update steps until convergence.
• Always StandardScale features before K-Means — Euclidean distance is sensitive to feature magnitude differences.
• Use the Elbow Method (inertia vs K) and Silhouette Score together to choose K; neither gives a perfect answer alone.
• K-Means++ initialisation spreads starting centroids to avoid poor local minima — it is the scikit-learn default.
• K-Means assumes spherical, equal-density clusters; it fails on non-convex shapes, heavy outliers, or unequal cluster sizes.
• MiniBatchKMeans offers near-identical results with far less compute time for datasets above ~100 K rows.
• Always embed K-Means in a Pipeline so scaling and clustering are applied consistently to train and test data.