K-means + clustering — finding structure

📅 Day 41. K-means is the most-taught clustering algorithm — and rightly so. It's simple, fast, and works well when the data has spherical clusters of similar size.

🎯 The algorithm — four steps that repeat until convergence:

1️⃣ Pick k initial centroids. Random selection of k data points works, but k-means++ (sklearn default) is smarter — it picks initial centroids that are spread out, leading to faster convergence and better results.

2️⃣ Assignment. Each data point is assigned to the nearest centroid (using Euclidean distance). Now you have k clusters, each containing the points closest to its centroid.

3️⃣ Update. Each centroid moves to the mean (centroid) of its assigned points. New centroid position; clusters might shift on the next iteration.

4️⃣ Repeat. Steps 2 and 3 until centroids stop moving (or move very little). Usually 10-50 iterations on real data.

📊 The result — k clusters of points around k centroids. Each point belongs to one cluster.

💡 Where k-means works:

→ Customer segmentation by behaviour metrics.
→ Image quantisation (compressing image colors to k representative ones).
→ Document topic clustering (after embedding).
→ Anomaly detection (points far from any centroid are anomalies).

⚠️ Where k-means fails:

→ Non-spherical clusters. K-means assumes round blobs. For long curved clusters, use DBSCAN.
→ Very different cluster sizes. K-means tends to make clusters of similar size. For varied sizes, use Gaussian Mixture Models.
→ Choosing k. The algorithm requires you to specify k upfront. We address this in the midday post.
→ Outliers. They drag centroids toward them. Pre-clean or use a robust variant.

🚀 K-means is the right default for many clustering tasks. When it doesn't fit, you have alternatives.

🤔 K-means' biggest weakness — you have to pick k upfront. Pick wrong and the clusters are meaningless. Two methods help.

📈 Method 1 — Elbow. Plot inertia (within-cluster sum of squared distances) for k = 2, 3, ..., 15. Inertia decreases as k grows (more clusters → tighter fits). Look for the 'elbow' — the point where adding more k stops giving meaningful improvement.

Visually, the curve drops steeply, then flattens. The elbow is where the steep-to-flat transition happens. That k is the answer.

⚠️ Caveats with elbow:
→ The 'elbow' is sometimes ambiguous. Curves don't always have a clean bend.
→ Subjective. Different people pick different elbows from the same plot.
→ Best for showing 'k=10 is overkill, k=4 is enough'. Less good for distinguishing k=4 from k=5.

📊 Method 2 — Silhouette score. For each point, measure (b - a) / max(a, b) where a is mean distance to its own cluster and b is mean distance to the nearest OTHER cluster. Range: -1 to 1.

→ +1 means the point fits its cluster well and is far from other clusters.
→ 0 means the point is on the boundary between clusters.
→ Negative means the point might be in the wrong cluster.

For each k, compute the mean silhouette across all points. Pick the k that maximises mean silhouette.

🏆 Silhouette is more principled than elbow. The output is a single number, comparable across k values, with a clear interpretation.

📋 In practice — run both. If they agree, you have your k. If they disagree, your data probably doesn't have clean clusters, and the 'best' k is somewhat arbitrary. Use domain knowledge as the tiebreaker.

💡 Don't trust k blindly. Visualise the clusters (PCA or t-SNE for 2D projection). If they look meaningful, ship. If they look random, the data may not cluster at all — k-means will give you SOMETHING regardless.

💻 Twelve lines to find the best k for your dataset. Loop k from 2 to 10, fit k-means, compute silhouette, track the best.

Look at the snippet. We initialise best_k = 2 and best_s = -1 (silhouette can be negative; -1 is the lower bound).

For each k from 2 to 10, we create a KMeans model with n_init=10 (run k-means 10 times with different initial centroids and pick the best result; protects against bad random initialisations). Fit and predict labels. Compute silhouette_score on (X, labels).

If silhouette beats current best, update.

Print the silhouette per k as you go. Useful for seeing the curve, not just the winner.

📊 Interpreting the output:

→ Silhouette > 0.5 — strong, well-separated clusters.
→ Silhouette 0.25-0.5 — reasonable structure but some overlap.
→ Silhouette < 0.25 — weak structure, clusters are murky.
→ Silhouette near zero or negative — the data probably doesn't cluster at all. Don't fool yourself.

🎯 What to do with the best k:

→ Refit KMeans with that k on the full dataset.
→ Inspect the clusters — what makes each one distinct? Look at centroid coordinates, examine sample points.
→ Use cluster labels as features for downstream models, or as segments for analysis.

⚠️ The most common mistake — running this without scaling first. If features are on different scales (income in dollars, age in years), the clustering becomes dominated by the larger-scale feature. Always StandardScaler.fit_transform(X) before k-means. We cover this in tonight's tip.

🚀 12 lines. Real cluster discovery. Add scaling for production-grade results.

💡 The most common cluster bug — features on different scales.

🚨 The setup. You have a dataset with two features:

→ income — values in [10000, 200000]
→ age — values in [18, 80]

You run k-means. The clusters look weird. They're stratified entirely by income, ignoring age.

🤔 Why? Euclidean distance. The distance between two points is sqrt(sum of squared feature differences). When income's scale is ~1000x larger than age's scale, income's squared differences dominate. Age contributes essentially nothing to distance. The clusters form along income, period.

✅ The fix — StandardScaler. Scales each feature to mean=0, std=1. Now both features contribute equally to distance.

from sklearn.preprocessing import StandardScaler

X_scaled = StandardScaler().fit_transform(X)
kmeans = KMeans(n_clusters=k).fit(X_scaled)

📊 What changes — every feature lives in roughly the same range. Distances respect all features equally. Clusters reflect actual structure.

🎯 When to scale (the same rule applies):

→ KMeans, hierarchical clustering, DBSCAN — yes, all distance-based.
→ PCA, t-SNE, UMAP — yes, distance-based.
→ k-Nearest Neighbours — yes, classic example.
→ Linear/logistic regression with regularisation (Ridge, Lasso) — yes, regularisation is sensitive to scale.
→ Neural networks — yes (or at least normalize within the network).

📋 When NOT to scale:

→ Tree-based models (decision trees, random forests, gradient boosting) — no. They split on threshold values, which are scale-invariant.

💡 Default — when in doubt, scale. The cost is one line; the savings are 'why are my clusters terrible' debugging sessions.

⚠️ The variant — for clusters with outliers, RobustScaler is better than StandardScaler. Uses median and IQR instead of mean and std.

📅 End of Day 41.

✅ Recap:

🎯 K-means in 4 steps — init, assign, update, repeat. Spherical clusters of similar size. Fails on non-spherical, varied-size, or no-structure data.

📊 Picking k — elbow (visual) or silhouette (principled). Run both; if they disagree, your data may not cluster cleanly.

💻 12-line silhouette loop to find the best k. n_init=10 for robust initialisation.

📐 StandardScaler before any distance algorithm. Mandatory for k-means, PCA, k-NN. Saves you the 'why are clusters dominated by one feature' bug.

🧠 Reflection — clustering is harder than supervised learning because there's no ground truth. You can always cluster; the question is whether the clusters mean anything. Visualise (PCA + scatter), inspect cluster centroids, check business interpretability.

🚀 Tomorrow, Day 42 — SVMs and the wrap of week 6. Why classical ML still wins on tabular data even in the age of LLMs. The classical-vs-DL decision tree by data type.

💼 Six weeks done after tomorrow. Foundations + Python + DSA + data + classical ML covered. Then we go into deep learning, transformers, RAG, agents, automation, career. The remaining seven weeks are the AI-modern stack.

👋 See you in the morning.