0
$\begingroup$

The objective/loss function of K-Means algorithm is to minimize the sum of squared distances, written in a math form, it looks like this: $$J(X,Z) = min\ \sum_{z\in Clusters}\sum_{x \in data}||x-z||^2$$

If we have different distance metric, for instance, cosine (I realize there's a conversion between cosine and Euclidean but let's forget it for now), manhattan etc, does it mean we will have a different loss function?

That is, the traditional K-Means based on expectation maximization won't be working right? Because for every iteration we revise centroids, normally, by computing the average. However, for some of the metrics other than Euclidean, average might not be a legit representation for the center.

$\endgroup$
2
$\begingroup$

You're right and you're wrong.

The objective/loss function of K-Means algorithm is to minimize the sum of squared distances

Yes, absolutely.

written in a math form, it looks like this: $$J(X,Z) = min\ \sum_{z\in Clusters}\sum_{x \in data}||x-z||^2$$

Err... sort of. This is definitely the most popular formulation of kmeans, but a more appropriate formulation would be:

$$J(X,Z) = min\ \sum_{z\in centroids}\sum_{x \in data} distance(x,z)$$

In your formulation, you're concretely defining distance as euclidean distance, i.e. the L2 norm. But you can swap out L2 for any distance kernel and apply kmeans.

The caveat here is that kmeans is a "hill climbing" algorithm, which means each iteration should always be at least as good as the previous iteration, and so it must be the case that this improvement will be true for both the E and M steps. For most common distance metrics (L1, L2, cosine, hamming...) this is the case and you're good to go, but there are infinite possible distance metrics and if we're going to be technical about it, the probability that a random distance metric will satisfy this criterion is almost surely 0.

So, to circle back to your question: does the objective function as you formulated it imply the distance metric is euclidean? Yes. But does kmeans only apply to euclidean space? No, absolutely not. Use whatever distance metric you want and throw the EM algorithm at it and bam: you've got yourself a non-euclidean kmeans.

Generally, when people say "kmeans", they're talking about euclidean kmeans. But Kmeans is super easy to modify with a different distance metric and I think only the most pedantic people would argue that you shouldn't call it "kmeans" after such a modification. Although it's generally always described with the objective you posted (which, yes, does imply euclidean distance), you can really drop in pretty much any useful distance metric, throw EM at it, and it'll work. Some people might call it "___ kmeans" depending on the distance metric, but really it's all kmeans.

I think part of the reason kmeans often isn't described this way isn't formulated like this is because its often compared with gaussian mixture models (GMM). With a euclidean norm, kmeans is equivalent to a GMM with diagonal covariance (and hard cluster assignment), and is consequently often described as an easy way to fit a GMM with spherical clusters. But this comparison fails if we use a different distance metric.

I suggest you check out the CrossValidated discussion on this topic. Full disclosure: the highest voted answers disagree with me, but as you probably guessed I think they're being fairly pedantic.

$\endgroup$
  • $\begingroup$ K-Means is not equivalent to a GMM with diagonal covariance. Diagonal covariance gives ellipsoids. GMMs with diagonal covariance are called Single Gaussians $\endgroup$ – Carl Rynegardh Feb 27 '18 at 9:21
  • $\begingroup$ Fine: Kmeans = GMM with diagonal covariance if you preprocess the features to have unit variance. $\endgroup$ – David Marx Feb 27 '18 at 9:38
  • $\begingroup$ "more appropriate" - I beg to differ. The SSQ formulation is the most appropriate. Because it is the mean that matters for k-means. K-means does not minimize euclidean distance - because the mean does not. It minimizes the sum of squares. That is squared Euclidean, not regular Euclidean. $\endgroup$ – Anony-Mousse Feb 28 '18 at 1:06
  • $\begingroup$ Also, kmeans is not GMM. Because GMM usually is soft, means hard. Diagonal is not strict enough, either: they must be unit. Preprocessing won't do. $\endgroup$ – Anony-Mousse Feb 28 '18 at 1:31
  • $\begingroup$ Thanks for the answer. Tho I don't quite sure about the description that quote each iteration should always be at least as good as the previous iteration, I suppose what you've meant is the loss is non-increasing over time, but in my toy example, if the algo stuck in a local minima, the loss will fluctuate. $\endgroup$ – Logan Feb 28 '18 at 2:44
1
$\begingroup$

Yes, the mean is crucial.

If you just plug in another distance function instead of the sum-of-squares, the algorithm may fail to converge (and will not find a local optimum). The k-means algorithm relies on both steps (reassignment and mean recomputation) to optimize the same function. If they optimize different functions, you can get an infinite loop on the worst case.

You can use any Bergman divergence. And in some cases such as Euclidean instead of squared Euclidean nothing really bad will happen (no infinite loop etc.). It just won't find the best solution, because the mean isn't minimizing Euclidean distances.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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