Clustering, Mixture Models and EM

Unsupervised learning aims to find structure in unlabeled data. One of the most common tasks is Clustering, which involves grouping similar data points together.

1. K-Means Clustering

K-Means is the simplest and most widely used clustering algorithm. It partitions the data into $K$ clusters by minimizing the within-cluster sum of squares (Inertia):

Where:

• $r_{nk} = 1$ if point $n$ is assigned to cluster $k$, 0 otherwise.
• $\boldsymbol{\mu}_k$ is the center (centroid) of cluster $k$.

The Algorithm:

1. Initialize: Choose $K$ random centroids.
2. Assign: Assign each point to the nearest centroid.
3. Update: Move each centroid to the mean of its assigned points.
4. Repeat: Until the centroids no longer move.

2. Gaussian Mixture Models (GMM)

While K-Means performs "hard" assignments (a point belongs to exactly one cluster), Mixture Models provide "soft" assignments (a point has a probability of belonging to each cluster).

A GMM assumes the data is generated from a weighted sum of $K$ Gaussians:

where $\pi_k$ are the mixing coefficients (must sum to 1).

3. The Expectation-Maximization (EM) Algorithm

EM is a powerful iterative framework for finding Maximum Likelihood estimates in latent-variable models like GMMs.

E-Step (Expectation):

Calculate the "responsibilities" $\gamma(z_{nk})$—the probability that point $n$ was generated by component $k$ given the current parameters.

M-Step (Maximization):

Update the parameters ($\pi_k, \boldsymbol{\mu}_k, \boldsymbol{\Sigma}_k$) to maximize the expected log-likelihood based on the E-step responsibilities.