K-Means Clustering Vector Quantization Unsupervised Learning

# K-Means Clustering: Vector Quantization & Unsupervised Learning

## Introduction & Motivation

K-Means: partition data into K clusters. Minimize within-cluster variance. Lloyd's algorithm: iterate assignment and update. Applications: data compression, image segmentation, customer segmentation.

Motivation: Unsupervised pattern discovery; scalable.

Applications: Clustering, compression, segmentation.

---

## Core Concepts & Theory

### Centroids

Cluster center; mean of points.

### Assignment Step

Assign points to nearest centroid.

### Update Step

Recompute centroids from assigned points.

---

## Mathematical Formulation

K-Means objective:
$$J = \sum_{i=1}^{K} \sum_{x \in C_i} \|x - \mu_i\|^2$$

Assignment:
$$C_i = \{x : \|x - \mu_i\| < \|x - \mu_j\| \forall j eq i\}$$

Centroid update:
$$\mu_i = \frac{1}{|C_i|} \sum_{x \in C_i} x$$

---

## Advanced Theory & Extensions

### K-Means++

Smart centroid initialization.

### Mini-Batch K-Means

Stochastic updates; scalability.

### Hierarchical K-Means

Tree structure; fast retrieval.

---

## Computational Considerations

Iteration: O(N·K·D) where N=points, K=clusters, D=dimensions.

Convergence: Typically 10-100 iterations.

Overall: O(N·K·D·iterations).

---

## Practical Implementation Strategies

### Initialization

K-Means++ or random selection.

### Convergence Criterion

Centroid movement threshold.

### Restart Strategy

Multiple random initializations.

---

## Benchmark Datasets & Evaluation

Iris: Classic clustering task.

MNIST: Digit clustering.

Image Segmentation: Benchmark suite.

---

## Key Challenges & Limitations

### Initialization Sensitivity

Random initialization affects results.

### K Selection

No principled method; elbow/silhouette.

### Spherical Assumption

Assumes roughly spherical clusters.

---

## Hyperparameter Tuning

K (number of clusters): Elbow method, silhouette score.

Initialization: K-Means++; n_init runs.

Max iterations: 100-300; convergence.

---

## Real-World Applications & Case Studies

Customer Segmentation: Market analysis.

Image Compression: Color quantization.

Document Clustering: Topic grouping.

---

## Integration with Other Methods

K-Means + Feature Reduction → visualization.

K-Means + Classifier → semi-supervised.

---

## Summary & Key Takeaways

K-Means via iterative centroid optimization enables scalable unsupervised clustering through partition minimization.

Principles:
1. Lloyd's algorithm: assign-update cycle.
2. Objective: within-cluster variance.
3. Initialization: K-Means++ strategy.
4. Convergence: centroid stability.
5. Extensions: mini-batch, hierarchical.

---

---

## Appendix: Practical Labs

### Lab 1: K-Means Assignment

import numpy as np

def kmeans_assign(X, centroids):
 """Assign points to nearest centroid"""
 # Distances to all centroids
 distances = np.sqrt(((X[:, None, :] - centroids[None, :, :]) ** 2).sum(axis=2))
 
 # Nearest centroid
 assignments = np.argmin(distances, axis=1)
 
 return assignments

# Test
np.random.seed(42)
X = np.random.randn(100, 2)
centroids = np.random.randn(3, 2)

assignments = kmeans_assign(X, centroids)

assert assignments.shape == (100,), "Assignment shape"
assert np.all((assignments >= 0) & (assignments < 3)), "Valid cluster assignments"
print("✓ K-Means assignment working")

if __name__ == "__main__":
 print("Lab 1: KMeansAssignment - PASSED")

### Lab 2: K-Means Update

import numpy as np

def kmeans_update_centroids(X, assignments, K):
 """Update centroids from assignments"""
 centroids = np.zeros((K, X.shape[1]))
 
 for k in range(K):
 points_in_cluster = X[assignments == k]
 if len(points_in_cluster) > 0:
 centroids[k] = points_in_cluster.mean(axis=0)
 else:
 # Empty cluster: reinitialize randomly
 centroids[k] = X[np.random.randint(len(X))]
 
 return centroids

# Test
np.random.seed(42)
X = np.random.randn(100, 2)
assignments = np.random.randint(0, 3, 100)

centroids = kmeans_update_centroids(X, assignments, 3)

assert centroids.shape == (3, 2), "Centroids shape"
print("✓ K-Means update working")

if __name__ == "__main__":
 print("Lab 2: KMeansUpdate - PASSED")

### Lab 3: K-Means Objective

import numpy as np

def kmeans_objective(X, centroids, assignments):
 """Compute K-Means objective (within-cluster variance)"""
 total_variance = 0
 
 for k in range(len(centroids)):
 points_in_cluster = X[assignments == k]
 if len(points_in_cluster) > 0:
 distances_sq = ((points_in_cluster - centroids[k]) ** 2).sum(axis=1)
 total_variance += distances_sq.sum()
 
 return total_variance

# Test
np.random.seed(42)
X = np.random.randn(100, 2)
centroids = np.random.randn(3, 2)
assignments = np.random.randint(0, 3, 100)

obj = kmeans_objective(X, centroids, assignments)

assert obj >= 0, "Objective non-negative"
assert np.isfinite(obj), "Objective finite"
print("✓ K-Means objective working")

if __name__ == "__main__":
 print("Lab 3: KMeansObjective - PASSED")

### Lab 4: Silhouette Score

import numpy as np

def silhouette_score(X, assignments, centroids):
 """Compute silhouette score for clustering"""
 silhouette_vals = []
 
 for i in range(len(X)):
 # Within-cluster distance
 cluster = assignments[i]
 within_distances = np.linalg.norm(X[i] - X[assignments == cluster], axis=1)
 a = within_distances.mean()
 
 # Between-cluster distance (nearest other cluster)
 between_distances = []
 for k in range(len(centroids)):
 if k != cluster:
 other_distances = np.linalg.norm(X[i] - X[assignments == k], axis=1)
 between_distances.append(other_distances.mean())
 
 if between_distances:
 b = min(between_distances)
 silhouette = (b - a) / (max(a, b) + 1e-8)
 silhouette_vals.append(silhouette)
 
 return np.mean(silhouette_vals) if silhouette_vals else 0

# Test
np.random.seed(42)
X = np.random.randn(100, 2)
centroids = np.random.randn(3, 2)
assignments = np.random.randint(0, 3, 100)

score = silhouette_score(X, assignments, centroids)

assert -1 <= score <= 1, "Silhouette in [-1, 1]"
print("✓ Silhouette score working")

if __name__ == "__main__":
 print("Lab 4: SilhouetteScore - PASSED")