Why is it bad to use Pearson distance in K-means clustering? [duplicate]

Question

I have implemented this algorithm in MATLAB and when I produce plots I notice that using Euclidean distance, I usually get presented with a clear pattern (sum of squares decreases with the number of iterations). However, when I run the algorithm using the modified Pearson correlation distance (1 - r, where r is the Pearson correlation coefficient), sometimes I would see no trend at all. In fact, on some occasions the sum of squares seems to increase with the number of iterations.

Is there a reason for this? Also I know that Euclidean distance is the preferred metric for this algorithm, but does it have any drawbacks?

Answer 1

k-means minimizes least-squares. It does not minimize distances, although every other book reiterates this approximation. (Fact is, it optimizes least squares, which is squared Euclidean distance.)

As you may know, Lloyd k-means has two steps: 1. assign every point to the "nearest" cluster (precisely, the least-squares center) 2. update the centers with the arithmetic mean (the least-squares estimate).

Replacing only the distance does not work

Because you change the objective only in 1., but not in step 2. To converge, both need to optimize the same objective!

Counterexample for Pearson:

Assume that the two objects (0,1,2,3,4) and (4,3,2,1,0) are assigned to the same cluster. The arithmetic mean is (2,2,2,2,2) Pearson distance to this center is no longer defined.

Don't forget the "mean" in k-means!