Màster en Enginyeria Informàtica i de la Seguretat
Màster interuniversitari en Intel·ligència Artificial
Presentació de Treball de Recerca/Tesi de Màster
Noms i cognoms dels alumnes:
Director del Treball de Re
Co-directors: Albert Solé Ribalta
Data de presentació: 15/01/2009
Títol del Treball de Recerca/Tesi de Màster:
Graphs
Marcar les caselles corresponents a l’
MEIS, Itinerari Seguretat
MEIS, Itinerari Sistemes Intel·ligents
MIA
MEIS, Pla d’estudis 2006 (Treball de Recerca, 10.5 crèdits)
MEIS, Pla d’estudis 2007 (Treball de Recerca, 30 crèdits)
MIA, Pla d’estudis 2006 (Tesi de Màster, 3
Qualificació:
President
____________
Màster en Enginyeria Informàtica i de la Seguretat
(MEIS)
Màster interuniversitari en Intel·ligència Artificial
(MIA)
Presentació de Treball de Recerca/Tesi de Màster
Noms i cognoms dels alumnes: Enric Vidiella Mars
Director del Treball de Recerca: Dr. Francesc Serratosa
Ribalta
15/01/2009
Títol del Treball de Recerca/Tesi de Màster: Graph Indexing based on
Marcar les caselles corresponents a l’itinerari i el pla d’estudis:
MEIS, Itinerari Seguretat
MEIS, Itinerari Sistemes Intel·ligents
MEIS, Pla d’estudis 2006 (Treball de Recerca, 10.5 crèdits)
MEIS, Pla d’estudis 2007 (Treball de Recerca, 30 crèdits)
MIA, Pla d’estudis 2006 (Tesi de Màster, 30 crèdits)
Secretari
Vocal
_____________ _____
Màster en Enginyeria Informàtica i de la Seguretat
Màster interuniversitari en Intel·ligència Artificial
Presentació de Treball de Recerca/Tesi de Màster
Graph Indexing based on Median
Vocal
_____________
2
ÍNDEX
Agraïments ................................................................................................... 4
1. Descripció del problema a resoldre, objectius del treball de recerca .................. 5
1.1 Objectius: ............................................................................................ 6
2. Estat actual de la tecnologia sobre el problema atacat .................................... 7
2.1- Indexació d’Imatges per contingut ......................................................... 8
2.2- Recuperació de similituds ..................................................................... 9
2.3- Matching, similitud, classificació ........................................................... 10
2.4- Aplicacions de la recuperació d’imatges ................................................. 10
2.5- Estudis actuals ................................................................................... 11
2.6- Conclusions ........................................................................................ 12
2.7- Frameworks dins de la temàtica de recuperació d’imatges usant grafs ....... 13
2.7.1- Definicions ................................................................................... 13
2.7.1.1- Framework ............................................................................ 13
2.7.1.2- Representació basada en grafs ................................................. 13
2.7.1.3- Attributed Graphs (AG’s) ......................................................... 14
2.7.1.4- Random Graphs ( Grafs Aleatoris ) .......................................... 15
2.7.1.5- Outcome Graphs (Grafs Resultants) .......................................... 15
2.7.1.6- Function-Described Graphs (FDGs) ........................................... 16
2.7.1.7- First-Order Random Graphs (FORGs) ........................................ 16
2.7.1.8 Second Order Random Graphs (SORGs) ..................................... 17
2.7.1.9- Median Graphs ....................................................................... 18
2.7.2- Frameworks trobats en la bibliografia .............................................. 19
3. Disseny de la nova solució, justificació de la nova proposta ............................ 27
3.1- Mètrica: graph edit distance ................................................................. 27
3.2- L’estructura: m-tree ............................................................................ 29
3.3- Clustering: dendrograma ..................................................................... 32
3.4- Representant smallest SOD (sum of distances) ....................................... 33
3.5- Prototips: median graph ...................................................................... 34
3
3.6- Cerca ................................................................................................ 37
3.7- Anàlisi de l’arbre: el factor solapament .................................................. 38
4. Aspectes de desenvolupament i implementació .......................................... 40
4.1- Mètrica: graph edit distance ................................................................. 40
4.2- L’estructura ....................................................................................... 43
4.3- Clustering: dendrograma ..................................................................... 46
4.4- Representant smallest SOD (sum of distances) ....................................... 50
4.5- Prototips: Median Graph ...................................................................... 50
4.6- Cerca ................................................................................................ 52
5. Avaluació del sistema desenvolupat, comparació amb altres alternatives ......... 59
5.1- La base de dades. ............................................................................... 60
5.2- Anàlisi de l’arbre: el factor solapament .................................................. 61
5.2 Anàlisi de la cerca: nombre d’accessos ................................................... 63
5.3. Incidència de µMax ............................................................................... 66
5.3.1-Mumax = (dMax(matriu_distancies_tots_amb_tots))/2 .......................... 67
5.3.2- Mumax = (dMax(matriu_distancies_tots_amb_tots))/4 ......................... 68
5.3.3- Mumax = (dMax(matriu_distancies_tots_amb_tots))/8 ......................... 69
5.4- Altres factors amb influència sobre els testos ......................................... 70
6. Conclusions, treball futur ........................................................................... 74
7. Referències .............................................................................................. 75
8. Annex 1 ................................................................................................... 77
9. Annex 2: publicacions ............................................................................... 84
4
Agraïments
Sembla bastant difícil agrair com es mereix, en un petit bocí de paper, a totes les
persones que han estat al meu costat durant aquest temps. De totes maneres, ho
intentaré fer des del més gran dels aprecis.
Abans que ningú vull destacar la meva família. L’any 2009 ha posat una paraula de
moda: persistir. Però jo, gràcies a els de casa, fa molts d’anys que tinc coneixença
d’aquest valor. D’aquest i de la resta de valors, entre milions d’altres coses, que
s’han encarregat de transmetre’m i ensenyar-me des de ben petit per fer-me ser
qui sóc. Sempre han confiat en mi, m’han recolzat i m’han animat. De debò, sou
una familia genial i m’encanta tenir-vos al meu costat.
També voldria agrair al Francesc Serratosa i a l’Albert Solé, no només les hores de
dedicació a aquest treball de recerca: les reunions setmanals (a vegades més sovint
i tot), la resposta a les meves preguntes, l’ajuda donada en qualsevol moment,
etc.; sinó que també voldria agrair el com m’han tractat i recolzat, i la gran
quantitat de coses que he après al seu costat, no només d’informàtica o de recerca,
de tot en general.
No em voldria oblidar als companys de laboratori. Aquestes converses sobre temes
del projecte, d’informàtica en general, o que no tenien res a veure amb la feina,
però que ajudaven a treure un somriure i a tornar amb energies a la feina.
A tots els que han influït en la meva vida, tant positiva com negativament, ja que
gràcies a tots i cadascun d’ells sóc el que sóc ara mateix i estic on estic.
Per acabar, gràcies Pamela simplement per ser genial i per ajudar-me a treure
energies d’allà on no n’hi ha, i a ser feliç en cada instant de la vida.
Gràcies a tots, gràcies de tot cor!
1. Descripció del problema a resoldre, objectius del treball de recerca
5
1. Descripció del problema a resoldre, objectius del
treball de recerca
Indexar un espai mètric significa tenir un manteniment eficient de respostes a
cerques per similitud. Per exemple, cerques amb el propòsit de retornar objectes de
la base de dades que siguin similars a un objecte referència. I on la (dis)similitud
entre objectes es mesura amb una funció de distància mètrica específica d.
Les estructures indexades són eines fonamentals en la utilització de les bases de
dades, ja que s’usen per obtenir un accés eficient en la recuperació d’imatges en
grans recopilacions d’imatges. Tradicionalment els sistemes de bases de dades
manegaven les propietats globals de les imatges, com els histogrames i moltes
altres tècniques que han estat definides per al tractament de conjunts de dades
com per exemple la indexació unidimensional. Com que una comanda de funció
total en un determinat domini sempre existeix, aquesta comanda pot ser utilitzada
per la partició de dades, i aquesta propietat per a partir les dades pot ser explotada
per donar suport a les consultes eficients.
Tanmateix, pocs fan ús d’enfocaments de les relacions entre les entitats de la
imatge [1]. En aquests casos, les imatges són representades per “Attributed
Graphs” (AGs), i la distància entre aquets AGs es utilitzada per dividir les dades [2]
i fer més eficient la recuperació de les imatges.
En aquest treball, volem aplicar els Median Graphs [5] i [6] com la principal
estructura per representar la propietat de partició de dades en lloc d’utilitzar AGs
com s’ha fet en [2]. Com que els Median Graphs tenen més capacitat de
representar a un grup d’AGs, en lloc d’un prototips representat per un sol AG,
volem estudiar si aquest augment del coneixement del grup fa la recuperació
d’imatges més ràpida i més precisa.
1. Descripció del problema a resoldre, objectius del treball de recerca
6
1.1 Objectius:
⇒ Informe sobre l’estat actual de la tecnologia de recuperació d’imatges
⇒ Informe general dels frameworks trobats dins de la temàtica de recuperació
d’imatges usant AGs (Attribute Graphs)
⇒ Definir un nou framework per a la recuperació de grafs.
⇒ Implementar un sistema per a la recuperació de grafs usant Median Graphs
⇒ Testejar el nou sistema usant alguns grafs pertanyents a una base de dades
⇒ Comparar el nou model amb algun clàssic com per exemple “nearest-
neighbours”
2. Descripció del problema a resoldre, objectius del treball de recerca
7
2. Estat actual de la tecnologia sobre el problema
atacat
Tant la recuperació d’imatges com la de vídeo, continuen sent unes de les àrees
d’investigació que han anat creixent ràpidament en els últims anys dins el camp de
la tecnologia multimèdia. Però la pregunta que volem respondre és: que pretenem
obtenir a partir de la recuperació d’imatges o de vídeo? Com tots sabem des de fa
pocs anys, l’era digital s’ha imposat dins les nostres vides, i ara els preus dels
dispositius digitals són més assequibles. Això fa possible que sigui una tecnologia a
l’abast de casi tothom. El creixement d’aquesta tecnologia és constant, com per
exemple, l’augment de la capacitat de disc, entre d’altres. Això fa que tinguem
molta informació emmagatzemada en cintes, CD-ROMs, DVDs, o grans dispositius
d’emmagatzematge. Necessitem tècniques d’organització d’imatges i vídeo en
proporció a les quantitats d’informació que disposem. Aquest fet fa que necessitem
alguna mena de mecanisme de compressió d’imatges i vídeo. Avui en dia l’anàlisi i
recuperació d’imatges estàtiques és un problema bastant difícil de resoldre, ja que
requereix un treball sacrificat, que necessita el modelatge, l’adquisició de molts de
coneixements, i l’anàlisi dels continguts de la imatge.
El vídeo a diferència de la imatge es pot definir com a un problema simple per
accedir a les imatges estàtiques, ja que es presenta com una seqüència d’imatges
que reprodueix la vida real, fet que fa que la segmentació de vídeo sigui més
simple que la d’una imatge estàtica. Tot i això, afegeix diversos ordres de
complexitat a l’hora de la recuperació a causa de la indexació i l’anàlisi. Per
exemple l’usuari pot plantejar una consulta basada en la petició de trobar una
escena de vídeo semblant a aquesta. Respondre a aquesta petició requereix
representacions de la imatge i aspectes temporals de l’escena de vídeo. A més,
l’augment de nivell de representacions, que reflecteixen l’estructura constituent de
vídeo o informació semàntica temporal, també podria ajudar en la correcta
recuperació de la escena de vídeo. Aquests, inclouen la semàntica per a la
recuperació d’imatges de vídeo, recuperació de paradigmes interactius, interacció
afectiva i emocional, recuperació d’imatges i vídeos basats en la percepció humana,
l’aprenentatge d’estratègies, i els resums d’informació intel�ligents.
El contingut digital ha esdevingut un objectiu vital per a les empreses i la gestió
d’aquest contingut ha emergit com una necessitat estratègica. Una gran quantitat
2. Descripció del problema a resoldre, objectius del treball de recerca
8
de fotos i vídeos són generats, publicats, transmesos i accedits cada dia per
empreses i per públic en general. Mentre que la paraula clau indexació de dades
visuals és útil, també és tediosa i normalment es queda curta per a descriure el
contingut de la imatge. Una foto és una senyal en ella mateixa; traduint això a text,
és necessària una operació “lossy”. Aquest tipus d’operacions utilitzen un mètode
en el qual s’elimina informació en el procés de compressió, disminuint així
substancialment la mida de la foto, i sense perdre molta qualitat.
“Content-based indexing of visual data” és una tecnologia clau per a referir-se a
aquest problema. De forma interessant, pot ser un bon complement per a la
paraula clau indexació.
2.1- Indexació d’Imatges per contingut
El prerequisit per aquest tipus de tecnologia és l’existència d’una base de dades de
dades visuals (per exemple imatges). La base de dades ha de ser dinàmica, per
exemple, s’han de poder inserir noves imatges.
Enlloc de descriure el contingut visual d’una imatge per contingut, es calcula una
ditada visual (o signatura). Aquesta signatura ha de ser una codificació optima dels
característiques visuals clau, representant informació general de baix nivell sobre la
imatge: colors, formes, textures, patrons etc [1].
Figura 1: extracció de característiques i codificació
Les signatures d’imatges es calculen per totes les imatges de la base de dades
(totes les imatges inserides). Posteriorment, en el procés de consulta d’imatges,
s’han d’actualitzar aquestes signatures per a realitzar la recuperació d’imatges.
Colors Formes Textures
2. Descripció del problema a resoldre, objectius del treball de recerca
9
2.2- Recuperació de similituds
La recuperació d’imatges des del punt de vista de l‘usuari es pot realitzar de
diverses formes:
• Cerca d’un objectiu. Buscar una imatge específica a la base de dades
(per exemple la ditada d’una persona).
• Cerca de categoria. L’usuari està interessat en recuperar imatges de la
mateixa categoria (o semàntica) (per exemple ditades del tipus “whorl”).
• Cerca oberta (Open-ended browsing). L’usuari no està buscant cap
imatge o sèrie d’imatges sinó que busca “idees”.
A partir de l’observació comentada anteriorment dels objectius de l’usuari, és
evident que la similitud d’imatges serà una tecnologia clau. La majoria dels
sistemes de recuperació per contingut es centren en l’enfocament “query-by
example” (consulta per exemple). Aquest enfocament consisteix en mostrar alguna
cosa que agradi a l‘usuari, i aleshores, el sistema en troba més com aquesta.
Des d’un punt de vista algorítmic, la similitud d’imatges es deriva de la comparació
de signatures (imatges similars han de tenir signatures similars). Les imatges més
semblants són normalment les “nearest neighbors” (veïns més propers) en l’espai
de característiques.
Des del punt de vista de l’usuari, s’espera prémer en una imatge (o pujar-ne una
de nova) i recuperar les imatges més similars a la seva consulta.
Des d’un punt de vista funcional, el problema és que, per a començar, l’usuari
necessita trobar una imatge similar al resultat esperat. Quan les paraules claus
estan disponibles, el problema pot ser solucionat, com una aproximació, amb
l’enfocament “seleccionar per text, classificar per imatge”, encara que es poden
aconseguir millors resultats mitjançant el més sofisticat esquema de recuperació en
mode creuat.
Per tal d’usar el sistema com una eina potent, l’usuari necessita:
• Ser conscient de l’objectiu (cerca d’objectiu, cerca de categoria o cerca
oberta).
• Ser conscient de què s’està intentant maximitzar: precisió o memòria.
2. Descripció del problema a resoldre, objectius del treball de recerca
10
Suggerir paraules clau:
Trobar imatge similar
Whorl
...
• Usar la flexibilitat i la intuïció del sistema per refinar la consulta inicial per
a trobar l’objectiu.
2.3- Matching, similitud, classificació
La tecnologia explicada anteriorment de recuperació per similitud és només un
aspecte de l’anàlisi de contingut d’imatges. Desprès de la indexació d’imatge, es
poden aplicar un total de tres tecnologies per a la signatura digital:
1. Matching – per exemple trobar la mateixa imatge (fins i tot amb la seva
geometria o fotometria lleugerament alterada).
2. Similitud – per exemple trobar sèries d’imatges similars (com s’ha descrit el
punt 2.2).
3. Classificació – per exemple suggerint paraules clau basades en paraules clau
d’imatges similars (raonament basat en cas) o basat en classes predefinides
(classificació)
Figura 2: Basada en la signatura digital de la imatge consultada, el sistema pot trobar la
mateixa imatge o similar a la base de dades, o suggerir paraules clau per a la consulta.
2.4- Aplicacions de la recuperació d’imatges
Des de 1999, s’han aplicat satisfactòriament les tecnologies anteriors als següents
sectors de mercat:
• Seguretat – per exemple comparació d’imatges per a la seguretat
corporativa, biometria i multitud d’investigacions per enfortir-les.
2. Descripció del problema a resoldre, objectius del treball de recerca
11
• Propietat Intel�lectual – per exemple recuperació d’informació de dades,
patents i marques comercials (per exemple dibuixos tècnics, logos,
fotos).
• Protecció de marques – per exemple seguiment de la propietat de dades
visuals a Internet.
� Arxius Multimèdia– per exemple cerca, recuperació i gestió
d’actius visuals (i meta dades associades).
� Representació d’imatges científiques– per exemple recuperar i
classificar imatges en respecte a un contingut visual científic
(utilitzat en ciències de la vida, salut, biotecnologia, etc.).
2.5- Estudis actuals
Diversos documents fan referència als problemes semàntics i donen informació
valuosa sobre l’estat actual de la tècnica de recuperació d’imatges i vídeo. A
continuació es mostra un llistat dels diferents temes investigats i estudiats
referents a aquest camp.
En un dels estudis es resumeixen els principals temes de recerca en mètodes
automàtics per a la descripció d’alt nivell i anotació. Un altre presenta un estudi
complet de la recuperació d’informació visual, l’objectiu del qual es proporcionar
una millor informació sobre la naturalesa semàntica necessitada i sobre la
representació i recuperació del contingut semàntic a traves de l’ampli espectre de
l’activitat de recuperació d’imatges.
En un altre s’argumenta que la comprensió semàntica de continguts multimèdia
requereix models de conceptes semàntics, context i una estructura. Per aquest
motiu, presenten un framework que pot combinar models generatius per a
estructures i contextos. Un altre framework per a la comprensió de vídeo usant
context i ontologies multimèdia. Aquest és un sistema expert que utilitza un motor
basat en regles, en domini del coneixement, detectors visuals, i meta dades. Un
altre autor proposa la detecció de conceptes semàntics de vídeo utilitzant gradients
temporals i classificació d’àudio. Un altre analitza diferents formes d’acoblament de
la informació per mitja de les característiques múltiples visuals en la representació
de continguts visuals temporals usant models basats en cadenes de Markov. De la
mateixa manera es presenta un algorisme per a la recuperació de vídeo que fusiona
2. Descripció del problema a resoldre, objectius del treball de recerca
12
les decisions d’agents de recuperació múltiple tant en modalitat text com en
imatge.
També existeix una avaluació de les tècniques de reconeixement d’expressió facial.
Aquestes tècniques es centren en el disseny dels classificadors utilitzats per al
reconeixement d’emocions: estàtic i dinàmic. La recuperació de vídeo de les
interaccions humanes mitjançant en el “model-based motion tracking”. També
tenim un estudi “eyetracking” sobre com la gent veu el vídeo digital. Hi ha autors
que discuteixen els possibles problemes relacionats amb la indexació de vídeos
personals capturats per un sistema d’imatges. Un repte important en la recuperació
de la informació visual prové de la interpretació dinàmica de les imatges en
diferents circumstàncies. En altres paraules, la semblança de percepció depèn sobre
l’aplicació, la persona, i el context on és usat. Molts documents estan adreçats a
l’aprenentatge i donen molta rellevància al tema de recuperació d’imatge i vídeo.
Diversos algoritmes d’aprenentatge que utilitzen representacions d’imatges globals,
són usats per a la recuperació d’imatges basada en regions de manera eficient. Es
pot usar un enfocament diferent per a millorar la recuperació d’imatges i la
classificació d’aquestes. A més a més, s’han presentat noves tècniques referents a
problemes de recuperació, incloent el seguiment d’objectes, recuperació basada en
formes, cerca d’imatges a gran escala dins d’una base de dades, arbres k-d per a
indexació de dades, trademarks, i recuperació d’imatges per web.
2.6- Conclusions
La recuperació d’imatges basada en contingut és una tecnologia trencadora que
avui en dia és madura i que ajuda a les empreses i organitzacions a recuperar i
gestionar dades visuals de manera més eficient.
L’aspecte més important d’aquesta tecnologia és la seva versatilitat: no només pot
complementar idealment la paraula clau indexació, sinó que també pot canviar-la si
no es pot utilitzar, per exemple en aplicacions en temps real. També és una
tecnologia que ha de ser ben refinada per a aplicacions específiques.
2. Descripció del problema a resoldre, objectius del treball de recerca
13
2.7- Frameworks dins de la temàtica de recuperació d’imatges usant grafs
2.7.1- Definicions
En aquest punt es definiran diferents conceptes que ajudaran a la comprensió de
les posteriors explicacions.
2.7.1.1- Framework
Framework és una estructura conceptual bàsica utilitzada per resoldre problemes
complexos. És un terme adoptat de l'anglès i equival a entorn de treball o, també,
marc de treball. Aquest mot forma part de la terminologia tècnica utilitzada en
múltiples àmbits de l'enginyeria i de l'informàtica.
2.7.1.2- Representació basada en grafs
Una representació basada en grafs és molt més fàcil d’entendre i suficientment
flexible per a crear diferents representacions del mateix domini. El domini (per
exemple dades i relacions) es descriu utilitzant grafs. Aquests grafs esdevenen una
aportació important en les eines que utilitzen heurístiques per a escollir subgrafs
considerats importants (patterns).
Un graf es defineix com un parell G(V,A):
• V= {v1,..., vn} són un conjunt d’elements anomenats vèrtexs.
• A és el conjunt d’arestes a que satisfan E �[V]2. Aleshores, cada aresta a � E
és parell (vi,vj). Si (vi,vj) és un parell ordenat per cada (vi,vj) � E aleshores
G=(V,E) és diu que és un graf dirigit. Un graf etiquetat té etiquetes
associades a les seves arestes i vèrtexs.
Es pot representar una gran varietat d’objectes en forma de grafs, mitjançant unt
algorisme de transformació de dades a format graf, com es mostra en la següent
figura:
2. Descripció del problema a resoldre, objectius del treball de recerca
14
Figura 3: representació de diferents objectes en forma de grafs.
2.7.1.3- Attributed Graphs (AG’s)
Abans de tot, hem de tenir clar què és un graf. Un graf consisteix en un conjunt de
vèrtexs que representen primitives i un conjunt d’arestes que representen relacions
entre les primitives. Però nosaltres necessitem tenir més informació a cada vèrtex, i
per solucionar aquest problema utilitzem els Grafs amb Atributs, en els quals
podem incorporar més informació semàntica sobre ells. Els Grafs amb Atributs han
estat utilitzats per fer aplicacions tals com reconeixement de caràcters, anàlisi
esquemàtic de dibuixos, anàlisi de formes 2-dimensionals, anàlisi d’escenes
dinàmiques, anàlisi d’imatges dins del camp de la medicina... Normalment, els grafs
són usats per representar models coneguts d’una base de dades i mostres
d’entrada desconegudes, i la tasca d’aquest reconeixement gira en front al
problema de “graph-matching”.
Xarxes Físiques Xarxes Lògiques Ditades
Lletres Imatges
Estructures Químiques
Símbols Gràfics
Formes
2. Descripció del problema a resoldre, objectius del treball de recerca
15
2.7.1.4- Random Graphs ( Grafs Aleatoris )
En la aproximació dels Random Graphs, els AGs s’amplien de varies formes per tal
d’incloure informació probabilística o fuzzy. Wong va definir els RGs per a modelar
classes de patrons descrits per AGs a través d’un espai de probabilitat conjunta de
variables aleatòries, però degut a la dificultat computacional de treballar amb els
grafs aleatoris, es van proposar els First Order Random Graphs (FORGs) per a
aplicacions reals (és interessant notar que encara que els Random Graphs formen
ara part de la terminologia estàndard en reconeixement de patrons,
desafortunadament en teoria de grafs precisament aquest nom es refereix a un
concepte completament diferent i ben arrelat introduït per Erdos).
2.7.1.5- Outcome Graphs (Grafs Resultants)
Un graf resultant és qualsevol graf amb atributs obtingut per mitjà de la
instanciació de tots els vèrtexs aleatoris i totes les arestes aleatòries d’un graf
aleatori (RG) en el camí que satisfaci totes les relacions estructurals. D’aquesta
manera, un Graf Aleatori representa el conjunt de tots els possibles Grafs amb
Atributs que poden resultar Grafs Resultants d’aquest, d’acord amb una distribució
de probabilitat associada.
Definició:
Per a cada graf resultant G d’un RG R, la probabilitat conjunta dels vèrtexs i arestes
aleatoris es definida per la instanciació que produeix G. Suposem que G s’orienta
respecte R per un isomorfisme estructural µ; per cada vèrtex ω� a R, suposem que a� � γ�µ� �ω��� és el corresponent valor de l’atribut dins de G’, i similarment, per a
cada aresta ε�� en R (associada a la variable aleatòria β�) agafem b� � γ��µ� �ε���� corresponent al valor de l’atribut en G’. Llavors la probabilitat de G d’acord amb
l’orientació de µ, definit per P(G| µ) es defineix com:
���|�� � �� ����� � ���^ ��!� � "#�$#%
&�% ' � (�� , … , �& , " , … , "$�
2. Descripció del problema a resoldre, objectius del treball de recerca
16
2.7.1.6- Function-Described Graphs (FDGs)
Un FDG és una estructura que conté informació per mantenir les característiques
locals dels AGs que pertanyen a una classe, així com permetre el rebuig dels AGs
que no pertanyen a aquesta classe. En general, un FDG pot ser derivat com una
síntesis d’un conjunt individual d’AGs. Per tal d’aconseguir una representació
compacta d’un conjunt d’AGs per mitjà d’un prototip, es desitjable tenir una
descripció probabilística del conjunt per tenir en compte les variacions dels patrons
estructurals en el conjunt de referències. FDG son definits com una aproximació del
conjunt probabilístic dels elements aleatoris.
Conseqüentment tenim dos mètodes per resoldre-ho. Depèn de:
• Suposició d’independència
• Relacions de segon ordre
El primer d’aquests dos, ens diu que els atributs als nodes són independents dels
altres nodes i també de les arestes, i són considerades algunes suposicions
d’independència. I el segon mètode, ens diu que algunes funcions de segon ordre
són incloses per permetre una generalització limitada.
Figura 4: Function-Described Graph
2.7.1.7- First-Order Random Graphs (FORGs)
Degut a la dificultat computacional dels grafs generals aleatoris, causada per la
dificultat a l’hora d’estimar i manipular la distribució de probabilitat dels conjunts
d’alt-ordre, es van proposar els FORGs per a aplicacions reals. Es van introduir tres
suposicions sobre la independència probabilística entre els vèrtexs i les arestes:
2. Descripció del problema a resoldre, objectius del treball de recerca
17
• Els vèrtexs aleatoris són mútuament independents.
• Les arestes aleatòries són independents donant valors per als vèrtexs
aleatoris.
• Les arestes són independents dels vèrtexs, exceptuant els vèrtexs que estan
connectats.
Definició
Per un FORG R podem dir que és un RG (Random Graph) que satisfà la les
proposicions del graf resultant i dels FDGs. Basant-nos amb aquestes proposicions,
per a un FORG R, la probabilitat de P(G| µ) es converteix en:
��+|�� � , (�&
�% ���� , -#$
#% �"#|�# , �#.�
On pi (a) = Pr(��� � ��, 1 ≤ i≤n, són funcions de probabilitat de densitat marginal
per als vèrtexs i qj /"|�# � �#.0=Pr/!# � "|�# � �#. � �#.0,1 ≤j≤m, són les funcions de
probabilitat condicionals per a les arestes, en les quals �# , �#. es refereixen als
vèrtexs aleatoris per als punts finals dels arcs aleatoris !#.
2.7.1.8 Second Order Random Graphs (SORGs)
Els SORGs els podem definir com una formula general per a l’estimació de la
probabilitat conjunta dels elements aleatoris dins d’un RG sintetitzat des d’un
conjunt d’AGs. Els SORGs volen millorar la representació dels FORGs i dels FDGs.
La probabilitat conjunta d’una instanciació d’elements aleatoris en el RG es pot
descriure com una aproximació a:
���|�� � (�1 , … , 12� 3 , (�2
�% �1�� , , ��#�1� , 1#�2#%�4
2� �%
On pi(di) són les probabilitats marginals dels elements aleatoris 5� (vèrtexs o
arestes) i rij son els coeficients de compatibilitat de Peleg que hem de tenir en
compte ambdues, la marginal i la probabilitat conjunta de segon ordre.
��#/1� , 1#0 � Pr �5� � 1�^5# � 1#�(��1��(#�1#�
2. Descripció del problema a resoldre, objectius del treball de recerca
18
El coeficient de Peleg, amb un rang que no és negatiu, esta relacionat amb el
“grau” de dependència entre dues variables aleatòries. Si aquestes dues variables
són independents, la probabilitat conjunta és definida com el producte del primer
marginal, d’aquesta manera rij =1 (o un valor pròxim a 1 si les funcions de
probabilitat són estimades). Si una d’aquestes probabilitats marginals és nul�la, la
probabilitat conjunta és també nul�la. En aquest cas, la indeterminació 0/0 és
solucionada com a 1, sense que això afecti a la probabilitat conjunta global, que es
nul�la.
2.7.1.9- Median Graphs
Donat un conjunt de grafs, el median graf ha de ser definit com el graf que te la
mínima suma de distàncies (SOD, Sum Of Distances) a tots els grafs del conjunt.
Aquesta simple definició amaga el poderós concepte de descriure un prototips d’un
conjunt de grafs. La única restricció imposada per aquesta definició és que s’ha de
definir la mesura per comparar grafs. De fet, la definició de median graf té una
definició equivalent en el concepte de median vector, o en un cas més general, en
el concepte de median d’un conjunt d’objectes, que es coneix com una de les
maneres més importants d’obtenir un prototips del conjunt. Aquesta simple però
poderosa definició fa que el concepte de median graf sigui molt atractiu.
A més, els median grafs tenen un gran nombre d’aplicacions. Per exemple, poden
ser utilitzats en clústering de grafs (com és el nostre cas) per a representar el
centre del clúster. També són d’interès en el context d’aprenentatge d’objectes
prototips. En aquest cas l’objectiu és deduir un model representatiu d’una col�lecció
de mostres amb soroll del mateix objecte. Finalment, els prototips obtinguts amb el
median graf es fan servir en tasques de classificació (molt important en aquest
article ja que són els que formen els routing nodes de l’arbre representant als
nodes fulla). Fins i tot en un esquema més general, els median grafs poden ser
potencialment usats en qualsevol aplicació en la que es necessiti un prototips que
representi al conjunt.
2.7.1.7.1- Per a que son usats els SORGs.
Els SORGs han estat creats des de fa pocs anys. Actualment els investigadors
encara estan investigant com explotar el potencial d’aquests i com millorar les
seves representacions. Fins avui, tenim diversos articles que tracten aquest tema:
2. Descripció del problema a resoldre, objectius del treball de recerca
19
• “SORG for modeling sets of attributed graphs and their application to
object learning recognition”: la principal característica d’aquest article és
ensenyar-nos la representació dels grafs aleatoris, que estan basats en
relacions de 2n ordre entre els elements del graf, per aconseguir un
conjunt de models de “Attributed graphs” (AGs).
• “Distance Measures between Attributed Graphs and Second-Order
Random Graphs”: el principal punt d’aquest article és proposar el
mesurament de distàncies entre els “Attributed Graphs”(AGs) i els
Second-Order Random Graphs (SORGs) per a la seva classificació
posterior i el seu reconeixement.
Tot i això en l’actualitat encara hi ha projectes d’investigació en procés:
• “Reasoning about the representative of a set of ndimensional elements”:
en aquest treball alguns elements són representats com a SORGs i
l’objectiu que té és la definició d’algunes distàncies, i la definició
d’algoritmes per a crear la representació i per calcular la distància entre
un element i la seva representació
• “Graph indexing based on SORGs”: en aquest treball, el principal punt a
tractar és l’aplicació dels SORGs com a una estructura principal per
representar la propietat de dividir les dades en comptes d’utilitzar els
AGs. Com que els SORGs tenen més capacitat per representar grups
d’AGs, en aquest article són estudiats si aquest augment de coneixement
dels clústers fa que la recuperació d’imatges sigui més ràpida i més
exacta.
2.7.2- Frameworks trobats en la bibliografia
Per la realització d’aquest punt, hem cercat informació en la documentació que
forma l’apartat de referències.
En l’article “SECOND-ORDER RANDOM GRAPHS FOR MODELING SETS OF
ATTRIBUTED GRAPHS AND THEIR APPLICATION TO OBJECT LEARNING AND
RECOGNITION” d’Alberto Sanfeliu, Francesc Serratosa i René Alquézar es parla dels
SORGs (Second Order Random Graphs), un dels frameworks utilitzats per a la
recuperació d’imatges usant Grafs amb Atributs.
2. Descripció del problema a resoldre, objectius del treball de recerca
20
Els SORGs són un tipus de representació de grafs aleatoris (Random Graphs)
basada en relacions de segon ordre entre els elements del graf. Aquestes són
usades per a un conjunt de models dels AGs. La principal característica dels SORGs
és que aquests contenen dues funcions de probabilitat:
• Funcions de probabilitat marginal dels elements del graf
• Funcions de probabilitat de conjunts de segon ordre
Els SORGs han sigut creats per aconseguir resoldre problemes de dades i
representacions de prototips dels AGs, ja que aquests últims presenten molta
complexitat computacional a l’hora de compara dos AGs.
Per entendre bé com funcionen els SORGs s’han d’entendre els conceptes explicats
en l’apartat 2.7.1 (Definicions): FORGs (First Order Random Graphs) i FDGs
(Function Describe Graphs), ja que els SORGs els podem definir com una
generalització d’aquests dos últims, i a més alguns conceptes generals com els
grafs amb atributs, grafs aleatoris, i grafs resultants (outcome graphs).
En l’article “Efficient Matching and Indexing of Graph Models in Content-Based
Retrieval” de Stefano Berretti, Alberto Del Bimbo, and Enrico Vicario es tracten
bàsicament els ARG’s (Attributed Random Graphs).
En la recuperació d’imatges de bases de dades, l’avaluació de similituds, basada en
l’aparença d’entitats espaials i en les seves relacions mútues, depèn de la
representació del contingut basat en ARGs. Aquesta classe de modelatge comporta
una indexació i “matching” complicat, la qual cosa impedeix que s’utilitzi
actualment dintre d’aplicacions integrals. Al llarg de l’article s’exposa una
formulació teòrica i gràfica per al problema de la recuperació d’imatges basat en la
similitud conjunta d’entitats individuals i les seves relacions mútues.
En concret, es mostra l’ús de la tècnica “metric indexing” per tal d’organitzar arxius
grans de models de grafs, i es proposa un mètode innovador, que representa una
solució eficient per a corregir el problema de l’error d’isomorfisme de (sub)grafs
que es necessita per calcular distàncies entre objectes. La comparació analítica i els
resultats experimentals mostren que millora l’estat actual de la tecnologia en
mètodes de cerques estat-espai i que l’ús combinat del “matching” i l’esquema
2. Descripció del problema a resoldre, objectius del treball de recerca
21
d’indexació proposat, permeten que es manegui la complexitat de les aplicacions de
recuperació per plans espaial.
L’accés efectiu a les bases de dades d’imatges requereix que els índexs
convencionals es complementin amb consultes que apuntin a l’aparença esperada
de la imatge que es cerca. Per això s’ha estudiat una gran quantitat de tècniques
que comparen característiques visuals, com per exemple el color o la textura.
Aquestes tècniques afecten a la imatge en general o a algun conjunt de píxels que
forma una entitat espaial amb algun tipus de cohesió visual. Quan s’han definit
múltiples entitats, el model també ha de capturar informació sobre les seves
relacions. Aquest pas pot millorar la efectivitat de la recuperació mitjançant el
registre de diferències i similituds que depèn de la disposició de les entitats enlloc
de dependre de les seves característiques individuals.
En el mètode més utilitzat, l’aparença visual de cada entitat espaial es representa
independentment com un vector de característiques de dimensions predefinides.
Això permet considerar a les entitats com a punts independents en un espai
vectorial de característiques, i així habilitar un indexat eficient basat en mètodes
d’accés a punts consolidats, que divideixen l’espai al llarg d’una estructura
jeràrquica ordenada. Les relacions mútues entre entitats es poden tenir en compte
en aquest procés de recuperació a través d’un filtre en cascada. Aquest filtre avalua
la similitud en el posicionament de les entitats desprès que aquestes hagin estat
recuperades a partir de les seves característiques individuals.
No obstant, aquest esquema de “matching” no és capaç d’escollir, tot i disminuir la
similitud de les característiques, dues entitats que s’assemblin suficientment.
Per a aconseguir un millor rendiment, s’ha de fer la consulta amb imatges
arxivades. Així maximitzem l’equilibri de similitud conjunta, la rellevància de les
característiques de les entitats individuals i les relacions mútues entre entitats. Això
requereix entitats i relacions representades i comparades com parts d’una
estructura global que captura les dependències mútues. En aquest cas, el model de
contingut pren forma d’ARG, amb vectors entitat i descriptors de relació associats a
vèrtex i arestes, respectivament.
Desafortunadament, la representació d’imatges com a ARGs, incrementa
radicalment la complexitat dels algoritmes de “matching”, i dificulta la viabilitat dels
esquemes d’indexació. Per aquesta raó, encara no s’ha proposat cap solució que
2. Descripció del problema a resoldre, objectius del treball de recerca
22
suporti la aplicació d’ARGs a la recuperació basada en contingut de bases de dades
d’imatges d’interès pràctic. De fet, mentre la distància entre dos conjunts de
vectors independents es pot calcular en un temps polinòmic, la distància entre dos
ARGs requereix la identificació òptima de correcció de l’error d’isomorfisme del
(sub)graf, cosa que és un problema NP-complet amb algoritmes amb un temps de
solució exponencial. A més, la falta de correspondència estructural entre entitats de
diferents imatges dificulta la representació directa de grafs a vectors amb
dimensions i estructura predefinida, impedint així la indexació basada en mètodes
d’accés a punts.
Per tal de comparar un graf amb una gran quantitat d’altres grafs, s’arriba a la
conclusió que el millor és descompondre el problema. En temps
d’emmagatzematge, els grafs es descomponen repetidament en subgrafs i
s’organitzen per mida amb un índex jeràrquic global. En temps d’execució, es fa el
“matching” comparant el graf d’entrada amb els subgrafs amb una composició
d’índex “bottom-up” (de baix cap a dalt). Fent això cada subgraf apareixerà en
múltiples imatges i serà comprovat només un cop, cosa que reduirà la dependència
de la mida de la Base de Dades.
No obstant, aquesta reducció no és tan evident quant els grafs són etiquetats amb
valors numèrics (no simbòlics), una situació molt habitual en aquest tipus de
tecnologia de recuperació. En aquest context, fins i tot en la comparació de models
d’imatges aparentment similars, les diferències entre valors numèrics afecten a
totes les entitats i relacions.
Seguint un enfocament oposat, en un altre paper es representen els grafs com a
objectes amb estructura 3D organitzats en una jerarquia de conjunts, i cada
conjunt es representa com un supermodel paramètric que combina les estructures
dels supermodels que conté. En aquest cas l’accés es fa “top-down” (de dalt a
baix), ignorant aquells conjunts, els supermodels dels quals no corresponen a la
consulta realitzada, i per mitjà de baixar la jerarquia per a identificar un model
específic a través d’un refinament repetitiu de la seva representació paramètrica.
Aquest enfocament pot donar un “speedup” significatiu, però pot causar falsos
rebuigs i exagerar la mida dels supermodels.
En un altre paper, els ARGs que modelen imatges mediques es redueixen a
representacions vectorials habilitant un indexat R-tree (Real-Tree), sota la suposició
que tots els grafs contenen un conjunt d’entitats connexes amb etiquetes
2. Descripció del problema a resoldre, objectius del treball de recerca
23
predefinides. Les entitats no connexes també estan permeses, però el seu nombre
determina una degradació linear en la eficiència de l’índex. Això impedeix l’aplicació
quan les imatges arxivades no comparteixen un mateix nombre dominant d’entitats
connexes. Aquest enfocament no és aplicable en cas que les entitats siguin
identificades per característiques numèriques i ràpidament canviants enlloc
d’utilitzar identificadors simbòlics.
Fig. 5- Exemple senzill de r-tree per a rectangles 2D.
En un article diferent, es mapejen models teòrics de grafs d’objectes estructurals
en espais vectorials a través del càlcul de signatures de les seves “eigenvalues” de
la matriu d’adjacència. Això permet la construcció d’un índex vectorial que permet
una selecció eficient d’un subconjunt de models que tenen una topologia semblant
a la utilitzada en la cerca. No obstant, aquest esquema tampoc es pot aplicar en
grafs etiquetats amb valors numèrics.
En un altre, es proposa una solució general per organitzar bases de dades
d’objectes sense reduir-los a representacions vectorials. De fet, en aquest esquema
d’indexació, els objectes s’agrupen i es recuperen segons les seves distàncies
mútues, enlloc de la seva posició absoluta en el sistema de referències d’un espai
vectorial. Això permet la indexació dels objectes amb alta dimensionalitat i habilita
cerques basades en distàncies de mètrica complexa. Aparentment, la indexació
2. Descripció del problema a resoldre, objectius del treball de recerca
24
mètrica també s’adequa eficientment a les necessitats per a organitzar un arxiu
d’ARGs. No obstant, aquesta solució, que no s’ha posat mai en pràctica, ja que
comporta una major dificultat degut a la necessitat per calcular contínuament les
distàncies d’objectes durant l’accés a l’índex. En el cas d’ARGs arxivats, cada
distància necessita solucionar el problema de correcció de l’error d’isomorfisme,
comportant així una complexitat computacional crítica.
En l’article den del Bimbo, es tracta el problema d’indexació i “matching” d’ARGs
empleat en el context d’aplicació de recuperació d’imatges basades en el contingut.
Es parla sobre aplicacions de models d’imatges que capturen propietats d’entitats i
de les seves relacions. També es descriu la representació com a ARG, i es formula
el càlcul de la distància entre models d’imatges com a correcció òptima al problema
de l’error d’isomorfisme. Desprès es recorden els principis de la indexació mètrica i
s’adapten a les necessitats específiques d’un arxiu de models ARG en el context de
recuperació d’imatges basat en el contingut. Desprès de diverses proves per a
avaluar les teories, els resultats mostren que la estratègia proposada millora l’estat
actual de la tecnologia, en algoritmes basats en espai i estat per al problema de la
correcció de l’error d’isomorfisme, i és capaç de manegar la complexitat en l’ús de
l’esquema d’indexació mètrica per a accedir a una base de dades realista.
Quant a les conclusions, el modelatge del contingut d’imatges basat en ARGs
adapta les necessitats a una recuperació efectiva basada en la similitud conjunta
entre entitats individuals i la seva relació mútua. En particular, això pot servir en
recuperacions per plans espaials. No obstant, la aplicació pràctica d’aquest
enfocament de modelatge es descarta degut a la complexitat de la indexació i el
“matching”. En aquest article es proposa una solució comprensiva per a ambdós
problemes, amb resultats que mostren la seva viabilitat en un context d’ús realista.
Es proposa l’ús de l’esquema d’indexació mètrica com a forma de manegar la
organització de grans arxius d’ARGs amb una mida comú.
Usant aquest esquema, els ARGs s’han organitzat jeràrquicament segons les seves
distàncies mútues, evitant així la necessitat de representar-los en forma vectorial.
Això permet aprofitar la complexitat de la distància mètrica entre grafs i la seva
capacitat per combinar la similitud entre entitats i entre relacions amb una
compensació (trade-off) equilibrada. L’esquema d’indexació proposat també sembla
apropiat per a suportar fàcil integració de cerques i exploracions (browsing),
permetent una participació més propera de l’usuari en la tasca de recuperació.
2. Descripció del problema a resoldre, objectius del treball de recerca
25
Per confirmar la aplicació de l’esquema en el context de recuperació d’imatges
basat en el contingut, s’han realitzat mètodes originals que permeten manegar
diferencies entre funcions de distància usades per a arxivar i recuperar. Aquests
mètodes permeten abastar modalitats de consulta comuns on se li permet a l’usuari
equilibrar la rellevància de diferents característiques visuals i establir el nombre
d’entitats especificant les imatges que espera que apareguin com a resultat.
Aquesta ultima solució sembla adequada quan estenem l’esquema d’indexació al
cas en el que els arxius de grafs tenen diverses mides i suporten funcions de
distància que són tolerants a la presència, en la consulta, d’un subconjunt d’entitats
que no poden fer el “matching” efectivament en el contingut de la base de dades.
L’aplicació de l’esquema d’indexació mètrica a una base de dades realista de
models de grafs, depèn críticament d’una solució eficient per al problema de la
correcció de l’error d’isomorfisme de subgraf. Aquest és el component central
utilitzat en la avaluació repetida de distàncies entre grafs que condueixen l’accés
cap a la jerarquia d’índex. Per a aquesta finalitat, s’ha proposat un algoritme que
combina la cerca amb una estimació original de la visió de futur. Aquesta estimació
es deriva de la solució òptima de l’assignació ponderada, que disminueix el
problema de la visió de futur, amb la finalitat d’eliminar el factor bàsic de
complexitat exponencial. Aquesta classe de disminució dóna com a resultat una
estimació molt ben informada que encara es pot calcular en un temps polinòmic.
Els resultats analítics i experimentals demostren que això millora significativament
l’actual estat de la tecnologia en un mètode de cerca òptima espai-estat. En
concret, la precisió de l’estimació i la seva estructura incremental permeten
reutilitzar un únic conjunt de condicions amb visió de futur al llarg de tot el procés
de “matching”. Això s’anomena “look-ahead” global en contrast amb la pràctica
usual de mètodes de branca i límits (branch and bound) on es calcula una
estimació per cada estat intermedi del procés de cerca. L’ús d’un únic “look-ahead”
global redueix dràsticament la càrrega computacional en la estimació (i també la
dificultat de programació en la seva aplicació pràctica), i, a més, encara dóna un
“look-ahead” que, de lluny, està més informat que els resultats anteriors de la
bibliografia.
L’experiència computacional demostra que l’ús combinat de l’esquema de
“matching” i indexació proposat, permet gestionar la complexitat d’una aplicació
típica de recuperació basada en la disposició visual del contingut. La implementació
2. Descripció del problema a resoldre, objectius del treball de recerca
26
i experimentació de l’aplicació també permet entendre les dependències crítiques
entre aspectes de la complexitat computacional i la efectivitat de percepció.
L’avaluació conjunta d’ambdós aspectes simulats combina recerca i experimentació
de “trade-offs” (compensació).
3. Disseny de la nova solució, justificació de la nova proposta
27
3. Disseny de la nova solució, justificació de la nova proposta
En aquest punt es descriuran les diferents parts teòriques que té el nou model.
L’objectiu bàsic que es pretén assolir és el de crear un nou mètode d’organitzar una
base de dades de grafs estructurada en forma d’arbre, en la que els routing objects
són prototips dels subconjunts de nodes fulla (grafs nous creats a partir dels nodes
fulla) i comparar-la amb un altre mètode, amb la mateixa estructura però en el que
els routing objects són representants dels subconjunts de nodes fulla (un mateix
graf del node fulla es replica i es promociona). S’explicaran les diverses opcions que
hi havia en cada cas i se’n veuran els avantatges i inconvenients que proporciona
cada opció. Al final de cada punt, s’explicarà l’opció escollida en detall i el perquè
d’aquesta elecció.
3.1- Mètrica: graph edit distance
Abans de començar a explicar l’estructura, definirem el concepte de mètrica.
En matemàtiques, una mètrica o funció de distància és una funció que defineix una
distància entre els elements d’un conjunt. S’anomena espai mètric un conjunt amb
una mètrica. Una mètrica indueix una topologia en un conjunt però no totes les
topologies poden ser generades per una mètrica. Quan un espai topològic te una
topologia que pot ser descrita per una mètrica, es diu que l’espai topològic és
metritzable. Una mètrica en un conjunt X és una funció de distància o simplement
la distància:
d : X × X → R
On R és el conjunt de tots els nombres reals. Per tot x, y, z en X, aquesta funció
requereix que es satisfacin les següents condicions:
1. d(x, y) ≥ 0 � no negativitat (la impliquen les altres)
2. d(x, y) = 0 si i només si x = y � identitat dels indistingibles
Nota: les condicions 1 i 2 juntes produeixen definitud positiva
3. d(x, y) = d(y, x) � simetria
4. d(x, z) ≤ d(x, y) + d(y, z) � desigualtat triangular:
3. Disseny de la nova solució, justificació de la nova proposta
Ja parlant sobre la mètrica escollida per desenvolupar aquest treball, parlarem de la
graph edit distance [7] o distància d’edició
com la mínima quantitat de distorsió que es necessita per a transformar un graf en
un altre. Aquesta distorsió s’afegeix mitjançant les operacions d’edició
operacions d’edició poden ser:
dels elements que formen un graf, és a dir,
El conjunt de distorsions aplicades a un graf per a arribar a un altre s’anomena
camí d’edició (edit path [
distància es calcula utilitzant aquests valors
complicades, en les que no entrarem en aquest treball
A continuació es veurà un exemple de com calcular la distància entre dos grafs, g
g2:
En la figura 7, es mostra com,
el primer pas s’eliminen tres arestes. En el segon pas s’elimina un node. En el
tercer s’afegeix un node. En el quart, s’afegeixen dues arestes, i ja tenim el g
Aquests passos es combinen amb d’altres de modificació de
complicats de representar en un gràfic visual.
3. Disseny de la nova solució, justificació de la nova proposta
mètrica escollida per desenvolupar aquest treball, parlarem de la
distància d’edició de grafs. Es defineix dissimilitud de grafs
nima quantitat de distorsió que es necessita per a transformar un graf en
un altre. Aquesta distorsió s’afegeix mitjançant les operacions d’edició
operacions d’edició poden ser: insercions, eliminacions i substitucions
e formen un graf, és a dir, de nodes i arestes.
El conjunt de distorsions aplicades a un graf per a arribar a un altre s’anomena
[8]). A cada distorsió se li assigna un valor o pes. I la
distància es calcula utilitzant aquests valors, amb funcions de ponderació
complicades, en les que no entrarem en aquest treball.
A continuació es veurà un exemple de com calcular la distància entre dos grafs, g
Figura 7: grafs d’exemple
com, afegint una sèrie de distorsions a g1 s’arriba a g
el primer pas s’eliminen tres arestes. En el segon pas s’elimina un node. En el
tercer s’afegeix un node. En el quart, s’afegeixen dues arestes, i ja tenim el g
Aquests passos es combinen amb d’altres de modificació de nodes i arestes, més
complicats de representar en un gràfic visual.
Figura 6: exemples de
desigualtat triangular.
La figura de dalt
mostra una desigualtat
estricta i la figura de
baix mostra una
igualtat.
28
mètrica escollida per desenvolupar aquest treball, parlarem de la
s defineix dissimilitud de grafs
nima quantitat de distorsió que es necessita per a transformar un graf en
un altre. Aquesta distorsió s’afegeix mitjançant les operacions d’edició ei. Les
insercions, eliminacions i substitucions de qualsevol
El conjunt de distorsions aplicades a un graf per a arribar a un altre s’anomena
). A cada distorsió se li assigna un valor o pes. I la
amb funcions de ponderació
A continuació es veurà un exemple de com calcular la distància entre dos grafs, g1 i
s’arriba a g2. En
el primer pas s’eliminen tres arestes. En el segon pas s’elimina un node. En el
tercer s’afegeix un node. En el quart, s’afegeixen dues arestes, i ja tenim el g2.
nodes i arestes, més
: exemples de
desigualtat triangular.
La figura de dalt
mostra una desigualtat
estricta i la figura de
baix mostra una
3. Disseny de la nova solució, justificació de la nova proposta
29
Figura 8: edit path [8] entre g1 i g2.
Tot i que sembla evident, cal remarcar que, com es veurà en el punt 4.1, no
existeix un únic camí d’edició, i que calcular l’òptim és una tasca
computacionalment costosa.
3.2- L’estructura: m-tree
Per a dissenyar l’estructura ens hem basat en l’m-tree [4], o metric tree, que és el
tipus d’arbre que s’utilitza en [2]. S’ha escollit aquest perquè dóna un mètode
d’accés eficient per a la cerca per similitud en espais mètrics i grans bases de
dades. En [4] es demostra que aquest tipus d’arbre amplia el domini d’aplicabilitat
més enllà dels tradicionals espais vectorials, rendeix raonablement bé en espais de
dades d’altes dimensions, i escala bé en cas d’arxius que creixen (en pes) amb el
pas del temps. És un arbre balancejat, capaç de tractar arxius de dades dinàmics,
de tal manera que no requereix reorganitzacions periòdiques. Pot indexar objectes
usant comparació de característiques mitjançant funcions de distància que no caben
en un espai vectorial o no usen una mètrica Lp, cosa que amplia considerablement
els casos pels quals el processament de cerques és possible. El disseny d’aquest
tipus d’arbre s’inspira en els principis d’arbres mètrics i mètodes d’accés a bases de
dades, i la optimització del rendiment té en compte tant la CPU (càlculs de
distància) i costos d’E/S. Divideix objectes segons les seves distàncies relatives,
calculades amb la funció de distància específica d, i emmagatzema aquests objectes
en nodes de mida fixa, que corresponen a regions obligades de l’espai mètric.
Usant un indexat mètric es divideix un arxiu en una col�lecció jeràrquica de
conjunts, que reuneix objectes similars. Cada conjunt té una referència (routing
object) i un radi que dóna un límit superior per a la distància màxima entre
l’objecte referència i qualsevol altre objecte del conjunt. En l’m-tree cada node
3. Disseny de la nova solució, justificació de la nova proposta
30
conté un nombre màxim fixat de m entrades (entries). A la seva vegada, cada
entry conté:
- un routing object D;
- una referència a l’arrel subD, d’un (sub)índex que conté els ARGs en l’anomenada
covering region de D;
- radi µD que prové un límit superior per a la distància entre D i qualsevol ARG en la
seva covering region;
< node > ::. {< entry >}m < entry > ::. D, subD; µD.
Aquest esquema es pot aplicar per organitzar una col�lecció gran d’objectes, sense
requerir que aquests s’hagin de passar a una representació vectorial, i més aviat
que es compti amb la seva distància mútua. Si la distància és mètrica, es pot usar
la desigualtat triangular (triangular inequality) durant l’accés a l’arxiu per retallar
conjunts que surten d’un rang assignat des d’una consulta (query).
Figura 9: Organització m-tree per a un conjunt d’objectes en un espai bidimensional. En
aquest exemple s’ha assignat 3 com a mida fixa del node.
Entre les modificacions que hem fet al m-tree dissenyat en [2] i [4], per a que sigui
més eficient i s’adeqüi millor a les nostres necessitats, destaca el canvi de la mida
fixa dels nodes per variable, ja que d’aquesta manera es poden fer clústers basant-
se únicament en la distància. Si es fixa la mida dels nodes, es a dir, el nombre
d’entries que tindrà cada node, es condiciona a l’algorisme de clustering, i força que
s’ajuntin entries que poden tenir distàncies molt grans, augmentant així el radi i en
conseqüència, el solapament com es veu en la figura 9. Tots aquests canvis fan que
disminueixi l’eficiència de la cerca augmentant el nombre d’accessos. També, i per
la mateixa raó, s’ha canviat que l’arbre es mantingui balancejat.
3. Disseny de la nova solució, justificació de la nova proposta
31
A l’hora d’indexar, s’agafa subD, que recordem que era l’índex al node fill, de la
següent manera:
Pare p
Com a exemple de l’aplicació de la nostra estructura d’arbre a la seguretat en el
camp de la biometria es pot agafar el següent: Francis Galton(1822-1911) va
classificar les ditades com: arch, left loop, right loop, whorl, etc., i en el nostre
arbre podrien quedar classificades de la següent manera:
x, r(x), indexFill(x) y, r(y), indexFill(y)
z
Figura 11: Entry Index = (routing object, índex al fill, covering radi),
Tots els objectes del subarbre estan dins del “covering radi” del routing object
x y
d(y,z)≤ r(y)
a) b)
Figura: 10 efecte de la fixació de la mida del node a l’hora de fer el clustering:
En la figura a) hem agafat 3 com a mida fixa del node i veiem com les covering region són
molt més grans i hi ha solapament, pel que la cerca serà mol menys eficient (hi ha molta
més area ocupada que fa que augmenti la probabilitat d’explorar tots els entries que formen
aquell node) que en la figura b) on les covering region són molt més petites i a sobre, no hi
ha solapament.
3. Disseny de la nova solució, justificació de la nova proposta
Figura 12:exemple
3.3- Clustering: dendrograma
El primer que es farà en aquesta secció és definir la paraula clau cl
segons el TERMCAT (organisme català destinat a estudiar la terminologia en
català), i segons ens mostra l’enciclopèdia catalana, és
funcionals interconnectades per mitjà d'una
En el nostre cas muntarem clústers de gr
s’uniran per a formar nodes. Aquests formaran l’arbre resultant.
Un algorisme de clustering és, doncs, un procediment de càlcul que unirà, en el
nostre cas, un conjunt de grafs segons una política a escollir
nodes, que s’uniran, completaran l’arbre
d’aquest tipus que existeixen avui en dia, s’ha decidit utilitzar l’anomenat
dendrograma per la seva facilitat de comprensió i d’ús, unida al seu més que
correcte rendiment.
3. Disseny de la nova solució, justificació de la nova proposta
12:exemple d’aplicació de m-tree en el camp de la biometria
ing: dendrograma
El primer que es farà en aquesta secció és definir la paraula clau clúster. Un cl
organisme català destinat a estudiar la terminologia en
, i segons ens mostra l’enciclopèdia catalana, és un conjunt d'unitats
funcionals interconnectades per mitjà d'una xarxa que actuen com una sola unitat
En el nostre cas muntarem clústers de grafs, on cadascun formarà un
s’uniran per a formar nodes. Aquests formaran l’arbre resultant.
Un algorisme de clustering és, doncs, un procediment de càlcul que unirà, en el
nostre cas, un conjunt de grafs segons una política a escollir per tal de
, completaran l’arbre. Entre la gran varietat d’algorismes
d’aquest tipus que existeixen avui en dia, s’ha decidit utilitzar l’anomenat
dendrograma per la seva facilitat de comprensió i d’ús, unida al seu més que
Arch
32
tree en el camp de la biometria
ster. Un clúster,
organisme català destinat a estudiar la terminologia en
un conjunt d'unitats
que actuen com una sola unitat.
, on cadascun formarà un entry, i
Un algorisme de clustering és, doncs, un procediment de càlcul que unirà, en el
per tal de formar
. Entre la gran varietat d’algorismes
d’aquest tipus que existeixen avui en dia, s’ha decidit utilitzar l’anomenat
dendrograma per la seva facilitat de comprensió i d’ús, unida al seu més que
3. Disseny de la nova solució, justificació de la nova proposta
33
El dendrograma és un tipus de representació gràfica o diagrama de dades en forma
d’arbre (del grec Dendro=arbre i Grama=gràfic) que organitza les dades en
subcategories que es van dividint en d’altres fins a arribar al nivell de detall desitjat
(assimilant-se a las branques d’un arbre que es van dividint en altres
sucessivament). Aquest tipus de representació permet apreciar clarament las
relacions d’agrupació entre les dades i entre grups d’elles encara que no les
relacions de similitud o proximitat entre categories.
Observant las successives subdivisions podem fer-nos una idea sobre els criteris
d’agrupació dels mateixos, la distància entre les dades segons les relacions
establertes, etc. També podríem referir-nos al dendrograma com la il�lustració de
las agrupacions derivades de la aplicació d’un algoritme de clustering.
Com a exemple, imaginem que les dades següents s'han d'agrupar usant
la distancia euclidiana com a distància mètrica.
Figura 13: Els nodes de la línia superior representen les dades, la resta de nodes representen
els agrupaments als quals pertanyen, i les fletxes representen la distància.
3.4- Representant smallest SOD (sum of distances)
Es poden implementar diferents politiques per a seleccionar el node fulla més
apropiat per a promoure i representar un clúster de grafs. Les polítiques més
comuns són les anomenades “Minimum of Maximum of Radii” (que redueix la mida
3. Disseny de la nova solució, justificació de la nova proposta
34
dels conjunts) i “Maximum Lower Bound on Distance” (que redueix la superposició
entre diferents conjunts).
En aquest treball, per a simplificar la feina, i enfocar els nostres esforços a assolir
els objectius proposats al principi, s’ha escollit que el representant d’un node sigui
el graf del clúster que tingui la mínima suma de distàncies (minimum or smallest
SOD) entre ell i la resta de grafs del subconjunt al que pertany. Aquest
representant també s’anomena Set Median. Hi ha altres politiques que tenen un
rendiment que a la llarga s’acosta al Set Median però tenen desavantatges com
l’augment del temps de computació o el solapament. Tot i que un dels objectius és
comparar els solapaments, no s’ha volgut comparar el nou model amb un que fos
absolutament ineficient, sinó que s’ha buscat un que rendís de forma raonable, amb
un cost de creació d’arbre i de cerca moderat.
3.5- Prototips: median graph
S’ha decidit buscar un prototips amb l’objectiu de reduir el solapament de zones i,
per tant, el nombre d’accessos. Per a calcular el radi es busca la distància més gran
del centre al graf mes llunyà i se li suma el radi d’aquest graf més llunyà. Si fem el
prototips aquest és equidistant a la resta de grafs, però si agafem un representant,
al no estar aquest just al centre de la resta, la distància entre aquest i el més llunyà
serà més gran, i en conseqüència, també ho serà el radi, fent la covering region del
representant més gran que la del prototips. Com això influeix a tot el conjunt de
representants, s’incrementen totes les covering region del nostre espai i el
solapament augmenta de manera exagerada. Aquest factor incideix directament en
la cerca, ja que com més grans siguin les covering region, més gran serà la
possibilitat de que l’algorisme de cerca hagi d’explorar aquestes zones, cosa que
implica fer càlculs i que, d’aquesta manera, disminueixi el seu rendiment.
3. Disseny de la nova solució, justificació de la nova proposta
35
Com s’introduïa abans i es veu en la figura anterior, aquest factor implica que, si
busquem algun graf posicionat en aquesta zona de solapament, s’hauran de
comparar els dos representants i recórrer els fills d’aquests ja que entren a la
covering region. D’aquesta manera, l’algorisme de cerca interpreta que és possible
que existeixi algun graf en aquella zona. En canvi, al utilitzar prototips, ens
estalviem aquestes dues comparacions (i els recorreguts dels fills corresponents)
Solapament
a) Representant
X
r
X
r
b) Prototips
X
P X
P
Figura 14: comparació de radis utilitzant com a centre:
a) un representant b) el prototips
3. Disseny de la nova solució, justificació de la nova proposta
36
perquè aquell espai mort ja no existeix, cosa que ens informa que no hi ha cap graf
en aquella zona.
En aquest exemple es pot veure també que la tolerància de la cerca, radi de cerca o
el que anomenem µMAX, hauria de ser molt gran en l’exemple dels prototips per tal
Area tractada
a) Representant
X
r
X
r
b) Prototips
X
P X
P
Figura 15: comparació d’àrees explorades en la cerca d’un objecte
posicionat qualsevol punt de l’àrea de solapament de a, utilitzant com a centre a) un
representant b) el prototips
3. Disseny de la nova solució, justificació de la nova proposta
37
que la cerca hagués d’explorar tots els fills ha de ser molt gran, pel que també es
pot afirmar que el nou sistema és més tolerant a la variació d’aquest factor.
El graf escollit per a calcular el prototips és l’anomenat Median Graph, concepte del
qual, ja ha estat introduït en el punt 2.7.1.7.
En aquest punt, només afegir que el càlcul del Median Graf és exponencial tant en
nombre de grafs d’entrada (que fa que l’espai de cerca per al càlcul sigui molt gran)
com en la seva mida (degut a la complexitat de càlcul de la distància entre dos
grafs). En el passat s’han proposat un elevat nombre d’algoritmes per a calcular els
Median Grafs però l’únic exacte que s’ha proposat fins ara es basa en un algorisme
A*(A star o A estrella) utilitzant una estructura de dades anomenada multimatch.
Com el cost computacional d’aquest algorisme és molt elevat, s’utilitzen d’altres
aproximacions com la cerca genètica i els algorismes greedy-based. Malgrat aquest
desavantatge clar, s’utilitzarà l’algorisme A*, disminuint una mica la precisió
d’aquest per tal de que sigui factible fer tests en la nostra màquina.
Fins ara, els MG s’han utilitzat satisfactòriament per a obtenir prototips de símbols
gràfics, per a obtenir median words per tasques OCR i per a realitzar clustering
d’imatges basat en contingut. Però totes aquestes aplicacions s’han provat en
dades sintètiques o en grafs molt petits, a vegades només representats per nodes.
Així, a pesar de la seva potencial aplicació, e seu ús s’ha limitat a escenaris amb
poca aplicabilitat real.
3.6- Cerca
Durant la cerca i recuperació, es pot usar la desigualtat triangular (explicada en el
punt 3.1- Mètrica: graph edit distance) per a mantenir un processat eficient de les
cerques de rang. Un exemple en són les cerques que busquen tots els grafs d’un
arxiu que estiguin en un rang de distància donat (que nosaltres anomenem µmax),
des d’un element de cerca Q. Per a això, la distància entre Q i qualsevol graf,
anomenem-lo D, en la covering region del routing object D, pot ser limitada
utilitzant el radi µD i la distància entre D i Q. Específicament, si µmax és el rang de la
consulta, es pot utilitzar la següent consulta per comprovar si tots els grafs en la
regió coberta per D poden ser descartats, basant-nos en un sol càlcul de la
distancia µ(Q,D):
3. Disseny de la nova solució, justificació de la nova proposta
38
µ(Q, D) ≥ µmax + µD � cap ARG in subD és acceptable: (a)
De forma similar, la condició següent comprova si tots els grafs den la regió coberta
per D cauen dintre del rang de la consulta (en aquest cas, tots els grafs de la regió
poden ser acceptats):
µ(Q, D) ≤ µmax - µD � cada ARG en subD és acceptable: (b)
En el cas crític que cap de les dues desigualtats (a) o (b) es complís, la regió que
cobreix D ha de contenir tant els ARGs acceptables com els que no ho són, i la
cerca ha de repetir-se amb el subíndex subD.
Així doncs i en resum, es farà la cerca de tots els grafs que estiguin a una distància
µmax de l’element de cerca Q que se li introdueixi al sistema. Si es vol buscar algun
graf de manera exacta, només s’ha d’assignar a µmax el valor 0.
Les consultes K-nearest neighbour que cerquen els K grafs que siguin més
semblants a la cerca en l’arxiu es poden manegar de manera similar, però amb
menys eficiència. Així s’obté, mitjançant la consideració de la consulta com un cas
particular en el que el rang µmax, es determinat durant la cerca. Mentre (a) encara
pot ser aplicada, (b) requereix una major complexitat, encara que el manegament
és intuïtiu.
3.7- Anàlisi de l’arbre: el factor solapament
Un dels objectius d’aquest projecte és reduir el nombre d’accessos per tal
d’augmentar la velocitat de recuperació d’informació emmagatzemada en forma de
grafs d’una base de dades. Per tal d’assolir aquest objectiu, el primer pas és reduir
el solapament entre els clústers que formen cada node de l’arbre, per a explorar el
mínim de branques possibles, fent així, el mínim càlcul de distàncies possible.
En un principi, es va decidir calcular-lo com la suma dels radis dels fills agafats de
dos en dos menys la distància entre ells. Si la suma dels radis era més gran que la
distància entre els dos entries, el solapament era la suma dels radis menys la
distància entre entries. D’altra banda, el solapament era zero.
A continuació veurem el pseudocodi per a intentar que tot quedi més clar:
3. Disseny de la nova solució, justificació de la nova proposta
39
Si (Ri+Rj)>d(i,j) aleshores
S(i,j)=Ri+Rj-d(i,j);
Sinó
S(i,j)=0;
Fsi
Això es faria per a tots els germans, calculant la distància de tots amb tots, i se’n
faria la mitja amb el nombre de germans al quadrat com es mostra tot seguit:
89 � ∑ ∑ 8�;, <�=#>�=�#+@�A�BC.
Aquesta definició ens mostrava uns resultats força interessants però que eren
excessivament positius, pel que vam haver de treballar més aquesta definició. Al
repassar-ho, ens vam adonar que no s’estava sent just amb la forma que tindria
l’arbre i ho vam definir com segueix. Per cada germà es calcula la suma del seu radi
amb el de cadascun dels germans i es divideix distància entre els dos entries. Si
aquesta divisió és més gran que 1, s’assigna el resultat d’aquesta divisió al
solapament entre aquests dos entries.
Si 8 � �D�4D��E��,�� >1 aleshores
S(i,j) � �D�4D��E��,��
Sinó
S(i,j)=0;
Fsi
Això es farà per a tots els germans, calculant la distància de tots amb tots, i se’n
farà la divisió amb el binomi de Newton com es mostra tot seguit:
8F � ∑ ∑ G�H�,H#�IJKLIL /MN0 ; on N és el nombre de fills de l’entry.
4. Aspectes de desenvolupament i implementació
4. Aspectes de desenvolupament i implementació
Per al desenvolupament d’aquest article
Aquest és un entorn de computació numèrica
per la companyia The MathWorks
dibuixar funcions i dades, implementar algorismes, crear
comunicar-se amb altres programes en altres llenguatges. Aquesta característica ha
estat molt útil ja que des d’aquest entorn, s’han realitzat crides a codi Java per tal
de calcular les distàncies, els camins d’edició i els
que s'especialitza en computació numèrica, una caixa d'eines opcional (
permet treballar en altres camps
4.1- Mètrica: graph edit distance
La distància d’edició es defineix com:
On és el conjunt de camins
d’edició que mesura el pes c(e
Tot i que questa distància proporciona un model de desigualtat general per als
grafs, s’ha de tenir en compte la complexitat de l’algorisme de cerca d’aquesta
distància. S’utilitzen arbres de cerca com a formalismes representatius del
problema d’optimització del camí. Es a dir, s’utilitza una heurística que té en
compte totes les possibilitats
4. Aspectes de desenvolupament i implementació
Aspectes de desenvolupament i implementació
Per al desenvolupament d’aquest article s’ha utilitzat bàsicament
computació numèrica i un llenguatge de programació. Creat
The MathWorks, MATLAB permet manipular fàcilment
i dades, implementar algorismes, crear interfícies d'usuari, i
se amb altres programes en altres llenguatges. Aquesta característica ha
es d’aquest entorn, s’han realitzat crides a codi Java per tal
de calcular les distàncies, els camins d’edició i els prototips (median graphs
que s'especialitza en computació numèrica, una caixa d'eines opcional (
altres camps.
Mètrica: graph edit distance
La distància d’edició es defineix com:
és el conjunt de camins que transformen g1 en g2 , i c és la funció de cost
d’edició que mesura el pes c(ei) de cada operació d’edició ei.
ncia proporciona un model de desigualtat general per als
grafs, s’ha de tenir en compte la complexitat de l’algorisme de cerca d’aquesta
S’utilitzen arbres de cerca com a formalismes representatius del
ció del camí. Es a dir, s’utilitza una heurística que té en
possibilitats.
40
bàsicament MATLAB.
ogramació. Creat
, MATLAB permet manipular fàcilment matrius,
interfícies d'usuari, i
se amb altres programes en altres llenguatges. Aquesta característica ha
es d’aquest entorn, s’han realitzat crides a codi Java per tal
median graphs). Tot i
que s'especialitza en computació numèrica, una caixa d'eines opcional (toolbox)
és la funció de cost
ncia proporciona un model de desigualtat general per als
grafs, s’ha de tenir en compte la complexitat de l’algorisme de cerca d’aquesta
S’utilitzen arbres de cerca com a formalismes representatius del
ció del camí. Es a dir, s’utilitza una heurística que té en
4. Aspectes de desenvolupament i implementació
Figura 16: arbre de cerca en el que el node arrel representa
inicial de la nostra cerca, i els nodes fulla representen camins compl
solucions al problema proposat de transformar un graf completament en un altre.
La solució amb el pes més petit serà la solució òptima, es a dir, distància més
acurada i el camí d’edició més precís entre
La complexitat de càlcul del camí d’edició òptim
Els nodes del graf font poden ser mapejats com qualsevol dels nodes del graf destí,
cosa que pot portar problemes
sigui exponencial en quant al nombre de nodes en els grafs en general
alguns casos concrets pot ser només lineal.
Figura 17: totes les combinacions possibles per a assignar nodes
Per a obtenir les distàncies i el camí d’edició entre dos grafs, s’ha incorpo
l’algorisme ideat i desenvolupat
donats pels mateixos articles
testos. Es va mirar que aquests valors influïssin de tal manera que els resultats
donats fossin el més reals possibles.
Per a començar a calcular la distància, es necessiten dos grafs g1 i g2
anomenarem source (font)
aplicarem les distorsions per tal que arribi
objectiu. Cada graf està format per
- Matriu d’ocurrència
apareixen a la vegada. En matlab es pot saber el nombre de nodes del graf
4. Aspectes de desenvolupament i implementació
arbre de cerca en el que el node arrel representa el principi
i els nodes fulla representen camins complets, que proporcionen
solucions al problema proposat de transformar un graf completament en un altre.
La solució amb el pes més petit serà la solució òptima, es a dir, distància més
acurada i el camí d’edició més precís entre ambdós grafs.
de càlcul del camí d’edició òptim és el seu principal desavantatge.
Els nodes del graf font poden ser mapejats com qualsevol dels nodes del graf destí,
cosa que pot portar problemes, i, també, provoca que el càlcul d’aquesta assignació
n quant al nombre de nodes en els grafs en general
casos concrets pot ser només lineal.
totes les combinacions possibles per a assignar nodes
Per a obtenir les distàncies i el camí d’edició entre dos grafs, s’ha incorpo
desenvolupat en [5] i [6]. Els pesos de les distorsions venen
donats pels mateixos articles i van ser trobats mitjançant un elevat nombre de
mirar que aquests valors influïssin de tal manera que els resultats
ossin el més reals possibles.
Per a començar a calcular la distància, es necessiten dos grafs g1 i g2
(font) i target (destí), ja que g1 serà el graf inicial
aplicarem les distorsions per tal que arribi a convertir-se en g2 , que serà el graf
format per tres matrius:
Matriu d’ocurrència: matriu que indica si en la posició (x,y)
apareixen a la vegada. En matlab es pot saber el nombre de nodes del graf 41
del camí, o punt
ets, que proporcionen
solucions al problema proposat de transformar un graf completament en un altre.
La solució amb el pes més petit serà la solució òptima, es a dir, distància més
principal desavantatge.
Els nodes del graf font poden ser mapejats com qualsevol dels nodes del graf destí,
d’aquesta assignació
n quant al nombre de nodes en els grafs en general, tot i que en
totes les combinacions possibles per a assignar nodes.
Per a obtenir les distàncies i el camí d’edició entre dos grafs, s’ha incorporat
en [5] i [6]. Els pesos de les distorsions venen
van ser trobats mitjançant un elevat nombre de
mirar que aquests valors influïssin de tal manera que els resultats
Per a començar a calcular la distància, es necessiten dos grafs g1 i g2, que
serà el graf inicial al que
que serà el graf
), els dos nodes
apareixen a la vegada. En matlab es pot saber el nombre de nodes del graf
4. Aspectes de desenvolupament i implementació
42
fent: diag(squeeze(class(1).occurrenceMatrix(1,:,:))). Un exemple d’aquesta
matriu, amb 2 nodes, per exemple la lletra I seria:
O1 1 0 R1 1 0 R0 0 0 RS S S T O
Aquesta matriu indica que existeixen els nodes 1 i 2, ja que els índexs (1,1),
(1,2), (2,1) i (2,2) tenen el valor 1, i es compleix la característica
esmentada en el paràgraf anterior.
- Matriu d’adjacències: matriu que ens dona informació sobre les arestes. On
les i, i les j són els identificadors del node. Si hi ha aresta entre el node i, i
el node j, el valor de MatriuAdjacencies[i,j] serà 1. En cas contrari serà 0.
Continuant amb l’exemple de la classe de la lletra I, el graf que representa
aquesta lletra te una aresta entre els nodes 1 i 2. Val a dir que si les arestes
són dirigides, i en conseqüència, el graf és dirigit (la relació entre els vèrtexs
no és simètrica), la matriu no serà simètrica. En el nostre cas, les arestes no
són dirigides i per tant la matriu serà simètrica. Podem veure com les
posicions (1,2) i (2,1) tenen valor 1 perquè hi ha una única aresta entre el
node 1 i el node 2, que és la mateixa que de 2 a 1.
O0 1 0 R1 0 0 R0 0 0 RS S S T O
- Matriu d’atributs quantitatius dels nodes: matriu de 2X#grafs que guarda els
valors x i y amb les coordenades de cada node. En la matriu, les dades es
guarden com x=(1,índex) i y=(2,índex), on índex és l’identificador del graf del
que formen part aquestes coordenades..
N1 N2 … UV W1,23 1,23 0 R0,59 4,52 0 RW
Per la qual cosa tenim cada node i cada aresta identificat. L’algorisme els identifica i
relaciona com es mostra en la figura:
4. Aspectes de desenvolupament i implementació
43
Figura 18: Identificació i relació de nodes i arestes dels grafs source i target.
A continuació es van creant diversos camins d’edició mitjançant l’aplicació de
distorsions trobades per un algorisme A*, que queda fora de l’abast d’aquest
treball. Com que no existeix un únic camí d’edició, aquest algorisme els mira tots
(si es busca l’òptim), sinó només alguns, i s’encarrega de tornar el camí més adient
segons els paràmetres introduïts, amb un temps de resposta força bo en
comparació als diversos algorismes existents avui en dia. Aquest anàlisi i
desenvolupament s’ha fet en [5] i [6]. Anteriorment, en la secció 3.1, s’ha
comentat que, és un algorisme computacionalment costós, però el fet que tingui un
paràmetre d’optimització configurable i que entre tots els algorismes actuals trobi el
camí d’edició més òptim ens ha fet decidir per ell.
4.2- L’estructura
Segons els experiments realitzats en [4], en un m-tree, es poden escollir dos
factors que incideixen directament en el rendiment del arbre: la distribució dels
entries i la elecció dels routing objects. En el primer hi ha dues polítiques, que es
poden descriure de la següent manera:
• Generalized Hyperplane: Assigna cada objecte Oj Є N al routing object més proper: si d(Oj,Op1) ] d(Oj, Op2) aleshores assigna Oj a N1, sinó assigna Oj a N2.
• Balanced: Calcula d(Oj, Op1) i d(Oj, Op2,) per tot Oj Є N. Repeteix fins que N estigui buit:
4. Aspectes de desenvolupament i implementació
44
o Assigna a N1 el veí més proper a Op1 en N i elimina’l de N;
o Assigna a N2 el veí més proper a Op2, en N i elimina’l de N.
Depenent de la distribució de les dades i de com es triïn els objectes, no balancejar
l’arbre provoca que s’encamini millor cap als objectes degut a el grau addicional de
llibertat que obté. També és millor que fer-lo balancejat pel fet que no
s’incrementen els radis de les regions al llarg de les dimensions necessàries. En un
espai mètric, el consegüent increment del covering radius es propaga a totes les
“dimensions”. És per això que hem decidit fer-lo no balancejat.
El segon factor (la elecció dels routing objects) s’utilitza en el moment de
promoure. Aquest mètode determina, donat un conjunt d’entries, N, dos objectes
poden ser promoguts i emmagatzemats en el node pare. Els algorismes específics
que es tracten en [4] es poden classificar primerament d’acord en si confirmen o no
al pare original. Una política de divisió confirmada escull un objecte promogut, per
exemple O1 , com a objecte pare del node dividit.
En altres paraules, una política de divisió confirmada només extreu una regió,
centrada en el segon routing object, Op2, de la regió en la que encara es mantindrà
centrada en Op. En general, això simplifica l’execució de la divisió i redueix el
nombre de càlculs de distància.
Les alternatives descrites per implementar el promoure explicades a continuació
són un subconjunt de polítiques que han estat seleccionades del conjunt complet
avaluat en [4], format per:
• m_RAD: l’ algorisme "minimum (sum) of radii" és el més complex en termes
de càlculs de distància. Es consideren tots els possibles parells d'objectes i,
després de la partició del conjunt d'entrades, promou el parell d'objectes per
als quals la suma de la covering radii, r(Op1) + r (Op2), és mínim.
• mM_RAD: és semblant a m_RAD, però minimitza el màxim dels dos radis.
• M_LB_DIST: l’acrònim ve de “Maximum Lower Bound on DISTance”.
Aquesta política canvia de la anterior en que només utilitza distàncies
precalculades. En la versió confirmada on Op1 ^ Op2, l’algorisme determina
Op2 com l’objecte més llunya d’ Op que és:
4. Aspectes de desenvolupament i implementació
45
d(Op2, Op)=maxj {d(Oj, Op)}.
- RANDOM: aquesta variant escull de forma aleatòria com referenciar
objectes. Encara que no és una estratègia gaire intel�ligent, es ràpida i el
seu rendiment pot ser utilitzat per a comparar-lo amb altres polítiques.
- SAMPLING: aquesta és una política aleatòria, però iterada sobre una mostra
d’objectes de mida s>1. Els entries són distribuïts per a cada parell
d’objectes s(s-1)/2 de la mostra, i s’estableix el coveriing radii. Aleshores es
tria la parella de la qual el màxim resultat dels dos coveriing radiis és
mínim. En el cas de la promoció confirmat, només s diferents distribucions
són analitzades. La mida gran de la mostra en els experiments realitzats en
[4], es va establir a la desena part de la capacitat dels nodes.
De totes aquestes polítiques, s’ha escollit la M_LB_DIST per als representants, ja
que minimitzarà els radis i, en conseqüència els solapaments i el nombre
d’accessos. D’aquesta manera tindrà molt més valor que el model desenvolupat
durant aquest treball sigui més eficient. En el primer pas del procés de creació d’un
arbre, es calculen les distàncies de tots a tots per a que, posteriorment, puguin ser
utilitzades per a iniciar l’algorisme de clustering. Aquestes distancies
s’emmagatzemen en una matriu mDis, i s’utilitzen desprès en la cerca per a
estalviar temps en fer els tests i com que no compararem temps de cerca, no
afectarà a la nostra anàlisi i ens permetrà utilitzar aquest temps en fer més testos.
Per a mantenir la mateixa estructura d’arbre entre l’arbre muntat amb prototips i
l’arbre muntat amb representants, i que aquests siguin comparables, a l’hora de
promoure un prototips, calculem aquest i el promovem directament. Ho fem de la
mateixa manera amb el representant. El calculem els representants de cada clúster
i els promovem, però no deixem de tenir-lo a les fulles. Dit d’una altra manera, el
repliquem i el promovem. En la cerca, els routing objects no conten com a objectes
a trobar, pel que només s’acceptaran els nodes fulla.
Per tal de millorar l’eficiència de l’arbre i enfocar els esforços de la recerca cap als
objectius comentats al principi, s’han utilitzat els conceptes teòrics de l’m-tree però
sense implementar les funcions inserir i esborrar. En conseqüència no ens calen
tampoc les politiques de dividir nodes. En canvi, si que utilitzem la funció de
promoció en el moment d’escollir un representant, com s’explicarà més endavant.
4. Aspectes de desenvolupament i implementació
L’arbre es muntat a partir d’un
pròxima secció. Aquest algorisme retorna un conjunt de clústers que nosaltres
anomenem entries, i que s’agrupen en nodes. Aquests nodes s’enllacen, a partir de
les distàncies entre ells formant l’arbre final.
Així doncs, l’arbre queda estructurat de la següent manera: e
emmagatzemen tots els objectes indexats (bd), representats per les seves claus o
característiques, mentre que els nodes interns emmagatzemen els
que són objectes de base d
mitjà d’un algoritme de promoció específic.
4.3- Clustering: dendrograma
El procés de creació del dendrograma es resumirà de forma esquemàtica en la
figura següent:
Figura 19: gràfic esquemàtic del procés de creació del dendrograma.
El primer que s’ha fet és calcular la distància del grafs de tots amb tots. Per a fer
això, s’ha creat una matriu de NxN, on N és el nombre de grafs fulla
•Matriu de Grafs
pdistGrafs
Vector de distàncies de tots amb tots
4. Aspectes de desenvolupament i implementació
a partir d’un algorisme de clústering que serà explicat en la
pròxima secció. Aquest algorisme retorna un conjunt de clústers que nosaltres
, i que s’agrupen en nodes. Aquests nodes s’enllacen, a partir de
les distàncies entre ells formant l’arbre final.
cs, l’arbre queda estructurat de la següent manera: e
emmagatzemen tots els objectes indexats (bd), representats per les seves claus o
característiques, mentre que els nodes interns emmagatzemen els
que són objectes de base de dades als quals se’ls assigna un rol d’enrutament per
mitjà d’un algoritme de promoció específic.
ing: dendrograma
El procés de creació del dendrograma es resumirà de forma esquemàtica en la
: gràfic esquemàtic del procés de creació del dendrograma.
El primer que s’ha fet és calcular la distància del grafs de tots amb tots. Per a fer
això, s’ha creat una matriu de NxN, on N és el nombre de grafs fulla
•Algorisme de
clustering
•'single'
linkage•Dibuixa
l'arbre
dendrogram
Vector de distàncies de tots amb tots
Taula amb tots els clústers i la distància entre ells
46
que serà explicat en la
pròxima secció. Aquest algorisme retorna un conjunt de clústers que nosaltres
, i que s’agrupen en nodes. Aquests nodes s’enllacen, a partir de
cs, l’arbre queda estructurat de la següent manera: els nodes fulla
emmagatzemen tots els objectes indexats (bd), representats per les seves claus o
routing objects,
e dades als quals se’ls assigna un rol d’enrutament per
El procés de creació del dendrograma es resumirà de forma esquemàtica en la
: gràfic esquemàtic del procés de creació del dendrograma.
El primer que s’ha fet és calcular la distància del grafs de tots amb tots. Per a fer
això, s’ha creat una matriu de NxN, on N és el nombre de grafs fulla que tindrà
Dibuixa
dendrogram
Taula amb tots els clústers i la distància entre ells
4. Aspectes de desenvolupament i implementació
47
l’arbre. La diagonal d’aquesta matriu serà, òbviament, zero ja que la distància entre
un graf amb ell mateix és zero. Per tal de millorar l’eficiència d’aquest algorisme,
s’ha calculat només la diagonal superior, ja que la matriu és simètrica. En aquest
pas s’han guardat dues variables: aquesta matriu, i la mateixa matriu en forma de
vector, ja que és el paràmetre que es necessita per al següent pas. La matriu serà
reutilitzada posteriorment per a estalviar càlculs de distàncies entre grafs ja
existents, no servirà en el cas dels prototips, augmentant notablement la velocitat
de càlcul de tot el procés. Aquesta part de l’algorisme de clustering l’anomenarem
pdistGrafs.
El següent pas consisteix en agafar les distàncies mínimes per a fer el clústers. Això
es fa mitjançant la funció linkage() proporcionada per Matlab.
Z = LINKAGE(Y, METHOD) crea un arbre de clústers jeràrquic utilitzant un
algoritme específic. Els mètodes disponibles són:
� 'single' : distància més propera;
� 'complete' : distància més llunyana;
� ‘average': distància mitjana no ponderada o mitjana del grup
(UPGMA: unweighted average distance)
� 'weighted': distància mitjana ponderada
� (WPGMA: weighted average distance)
� 'centroid': distància de centre de masses no ponderada
(UPGMC: unweighted center of mass distance)
� 'median’:distància ponderada de centre de masses
(WPGMC: weighted center of mass distance)
� 'ward': (inner squared distance) algorisme de variància mínima
Després d’analitzar totes les opcions i fer diversos testos a mà i sobre el paper
mitjançant exemples 2D, i comparar-los amb els resultats extrets per aquesta
funció s’ha decidit escollir la primera opció: ‘single’.
La informació dels clústers es retorna com una matriu Z amb mida m-1 per 3, on m
és el nombre d'observacions de les dades originals. Les columnes 1 i 2 de Z
contenen índexs de clúster enllaçats en parelles per formar un arbre binari. Els
nodes fulla estan numerats de 1 a m. Aquests són els grups solitaris dels quals es
4. Aspectes de desenvolupament i implementació
48
construeixen totes les grans agrupacions. A cada grup acabat de formar, que
corresponent a la Z (i,:), se li assigna l'índex m + i, on m és el nombre total de
fulles inicial. Z (i, 1:2) conté els índexs dels dos grups de components que el clúster
m+i. Hi ha m-1 clústers de més amunt que corresponen als nodes interiors de
l’arbre de clustering de sortida. Z (i, 3), conté les distàncies d'enllaç corresponents
entre els dos grups que es fusionen en Z (i,:), per exemple, si hi ha un total de 30
nodes inicials, i en el pas 12, el grup 5 i el grup 7 es combinen i la seva distància en
aquest moment és d’1,5, aleshores la fila 12 de Z serà (5,7,1.5). L'agrupació
acabada de formar tindrà un índex de 12 +30 = 42. Si la mostra de clúster 42 a
una fila d'aquest últim, el que significa aquest grup acabat de formar es combina de
nou en alguns més grans del clúster.
El tercer i últim pas és dibuixar el dendrograma. Aquesta acció es fa a través de la
funció dendrogram(Z) que també incorpora Matlab. Aquesta funció genera una
imatge del clúster binari jeràrquic creat per la funció anterior. El dendrograma
consisteix en diverses línies que connecten els objectes en un arbre jeràrquic.
L’alçada de cada clúster representa la distància entre els dos objectes que s’estan
connectant.
Es poden utilitzar diversos paràmetres per retornar la informació creada per
aquesta funció, però no ha estat necessari ja que només s’ha utilitzat la impressió
com a mode per adquirir informació i estudiar els resultats obtinguts. Per millorar la
visibilitat de la imatge i ajudar a comprendre-la millor, existeix el paràmetre
('COLORTHRESHOLD',T), que assigna un color únic a cada grup de nodes que es
vinculen per sota del valor escalar T on T és en el rang de 0 <t <max(Z(:,3)). Si T
és menor o igual a zero o si T és més gran que la vinculació màxima llavors el
dendrograma s'elaborarà utilitzant un sol color. T també es pot establir en 'default'
en aquest cas el llindar s'estableix en el 70% de la vinculació és a dir, màxim 0,7 *
Max (Z (:, 3)). En la següent figura es veurà la utilització d’aquest paràmetre per
tal de representar els 3 límits aplicats a un dendrograma per a construir un arbre
d’exemple.
4. Aspectes de desenvolupament i implementació
49
Figura 20 exemple de procés de clustering en tres passos. La primera imatge mostra els
clústers creats amb límits 0-4. La segona amb límits de 4-8. La tercera amb límits 8-10.
4. Aspectes de desenvolupament i implementació
50
4.4- Representant smallest SOD (sum of distances)
Per tal d’implementar aquest punt, s’han agafat tots els nodes que formen un
clúster, en temps de creació de l’arbre, i s’ha calculat la matriu de distància de tots
amb tots. Un cop calculada la matriu de NxN, sent N el nombre de grafs que formen
el clúster, s’ha escollit el node que te la suma mínima de distàncies entre ell i la
resta dels elements del clúster.
4.5- Prototips: Median Graph
Per tal de calcular el Median Graph de dos grafs g1 i g2, s’ha calculat la distància i el
camí d’edició entre ells. S’ha buscat un graf que estigui a la mateixa distància de g1
que de g2, és a dir, que si la distància entre g1 i g2 la és d, la del MG a g2 sigui d/2.
Fig. 21. Exemple gràfic de la idea del càlcul del Median Graph.
d
d/2
4. Aspectes de desenvolupament i implementació
51
El MG es va calculant, com ja s’ha dit anteriorment, mitjançant l’addició de
distorsions al graf font g1. Les distorsions a afegir venen donades pel camí d’edició.
Així doncs, a cada pas del camí, s’aplica una nova distorsió del camí d’edició al MG
actual (agafant com a primer median g1), es forma un nou MG i es calcula la
distància d’aquest nou graf al graf destí d(MG,g2). Es repeteix aquesta seqüència
fins que d(MG,g2) < d/2.
Com que al realitzar el clustering mitjançant el dendrograma, ens pot agrupar més
de dos grafs en un mateix clúster, s’ha decidit agafar els grafs de dos en dos i anar
realitzant el Median Graph d’aquests (G1 i G2) que seria M G12. En el següent pas
s’agafa el següent graf del clúster (G3), i es calcula el Median Graph d’aquest MG12
amb el G3 i així successivament, amb el que aconseguim el Median Graph del
conjunt.
Figura 23: càlcul de MGs en un clúster de grafs. Els cercles representen nodes i els triangles
els Median Grafs. Primer es calcula el median groc (G1,G2), i desprès el vermell (MG12,G2).
Figura 22: exemple de com crear el Median Graph entre 2 grafs. G1 és el graf font i G2 és
el grafs destí. Els Cn són els canvis o distorsions que apliquem al graf font per a fer el
Median Graf fins que la distancia d(MG,g2) < d/2.
d(MG,g2) < d/2?
No No No Si
MG1 MG2 MG3 MG(G1,G2)=MG4
C1 C2 C3 C4
G1 G2
G1
G2
G3 MG12 = MG(G1,G2)
MG123 = MG(MG12,G2)
4. Aspectes de desenvolupament i implementació
52
4.6- Cerca
En aquesta secció s’explicarà com s`ha realitzat la cerca: els paràmetres analitzats,
els casos possibles que es pot trobar l’algorisme, els problemes trobats i les
solucions proposades.
En el punt “3.6- Cerca” s’ha realitzat un petit esbós de com es portarà terme
aquesta secció. A continuació s’aprofundirà en aquest procés, en un nivell més alt
de detall i molt més enfocat a la programació realitzada, sense perdre mai de vista
els conceptes teòrics.
Sent:
• Q el graf que volem cercar;
• D un graf que està en la base de dades;
• µMAX el que nosaltres anomenarem tolerància, el radi o rang de la cerca que
tindrà el graf Q;
• µD radi que ens dona una distància límit entre D i qualsevol graf. En els
nodes fulla, tindrem µD = 0;
Tenim 3 casos possibles:
1) Cap graf de l’arrel subD és acceptable si:
a� µ�Q, D� a µbcd e µf b� µ�Q, D� g µbcd e µf
Amb la qual cosa el graf Q està fora de la covering region de D i mai no estarà
situat sota l’arrel subD tal i com es mostra en la següent figura. Val a dir que al
principi s’utilitzava la desigualtat a) i al final ens hem quedat amb la desigualtat b)
recoberta amb el rectangle, que és la mateixa que la anterior però canviant el a per
> ja que, si només volem trobar, o altrament dit, fer matching amb l’element
exacte posem la tolerància µMAX = 0 i estem buscant en un node fulla (on el radi µD
= 0), l’algorisme de cerca entraria en aquesta desigualtat erròniament, perquè
estaríem dient que no és acceptable quan, en realitat, el graf és exactament igual i
fa match.
4. Aspectes de desenvolupament i implementació
53
Figura 24: Efecte µ en el càlcul de distància entre dos grafs Q és el graf que s’està cercant i
D és un graf qualsevol en l’espai. En aquest cas no s’accepta ni el graf D ni la resta dels seus
fills perquè estan fora de l’abast de la query.
2) Tots els ARGs en subD són acceptables si:
µ�Q, D� ] µbcd h µf
Es a dir, que tots els grafs pertanyents a la covering region de D, es a dir, els fills,
també estaran continguts en el conjunt de punts que forma el cercle Q amb radi
µMAX.
Figura 25: Efecte µ en el càlcul de distància entre dos grafs Q és el graf que s’està cercant i
D és un graf qualsevol en l’espai. En aquest cas s’accepta el graf D i el conjunt sencer dels
seus fills perquè estan tots dintre de l’abast de la query.
Q
µ (Q,D)
µD
D
µMAX
Q
µD
µ (Q,D)
µMAX
D
4. Aspectes de desenvolupament i implementació
54
3) En el cas crític que cap de les dues desigualtats anteriors es compleixi, la
covering region de D conté grafs acceptables i no acceptables, per la qual cosa la
cerca s’ha de repetir en els subíndex subD. Dit d’una altra manera, s’han d’explorar
els fills de l’arbre actual per tal d’afinar més.
Figura 26: Efecte µ en el càlcul de distància entre dos grafs Q és el graf que s’està cercant i
D és un graf qualsevol en l’espai. En aquests casos s’han de continuar explorant els fills de D
perquè estan dintre de l’abast de la query tot i que el graf D no hi sigui.
S’ha comprovat matemàticament que si tenim un node fulla (µD = 0) i busquem el
graf exacte (µMAX = 0, sense tolerància), només pot entrar en (a) o (b) però no a
les 2 alhora. Posteriorment s’ha comprovat directament amb el programa posant un
if > i un else <= per la qual cosa ja serà excloent. S’ha provat amb diversos
exemples i s’ha comprovat com veritablement no s’entra en la inequació a)
mitjançant el retorn del vector d’acceptats torna l’objecte que toca i no pas el
descarta. Malgrat tot s’ha confirmat amb el debugger, que quan arriba a la
inequació 0 > 0+0 passa de llarg fins a la segona on 0<=0 + 0.
S’ha comprovat el retorns de punts mentre es va canviant (augmentant per a veure
l’efecte als radis) la tolerància µMAX. En un exemple 2D amb 39 objectes i emplaçant
el punt Q de cerca al centre de l’espai, s’ha començat amb µMAX = 0 fins a µMAX = 50
Q
µMAX
µ (Q,D)
µD
D Q
µMAX
µ (Q,D)
µD
D
1 2
4. Aspectes de desenvolupament i implementació
55
Figura 27: gràfica d’exemple de la resposta de la cerca (quant al nombre d’acceptats)
reaccionant a l’increment lineal de µMAX. La distància màxima entre elements que formen
aquest espai és 60 i el punt Q s’ha posicionat en el centre de tots els punts de l’espai. Es pot
comprovar que ja quan el radi de cerca és 30, es a dir, la meitat de la distància més gran, ja
accepta tots els grafs de l’espai.
Un aspecte que es realitza en temps de creació de l’arbre però que afecta
directament a la cerc, és el càlcul dels radis dels routing objects que s’explicarà tot
seguit.
Per a calcular els radis de cada routing object, al principi es va decidir agafar com a
radi la distància entre el centre (pare) i el fill més llunyà. Però ràpidament es va
veure com hi havia un problema de “zones mortes” quan el radi dels fills quedava
fora de l’abast dels pares com es mostra en la següent figura:
0 0
4
12
24
34
39 39 39 39 39
0
5
10
15
20
25
30
35
40
0 5 10 15 20 25 30 35 40 45 50
Nu
me
ro d
'Acc
ep
tats
µ MAX
(25,17)
4. Aspectes de desenvolupament i implementació
56
Zona morta Area amb rang de cerca de G
Figura 28. Zona morta al calcular de manera errònia el covering radi. A és el pare, D el fill, i Q
un objecte de cerca en la zona morta.
Si explorem aquesta part de l’arbre, cercant un graf Q amb rang de cerca µbcd en
qualsevol punt de la zona morta, mirem si, en relació a A, compleix µ�Q, D� g µbcd eµf ho compleix, per tant descarta tots els fills de A, deixant-se per explorar la zona
morta on pot trobar grafs que estiguin dins del rang de cerca µbcd.
Per a solucionar aquest problema s’ha decidit que, partint de la base que la solució
no pot ser la distància màxima de l’arrel A als nodes fulla F, perquè aquest F podria
estar entre A i B (pare d’C i fill d’A) i d’aquesta manera i erròniament, el radi de A
seria petit i descartaria al seu fill B i molts dels seus possibles fills:
Figura 29.A és el pare, B és fill d’A i C és fill de B. Aquesta figura mostra perquè no es pot
calcular el radi de A com la distància entre ell i els fulla. Molta àrea del graf B quedaria
descartada.
C
µD
B A
µD
D A
µA
Q
4. Aspectes de desenvolupament i implementació
57
Aleshores tenim:
A/µ A’ A’’
B/µ B’/µ B’’/µ
C/µ C’/µ C’’/µ
Figura 30: exemple gràfic de com calcular els radis
I ara si que s’ha eliminat aquest problema com es mostra en la figura següent:
Fig 31. Error de zona morta al calcular el covering radii corregit amb èxit.
Hem comprovat que no si hi ha routing objects repetits dintre de la mateixa taula,
per exemple t(15) = (2,1), t(24) = (2,1) en 2D, els trobi els dos. Efectivament la
cerca dóna com a resultat que els 2 elements repetits són trobats correctament.
També s’ha tingut en compte tractar els nodes NO fulla si:
µ(Q,D)
µD
A
c
S’ha de buscar el màxim en tots
els fills calculant:
MAX(distància entre pare i fill +
radi d’aquest fill)
µA = MAX( d(A, B) + µB)
sent µ el radi de cada entry.
µ (A,B)
µB(MAX)
4. Aspectes de desenvolupament i implementació
58
μf ] μ�Q, D� ] μbcd
µMAX
]
µ (Q,D)
]
µD
Figura 32: la distància entre Q i D està entre la µMAX i el radi de cerca
Però aquesta inequació presenta un problema quan el radi de D és més gran que el
rang de cerca, ja que seria impossible que es compleixi la condició anterior:
Figura 33: problema quan el radi és més gran que el rang de cerca
Per tant s’ha de modificar la inequació, que finalment queda així, ja que, quan no
depèn de µf, accepta tots dos casos: μ�Q, D� ] μbcd
Ara si doncs, l’algorisme implementat té en compte tots els casos descrits en
aquest punt.
µD
D µMAX
Q
µ (Q,D)
D
µ (Q,D)
µMAX
µD
Q
5. Avaluació del sistema desenvolupat, comparació amb altres alternatives
59
5. Avaluació del sistema desenvolupat, comparació amb altres
alternatives
En aquest punt es descriuran els testos realitzats tant en el sistema inicial com en
el nou sistema desenvolupat per tal de poder comparar-los i extreure’n conclusions.
Els testos s’han realitzat en una màquina: Pentium 4 amb CPU 2.00 GHz del
laboratori 143, en el campus Sescelades de l’ETSE (URV). S’han realitzat sota els
entorns Matlab i Java, amb l’editor Eclipse. S’ha escollit Matlab per la seva potència
de càlcul amb elements matemàtics, i perquè és un dels llenguatges més utilitzats
en el camp que estem tractant. La raó d’escollir Java va ser perquè l’algorisme de
càlcul de distàncies i camins d’edició estava desenvolupat en aquest llenguatge. Per
tal de fer testos raonablement grans en aquesta màquina s’ha hagut de disminuir la
precisió del càlcul de la distància d’edició, del camí d’edició i del Median Graph.
Podem assegurar que l’estructura d’ambdós arbres és la mateixa perquè, a part de
només canviar el routing object promocionat, s’han realitzat testos que retornaven
la mitjana de numero de fills per node. S’han comparat totes les dades extretes
d’aquest test i la diferència entre totes elles era 0, pel que els 2 arbres tenien el
mateix nombre de nodes per arbre i el mateix nombre d’elements per node.
Per a fer els testos, s’han creat 15x4x3 = 180 arbres de cada tipus (representants i
prototips), o sigui, un total de 180x2 = 360 arbres. Els nombres utilitzats per
aquest càlcul es refereixen a:
• 15: nombre de classes que formen la base de dades (explicat amb detall al
pròxim punt);
• 4: nombre de les diferents particions que se li faran al dendrograma per tal
d’organitzar els clústers. Aquestes particions el dividiran en 4, 7, 10 i 12
parts de la mateixa mida. D’aquesta manera es veurà l’efecte del sistema
ideat segons com estigui muntat l’arbre.
• 3: nombre d’elements fulla utilitzats per a crear l’arbre. Crearem arbres de
15, 30 i 50 grafs fulla. Recordem que posteriorment el nombre de grafs que
formaran l’arbre es veurà augmentat degut a les promocions.
5. Avaluació del sistema desenvolupat, comparació amb altres alternatives
60
5.1- La base de dades.
Abans de definir i explicar els testos realitzats, es farà una breu explicació sobre el
conjunt de bases de dades del test trainDataLetterHIGH.m [8].
Aquesta base de dades la formen 15 classes. Cada classe correspon a una lletra. El
perquè de que siguin 15 és degut a que només tenim les lletres formades per
traçades rectes sense cap ni una corba, es a dir, tenim lletres com A, E, F... i no en
tenim cap de l’estil de O,P,S...
Índex: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Lletra A E F H I K L M N T V W X Y Z
Nodes 5 6 5 6 2 5 3 5 4 4 3 5 5 4 6
Arestes 4 5 4 5 1 4 2 3 3 3 2 4 4 3 5
Taula 1: classes que formen la base de dades trainDataLetterHIGH.m
Els nodes i arestes de la taula anterior corresponen a una lletra escrita
perfectament, però com es veu en la figura següent, no ha de ser sempre així, ja
que les lletres han estat escrites a mà i passades a grafs per un programa
especialitzat en aquesta funció i, com ja sabem, no s’escriu sempre de la mateixa
manera. Per a que les lletres siguin una mica més diferents, s’ha exagerat la
diferència d’escriptura.
Figura 34: exemple de grafs de la base de dades trainDataLetterHIGH.m.
Exemples del conjunt de lletres A.
5. Avaluació del sistema desenvolupat, comparació amb altres alternatives
61
Cada classe esta formada per 150 elements dividits en 3 grups de 50 elements per
grup, on cada element correspon a un graf. Aquests grups són:
• 50 Aprenentatge
• 50 Entrenament
• 50 Test
5.2- Anàlisi de l’arbre: el factor solapament
Un cop definit el concepte de solapament, ens disposem a explicar els testos
realitzats, mostrar els resultats en forma de gràfiques de barres i a comentar-ne els
resultats.
S’han realitzat aquests càlculs a tots i cadascun dels 360 arbres creats. S’han desat
els resultats en una matriu de 15X4X3 i se n’ha fet la mitjana de la dimensió de les
classes (la de 15), per tal de poder-ne tenir una representació gràfica.
En la figura següent veurem ambdues gràfiques del solapament dels representants i
dels prototips respectivament. En aquestes gràfiques es veu que com més
compacte és l’algorisme de clustering més es redueix el solapament al utilitzar els
prototips. Un factor estrany és que decreixi aquest solapament a mesura que
augmenta el nombre de nodes fulla. Aquest fet es pot atribuir a que, al haver-hi
més elements, l’algorisme de clustering te més opcions on triar, i augmenta el seu
rendiment.
Figura 35: Solapament del representant i prototips. El càlcul del solapament és la mitja dels testos realitzats a les 15 lletres.
5. Avaluació del sistema desenvolupat, comparació amb altres alternatives
En la figura anterior s’intueix un decreixement general del solapament
amb prototips respecte als arbres amb representants
diferència entre els dos. Per tal de
la gràfica de la divisió del solapament dels arbres formats per representants per la
dels formats pels prototips
Figura 36: divisió
Sembla ser que a mesura que augmenten les particions, el nombre de germans
també augmenta i aleshores, és normal que el solapament també augmenti. A més
s’intueix que a mesura que s’incrementa el nombre d’elements fulla, disminueix el
nombre de germans, reduint també el solapament. Això creiem que es deu al fet
que augmenta la probabilitat d’ajuntar grafs en el moment de fer el clúster,
repartint l’arbre de manera més justa.
Per tal d’extreure més dades concloents
estàndard del solapament
funció STD que incorpora Matlab
veure que el solapament dels arbres amb prototips té menys desviació, per tant,
junt amb els resultats de Figura 35 concloem que la representació de l’arbre amb
prototips és més eficaç que amb representants.
1012
So
lap
am
en
t
Numero Particions Dendrograma
Solapament Representant/Solapament Prototipus
Avaluació del sistema desenvolupat, comparació amb altres alternatives
ior s’intueix un decreixement general del solapament
respecte als arbres amb representants, però és difícil d’apreciar la
diferència entre els dos. Per tal de solucionar aquest problema, s’ha decidit realitzar
la gràfica de la divisió del solapament dels arbres formats per representants per la
prototips, donant el següent resultat:
divisió del solapament dels representants i dels prototips
Sembla ser que a mesura que augmenten les particions, el nombre de germans
també augmenta i aleshores, és normal que el solapament també augmenti. A més
s’intueix que a mesura que s’incrementa el nombre d’elements fulla, disminueix el
germans, reduint també el solapament. Això creiem que es deu al fet
que augmenta la probabilitat d’ajuntar grafs en el moment de fer el clúster,
repartint l’arbre de manera més justa.
Per tal d’extreure més dades concloents es va decidir analitzar la des
del solapament entre els dos tipus d’arbres. Això es va fer
funció STD que incorpora Matlab a les dades anteriors. En la figura següent es pot
que el solapament dels arbres amb prototips té menys desviació, per tant,
amb els resultats de Figura 35 concloem que la representació de l’arbre amb
que amb representants.
15
30
50
0
0,1
0,2
0,3
0,4
0,5
47
nElemsFulla
Numero Particions Dendrograma
Solapament Representant/Solapament Prototipus
Avaluació del sistema desenvolupat, comparació amb altres alternatives
62
ior s’intueix un decreixement general del solapament dels arbres
, però és difícil d’apreciar la
solucionar aquest problema, s’ha decidit realitzar
la gràfica de la divisió del solapament dels arbres formats per representants per la
prototips.
Sembla ser que a mesura que augmenten les particions, el nombre de germans
també augmenta i aleshores, és normal que el solapament també augmenti. A més
s’intueix que a mesura que s’incrementa el nombre d’elements fulla, disminueix el
germans, reduint també el solapament. Això creiem que es deu al fet
que augmenta la probabilitat d’ajuntar grafs en el moment de fer el clúster,
es va decidir analitzar la desviació
dos tipus d’arbres. Això es va fer aplicant la
En la figura següent es pot
que el solapament dels arbres amb prototips té menys desviació, per tant,
amb els resultats de Figura 35 concloem que la representació de l’arbre amb
0,1
0,2
0,3
0,4
0,5
nElemsFulla
Solapament Representant/Solapament Prototipus
5. Avaluació del sistema desenvolupat, comparació amb altres alternatives
63
Figura 37: resta del solapament dels representants i dels prototips.
5.2 Anàlisi de la cerca: nombre d’accessos
El nombre d’accessos és una variable que s’incrementa cada cop que es realitza un
càlcul de distància entre grafs en temps de cerca. Aquesta variable ens indica el
numero de càlculs que s’han de fer abans no s’acaba la cerca.
Aquest nombre pot portar a conclusions errònies en certes ocasions, perquè pot
donar més elevat que el nombre d’elements. Això és degut a que el nombre
d’elements es refereix al numero d’elements fulla que hi ha a l’arbre. Com ja s’ha
explicat, al crear aquest arbre, es fan promocions de grafs (tant Set Medians com
Graph Medians), a partir de les fulles, per tal que exerceixin com a nodes
enrutadors (routing objects). En el moment de crear un prototips i promocionar-lo
(fer-lo pare del node format pels entries que s’han utilitzat per crear-lo) i en el de
promocionar un Set Median (recordem que en aquest moment es copia el mateix
routing object), estem augmentant el nombre d’entries que formaran l’arbre i, en
conseqüència, el nombre d’accessos que es poden fer per a trobar un graf dins
d’aquest arbre.
Si això passa, deixa el nostre sistema en evidència, ja que seria més eficient tenir
els elements en una taula y cercar un los mitjançant un recorregut. Per sort, el
nostre sistema normalment no ho fa, tot i que no es pot assegurar que no ho faci
mai.
Descripció dels testos realitzats:
5. Avaluació del sistema desenvolupat, comparació amb altres alternatives
64
• Test 1: cerca 3 elements dels que formen l’arbre.
• Test 2: cerca 3 elements dels que estan a la mateixa classe però fora de
l’arbre.
• Test 3: cerca 3 elements que no pertanyen a la classe utilitzada per a crear
l’arbre.
Figura 38: Exemple gràfic de les consultes realitzades. En la primera filera de taules s’està
consultant els elements de la classe 1 que pertanyen al test (Test 1). En la segona filera els
elements de la classe 1 que no formen part de l’arbre. No els trobarà però la distància serà
relativament petita (Test 2). En la tercera s’agafen elements d’una altra classe, on la
distància serà més gran (Test 3).
Aquestes 9 operacions s’han realitzat per a tots els arbres creats (360) i per a cada
arbre amb 3 radis de cerca (µMAX) diferents. Els radis de cerca s’han calculat dividint
la distància entre els 2 elements més allunyats de l’arbre. Per a fer aquesta divisió
s’han escollit tres valors diferents: 2, 4 i 8. Aquesta µMAX s’aplicarà a cada graf Q
que vulguem cercar.
Figura 39: mostra de com es selecciona la µMAX. El node en blau marca l’inici i el vermell el
final. Les 3 µMAX diferents van del node blau fins a caddascuna de les 3 particions marcades.
C1
C1
C1
C2
C2
C2
#ElemsTest
|
DMAX/2 |
DMAX/4 |
DMAX/8
µ
5. Avaluació del sistema desenvolupat, comparació amb altres alternatives
65
Per adonar-nos de la gran càrrega computacional que han suposat aquests testos,
mostrarem algunes xifres:
360 arbres x 9 queries x 3 µMAX =9720 testos
Tenint en compte que cada arbre esta format per un munt de grafs i que els grafs
tenen una mitja de 5 nodes i 4 arestes, s’han de calcular diverses distàncies i
camins d’edició. Cal remarcar que com més nodes i més arestes, més costós serà
de calcular.
Així doncs, cada un d’aquests 9720 testos tindrà un cost bastant elevat tot i no
utilitzar l’algorisme òptim.
5. Avaluació del sistema desenvolupat, comparació amb altres alternatives
66
5.3. Incidència de µMax
Com més gran sigui aquest factor sembla ser que més accessos hauria d’haver-hi,
però no ha de ser així forçosament. L’explicació recau en l’algorisme de cerca, ja
que en radis de cerca grans, totes les distàncies (d(Q,D) + RadiD) seran més petites
que el radi de cerca µMAX, complint així la condició 2) del punt “4.6. Cerca”, i
acceptant així tots els fills d’un entry amb un únic càlcul de distància, realitzat en
d(Q,D). En la següent figura es veurà la diferència entre la situació acabada
d’esmentar i una en la que el radi de cerca és més petit i ha de fer 3 càlculs de
distàncies.
a) b)
Figura 40:explicació visual de com influeix la el radi de
cerca en el nombre total de càlculs realitzats
a) µMAX petita: 3 càlculs per a acceptar 3 nodes
b) µMAX gran: 1 càlcul per acceptar 3 nodes
En la figura 40a) l’algorisme de cerca escolliria la tercera opció, explorar tots els
fills, ja que ni s’han de descartar, ja que pot ser que n’hi hagi dintre del radi de
cerca i la covering region de D, ni s’han d’acceptar tots, per la explicació feta en el
paràgraf anterior. Aleshores s’haurien de calcular 3 distàncies per tal de mirar si
entren dins al radi de cerca i decidir si s’accepten o no. En canvi, en la 39b), i com
s’ha explicat abans, en un càlcul de distància s’acceptarien els 3 sense cap
necessitat de calcular la resta de distàncies. Cal remarcar que aquests fills poden
tenir més fills i la poda pot disminuir encara més aquest nombre de càlculs.
Q
D
Q
D
5. Avaluació del sistema desenvolupat, comparació amb altres alternatives
67
5.3.1-Mumax = (dMax(matriu_distancies_tots_amb_tots))/2
Figura 41: nombre d’càlculs de distància fets en els tests per als representants i per als
prototips.
Figura 42: percentatge d’estalvi de càlculs de distància fets en els tests per als representants
i per als prototips. En la primera figura es mostren els càlculs fets
5. Avaluació del sistema desenvolupat, comparació amb altres alternatives
68
5.3.2- Mumax = (dMax(matriu_distancies_tots_amb_tots))/4
Figura 43: nombre d’càlculs de distància fets en els tests per als representants i per als
prototips.
Figura 44: percentatge d’estalvi de càlculs de distància fets en els tests per als representants
i per als prototips. En la primera figura es mostren els càlculs fets
5. Avaluació del sistema desenvolupat, comparació amb altres alternatives
69
5.3.3- Mumax = (dMax(matriu_distancies_tots_amb_tots))/8
Figura 45: nombre d’càlculs de distància fets en els tests per als representants i per als
prototips.
Figura 46: percentatge d’estalvi de càlculs de distància fets en els tests per als representants
i per als prototips. En la primera figura es mostren els càlculs fets
5. Avaluació del sistema desenvolupat, comparació amb altres alternatives
70
Les gràfiques anteriors s’han realitzat agafant el nombre d’accessos realitzats, i
dividint-lo pel nombre d’elements fulla utilitzats en cada cas per construir l’arbre.
Això ho hem fet per a veure quin percentatge d’accessos fem menys que si es
recorregués l’arbre de manera seqüencial. D’aquesta manera es pot veure que en
alguns casos, muntar l’arbre amb representants com s’ha fet, pot arribar a ser
pitjor que en seqüencial, tot i que això no passa sempre. Al crear-lo amb prototips
aquest factor no supera mai el 100% d’elements fulla. És més, comparant els
arbres amb prototips, veiem un estalvi d’accessos entre el 10% i el 20% dels
accessos. Per analitzar els resultats, ens fixarem bàsicament en les columnes dels
arbres formats per 50 elements fulla.
També observem que, com sembla evident, com més elements fulla hi ha a l’arbre,
més accessos es fan.
D’altra banda, el nombre de particions sembla no influir tant com s’esperava
inicialment.
S’observa que el representant no escala massa bé , pel que no valdria la pena
utilitzar-lo quant es pot recórrer la taula seqüencialment més ràpidament.
5.4- Altres factors amb influència sobre els testos
Els factors analitzats en aquest treball no són els únics que influeixen en la millora
de l’aspecte de la cerca. La complexitat de les variables analitzades i el cost de fer
els testos, ha fet impossible dur a terme aquesta anàlisi. D’haver-ho intentat,
s’haurien ampliat les proporcions d’aquest treball de manera exagerada, requerint
així, un temps de dedicació i de computació molt elevats.
En aquest punt es comentaran alguns d’aquests altres factors, i se’n analitzaran les
possibles causes i/o conseqüències.
El primer i un dels més importants són les particions del dendrograma creant
clústers en el moment de crear l’arbre. Com ja s’ha explicat, aquestes divisions en
el factor de solapament i, de retruc, en el moment de fer consultes. Per a realitzar
questa acció, s’han hagut d’escollir uns límits genèrics, cosa que és molt difícil tant
d’escollir com de ser just amb el conjunt de clústers, que associïn tots els grafs de
manera equitativa.
5. Avaluació del sistema desenvolupat, comparació amb altres alternatives
71
La precisió en el càlcul de la distància i del Median Graph també influeix. S’han
realitzat els testos amb el paràmetre astarDeep de l’arxiu ‘median.prop‘ amb el
paràmetre a 10 (recordem que -1 significa infinit, es a dir, algorisme òptim i com
aquest numero sigui més gran, més òptim serà el resultat). Així doncs tenim els
càlculs subòptims, que disminueixen el temps dels testos i permeten treballar amb
un nombre elevat de grafs, i que aquests siguin més complexos, és a dir, que
tinguessin més nodes i arestes.
En un principi s’havia intentat amb el paràmetre a -1 i s’ha comprovat com els
resultats milloraven però, com a contrapartida, calcular distàncies i, en
conseqüència, medians, tenia un cost molt més elevat, i això afectava a l’algorisme
sencer. Per tal de reduir aquest cost i demostrar els nostres objectius de manera
pràctica, es va buscar utilitzar trade-off entre velocitat de càlcul i precisió, abans
esmentat. Aquest paràmetre ens el va facilitar el mateix desenvolupador de
l’algorisme de càlcul de distàncies i medians [5] i [6], ja que va ser ell mateix qui
va testejar aquest rendiment.
Amb tot això podem veure com els resultats no seran tant bons com es pot esperar
ja que el MG no serà l’òptim, i això farà que els radis augmentin i, en cascada, els
les covering region, els solapaments i el nombre de càlculs de distància a realitzar
en temps de cerca, que aquí hem anomenat nombre d’accessos.
Fent referència a la figura 14 de la secció “3.5-. Prototips Median Graph”, en la que
es mostrava un exemple en la que es comparava el solapament de dos clústers
amb el Set Median com a representant i un altre amb els mateixos clústers amb el
Median Graph com a representant del clúster, a la figura següent es pot veure com
la diferència ja no és tant gran al ser el Median Graph no òptim.
5. Avaluació del sistema desenvolupat, comparació amb altres alternatives
72
Figura 47: mostra d’augment del radi si el Median Graph no és l’òptim
Aquest desplaçament del centre pot donar, en el pitjor dels casos de l’exemple
anterior, un augment enorme del radi que produeixi solapament, com es veurà en
la següent figura:
5. Avaluació del sistema desenvolupat, comparació amb altres alternatives
73
b) Median graph zona d’error
Figura 48: ampliació del radi del prototips degud
a a la disminució de precisió del Median Graph.
6. Conclusions, treball futur
74
6. Conclusions, treball futur
En l’estudi realitzat s’ha intentat avaluar les característiques de l’arbre generat amb
prototips i amb representats com també rendiment en la realització de cerques.
Des del punt de vista de l’estructura generada en l’arbre els resultats obtinguts
conclouen una reducció de prop d’un 25% del solapament, cosa que ens indica que
l’arbre forma un estructura més equilibrada on els clústers tenen una separació
més equidistant.
Referent a l’avaluació en la realització de les consultes podem concloure que s’ha
reduït el nombre d’accessos entre un 10 i un 20% de mitjana. Aquest valor s’ha
extret al comparar les dues gràfiques d’accessos tant de l’arbre amb representants
com de l’arbre amb prototips. Cal remarcar que, en algun cas concret, el nombre
d’accessos que es fa en l’arbre amb representants supera en mitjana el nombre
d’elements utilitzats per a crear l’arbre, del qual és pot deduir que usar un arbre en
representats no suposa cap benefici. En canvi, en l’arbre creat amb prototips és
supera en cap cas aquest límit, sinó que sempre és redueix el nombre d’accessos.
Un paràmetre molt important en la realització de les consultes és el valor µmax. De
l’estudi realitzat per diferents valors d’aquest paràmetre µmax s’esperava veure la
influencia en el nombre d’accessos realitzats al llarg de l’arbre donada una consulta
determinada, ja que com més petit és el radi de la consulta (valor més petit de
µmax) més dirigida aquesta a un element en concret. En canvi l’avaluació d’aquest
paràmetre demostra que aquest radi només influeix lleugerament en la mitjana
d’accessos per cerca.
Quant al treball futur, s’espera poder estudiar més exhaustivament com afecta la
reducció del solapament entra els clústers de l’arbre en la reducció del nombre
d’accessos en una consulta determinada. També seria interessant veure com afecta
la precisió del Median Graph en les consultes. Referent als paràmetres que
influeixen en la creació de l’arbre (límits que divideixen el dendrograma i tipus
d’algorisme de clustering) s’haurien d’estudiar com aquests influeixen en la creació
els arbres i analitzar com afecten en l’aplicació del sistema ideat en aquest treball.
7. Referències
75
7. Referències
Recursos utilitzats (bibliografia, pàgines web, programari, hardware, etc.)
[1] Massimo De Santo, Gennaro Percannella, Carlo Sansone, Mario Vento: A Multi-
Expert System For Shot Change Detection In Mpeg Movies. IJPRAI 18(5): 933-956
(2004).
[2] S.Berretti, A.Del Bimbo, E.Vicario, Efficient Matching and Indexing of Graph
Models in Content Based Retrieval, IEEE Transactions on Pattern Analysis and
Machine Intelligence, (2001).
[3] A. Sanfeliu, F. Serratosa & R. Alquézar, “Second-Order Random Graphs for
modelling sets of Attributed Graphs and their application to object learning and
recognition”, International Journal of Pattern Recognition and Artificial Intelligence,
Vol. 18, No. 3, pp: 375-396 (2004).
[4] P. Ciaccia, M. Patella, and P. Zezula, “M-Tree: An Efficient Access Method for
Similarity Search in Metric Spaces”, Proc. Int'l Conf. Very Large Data Bases, 1997).
[5] Miquel Ferrer, Ernest Valveny, Francesc Serratosa: Median graphs: A genetic
approach based on new theoretical properties. Pattern Recognition 42(9): 2003-
2012 (2009).
[6] Miquel Ferrer, Ernest Valveny, Francesc Serratosa: Median graph: A new exact
algorithm using a distance based on the maximum common subgraph. Pattern
Recognition Letters 30(5): 579-588 (2009).
[7] A. Sanfeliu and K. Fu, “A distance measure between attributed relational graphs
for pattern recognition”, IEEE Transactions on Systems, Man and Cybernetics, 13,
353-362 (1983).
[8] Riesen, K. and Bunke. IAM Graph Database Repository for Graph Based Pattern
Recognition and Machine Learning, Structural, Syntactic, and Statistical Pattern
Recognition, LNCS 5342, 287-297(2009).
7. Referències
76
[9] Michel Neuhaus, Kaspar Riesen and Horst Bunke: “Fast Suboptimal Algorithms
for the Computation of Graph Edit Distance”, Graph Based methods, SSSP, Vol:
4109/2006, 163-172 (2006).
8. Annex 1
77
8. Annex 1
En aquest apartat s’explicaran les rutines més importants i els paràmetres que
utilitzen.
testCrearCubArbres.m
És una rutina que crea un cub d’arbres de dimensions #elements_classe X
#particions_cluster X #elems_arbre . No te paràmetres ni d’entrada ni de
sortida. Desa les dades en el fitxer “BBDDcubs.mat”. Les 3 variables més
importants desades son:
o matriuRepre:
o matriuProto:
o mDis[i,j,k]: matriu de distàncies de tots amb tots (tant de l’arbre
amb representants com de l’arbre amb prototips)
[arbre, arbre2, mDis]=muntarArbre(m,numParticions)
Aquesta rutina munta dos arbres, un amb representants i l’altre amb
prototips a partir d’una matriu m de grafs i el nombre de particions que es
vol que tingui el clúster.
Paràmetres d’entrada:
o m: matriu que conté tots els grafs.
o numParticions: nombre de divisions que es faran en el dendrograma
Paràmetres de sortida:
o arbre: arbre prototips
o arbre2: arbre representants.
o mDis: matriu de distàncies de tots els grafs de m amb tots. Per
estalviar càlculs, s’ha calculat només la matriu superior. Pel que
sempre que es busqui mDis(x,y), x>y. Això està controlat en la
funció calcular distància.
8. Annex 1
78
[mpdis,mDis]=pdistGrafs(m)
Rutina que calcula la distancia de tots amb tots els grafs de m. Retorna un
vector de distàncies que es necessari per a fer el clustering i una matriu de
distàncies de tots amb tots, útil per a estalviar processament a l’hora de
construir l’arbre amb representants, ja que reutilitza aquestes distancies
calculades.
Paràmetres d’entrada:
o m: matriu que conté tots els grafs.
Paràmetres de sortida:
o mpdis: vector de distàncies de tots els grafs de m amb tots, en el
que les distàncies es van guardant de manera seqüencial a mesura
que es calcula la matriu superior.
o mDis: matriu de distàncies de tots els grafs de m amb tots.
taula=dBuscarUnirFillsRepresentant(clusters,v,mat,taula)
Analitza tots els clústers i els uneix formant nodes segons els límits
especificats en v (que són els valors on particions dividiran el dendrograma),
que posteriorment emmagatzema en una taula.
Paràmetres d’entrada:
o clústers: matriu de 3 X #clústers calculada per linkage. (Explicat en
la secció de clustering).
o v: vector amb els límits inferior i superior entre els que ha de fer els
clústers. Cal remarcar que no és un índex, sinó un valor concret on
tallar el dendrograma
o mat: matriu amb tots els grafs.
o taula: taula on es desen els nodes creats desprès d’ajuntar els clúster
Paràmetres de sortida:
o taula: taula on es desen els nodes creats desprès d’ajuntar els clúster
8. Annex 1
79
taula=dBuscarUnirFillsPrototips(clusters,v,mat,taula);
Igual que l’anterior però amb prototips enlloc de representants, calculant-ne
els medians. En aquest cas es modifica també la matriu mat, per tal
d’emmagatzemar també els prototips just al final.
arbre=dMontarArbreRepresentant(taula,m);
Reordena la taula (posant el node arrel que està en la ultima posició al
principi i així successivament). Crea els enllaços entre nodes (pare - fill), i
calcula el radi de cada node.
Paràmetres d’entrada:
o taula: taula on es desen els nodes creats desprès d’ajuntar els clúster
o m: matriu amb tots els grafs.
Paràmetres de sortida:
o arbre: taula on es desen els nodes creats desprès d’ajuntar els
clúster
arbre2=dMontarArbrePrototips(taula2);
De la mateixa manera que l’anterior, reordena la taula, però tenint en
compte els grafs nous (prototips) emmagatzemats en la matriu.
booleà = esfulla(node)
Indica si el node passat per paràmetre és fulla, es a dir, si te fills o no.
8. Annex 1
80
distancia = calcularDistanciaGrafs(g1,g2)
Retorna la distància entre els dos grafs passats per paràmetre, del mateix
tipus carregat de la base de dades:
g1.occurrenceMatrix;
g1.adjacencyMatrix;
g1.quantitativeNodeAttributes;
I crida a la funció java per a calcular-ne la distància entre ells, passant-li per
paràmetre, les 3 matrius de cada graf.
Paràmetres d’entrada:
o g1: graf font.
o g2: graf destí.
Paràmetres de sortida:
o distància: distància d’edició entre els dos grafs.
distancia = calcularDistanciaIndexos(x, y)
Retorna la distància entre els dos grafs passats per paràmetre en forma
d’índex de la matriu de grafs mDis creada anteriorment. Amb aquesta
informació només cal enviar buscar a la posició (x,y) de la matriu i retornar-
ne el valor. D’aquesta manera estalvia càlculs de distàncies i l’algorisme és
més eficient. Val a dir que aquesta funció només s’utilitza en muntar l’arbre
amb representants, perquè el de prototips pot tenir distàncies diferents
degut a la creació de nous elements dintre de l’espai en forma de prototips.
Paràmetres d’entrada:
o g1: graf font.
o g2: graf destí.
Paràmetres de sortida:
o distància: distància d’edició entre els dos grafs.
8. Annex 1
81
arbre=dCalcularRadis(index,arbre)
Funció que calcula tots els radis d’un arbre.
Paràmetres d’entrada:
o arbre: arbre en el que es desitja fer la cerca. Pot ser tant fet amb
prototips com amb representants.
o index: índex de l’arbre per on començarà el càlcul.
Paràmetres de sortida:
o arbre: arbre en el que es desitja fer la cerca amb els nous radis
assignats. Pot ser tant fet amb prototips com amb representants.
[acceptats,nAcceptats,nAccessos]=dMtRangeQuery(arbre,n,q)
Aquesta fa la cerca de q, en un arbre seguint les condicions esmentades en
els punts de cerca tant de teoria com de desenvolupament. A mesura que va
cercant, compta també el nombre de càlculs realitzats i els retorna
juntament amb el conjunt d’elements trobats i el nombre d’aquests.
Paràmetres d’entrada:
o arbre: arbre en el que es desitja fer la cerca. Pot ser tant fet amb
prototips com amb representants.
o n: índex de l’arbre per on començarà la cerca.
o q: element que es vol cercar. Estructura que conté:
� d: element o graf que es vol cercar.
� µMAX que tindrà la cerca.
Paràmetres de sortida:
o acceptats: taula de grafs acceptats, es a dir, dintre del rang µMAX introduït
mitjançant q .
o nAcceptats: nombre d’elements acceptats.
o nAccessos: nombre de càlculs realitzats durant la cerca.
8. Annex 1
82
[acceptatsRepre,acceptatsProto,nAccessosRepre, nAccessosProto] = ferCerques (q,
arbreRrepre,arbreProto)
Crida a la funció anterior per als arbres representant i prototips. Els
paràmetres són els mateixos, però duplicats perquè hi ha 2 arbres. S’ha
exclòs retornar la taula d’elements trobats perquè no s’ha analitzat.
testCalcularSolapaments.m
Aquesta rutina que carrega el fitxer “BBDDcubs.mat” i crea un cub de
solapaments per a cada tipus d’arbre (representants i prototips) de
dimensions #elements_classe X #particions_cluster X #elems_fulla_arbre
(15X4X3), pertanyents als arbres calculats a la rutina anterior . No te
paràmetres ni d’entrada ni de sortida. També es guarden les desviacions
estàndard de cada arbre per al posterior estudi d’aquests. Desa les dades en
el fitxer “BBDDsolapaments.mat”
testCalcularAccessos.m
Rutina que carrega el fitxer “BBDDcubs.mat” i s’encarrega de calcular la
mitjana d’accessos. Crea un cub de 5 dimensions: Divisió(µMAX) X
#particions_cluster X #elems_fulla_arbre X elements_classe X num_test
(3X4X3X15X9), per a cada arbre (representants i prototips) amb els
accessos generats per cada test. Desa les dades en el fitxer
“BBDDaccessos.mat”
testCalcularMitjanesSolapament.m
Aquesta rutina carrega el fitxer “BBDDsolapaments.mat” i en calcula les
mitjanes. Emmagatzema les dades en una taula de 2 dimensions:
#particions_cluster X #elems_fulla_arbre, fent la mitjana dels valors de la
resta de dimensions. Desa els resultats en el fitxer
BBDDMatriuSolapament.mat.
8. Annex 1
83
testCalcularMitjanesAccessos.m
És una rutina que carrega el fitxer “BBDDaccessos.mat” i en calcula les les
mitjanes, tal com ho ha fet la rutina anterior, però en aquest cas de la
variable nombre d’accessos. S’emmagatzemen els resultats obitinguts en el
fitxer BBSSMatriuAccessos.mat.
9. Annex 2
84
9. Annex 2: publicacions
Pendent de submissió a SSSPR2010 (Syntactic and Structural Pattern Recognition),
amb deadline 1 de Febrer.