# Difference between Hausdorff and earth mover (EMD) distance

I have two dataset that i want to compare. each dataset contain the weight of 10 different person measured for 3 different day.

I am interested in measuring the probabily that the two sample originate from the same population.

People seem to suggest doing a Kolmogorov-Smirnov test but i need a measurement.

I was thinking doing the EMD to compare the distribution for each day

EMD(dataset1.day1,dataset2.day1) + EMD(dataset1.day2,dataset2.day2) + EMD(dataset1.day3,dataset2.day3)

where dataset1.day1 is the histogram of the value for day1 in dataset 1...

But i could probably take each person as a 3d datapoint and do the EMD in 3d.

One other possibility was to do the Hausdorff distance but doing the average of the distance for each point instead of taking the maximum distance.

The two dataset have very different skewness so i was also considering using the Mann-Whitney-Wilcoxon_test.

What are the main difference between the two technique.

• (1) What is "EMD"? (2) Are the same 10 people included each day, or are they different people? (3) How are the people selected? -- This determines the populations from which they are taken; the answer likely provides the answer to your question. (4) Hausdorff distance between which sets? What is a "point" in this context?
– whuber
Jul 1, 2011 at 12:56
• (1) EMD is earth mover distance (the total work required to move all A's mass onto B, under the optimal scheme for doing so) (2) in each sample the weight are for the same 10 people each day. But the people in each sample are different which mean we have 20 people in total. (3) at random (4) Hausdorff distance between the 3d point from the first dataset and the 3d point of the second dataset Jul 1, 2011 at 19:07

There are two questions here: (1) how to determine the probability that the two samples are from the same distribution and (2) what kind of distance metric could be used to measure their overlap.

For the first, one simple way would be to determine the distribution of the first sample (perhaps it's multivariate normal?) and then calculate the posterior density of the second sample under the assumption of the distribution of the first. I like this approach because the interpretation is very straightforward.

For the second, I wouldn't do what you're suggesting with EMD unless you have some natural pairing of individuals in samples 1 and 2 (see @whuber's questions above). One common point between Hausdorff and EMD is that both let you specify an arbitrary distance metric for the points, e.g., euclidean or cosine, so you don't have to average the points (I'd go further and say you shouldn't if you use these methods). The downside is that your results will depend on your choice of the distance metric so you need some way of justifying your choice.

Because of the downside of the distance metric being arbitrary, I'd consider, instead, the Bhattacharyya distance or perhaps mutual information, provided you can make some information choice about what the distributions are.

• I am not sure why (1) is not a way to do (2). Anyway could you please provide more detail on how to go about doing (1)? Jul 1, 2011 at 19:13
• Before commenting on the specifics of doing it, can you clear up what the data looks like? For example, are samples 1 and 2 for different weight loss treatments and the 3 measurements are weights over 3 days of the treatment? Are the same 10 people in both samples (that is, did they try treatment 1 for while and then treatment 2)? If not, can we assume that for every individual in sample 1 there is a match in sample 2?
– Joey
Jul 1, 2011 at 20:18
• 1) sample 1 and 2 are people that subscribed to my service in different country. 2) the 3 measurments are weight over 3 days without treatements 3) they are not the same personnes 4) there is the same number of individual in each sample and if they come from the same population or generated from the same PDF then i guess y for every individual in sample1 you should be able to find a similar individual in sample2 Jul 1, 2011 at 20:25

The intuitive difference between Hausdorff distance and EMD between sets A and B is:

• EMD tells you the total work required to move all A's mass onto B, under the optimal scheme for doing so.
• Hausdorff tells you the worst-case distance between an element of A and the nearest element of B. If you consider each point to have unit mass, then you can think of Hausdorff as telling you the worst-case amount of work required to move a single element of A onto some element of B, under the optimal scheme for doing so.

Your modification of Hausdorff would have the characterization:

• It tells you the average amount of work required to move each element of A onto some element of B, under the optimal scheme for doing so.

Of course, which one you want depends on your application...

• Thanks a lot for your help. I was mainly interested in measuring the probabily that the two sample are originating from the same population. I taught there was one specific best way to do it. Jul 1, 2011 at 2:31
• I'm not sure, I guess you will need to put in place more machinery for that, since the distance between two sets doesn't tell you anything, by itself, about probability that they come from the same population... I'm not very knowledgeable about that. I'm not aware of any best way to do it, though.
– N F
Jul 1, 2011 at 2:53