Theory and algorithms on the median graph
Miquel Ferrer Sumsi, Ernest Valveny Llobet, Francesc Serratosa Casanelles · 2009
Donat un conjunt d'objectes, el concepte generic de mediana esta definit com l'objecte amb la suma de distancies a tot el conjunt, mes petita. Sovint, aquest concepte es usat per a obtenir el representant del conjunt. En el reconeixement estructural de patrons, els grafs han estat usats normalment per a representar objectes complexos. En el domini dels grafs, el concepte de mediana es conegut com median graph. Potencialment, te les mateixes aplicacions que el concepte de mediana per poder ser usat com a representant d'un conjunt de grafs. Tot i la seva simple definicio i les potencials aplicacions, s'ha demostrat que el seu calcul es una tasca extremadament complexa. Tots els algorismes existents nomes han estat capacos de treballar amb conjunts petits de grafs, i per tant, la seva aplicacio ha estat limitada en molts casos a usar dades sintetiques sense significat real. Aixi, tot i el seu potencial, ha restat com un concepte eminentment teoric. L'objectiu principal d'aquesta tesi doctoral es el d'investigar a fons la teoria i l'algorismica relacionada amb el concepte de medinan graph, amb l'objectiu final d'extendre la seva aplicabilitat i lliurar tot el seu potencial al mon de les aplicacions reals. Per aixo, presentem nous resultats teorics i tambe nous algorismes per al seu calcul. Des d'un punt de vista teoric aquesta tesi fa dues aportacions fonamentals. Per una banda, s'introdueix el nou concepte d'spectral median graph. Per altra banda es mostra que certes de les propietats teoriques del median graph poden ser millorades sota determinades condicions. Mes enlla de les aportacioncs teoriques, proposem cinc noves alternatives per al seu calcul. La primera d'elles es una consequencia directa del concepte d'spectral median graph. Despres, basats en les millores de les propietats teoriques, presentem dues alternatives mes per a la seva obtencio. Finalment, s'introdueix una nova tecnica per al calcul del median basat en el mapeig de grafs en espais de vectors, i es proposen dos nous algorismes mes. L'avaluacio experimental dels metodes proposats utilitzant una base de dades semi-artificial (simbols grafics) i dues amb dades reals (mollecules i pagines web), mostra que aquests metodes son molt mes eficients que els existents. A mes, per primera vegada, hem demostrat que el median graph pot ser un bon representant d'un conjunt d'objectes utilitzant grans quantitats de dades. Hem dut a terme experiments de classificacio i clustering que validen aquesta hipotesi i permeten preveure una prospera aplicacio del median graph a un bon nombre d'algorismes d'aprenentatge.