2. Classification: Clustering

K-Means, Gaussian Mixture Models, EM algorithm, unsupervised learning, dimensionality reduction

1. Classification vs Object Detection

These are two fundamentally different computer vision tasks that are frequently confused.

Left: classification assigns a single label ("CAT") to the whole image. Right: detection draws bounding boxes around every object and labels each one.

2. Supervised vs Unsupervised Learning

Supervised learning uses labeled input/target pairs; unsupervised learning discovers hidden structure in unlabeled data.

This module covers unsupervised clustering. The running example is handwritten digit classification using the MNIST dataset (28x28 pixel images of digits 0–9), where the goal is to group similar-looking images together without using labels.

MNIST digits 0–9. Wide variability in writing style motivates machine learning rather than hand-crafted rules.

3. K-Means Clustering

K-Means is the most fundamental clustering algorithm. The intuition: given a scatter plot of $N$ data points, partition them into $K$ groups such that each group's points are as close as possible to their group's center.

Initial data: 5 natural clusters visible in 2D space. Goal is to recover these groups automatically.

Algorithm — Intuitive Steps

1. Initialize: Randomly place $K$ cluster centers (centroids) in the data space.
2. Assign: Assign each data point to its nearest cluster center.
3. Update: Recompute each cluster center as the centroid (mean) of all points assigned to it.
4. Repeat steps 2–3 until assignments stop changing (convergence).

Voronoi Regions and Classification

After convergence, the cluster centers define Voronoi regions: every point in space is assigned to the nearest center. New test points can be classified by finding the nearest cluster center.

At convergence, the 5 cluster regions are stable and well-aligned with the natural groups.

Final labeled cluster regions. New points are classified by nearest-center assignment.

4. K-Means Mathematics

Euclidean Distance

Distance between two points in $D$ dimensions:

In 2D, Euclidean distance is the hypotenuse of the right triangle formed by horizontal and vertical differences.

Cost Function (Distortion)

Alternating Optimization

K-Means minimizes $J$ by alternating two steps:

Convergence and Choosing K

K-Means is guaranteed to converge because $J$ cannot increase at any step. For choosing $K$:

• Compute optimal clustering for all candidate $K$ values.
• Plot $J$ vs $K$: use the elbow method — pick the $K$ where $J$ drops steeply then levels off.
• $J$ always decreases as $K$ increases, so the elbow is the best tradeoff.

K-Means generalizes naturally to any number of dimensions — the math is identical.

5. K-Means Applied to Digit Classification

Images as Vectors

Each 28×28 pixel MNIST image is flattened into a 784-dimensional vector by reading pixels row by row:

A 28x28 pixel grid — each cell is a grayscale intensity value. Most pixels are 0 (background).

The digit "1" and its 28x28 intensity matrix. Flattening gives a 784-dimensional vector.

Cluster Centroids as "Average Digits"

Each centroid $\mu_k \in \mathbb{R}^{784}$ can be reshaped back into a 28×28 image, revealing the "average" appearance of its cluster.

The 10 cluster centroids visualized as images. Each looks like a blurry averaged version of its digit.

Single centroid for the "0" cluster — a soft, averaged zero shape.

6. K-Means Properties

K-Means Pseudocode

For each seed trial:
  1. INITIALIZE: Randomly place K centers mu_1, ..., mu_K

  2. REPEAT:
     a. ASSIGNMENT: For each point x_n:
          assign to k* = argmin_k ||x_n - mu_k||^2
          set r_{n,k*} = 1, r_{n,j} = 0 for j != k*

     b. UPDATE: For each cluster k:
          mu_k = (sum of x_n where r_{nk}=1) / (count in cluster k)

     c. COMPUTE J = sum of r_{nk} * ||x_n - mu_k||^2

  UNTIL J does not improve

Select trial with lowest J as final result.

7. Gaussian Mixture Models

Why Move Beyond K-Means?

Two overlapping groups. There is no clear boundary — many points could plausibly belong to either cluster.

GMM replaces hard cluster centers with $K$ Gaussian distributions. Each cluster is described by a full probability distribution, and each data point has a probability of belonging to each cluster.

Two Gaussian clusters in 2D. Points in the overlap region have high posterior probability for both clusters.

Real-data example: multiple overlapping elliptical Gaussian clusters. K-Means would struggle with these non-spherical shapes.

8. Gaussian Distributions

1D Gaussian

Same mean $\mu = 0$, varying $\sigma$: small $\sigma$ = tall narrow peak; large $\sigma$ = short wide peak.

2D and Multivariate Gaussian

2D Gaussian: bell-shaped surface over $(x, y)$ with contour plot below. Peak is at the mean; contours are ellipses.

9. EM Algorithm

The Expectation-Maximization (EM) algorithm fits a GMM to data. It is the soft-assignment analog of K-Means alternating optimization.

E-Step: Compute Soft Assignments

For each data point $x_i$ and each Gaussian $k$, compute the posterior probability using Bayes' theorem:

The posterior formula: probability that point $x_i$ was generated by each Gaussian.

After E-step: points colored fractionally (dot size indicates strength of membership in each Gaussian).

M-Step: Recompute Gaussian Parameters

Using the soft assignments as weights, update each Gaussian's parameters:

M-step: every point contributes to every Gaussian's update, weighted by its posterior probability.

Unlike K-Means (where only assigned points update a centroid), in EM every point contributes to every Gaussian, weighted by how likely it is to belong to that Gaussian.

Visual Convergence

Initial state: two overlapping Gaussians placed randomly.

Mid-convergence: Gaussians shifting toward the true cluster centers.

After convergence: two well-separated Gaussians accurately modeling the two clusters.

EM in 2D

Initial Gaussian components in 2D shown as contour ellipses.

Converged 2D GMM: probability surface with contour projections showing Gaussian mixture.

10. GMM and EM Summary

Input: Data {x_1, ..., x_N}, number of Gaussians K

1. INITIALIZE: Randomly set mu_k, sigma_k, pi_k for each k

2. REPEAT:

   E-STEP: For each point x_i, each Gaussian k:
     Compute likelihood: P(x_i | k) using Gaussian PDF
     Compute posterior:  gamma(i,k) = P(k | x_i) via Bayes' theorem

   M-STEP: For each Gaussian k:
     mu_k    = weighted mean (weights = gamma(i,k))
     sigma_k = weighted variance (weights = gamma(i,k))
     pi_k    = average of gamma(i,k) over all points

UNTIL Gaussian updates are small (convergence)

K-Means vs GMM Side-by-Side

11. Dimensionality Reduction (PCA)

MNIST digit images are 784-dimensional, making clustering computationally expensive (especially for GMM, which requires 784×784 covariance matrices).

Flashcards