[SciPy-User] Mailing list?
Simon Friedberger
I sent a message about the K-Means algorithm a couple of days ago but it
seems like it never made it on the list. Are new members moderated or
something?
Best
Simon
_______________________________________________
SciPy-User mailing list
SciPy...@scipy.org
http://mail.scipy.org/mailman/listinfo/scipy-user
Simon Friedberger
Here is my original messages.
Sorry for the confusion.
Good Night Everybody,
I just looked at the documentation for the K-Means vector quantization
functions and I am a bit confused. On the one hand it says that
normalization to unit variance would be beneficial on the other hand
there are a lot of "must"s in the descriptions.
I was wondering if it is possible to use the functions without
normalization or if there is a negative impact.
This would make sense because it seems reasonable that one would want to
build the codebook on some set and then quantize a different set. In
this case normalization would have to be the same or be omitted.
I am also interested in literature recommendations concerning why this
is a good idea in general.
Any help would be greatly appreciated.
Best
Simon
David Warde-Farley
> I just looked at the documentation for the K-Means vector quantization
> functions and I am a bit confused. On the one hand it says that
> normalization to unit variance would be beneficial on the other hand
> there are a lot of "must"s in the descriptions.
> I was wondering if it is possible to use the functions without
> normalization or if there is a negative impact.
Damian did use some strong language there. The kmeans function won't
know whether you've normalized or not, but in some cases you can
expect much better solutions with normalized input (the function is
called "whiten" which is somewhat misleading, as "whitening" is often
used in the literature to mean decorrelating i.e. rotating by the
eigenvectors of the covariance).
kmeans uses the Euclidean distance, meaning that the distance between
two points is the sum of the squared difference of each point's
coordinates. If you have different coordinates that have vastly
different scales, say some in the thousands and some that are always
less than one, then one or two coordinates can dominate the distance
calculation and make the other coordinates nearly irrelevant in the
clustering (if the difference in scale is _really_ big then you can
lose precision in the rounding error, too).
Units are almost always arbitrary, and so scaling by the standard
deviation helps this in that it treats all of your features
"equally" (you may also want to subtract the mean before calling
whiten(), as well - this is in fact one of the standard tricks, it
doesn't matter so much here but it can help with numerical
conditioning in a lot of algorithms, particularly ones that involve
gradient descent).
If you want to quantize new vectors after clustering then you can
simply apply the reverse transformation to your codebook/centroids
(i.e. multiply by the std. dev. of the original data and add back the
mean if you subtracted it) which will scale them to the correct
position in the space of the original data.
> This would make sense because it seems reasonable that one would
> want to
> build the codebook on some set and then quantize a different set. In
> this case normalization would have to be the same or be omitted.
Yes, you could apply the normalization you applied to the training
data on every point you wish to quantize after the fact, but it's
usually easier to just apply the inverse transformation to the
codebook (especially if the number of points you want to quantize
greatly exceeds the number of items in your codebook, in which case
you save a lot of floating point ops).
> I am also interested in literature recommendations concerning why this
> is a good idea in general.
Well, lots of references will tell you what I just told you (that high-
variance features will dominate distance calculations if you don't
normalize). There is some discussion of it in the 'Prototype Methods'
chapter in 'The Elements of Statistical Learning': http://www-stat.stanford.edu/~tibs/ElemStatLearn/
David
Simon Friedberger
thanks for your explanation. I agree with your arguments but couldn't it
have the opposite effect: Weighing features that should have less
discriminative power more because they have a small variance?
I'm just not sure about it but I will check out the book you reference.
I've had it lying around for a while anyway.
On the case of inverting the transformation. Is this functionality
built-in? I can't find anything in the docs.
Thanks
Simon
Robert Kern
<simon+...@a-oben.org> wrote:
> Hi David,
>
> thanks for your explanation. I agree with your arguments but couldn't it
> have the opposite effect: Weighing features that should have less
> discriminative power more because they have a small variance?
If a variable has a small variance, a large deviation in that variable
is *very* informative and should have a larger impact on the
classification than a small deviation in a variable that has a large
variance.
Let's distinguish two cases: one in which each variable has its own
units (let's say degrees Celsius and meters) and one in which each
variable is commensurable and in the same units (let's say meters).
Now, in the first case, you need some way to put all of the variables
into the same units so you can sensibly compute a distance using all
of the variables. A reasonable choice of units is "one standard
deviation [of the marginal distribution for the variable]".
In the second case, there *may* be a case for not doing prewhitening.
If your points are actually 3D points in real space with a metric,
then you may want to use that space's metric as the distance. However,
if the process that created your data is creating "oblong"
distributions of points, that may indicate that it is using a
different notion of distance. In fact, you may want to do a PCA to
find the right rotation such that your variables are orthogonal to the
principal directions of variation. And then prewhiten in those
directions.
The key point is to find an appropriate definition of distance to use.
Prewhitening is a good default when you don't have a model of your
process, yet. And you usually don't. :-)
--
Robert Kern
"I have come to believe that the whole world is an enigma, a harmless
enigma that is made terrible by our own mad attempt to interpret it as
though it had an underlying truth."
-- Umberto Eco
Simon Friedberger
I agree with you in every respect. :)
Now, it only remains to see if anybody knows how to get to the
'whitening' transformation so I can invert it or apply it to my other
data.
Anybody? :)
Best
Simon
David Warde-Farley
> thanks for your explanation. I agree with your arguments but
> couldn't it
> have the opposite effect: Weighing features that should have less
> discriminative power more because they have a small variance?
> I'm just not sure about it but I will check out the book you
> reference.
> I've had it lying around for a while anyway.
It could, but typically when you're employing k-means, you have little
reason to believe any of the variables have any more explanatory power
than any of the others, so treating them "equally" is the simplest,
most reasonable thing to do. It indeed will inflate the range of low
variance.
You also use the word "discriminative", which makes me think you're
trying to do some sort of classification. Note that k-means can't take
into account any label information and is thus ill-suited to
classification, though it is sometimes used for this.
> On the case of inverting the transformation. Is this functionality
> built-in? I can't find anything in the docs.
It isn't, but maybe it should be. It'd involve rethinking the cluster
module a bit (which I've been planning on as a means to expand it, but
oh, the time, where does it go?...).
David
David Warde-Farley
> Hi Robert,
> I agree with you in every respect. :)
>
> Now, it only remains to see if anybody knows how to get to the
> 'whitening' transformation so I can invert it or apply it to my other
> data.
The 'whiten' function is only two lines:
std_dev = std(obs, axis=0)
return obs / std_dev
codebook *= std(youroriginaldata, axis=0)
will invert the transformation done by whiten() and apply it to your
codebook.
David