K-Means Clustering

K-Means Clustering: Finding Hidden Groups in Data

Clustering is unsupervised learning — you have data but no labels. K-Means finds structure by grouping similar examples together. It's one of the most widely used algorithms in data science, powering customer segmentation, anomaly detection, image compression, and document organization.

The Algorithm

K-Means iterates between two steps until convergence:

Initialize: Place k centroids randomly in the feature space

Step 1 — Assignment:
  For each point, find the nearest centroid
  Assign that point to that centroid's cluster

Step 2 — Update:
  Move each centroid to the mean of all points assigned to it

Repeat until centroids stop moving (convergence)

Iteration 0 (random init):
  Centroid 1: (1, 5)
  Centroid 2: (8, 2)
  Centroid 3: (5, 8)

Iteration 1 (after assignment + update):
  Centroid 1: (2, 4)  ← Moved to mean of its cluster
  Centroid 2: (7, 3)
  Centroid 3: (5, 7)

... continues until centroids stabilize

Basic K-Means Implementation

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

# Generate sample data
X, y_true = make_blobs(n_samples=500, centers=4, cluster_std=0.8, random_state=42)

# Scale data — K-Means is distance-based
scaler = StandardScaler()
X_scaled = scaler.fit_transform(X)

# Fit K-Means
kmeans = KMeans(
    n_clusters=4,
    init='k-means++',   # Smart initialization (better than random)
    n_init=10,          # Run 10 times with different seeds, keep best
    max_iter=300,
    random_state=42
)
kmeans.fit(X_scaled)

# Results
labels = kmeans.labels_
centroids = kmeans.cluster_centers_
inertia = kmeans.inertia_  # Sum of squared distances to centroids

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

# Visualize
plt.figure(figsize=(10, 6))
scatter = plt.scatter(X[:, 0], X[:, 1], c=labels, cmap='viridis', alpha=0.6)
centroids_unscaled = scaler.inverse_transform(centroids)
plt.scatter(centroids_unscaled[:, 0], centroids_unscaled[:, 1], 
            marker='*', s=300, c='red', label='Centroids')
plt.colorbar(scatter)
plt.title('K-Means Clustering Result')
plt.legend()
plt.show()

Finding the Right K: The Elbow Method

inertias = []
silhouette_scores = []
k_range = range(2, 12)

from sklearn.metrics import silhouette_score

for k in k_range:
    kmeans = KMeans(n_clusters=k, init='k-means++', n_init=10, random_state=42)
    kmeans.fit(X_scaled)
    inertias.append(kmeans.inertia_)
    silhouette_scores.append(silhouette_score(X_scaled, kmeans.labels_))

fig, (ax1, ax2) = plt.subplots(1, 2, figsize=(14, 5))

# Elbow curve
ax1.plot(k_range, inertias, 'bo-')
ax1.set_xlabel('Number of Clusters (k)')
ax1.set_ylabel('Inertia')
ax1.set_title('Elbow Method')

# Silhouette scores
ax2.plot(k_range, silhouette_scores, 'ro-')
ax2.set_xlabel('Number of Clusters (k)')
ax2.set_ylabel('Silhouette Score')
ax2.set_title('Silhouette Analysis')
ax2.axvline(x=k_range[np.argmax(silhouette_scores)], linestyle='--', color='gray')

plt.tight_layout()
plt.show()

best_k = k_range[np.argmax(silhouette_scores)]
print(f"Best k by silhouette: {best_k}")

Elbow method: Look for the "elbow" where adding more clusters stops significantly reducing inertia.

Silhouette score (better): Measures how similar a point is to its own cluster compared to other clusters.

• Score close to 1: point is well-clustered
• Score near 0: point is between clusters
• Score negative: point might be in the wrong cluster

Real-World Example: Customer Segmentation

import pandas as pd
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import KMeans
from sklearn.decomposition import PCA

# Customer data
np.random.seed(42)
n_customers = 1000
customer_data = pd.DataFrame({
    'age': np.random.normal(40, 12, n_customers).astype(int),
    'annual_income': np.random.normal(50000, 20000, n_customers),
    'spending_score': np.random.normal(50, 25, n_customers),
    'visits_per_month': np.random.exponential(3, n_customers),
    'avg_order_value': np.random.normal(80, 40, n_customers)
})
customer_data = customer_data.clip(lower=0)

# Scale features
scaler = StandardScaler()
X_scaled = scaler.fit_transform(customer_data)

# Find optimal k
silhouettes = []
for k in range(2, 10):
    km = KMeans(n_clusters=k, n_init=10, random_state=42)
    km.fit(X_scaled)
    silhouettes.append(silhouette_score(X_scaled, km.labels_))

best_k = range(2, 10)[np.argmax(silhouettes)]

# Fit final model
kmeans = KMeans(n_clusters=best_k, n_init=10, random_state=42)
customer_data['segment'] = kmeans.fit_predict(X_scaled)

# Analyze segments
segment_profiles = customer_data.groupby('segment').mean().round(1)
print("Customer Segment Profiles:")
print(segment_profiles)

# Name segments based on characteristics
# High income, high spending → Premium customers
# Low income, low spending → Budget shoppers
# etc.

K-Means Limitations and Alternatives

K-Means Assumes Spherical Clusters

from sklearn.datasets import make_moons, make_circles

# K-Means fails on non-spherical data
X_moons, _ = make_moons(n_samples=200, noise=0.05)

kmeans = KMeans(n_clusters=2)
labels = kmeans.fit_predict(X_moons)
# K-Means will give wrong clusters — it assumes circular/spherical shapes

# DBSCAN handles non-spherical clusters
from sklearn.cluster import DBSCAN

dbscan = DBSCAN(eps=0.15, min_samples=5)
labels_dbscan = dbscan.fit_predict(X_moons)
# DBSCAN correctly finds the moon shapes

Sensitivity to Outliers

from sklearn.cluster import MiniBatchKMeans

# For large datasets: MiniBatchKMeans is much faster
mini_kmeans = MiniBatchKMeans(
    n_clusters=4,
    batch_size=1000,
    n_init=3,
    random_state=42
)
mini_kmeans.fit(X_scaled)

Advanced: DBSCAN for Non-Spherical Clusters

from sklearn.cluster import DBSCAN

# eps: maximum distance between two points to be considered neighbors
# min_samples: minimum neighbors to form a core point
dbscan = DBSCAN(eps=0.5, min_samples=5)
labels = dbscan.fit_predict(X_scaled)

# DBSCAN assigns -1 to noise/outliers
n_clusters = len(set(labels)) - (1 if -1 in labels else 0)
n_noise = list(labels).count(-1)

print(f"Clusters found: {n_clusters}")
print(f"Noise points: {n_noise}")

DBSCAN advantages: finds arbitrary shapes, detects outliers, doesn't need k specified.

Evaluating Clustering Quality

from sklearn.metrics import silhouette_score, davies_bouldin_score, calinski_harabasz_score

labels = kmeans.labels_

# Silhouette score: higher is better (-1 to 1)
print(f"Silhouette: {silhouette_score(X_scaled, labels):.3f}")

# Davies-Bouldin: lower is better
print(f"Davies-Bouldin: {davies_bouldin_score(X_scaled, labels):.3f}")

# Calinski-Harabasz: higher is better
print(f"Calinski-Harabasz: {calinski_harabasz_score(X_scaled, labels):.1f}")

None of these metrics tell you if your clusters are meaningful — only domain knowledge can do that. A clustering is good if the resulting segments are actionable and make business sense.

Visualizing High-Dimensional Clusters

from sklearn.decomposition import PCA

# Reduce to 2D for visualization
pca = PCA(n_components=2)
X_2d = pca.fit_transform(X_scaled)

plt.figure(figsize=(10, 6))
scatter = plt.scatter(X_2d[:, 0], X_2d[:, 1], c=labels, cmap='tab10', alpha=0.6)
plt.colorbar(scatter, label='Cluster')
plt.xlabel(f'PC1 ({pca.explained_variance_ratio_[0]:.1%} variance)')
plt.ylabel(f'PC2 ({pca.explained_variance_ratio_[1]:.1%} variance)')
plt.title('Clusters in PCA Space')
plt.show()

When to Use K-Means vs Alternatives

Algorithm	Use When
K-Means	Clusters are spherical, roughly equal size, large datasets
DBSCAN	Arbitrary cluster shapes, many outliers, unknown k
Hierarchical	Need dendrogram, small dataset, unknown k
GMM	Soft cluster assignments, probabilistic framework
Spectral	Non-convex clusters, graph-based data

K-Means is a great default — fast, scalable, and effective when clusters are reasonably well-separated.

Next lesson: Principal Component Analysis — reducing dimensions to find the essential structure in data.