Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Wikipedia defines the Jaccard distance between sets A and B as $$J_\delta(A,B)=1-\frac{|A\cap B|}{|A\cup B|}.$$ There's also a book claiming that this is a metric. However, I couldn't find any explanation of why $J_\delta$ obeys the triangle inequality. The naive approach of writing the inequality with seven variables (e.g., $x_{001}$ thru $x_{111}$, where $x_{101}$ is the number of elements in $(A\cap C) \backslash B$) and trying to reduce it seems hopeless for pen and paper. In fact it also seems hopeless for Mathematica, which is trying to find a counterexample for 20 minutes and is still running. (It's supposed to say if there isn't any.)

Is there a simple argument showing that this is a distance? Somehow, it feels like the problem shouldn't be difficult and I'm missing something.

share|improve this question
add comment

2 Answers 2

up vote 21 down vote accepted

The trick is to use a transform called the Steinhaus Transform. Given a metric $(X, d)$ and a fixed point $a \in X$, you can define a new distance $D'$ as

$$D'(x,y) = \frac{2D(x,y)}{D(x,a) + D(y,a) + D(x,y)}$$

It's known that this transformation produces a metric from a metric. Now if you take as the base metric $D$ the symmetric difference between two sets, what you end up with is the Jaccard distance (which actually is known by many other names as well).

For more information and references, check out Ken Clarkson's survey (Section 2.3)

share|improve this answer
    
You forgot to specify what $a$ should be, but the empty set seems to do the job. –  Harald Hanche-Olsen Mar 13 '10 at 19:31
    
Steinhaus Transform, is it a standard term? –  Anton Petrunin Mar 14 '10 at 0:24
    
I believe so, at least among the right folks :). It's possible it shows up under other names as well –  Suresh Venkat Mar 14 '10 at 2:10
2  
It seems that proving that Steinhaus Transform gives a metric is just as hard as the original problem... –  Anton Petrunin Mar 18 '10 at 2:26
add comment

It is possible to prove this directly too, without invoking the Steinhaus Transform. But that would probably make the proof longer. However, I did once prove it directly, and I think it went a bit like this:

Assume there exist A, B ,C such that d(A,B) + d(B,C) < d(A,C). For such a counterexample, note that A, C and $A\cap C$ have to be nonempty. Now since the right hand side remains unchanged on changing B, we can remove all elements in B which are not in A or C, since that would only further decrease the left hand side. Thus B is contained in $A\cup C$. The final step involves arguing that we can also remove all those elements in B which are only in A or C, as this operation will also only decrease the left hand side. Finally, we will have a B that is supposedly a counterexample to the metric distance claim, but it lies completely in $A \cap C$. This can also be shown to be not possible.

I hope I remember it right, I haven't worked this out recently.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.