K-means clustering

Suppose we have a dataset {\textbf{x}_1, \ldots, \textbf{x}_n} consisting of $N$ observations of a random $D$-dimensional space. The goal is to partition the dataset into some number $K$ of clusters. Formally, let { \pmb{\mu} _1, \ldots, \pmb{\mu}_k } be a set of $D$-dimensional vectors in which $\mu {\mu }_k$ is associated with the $k^{th}$ cluster ($\mu {\mu }_k$ can be thought of as the centers of the clusters). The goal is to find an assignment of data points so that the distance of each data point to its closest vector $\mu {\mu }_k$ is a minimum.

Let $r_{n}k\in 0,1$, where $k=1,\dots ,K$, describe the assignment of each data point to a cluster (1 if it’s assigned to a cluster and 0 if not). We define a function called the distortion measure, given by:

This represents the sum of the squares of the distances of each data point to its assigned vector $\mu {\mu }_k$. Our goal is to find values for $r_{n}k$ and the $\mu {\mu }_k$ so as to minimize $J$. The algorithm is as follows:

Algorithm:

• Pick initial values for the $\mu \mu$.
• Minimize J with respect to $r_{n}k$, keeping the $\mu {\mu }_k$ fixed (Expectation).
• Minimize J with respect to the $\mu {\mu }_k$, keeping $r_{n}k$ fixed (Maximization).

Multivariate gaussian distribution

For a random variable $X$ with a finite number of outcomes $x_1,x_2,\dots ,x_n$ occurring with probabilities $p_1,p_2,\dots ,p_n$, the expectation of $X$ is defined as:

The covariance between two variables, $X$ and $Y$, is defined as the expected value (or mean) of the product of their deviations from their individual expected values:

When working with multiple variables $X_1,X_2,\dots ,X_n$, the covariance matrix, denoted as $\mathrm{\Sigma }$, is the $n\times n$ matrix whose $(i,j)$-th entry is $cov(X_i,X_j)$.

The density function of a univariate gaussian distribution is given by:

• $(x-\mu {)}^2$ is always positive.
• The value $k(x,\mu )=-\frac{1}{2{\sigma }^2}(x-\mu {)}^2$ is always negative. It’s a parabola pointing downward.
• The $\exp (k(x,\mu ))$ part makes sure that the quantity is always $\ge 0$.
• The normalization factor $\frac{1}{\sqrt{2\pi {\sigma }^2}}$ multiplies $\exp (k(x,\mu ))$ so that this sum equals 1.

A vector random variable $X=[X_1,\dots ,X_n{]}^T$ is said to have a multivariate Gaussian distribution with mean $\mu \in {\mathbf{R}}^n$ and covariance matrix $\mathrm{\Sigma }$ if its probability density function is given by:

Like in the univariate case, the argument of the exponential function is a downward-opening bowl. The coefficient in front is a normalization factor used to ensure that:

Gaussian mixture models and EM

https://www.youtube.com/watch?v=qMTuMa86NzU