5
$\begingroup$

We often normalize inputs to the k-means algorithm by 1) subtracting the mean on a per-feature basis and 2) dividing by the standard deviation on a per-feature basis. Some rational behind this is discussed here:

Are mean normalization and feature scaling needed for k-means clustering?

But it seems strange to assume that the features aren't correlated, so my question is, why don't we fully whiten the data instead? In other words, if the data has mean $\mu$ and covariance $\Sigma$, why not preprocess each sample using $ \tilde{x} = \Sigma^{-1/2} (x - \mu) $ ?

The only argument I see is that this will get computationally difficult when the dimensionality of $x$ gets very large, for example $\gg 100$, but are there other reasons?

Thank you.

Improve this question
$\endgroup$
4
  • $\begingroup$ It is possible. You may pre-process data in any way if it has sense relative to the future result obtained. But - I'd notice - K-means doesn't assume variables to be uncorrellated. What it assumes is that clusters within the data are, roughly, spherical, and it is another thing. $\endgroup$
    – ttnphns
    Commented Jun 24, 2014 at 11:05
  • $\begingroup$ Yes, but the data will be "more spherical" after full whitening than after per-feature normalization. $\endgroup$
    – rd11
    Commented Jun 24, 2014 at 11:14
  • $\begingroup$ The whole data cloud - yes. But not necessarily clusters in it. Normalizations (any) are not required by K-means, but they may have sense and often do have. $\endgroup$
    – ttnphns
    Commented Jun 24, 2014 at 11:15
  • $\begingroup$ Agreed! Although now we're getting into a different topic :). You could say the same about per-feature normalization. $\endgroup$
    – rd11
    Commented Jun 24, 2014 at 11:17

1 Answer 1

Reset to default
6
$\begingroup$

That is a good question, and it really makes a lot of sense to perform whitening of data. In particular there is a paper by Coates and Ng where they discuss the difference among these two steps (among other things) and their effect on k-means in order to learn some dictionary of patches of images.

As you already point out, whitening decorrelates data (up to a second order, since you are using the covariance matrix). Whitening presents some numerical problems (as well as normalization), and the standard trick is to add some constant term (regularization) when performing scalings.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.