k-means clustering unsupervised learning
# K-Means Clustering & Unsupervised Learning
## Introduction & Motivation
K-Means clustering is one of the most widely used and practical unsupervised learning algorithms in machine learning. Unlike supervised learning—where we have labeled examples guiding model training—unsupervised learning discovers hidden structure, patterns, and groupings within data without explicit labels. K-Means addresses a fundamental problem: given a dataset of unlabeled points, partition it into k clusters such that points within clusters are similar to each other and dissimilar to points in other clusters.
Motivation spans multiple domains. In customer segmentation, retailers cluster purchase histories to identify distinct customer groups and tailor marketing strategies. In image compression, K-Means quantizes pixel colors to a small set of representative colors, reducing file size. In gene expression analysis, researchers cluster cells to discover cell types and subtypes in single-cell data. In recommendation systems, clustering users or items provides the foundation for collaborative filtering.
K-Means combines simplicity, interpretability, and computational efficiency with remarkable empirical performance. Its core algorithm—iteratively assigning points to nearest cluster centers and updating centers—is intuitive and runs in polynomial time. Yet K-Means raises profound questions: How do we choose the number of clusters k? How sensitive is the solution to initialization? What guarantees exist on solution quality? This article covers the algorithm, theory, practical strategies, and integration with modern machine learning pipelines.
---
## Core Concepts & Theory
### The Clustering Problem
Clustering seeks to partition data \mathbf{X} = \{\mathbf{x}_1, \ldots, \mathbf{x}_n\} with \mathbf{x}_i \in \mathbb{R}^d into k non-overlapping groups (clusters). A clustering \mathcal{C} = \{C_1, \ldots, C_k\} assigns each point to exactly one cluster. The quality of a clustering depends on minimizing within-cluster variance (compactness) and maximizing between-cluster variance (separation).
### K-Means Objective
K-Means minimizes the sum of squared distances from points to their assigned cluster centers:
$$J = \sum_{i=1}^{n} \sum_{j=1}^{k} r_{ij} \| \mathbf{x}_i - \boldsymbol{\mu}_j \|^2$$
where r_{ij} \in \{0, 1\} is an indicator (r_{ij} = 1 if point i is assigned to cluster j), and \boldsymbol{\mu}_j is the center of cluster j. This objective is known as inertia and directly measures within-cluster compactness.
### Lloyd's Algorithm
The standard K-Means algorithm (Lloyd's algorithm) alternates between two steps until convergence:
1. Assignment Step: Assign each point to the nearest cluster center:
$$r_{ij} = \begin{cases} 1 & ext{if } j = \arg\min_{\ell} \| \mathbf{x}_i - \boldsymbol{\mu}_{\ell} \|^2 \\ 0 & ext{otherwise} \end{cases}$$
2. Update Step: Recompute cluster centers as the mean of assigned points:
$$\boldsymbol{\mu}_j = \frac{\sum_{i=1}^{n} r_{ij} \mathbf{x}_i}{\sum_{i=1}^{n} r_{ij}}$$
These steps repeat until assignments stabilize (convergence) or a maximum iteration count is reached.
### Convergence Properties
Lloyd's algorithm is guaranteed to converge in finite iterations because:
1. The objective J is non-increasing after each step (inertia decreases or stays constant).
2. The objective is lower-bounded by zero.
3. The finite number of possible assignments means termination.
However, convergence is to a local optimum, not necessarily the global optimum. Different initializations yield different solutions.
---
## Mathematical Formulation
### Hard Assignment K-Means
The standard formulation minimizes inertia over all possible assignments:
$$\min_{\mathbf{r}, \boldsymbol{\mu}} \sum_{i=1}^{n} \sum_{j=1}^{k} r_{ij} \| \mathbf{x}_i - \boldsymbol{\mu}_j \|^2 \quad ext{s.t.} \quad \sum_{j=1}^{k} r_{ij} = 1 \, \forall i$$
The constraint ensures each point belongs to exactly one cluster.
### Centroid Computation
Given an assignment, the optimal centroid minimizes the within-cluster sum of squares:
$$\boldsymbol{\mu}_j^* = \arg\min_{\boldsymbol{\mu}} \sum_{i: r_{ij}=1} \| \mathbf{x}_i - \boldsymbol{\mu} \|^2$$
Taking the derivative and setting to zero:
$$\boldsymbol{\mu}_j^* = \frac{1}{n_j} \sum_{i: r_{ij}=1} \mathbf{x}_i$$
where n_j = \sum_i r_{ij} is the cluster size.
### Soft Assignment & Expectation-Maximization
A probabilistic variant replaces hard assignments with soft (probabilistic) assignments. Define \pi_j as the prior probability of cluster j and p(\mathbf{x} | j) as the likelihood of \mathbf{x} given cluster j. The posterior probability of cluster membership is:
$$p(j | \mathbf{x}_i) = \frac{\pi_j p(\mathbf{x}_i | j)}{\sum_{\ell=1}^{k} \pi_{\ell} p(\mathbf{x}_i | \ell)}$$
Expectation-Maximization (EM) iteratively optimizes this probabilistic model. K-Means can be viewed as a limiting case of Gaussian Mixture Models (GMM) with spherical, equal-variance covariances as variance approaches zero.
---
## Advanced Theory & Extensions
### K-Means++: Intelligent Initialization
Standard K-Means is highly sensitive to initialization. K-Means++ (Arthur & Vassilvitskii, 2007) addresses this by choosing initial centers to be far apart:
1. Choose the first center uniformly at random from \mathbf{X}.
2. For j = 2, \ldots, k: choose the next center \mathbf{c}_j with probability proportional to D(\mathbf{x}_i)^2, where D(\mathbf{x}_i) is the distance from \mathbf{x}_i to the nearest already-chosen center.
K-Means++ provably reduces the approximation ratio. Expected inertia is O(\log k) times the optimal, compared to arbitrary initialization which can be O(k) times suboptimal.
### Elkan's Algorithm
Elkan (2003) accelerates Lloyd's algorithm using triangle inequalities and cached distances. By tracking lower and upper bounds on distances, many assignment distance computations are skipped, reducing runtime from O(nkd \cdot i) to approximately O(nkd) without computing all nkd distances per iteration.
### Mini-Batch K-Means
For large datasets, mini-batch K-Means processes random subsets of data, updating centers incrementally. This reduces computation from O(nkd) per iteration to O(bkd) where b is batch size. Trade-off: slightly lower solution quality for massive scalability.
### Kernel K-Means
Extends K-Means to nonlinear clustering via kernel trick. Data is implicitly mapped to a high-dimensional space \phi(\mathbf{x}), and clustering is performed in that space without explicit coordinates. Enables clustering on non-Euclidean data (e.g., kernels for graphs, sequences).
### Spectral Clustering
Uses eigenvectors of the data affinity graph's Laplacian matrix to perform clustering in a lower-dimensional space before applying K-Means. Particularly effective on non-convex cluster shapes and data on manifolds.
---
## Computational Considerations
### Time Complexity
Per Iteration: O(nkd)
- n points, k cluster centers, d dimensions.
- Each point is compared to k centers; each comparison costs O(d).
Total: O(nkd \cdot i) where i is the number of iterations until convergence. In practice, i is often small (5–20 iterations).
Space: O(nk + kd)
- Storing assignments: O(nk) (can reduce to O(n) with incremental updates).
- Storing centers: O(kd).
### Scalability Improvements
- Mini-batch K-Means: Reduces per-iteration cost to O(bkd) with small b.
- Elkan's algorithm: Prunes distance computations via triangle inequalities; effective when k is large.
- GPU acceleration: Parallelizing distance computations and assignments across thousands of cores.
- Approximate nearest neighbors: Use approximate kNN structures (e.g., LSH) to avoid exact distance computation.
### Practical Runtime on Common Datasets
- MNIST (70K, 784D, k=10): ~1–2 seconds (standard K-Means).
- CIFAR-10 (60K, 3072D, k=10): ~3–5 seconds.
- Text (millions of words, 10K vocabulary): ~seconds–minutes with mini-batch variant.
---
## Practical Implementation Strategies
### Choosing the Number of Clusters k
1. Elbow Method: Plot inertia (or silhouette score) vs. k. An "elbow" in the curve suggests an optimal k. This is heuristic but practical.
2. Silhouette Score: For each point, compute s_i = \frac{b_i - a_i}{\max(a_i, b_i)}, where a_i is average distance to same-cluster points and b_i is average distance to nearest other cluster. Silhouette ranges from -1 to 1; higher is better. Choose k maximizing mean silhouette.
3. Gap Statistic: Compare inertia of real data to uniform random data. The "gap" suggests if data exhibits structure at a given k.
4. Domain Knowledge: Often, k is determined by problem requirements (e.g., number of customer segments, desired compression levels).
### Initialization Strategies
- K-Means++: Recommended default; improves solution quality and convergence.
- Random Restart: Run standard K-Means multiple times with different random initializations, keep best solution.
- Warm Start: Initialize from previous run or a related task.
### Preprocessing
Standardization: Features should be scaled to mean 0, variance 1. Otherwise, high-variance features dominate clustering.
$$\mathbf{x}'_i = \frac{\mathbf{x}_i - \boldsymbol{\mu}}{\boldsymbol{\sigma}}$$
Feature Selection: Remove irrelevant or redundant features; K-Means is sensitive to dimensionality (curse of dimensionality).
### Handling Empty Clusters
When an iteration assigns no points to a cluster, the center becomes undefined. Strategies:
- Re-initialize that center randomly.
- Assign it to a point from the cluster with largest inertia (splitting dense clusters).
- Reinitialize from data if initialization strategy allows.
---
## Benchmark Datasets & Evaluation
### Synthetic Datasets
- Blobs: Gaussian-distributed clusters; ground truth known. Tests basic performance.
- Moons / Circles: Non-convex clusters; reveals K-Means weakness on complex shapes.
- Varied Variance: Clusters with different sizes and densities; tests robustness.
### Real Benchmark Datasets
- Iris: 150 samples, 4 features, 3 classes. Fast; traditional benchmark.
- MNIST: 70,000 handwritten digits, 784 features, 10 classes. Larger scale; labels available for evaluation.
- 20 Newsgroups: Document clustering; high-dimensional sparse text data.
- STL-10: Image dataset; larger scale and complexity than MNIST.
### Evaluation Metrics (Unsupervised)
- Inertia (Within-Cluster Sum of Squares): Lower is better. But inertia decreases monotonically with k; not absolute measure.
- Silhouette Score: Ranges -1 to 1; measures how similar points are to their own cluster vs. other clusters.
- Calinski-Harabasz Index: Ratio of between-cluster to within-cluster variance; higher is better.
- Davies-Bouldin Index: Average dissimilarity between each cluster and its most similar cluster; lower is better.
### Evaluation Metrics (If Labels Available)
- Purity: Fraction of points whose cluster matches majority class in ground truth.
- Normalized Mutual Information (NMI): Mutual information between clustering and labels, normalized.
- Adjusted Rand Index (ARI): Measures agreement between two clusterings; accounts for chance.
---
## Key Challenges & Limitations
### Non-Convex Clusters
K-Means assumes clusters are roughly spherical (convex). Crescent-shaped, elongated, or multi-lobed clusters are often misclassified. Solution: Use spectral clustering or density-based methods (DBSCAN).
### Sensitive to Initialization
Different random initializations yield different local optima. Solution quality can vary significantly. Mitigations: K-Means++, multiple random restarts, warm starts.
### Difficulty Determining k
Choosing the right number of clusters is subjective. Elbow method is heuristic; gap statistic and silhouette provide quantitative guidance but are not always decisive. Reality: Often domain knowledge or downstream task performance guides k.
### Sensitivity to Outliers
Outliers can distort cluster centers. A single outlier far from others can pull a center away, degrading clustering quality. Solutions: Robust variants (e.g., K-Medoids), outlier preprocessing, or capping extreme values.
### Curse of Dimensionality
In high dimensions, all pairwise distances become similar; notion of "nearest neighbor" degrades. Distances lose discriminative power. Mitigations: Dimensionality reduction (PCA) before clustering, feature selection, or distance metrics robust to high dimensions.
### Computational Cost at Extreme Scales
Although O(nkd) per iteration is reasonable, processing billions of points becomes expensive. Solutions: Mini-batch K-Means, approximate nearest neighbors, distributed computing (MapReduce, Spark).
---
## Hyperparameter Tuning
### Number of Clusters k
Use elbow method, silhouette score, or gap statistic. If domain knowledge specifies k, use it directly.
### Initialization Method
- K-Means++: Default choice; provable guarantees.
- Random: Faster initialization but potentially lower quality; use with multiple restarts.
### Distance Metric
- Euclidean: Default; assumes continuous, scale-invariant data (after standardization).
- Manhattan (L1): More robust to outliers than L2.
- Cosine: For text data, sparse data, or when direction (not magnitude) matters.
- Custom kernels: Via kernel K-Means.
### Convergence Criteria
- Max iterations: Stop after fixed number of iterations (e.g., 300).
- Tolerance: Stop when change in centers is below threshold (e.g., 10^{-4}).
- No improvement: Stop if inertia improves less than threshold over last m iterations.
### Mini-Batch Settings (if using mini-batch variant)
- Batch size: Typically 256–1024. Larger batches = better quality, slower; smaller = faster, more variance.
- Number of batches: Determines total passes over data; more passes = better convergence.
Tuning Strategy: Grid search or random search over k and initialization methods; evaluate on validation set using task-specific metrics (downstream task performance, domain metrics).
---
## Real-World Applications & Case Studies
### Customer Segmentation
Scenario: E-commerce platform with millions of users, purchase histories, and browsing behavior.
Application: K-Means clusters users by spending patterns, engagement frequency, and product preferences. Marketing teams target each segment with personalized campaigns (e.g., high-value vs. price-sensitive vs. occasional users).
Outcome: Improved marketing ROI, personalized recommendations, reduced churn.
### Image Compression & Quantization
Scenario: Compress images to reduce storage and transmission bandwidth.
Application: Treat pixels as data points; K-Means clusters pixel colors to k representative colors (e.g., k=16 from 256). Replace each pixel with nearest cluster center, reducing storage.
Outcome: Compression ratios of 10–100x with minimal perceptual quality loss for k=256.
### Gene Expression & Cell Typing
Scenario: Single-cell RNA sequencing measures expression of thousands of genes across millions of cells.
Application: K-Means clusters cells by expression profile to identify cell types and subtypes. Combined with marker gene analysis, researchers annotate clusters biologically.
Outcome: Discovery of rare cell populations, disease-associated subtypes, developmental trajectories.
### Document & Topic Clustering
Scenario: Corpus of millions of documents (news, papers, social media).
Application: K-Means clusters documents by TF-IDF or embedding vectors. Discovers latent topics and groups related documents.
Outcome: Enables content organization, recommendation, and trend detection.
---
## Integration with Other Methods
### K-Means + Dimensionality Reduction
Pipeline: Reduce dimensionality via PCA or UMAP, then apply K-Means on reduced features. Improves efficiency and often solution quality (noise reduction).
### K-Means + Classification
Semi-supervised use: Cluster unlabeled data, then train classifier on labeled data within each cluster. Can improve classifier generalization.
### K-Means + Hierarchical Clustering
Ensemble approach: Run K-Means with different k values, then hierarchically merge clusters based on centroid distance. Reveals hierarchical cluster structure.
### K-Means + Anomaly Detection
Outlier detection: Points far from their assigned cluster center are flagged as outliers. Use K-Means as preprocessing step.
### K-Means as Initialization for EM
Initialization strategy: Run K-Means to initialize Gaussian Mixture Model centers and variances. EM then refines probabilistic model.
---
## Future Research Directions
### Scalability to Trillion-Scale Data
Distributed K-Means on edge devices and cloud clusters; federated clustering preserving privacy while discovering global patterns.
### Adaptive k Selection
Algorithms that automatically discover appropriate k from data without user specification. Theoretical and empirical advances in gap statistics and silhouette methods.
### Robust Clustering
Clustering robust to outliers, noise, and adversarial perturbations. Connections to robust statistics and distributionally-robust optimization.
### Online & Incremental Clustering
Updating clusters as new data streams in, without full retraining. Important for real-time applications.
### Non-Euclidean Clustering
Extending K-Means to non-Euclidean geometries (hyperbolic space, graphs, manifolds) while maintaining computational efficiency.
### Interpretability & Explainability
Understanding why K-Means assigns points to clusters; identifying cluster-defining features; visual and interactive tools.
---
## Summary & Key Takeaways
K-Means is a foundational unsupervised learning algorithm combining simplicity, interpretability, and practical efficiency. Key insights:
1. Core Algorithm: Lloyd's alternating assignment-update procedure converges to a local optimum in polynomial time.
2. Initialization Matters: K-Means++ significantly improves solution quality with minimal computational overhead.
3. Choosing k: Use elbow method, silhouette score, or gap statistic; domain knowledge is invaluable.
4. Scalability: Mini-batch and approximate variants scale to massive datasets; GPU acceleration available.
5. Integration: K-Means works synergistically with dimensionality reduction, downstream classifiers, anomaly detection, and probabilistic models.
6. Limitations: Sensitive to initialization, assumes convex clusters, struggles with high dimensions. Robust variants and ensemble approaches mitigate these.
K-Means remains essential for exploratory data analysis, segmentation, compression, and as a building block in modern ML pipelines—from small datasets to web-scale applications.
---
---
## Appendix: Practical Labs
### Lab 1: K-Means from Scratch and Convergence Analysis
Implement K-Means manually; track inertia and convergence behavior.
import numpy as np
import matplotlib.pyplot as plt
from sklearn.preprocessing import StandardScaler
def kmeans_from_scratch(X, k, max_iter=100, tol=1e-4, random_state=42):
"""
K-Means implementation from scratch.
Args:
X: data matrix (n_samples, n_features)
k: number of clusters
max_iter: maximum iterations
tol: convergence tolerance for center movement
random_state: seed for reproducibility
Returns:
centers: cluster centers (k, n_features)
labels: cluster assignments (n_samples,)
inertia_history: inertia at each iteration
"""
np.random.seed(random_state)
n_samples, n_features = X.shape
# Initialize centers randomly from data points
indices = np.random.choice(n_samples, k, replace=False)
centers = X[indices].copy()
inertia_history = []
for iteration in range(max_iter):
# Assignment step: assign each point to nearest center
distances = np.linalg.norm(X[:, np.newaxis, :] - centers[np.newaxis, :, :], axis=2)
labels = np.argmin(distances, axis=1)
# Compute inertia
inertia = 0
for j in range(k):
mask = labels == j
if np.sum(mask) > 0:
cluster_points = X[mask]
inertia += np.sum((cluster_points - centers[j]) ** 2)
inertia_history.append(inertia)
# Update step: recompute centers
new_centers = np.zeros_like(centers)
for j in range(k):
mask = labels == j
if np.sum(mask) > 0:
new_centers[j] = X[mask].mean(axis=0)
else:
# Handle empty cluster: reinitialize randomly
new_centers[j] = X[np.random.choice(n_samples)]
# Check convergence
center_shift = np.linalg.norm(new_centers - centers)
centers = new_centers
if center_shift < tol:
print(f"Converged at iteration {iteration}")
break
return centers, labels, np.array(inertia_history)
# Generate synthetic data with known clusters
np.random.seed(42)
n_samples_per_cluster = 100
cluster_centers_true = np.array([[0, 0], [5, 0], [2.5, 5]])
k_true = len(cluster_centers_true)
X_list = [
cluster_centers_true[j] + np.random.randn(n_samples_per_cluster, 2) * 0.8
for j in range(k_true)
]
X = np.vstack(X_list)
# Standardize
scaler = StandardScaler()
X = scaler.fit_transform(X)
# Run K-Means
centers, labels, inertia_history = kmeans_from_scratch(X, k=3, max_iter=50)
print("K-Means Convergence Analysis:")
print(f"Initial inertia: {inertia_history[0]:.4f}")
print(f"Final inertia: {inertia_history[-1]:.4f}")
print(f"Inertia reduction: {(1 - inertia_history[-1]/inertia_history[0])*100:.2f}%")
print(f"Number of iterations: {len(inertia_history)}")
# Tests: Verify inertia is monotonically decreasing
assert np.all(np.diff(inertia_history) <= 1e-6), "Inertia not monotonically decreasing!"
print("✓ Inertia is monotonically non-increasing")
# Test: Final inertia should be significantly smaller
assert inertia_history[-1] < inertia_history[0] * 0.5, "Inertia reduction insufficient"
print("✓ Inertia converged to stable value")
if __name__ == "__main__":
print("Lab 1: K-Means from Scratch - PASSED")### Lab 2: K-Means++ vs Random Initialization
Compare initialization strategies; evaluate solution quality.
import numpy as np
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score
# Generate data
np.random.seed(42)
X, y_true = make_blobs(n_samples=300, centers=4, n_features=2, cluster_std=0.8, random_state=42)
scaler = StandardScaler()
X = scaler.fit_transform(X)
k = 4
# Test multiple random initializations
random_inertias = []
for trial in range(10):
km_random = KMeans(n_clusters=k, init='random', n_init=1, random_state=trial, max_iter=100)
km_random.fit(X)
random_inertias.append(km_random.inertia_)
# Test K-Means++ (default)
kmeans_pp_inertias = []
for trial in range(10):
km_pp = KMeans(n_clusters=k, init='k-means++', n_init=1, random_state=trial, max_iter=100)
km_pp.fit(X)
kmeans_pp_inertias.append(km_pp.inertia_)
random_inertias = np.array(random_inertias)
kmeans_pp_inertias = np.array(kmeans_pp_inertias)
print("Initialization Comparison:")
print(f"Random init - Mean inertia: {random_inertias.mean():.4f}, Std: {random_inertias.std():.4f}")
print(f"K-Means++ - Mean inertia: {kmeans_pp_inertias.mean():.4f}, Std: {kmeans_pp_inertias.std():.4f}")
print(f"K-Means++ is {random_inertias.mean() / kmeans_pp_inertias.mean():.2f}x better on average")
# K-Means++ should have lower mean inertia and lower variance
assert kmeans_pp_inertias.mean() < random_inertias.mean(), "K-Means++ not better than random"
assert kmeans_pp_inertias.std() < random_inertias.std(), "K-Means++ not more stable than random"
print("✓ K-Means++ outperforms random initialization")
# Test: Silhouette scores should be higher for K-Means++
km_pp = KMeans(n_clusters=k, init='k-means++', n_init=1, random_state=42, max_iter=100)
labels_pp = km_pp.fit_predict(X)
sil_pp = silhouette_score(X, labels_pp)
km_random = KMeans(n_clusters=k, init='random', n_init=1, random_state=0, max_iter=100)
labels_random = km_random.fit_predict(X)
sil_random = silhouette_score(X, labels_random)
print(f"Silhouette score (K-Means++): {sil_pp:.4f}")
print(f"Silhouette score (Random): {sil_random:.4f}")
assert sil_pp > 0.4, "Silhouette score too low"
print("✓ Silhouette scores indicate good clustering")
if __name__ == "__main__":
print("Lab 2: K-Means++ vs Random Initialization - PASSED")### Lab 3: Elbow Method and Silhouette Analysis
Determine optimal number of clusters using multiple heuristics.
import numpy as np
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import KMeans
from sklearn.metrics import silhouette_score, davies_bouldin_score, calinski_harabasz_score
# Generate data with true k=3 clusters
np.random.seed(42)
X, y_true = make_blobs(n_samples=300, centers=3, n_features=2, cluster_std=0.6, random_state=42)
scaler = StandardScaler()
X = scaler.fit_transform(X)
# Test k from 2 to 8
k_values = range(2, 9)
inertias = []
silhouette_scores = []
davies_bouldin_scores = []
calinski_harabasz_scores = []
for k in k_values:
km = KMeans(n_clusters=k, init='k-means++', n_init=10, max_iter=100, random_state=42)
labels = km.fit_predict(X)
inertias.append(km.inertia_)
silhouette_scores.append(silhouette_score(X, labels))
davies_bouldin_scores.append(davies_bouldin_score(X, labels))
calinski_harabasz_scores.append(calinski_harabasz_score(X, labels))
print("Cluster Quality Metrics:")
for k, inertia, sil, db, ch in zip(k_values, inertias, silhouette_scores, davies_bouldin_scores, calinski_harabasz_scores):
print(f"k={k}: Inertia={inertia:.2f}, Silhouette={sil:.3f}, Davies-Bouldin={db:.3f}, Calinski-Harabasz={ch:.1f}")
# Test: Inertia should decrease monotonically
assert np.all(np.diff(inertias) < 0), "Inertia not strictly decreasing!"
print("✓ Inertia decreases monotonically with k")
# Test: For true k=3, silhouette should be high
sil_at_k3 = silhouette_scores[1] # k=3 is at index 1 (k_values starts at 2)
assert sil_at_k3 > 0.4, f"Silhouette at k=3 too low: {sil_at_k3}"
print(f"✓ Silhouette score at true k=3 is {sil_at_k3:.3f} (good)")
# Test: Davies-Bouldin should be low at true k
db_at_k3 = davies_bouldin_scores[1]
assert db_at_k3 < 1.5, f"Davies-Bouldin at k=3 too high: {db_at_k3}"
print(f"✓ Davies-Bouldin at k=3 is {db_at_k3:.3f} (low is good)")
# Test: Calinski-Harabasz should be high at true k
ch_at_k3 = calinski_harabasz_scores[1]
assert ch_at_k3 > 50, f"Calinski-Harabasz at k=3 too low: {ch_at_k3}"
print(f"✓ Calinski-Harabasz at k=3 is {ch_at_k3:.1f} (high is good)")
if __name__ == "__main__":
print("Lab 3: Elbow Method and Silhouette Analysis - PASSED")### Lab 4: Mini-Batch K-Means Scalability
Compare standard K-Means with mini-batch variant on large data.
import numpy as np
import time
from sklearn.datasets import make_blobs
from sklearn.preprocessing import StandardScaler
from sklearn.cluster import KMeans, MiniBatchKMeans
# Generate large dataset
np.random.seed(42)
n_samples = 50000
n_features = 100
k = 10
print(f"Generating dataset: {n_samples} samples, {n_features} features, {k} clusters...")
X, y_true = make_blobs(n_samples=n_samples, centers=k, n_features=n_features, cluster_std=0.8, random_state=42)
scaler = StandardScaler()
X = scaler.fit_transform(X)
# Standard K-Means
print("
Running standard K-Means...")
start = time.time()
km_standard = KMeans(n_clusters=k, init='k-means++', n_init=1, max_iter=100, random_state=42)
km_standard.fit(X)
time_standard = time.time() - start
inertia_standard = km_standard.inertia_
print(f"Standard K-Means - Time: {time_standard:.2f}s, Inertia: {inertia_standard:.2f}")
# Mini-Batch K-Means
print("Running mini-batch K-Means...")
start = time.time()
km_mini = MiniBatchKMeans(n_clusters=k, init='k-means++', batch_size=256, n_init=1, max_iter=100, random_state=42)
km_mini.fit(X)
time_mini = time.time() - start
inertia_mini = km_mini.inertia_
print(f"Mini-Batch K-Means - Time: {time_mini:.2f}s, Inertia: {inertia_mini:.2f}")
print(f"Mini-Batch is {time_standard/time_mini:.1f}x faster")
# Tests: Mini-batch should be faster
assert time_mini < time_standard, "Mini-batch not faster!"
print("✓ Mini-batch K-Means is faster than standard")
# Test: Inertia should be comparable (mini-batch may be slightly higher)
inertia_ratio = inertia_mini / inertia_standard
assert 0.95 < inertia_ratio < 1.1, f"Inertia ratio too extreme: {inertia_ratio}"
print(f"✓ Inertia ratio (mini/standard): {inertia_ratio:.4f} (acceptable)")
# Test: Cluster centers should be reasonably close (mini-batch is stochastic, so tolerance is higher)
center_distance = np.mean(np.linalg.norm(km_standard.cluster_centers_ - km_mini.cluster_centers_, axis=1))
assert center_distance < 2.0, f"Cluster centers too different: {center_distance}"
print(f"✓ Mean center distance: {center_distance:.4f} (reasonably aligned)")
if __name__ == "__main__":
print("Lab 4: Mini-Batch K-Means Scalability - PASSED")