# Is the Jaccard distance a distance?

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.

• What does that final period communicate in the formula? Oct 25, 2017 at 0:14
• @GabrielFair, it communicates that the sentence has ended: see en.wikipedia.org/wiki/Wikipedia:Manual_of_Style/… , which cites style guides. Jan 18, 2021 at 23:25

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 and empty set as $$a$$, 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 Nearest-neighbor searching and metric space dimensions (Section 2.3).

• You forgot to specify what $a$ should be, but the empty set seems to do the job. Mar 13, 2010 at 19:31
• Steinhaus Transform, is it a standard term? Mar 14, 2010 at 0:24
• It seems that proving that Steinhaus Transform gives a metric is just as hard as the original problem... Mar 18, 2010 at 2:26
• The "Steinhaus transform" proof may also be found in The minisum location problem for the Jaccard metric by H. Späth. Aug 30, 2017 at 21:39
• Indeed it's no trick, but a conceptual generalization.
– YCor
Nov 22, 2018 at 7:38

Here is an elementary proof of the Steinhaus transform (from which said metricity follows as a special case, as noted in Suresh's answer).

Lemma. Let $$p,q > 0$$ and $$r\geq 0$$ such that $$p \le q$$. Then, $$\frac{p}{q} \le \frac{p+r}{q+r}.$$

Corollary. Let $$d(x,y)$$ be a metric. Then, for arbitrary (but fixed) $$a$$, the map $$\delta$$ defined by $$\begin{equation*} \delta(x,y) := \frac{2d(x,y)}{d(x,a)+d(y,a)+d(x,y)} \end{equation*}$$ (and $$\delta(a,a)=0$$) is a metric.

Proof. Only the triangle inequality for $$\delta$$ is nontrivial. Let $$p=d(x,y)$$, $$q=d(x,y)+d(x,a)+d(y,a)$$, and $$r=d(x,z)+d(y,z)-d(x,y)$$. Applying the lemma, we obtain $$\begin{eqnarray*} \delta(x,y) &=& \frac{2d(x,y)}{d(x,a)+d(y,a)+d(x,y)} \le \frac{2d(x,z)+2d(y,z)}{d(x,a)+d(y,a)+d(x,z)+d(y,z)}\\ &=& \frac{2d(x,z)}{d(x,a)+d(z,a)+d(x,z)+d(y,z)+d(y,a)-d(z,a)} + \frac{2d(y,z)}{d(y,a)+d(z,a)+d(y,z)+d(x,z)+d(x,a)-d(z,a)}\\ &\le& \delta(x,z)+\delta(y,z), \end{eqnarray*}$$ where the last inequality again uses triangle inequality for $$d$$.

• What does that prime (comma) character mean in the denominator of your corollary equation? Oct 25, 2017 at 0:16
• I see, it looks visually a bit unfortunately placed; it's just a punctuation after the equation; I don't want to edit the answer just to add a tiny bit more space between the equation and the comma though. Oct 25, 2017 at 0:46
• oh, thanks. I'm a beginner and I saw the same thing on the wikipedia page and I was very confused. Oct 26, 2017 at 1:05
• @Gabriel Fair 2017: English sentences, whether or not containing mathematical formulae, are still English sentences, with punctuation working as usual. Nov 21, 2018 at 23:51
• I had added the comma not for grammatical reasons, but for focusing the reader to pause after having read the "definition" (notice :=) of $\delta$. If I had written $\delta =$, then I would not have placed that comma (a partial violation of grammar, for reasons of indicating a focus / pause). Nov 22, 2018 at 19:55

Possibly the simplest proof of the triangle inequality for the jaccard distance comes from the fact that it is the collision probability of the MinHash algorithm, and that's all we need. Let $$H(X) = \text{argmin}_{i\in X} \pi(i)$$ where $$\pi(i)$$ is a uniformly random permutation.

\begin{align*} J(X,Y) &= \Pr\left[H(X) = H(Y)\right] \\ 1 - J(X,Y) &= \Pr\left[H(X) \neq H(Y)\right].\\ \end{align*} So for any $$Z$$, \begin{align*} \Pr\left[H(X) = H(Y)\right] &\ge \Pr\left[H(X) = H(Z) \land H(Y) = H(Z)\right] \\ \Pr\left[H(X) \neq H(Y)\right] &\le \Pr\left[H(X) \neq H(Z) \lor H(Y) \neq H(Z)\right] \end{align*} But by the union bound, \begin{align*} \begin{split} \Pr\big[H(X) \neq H(Z) \lor H(Y) \neq H(Z)\big] &\le \Pr\big[H(X) \neq H(Z)\big] + \Pr\big[H(Y) \neq H(Z)\big] \end{split} \end{align*}

My co-author used this to prove that a particular jaccard generalization is a metric after I'd been struggling to prove it for a month, and I couldn't believe it.

• Note that this seems to be the same as the fixed version of Emolga's answer above. Nov 21, 2018 at 6:48

I know this is an old question, but I'm surprised that all other answers have overlooked a trivial proof technique. Let's reconsider the naïve approach, suggested by the OP, of splitting the Venn diagram for $$A$$, $$B$$, and $$C$$ into seven pieces $$x_{001}, \dots, x_{111}$$. The triangle inequality for the Jaccard metric is the following rational inequality:

$$\begin{multline} 1-\frac{x_{011}+x_{111}}{x_{001}+x_{010}+x_{011}+x_{101}+x_{110}+x_{111}} \\ +1-\frac{x_{110}+x_{111}}{x_{010}+x_{011}+x_{100}+x_{101}+x_{110}+x_{111}} \\ -1+\frac{x_{101}+x_{111}}{x_{001}+x_{011}+x_{100}+x_{101}+x_{110}+x_{111}} \ge 0. \end{multline}$$

Clear fractions by multiplying through by the product of the denominators, then fully expand the resulting polynomial products. What one obtains is the following monstrosity:

$$x_{001}^2 x_{010}+x_{001}^2 x_{011}+x_{001}^2 x_{100}+x_{001}^2 x_{101}+x_{001} x_{010}^2+2 x_{001} x_{010} x_{011}+2 x_{001} x_{010} x_{100}+4 x_{001} x_{010} x_{101}+2 x_{001} x_{010} x_{110}+2 x_{001} x_{010} x_{111}+x_{001} x_{011}^2+2 x_{001} x_{011} x_{100}+4 x_{001} x_{011} x_{101}+x_{001} x_{011} x_{110}+x_{001} x_{011} x_{111}+x_{001} x_{100}^2+4 x_{001} x_{100} x_{101}+2 x_{001} x_{100} x_{110}+2 x_{001} x_{100} x_{111}+3 x_{001} x_{101}^2+3 x_{001} x_{101} x_{110}+3 x_{001} x_{101} x_{111}+x_{010}^2 x_{011}+x_{010}^2 x_{100}+2 x_{010}^2 x_{101}+x_{010}^2 x_{110}+2 x_{010}^2 x_{111}+x_{010} x_{011}^2+2 x_{010} x_{011} x_{100}+5 x_{010} x_{011} x_{101}+2 x_{010} x_{011} x_{110}+3 x_{010} x_{011} x_{111}+x_{010} x_{100}^2+4 x_{010} x_{100} x_{101}+2 x_{010} x_{100} x_{110}+2 x_{010} x_{100} x_{111}+4 x_{010} x_{101}^2+5 x_{010} x_{101} x_{110}+6 x_{010} x_{101} x_{111}+x_{010} x_{110}^2+3 x_{010} x_{110} x_{111}+2 x_{010} x_{111}^2+2 x_{011}^2 x_{101}+3 x_{011} x_{100} x_{101}+x_{011} x_{100} x_{110}+4 x_{011} x_{101}^2+4 x_{011} x_{101} x_{110}+4 x_{011} x_{101} x_{111}+x_{100}^2 x_{101}+x_{100}^2 x_{110}+3 x_{100} x_{101}^2+4 x_{100} x_{101} x_{110}+3 x_{100} x_{101} x_{111}+x_{100} x_{110}^2+x_{100} x_{110} x_{111}+2 x_{101}^3+4 x_{101}^2 x_{110}+4 x_{101}^2 x_{111}+2 x_{101} x_{110}^2+4 x_{101} x_{110} x_{111}+2 x_{101} x_{111}^2 \ge 0$$

Despite its length, this inequality is completely obvious, because every coefficient is positive!

Of course, this technique is beyond the reach of a pen-and-paper calculation, but expanding and simplifying polynomial products should be instantaneous in any modern computer algebra system.

• Actually, going via the Steinhaus transform gives you vastly more than just triangle inequality for the Jaccard distance (because it applies to arbitrary metric spaces!). That said, I think so far the cleanest "venn" diagram proof is in Ryan Moulton's answer. The rational inequality you note above also looks very nice! Nov 21, 2018 at 13:25
• @Suvrit I definitely agree it's not the most enlightening proof! I was mostly spurred by the OP's remark that the problem "seems hopeless for Mathematica," to which I thought "nonsense --- moderate-sized rational inequalities should be well within reach." And I do find some elegance, admittedly of a different sort, when a simple-minded proof idea can be made to work modulo computational effort. Nov 21, 2018 at 23:48
• IIRC, the first inequality is exactly what I plugged in some Mathematica function. But now I can't recall which one ... Jan 10, 2019 at 19:11
• @rgrig Just write the unfactored expression into Mathematica and press "expand". It works perfectly. May 24, 2020 at 7:57
• @BjørnKjos-Hanssen: Maybe it works now. The question is many years old. I don't have a Mathematica licence any more, because of changing jobs. May 24, 2020 at 20:23

We permute all the elements of $A \cup B \cup C$ and denote by $p_{A,B}$ the probability that the first element of the permutation that is in $A$ or $B$ is not in both. This probability is equal to $1-\frac{A \cap B}{A \cup B}$, which is the Jaccard distance, because we look at the first element which is in $A \cup B$ and the probability that it is in both sets is $\frac{A \cap B}{A \cup B}$.

Now we are only left to prove that $p_{A,B}+p_{B,C} \geq p_{A,C}$. That's true because if the first element of the permutation that is in $A$ is in index $i(A) \neq i(C)$, then it means that $i(A) \neq i(B)$ or $i(B) \neq i(C)$.

• The definition of $p_{A,B}$ is asymmetric in $A$ and $B$, unlike Jaccard distance. The error in the proof occurs in "we look at the first element which in in $A\cup B$" since the first element which is in $A\cup B$ might be in $B$, but not in $A$; even though the first element in $A$ is also in $B$. Jul 3, 2015 at 7:33
• Howver, the proof can be salvaged. Just define $i(A)$ to be the first element of $A$, $i(B)$ to be the first element of $B$, etc. Define $p_{A,B}$ as "$i(A)\neq i(B)$", and so on. Jul 3, 2015 at 7:38

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.

I found a very brief and easy-understanding proof in the paper by Sven Kosub, "A note on the triangle inequality for the Jaccard distance".