UNIVERSITATEA ALEXANDRU IOAN CUZA IAŞI
FACULTATEA DE INFORMATICĂ
LUCRARE DE LICENŢĂ
Construirea unui sistem complex pentru alinierea ontologiilor
propusă de
Alexandru Lucian Gînscă
Sesiunea: iulie, 2010
Coordonator ştiinţific
Dr. Adrian Iftene
2
UNIVERSITATEA ALEXANDRU IOAN CUZA IASI FACULTATEA DE INFORMATICA
Construirea unui sistem complex pentru alinierea ontologiilor
Alexandru Lucian Gînscă
Sesiunea: iulie, 2010
Coordonator ştiinţific
Dr. Adrian Iftene
3
Declaraţie privind originalitate şi respectarea drepturilor de autor
Prin prezenta declar că Lucrarea de licenţă cu titlul “Construirea unui sistem complex pentru alinierea ontologiilor” este scrisă de mine și nu a mai fost prezentată niciodată la altă facultate sau instituție de învățământ superior din țară sau străinătate. De asemenea, declar că toate sursele utilizate, inclusiv cele preluate de pe Internet, sau indicate în lucrare, cu respectarea regulilor de evitare a plagiatului:
toate fragmentele de text reproduse exact, chiar și în traducere proprie din altă limbă, sunt scrise între ghilimele și dețin referința precisă a sursei;
reformularea în cuvinte proprii a textelor scrise de către alți autori deține referința precisă;
codul sursă, imagini etc. preluate din proiecte open-source sau alte surse sunt utilizate cu respectarea drepturilor de autor și dețin referințe precise;
rezumarea ideilor altor autori precizează referința precisă la textul original.
Iași,
Absolvent: Alexandru Lucian Gînscă _______________
4
Declaraţie de consimţământ
Prin prezenta declar că Lucrarea de licenţă cu titlul “Construirea unui sistem complex pentru alinierea ontologiilor”, codul sursă al programelor şi celelalte conţinuturi (grafice, multimedia, date de test etc.) care însoţesc această lucrare să fie utilizate în cadrul Facultăţii de Informatică. De asemenea, sunt de acord ca Facultatea de Informatică de la Universitatea Alexandru Ioan Cuza Iaşi să utilizeze, modifice, reproducă şi să distribuie în scopuri necomerciale programele-calculator, format executabil şi sursă, realizate de mine în cadrul prezentei lucrări de licenţă.
Iași,
Absolvent: Alexandru Lucian Gînscă _______________________
5
Acord privind proprietatea dreptului de autor
Facultatea de Informatică este de acord ca drepturile de autor asupra programelor-calculator, format executabil şi sursă, să aparţină autorului prezentei lucrări, Alexandru Lucian Gînscă.
Încheierea acestui acord este necesară din următoarele motive:
Iași,
Decan: Gheorghe Grigoraş Absolvent: Alexandru Lucian Gînscă
_______________________ _______________________
6
Cuprins
1. Introducere
1.1 Motivaţie
1.2 Contribuţii personale
2. Definiţii şi exemple
2.1 Ontologie 2.1.1 Definiţii
2.1.2 Exemplu de ontologie 2.2 Alinierea Ontologiilor
2.2.1 Definiţia 2.2.2 Exemplu 2.3 Similaritatea
3. Scenarii de utilizare
3.1 Descoperirea entităţilor similare 3.2 Comunicarea între servicii web 3.3 Integrarea informaţiei
3.4 Evoluţia ontologiilor 3.5 Contopirea ontologiilor
3.6 Interogarea bazelor de cunoştinţe
4. Abordari şi sisteme existente
4.1 Elemente luate în considerare pentru analiza sistemelor 4.2 Sisteme de referinţă
5. Metode de bază folosite în procesul de aliniere
5.1 Metode sintactice 5.2 Metode semantice
7 5.3 Metode bazate pe taxonomie
6. Metode avansate
6.1 Algoritmi genetici
6.1.1 Algoritmi genetici în alte sisteme
6.1.2 Folosirea unui algoritm genetic pentru optimizarea agregării similarităților 6.1.2.1 Codarea cromozomilor
6.1.2.2 Selecția cromozomilor 6.1.2.3 Operatori genetici 6.1.2.4 Funcția fitness
6.1.2.5 Structura generală a algoritmului și îmbunătățiri suplimentare 6.1.2.6 Rezultate obținute
6.2 Rețele Markov
6.2.1 Schema pentru alinieri
6.2.2 Construirea modelului probabilistic 6.2.3 Rezultate obținute
7. Evaluarea alinierilor
7.1 Metodele standard de evaluare 7.2 Alte funcții de evaluare
8. Prezentarea sistemului
8
1. Introducere
1.1 Motivaţie
A devenit recunoscută importanța interoperabilității între resursele utilizate în cadrul webului semantic, folosite în rețele peer-to-peer sau de către serviciile web. Un prim pas către o reprezentare uniformă a informațiilor este folosirea ontologiilor. Cu numărul tot mai mare de domenii care folosesc ontologiile, apare și problema unificării acestor informații. Pentru a putea contopi două sau mai multe ontologii într-una singură, este mai întâi nevoie de a se găsi alinieri între entitățile acestora. O modalitate este de a alinia manual ontologiile, dar această abordare este foarte ineficientă în cazul unui volum mare de date. Așadar, au apărut mai multe sisteme semi sau complet automate de aliniere a ontologiilor. Primele dintre ele foloseau numai metode simple pentru stabilirea alinierilor. Următoarele generații de sisteme și-au îndreptat atenția către modalități de a combina într-un mod cât mai eficient metodele de bază.
Alinierea ontologiilor, privită prin prisma identificării relaţiilor dintre elemente individuale ale mai multor ontologii, este un pas important în stabilirea interoperabilităţii între agenţi sau servicii care folosesc diferite ontologii individuale. Mai mult, li se uşurează sarcina utilizatorilor umani care doresc să acceseze o bază de cunoştinţe reprezentată de mai multe ontologii.
Un exemplu concret poate fi considerat cazul a două instituţii care au numitor comun cărţile: o librărie online şi o bibliotecă. Cu toate că lucrează cu acelaşi tip de produse, fiecare va pune accent pe anumite aspecte. Pe când prima va acorda mai multă importanţă preţului, tipului de copertă sau anului publicării, organizarea în cadrul bibliotecii se va face, în principal, după categoria literară sau ediţie. Ambele au în comun numele autorului şi titlul volumului. Aşadar, cele două instituţii vor avea organizată informaţia sub forma a două ontologii eterogene. Se poate imagina un scenariu în care organizaţiile trebuie să interacţioneze, spre exemplu, dacă cele două ajung la un acord de colaborare pentru a-şi îmbunătăţi fiecare baza de cunoştinţe, combinând cele două deja existente. Pentru aceasta este nevoie de identificarea corectă a entităţilor comune, acest lucru realizându-se prin procesul de aliniere.
9
1.2 Contribuții personale
În alcătuirea acestui sistem, am combinat în mod original unele dintre cele mai de succes metode prezente în sistemele de top. Mai mult, am folosit un algoritm genetic în mod inovativ pentru a optimiza întregul pas de agregare a similarităților din cadrul procesului de aliniere a ontologiilor. Eficiența acestor metode se reflectă prin rezultatele bune obținute.
În această lucrare, am urmărit evoluția sistemelor de aliniere a ontologiilor, de la cele care folosesc numai metode simple, cum ar fi măsurile de similaritate sintactică sau cele de
similaritate semantică, până la cele mai de succes sisteme actuale, care utilizează diferite metode avansate pentru a se obține o cât mai bună combinare a metodelor de bază.
Pentru sistemul care reprezintă partea practică a acestei lucrări și care a fost folosit pentru obținerea rezultatelor prezentate în lucrare, am gândit o alcătuire modulară. Astfel, modulul care se ocupă de calcularea funcțiilor de similaritate de bază este împărțit în trei submodule, fiecare conținând un anumit tip de funcții: cele care tratează similaritatea sintactică, similaritatea semantică, respectiv similaritatea dată de structura ontologiilor. Acestor module li se poate alătura oricând altul, cu un alt tip de similaritate, dar și cele actuale pot fi ușor extinse, prin introducerea unor noi măsuri de similaritate. Alte două module se ocupă de îmbunătățirea
rezultatelor, unul prin optimizarea agregării măsurilor de similaritate, folosind în mod original un algoritm genetic, iar altul prin recalcularea similarității globale cu ajutorul unei rețele Markov.
Pentru testare și evaluare, am implementat un modul special, care poate fi folosit în combinație cu oricare dintre cele prezentate mai sus și care folosește cele mai des întâlnite măsuri de evaluare a ontologiilor: Precision, Recall și F-Measure. Interoperabilitatea modulelor este
asigurată prin scrierea în fișiere XML a datelor care se obțin în urma utilizării unui modul și care constituie intrarea pentru un alt modul. Astfel, se asigură și reutilizarea informațiilor obținute.
10
2. Definiţii şi exemple
2.1 Ontologie
2.1.1 Definiţia unei ontologii
Una dintre cele mai citate definiţii este “O ontologie este o specificare explicită a unei conceptualizări.” (Gruber, 1995). Termenul de conceptualizare se referă la un model abstract al unei părţi din lumea înconjurătoare, model realizat prin identificarea conceptelor relevante din acea parte. Definiţia este extinsă prin adăugarea a trei noi condiţii. “O ontologie este o specificare formală, explicită a unei conceptualizări comune a unui domeniu de interes.”, unde “formală” se referă la faptul că ontologia trebuie să poată fi citită de un calculator, “comună” presupune nu atât faptul că are un înţeles comun la nivel global, ci că respectă viziunea comună a unui anumit grup, iar “domeniu de interes” sugerează faptul ca o ontologie nu trebuie să modeleze cât mai multe aspecte ale lumii, ci numai pe acelea relevante într-un anumit domeniu.
Definiţia de mai sus este una generală, dar pentru un sistem informatic care foloseşte ontologii este nevoie de o definiţie formală. Următoarea definiţie este o versiune simplificată a definiţiei prezentate în Stumme et al. (2003).
Def 2.1
O ontologie este o structură O = (C, ≤C ,R, ≤R), unde:
- C şi R sunt două mulţimi disjuncte, ale căror elemente sunt numite concepte, respectiv relaţii.
- ≤C este o realaţie de ordine parţială peste C, numită ierarhia conceptelor.
- ≤R este o realaţie de ordine parţială peste R, numită ierarhia relaţiilor, iar r1 ≤R r2 dacă şi numai dacă domeniul(r1) ≤C domeniul( r2) şi codomeniul( r1) ≤C codomeniul( r2).
Pentru simplificare, tipurile de date precum întregii sau şirurile de caractere sunt tratate drept cazuri speciale de concepte.
11 2.1.2 Exemplu de ontologie
Pentru a se clarifica noţiunea de ontologie, am ales un exemplu simplu [1], dar care ilustrează componentele principale ale unei ontologii. Această ontologie descrie domeniul vânzărilor auto, modelând o posibilă reprezentare a stocului unei reprezentanţe auto şi a relaţiilor cu clienţii.
Ontologia este prezentată în figura 2.1. Conceptele apar sub formă dreptunghiulară, relaţiile sub formă hexagonală, iar instanţele sub formă ovală. Subconceptele sunt legate de conceptele părinte printr-o săgeată plină. O relaţie are o săgeată întreruptă dinspre domeniu şi una spre codomeniu.
Instanţele sunt legate de entităţile din care provin printr-o săgeată întreruptă albastră.
Conform definiţiei 2.1, se poate distinge:
O = (C, ≤C ,R, ≤R) = ({object, vehicle, owner,...}, {(vehicle, object), (boat, vehicle),...}, {belongsTo, hasSpeed}, {}).
Fig. 2.1 : Exemplu de ontologie
Ontologia este descrisă în formatul OWL. Un spaţiu de nume XML este adăugat reprezentării OWL.
12
<rdf:RDF xmlns:auto="http://www.autoweb.com/onto1.owl">
<owl:Class rdf:about='auto#vehicul'>
<rdfs:label >vehicul</rdfs:label>
<rdfs:subClassOf rdf:resource='auto#obiect'/>
</owl:Class>
<owl:Class rdf:about='auto#masina'>
<rdfs:label>masina</rdfs:label>
<rdfs:subClassOf rdf:resource='auto#vehicul'/>
</owl:Class>
<owl:ObjectProperty rdf:about='auto#apartine'>
<rdfs:label >apartine</rdfs:label>
<rdfs:domain rdf:resource ='auto#vehicul'/>
<rdfs:range rdf:resource='auto#proprietar'/>
</owl:ObjectProperty >
<auto:Proprietar rdf:about='auto#Vlad'/>
<auto:Masina rdf:about='auto#Renault Clio'>
<rdfs:label>Renault Clio</rdfs:label>
<auto:apartine rdf:resource='auto#Vlad'/>
<auto:areViteza rdf :resource='auto#200 km/h’/>
</auto:Masina>
</rdf:RDF>
Tabel 2.1: Ontologie în formatul OWL
2.2 Alinierea ontologiilor 2.2.1
DefinițieO funcție de aliniere este definită pentru o pereche de ontologii și o entitate și returnează o altă entitate, care este alinierea celei dintâi.
∶ × × →
13
2.2.2
ExempluAlinierile pot apărea în mai multe formate, în funcție de cerința inițială sau scopul folosirii lor ulterioare. Un exemplu de aliniere, care este descrisă printr-un XML, este prezentat în continuare.
<rdf:RDF>
<Alignment>
<ontol>ontologyl.owl</ontol>
<onto2>ontology2.owl</onto2>
<uril> http://lonely.org/ontology1.owl</uril>
<uri2> http://travel.org/ontology2.owl/uri2>
<map>
<Cell>
<enttity1 rdf:resource='ontologyl.owl#garden />
<enttity2 rdf:resource='ontology2.owl#garden '/>
<measure rdf:datatype='XMLSchema#float'>1.0</measure>
<relation>=</relation>
</Cell>
<Cell>
<entityl rdf:resource='ontologyl.owl#lake '/>
<entity2 rdf:resource='ontology2.owl#lake '/>
<measure rdf:datatype='XMLSchema#float'>1.0</measure>
<relation>=</relation>
</Cell>
</map>
</Aligninent>
</rdf:RDF>
Tabel 2.2: Exemplu de aliniere în format XML
O altă modalitate de reprezentare a unei alinieri, folosită cu precădere pentru testarea și evaluarea alinierilor, este să se scrie pe aceeași linie entitățile care constituie o aliniere, eventual, împreună cu un scor care reprezintă încrederea în acea aliniere. Un exemplu în care apar alinieri sub această formă este luat dintr-un fișier “gold”, asociat unei perechi de ontologii prezentate în tabelul 6.1.
http://lonely.org/russia#fortress; http://travel.org/russia#fortress; 1;
http://lonely.org/russia#monument; http://travel.org/russia#monument; 1;
14
http://lonely.org/russia#garden; http://travel.org/russia#garden; 1;
http://lonely.org/russia#square; http://travel.org/russia#square; 1;
http://lonely.org/russia#forest; http://travel.org/russia#forest; 1;
http://lonely.org/russia#peninsula; http://travel.org/russia#peninsula; 1;
http://lonely.org/russia#island; http://travel.org/russia#island; 1;
http://lonely.org/russia#mountain; http://travel.org/russia#mountain; 1;
http://lonely.org/russia#sea; http://travel.org/russia#sea; 1;
http://lonely.org/russia#river; http://travel.org/russia#river; 1;
http://lonely.org/russia#lake; http://travel.org/russia#lake; 1;
http://lonely.org/russia#canal; http://travel.org/russia#canal; 1;
Tabel 2.3: Exemplu de fișier cu alinieri
2.3 Similaritatea
O funcție de similaritate generală primește la intrare două entități, câte una din fiecare dintre cele două ontologii pentru care se dorește aflarea alinierilor și returnează o valoare în intervalul [0, 1].
: → [0, 1]
Este important pentru ușurarea procesului de agregare a similarităților ca aceste funcții să returneze o valoare între 0 și 1. Dacă o anumită funcție nu respectă această condiție, este nevoie de o normalizare a acesteia, un exemplu fiind prezentat în capitolul 5.1.
3. Scenarii de utilizare
3.1 Descoperirea entităţilor similare
În acest scenariu, nu se cunoaşte cu exactitate scopul în care vor fi folosite rezultatele obţinute în urma identificării entităţilor similare sau, altfel spus, a candidaţilor propuşi pentru aliniere. Scenariul se referă la cazul de bază, în care accentul se pune pe procesul de aliniere
15
propriu-zis, ceea ce poate reprezenta scopul unor proiecte de cercetare sau al unor frameworkuri de evaluare, spre deosebire de obţinerea unui rezultat finit, lucru care s-ar dori în cadrul unei aplicaţii comerciale.
Tot în cadrul acestui scenariu de utilizare, intră şi cazul în care o aplicaţie doreşte să folosească un set de alinieri sub formă de resursă externă. Alinierile simple sunt mai puţin utile decât dacă ar fi obţinute în timpul rulării aplicaţiei, deoarece, în momentul în care se descoperă entităţile comune şi se salvează sub formă de alinieri, nu se cunosc specificaţiile furnizate de aplicaţie, ceea ce ar duce la rafinarea rezultatelor. Aplicaţia fiind deschisă, se pot obţine informaţii suplimentare, în mod automat sau furnizate de utilizatori, care vor fi folosite pentru extragerea alinierilor necesare. Din această cauză, este bine ca alinierile stocate să conţină cât mai multe metadate. Spre exemplu, un utilizator este mai interesat de corectitudinea alinierilor decât de numărul lor. Atunci, fişierul în care se găsesc alinierile ar trebui să conţină şi gradul de încredere că o asemenea aliniere este identificată corect. Acesta poate fi chiar scorul specific acelei perechi de entităţi, rezultat în urma procesului de aliniere.
3.2 Comunicarea între servicii web
De cele mai multe ori, serviciile folosesc reprezentări diferite ale cunoştinţelor, ceea ce duce la diferite mijloace de utilizare a acestora sau la inputuri şi outputuri diferite. Scopul unor servicii sau agenţi web este acela de a colabora, în ciuda reprezentărilor eterogene ale informaţiei, pentru a-şi putea îndeplini sarcinile. O modalitate prin care se poate realiza acest lucru este de a se apela laontologii standard, mai generale, care să poată asigura o corectă comunicare între două sau mai multe servicii web. Când nu se poate realiza acest lucru, dacă nu se poate găsi sau este dificil de construit o astfel de ontologie, este necesară alinierea ontologiilor folosite de respectivele servicii. Numai dacă se stabileşte o corectă corelare între ontologii, se poate decide dacă vor fi folosite informaţiile furnizate de acestea, în vederea utilizării funcţionalităţilor oferite de servicii.
În cazul acestui scenariu de utilizare, alinierea trebuie să fie rapidă, să folosească surse de încredere şi, cel mai important, să fie corectă. Adesea, serviciile sunt proiectate pentru a fi folosite contra cost. Acestea îşi vor pierde clienţii, dacă utilizatorii plătitori vor primi informaţii, răspunsuri greşite. Un compromis este de a permite celor care folosesc serviciul să confirme validitatea unor date intermediare, dar aceasta este o modalitate neelegantă de a rezolva problema, cel mai bine fiind ca întreg procesul să rămână complet automat. Aşadar, se va prefera
16
atenţionarea utilizatorului asupra imposibilităţii furnizării vreunui rezultat şi înaintarea unei cereri către acesta de a modifica inputul dat primului serviciu decât returnarea unui răspuns greşit.
Pentru a afla dacă outputul unui serviciu se potriveşte cu inputul altuia, acestea trebuie aliniate şi, cum informaţia este reprezentată sub formă de ontologii, acest lucru se realizează prin alinierea ontologiilor (Burstein and McDermott, 2005).
De exemplu, se poate folosi serviciul oferit de o linie aeriană, prin care se cumpără bilete de avion, împreună cu cel furnizat de un site, care se ocupă de rezervarea camerelor de hotel.
3.3 Integrarea informaţiei
După cum se prezintă în Volz et al. (2004), o mare parte din informaţiile disponibile pe internet sunt stocate în baze de date relaţionale. De asemenea, se mai precizează că schemele de baze de date pot fi translatate în ontologii. Totuşi, problema integrării informaţiei rămâne. Pentru aplicaţii care utilizează ontologii, trebuie sa fie recunoscute instanţele egale, chiar dacă acestea provin din surse diferite.
Informaţiile care provin din surse diferite trebuie integrate şi prezentate utilizatorului într-o manieră unificată, dacă se referă la acelaşi concept sau descriu instanţe identice. Pentru a se realiza această unificare este nevoie de alinierea ontologiilor. De cele mai multe ori, integrarea informaţiei se face o singură dată şi nu de fiecare dată cand se rulează o aplicaţie, ceea ce înseamnă că timpul necesar procesului de aliniere nu este important. Deoarece se procesează cantităţi foarte mari de date, procesul trebuie să fie în întregime automat, doar în cazuri excepţionale putându-se permite intervenţia unui utilizator uman pentru a rezolva anumite conflicte. Nefiind necesară o aliniere rapidă, se aşteaptă o calitate cât mai ridicată a alinierilor şi neincluderea unor alinieri asupra corectitudinii cărora există dubii nu reprezintă o problemă.
Un exemplu de sistem care se încadrează în acest scenariu este Bibster, o aplicaţie care le permite utilizatorilor să folosească o ontologie comună drept model, dar, în urma unei interogări în reţeaua peer-to-peer, pot fi returnate mai multe instanţe care conţin aceeaşi informaţie bibliografică. Aceste instanţe trebuie apoi integrate automat. Alinierea ontologiilor ajută la îndeplinirea acestei sarcini.
17 3.4 Evoluţia ontologiilor
Ontologiile evoluează în timp, sunt îmbunătăţite cu noi informaţii şi, pentru a se marca anumite etape ale progresului, li se pot atribui versiuni. Alinierea ontologiilor poate furniza informaţiile necesare stabilirii legăturii dintre diferite versiuni ale unei ontologii.
Dacă se dispune de o aliniere între diferite versiuni ale unei ontologii, atunci operaţiile efectuate asupra versiunii mai vechi pot fi transferate direct asupra versiunii mai noi, iar dacă se cere, şi invers. Calitatea alinierii, în acest caz, ar trebui să fie, în general, ridicată, dar acesta nu este un factor atât de important ca în alte scenarii de utilizare, deoarece există deja mai multe versiuni ale unei ontologii, care se presupun a fi corecte. Mai mult, fiind vorba despre aceeaşi ontologie, sunt multe similarităţi între versiuni diferite. Timpul nu este un factor critic şi, dacă nu este un volum prea mare de date, un utilizator uman poate asista procesul de aliniere.
3.5 Contopirea ontologiilor
Contopirea ontologiilor se referă la folosirea mai multor ontologii pentru crearea unei ontologii mai mari, care să unifice informaţiile conţinute de fiecare. În general, ontologiile-sursă dispar, rămânând numai ontologia rezultată în urma contopirii. Înainte ca două entităţi să fie contopite, este necesar ca acestea să fie identificate în urma unui proces de aliniere.
Ontologia rezultată trebuie să fie corectă şi, foarte important, completă, adică să cuprindă toate entităţile din ontologiile-sursă. Drept urmare, alienierea ontologiilor cu scopul contopirii include intervenţia umană pentru verificarea corectitudinii. Dacă o aliniere este propusă de sistem cu o încredere scăzută, este de preferat consultarea unui utilizator uman. Totuşi, dacă îi sunt propuse pentru analiză prea multe alinieri, acesta va fi deranjat. Timpul este mai puţin important, procesul de contopire putându-se realiza înaintea altor operaţii sau poate fi rulat în fundal.
3.6 Interogarea bazelor de cunoştinţe
O operaţie care apare adesea în cadrul aplicaţiilor care se ocupă cu gestionarea bazelor de cunoştinţe este interogarea anumitor surse. Utilizatorii formulează o interogare într-un limbaj pentru interogări bazat pe o ontologie. Această interogare este apoi trimisă unui sistem care se
18
ocupă cu rezolvarea acesteia sau este trimisă printr-o reţea către alte calculatoare (Tempich et al., 2004). Sistemul returnează răspunsul potrivit pentru acea interogare. Se doreşte ca o aplicaţie care incorporează operaţiile de mai sus să poată interoga diferite surse de informaţii eterogene, fără a necesita să cunoască reprezentarea internă a fiecărei ontologii în parte. Pentru a realiza acest lucru, o interogare formulată în conformitate cu sursa trebuie rescrisă pentru a se potrivi cu ontologia folosită în final pentru interogare. Rescrierea presupune maparea conceptelor cuprinse în interogare la cele ale ontologiei ţintă. După executarea interogării, răspunsul trebuie să fie transformat înapoi la reprezentarea iniţială, folosindu-se aceeaşi metodă ca la rescrierea interogării. Maparea rezultă în urma alinierii ontologiilor-sursă şi destinaţie.
Rescrierile sunt făcute în timpul rulării aplicaţiei, deci procesul de aliniere trebuie să fie rapid şi în totalitate automat. Este considerată acceptabilă returnarea de rezultate greşite, atât timp cât sunt întoarse şi cele corecte.
4. Abordări în sisteme existente
Alinierea ontologiilor este folosită în mai multe domenii, reprezentate de diferite scenarii de utilizare, după cum s-a putut vedea în capitolul anterior. Deoarece s-au realizat multe progrese în toate dintre aceste domenii, este necesară studierea altor sisteme, înainte de a începe lucrul la unul nou. În acest capitol, identific parametrii şi metodele comune mai multor sisteme şi prezint modul în care acestea sunt alese de către cele mai de succes dintre ele.
4.1 Elemente luate în considerare pentru analiza sistemelor
Este mai uşor de identificat particularităţile fiecărui sistem dacă sunt specificate în prealabil criteriile care sunt folosite în analiza acestuia. Am preluat împărţirea acestora în patru secţiuni, după modelul prezentat de Shvaiko şi Euzenat (2005). Aceste secţiuni sunt: schema de input, procesul de aliniere, schema de output şi scenariul de utilizare.
19 Schema de input:
În această lucrare, se află în atenţie alinierea a două ontologii, dar există sisteme care tratează cazuri în care este nevoie de alinierea şi a altor scheme de input.
- Pe lângă ontologii, sunt şi alte structuri de date cu mai mică valoare semantică, cum ar fi arborii sau schemele de clasificare. Pentru integrarea informaţiei, schemele care descriu baze de date relaţionale pot reprezenta, de asemenea, un input.
- Fişiere XML simple, fără a respecta vreun standard specific ontologiilor, sunt folosite la input în diferite abordări.
- Se poate trata diferit o ontologie care conţine şi instanţe faţă de una fără instanţe, construită la un nivel mai abstract.
Procesul de aliniere:
Aceasta este componenta cea mai complexa a unui sistem care se ocupă de alinierea ontologiilor. Aici se poate observa originalitatea unui sistem şi prin acest modul sistemele diferă cel mai mult între ele, deoarece există un număr mare de metode şi parametri care pot fi evidenţiaţi.
- Anumite sisteme folosesc o abordare care se axează pe sintaxă, pe când altele se folosesc pe deplin de semantica ontologiilor. Mai mult, se pot distinge mai multe nivele de folosire a semanticii oferite de ontologie. De exemplu, se pot lua în considerare numai proprietăţile lingvistice ale entităţilor sau se pot folosi relaţiile şi constrângerile oferite de limbajul prin care este modelată ontologia.
- O anumită abordare poate presupune concentrarea pe structură (concepte şi relaţii), pe când alta se poate folosi în special de instanţe.
- De cele mai multe ori, se folosesc diferite măsuri pentru propunerea unei alinieri. Sistemele diferă prin modul în care aleg să combine rezultatele oferite de aceste măsuri.
- Pot fi folosite resurse adiţionale pentru îmbunătăţirea rezultatelor. Unele sisteme utilizează mult astfel de resurse, spre exemplu, prin extragerea de informaţii din dicţionare precum Word-Net.
- Sistemele diferă şi în funcţie de gradul de automatizare al procesului de aliniere, acesta putând varia de la preponderent manual, până la complet automat.
20 Schema de output:
- În funcţie de schema de input, diferă şi elementele care sunt aliniate: concepte, relaţii şi noduri; noduri şi muchii; clase, obiecte şi atribute; elemente individuale sau structuri în întregime.
- Cele mai comune sunt alinierile unu-la-unu, dar se pot întâlni situaţii în care este nevoie de alinieri n-la-m.
- Cele mai multe sisteme nu întorc numai o mulţime de alinieri, ci şi încrederea în corectitudinea fiecăreia. Aceasta permite sistemelor implicarea unui utilizator uman în stabilirea corectitudinii alinierilor.
Scenarii de utilizare:
Cu toate că nu se disting alţi parametri diferiţi decât cei prezentaţi până acum, scenariul de utilizare pentru care este construit sistemul influenţează inputul, procesul de aliniere sau outputul.
Cele mai importante scenarii de utilizare sunt cele descrise în capitolul anterior.
4.2 Sisteme de referinţă
ONION
În sistemul lor, ONION (ONtology compositlON system), Mitra et al. (2000) abordează problema eterogenităţii care apare în(tre) diferite ontologii. Raţionamentul pe care-l fac este că unificarea ontologiilor este prea costisitoare şi ineficientă. Drept urmare, ei se concentrează pe crearea unor reguli de articulare, prin intermediul cărora se leagă conceptele corespunzătoare.
Deoarece un proces manual de creare a acestor reguli nu este eficient, ei folosesc o abordare semi-automată, care ia în considerare relaţii simple între etichete şi valorile atributelor. De asemenea, folosesc şi informaţii oferite de dicţionare în procesul de aliniere. Pe baza acestor relaţii, o aliniere este propusă unui utilizator care decide dacă alinierea este corectă sau nu.
OLA
Sistemul OWL Lite Aligner (OLA) , creat de Euzenat şi Valtchev (2004), foloseşte diferite componente ale ontologiilor folosite pentru aliniere pentru a calcula similarităţi. Similarităţile de bază sunt obţinute pe baza etichetelor. Iterativ, similarităţile de bază se influenţează reciproc,
21
până se echilibrează perechile desprinse din cele două ontologii. În fiecare iteraţie, similarităţile sunt recalculate în funcţie de similarităţile nodurilor vecine, unde două noduri sunt vecine, dacă există vreo relaţie între ele. Aceasta înseamnă că OLA este un sistem care foloseşte atât informaţiile despre elemente, cât şi informaţii legate de structură. Un utilizator introduce ponderile pe care doreşte să le asocieze fiecărei similarităţi, în vederea calculării scorului final, în funcţie de care se stabileşte dacă o pereche propusă spre aliniere va deveni o aliniere sau nu.
OLA returnează alinieri unu-la-unu ale conceptelor, relaţiilor şi instanţelor.
Cupid
Cupid (Madhavan et al., 2001) este un sistem care are ca scop alinierea atât la nivel de element individual, cât şi alinierea la nivel de structură. În ceea ce priveşte inputul, acesta variază mult, putând fi diferite scheme de date relaţionale sau fişiere XML. Algoritmul de aliniere are trei paşi.
În primul pas, elementele sunt comparate prin mijloace lingvistice, folosindu-se resurse externe, care oferă informaţii asupra sinonimiei. În al doilea pas, pentru alinierea la nivel structural, schemele oferite la input sunt translatate în arbori. Apoi, se compară elementele de pe frontieră.
Similaritatea se calculează printr-o medie ponderată a similarităţilor sintactice şi structurale. În al treilea pas, se aplică un prag, prin care se stabileşte dacă se face sau nu alinierea.
COMA
COMA (combination of MAtching algorithms) (Do şi Rahm, 2002) este un sistem care are ca scop combinarea mai multor module de aliniere într-un mod cât mai flexibil. Înainte de a începe procesul de aliniere, diferitele scheme folosite la input sunt transformate în arbori. Acest proces este compus din trei faze. Prima fază este opţională şi presupune implicarea unui utilizator uman care introduce parametrii algoritmului şi alege modulele. Apoi, în a doua fază, se execută fiecare modul în parte. Unele module folosesc informaţii lingvistice, iar altele elemente de structură, precum frunzele. În a treia fază, rezultatele întoarse de fiecare modul sunt combinate, folosindu- se media ponderată. Este, de asemenea, posibil ca sistemul să ruleze într-un mod complet automat.
S-MATCH (U. Trento)
S-MATCH este un sistem care folosește în principal metode semantice. Primește la input două structuri de graf și rezultatul obțtinut în urma prelucrării acestora este adăugarea de relații
22
semantice între nodurile grafurilor. Aceste relații pot fi: echivalență, mai general, mai puțin general, nepotrivire, suprapunere. Deoarece este bazat pe structura internă a ontologiei, acest sistem neglijează instanțele. Sistemul este foarte modulari, având unul pentru prelucrarea
inputului, care este transformat într-o structura proprie, un modul de preprocesare, care selectează diferite resurse externe care vor fi folosite, spre exemplu WordNet și un modul de stabilire a legăturilor semantice, care returnează un graf îmbunătățit.
5. Metode de bază folosite în procesul de aliniere
5.1 Metode sintactice
În această categorie intră diferite metode care se ocupă de compararea a două șiruri de caractere. În contextul ontologiilor, acest tip de funcții se pot aplica pe numele entităților, sau pe etichetele și comentariile asociate, dacă acestea sunt prezente.
Înainte de a fi comparate, șirurile de caractere trebuiesc aduse la o formă cât mai simplă, însă fără a se pierde semantica acestora. Câteva modalități de a săvârși acest lucru sunt următoarele :
- Eliminarea literelor mari. (Ex: Creion define creion, SRI devine sri) ; - Eliminarea semnelor de punctuație. (Ex: S.R.I devine SRI);
- Eliminarea caracterelor de legatură cu un singur caracter spațiu. (Ex: câine-lup devine câine lup);
- Eliminarea caracterelor spațtiu multiple sau a caracterului tab cu un singur caracter spațiu.
(Ex: pisică de mare devine pisică de mare );
În continuare, va urma o prezentare a măsurilor folosite.
23 Distanța Levenshtein
Distanța Levenshtein este o metodă des folosită pentru calcularea diferenței dintre două șiruri de caractere. Date două șiruri: s (șirul sursă ) și t (șirul destinație), distanța Levenshtein reprezintă numărul minim de operații elementare necesare transformării lui s în t, unde operațiile posibile sunt: inserția, ștergerea sau substituția unui character.
Exemplu: Dacă s este “masă” și t este “casă”, atunci dist(s,t) = 1 , deoarece este necesară o singură substituție (“m” devine “c”) pentru a transforma s în t.
Algoritmul folosit pentru calcularea distanței Levenshtein poate fi descris prin următoarea serie de pași:
1. Se inițializează m = numărul de caractere din s și n = numărul de caractere din t;
Dacă m = 0 sau n = 0, se returnează 0 ;
Altfel, se construiește o matrice d, cu m + 1 linii și n + 1 coloane.
2. Se inițializează prima coloană cu d[i,0] = i și prima linie cu d[0,i] = i, i = 0,…,n.
3. Se parcurg caracterele din s de la i = 1, la m și caracterele din t , de la j = 1 la n;
Dacă s[i] = t[j] , atunci cost = 0;
Altfel, cost = 1.
4. Se parcurge matricea atât timp cat mai sunt celule libere și se completează:
d[i , j] = min (d[i – 1, j] + 1, d[i , j – 1] + 1, d[i – 1, j – 1] + cost).
5. Distanța Levenshtein se găsește in celula d[n , m].
Exemplu: s = “priceput”, t = “perceput”.
p e r c e p u t
0 1 2 3 4 5 6 7 8
p 1 0 1 2 3 4 5 6 7
r 2 1 1 1 2 3 4 5 6
i 3 2 2 2 2 3 4 5 6
c 4 3 3 3 2 3 4 5 6
e 5 4 3 4 3 2 3 4 5
p 6 5 4 4 4 3 2 3 4
u 7 6 5 5 5 4 3 2 3
24
t 8 7 6 6 6 5 4 3 2
Tabel 5.1: Exemplu de calculare a distanței Levenshtein
Deoarece funcția de similaritate trebuie să returneze o valoare între 0 și 1, este necesară o normalizare a distanței Levenshtein. Astfel, calcularea similarității bazate pe distanța Levenshtein se realizează în felul următor [1] :
! " ℎ $, % = ' ( 0 ,$||, ||% – +$, %
$||, ||% , ∈ [0, 1]
- |s| este lungimea cuvântului s;
- d(s, t) este distanța Levenshtein dintre s și t.
Distanța Jaro
Distanța Jaro se bazează pe numarul de caractere comune dintre cele două cuvinte care se compară și pozițiile în care acestea apar. Distanța Jaro dintre s și t este [2] :
./'0$, % = 1
3 (0$, %
|| + 0$, %
|| + 0$, % − "$, %
0$, % ,
- com(s, t) = numărul de caractere comune dintre s și t;
- inv(s, t) = numărul de perechi de caractere comune, dar aflate pe locuri diferite în s, respectiv t.
Exemplu: Să luăm în considerare cazul în care un cuvânt este tastat greșit, inversându-se două litere. Fie s = priceput, t = pricpeut.
Atunci, com(s, t) = 8, inv(s, t) = 1 și DistJaro(s, t) = 0.95.
Deoarece DistJaro(s, t) este deja normalizată, valorile rezultate găsindu-se în intervalul [0,1], SimJaro(s, t) = DistJaro(s, t).
25
5.2 Metode semantice
Funcțiile de similaritate semantică se folosesc de resurse lingvistice externe. Pentru ca aceste resurse să poată fi folosite cu succes, este nevoie ca, mai întâi, entitățile să treacă printr-un proces de normalizare semantică, ce poate să includă operații precum extragerea cuvintelor sau lematizarea. Foarte util pentru calcularea acestor tipuri de similarități este WordNet-ul [16], care poate oferi mulțimea sinonimelor, hipernimelor sau hiponimelor pentru un cuvânt dat.
Similaritate generală
Folosind numai cele trei tipuri de relații semantice de mai sus, se poate defini o funcție de similaritate simplă, SimSemantic(c1,c2), dar foarte utilă, unde c1 și c2 sunt două cuvinte. În contextul comparării a două entități, c1 și c2 pot fi numele entităților după normalizare sau pot reprezenta numai un anumit termen din cadrul denumirii unei entități.
45678$9, :% = ; 1, +'ă 9 ' =' + > : ' "
0.5, +'ă 9 ℎ= ' ℎ=0 ' : ' "
0, +'ă ' + '
A
SynSet-ul reprezintă mulțimea sinonimelor unui cuvânt.
Cosinonimia
Aceasta este o funcție de similaritate semantică, ce folosește numărul de elemente comune din SynSet-urile celor două cuvinte pentru care se calculează similaritatea.
8BC7$9, :% = | > $9% ∩ > $:%|
| > $9% ∪ > $:%| ∈ [0, 1]
Prezint și un exemplu [2] cu valori returnate de funcția 8BC7:
26
illustrator author creator person writer
illustrator 1 0 0 0 0
author 0 1 0 0 0.25
creator 0 0 1 0 0
person 0 0 0 1 0
writer 0 0.25 0 0 1
Tabel 5.2: Exemplu de valori pentru 8BC7
Alte distanțe semantice care pot fi folosite sunt: Leacock–Chodorow, Resnik sau Jiang–
Conrath. Acestea sunt prezentate și descrise mai pe larg în [17].
5.3 Metode bazate pe taxonomie
Acest tip de metode se bazează pe structura internă a ontologiei și nu pot fi folosite separat pentru o pereche de entități, în afara contextului ontologiilor în care se găsesc acestea. Prin acest tip de metode, se calculează distanțe între entități în taxonomia unei ontologii, dar tot aici am încadrat și măsurile de similaritate care se folosesc atât de informațiile oferite de taxonomie, cât și de unele similarități de tipul celor prezentate în subcapitolele anterioare, astfel făcându-se trecerea către metodele avansate. Cele mai multe se bazează pe relațiile de tipul instanță – concept sau concept – relație – concept.
Un exemplu de astfel de funcție este Simparents, care calculează media aritmetică dintre valorile similarităților pentru entitățile care sunt entități -părinte pentru cele date ca parametri ai funcției.
Dacă una dintre acestea nu are un părinte diferit de entitatea care reprezintă nodul radăcină, această funcție de similaritate nu va fi folosită în procesul de agregare.
Un alt exemplu este funcția SimdomRan, folosită pentru alinierea relațiilor și care, într-un mod similar cu cea de mai sus, returnează un scor care reprezintă media valorilor similarităților pentru conceptele din domeniul și codomeniul relației.
Mai multe astfel de metode, sunt prezentate în [2].
27
6. Metode avansate
După cum s-a văzut în capitolul anterior, se pot folosi numeroase și diverse măsuri de similaritate pentru o pereche de entități, dar utilizarea exclusivă a acestora își manifestă rapid limitele. Din această cauză, a apărut necesitatea cercetării unor metode de folosire cât mai eficientă a acestor măsuri de bază. În continuare, vor fi prezentate unele dintre cele mai de succes metode, insistându-se asupra celor folosite în sistemul de aliniere, care reprezintă finalitatea practică a acestei lucrări și asupra contribuțiilor originale aduse la îmbunătățirea unora dintre acestea.
6.1 Algoritmi genetici
Folosirea unui algoritm genetic în vederea îmbunătățirii unui aspect din procesul de aliniere sau a întregului proces, privit în ansamblu, prin metode descrise mai jos, este justificată prin numeroasele cazuri în care i s-a dovedit puterea de convergență către o soluție optimală, prin structura sa generală, care îi permite mularea pe diverse probleme de optimizare, prin flexibilitatea oferită de posibilitatea alegerii structurii de encodare a cromozomilor și a parametrizării. Spre exemplu, se poate alege o creştere a explorării în spațiul soluțiilor, prin mărirea probabilității cu care se efectuează mutația sau o creștere a explorării, prin scăderea acestei probabilități. Prin aceste aspecte, dar nu numai, s-a văzut eficiența algoritmului genetic, în defavoarea unor meta-euristici, precum hill-climbing sau simulated annealing.
6.1.1 Algoritmi genetici în alte sisteme
Sunt mai multe sisteme care se folosesc de algoritmii genetici, într-un fel sau altul. Dintre acestea, cele mai de succes sunt GOAM și GOAL.
GOAM nu se folosește deloc de măsurile de similaritate de bază. În cazul acestui sistem, algoritmul genetic este folosit în contextul găsirii unei alinieri cât mai bune peste spațiul entităților, pornind de la o potrivire aleatorie și neavând niciun fel de informație anterioară, ce ar putea fi furnizată de unele măsuri de bază. În această abordare, un cromozom este un vector
28
unidimensional, reprezentând entitățile din prima ontologie și având ca valori poziția elementelor dintr-un alt vector asociat entităților din cea de-a doua ontologie. Operatorii genetici sunt cei clasici, iar cel mai bun cromozom va reprezenta alinierea finală.
GOAL are ca scop utilizarea algoritmului genetic pentru a îmbunătăți funcția de similaritate generală, obținută pe baza măsurilor elementare. Aceast tip de abordare a stat la baza dezvoltării modulului de optimizare a agregării similarităților, care este folosit in sistemul de aliniere propriu.
6.1.2 Folosirea unui algoritm genetic pentru optimizarea agregării similarităților
Spre deosebire de alte sisteme, scopul folosirii algoritmului genetic în sistemul propriu a fost acela de a optimiza întregul proces de agregare, nu numai funcția de similaritate globală.
Odată calculate mai multe măsuri de similaritate, de la cele de tip sintactic, până la cele legate de structură, se pune problema agregării lor, în vederea obținerii unei similarități globale pentru o pereche de entități.
O metodă des folosită este media aritmetică a similarităților:
6$ 9, :% = ∑ 7G9 7$ 9, :%
O altă metodă este media ponderată:
6$ 9, :% = H I7∗ 7$ 9, :%
7G9
, H I7
7G9
= 1
Pi ∈ [0, 1] este o pondere, iar Simi(e1, e2) este o instanță a unei funcții de similaritate generală, care poate fi una dintre cele prezentate în această lucrare sau poate fi oricare alta, cu singura condiție ca aceasta să returneze un număr aflat în intervalul [0, 1].
În acest caz, se ridică problema stabilirii ponderilor. Dacă se dorește acordarea unei importanțe mai mari unei anumite măsuri de similaritate, se va devia de la media aritmetică, crescând ponderea atribuită acesteia, dar în același timp scăzând una sau mai multe alte ponderi, astfel încât suma ponderilor să rămână 1. Această distribuire a ponderilor se poate face de către
29
un expert uman, pe baza experienței sau prin încercări repetate, în urma cărora se evaluează rezultatele primite și se hotărăște stabilirea unor valori pentru ponderi.
Problema prezentată mai sus poate fi mai bine exprimată ca o problemă de optimizare. După cum am argumentat în introducerea subcapitolului 6.1, folosirea unui algoritm genetic este o abordare naturală pentru această problemă. Se dorește să se găsească cele mai bune ponderi pentru agregarea similarităților, astfel încât să se obțină cât mai multe alinieri corecte. Mai mult, se pot urmări diferite aspecte ale alinierilor, din punct de vedere al evaluării acestora, lucru exprimat prin diferitele funcții fitness ce pot fi folosite în evaluarea cromozomilor, acest aspect fiind prezentat mai jos în această secțiune.
Cu toate că s-au observat îmbunătățiri ale rezultatelor în urma folosirii algoritmului genetic, s-a constatat necesitatea de a se stabili de fiecare dată pragul la care o pereche de entități este catalogată drept aliniere sau nu.
= ℎ ' K 9, :L = M' , +'ă 6K 9, :L ≥ ='O
≠ ' , +'ă 6K 9, :L < ='OA
Deoarece apare o nouă problemă de optimizare, am hotărât introducerea pragului în codarea unui cromozom, pentru a permite și acestuia să evolueze împreună cu ponderile. Astfel, algoritmul genetic urmărește optimizarea procesului de aliniere privit în ansamblu, lucru care s-a dovedit a crește simțitor îmbunătățirea rezultatelor.
6.1.2.1 Codarea cromozomilor
După cum s-a prezentat și mai sus, înr-un cromozom sunt codate atât ponderile care sunt folosite pentru agregarea măsurilor de similaritate, cât și pragul față de care se stabilesc alinierile.
Așa cum se observă în figura 5.1, un cromozom este un șir de biți alcătuit din două părți. Prima parte constă într-o concatenare a reprezentării în biți a valorilor ponderilor, iar a doua este reprezentarea pragului.
30
Fig. 6.1 Codarea unui cromozom
ShLungime și ThLungime sunt parametrii care indică numărul de biți folosiți pentru codarea ponderilor, respectiv a pragului.
Lungimea unui cromozom, CrLungime, este dată de următorul calcul:
R!O = ∗ ℎ!ℎ + Sℎ!O
Pentru punerea în practică a acestei scheme de codare, este nevoie de verificarea și asigurarea respectării constrângerilor impuse asupra valorilor ponderilor și a pragului. În cazul ponderilor, după cum se arată și la începutul secțiunii 6.1.2, apare nevoia ca valorile acestora să fie situate în intervalul [0,1]. Constrângerea asupra pragului este dată de doi parametri, PrMin și PrMax, valoarea minimă, respectiv valoarea maximă pe care o poate avea pragul. Deoarece similaritatea agregată pentru o pereche de entități este o valoare înte 0 și 1, apare, în mod normal, impunerea apartenenței la acest interval şi a parametrilor PrMin și PrMax.
În actuala implementare, constrângerile prezentate au fost satisfăcute cu ajutorul librăriei Java, aflată sub licență publică, GaFrame [13]. Metodele folosite sunt următoarele:
Pentru codare: java.util.BitSet doubleToBitSet(java.util.BitSet bitSet, int offset, int length, double minValue, double maxValue, double value),
• bitSet, obiectul BitSet, în care se va regăsi valoarea double ce se dorește convertită;
• offset, poziția față de primul bit din BitSet, de unde se va începe codarea;
• length, numărul de biți folosit pentru reprezentarea valorii double (ex.
ShLungime, ThLungime);
31
• minValue, valoarea minimă a numărului ce va fi reprezentat de BitSet;
• maxValue, valoarea maximă a numărului ce va fi reprezentat de BitSet;
• value, numărul propriu-zis care va fi codificat.
Pentru decodare: double bitSetToDouble(java.util.BitSet bitSet, int offset, int length, double minValue, double maxValue),
• bitSet , BitSet-ul ce se dorește a fi decodificat;
• offset, față de primul bit din BitSet, de unde se va începe decodarea;
• length, numărul de biți care vor fi citiți începând de la poziția de offset și care reprezintă valoarea double returnată;
• minValue, valoarea minimă a numărului ce va fi decodificat;
• maxValue, valoarea maximă a numărului ce va fi decodificat.
6.1.2.2 Selecția cromozomilor
Am testat mai multe scheme de selecție, printre care selecția bazată pe rang și selecția de tip roata norocului. În urma mai multor teste, în care am folosit mai multe perechi de ontologii și mai multe măsuri de similaritate, cel din urmă s-a dovedit a produce rezultatele cele mai bune.
Acest lucru poate fi explicat prin faptul că valorile funcției fitness nu variază mult, ceea ce înseamnă că nu va exista un cromozom sau un grup de cromozomi, care să fie în mod semnificativ mai bun decât ceilalți cromozomi din populație. Acesta ar fi fost principalul neajuns al acestei metode, deoarece, în cazul în care ar fi un grup de cromozomi care ar da o valoare a funcției fitness mult mai mare decât ceilalți, s-ar ajunge la o convergență prematură. Mai mult, selecția bazată pe rang, care sortează cromozomii în funcție de valoarea returnată de funcția fitness, nu reușește să mărească șansa pentru cei mai buni cromozomi de a fi reprezentați în generația următoare, deoarece numai puțini dintre ei se distanțează de restul. Acest tip de comportament poate fi legat de natura problemei de optimizare abordate.
32 .
Figura 6.2 : Selecție de tipul roata norocului
Selecția de tipul roata norocului prezentată în figura 5.2 poate fi descrisă pe scurt prin următorii pași:
• Întâi, se calculează S, suma valorilor funcției fitness pentru toți cromozomii din populație;
• Apoi, se generează un număr aleatoriu r, în intervalul (0, S);
• Se iterează prin cromozomii din populație, adăugându-se valoarea fitnessului fiecăruia dintre aceștia la suma s. Se oprește când s > r. Ultimul cromozom al cărui fitness a fost adăugat la s este returnat.
6.1.2.3 Operatori genetici
Metoda de încrucișare ia, la intrare, doi cromozomi numiți părinți și returnează doi cromozomi copii, obținuți prin amestecarea genelor părinților. Încrucișarea este aplicată cu o anumită probabilitate, parametru al algoritmului genetic. Se testează această probabilitate de două ori pentru fiecare cromozom-părinte, nu o singură dată, ca într-un algoritm genetic tipic. Se face acest lucru o dată pentru prima parte a șirului de biți, care reprezintă ponderile pentru funcțiile de similaritate și o a doua oară pentru partea în care este codat pragul. Se folosește o încrucișare cu două puncte de tăiere, așa cum este prezentată și în figura 6.3.
33
Figura 6.3 : Încrucișarea cromozomilor
Pentru o mai bună înțelegere, voi detalia un caz în care se aplică operatorul de încrucișare. Fie p numărul de biți folosiți pentru codarea tuturor ponderilor, p = n * PoLungime și q = PrLungime, unde n, PoLungime și PrLungime, are înțelesurile din secțiunea 6.1.2.1. Fie r1 și r2,
cu 0 < r1 < p, respectiv 0 < r2 < q, cele două puncte de tăiere alese aleatoriu. Primul copil este obținut copiind primii r1 biți ai primului cromozom, la care se adaugă următorii p – r1 biți din al doilea cromozom-părinte, urmați de biții dintre p și p + r2 din primul cromozom și ultimii p + q – r2 biți din al doilea. Al doilea copil are aceiași biți în prima parte ca primul, iar în partea corespunzătoare pragului are biții dintre p și p + r2 din al doilea cromozom, urmați de ultimii p + q – r2 biți ai primului cromozom. Fiii doi și trei au primii r1 biți din al doilea cromozom și următorii p – r1 biți din al doilea pentru prima parte, iar în partea a doua se găsește aceeași combinație ca în cazul primilor doi fii.
Deoarece se dorește păstrarea unui număr constant de cromozomi în populație pe parcursul generațiilor, pentru a trece în generația următoare, vor fi aleși cei mai buni doi dintre cei patru fii rezultați în urma procesului de încrucișare.
Nu este permis ca părinții aflați la intrarea procesului de încrucișare să fie același cromozom.
Cu toate că aceasta nu este neapărat un lucru interzis, este probabil să conducă la o convergență prematură. Pentru a preveni survenirea acestui eveniment, se selectează întâi un singur cromozom
34
din populație, după schema de selecție descrisă în secțiunea 6.1.2.3, iar apoi se execută procesul de selecție într-o buclă, până când este returnat un cromozom diferit.
Mutația cromozomilor asigură diversitatea în populație și previne convergența prematură. În această abordare, am folosit o versiune iterată de mutație. Pentru fiecare bit din cromozom, se testează dacă se aplică mutația și, dacă se întâmplă acest lucru, atunci acel bit este negat.
6.1.2.4 Funcția fitness
Funcția fitness evaluează calitatea alinierilor obținute, folosind pragul și ponderile rezultate în urma decodificării cromozomului. Funcția fitness poate fi una dintre următoarele: Precision, Recall, F-Measure. Acestea sunt măsurile cele mai des întâlnite în domeniul extragerii informațiilor și vor fi prezentate pe larg în capitolul dedicat evaluării ontologiilor.
6.1.2.5 Structura generală a algoritmului și îmbunătățiri suplimentare
Algoritmul urmărește structura clasică a unui algoritm genetic, dar fiecare pas este adaptat pentru a se potrivi cât mai bine problemei curente.
O populație inițială de dimensiune popSize cromozomi este generată aleatoriu. Atât timp cât un anumit număr de generații maxGen nu a fost încă atins și se observă o îmbunătățire a funcției fitness în cazul celui mai bun cromozom din ultimele maxGen / 2 generații, sunt executați următorii pași:
• Este creată o nouă populație vidă;
• Sunt selectați doi cromozomi din populația reprezentată de ultima generație, folosindu-se selecția de tipul roata norocului ;
• Se aplică încrucișarea cu probabilitatea stabilită în prealabil, în urma căreia vor rezulta doi fii, după procesul detaliat în secțiunea 6.1.2.4;
• Asupra fiecărui fiu se aplică operatorul de mutație cu probabilitatea rezervată apariției acestui eveniment;
• Cei doi cromozomi sunt introduși în noua populație ;
• Ultimii patru pași sunt executați până când noua populație conține popSize cromozomi;
• Se evaluează cromozomii din noua populație în raport cu funcția fitness aleasă;
35
• Se alege cel mai bun cromozom din populația nouă și se compară cu cel mai bun cromozom din generația precedentă.
Soluția este dată de cel mai bun cromozom din ultima generație.
O îmbunătățire adusă schemei de mai sus a fost introducerea elitismului. Înainte de a selecta vreun cromozom, cei mai buni (elitePercent * popSize) / 100 cromozomi din populația curentă sunt trecuți nealterați în populația următoare. Această strategie asigură supraviețuirea celor mai buni cromozomi din fiecare generație. Pentru a păstra diversitatea populației, această metodă este folosită împreună cu probabilitatea mutației ușor mai ridicată.
O altă îmbunătățire, dar folosită ca schemă generală alternativă, este turneul. Aceasta presupune pornirea consecutivă a unui număr de 2n algoritmi genetici, unde n variază de regulă între 1 și 3. Cei mai buni popSize / 2 cromozomi din fiecare ultimă generație dată de algoritmii genetici se grupează astel încât se formează 2n-1 populații, care vor reprezenta populațiile inițiale pentru o nouă serie de algoritmi genetici. După cum se observă și în exemplul din figura 6.4, aceste etape se execută până când se ajunge la o singură populație.
Cel mai bun cromozom din ultima generație obținută prin aplicarea algoritmului genetic asupra acestei populații este soluția returnată de schema de turneu:
Figura 6.4: Schemă turneu cu 4 populații inițiale
36
Deoarece se aplică algoritmul genetic de mai multe ori în cadrul acestei scheme, acesta va implica un număr mai scăzut de generații decât în cazul în care se folosește o singură dată algoritmul genetic. Un exemplu de valoare pentru numărul de generații pentru un algoritm genetic din cadrul schemei turneu este NrGen / 2 * n, unde NrGen este numărul de generații utilizat în cazul obișnuit, în care se folosește algoritmul genetic o singură dată, iar n este cel din contextul de mai sus.
6.1.2.6 Rezultate obținute
Testele au fost efectuate folosindu-se ontologii construite special pentru evaluarea alinierilor [12]. Aceste perechi de ontologii, care se găsesc în tabelul 6.1, sunt însoțite și de o aliniere realizată manual, care este folosită drept standard gold pentru precision și recall.
Pentru teste, am folosit următoarele funcții de similaritate: SimLevenshtein SimJaro, SimSemantic și SimdomRan. După mai multe teste și rulări, am lăsat următorii parametri : PoLungime = 15, PrLungime = 20, popSize = 100, maxGen = 200, elitePercent = 10, crossoverProbability=
0.95, mutationProbability = 0.07. Pentru aceste teste s-a folosit elitismul, dar nu și schema de tip turneu.
Nr.
Pereche
Ontologie 1 Ontologie 2
1. animalsA.owl animalsB.owl
2. hotelA.owl hotelB.owl
3. people+petsA.owl people+petsB.owl
4. russiaA.owl russiaB.owl
5. networkA.owl networkB.owl
Tabel 6.1: Ontologii folosite în testele pentru algoritmul genetic
În tabelul 6.2, sunt prezentate Precision (P), Recall (R) și F-measure, obținute folosindu-se media aritmetică a similarităților menționate mai sus, o metodă obișnuită de agregare și un prag fix cu valoarea de 0.75 și aceleași funcții de evaluare calculate cu ponderile și pragul rezultate în urma rulării algoritmului genetic. Ultimele se regăsesc în coloanele P(GA),
R(GA), respectiv F(GA). Se observă o îmbunătă 6.25% pentru Recall și 7.33% pentru
Nr.
Pereche Ontologii
Precision
1. 0.8947
2. 0.8571
3. 0.8471
4. 0.8655
5. 0.8891
Rezultatele întoarse de aceste func
similaritate folosite. Din această cauză, prin aceste teste, am pus accentul pe îmbunătă aduse de algoritmul genetic
În figura 6.5, este prezentat un grafic cu îmbunătă funcții de evaluare în parte.
Figura 6.5: Grafic cu
În al doilea test, am dorit să simulez un scenariu din lumea reală, în care, având o pereche de ontologii împreună cu alinierea realizată manual, am folosit algoritmul genetic, în urma
37
R(GA), respectiv F(GA). Se observă o îmbunătățire medie de 8.46% pentru i 7.33% pentru F-measure.
Precision (AG)
Recall Recall (AG)
F Measure
0.9764 0.9045 0.9239 0.8995
0.9473 0.75 0.7916 0.7999
0.9203 0.89261 0.9127 0.8692
0.9158 0.8119 0.8440 0.8378
0.9273 0.8624 0.9052 0.8755
Tabel 6.2: Rezultate comparative
Rezultatele întoarse de aceste funcții de evaluare sunt strâns legate de funcțiile de similaritate folosite. Din această cauză, prin aceste teste, am pus accentul pe îmbunătă aduse de algoritmul genetic și nu pe rezultatele propriu-zise.
.5, este prezentat un grafic cu îmbunătățirile suferite de fiecare dintre cele trei ții de evaluare în parte.
.5: Grafic cu îmbunătățirile obținute cu ajutorul algoritmului genetic
În al doilea test, am dorit să simulez un scenariu din lumea reală, în care, având o pereche de ontologii împreună cu alinierea realizată manual, am folosit algoritmul genetic, în urma țire medie de 8.46% pentru Precision, de
- Measure
F –
Measure (AG) 0.9494 0.8624 0.9164 0.8784 0.9161
ții de evaluare sunt strâns legate de funcțiile de similaritate folosite. Din această cauză, prin aceste teste, am pus accentul pe îmbunătățirile
țirile suferite de fiecare dintre cele trei
țirile obținute cu ajutorul algoritmului genetic
În al doilea test, am dorit să simulez un scenariu din lumea reală, în care, având o pereche de ontologii împreună cu alinierea realizată manual, am folosit algoritmul genetic, în urma
