Kermelized graph matching and clustering

Resumen

En esta tesis se proponen una serie de métodos para el matching y clustering de grafos que explotan el concepto de Kernel definido sobre el dominio de los grafos, Estos algoritmos son aplicados a diferentes problemas de reconocimiento, en los que los grafos son utilizados para codificar la información estructural de los patrones a reconocer. Se realizan experimentos tanto con grafos con atributos en sus nodos como con grafos en los que sólo contamos con información puramente estructural. En primer lugar, se analizan diferentes tipos de kernels definidos sobre el dominio de los grafos para extraer a partir de ellos atributos que sirvan como medida de similitud entre los nodos de los grafos, y se introducen estos atributos en una función de corte para el matching de grafos. Se evalúa la capacidad de diferentes tipos de atributos para distinguir entre emparejamientos correctos e incorrectos. A continuación, se introducen estos atributos en la función de coste de Gold y Rangarajan dentro del algoritmo Softassign y se evalúa su rendimiento dentro de este algoritmo de matching de grafos. En segundo lugar, se proponen dos métodos para obtener un prototipo representativo de un conjunto de grafos. Estos métodos son la fusión incremental y la fusión kernelizada. EL primero de ellos es un método eficiente que tiene la desventaja de que el resultado obtenido depende del orden en el que se presentan los grafos de entrada. El segundo es un método global que se basa en la obtención de todos los emparejamientos entre cada par de grafos de entrada, y consecuentemente tiene un coste temporal mayor que el anterior. Este segundo método se apoya en la información proporcionada por los kernels para seleccionar los emparejamientos que serán tenidos en cuenta para la construcción del prototipo. En cada nodo y arista de este grafo prototipo se registran sus frecuencias de aparición, de forma que tendremos un modelo generativo de primer orden. En tercer lugar, se integra de forma eficiente la construcción de prototipos dentro de un algoritmo de clustering central que nos permitirá obtener la estructura de clases de un conjunto de grafos y los prototipos que representan a cada clase. Concretamente, se integra el método de fusión kernelizada dentro de un algoritmo de clustering EM, obteniendo de esta forma un algoritmo de clustering de grafos central con el coste de un algoritmo pairwise. Por último, los métodos propuestos se aplican a problemas reales. Se aplican los métodos de matching y clustering de grafos a problemas de comparación de superficies de proteínas y de localización visual mediante características SIFT.