The Big Picture
Unlike supervised learning (where we have labels), clustering is unsupervised: we have just features and want to discover natural groups in the data. KMeans is the simplest and most popular clustering algorithm. It partitions data into K clusters by minimizing within-cluster variance — think of it as "placing K centers so that points cluster tightly around them."
When is clustering useful? When you want to discover structure without pre-existing labels. Examples include customer segmentation, document clustering, image compression, and anomaly detection. It's called "unsupervised" because the algorithm learns the clusters from data alone.
AdTech Example: Audience Segmentation for Bing Ads
At Microsoft Bing Ads, you have millions of users with behavioral data. You want to segment them into distinct audience groups to tailor ad strategies per group. Unlike supervised learning (where you'd predict a specific outcome), you don't have pre-labeled "audience segments" — you discover them via clustering.
How KMeans Works — Step-by-Step Algorithm
KMeans is simple: initialize K centers, then repeatedly (1) assign points to nearest center, (2) recompute centers. Repeat until convergence.
Distance Measures (Euclidean, Manhattan, Cosine, Mahalanobis)
The choice of distance metric fundamentally changes KMeans. Different metrics suit different data types and problem domains.
1. Euclidean Distance (L2)
2. Manhattan Distance (L1)
3. Cosine Similarity / Distance
4. Mahalanobis Distance
Accounts for correlation between features and feature variance. More sophisticated than Euclidean but computationally expensive.
When to Use Which Distance Metric?
| Metric | Best For | Characteristics | Cost |
|---|---|---|---|
| Euclidean | Continuous numeric data (user age, revenue, time spent). Most common default. | Geometric distance; assumes isotropic (equal variance) clusters | O(d) per pair |
| Manhattan | Data on grid/network (lat/lon, chess moves). Robust to outliers. | Sum of absolute differences; less sensitive to extreme values | O(d) per pair |
| Cosine | Text, TF-IDF vectors, sparse high-dimensional data (document clustering) | Angle-based; ignores magnitude. Symmetric. | O(d) per pair |
| Mahalanobis | When features are correlated; when you want to account for variance | Statistically principled; handles covariance | O(d³) initial + O(d²) per pair |
Handling Mixed Data Types (K-Prototypes, Gower Distance)
Real-world data often has both numeric (age, revenue) and categorical (device type, region) features. Standard KMeans (Euclidean) can't handle categorical data well. Here are three strategies.
Strategy 1: One-Hot Encoding + Euclidean
✓ Simple, uses standard KMeans.
✓ Works well when categorical features have few categories.
✗ Creates sparse, high-dimensional vectors (curse of dimensionality).
✗ Treats all categorical levels equally in distance (no semantic similarity).
Strategy 2: K-Prototypes (Numeric + Categorical)
K-Prototypes extends KMeans to handle both data types simultaneously by using different distance functions per type.
Strategy 3: Gower Distance (Unified Metric)
Gower distance normalizes all features to [0,1] range, then computes a weighted average of per-feature distances. Works for any data type.
• Gower: More flexible, works with any feature type. Distance between points, symmetric.
• K-Prototypes: Simpler to implement, faster, prototypes are interpretable feature vectors.
Comparison: Which Strategy?
| Strategy | When to Use | Pros | Cons |
|---|---|---|---|
| One-Hot + Euclidean | Few categorical features with few categories. Simple baselines. | Standard, well-understood. Most tools support it. | High dimensionality. Loses categorical semantics. Doesn't scale with many categories. |
| K-Prototypes | Mixed numeric + categorical data. Want interpretable prototypes. | Handles both types natively. Prototypes are human-readable. | Less common; fewer libraries. Need to tune λ parameter. |
| Gower Distance | Many feature types. Need unified distance metric. Robust approach. | Principled. Handles ordinal, binary, continuous, categorical. Normalized [0,1]. | More complex. Slower. Still need to pair with some clustering algorithm. |
Choosing K — Elbow Method, Silhouette Score, Gap Statistic
The number of clusters K is not known a priori in unsupervised learning. Here are three common methods to determine it.
1. Elbow Method
Compute WCSS (within-cluster sum of squares) for different K values. Plot WCSS vs K. Look for the "elbow" — the point where adding more clusters no longer significantly reduces WCSS.
Cons: Elbows aren't always clear (especially in noisy data). Subjective.
2. Silhouette Score
For each point, measure how similar it is to points in its own cluster vs. other clusters. Silhouette score ranges from -1 (bad, in wrong cluster) to +1 (good, far from other clusters).
Cons: Computationally expensive O(n²) for large datasets.
3. Gap Statistic
Compares WCSS of real data to WCSS of random uniform data. A large gap means the real clusters are much tighter than random noise, indicating good clustering.
Which Method to Use?
| Method | Speed | Reliability | When to Use |
|---|---|---|---|
| Elbow | Fast O(nk) | Moderate (subjective) | Quick exploration. Good starting point. Use when you want simplicity. |
| Silhouette | Slow O(n²) | Good (quantitative) | When you want quantitative quality metric. Works well for small-medium datasets. |
| Gap Statistic | Very slow (needs random samples) | Very good (statistically principled) | When you need statistical rigor. Slower but most robust. For research/critical applications. |
Initialization Strategies — Random vs KMeans++
KMeans is sensitive to initial center placement. Bad initialization can trap the algorithm in a poor local optimum. KMeans++ initialization dramatically improves convergence quality.
Random Initialization (Naive)
KMeans++ Initialization
Smart initialization: place first center randomly, then place each subsequent center far from existing centers. This spreads centers out, avoiding poor local optima.
• Better final WCSS (tighter clusters).
• Faster convergence (fewer iterations).
• Less dependent on random seed (more consistent).
Cost: O(nk) additional initialization (negligible for training).
Recommendation
Always use KMeans++ for production. It's the default in scikit-learn, nearly cost-free, and dramatically improves robustness. If you have domain knowledge about centers (e.g., "we know 5 cities matter"), you can seed with those instead.
Convergence, Local Minima & Practical Tips
Convergence Guarantee
KMeans is guaranteed to converge (reach a fixed point where assignments don't change). However, it may converge to a local optimum, not the global optimum. This is why good initialization (KMeans++) matters.
1. Run multiple times: KMeans 10+ times with different random seeds, pick the best (lowest WCSS).
2. Use KMeans++: Reduces local optima issues significantly.
3. Set convergence tolerance: Don't require perfect convergence; stop when centers move < ε.
Practical Tuning Tips
Convergence Settings
max_iter: 300 (default)
tol: 1e-4 (center movement threshold)
n_init: 10 (number of runs)
Run 10× with different seeds, keep best.
For Large Datasets
Mini-batch KMeans: Subset data per iteration (faster, lower WCSS quality)
Sampling: Cluster sample, apply to full data
Sparse matrices: If data is sparse, use sparse distance metrics
When KMeans Struggles
| Challenge | Why | Solution |
|---|---|---|
| Unequal cluster sizes | KMeans minimizes WCSS, not cluster size. Tends to split large clusters into many small ones. | Use DBSCAN or hierarchical clustering. Or apply K-means to balanced subsamples. |
| Non-convex clusters | KMeans assumes spherical (convex) clusters. Crescent or ring shapes confuse it. | Use DBSCAN, spectral clustering, or density-based methods. |
| High dimensions | Distance metrics become less meaningful ("curse of dimensionality"). All points equidistant. | Reduce dimensionality first (PCA, UMAP). Use cosine distance instead of Euclidean. |
| Outliers | KMeans (Euclidean distance) sensitive to outliers. One outlier can drag a center away. | Preprocess: remove/cap outliers. Or use robust distance (Mahalanobis, Manhattan). |
Python Implementation from Scratch
Here's a complete, class-based KMeans implementation using only numpy and pandas. Includes KMeans++, multiple distance metrics, and elbow method.
import numpy as np
import pandas as pd
from typing import Tuple, Optional
class KMeansClustering:
"""
KMeans clustering algorithm with KMeans++ initialization,
multiple distance metrics, and helper methods.
"""
def __init__(
self,
n_clusters: int = 3,
max_iter: int = 300,
tol: float = 1e-4,
random_state: int = 42,
metric: str = 'euclidean',
init: str = 'kmeans++'
):
"""
Parameters:
-----------
n_clusters : int
Number of clusters (K)
max_iter : int
Maximum iterations before stopping
tol : float
Tolerance for convergence (change in center positions)
random_state : int
Random seed for reproducibility
metric : str
Distance metric: 'euclidean', 'manhattan', 'cosine'
init : str
Initialization method: 'random', 'kmeans++'
"""
self.n_clusters = n_clusters
self.max_iter = max_iter
self.tol = tol
self.random_state = random_state
self.metric = metric
self.init = init
self.centers = None
self.labels = None
self.wcss = None
self.wcss_history = []
np.random.seed(random_state)
def _euclidean_distance(self, X: np.ndarray, center: np.ndarray) -> np.ndarray:
"""Compute Euclidean distance from points to a center."""
return np.sqrt(np.sum((X - center) ** 2, axis=1))
def _manhattan_distance(self, X: np.ndarray, center: np.ndarray) -> np.ndarray:
"""Compute Manhattan distance from points to a center."""
return np.sum(np.abs(X - center), axis=1)
def _cosine_distance(self, X: np.ndarray, center: np.ndarray) -> np.ndarray:
"""Compute cosine distance from points to a center."""
# Cosine similarity: (A·B) / (||A|| ||B||)
dot_product = np.dot(X, center)
norm_X = np.linalg.norm(X, axis=1)
norm_center = np.linalg.norm(center)
# Avoid division by zero
with np.errstate(divide='ignore', invalid='ignore'):
similarity = dot_product / (norm_X * norm_center + 1e-8)
similarity = np.nan_to_num(similarity)
return 1 - similarity # Convert similarity to distance
def _compute_distance_matrix(self, X: np.ndarray) -> np.ndarray:
"""
Compute distance from each point to each center.
Returns: (n_samples, n_clusters) array
"""
distances = np.zeros((X.shape[0], self.n_clusters))
for k in range(self.n_clusters):
if self.metric == 'euclidean':
distances[:, k] = self._euclidean_distance(X, self.centers[k])
elif self.metric == 'manhattan':
distances[:, k] = self._manhattan_distance(X, self.centers[k])
elif self.metric == 'cosine':
distances[:, k] = self._cosine_distance(X, self.centers[k])
else:
raise ValueError(f"Unknown metric: {self.metric}")
return distances
def _initialize_centers(self, X: np.ndarray):
"""Initialize cluster centers using specified method."""
if self.init == 'random':
indices = np.random.choice(X.shape[0], self.n_clusters, replace=False)
self.centers = X[indices].copy()
elif self.init == 'kmeans++':
# KMeans++ initialization
self.centers = np.zeros((self.n_clusters, X.shape[1]))
# Pick first center randomly
first_idx = np.random.randint(X.shape[0])
self.centers[0] = X[first_idx]
# Pick remaining centers
for k in range(1, self.n_clusters):
# Compute distances to nearest center
distances = self._compute_distance_matrix(X)
min_distances = np.min(distances, axis=1)
# Pick next center with probability ∝ distance²
probabilities = min_distances ** 2
probabilities /= np.sum(probabilities)
cumulative = np.cumsum(probabilities)
r = np.random.rand()
next_idx = np.searchsorted(cumulative, r)
self.centers[k] = X[next_idx]
else:
raise ValueError(f"Unknown init method: {self.init}")
def fit(self, X: np.ndarray) -> 'KMeansClustering':
"""
Fit the KMeans model to data.
Parameters:
-----------
X : np.ndarray
Data array of shape (n_samples, n_features)
Returns:
--------
self : KMeansClustering
"""
X = np.asarray(X, dtype=np.float64)
# Initialize centers
self._initialize_centers(X)
self.wcss_history = []
# Main EM loop
for iteration in range(self.max_iter):
# E-step: Assign points to nearest center
distances = self._compute_distance_matrix(X)
self.labels = np.argmin(distances, axis=1)
# Compute WCSS for this iteration
wcss = np.sum(np.min(distances, axis=1) ** 2)
self.wcss_history.append(wcss)
# M-step: Recompute centers
old_centers = self.centers.copy()
for k in range(self.n_clusters):
mask = self.labels == k
if np.sum(mask) > 0:
self.centers[k] = np.mean(X[mask], axis=0)
# If cluster is empty, keep old center
# Check convergence
center_shift = np.max(np.linalg.norm(self.centers - old_centers, axis=1))
if center_shift < self.tol:
print(f"Converged at iteration {iteration}")
break
# Final assignment
distances = self._compute_distance_matrix(X)
self.labels = np.argmin(distances, axis=1)
self.wcss = np.sum(np.min(distances, axis=1) ** 2)
return self
def predict(self, X: np.ndarray) -> np.ndarray:
"""
Predict cluster labels for new data.
Parameters:
-----------
X : np.ndarray
Data array of shape (n_samples, n_features)
Returns:
--------
labels : np.ndarray
Cluster labels for each point
"""
if self.centers is None:
raise ValueError("Model not fitted yet. Call fit() first.")
X = np.asarray(X, dtype=np.float64)
distances = self._compute_distance_matrix(X)
return np.argmin(distances, axis=1)
def fit_predict(self, X: np.ndarray) -> np.ndarray:
"""Fit model and return cluster labels."""
self.fit(X)
return self.labels
def elbow_method(X: np.ndarray, K_range: range = range(1, 11)) -> Tuple[list, list]:
"""
Compute WCSS for different K values (for elbow plot).
Parameters:
-----------
X : np.ndarray
Data array
K_range : range
Range of K values to test
Returns:
--------
K_values : list
K values tested
wcss_values : list
WCSS for each K
"""
wcss_values = []
K_values = list(K_range)
for k in K_values:
kmeans = KMeansClustering(n_clusters=k, init='kmeans++')
kmeans.fit(X)
wcss_values.append(kmeans.wcss)
return K_values, wcss_values
def silhouette_coefficient(X: np.ndarray, labels: np.ndarray) -> float:
"""
Compute average silhouette coefficient.
Parameters:
-----------
X : np.ndarray
Data array
labels : np.ndarray
Cluster labels
Returns:
--------
avg_silhouette : float
Average silhouette score in [-1, 1]
"""
n = X.shape[0]
silhouettes = []
for i in range(n):
# a(i): mean distance to points in same cluster
same_cluster = X[labels == labels[i]]
if len(same_cluster) > 1:
a_i = np.mean(np.linalg.norm(X[i] - same_cluster, axis=1))
else:
a_i = 0
# b(i): min mean distance to other clusters
b_i = np.inf
for c in np.unique(labels):
if c != labels[i]:
other_cluster = X[labels == c]
b_c = np.mean(np.linalg.norm(X[i] - other_cluster, axis=1))
b_i = min(b_i, b_c)
# Silhouette coefficient
if max(a_i, b_i) == 0:
s_i = 0
else:
s_i = (b_i - a_i) / max(a_i, b_i)
silhouettes.append(s_i)
return np.mean(silhouettes)
# ==============================================================================
# EXAMPLE: AdTech User Segmentation
# ==============================================================================
if __name__ == "__main__":
# Create synthetic user data
np.random.seed(42)
# Cluster 1: Power users (high spend, high CTR)
power_users = np.random.normal(loc=[50, 0.08, 1000], scale=[5, 0.01, 200], size=(100, 3))
# Cluster 2: Casual users (medium spend, low CTR)
casual_users = np.random.normal(loc=[25, 0.02, 200], scale=[5, 0.005, 50], size=(100, 3))
# Cluster 3: New users (low spend, medium CTR)
new_users = np.random.normal(loc=[10, 0.03, 50], scale=[3, 0.01, 30], size=(100, 3))
X = np.vstack([power_users, casual_users, new_users])
print("=" * 70)
print("ADTECH USER SEGMENTATION WITH KMEANS")
print("=" * 70)
print(f"Data shape: {X.shape}")
print(f"Features: [session_time (min), ctr, spend ($)]")
# 1. ELBOW METHOD
print("\n1. ELBOW METHOD")
print("-" * 70)
K_values, wcss_values = elbow_method(X, range(1, 8))
for k, wcss in zip(K_values, wcss_values):
print(f" K={k}: WCSS={wcss:.2f}")
# 2. FIT WITH K=3 (TRUE K)
print("\n2. FITTING WITH K=3")
print("-" * 70)
kmeans = KMeansClustering(n_clusters=3, init='kmeans++', metric='euclidean')
kmeans.fit(X)
print(f"Final WCSS: {kmeans.wcss:.2f}")
print(f"Convergence: {len(kmeans.wcss_history)} iterations")
print("\nCluster Centers:")
for k, center in enumerate(kmeans.centers):
print(f" Cluster {k}: session_time={center[0]:.1f}min, ctr={center[1]:.3f}, spend=${center[2]:.0f}")
print("\nCluster Assignments:")
for k in range(3):
count = np.sum(kmeans.labels == k)
print(f" Cluster {k}: {count} users")
# 3. SILHOUETTE SCORE
print("\n3. SILHOUETTE SCORE")
print("-" * 70)
sil_score = silhouette_coefficient(X, kmeans.labels)
print(f"Average Silhouette: {sil_score:.3f}")
# Compare with K=2 and K=4
for k in [2, 4]:
kmeans_k = KMeansClustering(n_clusters=k, init='kmeans++')
kmeans_k.fit(X)
sil = silhouette_coefficient(X, kmeans_k.labels)
print(f"K={k}: Silhouette={sil:.3f}")
print("\n" + "=" * 70)
print("✓ Clustering complete! Use Cluster IDs for audience segmentation.")
print("=" * 70)
Key Features
Class Structure
KMeansClustering: Full implementation
• fit(X): Train the model
• predict(X): Label new data
• fit_predict(X): Both
• Support for Euclidean, Manhattan, Cosine distances
Helper Functions
elbow_method(): Compute WCSS for K range
silhouette_coefficient(): Quantify cluster quality
Both use only numpy, no external deps
Usage Example
# Basic usage
kmeans = KMeansClustering(n_clusters=5, init='kmeans++')
kmeans.fit(user_data)
cluster_ids = kmeans.labels
# Find optimal K
K_values, wcss = elbow_method(user_data, range(1, 11))
# Plot K_values vs wcss, find elbow
# Evaluate cluster quality
silhouette = silhouette_coefficient(user_data, cluster_ids)
if silhouette > 0.5:
print("Good clustering!")
# Predict on new data
new_users = get_new_user_data()
new_cluster_ids = kmeans.predict(new_users)