Multiple graph matching and applications
Albert Solé Ribalta · TDX (Tesis Doctorals en Xarxa) · 2012
En aplicaciones de reconocimiento de patrones, los grafos con atributos son en gran medida apropiados. Normalmente, los vertices de los grafos representan partes locales de los objetos i las aristas relaciones entre estas partes locales. No obstante, estas ventajas vienen juntas con un severo inconveniente, la distancia entre dos grafos no puede ser calculada en un tiempo polinomico. Considerando estas caracteristicas especiales el uso de los prototipos de grafos es necesariamente omnipresente. Las aplicaciones de los prototipos de grafos son extensas, siendo las mas habituales clustering, clasificacion, reconocimiento de objetos, caracterizacion de objetos i bases de datos de grafos entre otras. A pesar de la diversidad de aplicaciones de los prototipos de grafos, el objetivo del mismo es equivalente en todas ellas, la representacion de un conjunto de grafos. Para construir un prototipo de un grafo todos los elementos del conjunto de enteramiento tienen que ser etiquetados comunmente. Este etiquetado comun consiste en identificar que nodos de que grafos representan el mismo tipo de informacion en el conjunto de entrenamiento. Una vez este etiquetaje comun esta hecho, los atributos locales pueden ser combinados i el prototipo construido. Hasta ahora los algoritmos del estado del arte para calcular este etiquetaje comun mancan de efectividad o bases teoricas. En esta tesis, describimos formalmente el problema del etiquetaje global i mostramos una taxonomia de los tipos de algoritmos existentes. Ademas, proponemos seis nuevos algoritmos para calcular soluciones aproximadas al problema del etiquetaje comun. La eficiencia de los algoritmos propuestos es evaluada en diversas bases de datos reales i sinteticas. En la mayoria de experimentos realizados los algoritmos propuestos dan mejores resultados que los existentes en el estado del arte.