k-means clustering minimizes conditional variance

Question

I keep reading that K-means clustering "finds cluster centers that minimize conditional variance (good representation of data)". I understand conceptually how K-means clustering works, but please explain how it minimizes the conditional variance.

Example reference: slide 44 of this ppt.

Answer 1

To show how the objective function you've probably seen refers to this concept:

The k-means objective function is $$ \sum_{i=1}^k \sum_{x \in G_i} \lVert x - \mu_i \rVert^2 ,$$ where $G_i$ is the set of points in the $i$th cluster and $\mu_i$ its mean. $\DeclareMathOperator{\E}{\mathbb{E}}$

Let $n$ be the total number of points, and $n_i$ the number in the $i$th cluster. Now, consider the variance of a random point $X$ conditional on its cluster ID: \begin{align} \mathrm{Var}[X \mid X \in G_i] &= \E\left[ \lVert X - \E[X] \rVert^2 \mid X \in G_i \right] \\&= \E\left[ \lVert X - \mu_i \rVert^2 \mid X \in G_i \right] \\&= \frac{1}{n_i} \sum_{x \in G_i} \lVert x - \mu_i \rVert^2 .\end{align} So, what's the overall conditional variance, i.e. the expected conditional variance over the cluster IDs? \begin{align} \E_i\left[ \mathrm{Var}[X \mid X \in G_i] \right] &= \sum_{i=1}^k \Pr(X \in G_i) \, \mathrm{Var}[X \mid x \in G_i] \\&= \sum_{i=1}^k \frac{n_i}{n} \times \frac{1}{n_i} \sum_{x \in G_i} \lVert x - \mu_i \rVert^2 \\&= \frac{1}{n} \sum_{i=1}^k \sum_{x \in G_i} \lVert x - \mu_i \rVert^2 ,\end{align} which is directly proportional to the k-means objective. So, the optimal k-means clustering will also minimize the expected conditional variance.

("But what about dividing the variance by $n-1$", you say? Well, in this case, we're not trying to talk about estimating the variance of some existing distribution. k-means chooses a particular, known, discrete distribution whose support is only the training set. For that distribution, the variance and probabilities of membership are exactly as above and do not need to be estimated.)

Answer 2

The idea of $k$-means (and clustering in general for that matter) is to group points into clusters so that points within clusters are close together but points in different clusters are far apart. The within cluster variance is what's meant by the "conditional" variance and it's what $k$-means seeks to minimize (the mean of a sample is the least squares estimate of location).

Consider the following simulated data:

# cluster 1, normal(0, 1)
x1 = rnorm(50)
y1 = rnorm(50)

# cluster 2, normal(6, 1)
x2 = rnorm(50, mean=6)
y2 = rnorm(50, mean=6)

# plot the data
plot(c(x1, x2), c(y1, y2),
     xlab='x',
     ylab='y')
grid()

# estimate the conditional variances
var(x1)
var(y1)
var(x2)
var(y2)
# estimate the unconditional variances
var(c(x1, x2))
var(c(y1, y2))

Within clusters both $x$ and $y$ only have unit variance, but if we ignore the groups and calculate the variances across clusters they becomes much larger. In fact the increase in variance is really attributable to a shift in location, and that is what $k$-means tries to capture.