Índice de Jaccard

Intersección y unión de dos conjuntos A y B.

La intersección sobre la unión como medida de similitud para la detección de objetos en imágenes : una tarea importante en la visión por computadora . 

El índice de Jaccard es una estadística que se utiliza para medir la similitud y la diversidad de conjuntos de muestras . Generalmente se define como la razón entre dos tamaños (áreas o volúmenes), es decir, el tamaño de la intersección dividido por el tamaño de la unión, también llamado intersección sobre unión ( IoU ).

El concepto fue introducido por primera vez por Grove Karl Gilbert en 1884 como el “cociente de verificación” en contextos de evaluación de predicciones geológicas. ^{[ 1 ]} y ahora se le suele llamar índice crítico de éxito en meteorología. ^{[ 2 ]} Posteriormente fue desarrollado independientemente por Paul Jaccard , quien originalmente le dio el nombre francés de coefficient de communauté (coeficiente de comunidad), ^{[ 3 ] [ 4 ]} y fue formulado de nuevo independientemente por Taffee Tadashi Tanimoto. ^{[ 5 ]} Por lo tanto, también se le llama índice de Tanimoto o coeficiente de Tanimoto en algunos campos.

El índice de Jaccard mide la similitud entre conjuntos de muestras finitos no vacíos y se define como el tamaño de la intersección dividido por el tamaño de la unión de los conjuntos de muestras:

${\displaystyle J(A,B)={\frac {|A\cap B|}{|A\cup B|}}={\frac {|A\cap B|}{|A|+|B|-|A\cap B|}}.}$

El índice de Jaccard puede interpretarse como una medida normalizada de superposición entre dos conjuntos, donde la intersección representa los elementos compartidos y la unión representa el conjunto total de elementos distintos. Por definición,${\displaystyle 0\leq J(A,B)\leq 1.}$Si los conjuntos${\displaystyle A}$y${\displaystyle B}$no tienen elementos en común, su intersección es vacía, por lo tanto${\displaystyle |A\cap B|=0}$y por lo tanto${\displaystyle J(A,B)=0.}$El otro extremo es que los dos conjuntos sean iguales. En ese caso${\displaystyle A\cap B=A\cup B=A=B,}$conque${\displaystyle J(A,B)=1.}$El índice de Jaccard se utiliza ampliamente en informática, ecología, genómica y otras ciencias donde se utilizan datos binarios o binarizados. ^{[ 6 ] [ 7 ]}

Tanto la solución exacta como los métodos de aproximación están disponibles para la prueba de hipótesis con el índice de Jaccard. ^{[ 8 ]} La similitud de Jaccard también se aplica a bolsas, es decir, multiconjuntos . Tiene una fórmula similar, ^{[ 9 ]} pero los símbolos utilizados representan la intersección de bolsas y la suma de bolsas (no la unión). El valor máximo es 1/2.

${\displaystyle J(A,B)={\frac {|A\cap B|}{|A\uplus B|}}={\frac {|A\cap B|}{|A|+|B|}}.}$

La distancia de Jaccard , que mide la disimilitud entre conjuntos de muestras, es complementaria al índice de Jaccard y se obtiene restando el índice de Jaccard de 1 o, equivalentemente, dividiendo la diferencia de los tamaños de la unión y la intersección de dos conjuntos por el tamaño de la unión:

${\displaystyle d_{J}(A,B)=1-J(A,B)={\frac {|A\cup B|-|A\cap B|}{|A\cup B|}}.}$

Una interpretación alternativa de la distancia de Jaccard es como la razón del tamaño de la diferencia simétrica.${\displaystyle A\mathbin {\triangle } B=(A\cup B)-(A\cap B)}$a la unión. La distancia de Jaccard se usa comúnmente para calcular una matriz n × n para la agrupación y el escalamiento multidimensional de n conjuntos de muestras. Estas medidas de distancia se usan comúnmente en el análisis de clústeres para agrupar observaciones similares. ^{[ 10 ]}

Esta distancia es una métrica sobre la colección de todos los conjuntos finitos. ^{[ 11 ] [ 12 ] [ 13 ]}

También existe una versión de la distancia de Jaccard para medidas , incluidas las medidas de probabilidad . Si${\displaystyle \mu }$es una medida en un espacio mensurable${\displaystyle X}$, luego definimos el índice de Jaccard por

${\displaystyle J_{\mu }(A,B)={\frac {\mu (A\cap B)}{\mu (A\cup B)}},}$

y la distancia de Jaccard por

${\displaystyle d_{\mu }(A,B)=1-J_{\mu }(A,B)={\frac {\mu (A\mathbin {\triangle } B)}{\mu (A\cup B)}}.}$

La definición no está bien definida cuando${\displaystyle \mu (A\cup B)=0}$o${\displaystyle \mu (A\cup B)=\infty }$.

El esquema de hash sensible a la localidad de permutaciones independientes min-wise MinHash se puede utilizar para calcular de manera eficiente una estimación precisa del índice de similitud de Jaccard de pares de conjuntos, donde cada conjunto está representado por una firma de tamaño constante derivada de los valores mínimos de una función hash .

El índice de Jaccard es particularmente útil para analizar conjuntos de datos dispersos y de gran escala en aplicaciones modernas de minería de datos . ^{[ 14 ]}

Dados dos objetos, A y B , cada uno con n atributos binarios , el índice de Jaccard es una medida útil de la superposición que A y B comparten con sus atributos. Cada atributo de A y B puede ser 0 o 1. El número total de cada combinación de atributos para A y B se especifica de la siguiente manera:

${\displaystyle M_{11}}$representa el número total de atributos donde A y B tienen ambos un valor de 1.

${\displaystyle M_{01}}$representa el número total de atributos donde el atributo de A es 0 y el atributo de B es 1.

${\displaystyle M_{10}}$representa el número total de atributos donde el atributo de A es 1 y el atributo de B es 0.

${\displaystyle M_{00}}$representa el número total de atributos donde A y B tienen ambos un valor de 0.

Cada atributo debe encajar en una de estas cuatro categorías, lo que significa que

${\displaystyle M_{11}+M_{01}+M_{10}+M_{00}=n.}$

El índice de similitud de Jaccard, J , se define como

${\displaystyle J={M_{11} \over M_{01}+M_{10}+M_{11}}.}$

La distancia de Jaccard, d _J , se da como

${\displaystyle d_{J}={M_{01}+M_{10} \over M_{01}+M_{10}+M_{11}}=1-J.}$

Se puede realizar inferencia estadística basada en el índice de similitud de Jaccard y, por consiguiente, en métricas relacionadas. ^{[ 8 ]} Dados dos conjuntos de muestras A y B con n atributos, se puede realizar una prueba estadística para ver si una superposición es estadísticamente significativa . La solución exacta está disponible, aunque el cálculo puede ser costoso a medida que n aumenta. ^{[ 8 ]} Los métodos de estimación están disponibles ya sea aproximando una distribución multinomial o mediante bootstrapping . ^{[ 8 ]}

Si${\displaystyle \mathbf {x} =(x_{1},x_{2},\ldots ,x_{n})}$y${\displaystyle \mathbf {y} =(y_{1},y_{2},\ldots ,y_{n})}$son dos vectores con todos los números reales${\displaystyle x_{i},y_{i}\geq 0}$, entonces su índice de similitud de Jaccard (también conocido como similitud de Ruzicka ) se define como

${\displaystyle J_{\mathcal {W}}(\mathbf {x} ,\mathbf {y} )={\frac {\sum _{i}\min(x_{i},y_{i})}{\sum _{i}\max(x_{i},y_{i})}},}$

y la distancia de Jaccard (también conocida entonces como distancia de Soergel)

${\displaystyle d_{J{\mathcal {W}}}(\mathbf {x} ,\mathbf {y} )=1-J_{\mathcal {W}}(\mathbf {x} ,\mathbf {y} ).}$

Con aún mayor generalidad, si${\displaystyle f}$y${\displaystyle g}$son dos funciones medibles no negativas en un espacio medible${\displaystyle X}$con medida${\displaystyle \mu }$, entonces podemos definir

${\displaystyle J_{\mathcal {W}}(f,g)={\frac {\int \min(f,g)d\mu }{\int \max(f,g)d\mu }},}$

dónde${\displaystyle \max }$y${\displaystyle \min }$son operadores puntuales. Entonces la distancia de Jaccard es

${\displaystyle d_{J{\mathcal {W}}}(f,g)=1-J_{\mathcal {W}}(f,g).}$

Luego, por ejemplo, para dos conjuntos medibles${\displaystyle A,B\subseteq X}$, tenemos${\displaystyle J_{\mu }(A,B)=J(\chi _{A},\chi _{B}),}$dónde${\displaystyle \chi _{A}}$y${\displaystyle \chi _{B}}$son las funciones características del conjunto correspondiente.

El cálculo del índice de similitud de Jaccard ponderado para dos vectores normalmente requiere una sola pasada sobre los datos, lo que resulta en una complejidad computacional lineal de${\displaystyle O(n)}$, dónde${\displaystyle n}$representa el número de dimensiones. En aplicaciones de ciencia de datos , esto a menudo se optimiza para vectores dispersos iterando solo sobre elementos distintos de cero, lo que reduce significativamente el tiempo de procesamiento para conjuntos de datos de alta dimensión. Esta optimización traslada la complejidad a${\displaystyle O(k)}$, dónde${\displaystyle k}$es el número de atributos distintos de cero.

# Pseudocódigo para la función de complejidad O(k) jaccardIndex ( vector_A , vector_B ): intersection_sum = 0 union_sum = 0# Obtener el total de claves únicas all_keys = unique_keys ( vector_A . keys () + vector_B . keys ())para cada clave en all_keys : val_a = vector_A.get ( key , 0 ) val_b = vector_B.get ( key , 0 )​​​suma_intersección += min ( val_a , val_b ) suma_unión += max ( val_a , val_b )devolver la suma de la intersección / la suma de la unión

Para optimizar aún más el tiempo de procesamiento, se utilizan técnicas como MinHashing y el hashing sensible a la localidad para aproximar el índice mediante firmas compactas. Estas mejoras algorítmicas garantizan que las medidas de similitud sigan siendo escalables y eficientes, a pesar del aumento en el volumen y la dimensionalidad de los datos. ^{[ 17 ]}

La similitud de Jaccard ponderada descrita anteriormente generaliza el índice de Jaccard a vectores positivos, donde un conjunto corresponde a un vector binario dado por la función indicadora , es decir${\displaystyle x_{i}\in \{0,1\}}$Sin embargo, no generaliza el índice de Jaccard a distribuciones de probabilidad , donde un conjunto corresponde a una distribución de probabilidad uniforme, es decir

${\displaystyle x_{i}={\begin{cases}{\frac {1}{|X|}}&i\in X\\0&{\text{otherwise}}\end{cases}}}$

Siempre es menor si los conjuntos difieren en tamaño. Si${\displaystyle |X|>|Y|}$, y${\displaystyle x_{i}=\mathbf {1} _{X}(i)/|X|,y_{i}=\mathbf {1} _{Y}(i)/|Y|}$entonces

${\displaystyle J_{\mathcal {W}}(x,y)={\frac {|X\cap Y|}{|X\setminus Y|+|X|}}<J(X,Y).}$

En cambio, una generalización que es continua entre las distribuciones de probabilidad y sus conjuntos de soporte correspondientes es

${\displaystyle J_{\mathcal {P}}(x,y)=\sum _{x_{i}\neq 0,y_{i}\neq 0}{\frac {1}{\sum _{j}\max \left({\frac {x_{j}}{x_{i}}},{\frac {y_{j}}{y_{i}}}\right)}}}$

que se denomina Jaccard de "Probabilidad". ^{[ 18 ]} Tiene los siguientes límites con respecto al Jaccard ponderado en vectores de probabilidad.

${\displaystyle J_{\mathcal {W}}(x,y)\leq J_{\mathcal {P}}(x,y)\leq {\frac {2J_{\mathcal {W}}(x,y)}{1+J_{\mathcal {W}}(x,y)}}}$

Aquí el límite superior es el coeficiente de Sørensen-Dice (ponderado) . La distancia correspondiente,${\displaystyle 1-J_{\mathcal {P}}(x,y)}$, es una métrica sobre distribuciones de probabilidad y una pseudométrica sobre vectores no negativos.

El índice de probabilidad de Jaccard tiene una interpretación geométrica como el área de una intersección de símplices . Cada punto en una unidad${\displaystyle k}$-símplex corresponde a una distribución de probabilidad en${\displaystyle k+1}$elementos, porque la unidad${\displaystyle k}$-símplex es el conjunto de puntos en${\displaystyle k+1}$Dimensiones que suman 1. Para derivar geométricamente el Índice de Jaccard de Probabilidad, represente una distribución de probabilidad como el símplice unitario dividido en subsímplices según la masa de cada elemento. Si superpone dos distribuciones representadas de esta manera y cruza los símplices correspondientes a cada elemento, el área restante es igual al Índice de Jaccard de Probabilidad de las distribuciones.

Optimalidad del índice de probabilidad de Jaccard

Consideremos el problema de construir variables aleatorias de tal manera que colisionen entre sí lo máximo posible. Es decir, si${\displaystyle X\sim x}$y${\displaystyle Y\sim y}$, nos gustaría construir${\displaystyle X}$y${\displaystyle Y}$para maximizar${\displaystyle \Pr[X=Y]}$. Si observamos solo dos distribuciones${\displaystyle x,y}$en aislamiento, el más alto${\displaystyle \Pr[X=Y]}$lo que podemos lograr está dado por${\displaystyle 1-{\text{TV}}(x,y)}$dónde${\displaystyle {\text{TV}}}$es la distancia de variación total . Sin embargo, supongamos que no solo nos interesa maximizar ese par en particular, sino que queremos maximizar la probabilidad de colisión de cualquier par arbitrario. Se podría construir un número infinito de variables aleatorias, una para cada distribución.${\displaystyle x}$y buscan maximizar${\displaystyle \Pr[X=Y]}$para todos los pares${\displaystyle x,y}$En un sentido bastante estricto, como se describe a continuación, el Índice de Jaccard de Probabilidad es una forma óptima de alinear estas variables aleatorias.

Para cualquier método de muestreo${\displaystyle G}$y distribuciones discretas${\displaystyle x,y}$, si${\displaystyle \Pr[G(x)=G(y)]>J_{\mathcal {P}}(x,y)}$entonces para algunos${\displaystyle z}$dónde${\displaystyle J_{\mathcal {P}}(x,z)>J_{\mathcal {P}}(x,y)}$y${\displaystyle J_{\mathcal {P}}(y,z)>J_{\mathcal {P}}(x,y)}$, cualquiera${\displaystyle \Pr[G(x)=G(z)]<J_{\mathcal {P}}(x,z)}$o${\displaystyle \Pr[G(y)=G(z)]<J_{\mathcal {P}}(y,z)}$. ^{[ 18 ]}

Es decir, ningún método de muestreo puede lograr más colisiones que${\displaystyle J_{\mathcal {P}}}$en un par sin lograr menos colisiones que${\displaystyle J_{\mathcal {P}}}$en otro par, donde el par reducido es más similar bajo${\displaystyle J_{\mathcal {P}}}$que el par incrementado. Este teorema es válido para el índice de Jaccard de conjuntos (si se interpreta como distribuciones uniformes) y la probabilidad de Jaccard, pero no para el índice de Jaccard ponderado. (El teorema utiliza el término "método de muestreo" para describir una distribución conjunta sobre todas las distribuciones en un espacio, ya que se deriva del uso de algoritmos de minhashing ponderado que logran esto como su probabilidad de colisión).

Este teorema tiene una demostración visual sobre distribuciones de tres elementos utilizando la representación simplex.

En la literatura y en internet aparecen diversas funciones denominadas similitud de Tanimoto y distancia de Tanimoto. La mayoría son sinónimos de similitud de Jaccard y distancia de Jaccard, pero algunas presentan diferencias matemáticas. Numerosas fuentes ^{[ 19 ]} citan un informe técnico de IBM ^{[ 5 ]} como referencia fundamental.

En «Un programa informático para clasificar plantas», publicado en octubre de 1960, ^{[ 20 ]} se presenta un método de clasificación basado en un índice de similitud y una función de distancia derivada. Parece ser la fuente más autorizada para comprender el significado de los términos «similitud de Tanimoto» y «distancia de Tanimoto». El índice de similitud es equivalente a la similitud de Jaccard, pero la función de distancia no es la misma que la distancia de Jaccard.

Otras definiciones de distancia de Tanimoto

La distancia de Tanimoto se suele considerar sinónimo de distancia de Jaccard.${\displaystyle 1-T_{s}}$Esta función es una métrica de distancia adecuada. En la práctica, la distancia de Tanimoto puede confundirse erróneamente con la distancia de Jaccard como métrica de distancia adecuada.

Si la similitud de Jaccard o Tanimoto se expresa sobre un vector de bits, entonces se puede escribir como

${\displaystyle f(A,B)={\frac {A\cdot B}{\|A\|^{2}+\|B\|^{2}-A\cdot B}}}$

donde el mismo cálculo se expresa en términos de producto escalar vectorial y magnitud. Esta representación se basa en el hecho de que, para un vector de bits (donde el valor de cada dimensión es 0 o 1), entonces

${\displaystyle A\cdot B=\sum _{i}A_{i}B_{i}=\sum _{i}(A_{i}\land B_{i})}$

y

${\displaystyle \|A\|^{2}=\sum _{i}A_{i}^{2}=\sum _{i}A_{i}.}$

Esta es una representación potencialmente confusa, porque la función expresada sobre vectores es más general, a menos que su dominio esté explícitamente restringido. Propiedades de${\displaystyle T_{s}}$no necesariamente se extienden a${\displaystyle f}$. En particular, la función de diferencia${\displaystyle 1-f}$no preserva la desigualdad triangular y, por lo tanto, no es una métrica de distancia propia, mientras que${\displaystyle 1-T_{s}}$es.

Existe un peligro real de que la combinación de la "Distancia de Tanimoto" definida mediante esta fórmula, junto con la afirmación "La distancia de Tanimoto es una métrica de distancia adecuada", lleve a la falsa conclusión de que la función${\displaystyle 1-f}$En realidad, se trata de una métrica de distancia sobre vectores o multiconjuntos en general, mientras que su uso en algoritmos de búsqueda de similitud o de agrupamiento puede no producir resultados correctos.

Lipkus ^{[ 12 ]} utiliza una definición de similitud de Tanimoto que es equivalente a${\displaystyle f}$y se refiere a la distancia de Tanimoto como la función${\displaystyle 1-f}$Sin embargo, en el artículo se aclara que el contexto está restringido por el uso de un vector de ponderación (positivo).${\displaystyle W}$de tal manera que, para cualquier vector A que se esté considerando,${\displaystyle A_{i}\in \{0,W_{i}\}.}$En estas circunstancias, la función es una métrica de distancia propia, por lo que un conjunto de vectores regidos por dicho vector de ponderación forma un espacio métrico bajo esta función.

En las matrices de confusión empleadas para la clasificación binaria , el índice de Jaccard se puede formular de la siguiente manera:

${\displaystyle {\text{Jaccard index}}={\frac {TP}{TP+FP+FN}}}$

donde TP son los verdaderos positivos, FP los falsos positivos y FN los falsos negativos.

La fórmula de clasificación binaria del índice de Jaccard mide la concordancia entre los resultados positivos predichos y los resultados positivos reales. Indica el grado de coincidencia entre las predicciones del modelo sobre los casos positivos verdaderos y los casos positivos reales. Un índice de Jaccard más alto indica una mayor aproximación a la predicción.

El índice de Jaccard es una métrica de solapamiento que se define con los elementos de una matriz de confusión. Los verdaderos positivos representan los casos que se predijeron como positivos y que, efectivamente, lo son, creando un solapamiento entre ambos grupos. Los falsos positivos son los casos que se predijeron como positivos pero que en realidad no lo son. De forma similar, los falsos negativos son los casos que se predijeron como negativos pero que, en realidad, son positivos. El índice de Jaccard compara los verdaderos positivos con el conjunto de información relevante.

El índice de Jaccard es útil al comparar los resultados predichos con los resultados reales. El uso de la clasificación binaria junto con el índice de Jaccard ayuda a explicar la fiabilidad de un modelo de predicción. Se utiliza en muchos campos y es común en medicina para pruebas de laboratorio. ^{[ 21 ]}

En informática, el índice de Jaccard se utiliza para medir la similitud entre vértices de un grafo comparando sus conjuntos de adyacencia. Dados dos vértices, su similitud se calcula dividiendo el tamaño de la intersección de sus vecindarios entre el tamaño de su unión. Esta medida se aplica ampliamente en la predicción de enlaces , la detección de comunidades y la clasificación de grafos, donde sirve como guía para estimar la probabilidad de que se forme una arista entre dos nodos en redes. ^{[ 22 ]}

El cálculo de la similitud de Jaccard entre dos vértices se puede expresar utilizando sus conjuntos de adyacencia, como se muestra a continuación. ^{[ 22 ]}

// Código Javascript: function jaccardSimilarity ( graph1 , graph2 ){ const numNodes1 = graph1 . length ; const numNodes2 = graph2 . length ; let similarity = 0 ; // Iterar sobre todos los pares de nodos en ambos grafos for ( let i = 0 ; i < numNodes1 ; i ++ ){ for ( let j = 0 ; j < numNodes2 ; j ++ ){ // Calcular el tamaño de la intersección y la unión de los conjuntos de vecinos const intersectionSize = intersection ( graph1 [ i ], graph2 [ j ]). length ; const unionSize = union ( graph1 [ i ], graph2 [ j ]). length ; // Calcular la similitud de Jaccard y agregarla a la similitud total += intersectionSize / unionSize ; } } // Divide la similitud total por el número de pares de nodos para obtener la similitud promedio de retorno / ( numNodes1 * numNodes2 ); }// Función auxiliar para calcular la intersección de dos matrices function intersection ( a , b ) { return a . filter ( value => b . includes ( value )); }// Función auxiliar para calcular la unión de dos matrices function union ( a , b ){ return [... new Set ([... a , ... b ])]; }

^{[ 22 ]}

La figura anterior muestra una implementación basada en operaciones de conjuntos sobre listas de adyacencia. En la práctica, las representaciones de grafos, como las listas de adyacencia, se utilizan para mejorar la eficiencia de las operaciones de intersección y unión. Para grafos grandes, calcular la similitud entre todos los pares de vértices puede resultar computacionalmente costoso. Los programadores pueden usar aproximaciones para evitar asumir el costo total de este cálculo.

• coeficiente de superposición
• Coeficiente de coincidencia simple
• Precisión y recuperación
• distancia de Hamming
• Coeficiente de Sørensen-Dice , que es equivalente a:${\displaystyle J=S/(2-S)}$y${\displaystyle S=2J/(1+J)}$(${\displaystyle J}$: Índice de Jaccard,${\displaystyle S}$: Coeficiente de Sørensen-Dice)
• Índice de Tversky
• Correlación
• Información mutua , una variante métrica normalizada de la cual es una distancia de Jaccard entrópica.

• Apuntes de clase de Introducción a la Minería de Datos de Tan, Steinbach y Kumar
• Detección de características en imágenes satelitales Dstl de Kaggle - Evaluación