¿La distancia de Jaccard es una distancia?

Question

Wikipedia define el Distancia de Jaccard entre series A y B como $$J_\delta(A,B)=1-\frac{|A\cap B|}{|A\cup B|}.$$ También hay un libro afirmando que se trata de una métrica. Sin embargo, no pude encontrar ninguna explicación de por qué $J_\delta$ obedece a la desigualdad del triángulo. El enfoque ingenuo de escribir la desigualdad con siete variables (por ejemplo $x_{001}$ a través de $x_{111}$ , donde $x_{101}$ es el número de elementos en $(A\cap C) \backslash B$ ) y tratar de reducirlo parece inútil para el lápiz y el papel. De hecho, también parece inútil para Mathematica, que lleva 20 minutos intentando encontrar un contraejemplo y sigue funcionando. (Se supone que debe decir si no hay ninguno).

¿Existe un argumento sencillo que demuestre que se trata de una distancia? De alguna manera, parece que el problema no debería ser difícil y me estoy perdiendo algo.

Answer 1

El truco consiste en utilizar una transformación llamada Transformación de Steinhaus. Dada una métrica $(X, d)$ y un punto fijo $a \in X$ puede definir una nueva distancia $D'$ como $$D'(x,y) = \frac{2D(x,y)}{D(x,a) + D(y,a) + D(x,y)}.$$ Se sabe que esta transformación produce una métrica a partir de una métrica. Ahora bien, si se toma como métrica base $D$ la diferencia simétrica entre dos conjuntos, lo que se obtiene es la distancia de Jaccard (que en realidad se conoce también con muchos otros nombres).

Para más información y referencias, consulte la encuesta de Ken Clarkson Búsqueda del vecino más cercano y dimensiones del espacio métrico (Sección 2.3).

Answer 2

He aquí una demostración elemental de la transformada de Steinhaus (de la que se desprende dicha metricidad como un caso especial, como se señala en Suresh's respuesta).

Lema. Dejemos que $p,q > 0$ y $r\geq 0$ tal que $p \le q$ . Entonces, $\frac{p}{q} \le \frac{p+r}{q+r}.$

Corolario. Dejemos que $d(x,y)$ sea una métrica. Entonces, para una variable arbitraria (pero fija) $a$ el mapa $\delta$ definido por \begin{equation*} \delta(x,y) := \frac{2d(x,y)}{d(x,a)+d(y,a)+d(x,y)} \end{equation*} (y $\delta(a,a)=0$ ) es una métrica.

Prueba. Sólo la desigualdad del triángulo para $\delta$ no es trivial. Sea $p=d(x,y)$ , $q=d(x,y)+d(x,a)+d(y,a)$ y $r=d(x,z)+d(y,z)-d(x,y)$ . Aplicando el lema, obtenemos \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*} donde la última desigualdad vuelve a utilizar la desigualdad de triángulo para $d$ .

Answer 3

Posiblemente la prueba más sencilla de la desigualdad del triángulo para la distancia jaccard viene del hecho de que es la probabilidad de colisión del algoritmo MinHash, y eso es todo lo que necesitamos. Sea $H(X) = \text{argmin}_{i\in X} \pi(i)$ donde $\pi(i)$ es una permutación uniformemente aleatoria.

\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*} Así que para cualquier $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*} Pero por la unión atada, \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*}

Mi coautor utilizó esto para demostrar que un generalización particular de jaccard es una métrica después de haber estado luchando por probarla durante un mes, y no podía creerlo.

Answer 4

Sé que esta es una pregunta antigua, pero me sorprende que todas las demás respuestas hayan pasado por alto una técnica de prueba trivial. Reconsideremos el enfoque ingenuo, sugerido por el OP, de dividir el diagrama de Venn para $A$ , $B$ y $C$ en siete trozos $x_{001}, \dots, x_{111}$ . La desigualdad triangular para la métrica de Jaccard es la siguiente desigualdad racional:

\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}

Despeja las fracciones multiplicando por el producto de los denominadores, y luego expande completamente los productos polinómicos resultantes. Lo que se obtiene es la siguiente monstruosidad:

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

A pesar de su longitud, esta desigualdad es completamente obvia, porque todos los coeficientes son positivos.

Por supuesto, esta técnica está fuera del alcance de un cálculo con lápiz y papel, pero la expansión y simplificación de productos polinómicos debería ser instantánea en cualquier sistema moderno de álgebra computacional.

Answer 5

Permutamos todos los elementos de $A \cup B \cup C$ y denotar por $p_{A,B}$ la probabilidad de que el primer elemento de la permutación que está en $A$ o $B$ no está en ambos. Esta probabilidad es igual a $1-\frac{A \cap B}{A \cup B}$ que es la distancia de Jaccard, porque miramos el primer elemento que está en $A \cup B$ y la probabilidad de que es en ambos conjuntos es $\frac{A \cap B}{A \cup B}$ .

Ahora sólo nos queda demostrar que $p_{A,B}+p_{B,C} \geq p_{A,C}$ . Eso es cierto porque si el primer elemento de la permutación que está en $A$ está en el índice $i(A) \neq i(C)$ entonces significa que $i(A) \neq i(B)$ o $i(B) \neq i(C)$ .