K-Means Clustering
Unsupervised Learning Concepts
Unlike supervised learning, unsupervised learning works with data that has no labels. The goal is to discover hidden patterns, structures, or groupings in the data.
Types of Unsupervised Learning
Why Clustering Matters
Applications:
- Customer segmentation
- Document topic grouping
- Image segmentation
- Anomaly detection
- Gene expression analysis
- Social network analysis
K-Means Algorithm
K-Means is one of the most popular and straightforward clustering algorithms.
Algorithm Steps
Mathematical Formulation
Complete Python Implementation
Finding Optimal K
Elbow Method
Plot inertia vs K and look for the "elbow" – the point where adding more clusters provides diminishing returns.
Silhouette Score
- : Well-clustered
- : On cluster boundary
- : Likely in wrong cluster
Architecture Diagram
Elbow plot + Silhouette plot:
K=2: Inertia high, Silhouette moderate
K=3: Inertia dropping, Silhouette high
K=4: Inertia elbow, Silhouette highest <- Optimal
K=5+: Inertia plateaus, Silhouette decreasing
K-Means Variants
Mini-Batch K-Means
For large datasets, Mini-Batch K-Means uses random subsets for faster training:
from sklearn.cluster import MiniBatchKMeans
import time
# Standard K-Means
start = time.time()
kmeans_standard = KMeans(n_clusters=4, random_state=42, n_init=10)
y_standard = kmeans_standard.fit_predict(X)
time_standard = time.time() - start
# Mini-Batch K-Means
start = time.time()
kmeans_mini = MiniBatchKMeans(n_clusters=4, random_state=42, batch_size=100, n_init=10)
y_mini = kmeans_mini.fit_predict(X)
time_mini = time.time() - start
print(f"Standard K-Means: Inertia={kmeans_standard.inertia_:.2f}, Time={time_standard:.4f}s")
print(f"Mini-Batch K-Means: Inertia={kmeans_mini.inertia_:.2f}, Time={time_mini:.4f}s")
Limitations and Alternatives
K-Means Limitations
K-Means Limitations Non-Spherical Splits wrong clusters Different Sizes Splits larger cluster Outliers outlier Pulls centroid away Unequal Density Merges sparse, splits dense When to Use Alternatives Non-spherical clusters → Use DBSCAN or Spectral Clustering Varying cluster sizes → Use Gaussian Mixture Models (GMM) Many outliers → Use DBSCAN (handles noise naturally)
Alternatives Comparison
from sklearn.cluster import DBSCAN, AgglomerativeClustering
from sklearn.datasets import make_moons, make_circles
from sklearn.metrics import silhouette_score, adjusted_rand_score
# Generate challenging datasets
X_moons, y_moons = make_moons(n_samples=500, noise=0.1, random_state=42)
X_circles, y_circles = make_circles(n_samples=500, noise=0.05, factor=0.5, random_state=42)
algorithms = {
'K-Means': lambda X: KMeans(n_clusters=3, random_state=42, n_init=10).fit_predict(X),
'DBSCAN': lambda X: DBSCAN(eps=0.3, min_samples=5).fit_predict(X),
'Hierarchical': lambda X: AgglomerativeClustering(n_clusters=3).fit_predict(X),
}
print("Clustering Algorithm Comparison:")
print("-" * 60)
print(f"{'Algorithm':<20} {'Moons ARI':<12} {'Circles ARI':<12}")
print("-" * 60)
for name, alg_func in algorithms.items():
labels_moons = alg_func(StandardScaler().fit_transform(X_moons))
labels_circles = alg_func(StandardScaler().fit_transform(X_circles))
ari_moons = adjusted_rand_score(y_moons, labels_moons)
ari_circles = adjusted_rand_score(y_circles, labels_circles)
print(f"{name:<20} {ari_moons:<12.3f} {ari_circles:<12.3f}")
Algorithm Comparison Summary
Practical Application
Key Takeaways
Practice Exercises
Exercise 1: Image Segmentation
# Use K-Means to segment an image into K colors:
# 1. Load an image (or use random pixels)
# 2. Reshape to (n_pixels, 3)
# 3. Apply K-Means with K=2, 4, 8, 16
# 4. Recreate image with cluster colors
# 5. Analyze compression ratio
Exercise 2: Anomaly Detection
# Use clustering for anomaly detection:
# 1. Generate normal data + anomalies
# 2. Apply K-Means and DBSCAN
# 3. Identify points far from centroids (K-Means)
# 4. Identify noise points (DBSCAN)
# 5. Compare detection rates
Exercise 3: Compare Clustering Algorithms
# Compare K-Means, DBSCAN, and Hierarchical:
# 1. Create 5 different synthetic datasets
# 2. Apply all three algorithms
# 3. Evaluate with ARI and Silhouette
# 4. Create visualization
# 5. Discuss which works best for each dataset
Exercise 4: Choosing K for Real Data
from sklearn.datasets import load_iris
X, y = load_iris(return_X_y=True)
# 1. Apply K-Means with K=2,3,4,5
# 2. Use elbow method and silhouette analysis
# 3. Compare with true labels (ARI)
# 4. Visualize using PCA
Summary Table
| Algorithm | K Required | Shape Assumption | Complexity | Best For |
|---|---|---|---|---|
| K-Means | Yes | Spherical | O(nK) | Spherical clusters |
| DBSCAN | No | Arbitrary | O(n log n) | Noisy, irregular shapes |
| Hierarchical | No | Any | O(n²) | Small datasets |
| GMM | Yes | Elliptical | O(nK) | Soft assignments |