5 ms·
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 i
by globular-toast 5y ago
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.
- CardenB 5y agoWhat prevents you from using a different distance than Euclidean distance?
- danuker 5y agoSuppose 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.
- jacquesm 5y agoThat is not a proper distance function.
- danuker 5y agoWhat do you mean? Is it not the Euclidean distance? https://en.wikipedia.org/wiki/Euclidean_distance https://en.wikipedia.org/wiki/Euclidean_distance
- nerdponx 5y agoThis has nothing to do with using non-Euclidean distance, though. This is a separate issue related to having features on different scales.
- danuker 5y agoIt 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.
- deleted 5y ago[deleted]
- amilios 5y agoThe 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
- nerdponx 5y agoDo you lose convergence guarantees if you minimize "sum of squared distances from the centroid" using your other-than-Euclidean distance metric?
- fmakunbound 5y agoIt'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.
- whiplash451 5y agoNot 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-means-clustering-algorithm-use-only-euclidean-distance-metric https://stats.stackexchange.com/questions/81481/why-does-k-m...
- isoprophlex 5y agoThat'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
- amilios 5y agoLosing convergence guarantees is somewhat important!
- isoprophlex 5y agoI 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
- isoprophlex 5y agoBut you can. Get the distance to all your centroids, assign to closest centroid, update centroid location. The distance function can be anything.
- globular-toast 5y agoWhat's a centroid? It's the point that minimises the sum of squared Euclidean distances between itself and every point in the cluster.
- isoprophlex 5y agoIt'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.
- civilized 5y agoSo, 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?
- n4r9 5y agoAn alternative I've used is k-medoids: https://en.m.wikipedia.org/wiki/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.