3

I need to do some clustering using a correlation distance but instead of using the built-in 'distance' 'correlation' which is defined as d=1-r I need the absolute Pearson distance. In my application anti-correlated data should get the same cluster ID. And now when using the kmeans() function I'm getting centroids that are highly anticorrelated which I would like to avoid by combining them. Now, I'm not that fluent in matlab yet and have some problems reading the kmeans function. Would it be possible to edit it for my purpose?

Example:

Row 1 and 2 should get the same cluster ID when using the correlation distance as metrics.

I did some attempts to edit the built-in matlab function ( open kmeans- >line 775) but what's weird - when I change the distance function I'm getting a valid distance matrix but wrong cluster indexes, can't find the reason for it. Would love to get some tips! all best!

3
  • I do not understand your question... Your are saying: "And now when using the kmeans() function im getting centroids that are highly anticorreleted" I think this is what you want... Or Is this sentence wrong?
    – phyrox
    Jan 24, 2014 at 8:37
  • Thanks for answering, no this it not what i want maybe i wrote this sentence unclear. What i need is that the script treats anticorrelated data as the same. And to this be possible the distance function has to give the same value for -1 and 1. so it can be the abs(pearson_corr_coef)
    – i008
    Jan 24, 2014 at 9:40
  • So you can modify another version of kmeans as I indicated in the answer
    – phyrox
    Jan 24, 2014 at 10:06

2 Answers 2

6

This is a good example of why you should not use k-means with other distance functions.

k-means does not minimize distances. It minimizes the sum of squared 1-dimensional deviations (SSQ).

Which is mathematically equivalent to squared Euclidean distance, so it does minimize Euclidean distances, as a mathematical side effect. It does not minimize arbitrary other distances, which are not equivalent to variance minimization.

In your case, it's pretty nice to see why it fails; I have to remember this as a demo case.

As you may know, k-means (Lloyds, that is) consists of two steps: assign by minimum squared deviation and then recompute the means.

Now the problem is, recomputing the mean is not consistent with absolute pearson correlation.

Let's take two of your vectors, which are -1 correlated:

+1 +2 +3 +4 +5
-1 -2 -3 -4 -5

and compute the mean:

 0  0  0  0  0

Boom. They are not at all correlated to their mean. In fact, Pearson correlation is not even well-defined for this vector anymore, because it has zero variance...

Why does this happen? Because you misinterpreted k-means as distance based. It's actually as much arithmetic mean based. The arithmetic mean is a least-squares (!!) estimator - it minimizes the sum of squared deviations. And that is why squared Euclidean distance works: it optimizes the same quantity as recomputing the mean. Optimizing the same objective in both steps makes the algorithm converge.

See also this counter-example for Earth-movers distance, where the mean step of k-means yields suboptimal results (although probably not as bad as with absolute pearson)

Instead of using k-means, consider using k-medoids aka PAM, which does work for arbitrary distances. Or one of the many other clustering algorithms, including DBSCAN and OPTICS.

2
  • you may want to rephrase your answer - you say "k-means does not minimize distances", but then say "... so it does minimize Euclidean distances" Feb 2, 2014 at 1:59
  • It does not care whether it minimizes Euclidean distance. It tries to minimize variance. Which has a side effect. Feb 2, 2014 at 11:14
1

You can try to modify another version of kmeans: This version is also efficient, but much more simple (around 10 lines of code). Here you have the exmplanation of the code.

Your Answer

Reminder: Answers generated by Artificial Intelligence tools are not allowed on Stack Overflow. Learn more

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

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