Distancia de edición de gráfico

La distancia de edición del gráfico es el coeficiente de similitud (o diferencia) entre dos gráficos . El concepto de distancia de edición de gráficos fue formulado matemáticamente por primera vez por Alberto Sanfeliu y King-San Fu en 1983 [1] . La principal aplicación de la distancia de edición de gráficos es la coincidencia de gráficos inexactos , como el reconocimiento de patrones robusto en el aprendizaje automático [2] .

La distancia de edición de gráficos entre dos gráficos está relacionada con la distancia de edición entre filas . Al interpretar los sumideros como gráficos acíclicos dirigidos conectados con un grado máximo de dos, las definiciones clásicas de distancia de edición, como la distancia de Levenshtein [3] , la distancia de Hamming [4] y la distancia de Jaro-Winkler , pueden interpretarse como distancias de edición de gráficos entre gráficos adecuados. De manera similar, la distancia de edición de gráficos es una generalización de la distancia de edición de árboles entre árboles enraizados [5] [6] [7] [8] .

Definiciones y propiedades formales

La definición matemática de la distancia de edición del gráfico depende de la definición de los gráficos para los que se define la distancia. Por ejemplo, depende de si los vértices y los bordes del gráfico están etiquetados y cómo , y también de si el gráfico está dirigido . En general, dado un conjunto de operaciones de edición de gráficos (también conocidas como operaciones de gráficos elementales ), la distancia de edición de gráficos entre dos gráficos y , escrita como , se puede definir como ${\ estilo de visualización g_ {1}}$ ${\ estilo de visualización g_ {2}}$ $GED(g_{1},g_{2})$

GED(g_{1},g_{2})=\min_{(e_{1},...,e_{k})\in {\mathcal {P))(g_{1}, g_{2})}\sum_{i=1}^{k}c(e_{i})

donde significa el conjunto de caminos de transformación a ( isomorfos al gráfico) , y es igual al costo de cada operación de edición . ${\mathcal {P}}(g_{1},g_{2})$ ${\ estilo de visualización g_ {1}}$ ${\ estilo de visualización g_ {2}}$ ${\ Displaystyle c (e) \ geqslant 0}$ $mi$

El conjunto de operaciones gráficas elementales generalmente incluye:

inserción de vértice: se inserta un nuevo vértice etiquetado en el gráfico. Eliminación de vértices: se elimina un vértice (a menudo no relacionado) del gráfico. sustituir un vértice - cambiar la etiqueta (o color) de un vértice dado. inserción de borde: se inserta un nuevo borde coloreado en el gráfico entre un par de vértices. eliminación de aristas — eliminación de una arista entre un par de vértices. Sustitución de borde : cambie la etiqueta (o el color) de un borde dado.

Además, pero más raramente, operaciones como dividir un borde , que inserta un nuevo vértice en un borde (lo que da como resultado dos bordes), y reducir un borde , que elimina un vértice de grado dos entre los bordes (del mismo color) mientras fusionando los dos bordes, se incluyen en uno. Si bien operaciones tan complejas pueden definirse en términos de transformaciones más simples, su uso permite una mejor parametrización de la función de costo cuando el operador es más económico que la suma de sus partes. $C$

Aplicaciones

La distancia de edición de gráficos tiene aplicaciones en el reconocimiento de escritura a mano [9] , el reconocimiento de huellas dactilares [10] y la quimioinformática [11] .

Algoritmos y complejidad

Los algoritmos exactos para calcular la distancia de edición de gráficos entre un par de gráficos generalmente transforman el problema en un problema de encontrar la ruta de transformación mínima entre dos gráficos. El cálculo de la ruta de edición óptima se reduce a la búsqueda de rutas o al problema de la ruta más corta , a menudo implementado como el algoritmo de búsqueda A* .

Además de los algoritmos exactos, se conocen muchos algoritmos de aproximación efectivos [12] [13] .

Aunque los algoritmos anteriores a veces funcionan bien en la práctica, en general el problema de calcular la distancia de edición de un gráfico es NP-completo [14] (una prueba de esto está disponible en la sección 2 en el sitio web de Zeng et al. ) e incluso difícil de aproximar (formalmente, es APX -hard [15] ).

Notas

↑ Sanfeliu, Fu, 1983 , p. 353–363.
↑ Gao, Xiao, Tao, Li, 2010 , pág. 113-129.
↑ Levenstein, 1965 , pág. 845–848.
↑ Hamming, 1950 , pág. 147–160.
↑ Shasha y Zhang 1989 , pág. 1245–1262.
↑ Zhang, 1996 , pág. 205–222.
↑ Bille, 2005 , pág. 22–34.
↑ Demaine, Mozes, Rossman, Weimann, 2010 , pág. A2.
↑ Fischer, Suen, Frinken, Riesen, Bunke, 2013 , pág. 194–203.
↑ Neuhaus, Bunke, 2005 , pág. 191–200.
↑ Birchall, Gillet, Harper, Pickett, 2006 , pág. 557–586.
↑ Neuhaus, Bunke, 2007 .
↑ Riesen, 2016 .
↑ Garey, Johnson, 1979 .
↑ Lin, 1994 , pág. 74–82.

Literatura

Alberto Sanfeliu, Rey-Sun Fu. Una medida de distancia entre gráficos relacionales atribuidos para el reconocimiento de patrones // IEEE Transactions on Systems, Man and Cybernetics . - 1983. - T. 13 , núm. 3 . — S. 353–363 . -doi : 10.1109/ TSMC.1983.6313167 .
Xinbo Gao, Bing Xiao, Dacheng Tao, Xulong Li. Una encuesta sobre la distancia de edición de gráficos // Análisis de patrones y aplicaciones. - 2010. - T. 13 . — págs. 113–129 . -doi : 10.1007 / s10044-008-0141-y .
Vladimir I. Levenshtein. Códigos binarios con corrección de supresiones, inserciones y sustituciones de símbolos // Informes de las Academias de Ciencias del CCCP. - 1965. - T. 163 , núm. 4 . — S. 845–848 .
Richard W.Hamming. Códigos de detección y corrección de errores // Boletín técnico del Bell System . - 1950. - T. 29 , núm. 2 . — S. 147–160 . -doi : 10.1002 / j.1538-7305.1950.tb00463.x . Archivado desde el original el 25 de mayo de 2006.
Shasha D., Zhang K. Algoritmos simples y rápidos para editar la distancia entre árboles y problemas relacionados // SIAM J. Comput. . - 1989. - T. 18 , N º 6 . - S. 1245-1262 . -doi : 10.1137/ 0218082 .
Zhang K. Una distancia de edición restringida entre árboles etiquetados desordenados // Algorithmica . - 1996. - T. 15 , N º 3 . — Pág. 205–222 . -doi : 10.1007/ BF01975866 .
Bille P. Una encuesta sobre la distancia de edición de árboles y problemas relacionados // Theor. computar ciencia . - 2005. - T. 337 , núm. 1–3 . — Pág. 22–34 . -doi : 10.1016/ j.tcs.2004.12.030 .
Erik D. Demaine, Shay Mozes, Benjamin Rossman, Oren Weimann. Un algoritmo de descomposición óptimo para la distancia de edición del árbol // Transacciones ACM en algoritmos . - 2010. - T. 6 , núm. 1 . - S. A2 . -doi : 10.1145/ 1644015.1644017 .
Andreas Fischer, Ching Y. Suen, Volkmar Frinken, Kaspar Riesen, Horst Bunke. Un algoritmo de coincidencia rápida para el reconocimiento de escritura a mano basado en gráficos // Representaciones basadas en gráficos en el reconocimiento de patrones. - 2013. - T. 7877. - S. 194-203. — ( Apuntes de clase en informática ). — ISBN 978-3-642-38220-8 . -doi : 10.1007 / 978-3-642-38221-5_21 .
Michel Neuhaus, Horst Bunke. Un enfoque basado en la coincidencia de gráficos para la clasificación de huellas dactilares mediante la varianza direccional // Autenticación biométrica de personas basada en audio y video. - 2005. - T. 3546. - S. 191-200. — ( Apuntes de clase en informática ). — ISBN 978-3-540-27887-0 . -doi : 10.1007/ 11527923_20 .
Kristian Birchall, Valerie J. Gillet, Gavin Harper, Stephen D. Pickett. Medidas de similitud de entrenamiento para actividades específicas: aplicación a gráficos reducidos // Journal of Chemical Information and Modeling . - 2006. - Enero ( vol. 46 , No. 2 ). — S. 557–586 . -doi : 10.1021/ ci050465e . —PMID 16562986 .
Michel Neuhaus, Horst Bunke. Cerrando la brecha entre la distancia de edición de gráficos y las máquinas kernel. - World Scientific, 2007. - V. 68. - (Máquina de Percepción e Inteligencia Artificial). — ISBN 978-9812708175 .
Kaspar Riesen. Reconocimiento de patrones estructurales con distancia de edición de gráficos: algoritmos de aproximación y aplicaciones. - Springer, 2016. - (Avances en Visión por Computador y Reconocimiento de Patrones). — ISBN 978-3319272511 .
Garey MR, Johnson DS Computadoras e intratabilidad: una guía para la teoría de la integridad NP . - WH Freeman and Company, 1979. - ISBN 978-0-7167-1045-5 .
Chih Long Lin. Dureza del problema de transformación de gráfico de aproximación // Algoritmos y Computación / Ding-Zhu Du, Xiang-Sun Zhang. - Springer Berlin Heidelberg, 1994. - T. 834. - (Lecture Notes in Computer Science). — ISBN 9783540583257 . -doi : 10.1007 / 3-540-58325-4_168 .