stringtranslate.com

índice jaccard

Intersección y unión de dos conjuntos A y B
Intersección sobre unión como medida de similitud para la detección de objetos en imágenes: una tarea importante en visión por computadora .

El índice de Jaccard , también conocido como coeficiente de similitud de Jaccard , es una estadística utilizada para medir la similitud y diversidad de conjuntos de muestras .

Fue desarrollado por Grove Karl Gilbert en 1884 como su índice de verificación (v) [1] y ahora se lo conoce con frecuencia como el Índice de Éxito Crítico en meteorología. [2] Posteriormente fue desarrollado de forma independiente por Paul Jaccard , dándole originalmente el nombre francés de coeficiente de communauté , [3] [4] y formulado nuevamente de forma independiente por T. Tanimoto. [5] Así, el índice de Tanimoto o coeficiente de Tanimoto también se utilizan en algunos campos. Sin embargo, son idénticos en general al tomar la proporción de Intersección sobre Unión .

Descripción general

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 intersección B está vacía, entonces J ( A , B ) = 0. El coeficiente de Jaccard se usa ampliamente en informática, ecología, genómica y otras ciencias, donde se utilizan 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. [6]

La similitud de Jaccard también se aplica a los bolsos, es decir, a los Multisets . Esto tiene una fórmula similar, [7] 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 y la unión. La distancia de Jaccard se usa comúnmente para calcular una matriz n × n para agrupación y escalamiento multidimensional de n conjuntos de muestras.

Esta distancia es una métrica de la colección de todos los conjuntos finitos. [8] [9] [10]

También existe una versión de la distancia de Jaccard para medidas , incluidas medidas de probabilidad . Si es una medida en un espacio mensurable , entonces definimos el coeficiente de Jaccard por

y la distancia de Jaccard por

Hay que 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 min-wise 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.

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

El coeficiente de similitud de Jaccard, J , viene dado como

La distancia de Jaccard, d J , viene dada como

Se puede realizar inferencia estadística basándose en los coeficientes de similitud de Jaccard y, en consecuencia, en las métricas relacionadas. [6] 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. [6] Los métodos de estimación están disponibles ya sea mediante la aproximación de una distribución multinomial o mediante bootstrapping. [6]

Diferencia con el coeficiente de emparejamiento 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érmino en su numerador y denominador, mientras que el índice Jaccard no. Por lo tanto, el SMC cuenta tanto la presencia mutua (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 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 cesta de la compra , por ejemplo, la cesta de dos consumidores que deseamos comparar puede contener sólo una pequeña fracción de todos los productos disponibles en la tienda, por lo que el SMC normalmente arrojará valores muy altos de similitudes incluso cuando las cestas tengan valores muy altos. poca semejanza, lo que hace que el índice de Jaccard sea una medida de similitud más apropiada en ese contexto. Por ejemplo, pensemos en 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 cestas medida por el índice de Jaccard sería 1/3, pero la similitud llega a 0,998 utilizando el SMC.

En otros contextos, donde 0 y 1 contienen información equivalente (simetría), el SMC es una mejor medida de similitud. Por ejemplo, los vectores de variables demográficas almacenados 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 lo masculino se define como 0 y lo femenino. 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 ficticias en dos atributos binarios (en este caso, masculino y femenino), transformándolos así en atributos asimétricos, permitiendo el uso del índice Jaccard sin introduciendo cualquier sesgo. Sin embargo, el SMC sigue siendo más eficiente computacionalmente 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

donde y son operadores puntuales. Entonces la distancia de Jaccard es

Entonces, por ejemplo, para dos conjuntos medibles , tenemos donde y son las funciones características del conjunto correspondiente.

Probabilidad de 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 entonces

El índice de probabilidad de Jaccard puede interpretarse como intersecciones de simples.

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

que se llama "Probabilidad" Jaccard. [11] 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 en una unidad simplex corresponde a una distribución de probabilidad de elementos, porque la unidad simplex es el conjunto de puntos en dimensiones que suman 1. Para derivar geométricamente el índice de probabilidad de Jaccard, represente una distribución de probabilidad como la unidad simplex dividida en subsimplices según 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 Jaccard de las distribuciones.

Optimidad del índice de probabilidad Jaccard

Una prueba visual de la optimización del índice de probabilidad Jaccard en distribuciones de tres elementos.

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 maximizar . Si observamos solo dos distribuciones de forma aislada, lo más alto que podemos lograr viene dado por dónde está la distancia de variación total . Sin embargo, supongamos que no sólo nos preocupamos por maximizar ese par en particular, supongamos que quisiéramos 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 tratar de maximizar para todos los pares . En el sentido bastante estricto que se describe a continuación, el índice de probabilidad Jaccard es una forma óptima de alinear estas variables aleatorias.

Para cualquier método de muestreo y distribuciones discretas , si, entonces, para algún lugar y , o o . [11]

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 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 utiliza 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 minhashing ponderados que logran esto como su probabilidad de colisión).

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

Similitud y distancia de Tanimoto.

En la literatura y en Internet se encuentran varias formas de funciones descritas como similitud de Tanimoto y distancia de Tanimoto. La mayoría de estos son sinónimos de similitud de Jaccard y distancia de Jaccard, pero algunos son matemáticamente diferentes. Muchas fuentes [12] citan un informe técnico de IBM [5] como referencia fundamental. El informe está disponible en varias bibliotecas.

En "Un programa informático para clasificar plantas", publicado en octubre de 1960, [13] se proporciona 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.

Definiciones de Tanimoto de similitud y distancia.

En ese artículo, se proporciona 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, distintos 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 y son operadores bit a bit y u respectivamente, entonces la relación de similitud es

Si cada muestra se modela 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. [ cita necesaria ]

Tanimoto continúa definiendo un "coeficiente de distancia" basado en esta relación, definida para mapas de bits con similitud distinta de cero:

Este coeficiente no es, deliberadamente, una métrica de distancia. Se elige para permitir la posibilidad de que dos especímenes, 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

A menudo se hace referencia, erróneamente, a la distancia Tanimoto como sinónimo de distancia Jaccard . Esta función es una métrica de distancia adecuada. La "Distancia Tanimoto" a menudo se considera una métrica de distancia adecuada, probablemente debido a su confusión con la distancia 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. Las propiedades de no necesariamente se extienden a . En particular, la función de diferencia no preserva la desigualdad del triángulo y, por lo tanto, no es una métrica de distancia adecuada, mientras que sí lo es.

Existe un peligro real de que la combinación de la "Distancia de Tanimoto" definida utilizando esta fórmula, junto con la afirmación "La Distancia de Tanimoto es una métrica de distancia adecuada" lleve a la conclusión falsa de que la función es, de hecho, una métrica de distancia sobre vectores o conjuntos múltiples en general, mientras que su uso en búsqueda de similitudes o algoritmos de agrupamiento puede no producir resultados correctos.

Lipkus [9] 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 deja claro en el artículo que el contexto está restringido por el uso de un vector de ponderación (positivo) tal que, para cualquier vector A que se considere, en estas circunstancias, la función es una métrica de distancia adecuada, por lo que una 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, FP los falsos positivos y FN los falsos negativos. [14]

Ver también

Referencias

  1. ^ Murphy, Allan H. (1996). "El asunto Finley: un evento señalado en la historia de la verificación de pronósticos". Meteorología y previsión . 11 (1): 3. Código Bib : 1996WtFor..11....3M. doi : 10.1175/1520-0434(1996)011<0003:TFAASE>2.0.CO;2 . ISSN  1520-0434. S2CID  54532560.
  2. ^ "Glosario de verificación de pronósticos" (PDF) . noaa.gov . Consultado el 21 de mayo de 2023 .
  3. ^ Jaccard, Paul (1901). "Étude comparativo de la distribución floral en una porción de los Alpes y el Jura". Boletín de la Sociedad Vaudoise des Sciences Naturelles . 37 : 547–579.
  4. ^ 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. S2CID  85574559.
  5. ^ ab 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?).
  6. ^ abcd Chung NC, Miasojedow B, Startek M, Gambin A (diciembre de 2019). "Métodos de estimación y prueba de similitud de Jaccard / Tanimoto para datos biológicos de presencia-ausencia". Bioinformática BMC . 20 (Suplemento 15): 644. arXiv : 1903.11372 . doi : 10.1186/s12859-019-3118-5 . PMC 6929325 . PMID  31874610. 
  7. ^ 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
  8. ^ Kosub S (abril de 2019). "Una nota sobre la desigualdad del triángulo para la distancia de Jaccard". Letras de reconocimiento de patrones . 120 : 36–8. arXiv : 1612.02696 . Código Bib : 2019PaReL.120...36K. doi :10.1016/j.patrec.2018.12.007. S2CID  564831.
  9. ^ ab 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. S2CID  118263043.
  10. ^ Levandowsky M, Invierno D (1971). "Distancia entre series". Naturaleza . 234 (5): 34–35. Código Bib :1971Natur.234...34L. doi :10.1038/234034a0. S2CID  4283015.
  11. ^ ab Moulton R, Jiang Y (2018). "Muestreo máximamente consistente y el índice Jaccard de distribuciones de probabilidad". Conferencia internacional IEEE 2018 sobre minería de datos (ICDM) . págs. 347–356. arXiv : 1809.04052 . doi :10.1109/ICDM.2018.00050. ISBN 978-1-5386-9159-5. S2CID  49746072.
  12. ^ Por ejemplo Huihuan Q, Xinyu W, Yangsheng X (2011). Sistemas Inteligentes de Vigilancia . Saltador. pag. 161.ISBN 978-94-007-1137-2.
  13. ^ Rogers DJ, Tanimoto TT (octubre de 1960). "Un programa informático para clasificar plantas". Ciencia . 132 (3434): 1115–8. Código bibliográfico : 1960 Ciencia... 132.1115R. doi : 10.1126/ciencia.132.3434.1115. PMID  17790723.
  14. ^ Aziz Taha, Abdel (2015). "Métricas para evaluar la segmentación de imágenes médicas 3D: análisis, selección y herramienta". BMC Imágenes Médicas . 15 (29): 1–28. doi : 10.1186/s12880-015-0068-x . PMC 4533825 . PMID  26263899. 

Otras lecturas

enlaces externos