El índice de Jaccard , también conocido como coeficiente de similitud de Jaccard , es una estadística que se utiliza para medir la similitud y diversidad de conjuntos de muestras . Fue desarrollado por Paul Jaccard , originalmente dando el nombre francés coefficient de communauté , [1] y formulado de nuevo de forma independiente por T. Tanimoto. [2] Así, el índice de Tanimoto o el coeficiente de Tanimoto también se utilizan en algunos campos. Sin embargo, son idénticos en general, tomando la relación de intersección sobre unión. El coeficiente de Jaccard mide la similitud entre conjuntos de muestras finitos 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:
Tenga en cuenta que por diseño, Si A y B están vacíos, defina J ( A , B ) = 1. El coeficiente de Jaccard se usa ampliamente en ciencias de la computación, ecología, genómica y otras ciencias, donde se usan datos binarios o binarizados . Tanto la solución exacta como los métodos de aproximación están disponibles para la prueba de hipótesis con el coeficiente de Jaccard. [3]
La similitud de Jaccard también se aplica a las bolsas, es decir, Multisets . Tiene una fórmula similar, [4] pero los símbolos significan intersección de bolsas y suma de bolsas (no unión). El valor máximo es 1/2.
La distancia de Jaccard , que mide la disimilitud entre conjuntos de muestras, es complementaria al coeficiente de Jaccard y se obtiene restando el coeficiente de Jaccard de 1 o, de manera equivalente, 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:
Una interpretación alternativa de la distancia de Jaccard es como la relación entre el tamaño de la diferencia simétrica al sindicato. La distancia de Jaccard se usa comúnmente para calcular una matriz n × n para la agrupación y el escalado multidimensional de n conjuntos de muestras.
Esta distancia es una métrica de la colección de todos los conjuntos finitos. [5] [6] [7]
También hay una versión de la distancia Jaccard para medidas , incluidas las medidas de probabilidad . Sies una medida en un espacio medible , luego definimos el coeficiente de Jaccard por
y la distancia de Jaccard por
Se debe tener cuidado si o , ya que estas fórmulas no están bien definidas en estos casos.
El esquema de hash sensible a la localidad de permutaciones independientes de MinHash se puede utilizar para calcular de manera eficiente una estimación precisa del coeficiente 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 .
Similitud de atributos binarios asimétricos
Dados dos objetos, A y B , cada uno con n atributos binarios , el coeficiente 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:
- representa el número total de atributos donde A y B tienen un valor de 1.
- representa el número total de atributos donde el atributo de A es 0 y el atributo de B es 1.
- representa el número total de atributos donde el atributo de A es 1 y el atributo de B es 0.
- representa el número total de atributos donde A y B tienen un valor de 0.
A B | 0 | 1 |
---|---|---|
0 | ||
1 |
Cada atributo debe caer en una de estas cuatro categorías, lo que significa que
El coeficiente de similitud de Jaccard, J , se da como
La distancia de Jaccard, d J , se da como
La inferencia estadística se puede hacer basándose en los coeficientes de similitud de Jaccard y, en consecuencia, en las métricas relacionadas. [3] 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 resultar costoso a medida que n aumenta. [3] Los métodos de estimación están disponibles mediante la aproximación de una distribución multinomial o mediante bootstrapping. [3]
Diferencia con el coeficiente de coincidencia simple (SMC)
Cuando se utiliza para atributos binarios, el índice de Jaccard es muy similar al coeficiente de coincidencia simple . La principal diferencia es que el SMC tiene el términoen su numerador y denominador, mientras que el índice de Jaccard no lo hace. Por lo tanto, el SMC cuenta tanto las presencias mutuas (cuando un atributo está presente en ambos conjuntos) como la ausencia mutua (cuando un atributo está ausente en ambos conjuntos) como coincidencias y las compara con el número total de atributos en el universo, mientras que el índice de Jaccard solo cuenta la presencia mutua como coincidencias y la compara con el número de atributos que han sido elegidos por al menos uno de los dos conjuntos.
En el análisis de la canasta de mercado , por ejemplo, la canasta de dos consumidores que deseamos comparar puede contener solo una pequeña fracción de todos los productos disponibles en la tienda, por lo que el SMC generalmente arrojará valores muy altos de similitudes incluso cuando las canastas tengan muy poca semejanza, lo que hace que el índice de Jaccard sea una medida de similitud más apropiada en ese contexto. Por ejemplo, considere un supermercado con 1000 productos y dos clientes. La canasta del primer cliente contiene sal y pimienta y la canasta del segundo contiene sal y azúcar. En este escenario, la similitud entre las dos canastas medida por el índice Jaccard sería 1/3, pero la similitud se convierte en 0,998 utilizando el SMC.
En otros contextos, donde 0 y 1 llevan información equivalente (simetría), el SMC es una mejor medida de similitud. Por ejemplo, los vectores de variables demográficas almacenadas en variables ficticias , como el género, se compararían mejor con el SMC que con el índice de Jaccard, ya que el impacto del género en la similitud debería ser igual, independientemente de si el hombre se define como 0 o como mujer. como un 1 o al revés. Sin embargo, cuando tenemos variables ficticias simétricas, se podría replicar el comportamiento del SMC dividiendo las variables ficticias en dos atributos binarios (en este caso, masculino y femenino), transformándolos así en atributos asimétricos, permitiendo el uso del índice de Jaccard sin introduciendo cualquier sesgo. Sin embargo, el SMC sigue siendo más eficiente desde el punto de vista computacional en el caso de variables ficticias simétricas, ya que no requiere agregar dimensiones adicionales.
Similitud y distancia ponderadas de Jaccard
Si y son dos vectores con todo real , entonces su coeficiente de similitud de Jaccard (también conocido entonces como similitud de Ruzicka) se define como
y distancia de Jaccard (también conocida entonces como distancia de Soergel)
Con aún más generalidad, si y son dos funciones medibles no negativas en un espacio medible con medida , entonces podemos definir
dónde y son operadores puntuales. Entonces la distancia Jaccard es
Entonces, por ejemplo, para dos conjuntos medibles , tenemos dónde y son las funciones características del conjunto correspondiente.
Probabilidad similitud y distancia de Jaccard
La similitud ponderada de Jaccard 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. 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
Siempre es menor si los conjuntos difieren en tamaño. Si, y luego
En cambio, una generalización que es continua entre las distribuciones de probabilidad y sus correspondientes conjuntos de soporte es
que se llama Jaccard "Probabilidad". [8] Tiene los siguientes límites contra el Jaccard ponderado en vectores de probabilidad.
Aquí, el límite superior es el coeficiente de Sørensen-Dice (ponderado) . La distancia correspondiente,, 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 simples . Cada punto de una unidad-simplex corresponde a una distribución de probabilidad en elementos, porque la unidad -simplex es el conjunto de puntos en dimensiones que suman 1. Para derivar el índice de probabilidad de Jaccard geométricamente, represente una distribución de probabilidad como la unidad simplex dividida en sub simples de acuerdo con la masa de cada elemento. Si superpone dos distribuciones representadas de esta manera una encima de la otra y cruza los simples correspondientes a cada elemento, el área que queda es igual al índice de probabilidad de Jaccard de las distribuciones.
Optimidad del índice de probabilidad de Jaccard
Considere el problema de construir variables aleatorias de manera que colisionen entre sí tanto como sea posible. Es decir, si y , nos gustaría construir y para maximizar . Si miramos solo dos distribuciones en aislamiento, el más alto que podemos lograr está dado por dónde es la distancia de variación total . Sin embargo, supongamos que no solo nos preocupamos por maximizar ese par en particular, supongamos que nos gustaría 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.y busca maximizar para todos los pares . En un sentido bastante fuerte que 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 y distribuciones discretas , Si entonces para algunos dónde y , ya sea o . [8]
Es decir, ningún método de muestreo puede lograr más colisiones que en un par sin lograr menos colisiones que en otro par, donde el par reducido es más similar bajo que el par aumentado. Este teorema es cierto para el índice de conjuntos de Jaccard (si se interpreta como distribuciones uniformes) y la probabilidad de Jaccard, pero no para el Jaccard ponderado. (El teorema usa la palabra "método de muestreo" para describir una distribución conjunta sobre todas las distribuciones en un espacio, porque se deriva del uso de algoritmos de minhashing ponderados que logran esto como su probabilidad de colisión).
Este teorema tiene una demostración visual de distribuciones de tres elementos usando la representación simplex.
Similitud y distancia de Tanimoto
Varias formas de funciones descritas como similitud de Tanimoto y distancia de Tanimoto ocurren en la literatura y en Internet. La mayoría de estos son sinónimos de similitud Jaccard y distancia Jaccard, pero algunos son matemáticamente diferentes. Muchas fuentes [9] citan un Informe técnico de IBM [2] como referencia fundamental. El informe está disponible en varias bibliotecas .
En "Un programa informático para clasificar plantas", publicado en octubre de 1960, [10] se da un método de clasificación basado en una relación de similitud y una función de distancia derivada. Parece que esta es la fuente más autorizada para el significado de los términos "similitud de Tanimoto" y "Distancia de Tanimoto". La relación de similitud es equivalente a la similitud de Jaccard, pero la función de distancia no es la misma que la distancia de Jaccard.
Las definiciones de similitud y distancia de Tanimoto
En ese documento, se da una "relación de similitud" sobre mapas de bits , donde cada bit de una matriz de tamaño fijo representa la presencia o ausencia de una característica en la planta que se está modelando. La definición de la relación es el número de bits comunes, dividido por el número de bits establecidos ( es decir, distinto de cero) en cualquiera de las muestras.
Presentado en términos matemáticos, si las muestras X e Y son mapas de bits,es el i- ésimo bit de X , yson operadores bit a bit y , or respectivamente, entonces la relación de similitud es
Si cada muestra se modela en cambio como un conjunto de atributos, este valor es igual al coeficiente de Jaccard de los dos conjuntos. Jaccard no se cita en el artículo y parece probable que los autores no lo supieran.
Tanimoto pasa a definir un "coeficiente de distancia" basado en esta relación, definida para mapas de bits con similitud distinta de cero:
Este coeficiente, deliberadamente, no es una métrica de distancia. Se elige para permitir la posibilidad de que dos ejemplares, que son bastante diferentes entre sí, sean similares a un tercero. Es fácil construir un ejemplo que refute la propiedad de la desigualdad triangular .
Otras definiciones de distancia de Tanimoto
La distancia de Tanimoto a menudo se denomina, erróneamente, como sinónimo de distancia de Jaccard. . Esta función es una métrica de distancia adecuada. La "Distancia de Tanimoto" se indica a menudo como una métrica de distancia adecuada, probablemente debido a su confusión con la distancia de Jaccard.
Si la similitud de Jaccard o Tanimoto se expresa sobre un vector de bits, entonces se puede escribir como
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
y
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 no necesariamente se extienden a . En particular, la función de diferenciano conserva la desigualdad del triángulo y, por lo tanto, no es una métrica de distancia adecuada, mientras que es.
Existe un peligro real de que la combinación de "Distancia de Tanimoto" que se define 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 de hecho, es una métrica de distancia sobre vectores o conjuntos múltiples en general, mientras que su uso en algoritmos de búsqueda de similitud o agrupamiento puede fallar en producir resultados correctos.
Lipkus [6] utiliza una definición de similitud de Tanimoto que es equivalente a, y se refiere a la distancia de Tanimoto como la función . Sin embargo, se aclara en el documento que el contexto está restringido por el uso de un vector de ponderación (positivo)tal que, para cualquier vector A considerado,En estas circunstancias, la función es una métrica de distancia adecuada, por lo que un conjunto de vectores gobernados por dicho vector de ponderación forma un espacio métrico bajo esta función.
Índice de Jaccard en matrices de confusión de clasificación binaria
En las matrices de confusión empleadas para la clasificación binaria , el índice de Jaccard se puede enmarcar en la siguiente fórmula:
donde TP son los verdaderos positivos, TN son los verdaderos negativos, FP son los falsos positivos y FN son los falsos negativos. [11]
Ver también
- Coeficiente de superposición
- Coeficiente de coincidencia simple
- Distancia de Hamming
- Coeficiente de Sørensen-Dice , que es equivalente: y (: Índice de Jaccard, : 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.
Referencias
- ^ Jaccard, Paul (febrero de 1912). "LA DISTRIBUCIÓN DE LA FLORA EN LA ZONA ALPINA.1" . Nuevo fitólogo . 11 (2): 37–50. doi : 10.1111 / j.1469-8137.1912.tb05611.x . ISSN 0028-646X .
- ^ a b Tanimoto TT (17 de noviembre de 1958). "Una teoría matemática elemental de clasificación y predicción". Informe técnico interno de IBM . 1957 (¿8?).
- ^ a b c d Chung NC, Miasojedow B, Startek M, Gambin A (diciembre de 2019). "Ensayo de similitud Jaccard / Tanimoto y métodos de estimación para datos biológicos de presencia-ausencia" . BMC Bioinformática . 20 (Suppl 15): 644. doi : 10.1186 / s12859-019-3118-5 . PMC 6929325 . PMID 31874610 .
- ^ Leskovec J, Rajaraman A, Ullman J (2020). Minería de conjuntos de datos masivos . Cambridge. ISBN 9781108476348.y P. 76-77 en una versión anterior http://infolab.stanford.edu/~ullman/mmds/ch3.pdf
- ^ Kosub S (abril de 2019). "Una nota sobre la desigualdad del triángulo para la distancia de Jaccard". Cartas de reconocimiento de patrones . 120 : 36–8. arXiv : 1612.02696 . doi : 10.1016 / j.patrec.2018.12.007 .
- ^ a b Lipkus AH (1999). "Una prueba de la desigualdad del triángulo para la distancia de Tanimoto". Revista de Química Matemática . 26 (1-3): 263-265. doi : 10.1023 / A: 1019154432472 .
- ^ Levandowsky M, Winter D (1971). "Distancia entre conjuntos". Naturaleza . 234 (5): 34–35. doi : 10.1038 / 234034a0 .
- ^ a b Moulton R, Jiang Y (2018). "Muestreo de máxima coherencia y el índice de Jaccard de distribuciones de probabilidad". Conferencia internacional sobre minería de datos, taller sobre minería de datos de alta dimensión : 347–356. arXiv : 1809.04052 . doi : 10.1109 / ICDM.2018.00050 . ISBN 978-1-5386-9159-5.
- ^ Por ejemplo Huihuan Q, Xinyu W, Yangsheng X (2011). Sistemas de vigilancia inteligente . Saltador. pag. 161. ISBN 978-94-007-1137-2.
- ^ Rogers DJ, Tanimoto TT (octubre de 1960). "Un programa informático para la clasificación de plantas". Ciencia . 132 (3434): 1115–8. doi : 10.1126 / science.132.3434.1115 . PMID 17790723 .
- ^ Aziz Taha, Abdel (2015). "Métricas para evaluar la segmentación de imágenes médicas 3D: análisis, selección y herramienta" . Imágenes médicas de BMC . 15 (29): 1–28. doi : 10.1186 / s12880-015-0068-x .
Otras lecturas
- Tan PN, Steinbach M, Kumar V (2005). Introducción a la minería de datos . ISBN 0-321-32136-7.
- Jaccard P (1901). "Étude comparative de la distribution florale dans une porción des Alpes et des Jura". Bulletin de la Société vaudoise des sciences naturelles . 37 : 547–579.
- Jaccard P (1912). "La distribución de la flora en la zona alpina". Nuevo fitólogo . 11 (2): 37–50. doi : 10.1111 / j.1469-8137.1912.tb05611.x .
enlaces externos
- Introducción a las notas de clase de la minería de datos de Tan, Steinbach, Kumar
- SimMetrics, una implementación de sourceforge del índice Jaccard y muchas otras métricas de similitud
- Una calculadora basada en la web para encontrar el coeficiente de Jaccard
- Tutorial sobre cómo calcular diferentes similitudes
- Intersección sobre Unión (IoU) para detección de objetos
- Detección de características de imágenes satelitales Kaggle Dstl - Evaluación