0
$\begingroup$

It is my understanding that when the distance metric is euclidean distance, the mean of a dataset minimizes the average distance between all data points and the computed "mean".

In the case of Earth Movers Distance for discrete distributions, how would one compute a "mean" such that the average EMD distance between this "mean" and all of the histograms in the dataset is minimized? How would such an average distance minimizing formula be derived in general for a given distance function?

The application is for a K-means clustering task. Existing approaches only use averaging as an update rule for the new centroid even when using an unusual distance function for which a straightforward mean will not minimize average distance to the centroid. Our group believes using this approach for updating cluster centroids will improve the quality of our cluster generation.

$\endgroup$
1
  • $\begingroup$ Not my field, but I beleive earth mover distance is related to transport problems in OR. If you don't get help here maybe ask at or.stackexchange.com $\endgroup$ Apr 10 at 15:29
0
$\begingroup$

I think what you discribed is the Wasserstein Barycenter.

There is plenty of literature about the Wasserstein barycenter, including fast ways to compute it, (you could specify it’s the Wasserstein-1 distance you’re interested in, since it’s easier to compute than the general Wasserstein distance) and about its use for clustering.

$\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.