K-Means Clustering & Voronoi Space Partitioning

Unsupervised machine learning algorithms find hidden patterns in unlabeled datasets. K-Means Clustering is one of the most popular clustering algorithms, partitioning $N$ observations into $K$ distinct clusters by minimizing the sum of squared distances between data points and their assigned cluster centroids.

1. Summary & Key Takeaways

• Expectation-Maximization (EM): K-Means iterates between two alternating steps:
  1. E-Step (Assignment): Assign each data point $x_i$ to the nearest centroid $\mu_k$.
  2. M-Step (Update): Recalculate each centroid position $\mu_k$ as the mean of all assigned points.
• Objective Function (Inertia): Minimizes within-cluster sum-of-squares (WCSS): $J = \sum_{k=1}^{K} \sum_{x \in S_k} \| x - \mu_k \|^2$
• Voronoi Tessellation: The resulting cluster boundaries partition feature space into convex Voronoi cells.

2. Interactive K-Means Playground

Use the interactive 2D cluster simulator below to step through Expectation-Maximization iterations and watch centroid crosshairs adjust to point clusters!

# K-Means Clustering in Python using NumPy
import numpy as np

def k_means(X, k, max_iters=100):
    # 1. Randomly initialize k centroids
    centroids = X[np.random.choice(X.shape[0], k, replace=False)]
    
    for _ in range(max_iters):
        # Step 1: Assign points to nearest centroid (E-Step)
        distances = np.linalg.norm(X[:, np.newaxis] - centroids, axis=2)
        labels = np.argmin(distances, axis=1)
        
        # Step 2: Update centroids to mean of assigned points (M-Step)
        new_centroids = np.array([X[labels == i].mean(axis=0) for i in range(k)])
        
        if np.all(centroids == new_centroids):
            break
        centroids = new_centroids
        
    return centroids, labels

3. Mathematical Foundations

Given a set of $N$ data points $(x_1, x_2, \dots, x_N) \in \mathbb{R}^d$, K-Means partitions them into $K$ sets $S = \{S_1, S_2, \dots, S_K\}$:

Euclidean Distance Metric

$d(x, \mu_k) = \sqrt{\sum_{j=1}^{d} (x_j - \mu_{k,j})^2}$

Centroid Update Rule

$\mu_k^{(t+1)} = \frac{1}{|S_k^{(t)}|} \sum_{x_i \in S_k^{(t)}} x_i$

4. Clustering Algorithm Comparison