Hacker News Reader

Comment by globular-toast | Hacker News Reader

One thing not mentioned with k-means is it requires your data to be in Euclidean space. You can't just come up with a distance function and do clustering with it. That's one reason the other techniques often make sense. In fact, those techniques often don't care what the data actually is, they only need the distances, and even then they don't need all of them.

Still, k-means is enormously practical despite its shortcomings.

View on HN

Not sure why this was down voted.

K-means in its standard form does make a Euclidean hypothesis (it does not minimize a distance but the in-cluster variance).

It is not correct to use arbitrary distances because k-means may stop converging with other distance functions.

See this thread for more info: https://stats.stackexchange.com/questions/81481/why-does-k-m...

That's a really pedantic take, nothing precludes you from using whatever distance function you want to get the distance to k centroids and act accordingly

Losing convergence guarantees is somewhat important!

I totally agree with your point, but sometimes you can get away by being handwavey about it and making sure the centroids aren't skipping all over the place... and that's good enough

But you can. Get the distance to all your centroids, assign to closest centroid, update centroid location.

The distance function can be anything.

What's a centroid? It's the point that minimises the sum of squared Euclidean distances between itself and every point in the cluster.

It's a tuple of floats that you move slightly towards the closest point it has just seen, optionally with some rate of forgetting.

You shuffle your big ass wad of data, and loop over each element doing the above, optionally decreasing the forgetting rate.

You track the location of your centroids and if your data / loss fn isn't too pathological, they won't misbehave too badly and you have handwavey assurance of convergence... Definitions be damned.

So, you made up your own algorithm that is kinda like k-means, this algorithm might sometimes work, and this shows that k-means works in non-Euclidean spaces?

An alternative I've used is k-medoids:

https://en.m.wikipedia.org/wiki/K-medoids

This is especially useful in cases where the distance between points is given by a matrix, and cannot be derived from the points themselves. For example, the drive time between locations on a road network.

What prevents you from using a different distance than Euclidean distance?

Suppose you use prices and square meters, to cluster apartments. Suppose you also use a simple metric, like:

  distance <- sqrt(d_price*2 + d_area*2)

Without normalizing the units somehow, so that they have a meaningfully similar numeric expression, you are essentially only clustering by price, which is in the tens- or hundreds-of-thousands.

You use very little information about the area, because that is in the hundreds, at most thousands.

That is not a proper distance function.

What do you mean? Is it not the Euclidean distance?

https://en.wikipedia.org/wiki/Euclidean_distance

This has nothing to do with using non-Euclidean distance, though. This is a separate issue related to having features on different scales.

It was an example metric with coefficients of 1 for each feature.

The point I was making was that the different scale of the features influences the result by a lot.

The way k-means is constructed is not based on distances.

K-means minimizes within-cluster variance. If you look at the definition of variance, it is identical to the sum of squared Euclidean distances from the centroid

Do you lose convergence guarantees if you minimize "sum of squared distances from the centroid" using your other-than-Euclidean distance metric?

It's been ages since I've used K-means, but I thought you had a lot of freedom in how you define your distance function.

Reply on news.ycombinator.com