En estadística, la distancia del motor de la tierra ( EMD ) es una medida de la distancia entre dos distribuciones de probabilidad sobre una región D . En matemáticas, esto se conoce como la métrica de Wasserstein . De manera informal, si las distribuciones se interpretan como dos formas diferentes de apilar una cierta cantidad de tierra (tierra) sobre la región D , el EMD es el costo mínimo de convertir una pila en otra; donde se supone que el costo es la cantidad de tierra movida multiplicada por la distancia por la que se mueve. [1]
La definición anterior es válida solo si las dos distribuciones tienen la misma integral (informalmente, si las dos pilas tienen la misma cantidad de suciedad), como en los histogramas normalizados o en las funciones de densidad de probabilidad . En ese caso, el EMD es equivalente a la primera distancia de Mallows o la primera distancia de Wasserstein entre las dos distribuciones. [2] [3]
Teoría
Suponga que tenemos un conjunto de puntos en (dimensión ). En lugar de asignar una distribución al conjunto de puntos, podemos agruparlos y representar el conjunto de puntos en términos de los grupos. Por lo tanto, cada grupo es un solo punto eny el peso del conglomerado se decide por la fracción de la distribución presente en ese conglomerado. Esta representación de una distribución mediante un conjunto de clústeres se denomina firma . Dos firmas pueden tener diferentes tamaños, por ejemplo, una distribución bimodal tiene una firma más corta (2 grupos) que las complejas. Una representación de clúster (media o moda en) se puede considerar como una característica única en una firma. La distancia entre cada una de las características se denomina distancia al suelo .
La distancia de Earth Mover se puede formular y resolver como un problema de transporte . Suponga que se requieren varios proveedores, cada uno con una determinada cantidad de bienes, para abastecer a varios consumidores, cada uno con una determinada capacidad limitada. Para cada par de proveedor-consumidor, se da el costo de transportar una sola unidad de bienes. El problema del transporte es entonces encontrar un flujo de bienes menos costoso de los proveedores a los consumidores que satisfaga la demanda de los consumidores. De manera similar, aquí el problema es transformar una firma () a otro() con un trabajo mínimo realizado.
Asume esa firma posee agrupaciones con , dónde es el representante del clúster y es el peso del racimo. Del mismo modo, otra firma posee racimos. Dejar ser la distancia del suelo entre los racimos y .
Queremos encontrar un flujo , con el flujo entre y , que minimiza el costo total.
sujeto a las limitaciones:
El flujo óptimo se encuentra resolviendo este problema de optimización lineal. La distancia del movimiento de tierra se define como el trabajo normalizado por el flujo total:
Extensiones
Algunas aplicaciones pueden requerir la comparación de distribuciones con diferentes masas totales. Un enfoque es permitir una coincidencia parcial , donde la suciedad de la distribución más masiva se reorganiza para hacer la menos masiva, y cualquier "suciedad" sobrante se desecha sin costo alguno. Bajo este enfoque, el EMD ya no es una verdadera distancia entre distribuciones.
Otro enfoque es permitir la creación o destrucción de masa, a nivel global y / o local, como una alternativa al transporte, pero con una penalización de costo. En ese caso, se debe especificar un parámetro real σ, la relación entre el costo de crear o destruir una unidad de "suciedad" y el costo de transportarla por una unidad de distancia. Esto equivale a minimizar la suma del costo de movimiento de tierra más σ veces la distancia L 1 entre el pilote reordenado y la segunda distribución.
Notablemente, si es una función parcial que es una biyección en subconjuntos y , entonces uno está interesado en la función de distancia
dónde denota conjunto menos . Aquí,sería la porción de la tierra que fue movida; por lo tanto sería la parte no movida, y el tamaño de la pila no se movió. Por simetría, uno contemplacomo la pila en el destino que 'llegó allí' de P , en comparación con el Q total que queremos tener allí . Formalmente, esta distancia indica cuánto difiere una correspondencia inyectiva de un isomorfismo .
El EMD se puede extender naturalmente al caso en el que se comparan más de dos distribuciones. En este caso, la "distancia" entre las muchas distribuciones se define como el valor óptimo de un programa lineal. Este EMD generalizado se puede calcular exactamente usando un algoritmo codicioso, y se ha demostrado que el funcional resultante es aditivo de Minkowski y monótono convexo. [4]
Computando el EMD
El EMD se puede calcular resolviendo una instancia de problema de transporte , utilizando cualquier algoritmo para problemas de flujo de costo mínimo , por ejemplo, el algoritmo de red simplex .
El algoritmo húngaro se puede utilizar para obtener la solución si el dominio D es el conjunto {0, 1}. Si el dominio es integral, se puede traducir para el mismo algoritmo representando contenedores integrales como múltiples contenedores binarios.
Como caso especial, si D es una matriz unidimensional de "contenedores" de tamaño n , el EMD se puede calcular de manera eficiente escaneando la matriz y realizando un seguimiento de la cantidad de suciedad que se necesita transportar entre contenedores consecutivos. Aquí los contenedores están indexados a cero :
Análisis de similitud basado en EMD
El análisis de similitud basado en EMD (EMDSA) es una herramienta importante y eficaz en muchas aplicaciones de recuperación de información multimedia [5] y reconocimiento de patrones [6] . Sin embargo, el costo computacional de EMD es supercúbico al número de "contenedores" dado una "D" arbitraria. Se han investigado técnicas de cálculo EMD eficientes y escalables para datos a gran escala utilizando MapReduce , [7] [8] , así como un conjunto de datos distribuidos resilientes y paralelos síncronos masivos . [9]
Aplicaciones
Una de las primeras aplicaciones del EMD en ciencias de la computación fue comparar dos imágenes en escala de grises que pueden diferir debido a difuminado , difuminado o deformaciones locales. [10] En este caso, la región es el dominio de la imagen y la cantidad total de luz (o tinta) es la "suciedad" que se debe reorganizar.
El EMD se usa ampliamente en la recuperación de imágenes basada en contenido para calcular distancias entre los histogramas de color de dos imágenes digitales . [ cita requerida ] En este caso, la región es el cubo de color RGB , y cada píxel de la imagen es una parcela de "suciedad". La misma técnica se puede utilizar para cualquier otro atributo de píxel cuantitativo , como luminancia , gradiente , movimiento aparente en un fotograma de vídeo , etc.
De manera más general, el EMD se utiliza en el reconocimiento de patrones para comparar resúmenes genéricos o sustitutos de registros de datos llamados firmas . Una firma típica consiste en una lista de pares (( x 1 , m 1 ), ... ( x n , m n )), donde cada x i es una determinada "característica" (p. Ej., Color en una imagen, letra en una texto, etc.), y m i es "masa" (cuántas veces aparece esa característica en el registro). Alternativamente, x i puede ser el centroide de un grupo de datos y m i el número de entidades en ese grupo. Para comparar dos de estas firmas con el EMD, se debe definir una distancia entre características, que se interpreta como el costo de convertir una unidad de masa de una característica en una unidad de masa de la otra. El EMD entre dos firmas es entonces el costo mínimo de convertir una de ellas en la otra.
El análisis de EMD se ha utilizado para cuantificar cambios multivariados en biomarcadores medidos por citometría de flujo , con aplicaciones potenciales a otras tecnologías que informan distribuciones de medidas. [11]
Historia
El concepto fue introducido por primera vez por Gaspard Monge en 1781, [12] en el contexto de la teoría del transporte . El uso del EMD como medida de distancia para imágenes monocromáticas fue descrito en 1989 por S. Peleg, M. Werman y H. Rom. [10] El nombre "distancia de los movimientos de tierra" fue propuesto por J. Stolfi en 1994, [13] y fue utilizado en forma impresa en 1998 por Y. Rubner, C. Tomasi y LG Guibas . [14]
Referencias
- ^ Definición formal
- ^ Elizaveta Levina ; Peter Bickel (2001). "La distancia del EarthMover es la distancia de Mallows: algunas ideas de las estadísticas". Actas de ICCV 2001 . Vancouver, Canadá: 251–256.
- ^ CL Mallows (1972). "Una nota sobre la normalidad articular asintótica" . Anales de estadística matemática . 43 (2): 508–515. doi : 10.1214 / aoms / 1177692631 .
- ^ Kline, Jeffery (2019). "Propiedades del problema del movimiento de tierra d-dimensional". Matemáticas aplicadas discretas . 265 : 128-141. doi : 10.1016 / j.dam.2019.02.042 .
- ^ Mark A. Ruzon; Carlo Tomasi (2001). "Detección de bordes, uniones y esquinas mediante distribuciones de color". Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas .
- ^ Kristen Grauman; Trevor Darrel (2004). "Ajuste de contorno rápido utilizando la distancia aproximada del movimiento de tierra". Actas de CVPR 2004 .
- ^ Jin Huang; Rui Zhang; Rajkumar Buyya; Jian Chen (2014). "MELODY-Join: similitud de distancia de Efficient Earth Mover se une mediante MapReduce". Actas de la Conferencia Internacional IEEE sobre Ingeniería de Datos .
- ^ Jia Xu; Bin Lei; Yu Gu; Winslett, M .; Ge Yu; Zhenjie Zhang (2015). "Unión de similitud eficiente basada en la distancia de Earth Mover usando MapReduce". Transacciones IEEE sobre conocimiento e ingeniería de datos .
- ^ Jin Huang; Rui Zhang; Rajkumar Buyya; Jian Chen, M .; Yongwei Wu (2015). "Jefes-Join: Distancia de Efficient Earth Mover's Join en Hadoop". Transacciones IEEE en sistemas paralelos y distribuidos .
- ^ a b S. Peleg; M. Werman; H. Rom (1989). "Un enfoque unificado para el cambio de resolución: espacio y nivel de grises". Transacciones IEEE sobre análisis de patrones e inteligencia de máquinas . 11 (7): 739–742. doi : 10.1109 / 34.192468 .
- ^ Orlova, DY; Zimmerman, N; Meehan, C; Meehan, S; Waters, J; Ghosn, EEB (23 de marzo de 2016). "Earth Mover's Distance (EMD): una verdadera métrica para comparar niveles de expresión de biomarcadores en poblaciones celulares" . PLOS One . 11 (3): e0151859. doi : 10.1371 / journal.pone.0151859 . PMC 4805242 . PMID 27008164 .
- ^ "Mémoire sur la théorie des déblais et des remblais". Histoire de l'Académie Royale des Science, Année 1781, avec les Mémoires de Mathématique et de Physique . 1781.
- ^ J. Stolfi, comunicación personal a LJ Guibas, 1994, citado por Rubner, Yossi; Tomasi, Carlo; Guibas, Leonidas J. (2000). "La distancia del movimiento de tierra como métrica para la recuperación de imágenes" (PDF) . Revista Internacional de Visión por Computador . 40 (2): 99-121. doi : 10.1023 / A: 1026543900054 .
- ^ Yossi Rubner; Carlo Tomasi; Leonidas J. Guibas (1998). "Una métrica para distribuciones con aplicaciones a bases de datos de imágenes". Proceedings ICCV 1998 : 59–66. doi : 10.1109 / ICCV.1998.710701 . ISBN 81-7319-221-9.
enlaces externos
- Código C para la distancia del motor de la tierra
- Implementación de Python con referencias
- Envoltorio de Python2 para la implementación C de Earth Mover's Distance
- Los envoltorios de C ++ y Matlab y Java codifican para la distancia de Earth Mover, especialmente eficiente para distancias de tierra con umbrales
- Implementación de Java de un generador genérico para evaluar el análisis de similitud basado en la distancia de Earth Mover a gran escala