Does the mean normalization step of k-means affect its performance?

Question

A common step when clustering using k-means is to first standardize the dataset so that each feature has zero mean and unit variance.

I understand why forcing unit variance helps k-means generate better clusterings. Leaving the different variables in unstandardized form effectively puts more weight on the variables with higher variance. However, I'm less sure about the reasoning behind the step of subtracting off the mean before k-means. How does this affect the clusterings generated by k-means?

Answer 1

Forcing unit variances might be better because the standard k-means approximates spherical Gaussian distributions around centroids and, as a consequence, might favor inflated features like you said. But this is not effective in all cases since there are also other factors implied: deeply correlated features, scaling is global over all clusters, and so on.

However the mean substraction has no effects. The data is the same, only translated so that the general means over all data is at $\textbf{0}$. This does not cange the problem at all. It could have a tiny benefit, however, the numbers will be smaller in general, so smaller relative errors. The benefit is tiny because the numbers are already smaller due to scaling.

Answer 2

The following is a proof that the objective function in the non-centered case is exactly equal to the objective function in the centered case. Recall that K-means finds clusterings by minimizing $\sum_{k=1}^K \sum_{y\in X_k}\|y-\mu_k\|_2^2$ over clusterings $\{X_k\}_{k=1}^K$, where $\mu_k$ is the centroid of $X_k$.

Let $\{x_i\}_{i=1}^n\subset\mathbb{R}^D$ be an uncentered dataset with global mean $m = \frac{1}{n}\sum_{i=1}^n x_i$. Let $\hat{x}_i = x_i-m$ be the centered version of the data point $x_i$. Fix a clustering $\{X_k\}_{k=1}^K$ and consider the centroid of a cluster $X_k$: \begin{align*} \mu_k = \frac{1}{|X_k|}\sum_{y\in X_k} x_i = \frac{1}{|X_k|}\sum_{x_i\in X_k} (m+\hat{x}_i) = m + \frac{1}{|X_k|}\sum_{x_i\in X_k} \hat{x}_i. \end{align*} The K-Means objective function in the non-centered case is, therefore, \begin{align*} \sum_{k=1}^K \sum_{x_i\in X_k}\|x_i-\mu_k\|_2^2 &= \sum_{k=1}^K \sum_{x_i\in X_k}\bigg\|\bigg(\hat{x}_i+m\bigg)-\bigg(m + \frac{1}{|X_k|}\sum_{x_i\in X_k} \hat{x}_i\bigg)\bigg\|_2^2\\ &= \sum_{k=1}^K \sum_{x_i\in X_k}\bigg\|\hat{x}_i- \frac{1}{|X_k|}\sum_{x_i\in X_k} \hat{x}_i\bigg\|_2^2. \end{align*} This is exactly equal to the objective function in the centered case. Thus, subtracting off the global mean as a preprocessing step before the implementation of K-means will not affect the final answer.