Using k-means with other metrics

Question

So I realize this has been asked before: e.g. What are the use cases related to cluster analysis of different distance metrics? but I've found the answers somewhat contradictory to what is suggested should be possible in the literature.

Recently I have read two papers that have mention using the kmeans algorithm with other metrics, for example edit distance between strings and the "Earth Mover Distance" between distributions. Given that these papers mention using kmeans with other metrics without specifying how, particularly when it comes to computing the mean of set of points, suggests to me that maybe there is some "standard" method to dealing with this that I'm just not picking up on.

Take for example this paper, which gives a faster implementation of the k-means algorithm. Quoting from paragraph 4 in the intro the author says his algorithm "can be used with any black box distance metric", and in the next paragraph he mentions edit distance as a specific example. His algorithm however still computes the mean of a set of points and doesn't mention how this might affect results with other metrics (I'm especially perplexed as to how mean would work with edit distance).

This other paper describes using k-means to cluster poker hands for a texas hold-em abstraction. If you jump to page 2 bottom of lefthand column the author's write "and then k-means is used to compute an abstraction with the desired number of clusters using the Earth Mover Distance between each pair of histograms as the distance metric".

I'm not really looking for someone to explain these papers to me, but am I missing some standard method for using k-means with other metrics? Standard averaging with the earth mover distance seems like it could work heuristically, but edit distance seems to not fit the mold at all. I appreciate any insight someone could give.

(edit): I went ahead and tried k-means on distribution histograms using the earth mover distance (similar to what is in the poker paper) and it seemed to have worked fine, the clusters it output looked pretty good for my use case. For averaging I just treated the histograms as vectors and averaged in the normal way. The one thing that I noticed is the sum over all points of the distances to the means did not always decrease in a monotone manner. In practice though, it would settle on a local min within 10 iterations despite monotone issues. I'm going to assume that this is what they did in the second paper, the only question that remains then is, how the heck would you average when using something like edit distance?

Answer 1

It's not as if k-means will necessarily blow up and fail if you use a different metric.

In many cases it will return some result. It is just not guaranteed that it finds the optimum centroids or partitions with other metrics, because the mean may not be suitable for minimizing distances.

Consider Earth movers distance. Given the three vectors

3 0 0 0 0
0 0 3 0 0
0 0 0 0 3

The arithmetic mean is

1 0 1 0 1

which has EMD distances 6, 4, 6 (total 16). If the algorithm had instead used

0 0 3 0 0

the EMD distances would have been 6, 0, 6; i.e. better (total 12).

The arithmetic mean does not minimize EMD, and the result of using k-means (with artihmetic mean) will not yield optimal representatives.

Similar things will hold for edit distances.

Answer 2

K-means is appropriate to use in combination with the Euclidean distance because the main objective of k-means is to minimize the sum of within-cluster variances, and the within-cluster variance is calculated in exactly the same way as the sum of Euclidean distances between all points in the cluster to the cluster centroid. As other answers point out, the algorithm is only guaranteed to converge (even if to a local minimum) if both the centroid update step and the data points reassignment step are done in the same n-dimensional Euclidean space.

Also, it has been shown (and I put a link here because I myself cannot explain this) that the mean is the best estimator to be used when one needs to minimize total variance. So k-means tie to the Euclidean distance is two-fold: the algorithm must have some way to calculate the mean of a set of data points (hence the name k-means), but this mean only makes sense and guarantees convergence of the clustering process if the Euclidean distance is used to reassign data points to the nearest centroids.

You can still use k-means with other distance measures, as in this paper, in which the author uses the algorithm with the Minkowski distance, which is a generalization of the Manhattan, Euclidean and Chebyshev distances. However, in these cases, convergence is not guaranteed and, as a consequence, you might expect that future iterations of the algorithm will actually have greater total variance than previous iterations.

Even so, as shown in the paper above, even without the guarantee of convergence, k-means can achieve better clustering results in some scenarios by using other distance measures. If you take the $L^p$ norms, for example, and knowing that the Euclidean distance is the $L^2$ norm and that the Manhattan distance is the $L^1$ norm, it has been shown that, for sparse distance matrices, k-means used in conjunction with an $L^p$ norm with $0 < p \leq 1$ achieves greater clustering accuracy than when using the Euclidean distance.

Lastly, I think it is interesting to point out that there are some similarity measures that can in some way be converted to the Euclidean distance, in such a way that if you use said similarity measure in conjunction with k-means, you ought to get similar results. An example of that is the cosine similarity.

Answer 3

I don't know if this is what the linked papers are doing, but it is possible to do k-means with non-Euclidean distance functions using the kernel trick. That is, we implicitly map the inputs to a high-dimensional (often infinite-dimensional) space where Euclidean distances correspond to the distance function we want to use, and run the algorithm there. For Lloyd's k-means algorithm in particular, we can assign points to their clusters easily, but we represent the cluster centers implicitly and finding their representation in the input space would require finding a Fréchet mean. The following paper discusses the algorithm and relates it to spectral clustering:

I. Dhillon, Y. Guan, and B. Kulis. Kernel k-means, Spectral Clustering and Normalized Cuts. KDD 2005.

There are kernels based on the edit distance and based on the earth mover's distance.