As we increase the number of clusters, the between cluster variability increases? The within-cluster variability is the sum over all $\omega$ cluster variabilities
$$W(\omega) = \sum_{k = 1}^\omega V_\mathcal{c_k} = \sum_{k = 1}^\omega \sum_{\{ \mathbf{X}_i \in \mathcal{c_k} \}} \Delta(\mathbf{X}_i, \overline{\mathbf{X}}_k)^2,$$
where $\Delta$ is a matric, the $\mathcal{c}_k$ are disjoint clusters, and $\omega$ is the total number of clusters.
The between-cluster variability is the variability between cluster means and the sample mean
$$B(\omega) = \sum_{k = 1}^\omega \Delta(\overline{\mathbf{X}}_k, \overline{\mathbf{X}})^2.$$
I am told that increasing the number of clusters increases the between-cluster variability, but reduces the within-cluster variability. If this is true, then why does increasing the number of clusters increase the between-cluster variability, but reduce the within-cluster variability?
 A: Think intuitively about what the within and between variabilities are measuring.
Within variability
Loosely speaking, we can say that the within variability measures the distance between each point and the center of the cluster to which that point belongs.

*

*Consider one cluster. We will have only one centroid, and the within variability is calculated as the sum of the distance between that centroid and each point.

*Consider two clusters. We will have two centroids, and given how k-means work, each point is assigned to the cluster whose centroid is closer. So by adding an extra cluster, we reduce the within variability that we had before.

*The more clusters you add, the easier is for the algorithm to reduce the distance between points and centroids, reducing the within variability.

Between variability
Again, loosely speaking, the between variability measures the distance between the center of your dataset and each centroid.

*

*If you only have one cluster, the centroid of that cluster is precisely the center of your data, so the between variability is $0$.

*If you have two clusters, you will have two centroids that will no longer coincide with the center of your data, so your between variability will be a value larger than $0$.

*The more clusters you have, the more centroids you have, and likely the larger your between variability will be.

Example using R
Let's generate a dataset with three clear clusters
library(ggplot2)
library(tidyverse)
seed(5)
data = tibble(x=c(rnorm(100, mean=0, sd=1), rnorm(100, mean=5, sd=1), rnorm(100, mean=20, sd=1)),
            y=c(rnorm(100, mean=0, sd=1), rnorm(100, mean=5, sd=1), rnorm(100, mean=20, sd=1)),
            cluster=as.factor(rep(c(1,2,3), each=100)))

data %>% ggplot(aes(x=x, y=y, color=cluster)) + geom_point()


Consider only one cluster
If we consider only one cluster, we can compute the within variability as the distance between the center of your data and each point, and the between variability will be $0$
 one_centroid = colMeans(data[,c(1,2)])
 within_variability_1_cluster = data[, c(1, 2)] %>% apply(1, function(x) sqrt(sum((x-one_centroid)^2))) %>% sum()
 between_variability = 0  


*

*One cluster within variability: 3311.60

*One cluster between variability: 0

Three clusters
three_centroids = rbind(
colMeans(data[1:100,c(1,2)]),
colMeans(data[101:200,c(1,2)]),
colMeans(data[201:300,c(1,2)]))


within_variability_two_cluster = 
data[1:100, c(1, 2)] %>% apply(1, function(x) sqrt(sum((x-two_centroids[1,])^2))) %>% sum() +
data[101:200, c(1, 2)] %>% apply(1, function(x) sqrt(sum((x-three_centroids[2,])^2))) %>% sum() +
data[201:300, c(1, 2)] %>% apply(1, function(x) sqrt(sum((x-three_centroids[3,])^2))) %>% sum()

between_variability = three_centroids %>% apply(1, function(x) sqrt(sum((x-colMeans(data[,c(1,2)]))^2))) %>% sum()


*

*Three clusters within variability: 613.97

*Three clusters between variability: 32.94

So as you can see, three clusters have smaller within variability, but larger between variability.
