UNIVERSITATEA TEHNICĂ “GHEORGHE ASACHI” DIN IAŞI Facultatea de Automatică şi Calculatoare

Modele şi Algoritmi de Web Mining

- REZUMATUL TEZEI DE DOCTORAT -

Conducător de doctorat: Prof. univ. dr. Mitică Craus

Doctorand: Ing. Ioan Agavriloaei

IAŞI – 2012

UNIUNEA EUROPEANĂ GUVERNUL ROMÂNIEI

MINISTERUL MUNCII, FAMILIEI ŞI PROTECŢIEI SOCIALE

AMPOSDRU

Fondul Social European

POSDRU 2007-2013

Instrumente Structurale

2007-2013 OIPOSDRU UNIVERSITATEA TEHNICĂ

“GHEORGHE ASACHI” DIN IAŞI

UNIUNEA EUROPEANĂ GUVERNUL ROMÂNIEI

MINISTERUL MUNCII, FAMILIEI ŞI PROTECŢIEI SOCIALE

AMPOSDRU

Fondul Social European

POSDRU 2007-2013

Instrumente Structurale

2007-2013 OIPOSDRU UNIVERSITATEA TEHNICĂ

“GHEORGHE ASACHI” DIN IAŞI

UNIUNEA EUROPEANĂ GUVERNUL ROMÂNIEI

MINISTERUL MUNCII, FAMILIEI ŞI PROTECŢIEI SOCIALE

AMPOSDRU

Fondul Social European

POSDRU 2007-2013

Instrumente Structurale

2007-2013 OIPOSDRU UNIVERSITATEA TEHNICĂ

“GHEORGHE ASACHI” DIN IAŞI

Teza de doctorat a fost realizată cu sprijinul financiar al proiectului

„Burse Doctorale pentru Performanţa în Cercetare la Nivel European

(EURODOC)”.

Proiectul „Burse Doctorale pentru Performanţa în Cercetare la Nivel

European (EURODOC)”, POSDRU/88/1.5/S/59410, ID 59410, este un

proiect strategic care are ca obiectiv general „Dezvoltarea capitalului

uman pentru cercetare prin programe doctorale pentru îmbunătățirea

participării, creșterii atractivității şi motivației pentru cercetare.

Dezvoltarea la nivel european a tinerilor cercetători care să adopte o

abordare interdisciplinară în domeniul cercetării, dezvoltării şi

inovării.”.

Proiect finanţat în perioada 2009 - 2012.

Finanţare proiect: 18.943.804,97 RON

Beneficiar: Universitatea Tehnică “Gheorghe Asachi” din Iaşi

Partener: Universitatea „Babeş Bolyai” din Cluj-Napoca

Director proiect: Prof. univ. dr. ing. Mihaela-Luminiţa LUPU

Responsabil proiect partener: Prof. univ. dr. ing. Alexandru OZUNU

i

Cuprins

Cuprins i

1. Introducere 1

1.1 Motivaţia cercetării ............................................................................................................... 1 1.2 Obiectivele cercetării ............................................................................................................ 2

1.3 Organizarea tezei .................................................................................................................. 3 1.4 Diseminarea rezultatelor ....................................................................................................... 5

2. Concepte teoretice fundamentele de Web data mining 7

2.1 Data mining .......................................................................................................................... 7 2.1.1 Învăţarea supervizată (clasificarea) ......................................................................... 8 2.1.2 Învăţarea nesupervizată (clusterizarea) ................................................................... 9

2.2 Web data mining ................................................................................................................. 12

2.2.1 Web structure mining ............................................................................................ 12

2.2.2 Web content mining ............................................................................................... 14 2.2.3 Web usage mining ................................................................................................. 16

3. Stadiul actual al cunoaşterii în Web mining 17

3.1 Stadiul actual în Web structure mining .............................................................................. 17 3.2 Stadiul actual în Web content mining ................................................................................ 17

4. Studiu metricilor de evaluare având în vedere modul în care utilizatorii efectuează o

căutare 19

4.1 Formularea problemei ........................................................................................................ 19

4.2 Metodologie şi metrici ........................................................................................................ 19 4.2.1 Regăsirea ad-hoc ................................................................................................... 20

4.2.2 Regăsirea diversificată ........................................................................................... 20

5. Noi modele şi algoritmi pentru clusterizarea şi căutarea pe Web 21

5.1 Modelarea documentelor Web............................................................................................ 21 5.1.1 Ponderea termenilor ............................................................................................... 21 5.1.2 Reprezentarea documentelor web .......................................................................... 22

5.2 Combinarea dependenţei, relevanţei şi structurii pentru regăsirea pe Web eficientă ......... 23 5.2.1 Formularea problemei ............................................................................................ 23

5.2.2 Model hibrid de regăsire ad-hoc a informaţiei ...................................................... 23

5.3 Algoritm de clusterizare a unui site .................................................................................... 24 5.4 Concluzii ............................................................................................................................. 26

6. Evaluare 27

6.1 Studiul metricilor de evaluare folosite în regăsirea informaţie având în vedere modul în

care utilizatorii efectuează o căutare ........................................................................................ 27 6.1.1 Comparaţia metricilor ............................................................................................ 27 6.1.2 Rezultate şi discuţii ................................................................................................ 27

6.2 Evaluarea modelării şi clusterizării documentelor web ...................................................... 29 6.2.1 Metrici folosite pentru comparaţie ........................................................................ 29 6.2.2 Rezultate şi discuţii ................................................................................................ 29

6.3 Evaluarea regăsirii informaţiei ........................................................................................... 32

ii

6.3.1 Configurarea simulării ........................................................................................... 32 6.3.2 Determinarea parametrilor optimi ......................................................................... 33

6.3.3 Rezultate şi discuţii ............................................................................................... 35 6.3.4 Concluzii ............................................................................................................... 37

7. Concluzii 39

7.1 Concluzii generale .............................................................................................................. 39 7.2 Contribuţii ştiinţifice şi valorificarea rezultatelor .............................................................. 40

7.3 Direcţii viitoare .................................................................................................................. 42

Bibliografie 43

1

1. Introducere

1.1 Motivaţia cercetării

Datorită creşterii rapide şi haotice a Web-ului, reţeaua de informaţii rezultată a suferit la capitolul

organizare şi structură, conţinutul informaţional fiind disponibil în diverse formate. Evoluţia

continuă a dimensiunii şi utilizării Web-ului a avut drept consecinţă directă apariţia diferitelor

provocări, precum stocarea informaţiei sau dificultatea extragerii cunoştinţelor utile. Problemele care

au trebui să fie soluţionate sunt regăsirea informaţiei relevante, care implică căutarea şi indexarea

conţinutului web, crearea unor meta cunoştinţe din informaţiile disponibile pe Web, precum şi

tratarea intereselor şi nevoilor utilizatorilor prin personalizarea informaţiilor şi serviciilor oferite.

Termenul de Web mining a fost introdus odată cu explozia Web-ului de la mijlocul anilor 1990,

pentru a confirma aplicarea tehnicilor de data mining pentru extragerea de cunoştinţe din conţinutul

(Web content mining), structura (Web structure mining) şi utilizarea (Web usage mining) datelor web

prin intermediul regăsirii automate a paginilor şi serviciilor web, extragerea de informaţii din

resursele web şi descoperirii de modele în cadrul Web-ului. Aşadar, Web mining este un domeniu

convergent de cercetare, care cuprinde diferite aspecte ale unor arii de cercetare deja consacrate cum

ar fi bazele de date, regăsirea informaţiei (Text REtrieval Conference, TREC), inteligenţa artificială,

învăţărea automată, text mining, etc. Principiile lor sunt abordate şi adaptate în Web mining pentru a

face faţă noilor provocări. Cel mai evident domeniu care a trebuit să se adaptateze noilor condiţii a

fost regăsirea informaţiei, luând astfel naştere regăsirea informaţiei pe Web (Web information

retrieval). Cercetările din acest domeniu au dus la crearea unui nou instrument web, anume motorul

de căutare, care a transformat activitatea de regăsire a informaţiei într-o activitate zilnică pentru

orice persoană care utilizează un calculator.

Creşterea volumului de informaţie a generat noi provocări în prelucrarea eficientă a informaţiei

noi descoperite sau reactualizarea datelor deja cunoscute. A discuta despre Web este o sarcină

dificilă din mai multe motive. În primul rând, datorită conţinutului dinamic, se poate spune că

subiectul şi conţinutul unei pagini web nu vor mai fi de actualitate până când ajung la utilizatorul

final, deoarece adresa URL care face referire la informaţia în sine poate fi rescrisă sau chiar

redirectată între timp. Apoi, o abordare realistă şi acoperirea tuturor subiectelor de interes pentru

utilizatorii finali este imposibilă deoarece noi idei şi subiecte sunt propuse în mod continuu, fiind

acceptate sau respinse de comunitatea virtuală. Un alt motiv este acela că există tendinţa puternică de

a prezenta subiecte strans legate de trecutul autorului lor, astfel acordând-se importanaţă subiectelor

şi legaturilor de care acestea sunt conectate.

Ceea ce diferenţiază Web-ul de alte colecţii de documente este faptul că, în afară de

documentele pe care le conţine, este puternic caracterizat de hiper-legăturile care inter-conectează

aceste documente. Informaţiile furnizate către utilizatori sunt de tip text, imagini, date audio sau

video precum şi date structurate (tabele şi liste). Majoritatea documentelor web sunt în format

HTML (HyperText Markup Language) conţinâd tag-uri sau etichete folosite la formatare, astfel

aplicaţiile de Web mining trebuie să parseze documentele HTML eliminând părţile care nu prezintă

interes din punct de vedere informaţional. O problemă comună a sistemelor de regăsire o reprezintă

2

modelarea documentelor. De regulă, un document necesită prelucrări preliminare pentru a extrage

din el informaţii relevante într-un format eficient şi util, astfel încât documentul să fie procesat în

mod automat de către sistemul de regăsire. O problemă deschisă în acest domeniu o reprezintă

descoperirea caracteristicilor esenţiale şi definitorii care dau importanţa şi greutatea informaţiei

furnizate de o pagină web.

De asemenea, datorită caracterului dinamic a conţinutului web, se impune o structurare şi o

analiză prealabilă a documentelor web, astfel încât datele prezentate utilizatorului fie să ofere un

răspuns rapid şi concludent la o anumită interogare, fie să ofere o varietate de răspunsuri relevante

pentru o interogare ambiguă.

Importanţa evaluării sistemelor de regăsire a fost recunoscută încă de la începutul cercetării

acestui domeniu şi are un rol cheie în îndeplinirea scopului final. Cel mai important instrument al

evaluării îl reprezintă colecţia de test: o colecţie de documente cu un set de subiecte şi judecăţi care

indică ce document este relevant relativ la un subiect. Evaluarea prin această metodă şi-a dovedit

utilitatea în urmă cu zece ani, odată cu explozia volumului informaţional, când eficienţa şi

fiabilitatea rezultatelor a început să fie investigată în mod oficial. Deşi au mai fost create colecţii de

test pentru Web, datorită lipsei puterii de calcul, o colecţie reprezentativă şi reală pentru Web nu a

fost creată decât în 2009, anume colecţia ClueWeb09. Astfel, a apărut posibilitatea investigării

tehnicilor curente de Web mining şi a unora noi având ca suport o colecţie de test care reprezintă o

bună parte din contextul actual al Web-ului.

Existând atâtea provocări ale Web-ului şi cerinţe diverse din partea consumatorilor de

informaţie, această lucrare se concentrează pe metodele care duc la o creştere a eficienţei de

modelare, organizare şi regăsire a informaţiei utile în contextul Web, pentru a satisface, în final,

nevoia tot mai crescută şi diversificată, de informaţie a utilizatorilor.

1.2 Obiectivele cercetării

Obiectivul general al acestei cercetări este acela de a contribui la îmbunătăţirea tehnicilor actuale de

Web mining prin modelarea şi structurarea conţinutului web, precum şi analiza, modelarea şi

optimizarea sistemelor de regăsire a informaţiei. Datorită diverselor abordări atunci când vine vorba

de modelarea documentelor web, precum şi din cauza multitudinii de scopuri pentru care se iniţiază

un proces de regăsire, această lucrare a abordat următoarele direcţii de cercetare:

Analiza critică a stadiului actual al cunoaşterii în Web mining din punct de vedere al:

principalelor tehnici de învăţare utilizate: învăţarea supervizată (clasificarea) şi învăţarea

nesupervizată (clusterizarea);

tehnicilor fundamentale de modelare a termenilor, documentelor şi interogărilor web,

precum şi a modalităţii de calcul al relevanţei acestora: modele non-lingvistice şi modele

lingvistice;

metodelor şi metricilor de evaluare;

principalelor direcţii de regăsire a informaţiei: regăsirea ad-hoc şi cea diversificată.

Modelarea eficientă a termenilor unui document şi a documentului în sine, cu scopul de a

reprezenta informaţia valoroasă cât mai bine. Pentru a atinge acest scop se are în vedere

3

normalizarea termenilor în cadrul modelării documentelor web, utilizarea tag-urilor HTML

în definirea ponderii locale a unui termen şi utilizarea legăturilor care există între

documentele web pentru a reprezenta eficient o pagină web.

Organizarea conţinutului web prin elaborarea şi evaluarea unui algoritm de clusterizare

pentru structurarea unei colecţii reduse de documente web, în vederea regăsirii informaţiei

relevante.

Investigarea relaţiilor dintre diferite metrici de evaluare pentru regăsirea informaţiei cu

scopul de a determina care dintre metrici măsoară în mod fidel nevoia de informaţie a

utilizatorului. Un alt obiectiv al acestui studiu este de a produce câteva referinţe pentru

viitoarele experimente care vizează regăsirea ad-hoc şi diversificată a informaţiei.

Modelarea sistemelor de regăsire ad-hoc a informaţiei printr-un nou model hibrid de

regăsire, care cuprinde două modele consacrate (modelul de dependenţă şi cel de relevanţă),

un model nou, bazat pe câmpuri şi un model de filtrare a spam-ului, cu menirea de a

îmbunătăţi performanţa de regăsire. Acestă abordare are și scopul de a obţine a unei

perspective asupra rolului pe care documentele structurate web (care au în structura lor tag-

uri HTML sau adnotări definite) îl pot avea în creşterea eficienţei sistemelor actuale de

regăsire a informaţiei. Mai mult, odată cu introducerea modelului de filtrare a spam, se

investighează şi efectul spam-ului asupra rezultatelor regăsirii. În acelaşi timp, prin evaluarea

şi analiza pertinentă a rezultatelor, se urmăreşte confirmarea sau informarea afirmaţiei:

„există o relaţie de aditivitate între numărul de tehnici folosite şi eficienţa de regăsire

realizată” (Armstrong, et al., 2009). În final, se doreşte analiza modelului abordat şi din

perspectiva regăsirii diversificate.

1.3 Organizarea tezei

Această lucrare este compusă din 7 capitole, fiecare capitol conținând diferite aspecte ale temei

abordate.

În capitolul 1 sunt prezentate într-un mod concis motivaţia temei abordate, obiectivele propuse,

contribuţiile ştiinţifice, structura şi conţinutul tezei, iar la final, lucrările publicate.

Capitolul 2 prezintă cele mai utilizate concepte din cadrul Web data mining, care sunt apoi

utilizate pe parcursul acestei lucrării. Întâi de toate, în secţiunea 2.1, este definită noţiunea de

descoperire a cunoştinţelor şi a componentei sale fundamentale – data mining-ul, care stă la baza

acestei lucrări. Pe baza acestui concept şi ca o consecinţă a apariţiei şi dezvoltării Web-ului, în

secţiunea 2.2, este introdusă o nouă noţiune, şi anume noţiunea de Web data mining. Acest concept

constituie motivaţia principală a tezei. Abordarea acestei noţiuni se face din prisma structurii şi

conţinutului prin intermediul regăsirii informaţiei. Secţiunea 2.2.1 analizează sintetic modul de

structurare a Web-ului şi prezintă o sinteză a celor mai cunoscuţi algoritmi care iau în calcul analiza

legăturilor dintre paginile web. În cadrul secţiunii 2.2.2 se prezintă conţinutul Web din perspectiva

regăsirii informaţiei prin rezumarea principiilor fundamentale care stau la baza regăsirii informaţiei,

a modelelor de reprezentare a documentelor web (rezultate sintetizate parţial şi în (Agavriloaei &

Craus, 2010)), a metodelor şi metricilor de evaluare şi a principalelor avantaje şi dezavantaje care

rezultă din modelarea sistemelor de regăsire. În acelaşi timp, sunt clarificate şi ideile de clasificare şi

4

clusterizare a documentelor text şi web. În cele din urmă, capitolul se încheie cu o scurtă discuţie

despre provocările Web-ului, acesta fiind principalul suport al cercetărilor prezentate în această teză.

În capitolul 3 se prezentă cele mai importante cercetări referitoare la subiectele acestei teze sau

la unele aspecte ale lor. Astfel, sunt examinate ipotezele, aplicaţiile şi provocările Web structure şi

Web content mining. Cea mai mare atenţie este acordată lucrărilor care au răspuns unor provocări

majore, au lansat noi abordări sau au primit o atenţie semnificativă din partea comunităţii ştiinţifice

internaţionale. Secţiunea 3.1 sintetizează diferitele abordări ale celor doi algoritmi principali utilizaţi

pentru structurarea Web-ului, în timp ce în secţiunea 3.2 se face o cercetare a abordărilor actuale

care tratează modelarea, organizarea şi regăsirea informaţiei relevante.

O contribuţie importantă este prezentată în capitolul 4 sub forma unui studiu comparativ, în

care sunt stabilite câteva elemente de referinţă ale cercetării în regăsirea informaţiei. Studiul are

drept scop investigarea relaţiilor dintre diferitele metrici de evaluare prin intermediul experimentelor

prezentate la TREC 2011, precum şi a celor de referinţă, care utilizează un model de regăsire non-

lingvistic. Scopul acestui studiu este de a analiza modul în care regăsirea ad-hoc şi cea diversificată

reflectă performanţa de căutare a utilizatorului. Rezultatele dovedesc faptul că există două direcţii

distincte în evaluarea regăsirii informaţiei: unele metrici urmăresc o precizie mare a listei returnate,

iar altele au drept finalitate captarea unui aspect mai sumar al performanţei.

Capitolul 5 conţine cea mai mare parte a contribuţiilor originale ale acestei teze. În secţiunea

5.1 este propusă o nouă reprezentare a a unui document web (Agavriloaei, et al., 2011a) folosind o

normalizare a termenilor, o nouă definiţie a ponderii locale a termenilor, care ţine cont de tag-urile

HTML şi luând în considerare legăturile dintre documentele web. Pe baza modelului de document

web oferit, se propune un algoritm de clusterizare pentru structurarea unei colecţii reduse de

documente, cu scopul de a pune în valoare informaţia utilă. În secţiunea 5.3, este introdus modelul

matematic care are la bază cercetările din (Agavriloaei, et al., 2011a) şi (Agavriloaei & Craus,

2011b). În secţiunea 5.2 se propune un nou model hibrid de regăsire a informaţiei, care are drept

scop obţinerea unei perspective noi asupra rolului pe care documentele structurate web îl pot avea în

creşterea eficienţei sistemelor actuale de regăsire. Totodată, se face o sinteză a modelelor de regăsire

folosite de comunitatea ştiinţifică pentru a scoate în evidenţă unele lipsuri şi neajunsuri pe care

modelul propus le satisface. Modelul propus are la bază cercetările din (Agavriloaei, et al., 2012)

unde se investighează efectul asupra performanţelor în cazul regăsirii ad-hoc.

În cadrul capitolului 6 sunt analizate rezultatele experimentale ale aplicării modelelor, soluţiilor

de organizare, evaluare şi regăsire a informaţiei propuse în capitolele 4 şi 5, rezultate publicate în

lucrările (Agavriloaei, et al., 2011a), (Agavriloaei & Craus, 2011b) şi (Agavriloaei, et al., 2012). În

secţiunea introductivă sunt examinate rezultatele tehnicilor propuse asupra cărora se fac aprecieri şi

critici pertinente. Ultima secţiune a capitolului prezintă concluziile rezultatelor obţinute şi indică

unele avantaje şi dezavantaje care vor putea fi abordate în cercetările ulterioare.

Capitolul 7 este dedicat prezentării sumare a rezultatelor obţinute şi a ideilor principale care se

desprind din aspectele teoretice şi practice ale cercetărilor efectuate în domeniul Web mining. Apoi,

sunt evidenţiate contribuţiile originale aduse în această lucrare pentru modelarea, organizarea,

5

evaluarea şi regăsirea informaţiei pe Web. Finalul capitolului cuprinde câteva propuneri de cercetări

viitoare care provin din rezultatele obţinute.

1.4 Diseminarea rezultatelor

Rezultatele cercetărilor prezentate în această teză au fost validate prin publicarea a 7 lucrări la

conferinţe şi reviste ştiinţifice, precum şi a 3 lucrări elaborate în cadrul studiilor doctorale, astfel:

reviste B+ (2), volume ale conferinţelor internationale indexate IEEE Xplore (3), volume ale

conferinţelor internationale (1) şi reviste ISI (1).

Ioan Agavriloaei, Andreas Rauber şi Mitică Craus. Combination of Dependence, Relevance

and Structure for Effective Web Retrieval. Publicat în Journal of Applied Sciences, vol.

12(19), pg. 2035-2043, septembrie 2012 (indexat ISI Web of Knowledge, SCOPUS).

Ioan Agavriloaei, Adrian Alexandrescu şi Mitică Craus. Improving web clustering through

a new modeling for web documents. Publicat în Proceedings of 15th International Conference

on System Theory, Control, and Computing (ICSTCC 2011), pg. 1–6, Octombrie 2011,

Sinaia, România. ISBN: 978-1-4577-1173-2 (indexat IEEE Xplore).

Ioan Agavriloaei, Mitică Craus şi Adrian Alexandrescu. Performance Evaluation of a Two-

Step Clustering Method. Publicat în Buletinul Institutului Politehnic din Iaşi, vol. Tome LVII

(LXI), no. Fasc. 2, secţia Automatică şi Calculatoare, pg. 31–43, 2011. ISSN: 1220-2169

(revistă BDI, cotată CNCSIS categoria B+).

Adrian Alexandrescu, Ioan Agavriloaei şi Mitică Craus. A Genetic Algorithm for Mapping

Tasks in Heterogeneous Computing Systems. Publicat în Proceedings of 15th International

Conference on System Theory, Control, and Computing (ICSTCC 2011), pg. 1–6, Octombrie

2011, Sinaia, România. ISBN: 978-1-4577-1173-2 (indexat IEEE Xplore).

Adrian Alexandrescu, Mitică Craus şi Ioan Agavriloaei. Determining the Best Mutation

Probabilities of a Genetic Algorithm for Mapping Tasks. Publicat în Buletinul Institutului

Politehnic din Iasi, vol. Tome LVII (LXI), no. Fasc. 2, secţia Automatică şi Calculatoare, pg.

21–30, 2011. ISSN: 1220-2169 (revistă BDI, cotată CNCSIS categoria B+).

Adrian Alexandrescu, Ioan Agavriloaei şi Mitică Craus. A Task Mapping Simulation

Framework for Comparing the Performance of Mapping Heuristics in Various Scenarios.

Acceptat în Proceedings of 16th International Conference on System Theory, Control, and

Computing (ICSTCC 2012), pg. 1–6, Octombrie 2012, Sinaia, România. (indexat IEEE

Xplore).

Ioan Agavriloaei şi Mitică Craus. An Analysis of Web Clustering. Publicat în Proceedings of

6th European Conference on Intelligent Systems and Technologies (ECIT 2010), pg. 1–6,

Octombrie 2010, Iaşi, România. ISSN: 2069-038X.

6

Pe parcursul celor trei ani ai proiectului EURODOC, în cadrul studiilor doctorale, am elaborat

următoarele rapoarte de cercetare:

Ioan Agavriloaei, Raport de cercetare nr. 3, Soluţii integratoare de Web mining, 2012,

Universitatea Tehnică „Gheorghe Asachi” din Iaşi (conducător ştiinţific: Prof. univ. dr.

Mitică Craus).

Ioan Agavriloaei, Raport de cercetare nr. 2, Contribuţii la procesarea informaţiei web cu

ajutorul clasificării şi clusterizării, 2012, Universitatea Tehnică „Gheorghe Asachi” din

Iaşi (conducător ştiinţific: Prof. univ. dr. Mitică Craus).

Ioan Agavriloaei, Raport de cercetare nr. 1, Modele şi algoritmi utilizaţi în Web mining,

2011, Universitatea Tehnică „Gheorghe Asachi” din Iaşi (conducător ştiinţific: Prof. univ.

dr. Mitică Craus).

7

2. Concepte teoretice fundamentele de Web data mining

2.1 Data mining

Descoperirea cunoştinţelor în colecţii de date desemnează procesul de extragere a informaţiilor

netriviale, implicite, necunoscute anterior şi potenţial utile (Fayyad, et al., 1996) sau descoperirea

diverselor tipare valide, potenţial folositoare şi uşor de înţeles ce se regăsesc în resurse de date, ca de

exemplu, baze de date, documente text, imagini, Web, etc. (Adamo, 2000).

De cele mai multe ori, procesul de descoperire a cunoştinţelor (Knowledge Discovery in

Databases, KDD) (Figura 2.1) porneşte cu înţelegerea domeniului de aplicaţie a problemei şi

definirea obiectivelor ce se urmăresc prin analiză, după care urmează identificarea surselor

potenţiale de date, precum şi a datelor ţintă. Având datele necesare, extragerea şi exploatarea datelor

necesare poate fi efectuată prin aplicarea unor algoritmi specifici pentru extragerea de modele având

ca scop obţinerea de cunoştinţe noi. În practică, procesul de descoperire a cunoştinţelor în colecţii de

date de dimensiuni mari presupune un număr semnificativ de iteraţii şi poate să conţină bucle între

oricare două etape, după cum se poate observa în Figura 2.1. Dintre toate componentele acestui

proces, componenta data mining a fost cel mai intens studiată. Acest lucru nu a însemnat, însă,

neglijarea celorlalte componente, care sunt uneori foarte importante în practică, pentru asigurarea

succesului întregului proces.

Figura 2.1: Paşii care compun procesul de descoperire a cunoştinţelor

Data mining reprezintă procesul de analiză a unor seturi de date observaţionale, adesea de

dimensiuni foarte mari, cu scopul de a descoperi tipare sau relaţii ascunse; o modalitate de a

descoperi un nou înţeles al datelor.

Termenul de proces în cadrul data mining este foarte important, acestă abordare nu este o soluţie

întâmplătoare prin spaţiul tehnicilor de analiză, ci un proces plănuit cu grijă pentru a decide ceea ce

va fi mai folositor, mai promitător şi mai relevant. În practică, data mining este un proces interativ:

datele se examinează folosind tehnicile de analiză, se ia decizia abordării lor din alte perspective, se

fac uneori şi unele modificări asupra lor, apoi se revine la început şi se aplică altă tehnică,

obtinându-se în acest mod rezultate mai bune sau chiar total diferite. Aplicarea corectă a etapelor

8

descrise anterior şi identificarea corectă a metodelor de analiză ce vor fi utilizate nu va furniza

rezultatele mult aşteptate dacă nu sunt înţelese bine limitările şi restricţiile descoperirii de cunoştinţe

(Liu, 2011).Tehnicile şi modelele utilizate în descoperirea de cunoştinţe nu sunt general valabile, ele

nu oferă soluţii la orice problemă, dacă nu se ţine cont de domeniul în care sunt aplicate (Wang,

2009). Deasemenea, data mining nu este o simplă colecţie de instrumente izolate fiecare complet

diferită de celelalte şi care se poate potrivi unui anumit tip de problemă. Foarte rar o problemă este

formulată atât de precis încât o simplă aplicare a unei metode de data mining sa fie suficientă pentru

a obţine rezultatul dorit (Witten, et al., 2011).

2.1.1 Învăţarea supervizată (clasificarea)

Învăţarea supervizată (supervised learning) are un mare succes în aplicaţiile lumii reale. Este folosită

în aproape toate domeniile, inclusiv domeniul Web. Învăţarea supravegheată este denumită şi

clasificare sau învăţare inductivă în machine learning. Acest tip de învăţare este similar cu învăţarea

umană: ţinem cont de experienţele noastre din trecut pentru a dobândi cunoştinţe şi abilităţi noi cu

scopul de a ne îmbunătăţi capacitatea de a face faţă unor noi provocări. Deoarece computerele nu au

”experienţă”, învăţarea supervizată învaţă din datele pe care le-a colectat în trecut şi reprezintă

experienţe trecute din unele aplicaţii ale lumii reale. În acest subcapitol, ne vom concentra pe un

anumit tip de învăţare, şi anume, studierea unei funcţii de evaluare capabile să mapeze noile valori

ale unei clase discrete de atribute peste un număr limitat de clase predefinite. Acest tip de învăţare a

stat la baza machine learning şi este, de asemenea, una dintre cele mai utilizate paradigme în

aplicaţiile web. În mod formal, clasificarea poate fi definită astfel:

Clasificarea unui set de date reprezintă un proces de generare a unui set de constrângeri pe baza

experienţei şi performanţelor acumulate cu scopul de a sorta datele ulterioare.

Setul de date folosit pentru învăţare poartă numele de set de antrenament, iar după ce modelul

este construit din datele de antrenament de către un algoritm de învăţare (pasul de extragere a

cunoştinţelor), algoritmul este verificat folosind un set de test (care are la rândul său asociate etichete

de clasă dar nu este implicat în procesul de învăţare a clasificatorului) pentru a evalua acurateţea

modelului nou construit. Acurateţea cât şi alte metrici de evaluare a unui clasificator vor fi discutate

în subcapitolul următor.

În Figura 2.2 sunt ilustraţi paşii din procesul de învăţarea supravegheată bazându-ne pe

descrierea de mai sus. În faza de antrenare un algoritm de învăţare foloseşte datele de antrenament

pentru a genera un model de calsificare. Apoi, în faza de testare, modelul învăţat este testat, folosind

setul de test pentru a obţine o anumită acurateţe a clasificării. Dacă acurateţea modelului asupra

datelor de test îndeplineşte cerinţele iniţiale, atunci clasificatorul poate fi folosit pentru a clasifica

noi date de interes, date care nu mai au clase predefinite. În caz contrar, procesul este unul iterativ şi

se poate revenii la oricare pas precedent, fie pentru a alege alt algoritm de învăţare, fie pentru a

efectua operaţii suplimentare asupra datelor (faza de preprocesare). În practică, procesul de învăţare

presupune efectuarea mai multor iteraţii pentru a construi un clasificator satisfăcător.

9

Figura 2.2: Procesul de învăţare supervizată

2.1.2 Învăţarea nesupervizată (clusterizarea)

Învăţarea nesupervizată (unsupervised learning) nu necesită prezenţa setului de antrenament cu date

preclasificate apriori. Scopul învăţării nesupervizate este definit de necesitatea de explorare a datelor

pentru descoperirea unor structuri intrinseci. Utilizatorul explorează datele cu scopul de a găsi

structuri noi, interesante şi folositoare. Printre cele mai importante metode ale învăţării nesupervizate

este clusterizarea, care organizează datele în grupuri similare numite clustere în asa fel încât

instanţele dintr-un grup sunt similare dintr-un anumit punct de vedere şi total diferite faţă de datele

din celelalte grupuri. Conceptual, procesul de clusterizare poate fi definit astfel:

Clusterizarea reprezintă procesul de organizare a datelor dintr-o colecţie nestructurată în grupuri

numite clustere ale căror membrii sunt similari într-un anumit fel.

Calitatea diferitelor metode de clusterizare se diferenţiază prin folosirea funcţiilor obiectiv.

Calitatea clusterizării se referă în primul rând la omogenitatea în cadrul grupurilor şi separabilitatea

între grupurile rezultate în urma procesului de clusterizare. Procesul de învăţare nesupervizată este

unul iterativ şi este ilustrat în Figura 2.3.

Similaritatea este, în mod teoretic, metrica care reflectă potrivirea sau puterea de relaţie între două

date, două şiruri text sau caracteristici.

Clusterizarea are nevoie de o funcţie de similitudine pentru a măsura cât de similare sunt două

date, sau alternativ, o funcţie depărtare (disimilaritate) pentru a măsura distanţa dintre două date.

În domeniul informatic un număr din ce în ce mai mare de aplicaţii aplică metodele de

clusterizare pentru a obţine rezultate superioare. Este cazul clusterizării documentelor (Li & Chung,

2005) şi a sistemelor de regăsire a informaţiei (Grossman & Frieder, 2004). Principala problemă a

clusterizării o constituie volumul mare de date care trebuie procesat, algoritmii de clusterizare fiind

în general cu timp de răspuns mare.

10

Figura 2.3: Procesul de învăţare nesupervizată

2.1.2.1 Clusterizarea partiţională

Cel mai utilizat algoritm partiţional este algoritmul k-means (MacQueen, 1967), care adevenit

exponentul unei întregi categorii de algoritmi. Popularitatea este dată de simplitatea implementării,

scalabilitate, eficienţă şi viteza de convergenţă (Figura 2.4).

Algoritmul k-means(k, D)

Alege k date ca centroizi iniţiali (centrele clusterelor)

repeat

for each dată x D do

Calculează distanţa de la x la fiecare centroid;

Asociază x la cel mai apropiat centroid // centroidul reprezintă un

cluster;

endfor

Recalculează centroidul cu ajutorul membrilor actuali ai clusterului

until criteriul de oprire este îndeplinit

Figura 2.4: Algoritmul k-means

Avantaje şi dezavantaje. Deşi k-means are marele avantaj că este uşor de implementat şi eficient,

are şi câteva mari neajunsuri. Primul dezavantaj constă în aceea că poate fi foarte lent din moment ce

în fiecare pas distanţa dintre fiecare dată şi fiecare cluster trebuie calculată, afectând astfel timpul de

executie. O posibilă soluţie este calcularea centroizilor în fiecare pas şi contorizarea datelor din

fiecare cluster oferită de (Ordonez & Omiecinski, 2004). Al doilea dezavantaj este dat de faptul că

aceată metodă e foarte sensibilă la numărul şi iniţializarea clusterelor iniţiale, algoritmul putând să

furnizeze doar un optim local. Pentru a creşte şansa determinării optimului global, algoritmul poate

fi repetat cu centre de clustere diferite Această problemă a fost abordată cu rezulate notabile de către

(Fayyad, et al., 1998). Pentru selectarea clusterelor iniţiale s-au propus metodele: alegerea punctului

cel mai îndepărtat de ultimul centroid ales, o clusterizare ierarhică suplimentară pentru fiecare

centroid sau selectarea manuală a valorilor de start. Nu în ultimul rând, algoritmul este vulnerabil la

valorile extreme, marginale.

11

2.1.2.2 Clusterizarea ierharhică

Algoritmii de clusterizare ierarhici au ca rezultat o ierarhie de clustere numită dendrogramă, adică

un arbore care reflectă strucura clusterelelor de date la diferite niveluri de similaritate. Datele nu sunt

atribuite unui anumit cluster într-un singur pas, clusterele atomice găsindu-se la baza arborelui, iar

toate clusterele intermediare fiind cuprinse într-un cluster rădăcină care conţine tot data setul.

Clusterele de pe fiecare nivel al ierarhiei se obţin prin gruparea clusterelor situate pe nivelul imediat

inferior, criteriul de grupare făcându-se pe baza calculului distanţei dintre datele clusterelor.

Există două metode de clusterizare ierarhică (Hastie, et al., 2009):

Clusterizare aglomerativă (bottom up): dendrograma se construieşte de jos în sus prin

combinarea celor mai similare perechi de clustere de pe fiecare nivel pentru a merge apoi pe

un nivel mai sus. Procesul continuă până când toate clusterele sunt grupate într-un singur

cluster, clusterul rădăcină. Pseudocodul algoritmului aglomerativ este prezentat în Figura 2.5

Clusterizarea divizivă (top down): porneşte de la un singur cluster care cuprinde toate datele,

clusterul rădăcină şi se împarte într-un set de clustere, fiecare cluster fiind apoi divizat

recursiv până se obţine clustere atomice care conţin o singură dată.

Algoritmul Aglomerativ(D)

Iniţializează fiecare dată din setul de date D ca fiind un cluster,

Compute all pair-wise distances of x1, x2, …, xn D;

Calculează toate distanţele pereche ale x1, x2, …, xn D;

repeat

Găseşte două clustere care sunt cele mai apropiate unul de altul;

Combină cele două clustere şi formează un cluster nou c;

Calculează distanţa de la clusterul c la toate celelalte clustere;

until există doar un singur cluster rămas

Figura 2.5: Algoritmul de clusterizare ierarhică aglomerativ

Avantaje şi dezavantaje. Clusterizarea ierarhică are posibilitatea să utilizeze orice funcţie distanţă

sau similaritate. Un avantaj al acestei tehnici îl reprezintă posibilitatea de a explora datele la diferite

niveluri de granularitate, deoarece se reţine toata ierarhia de clustere şi utilizatorul poate alege să

vizualizeze clusterele la orice nivel al arborelui. Unele studii au demonstrat că clusterizarea ierarhică

aglomerativă produce rezultate mai bune decât metoda k-means, putând detecta clustere de forme

arbitrare. Ca puncte slabe, calitatea clustrizării ierarhice poate fi afectată de efectul de lanţ şi de

datele marginale. Principalele neajunsuri al metodelor de mai sus sunt date de complexitatea de

calcul şi cerinţele de spaţiu, ceea ce le face foarte neeficiente şi nepractice pentru seturi mari de date,

cum este Web-ul. O posibilă soluţie pentru această problemă ar fi extragerea de eşantioane asupra

cărora se aplică clusterizarea şi apoi distribuţia datelor la clustere fie pe baza distanţei, fie prin

învăţare supervizată.

12

2.2 Web data mining

Dezvoltarea rapidă a World Wide Web-ului (pe scurt WWW sau Web) în ultimele două decenii a

facut din el cea mai mare bază de date accesibilă publicului din lume. În momentul de faţă Web-ul se

schimbă mai rapid ca niciodată, nerespectând caracteristicile standard ale unui SGBD clasic, având

multe caracteristici unice care fac din procesul de descoperire a cunoştinţelor şi exploatarea

informaţiei o sarcină fascinantă şi provocatoare. Putem afirma că Web-ul cuprinde toate trăsăturile

particulare ale colecţiilor de date create până la apariţia lui. Procesul de data mining a trebuit să dea

un răspuns noilor provocări şi cerinţe, prin modificarea modului de analiză a datelor şi felului în care

sunt prezentate rezultatele către utilizator dând astfel naştere unui domniu de sine stătător, anume

Web data mining.

Din punctul de vedere al utilizatorilor cât și al oamenilor de ştiinţă toate aceste caracteristici

prezintă atât provocări cât şi oportunităţi pentru exploatarea şi descoperirea de informaţii şi

cunoştinţe pe Web. Studiul de față face abstracție de datele multimedia de pe Web şi se axează

numai pe exploatarea datelor de tip text. Datorită bogăţiei şi diversităţii informaţiei şi altor

caracteristici ale Web-ului, în domeniul Web mining au fost definiţi şi dezvoltaţi algoritmi specifici

sau au fost adaptaţi algoritmii existenți în data mining-ul clasic.

Web mining-ul îşi propune să descoperire informaţii şi cunoştinţe folositoare din structura de

hiperlegături a Web-ului, din conţinutul paginilor Web precum şi din modul de utilizare de către

utilizator al acestor date.

Web mining reprezintă aplicarea tehnicilor de data mining pentru descoperirea şi extragerea de

informaţii interesante şi utile din documentele şi serviciile web, de obicei, prin intermediul

instrumentelor bazate pe Web.

Deşi Web mining-ul are ca bază de principii data mining-ul tradițional şi utilizează multe din

tehnicile de data mining prezentate anterior, acest proces nu este similar cu tehnicile tradiţionale de

explorare a datelor datorită în primul rând eterogenităţii şi naturii semi-structurate sau nestructurate a

datelor web (Liu, 2011). Multe idei noi şi de asemenea algoritmi au fost propuşi în ultimul deceniu,

odată cu explozia fără precedent a volumului de informaţie de acest tip. Ţinând cont de obiectivele

analizei şi de tipurile primare de date utilizate în procesul de exploatare, activitatea de Web mining

poate fi împărţită în trei mari domenii: Web structure mining, Web content mining şi Web usage

mining.

2.2.1 Web structure mining

Prin exploatarea structurii Web-ului informaţia care nu este evidentă pentru utilizator poate fi

descoperită. În acest capitol sunt prezintate principalele proprietăţi, concepte şi modele ale grafului

Web, precum şi principalii algoritmi de clasificare şi clusterizare a paginilor web bazaţi pe legături.

2.2.1.1 Algoritmul PageRank

Algoritmul PageRank (Brin & Page, 1998) este influenţat de analiza citaţiilor, considerând

legăturile către o pagină web ca fiind citaţii. Algoritmul oferă un mod de a calcula importanţa unei

13

pagini, nu doar prin numărarea numărului de pagini (backlinks) care au o legătură către ea, ci şi prin

ierarhizarea paginilor care fac această referire. Astfel, o legătură care vine de la o pagină importană

cântăreşte mai mult decât una care vine de la o pagină minoră, fiind un vot de încredere primit de la

cineva care are la rândul său încredere. Brin şi Page afirmă că „o pagină are un rang mare dacă suma

rangurilor paginilor care au legătură către ea este mare. Acest lucru acoperă atât cazul când o pagină

este referită de multe alte pagini cât şi cazul când o pagină are câteva referiri de la pagini de rang

înalt” („a page has high rank if the sum of the ranks of its backlinks is high. This covers both the

case when a page has many backlinks and when a page has few highly ranked backlinks”) (Brin &

Page, 1998).

Primul pas al algoritmului constă în calcularea numărului de legături care fac referire la fiecare

pagină web. Acest lucru se realizează printr-o pargurgere aleatorie a grafului Web. Fiecare pagină

obţine astfel o rată de vizitare care defineşte importanţa sa.

Apoi, presupunând că pagina are legături de la paginile , scorul PageRank (PR) al

paginii este definit astfel:

( ) ( ) ( ( ) ( )⁄ ( ) ( )⁄ ) (2.1)

unde, ( ) este definit ca numărul de legături pe care le are pagina către , * + şi este

un factor de amortizare, având de obicei valoarea 0.85.

Scorul PageRank trebuie calculat printr-un algoritm iterativ înainte de a avea o valoare de

echilibru. Algoritmul a stat la baza creării motorului de căutare Google.

Avantaje şi dezavantaje. Principalul avantaj al algoritmului PR este capacitatea sa de a lupta

împotriva spam-ului. Un alt mare avantaj al algoritmului PR este faptul că este o măsură globală,

fiind independentă de interogarea utilizatorului. Principala critică adusă algoritmului este chiar

independenţa sa faţă de interogare, deoarece nu poate distinge între paginile care sunt autorităţi în

general şi paginile autorităţi pentru un anumit subiect. O altă critică adusă acestui algoritm este aceea

că nu ia în considerare timpul când o anumită pagină a apărut pe Web.

2.2.1.2 Algoritmul HITS

Algoritmul HITS (Kleinberg, 1999) introduce noţiunea de autoritate – pagină importantă din punct

de vedere al conţinutului (pagina spre care trimit legăturile) şi noţiunea de hub – pagină cu rol de

resursă, pentru ghidarea utilizatorilor către autorităţi (pagina din care pleacă legăturile). Algoritmul

HITS atribuie unei pagini două valori iniţiale unitare: o pondere de hub, Hub(p), şi o pondere de

autoritate, Auth(p). Aceste ponderi se modifică după formulele:

( ) ∑ ( )

(2.2)

unde este numărul de pagini care au legătură către şi este o pagină care are legătură către .

( ) ∑ ( )

(2.3)

unde este numărul de pagini spre care are legătură şi este o pagină spre care are legătură.

14

Ideea în jurul căreia gravitează algoritmul HITS este aceea că o pagină bună de tip hub

pointează către mai multe autorităţi bune şi o pagină autoritate este referită de mai multe pagini hub

de calitate, definind astfel noţiunea de comunitate. Astfel, autorităţile şi hub-urile sunt într-o relaţie

de consolidare reciprocă, formând un graf bipartit.

Algoritmul este unul iterativ şi converge după câteva iteraţii. Pe baza acestui algoritm s-a creat

motorul de căutare Clever.

Avantaje şi dezavantaje. Principalul avantaj al algoritmului HITS este capacitatea sa de a clasa

pagini în funcţie de subiectul interogării, caracteristică care poate să ofere autorităţi şi hub-uri mai

relevante. Algoritmul HITS are mai multe dezavantaje: nu are caracteristica de anti-spam precum

algoritmul PR, poate colecta pagini care deviază de la subiect şi timpul de interogare este mare.

2.2.2 Web content mining

Web content miningul oferă metode de descoperire automată, regăsire, organizare şi management a

extraordinarei cantităţi de informaţie şi resurse disponibile pe Web. (Cooley, 2003) vede două

abordări în domeniu Web content mining: regăsirea informaţiei web şi abordarea din punctul de

vedere al bazelor de date. Regăsirea informaţiei pe Web presupune dezvoltarea de sisteme

inteligente care pot acţiona autonom sau semi-autonom pentru a descoperi şi a exploata informaţia

web. Prin acest proces se doreşte găsirea unui set de documente care este relevant la interogarea

utilizatorului. Căutarea pe Web implică aplicarea metdelor de regăsire a informaţiei asupra Web-

ului, dar are la rândul său tehnici unice datorate provocărilor noi pe care Web-ul le-a generat.

De regulă, Web content mining este analizat alături de Web structure mining, deoarece sunt

folosite împreună pentru extragerea şi organizarea informaţiei. În această secţiune sunt prezentate

principiile care stau la baza regăsirii informaţiei şi a căutării pe Web.

Regăsirea informaţiei pe Web (Web-IR) este domeniul de cercetare orientat spre găsirea

informaţiei de pe Web care să se potrivească cu nevoilor de informare ale utilizatorilor.

Funcţia unui sistem de regăsire a informaţiilor este de a prelua interogarea unui utilizator şi a

întoarce o listă de documente care sunt relevante pentru respectiva interogare, ordonate

descrescător în funcţie de probabilitatea de relevanţă.

În regăsirea informaţiei, relevanţa denotă cât de bine satisface nevoia de informaţie a

utilizatorului un document sau un set de documente regăsit. În literatura de specialitate, relevanţa se

fundamentează pe ceea ce se doreştea a fi „punctul de vedere al sistemului” („the system’s view”) şi

„punctul de vedere al utilizatorului” („ the user’s view”).

În cadrul procesului de regăsire a informaţiei utilizatorul lansează o interogare (user query)

sistemului prin intermediul unui modul care prelucrează interogarea şi o trimite modulului de

regăsire. Acesta, identifică documentele relevante prin intermediul modelelor de reprezentare, le

calculează relevanţa, le ordonează şi le prezentă utilizatorului. Înainte ca acţiunea de mai sus să aibă

loc, colecţia de documente este supusă unui proces de indexare cu ajutorul unui instrument de

indexare pentru a eficientiza regăsirea. Dacă colecţia de documente este Web-ul atunci vorbim

despre regăsirea informaţiei pe Web.

15

2.2.2.1 Modele de reprezentare şi regăsire a documentelor web

În contextul regăsirii informaţiei şi a căutării pe Web, prin modelul de regăsire a unui document web

se doreşte definirea următoarelor trei chestiuni:

modul de reprezentare a unui document,

modul de reprezentare a unei interogări şi

modul în care este definită funcţia de relevanţă/clasare a unui document la o interogare.

Dacă privim doar din punctul de vedere al clasificării şi clusterizării web, prin model de

reprezentare a unui document web se înţelege doar reprezentarea strictă a unui document, celelalte

două elemente nefăcând obiectul celor două arii de interes. Deoarece clusterizarea şi clasificarea sunt

strâns legate de regăsirea informaţiei, în continuare vor fi descrise toate cele trei componente.

Există şase modele principale de reprezentare a unui document web: modelul Boolean

(Lancaster & Fayen, 1973), modelul spaţiului vectorial (Vector Space Model, VSM) (Salton, 1971),

modelul lingvistic (Ponte & Croft, 1998), modelul probabilistic (Jones, et al., 2000) şi modelul

maşinilor cu vectori suport (Support Vector Machines, SVM) (Vapnik, 1995).

Toate modelele de mai sus au la bază acelaşi principiu definit de (Salton, 1971): se consideră

fiecare document şi interogare ca fiind un „sac” de cuvinte sau termeni (bag-of-words). Aceste

modele formează aşa numitul concept de layout representation.

Fie colecţia de documente şi setul de termeni distinţi { | |}, unde este un

termen, iar | | este mărimea setului. O pondere este asociată fiecărui termen a

documentului . Pentru un termen care nu aparţine documentului . Fiecare

document este reprezentat sub forma unui vector de termeni:

( | | ) (2.4)

unde fiecare pondere corespunde termenului şi semnifică nivelul de importanţă al

termenului in documentul . Astfel, este reprezentat sub forma unui tabel relaţional sau sub

forma unei matrici, numită matricea indecşilor (Term-Document Frequency Matrix). Ceea ce

diferenţiază, în mare parte, modelele care au la bază acest principiu este modul de definire a ponderii

şi funcţia de clasare a unui document în raport cu o interogare.

2.2.2.2 Evaluarea prin colecţii de test

Definiţia 2.6 conduce la următoarea concluzie: eficacitatea unui sistem de regăsire a informaţiei

trebuie să fie evaluată pe baza numărului, proporţiei, şi clasificării documentelor relevante

returnate.

Definiţia 2.6 şi concluzia de mai sus definesc interpretarea relevanţei unui subiect în IR şi

formează aşa zisul model de relevanţa a unui subiect (the topical relevance model).

Modelul de relevanţă a unui subiect identifică trei elemente ale procesului de regăsire: nevoia

utilizatorului de informare, setul de documente din care sistemul încearcă să satisfacă nevoia şi

valoarea relevanţei fiecărui document din colecţie la nevoia respectivă. Acestor trei elemente le

corespund trei componente într-o colecţie de test: un set de subiecte sau interogări (topics), fiecare

descriind o nevoie de informaţie, un set de documente sau colecţie (corpus) şi un set de evaluări ale

16

documentelor (qrels), care indică relevanţa documentelor la fiecare subiect. Termenul qrels

desemnează judecăţile făcute de experţi umani pentru a stabili dacă un document este relevant pentru

o nevoie de informaţie (un subiect).

Un sistem de regăsire este evaluat în raport cu o colecţie după cum urmează. Fiecare subiect este

formulat sub forma unei interogări, în general, prin extragerea termenilor din subiect, interogarea

fiind trimisă sistemulului. Sistemul identifică potrivirile dintre interogare şi documentele din colecţie

printr-un algoritm de regăsire şi returnează o listă de documente, ordonate descrescător în funcţie de

probabilitatea de relevanţă la interogare. Evaluările qrels sunt consultate pentru a determina care

documente sunt relevante pentru subiect şi ordonarea este transformată într-o listă ordonată de valori

relevanţă, numită vector de relevanţă. Apoi, o metrică de evaluare este folosită pentru a evalua

vectorul de relevanţă, precum este descris în secţiunea următoare şi apoi, scorurile pe care sistemul

le obţine pentru fiecare subiect sunt cumulate, în mod normal ca medie aritmetică, pentru a obţine

indicele de performanţă al sistemului pentru întreaga colecţie.

Metodologia descrisă mai sus reduce utilizatorul la o interogare şi un set de evaluări ale

relevanţei, iar rezultatul căutării la un vector de valori, care este mai apoi concentrat într-un singur

scor. Avantajul acestei abstractizări este dat de faptul că interogările şi evaluările pot fi create în

avans. Comunitatea ştiinţifică poate, astfel, să le utilizeze fără schimbări în experimente repetate pe

diferite sisteme, cu diferiţi parametrii de regăsire şi în momente diferite de timp.

Prin urmare, colecţia de test asigură un set de instrumente automate reproducând cu fidelitate

esenţa procesului manual de căutare a informaţiei şi evaluarea rezultatului.

2.2.3 Web usage mining

Web usage mining se referă la descoperirea şi analiza automată a modelelor în datele colectate sau

generate ca rezultat al interacţionării utilizatorului cu resursele web din cadrul unui sau mai multor

site-uri. Scopul este de a observa, modela şi analiza modele comportamentale ale utilizatorilor care

interacţionează cu un site web. Modelele descoperite sunt de obicei reprezentate sub forma de

colecţii de pagini, obiecte sau resurse care sunt accesate frecvent sau utilizate de către grupuri de

utilizatori cu nevoi şi interese comune.

Urmând procesul standard de date mining, procesul de Web usage mining poate fi împărţit în trei

etape inter-dependente: colectarea şi preprocesarea datelor, descoperirea de modele şi analiza

modelelor. În faza de preprocesare, datele provenite de la click-urile utilizatorilor sunt curăţate şi

partiţionate în seturi care reprezintă activităţile fiecărui utilizator la diferite momente de accesare a

unui site. În faza de descoperire a modelelor, sunt efectuare diferite procese de statistică, baze de

date, machine learning pentru a descoperi modele ascunse care reflectă comportamentul tipic al

utilizatorilor, precum şi statistici sumare ale resurselor web, sesiunilor şi utilizatorilor. În ultima

etapă a procesului, modelele şi statisticile descoperite sunt procesate, filtrate pentru a forma modele

de utilizator care pot fi folosite ca date de intrare pentru motoarele de recomandare, instrumente de

vizualizare, analiza şi generare a rapoartelor web.

17

3. Stadiul actual al cunoaşterii în Web mining

3.1 Stadiul actual în Web structure mining

Înţelegerea scopului din spatele legăturilor şi exploatarea lor pentru a obţine noi înţelesuri ale

informaţiei stă la baza Web structure mining-ului. Utilizarea analizei legăturilor în contextul Web a

început odată cu algoritmii PageRank (Brin & Page, 1998) şi HITS (Kleinberg, 1999). Aproape toate

cercetările ulterioare care investighează structura Web-ului s-au axat pe principiile definite în aceşti

doi algoritmi. Datorită mai multor neajunsuri ale acestor doi algoritmi, cercetările ulterioare au

incercat să aducă unele îmbunătăţiri.

Algoritmul PageRank a fost acela care a făcut popular motorul de căutare Goolge. S-a încercat

îmbunătăţirea lui în multe direcţii, astfel: modul de calcul al scorului PageRank a fost studiat de

(Kamvar, et al., 2003) şi (McSherry, 2005), evoluţia Web-ului şi influenţa motoarelor de căutare

asupra lui a fost investigată de (Cho & Roy, 2004) şi (Fortunato, et al., 2006), felul cum influenţează

alte modele bazate pe legături a fost analizat de (Tomlin, 2003) şi (Nie, et al., 2005), caracteristicile

grafului Web au fost investigate de (Pennock, et al., 2002) şi dimensiunea temporală a căutării pe

Web a fost analizată de (Baeza-Yates, et al., 2002) şi (Diaz, 2009).

O nouă metodă de analiză şi funcţie de clasare a legăturilor bazată pe log-urile de navigare ale

utilizatorului a fost propusă de (Liu, et al., 2008). Metoda BrowserRank se foloseşte de procesul

Markov cu timp continuu pentru a construi funcţia de clasare, spre deosebire de PageRank care este

un model Markov cu timp discret. Diverse variante şi îmbunătăţiri ale algoritmului HITS au fost

propuse de (Lempel & Moran, 2000), (Chakrabarti, et al., 2006) introducând astfel noţiunea de

comunitate. Un algoritm pentru identificarea paginilor cu rol bipartit a fost propus de (Kumar, et al.,

1999), iar definirea mai strictă a comunităţilor a fost propusă de (Ino, et al., 2005). Un algoritm de

indentificare a comunităţilor care se suprapun a fost propus de (Li, et al., 2006). La ora actuală

variaţii ale celor doi algoritmi se folosesc împreună cu tehnicile bazate pe conţinut pentru a obţine o

eficienţă mai ridicată a sistemelor de regăsire a informaţiei şi a motoarelor de căutare.

3.2 Stadiul actual în Web content mining

Modelarea documentelor este cheia pentru obţinerea unei eficienţe crescute a oricărui algoritm de

organizare. Pentru un sistem de regăsire a informaţiei, modelul unui document este strâns legat de

modelul interogării şi funcţia de clasare care leagă respectiva interogare de document. Este evident

că realizarea unui model optim de reprezentare duce la o calitate superioară atât a modului de

organizare cât şi a rezultatelor procesului de căutare.

Modele provenite din regăsirea informaţiei clasice se bazează exclusiv pe modelul spaţiului

vectorilor de caracteristici (VSM) (Salton, 1971) în care un document este reprezentat sub forma

unui vector n dimensional iar, similaritatea document-interogare este calculată după reguli

geometrice. Calcularea importanţei termenilor se face cu una din următoarele ponderi: ponderea

booleană (Pazzani & Billsus, 1997), ponderea (Hawking, et al., 2004), ponderea Okapi

BM25 (Robertson, et al., 2000) sau ponderea determinată prin algoritmi genetici.

18

Modelele din sistemele Web-IR, bazate pe trasăturile noi, specifice Web-ului cu ar fi legăturile

(Brin & Page, 1998), (Kleinberg, 1999) sau tag-uri (Molinari, et al., 2003) au ca bază tot conceptul

VSM dar modelarea se face ţinând cont de structura HTML, respectiv structura de legături a

documentelor. Aceaste modele reprezentă prima încercare de modelare orginală a Web-ului, odată ce

regăsirea informaţiei s-a orientat spre această colecţie de date. Modele de mai sus fac parte din

sisteme de regăsire a informaţiei web care exploatează caracteristicile specifice Web-ului atribuind o

pondere dependentă de poziţia (sistemul Indexing HTML Model (Molinari, et al., 2003)), structura

(sistemul WEBOR (Cutler, et al., 1999)), (sistemul Indexing HTML Model (Pereira, et al., 2005)),

persistenţa (Markov, et al., 2008), contextul (sistemul Indexing HTML Model (Pereira, et al., 2005))

şi rolul (sistemul IRIS) unui termen sau concept. (Geva & Sahama, 2005) au propus un model de

reprezentare pentru documentele semi-structurate de pe Web. Alte modele se bazează pe o abordare

conceptuală, numită Latent Semantic Indexing (Deerwester, et al., 1991), unde un document este

modelat pe baza unor concepte, iar alte modele se bazează pe principiile inteligenţei artificiale: retele

neuronale (Yang, et al., 2003), reţele Bayesiene. Modele bazate pe SVM vin cu ideea de a reprezenta

un document prin vectori suport care nu restricţionează numărul de caracteristici rezolvând astfel

problema dimensionalităţii şi neafectând eficienţa şi abititatea de a generaliza. (Joachims, 1999) a

demonstrat că clasificatorul SVM obţine rezultate superioare faţă de ceilalţi clasificatori. După cum

se poate observa, modelul VSM este încă foarte popular şi este la baza majorităţii sistemelor de

regăsire datorită, în principal, simplităţii şi eficacităţii lui.

În cadrul procesului de Web mining abordările actuale se axează pe utilizarea complementară a

unor clase de algoritmi – descriptivi sau predictivi – din cadrul domeniului de descoperire de

cunoştinţe. Clusterizarea este doar una dintre metodele de a organiza continutul web pentru a facilita

căutarea şi regăsirea informaţiilor de pe Web. Validarea, îmbunătăţirea şi compararea performanţelor

diferiţilor algoritmi de custerizare este complexă, deoarece este dificil să se gasească o masură

obiectivă a calităţii clusterilor rezultaţi. Cele mai importante aspecte care trebuie luate în considerare

sunt calitatea clusterilor rezultaţi şi complexitatea timp a algoritmilor.

În ceea ce priveşte clusterizarea paginilor web, majoritatea implementărilor au la bază

algoritmul k-means (Steinbach, et al., 2000) şi metodele ierarhice (Zhao, et al., 2005) sau variaţii ale

lor, dar folosind funcţii similaritate sau distanţă specifice pentru datele de tip text. Pentru ca procesul

de clusterizare a documentelor să fie posibl trebuie mai întâi ca informaţiile textuale din document să

fie transformate în informaţii cantitative de genul atribut-valoare. Ţinând cont de specificacitatea

documentelor s-au adus şi unele îmbunătăţiri asupra algoritmilor clasici. Clusterizarea este intens

folosită pentru regăsirea documentelor cu subiecte similare sau pentru a grupa rezultatele motoarelor

de căutare, putând astfel organiza rezultatele pe diferite subiecte sau teme (Kummamuru, et al.,

2004), (Zeng, et al., 2004).

În literatură, nu există încă un consens în privinţa celui mai bun algoritm de clusterizare a

documentelor. Există lucrări care arată că algoritmii ierarhici obţin o performanţă superioară

(Steinbach, et al., 2000), dar alte cercetări sugerează că algoritmii partiţionali sunt mai performanţi

(Zhao, et al., 2005).

19

4. Studiu metricilor de evaluare având în vedere modul în

care utilizatorii efectuează o căutare

4.1 Formularea problemei

Un sistem de regăsire a informaţiei este definit de modalitatea de reprezentare a unui document,

respectiv a unei interogări şi de funcţia care evaluează relevanţa document-interogare, care are drept

scop satisfacerea nevoii de informaţie a utilizatorului. Deşi majoritatea sistemelor IR au la bază

paradigma „bag of words” pentru modelarea documentelor şi interogărilor, ceea ce le diferenţiază

fundamental este procedura de estimare a probabilităţii de relevanţă a documentelor la interogările

utilizatorului. Cea mai utilizată metodă de evaluare a unui sistem în regăsirea informaţiei constă în

folosirea colecţilor de test, astfel: un set de interogări (sau subiecte) este rulat împotriva unei colecţii

statice de documente.

Din punctul de vedere al evaluării, o satisfacţie cât mai mare a nevoii de informaţie se traduce

printr-un indice de performanţă cât mai apropiat de valoarea 1. Ţinând cont de relevanţa judecăţilor,

o varietate de metrici pot fi calculate, cu scopul de a capta diferite aspecte din comportamentul

utilizatorului şi de a reprezenta indicele de performanţă al sistemului de regăsire. Pentru evaluarea

performanţelor unui sistem IR, în general, metricile propuse se bazează, pe două concepte

fundamentale: precizia unui sistem de regăsire, definită ca raportul dintre numărul de documente

relevante returnate şi numărul total de documente returnat, şi reapelul, definit ca raportul dintre

numărul de documente relevante returnate şi numărul total de documente relevante din colecţia de

test. Prin precizie se urmăreşte măsurarea acurateţei listei returnate, ţinându-se cont de proporţia

documentelor nerelevante, iar prin reapel se măsoară gradul de acoperire al subiectului, analizând-se

doar documentele relevante. Aşadar, atât precizia cât şi reapelul se bazează pe înţelegerea şi

măsurarea relevanţei unui document.

Deoarece experimentele de evaluare urmăresc, în general, performanţa sistemului pe baza unui

set de 50 sau mai multe interogări, se folosesc diverse măsuri unificatoare pentru a indica un indice

global de performanţă al sistemului. Cu toate acestea, pentru căutările care au drept scop precizia,

cercetările recente au arătat că unele metrici care cuantifică performanţa sistemului nu au o relaţie de

corespondenţă cu metricile care urmăresc performanţa sistemului din perspectiva utilizatorului.

Motivaţi de această constatare, dar şi pentru a justifica abordările viitoare şi a stabili câteva

referinţe ale cercetării, ne propunem să investigăm relaţiile dintre diferite metrici de evaluare pentru

cele două direcţii actuale ale regăsirii informaţiei prin intermediul celor 60 de experimente

prezentate la conferinţa TREC 2011 şi cu ajutorul unui model IR care nu implică existenţa unui

limbaj de modelarea a interogării (adică modelul care stă la baza sistemului de regăsire este unul

non-lingvistic). Prin analiza metricilor, urmărim să determinăm care mătrică trebuie folosită pentru a

răspunde cât mai bine aşteptărilor utilizatorului.

4.2 Metodologie şi metrici

Pentru a analiza dacă diferite metrici de evaluare măsoară lucruri similare sau diferite, vom compara

perfomanţa relativă a celor 60 de experimente care au fost prezentate la coferinţa TREC din 2011

20

pentru regăsirea ad-hoc şi diversificată. Aceste experimente au constat în rularea a 50 de interogări

împotriva colecţiei de test ClueWeb09. Celor 60 de experimente de la TREC 2011 li s-au adaugat 10

experimente noi, care au fost concepute fără un limbaj de modelare a interogării, cu scopul de a

produce câteva referinţe pentru viitoarele experimente.

Prin intermediul celor două direcţii de regăsire a informaţiei se doreşte obţinerea atât a unei

precizii ridicate, cât şi a unei acoperiri corespunzătoare a subiectului în cadrul listei returnate. Cele

două tipuri de regăsire folosesc un set de interogări comune, diferenţiindu-se numai prin

metodologia de evaluare. Interogările sunt create pe baza informaţiilor din log-urile unui motor de

căutare comercial, fiecare interogare fiind structurată sub forma unui set reprezentativ de

subintergări, fiecare subinterogare reflectând o nevoie diferită de informaţie a utilizatorului. Pentru

regăsirea ad-hoc documentele sunt judecate în raport cu un subiect, subiectul fiind considerat ca un

întreg. Procesul de evaluare se face pe baza câmpului de descriere utilizând o scală de 6 niveluri de

relevanţă. Regăsirea diversificată analizează documentele în raport cu sub-interogările, precum şi în

raport cu subiectul ca întreg. În cazul acesta, pentru fiecare sub-interogare, se face o evaluare binară

care stabileşte dacă un document satisface sau nu nevoia de informaţie asociată unei sub-interogări.

4.2.1 Regăsirea ad-hoc

Regăsirea ad-hoc analizează performanţele sistemelor care identifică un set static de documente cu

ajutorul unui set de subiecte necunoscute, cu scopul de a returna setul de documente ordonat

descrescător în funcţie de probabilitatea de relevanţă. În cadrul acestui proces, relevanţa

documentelor nu este dependentă de celelalte documente din cadrul listei returnate şi este analizată

pe baza câmpului de descriere a subiectului prin intermediul unei scale de 6 niveluri. Experimentele

pentru regăsirea ad-hoc sunt analizate prin intermediul a 4 metrici de evaluare din cadrul IR. Aceste

metrici sunt definite pentru o rulare dată, în cadrul căreia s-au executat toate cele 50 de interogări,

astfel: precizia în poziţia 20 (P@20), media preciziilor medii (MAP), câştigul cumulat redus

normalizat în poziţia 20 (nDCG@20), gradul de aşteptare reciproc în poziţia 20 (ERR@20).

4.2.2 Regăsirea diversificată

Regăsirea diversificată este similară celei ad-hoc, ceea ce le diferenţiază fiind criteriul de analiză şi

metricile de evaluare. Scopul acestei metode este de a returna o listă ordonată de documente care să

acopere toate aspectele unui subiect, printr-o redundanţă minimă. În cazul acesta, probabilitatea de

relevanţă a unui document este condiţionată de celelalte documente care apar înaintea lui în listă, iar

analiza se face în raport cu sub-interogările unui subiect printr-o judecată binară. Experimentele sunt

analizate prin intermediul a 4 metrici de evaluare de tipul „intent aware” în sensul definit de

(Agrawal, et al., 2009) din cadrul IR. Aceste metrici sunt definite pentru o rulare dată, în cadrul

căreia s-au executat toate cele 50 de subiecte, astfel: precizia în poziţia 20 (P-IA@20), media

preciziilor medii (MAP-IA), câştigul cumulat redus normalizat în poziţia 20 (α-nDCG@20), gradul

de aşteptare reciproc în poziţia 20 (ERR-IA@20) (Chapelle, et al., 2009).

21

5. Noi modele şi algoritmi pentru clusterizarea şi căutarea pe

Web

5.1 Modelarea documentelor Web

În continuare, se propune un nou model de reprezentare a unui de document Web, bazat pe tag-uri,

legături şi o structură ierarhică a Web-ului. Considerând că documentele Web sunt deja grupate în

site-uri şi ţinând cont de structura HTML a unui document Web, prezentăm o nouă abordare de

modelare a conţinutului Web. Mai mult, pentru reprezentarea unui document ținem cont de ultimile

tendințte din Search Engine Optimization (SEO) pentru a îmbunătăți acuratețea și eficiența regăsirii

informației. Cu acest model, intenționăm să construim o reprezentare a documentelor Web care să

fie folosită de aplicațiile care au ca scop procesarea informației intr-un mod automat. Având ca bază

acest nou model de document Web şi structura ierarhică a Web-ului, este propus un nou algoritm

partiţional de clusterizare.

5.1.1 Ponderea termenilor

Ponderea unui termen trebuie să reflecte utilitarea informaţiei şi este necesară pentru reprezentarea

corectă și regăsirea documentului care îl conține (Salton & McGill, 1983). O pondere adecvată a

termenului poate îmbunătăți considerabil performanța modelului VSM (Chisholm & Kolda, 1999).

O schema de pondere este compusă din trei ponderi: o pondere locală, o pondere globală și un factor

de normalizare. Astfel, ponderea unui termen poate fi definită ca fiind:

(5.1)

unde, este ponderea locală pentru termenul în documentul , este ponderea global a

termenului în colecție, și este factorul de normalizare.

În aproape toate tehnicile de regăsire a informației ponderea locală depinde de numărul de

apariții ale termenului în documentul și este evaluată în funcţie de termenii din respectivul

document. În acest sens, ponderea locală, , pentru termenul este o funcție de frecvență a

termenului în documentul :

( ) (5.2)

Ţinând cont de abordarea lui Cutler et al. (Cutler, Deng, Maniccam, & Meng, 1999), putem

defini un nou model de pondere locală bazându-ne pe rezultatele obținute. În abordarea sa, Clutler

reprezintă un document Web prin șase clase de taguri: (Plain Texts, Strongs, Lists, Headings,

Anchors, Titles). Ponderea locală este definită ca produsul scalar dintre doi vectori: Class

Importance Vector (CIV) și Term Frequency Vector ( ). În experimentele sale, Clutler a găsit trei

vectori CIV diferiți: (1, 8, 1, 8, 8, 2), (1, 8, 1, 7, 8, 2) și (1, 8, 1, 5, 8, 2). Considerând că unele clase

de tag-uri au același factor de importanță, putem reprezenta un document Web numai prin

intermediul a doar patru clase de taguri: (Titles, Headings, Strongs-Anchors, Plain Texts). Pentru

clasa Headings am luat valoarea medie din rezultatele lui Clutler. Astfel, vectorul CIV va avea

valorile: (1, 8, 7, 2) (a se vedea Tabelul 5.1).

22

Tabelul 5.1: Clasele şi tagurile asociate

Numele clasei Tag-uri HTML sau atribute ale lor Factorul de importanţă

Title title 1

Header h1, h2, h3, h4, h5, h6 8

Strongs-Anchors strong, b, em, i, u, a, a:href, a:alt 7

Plain Texts Nici unul din cele de mai sus 2

Pentru a reprezenta cât mai bine un document trebuie să procesăm fiecare cuvânt care nu se

găsește în lista stopwords, îl supunem unui proces de stemming, pentru a obține doar rădăcina

cuvântului iar termenul obținut este atribuit unei din cele patru clase, incrementând corespunzător

indecele clasei respective. Acum putem defini ponderea locală ca fiind:

(5.3)

unde, ( ) conține ponderea fiecărei clase și * + conține

frecvența de apariție a termenului în documentul pentru fiecare clasă de tag-uri.

Dacă ( ) ponderea locală devine:

( ) ( ) (5.4)

Cu aceste valori ale vectorului CIV obținem definiția consacrată a frecvenței unui termen care

nu ține cont de tagurile HTML. În continuare vom numi regăsirea cu aceste valori ale CVI ca fiind

regăsirea normală.

Ponderea globală este dată de numărul de apariție ale fiecărui termen în întreaga colecție de

documente și încearcă să dea o valoarea de discriminare pentru fiecare termen. Factorul de

normalizare este o variabilă de corectare care trebuie să compenseze discrepanțele dintre lungimile

documentelor. Pentru experimentele noastre vom folosi factorul de normalizare cosinus, definit în

(Molinari, Pereira, & Pasi, 2003), și factorul de normalizare cu pivot definit în (Kobayashi &

Takeda, 2000) cu slope de 0.2, numit și ponderea Lnu în sistemul Smart (Salton G. , 1971)

5.1.2 Reprezentarea documentelor web

Dacă considerăm definițiile anterioare pentru ponderea unui termen și relația specifică dintre

documentele web, putem crea o reprezentare abstractă a unui document Web care să fie folosită cu

scopul de a procesa informația în mod automat. Modelul unui document web din colecția poate

fi definit ca un ansamblu de doi vectori:

{( ) } (5.5)

unde, este marimea colecției , { } reprezintă vectorul de ponderi pentru

documentul j, document care are termeni și, * + vectorul care conține

toate legăturile documentului .

Fiecare legătură a unui document web are ca scop să pună în evidență legătura semantică a două

documente web și este creată cu scopul de a asocia documentele conexe. Această conexiune, odată

descoperită, poate fi folosită pentru a găsi legături strănse de semantică între documentele web, în

cazul nostru legături între documentele dintr-un anumit cluster.

23

5.2 Combinarea dependenţei, relevanţei şi structurii pentru

regăsirea pe Web eficientă

5.2.1 Formularea problemei

Regăsirea ad-hoc este o temă importantă de cercetare, iar aplicaţiile ei acoperă o varietate mare de

probleme din IR. Regăsirea ad-hoc investighează performanţa determinării unui set static de

documente care sunt relvante cu ajutorul unor subiecte standard şi nevăzute, ordonate descrescător

după probabilitatea de relevanţă. Se consideră că relevanţa unui document este independentă de

relevanţa altor documente care apar înainte, în lista ordonată (Clarke, et al., 2004).

Acest capitol se bazează pe rezultatele publicate în (Agavriloaei, et al., 2012), în care se

examinează mai multe tehnici de regăsire despre care s-a demonstrat în trecut că pot aduce un

anumit grad de performanţă - modelul dependenţei şi modelul relevanţei. Aceste două metode sunt

combinate pentru a oferi o bază puternică la care se adaugă modelul de regăsire bazat pe câmpuri. Se

studiază modul în care se modifică performanţa regăsirii ad-hoc dacă modelul bazat pe câmpuri este

combinat cu modelul dependenţei şi relevanţei în LM. Acest studiu are drept scop obţinerea unei

perspective asupra rolului pe care documentele structurate Web (care au în structura lor câmpuri

HTML sau adnotări definite) îl pot avea în creşterea eficienţei sistemelor actuale de regăsire a

informaţiei. Mai mult, se investighează şi efectul spam-ului asupra rezultatelor regăsirii. Scopul

acestui studiu este de a îmbunătăţi metrica MAP (mean average precision) şi precizia în poziţia 10

(P@10). Experimentele studiului sunt efectuatepe subsetul Category B al colecţiei ClueWeb09.

5.2.2 Model hibrid de regăsire ad-hoc a informaţiei

În această secţiune se descrie abordarea propusă pentru regăsirea ad-hoc. Se consideră patru

componente majore ale IR pentru Web: dependenţa termenilor interogării, expansiunea interogării,

filtrarea spam-ului şi regăsirea bazată pe câmpuri. Primele trei abordări s-au dovedit a fi o parte

importantă a sistemelor de regăsire Web de către participanţii ultimilor conferinţe TREC, în timp ce

ultima abordare nu este la fel de bine explorată atunci când este combinată cu modelele anterioare.

5.2.2.1 Modelarea dependinţei termenilor

Modelul de dependenţă (DM) (Metzler & Croft, 2005) este o structură formală de rescriere a unei

interogări folosind câmpuri aleatoare Markov (Markov Random Fields) cu scopul de a obţine o mai

bună reprezentare introgării originale. Modelul permite utilizarea mai multe tipuri de evidenţă ale

textului (caracteristici) cum ar fi prezenţa termenilor unici, expresii ordonate (ferestre ordonate) şi

expresii neordonate (ferestre neordonate) ca funcţii de caracteristici cu valori reale.

Termenilor singulari, expresiilor ordonate şi celor neordonate le sunt atribuite diferite ponderi

(λT pentru termeni, λO pentru expresiile ordonate şi λU pentru expresiile neordonate), care sunt

determinate pentru a optimiza impactul asupra eficienţei sistemului. Unul dintre principalele

rezultate ale acestui model este faptul că aceste trei caracteristici ale modelului surprind doar

aspectele generale ale textului deoarece ponderile asociate (λT=0,8, λO=0,1, λU=0,1) sunt valabile

peste mai multe colecţii Web.

24

5.2.2.2 Modelarea relevanţei şi expansiunea interogării

Modelul de relevanţă (RM) (Lavrenko & Croft, 2001) este o metodă efectiv formală pentru

estimarea probabilităţilor noilor termeni într-un set necunoscut de documente relevante la termenii

interogării fără date de antrenament. De obicei, metoda începe cu o interogare iniţială, apoi se

efectuează câteva operaţii asupra ei şi, la final, returnează o listă cu termeni pentru expansiune.

Aceşti termeni sunt apoi adăugaţi la interogarea originală şi sistemul este supus procesului de

regăsire cu noua interogare extinsă.

5.2.2.3 Modelarea câmpurilor specifice

Deoarece modelul de dependenţă acoperă aspectele generale ale unei interogări şi modelul de

relevanţă furnizează o extindere a interogării cu termeni de acelaşi tip, este o provocare în plus de a

analiza dacă mai multe caracteristici specifice pot aduce unele îmbunătăţiri eficienţei sistemului.

Documentele Web sunt pagini structurate care conţin elemente definite de autori sau adnotări

asociate de alte persoane sau procese (Zhai & Lafferty, 2001). Modelul regăsirii bazate pe câmpuri

(FM) ar putea fi o soluţie pentru o focalizare mai specifică cu privire la caracteristicile colecţiilor

Web, de exemlu formula BM25F (Robertson, et al., 2004). Mai mult, prin agregarea modelului bazat

pe câmpuri cu precedentele modele se aşteaptă ca eficienţa sistemului să crească. Cu aceste premise

se poate construi un model combinat care încorporează caracteristici ale dependenţei, relevanţei şi

aspectele bazate pe câmpuri. Prin urmare, putem lua în considerare cinci câmpuri specifice

documentelor HTML (adică body, title, heading, inlink şi strong) care au fost indexate la momentul

indexării documentelor.

5.2.2.4 Modelarea filtrului de spam

Deoarece colecţia ClueWeb09 conţine foarte multe documente considerate spam, rezultatele regăsirii

pot de asemenea să conţină documente spam, ceea ce ar avea o influenţă negativă asupra

performanţelor sistemului. Pentru detectarea şi stergerea documentelor spam din cadrul listei de

documente regăsite se foloseşte metoda propusă de (Cormack, et al., 2011), ca un pas de post

regăsire. Acest proces constă în asocierea unei valori procentuale ( ) fiecărui document din

colecţia ClueWeb09. Pentru Categoria B a colecţiei ClueWeb09 s-au exclus 10% din documente

care sunt considerate cel mai probabil spam prin metoda de fuziune. Această rată a fost determinată

experimental, cu scopul de a optimiza metrica MAP cu interogările Web Track 2009.

5.3 Algoritm de clusterizare a unui site

Implementarea eficientă a unui algoritm de clusterizare constă în găsirea unor relaţii intrinseci,

precum asemănările şi deosebirile dintre documentele web (Hou & Zhang, 2003).

Având modelul de document web propus şi ţinând cont că paginile web sunt grupate sub forma

unui site, putem proiecta un algoritm de clusterizare specific. Algoritmul de clusterizare propus

constă în două faze. Prima fază este dată de clusterizarea unui site, în care toţi termenii din colecţie,

respectiv matricea , sunt clusterizaţi pe acelaşi nivel fără, nici o ierarhie între documentele

aceluiaşi cluster. În acest punct un site este reprezentat sub forma unei colecţii de clustere, fiecare

cluster fiind compus dintr-un grup de termeni, care la rândul lor provin dintr-o mulţime de pagini

25

web. Faza a doua a algoritmului constă într-o sortare topologică a tuturor documentelor web din

fiecare cluster, anume luând în calcul lista de legături (in-site-links) din interiorul site-ului pentru

fiecare document. În Figura 5.1: Etapele algoritmului de clusterizare sunt ilustraţi grafic paşii

algoritmului.

Figura 5.1: Etapele algoritmului de clusterizare

Iniţial, se aplică procesul de clusterizare asupra unui site prin intermediul matricei de termeni

. Prin urmare, se poate observa că fiecare cluster poate fi reprezentat sub forma unui grup de

documente care conţin toţi termenii din clusterul respectiv. Această abordare are un mare avantaj şi

anume poate produce clustere care se suprapun, un singur document putând să aparţină mai multor

clustere.

Prima fază a algoritmului de clusterizare are la bază algoritmul K-Means în care site-ul este

reprezentat sub forma unei colecţii de clustere de bază (CL), fiecare cluster de bază fiind compus

dintr-un grup de termeni care aparţin unor pagini din site. Faza a doua a algoritmului constă în

sortarea topologică a tuturor documentelor dintr-un cluster. În mod obişnuit documentele web sunt

ordonate conform unei funcţii de similaritate, dar rolul fiecărui document în cadrul clusterului poate

fi pus în evidenţă şi de legăturile pe care le are un document cu documentele din acelaşi cluster, cu

documentele din celelalte clustere sau cu documentele din afara colecţiei. Luând în considerare lista

in-site-links de legături a fiecărui document dintr-un cluster şi faptul că un document este mai

important cu cât are mai multe legături cu documentele din acelaşi cluster sau cu documentele din

site, fiecare cluster de bază poate fi reprezentat ca o ierarhie de documente. Procesul de ordonare a

documentelor dintr-un cluster este descris în etapa a doua a algoritmului de clusterizare.

Provocare majoră a celei de a doua faze este dată de eliminarea unui număr de muchii din

digraful care contrazic proprietatea de a fi aciclic. În mod intuitiv, pentru a nu pierde

o cantitate mare din informaţia potenţial folositoare, numărul de muchii care trebuie eliminat trebuie

să fie minim. Pentru fiecare nod al gradului orientat se disting două tipuri de arce:

arce in-cluster, arcele unui nod, cu excepţia nodului out, care nu referă sau nu este referit de

nodul out,

muchii out-cluster, arcele care fac legătura dintre nodul out şi celelalte noduri ale digrafului.

Odată ce ciclul este rupt, putem sorta nodurile după criteriul “nodul cu cel mai mic număr de muchii

in-cluster primul”, adică o pagină care are cel mai mic număr de legături spre documentele din

26

acelaşi cluster este prima în listă. Când avem două noduri cu același număr de arce in-cluster,

definim un alt criteriu și anume “nodul cu cel mai mic număr de muchii out-cluster primul”. În acest

mod obținem o listă ordonată descrescător de documente web care poate fi accesată usor de către

utilizator.

Deoarece normalizarea documentului este facută odată cu ponderea termenilor, prin factorul de

normalizare cosinus sau pivot, putem observa faptul că algoritmul de clusterizare este independent

de ordinea documentelor obținută în urma sortării topologice. Nu este dificil de a demonstra că

algoritmul are complexitatea O(l*p*logp) + O(m +n), unde l este numărul de clustere, p este

numărul de documente supuse clusterizării, n este numărul de noduri și m este numărul de muchii

pentru toate digrafurile .

5.4 Concluzii

În acest capitol au fost prezentate principalele contribuţii originale aduse în cadrul acestei lucrări de

către autor. În primul subcapitol a fost studiată problema preprocesării informaţiei prin analiza

câtorva procedee de reducere a dimensiunii vectorului de reprezentare şi de creştere a ponderii

termenilor în cadrul acestui vector. În subcapitolul 2 s-a propus un nou model de reprezentare a unui

de document Web, bazat pe tag-uri, legături şi o structură ierarhică a Web-ului. În subcapitolul 3 s-a

abordat problema regăsirii informaţiei pe Web prin propunerea unui nou model hibrid de modelare a

unui sistem de regăsire a informaţiei, care cuprinde modelul de dependenţă, cel de relevanţă, cel

bazat pe câmpuri şi cel de filtrare a spamului. În final, a fost propus un algoritm de organizare a

conţinutului Web prin care s-a urmărit clusterizarea documentelor din cadrul unui site cu scopul de a

crea o ierarhie a documentelor în cadrul colecţiei.

27

6. Evaluare

6.1 Studiul metricilor de evaluare folosite în regăsirea informaţie

având în vedere modul în care utilizatorii efectuează o căutare

În cadrul acestui studiu, pentru studierea modului de satisfacere a nevoii de informaţie a

utilizatorului, s-au luat în considerare două tipuri de metrici: metrici care sunt utilizate pentru

regăsirea ad-hoc şi metrici folosite în regăsirea diversificată, după cum s-a văzut în secţiunea 4.2.

6.1.1 Comparaţia metricilor

Pentru început, se doreşte identificarea relaţiilor existente atât între metricile utilizate de către un

anumit tip de regăsire cât şi relaţiile dintre metricile celor două direcţii ale regăsirii informaţiei.

Pentru fiecare metrică, cele 70 de experimente pot fi ordonate descrescător (de la cea mai mare

valoare a unei metrici la cea mai mică valoare a aceleiaşi metrici), obţinând astfel 8 ordonări ale

experimentelor. Aceste ordonări, dintre diferite metrici, sunt apoi comparate folosind coeficientul de

corelaţie Kendall, . Coeficientul de corelaţie Kendall este o metrică care măsoară similaritatea

(nivelul de potrivire) dintre două seturi de date ordonate.

Tabelul 6.1: Coeficientul de corelaţie Kendall dintre diferite metrici de regăsire pentru cele 60 de

experimente TREC şi cele 10 experimente suplimentare. Toţi coeficienţii sunt semnificativi statistic

la un nivel de încredere de 95% (α=0,05).

P@20 MAP nDCG@20 ERR@20 α-nDCG@20 P-IA@20 MAP-IA

MAP 0,736 1

nDCG@20 0,790 0,649 1

ERR@20 0,577 0,425 0,725 1

α-nDCG@20 0,689 0,563 0,680 0,750 1

P-IA@20 0,855 0,738 0,730 0,542 0,679 1

MAP-IA 0,691 0,914 0,619 0,406 0,562 0,719 1

ERR-IA@20 0,662 0,540 0,653 0,755 0,945 0,648 0,551

Corelaţia dintre diferite perechi de metrici de regăsire este ilustrată în Tabelul 6.1. Dacă

presupunem că relaţia dintre metrici este liniară, se obţine o linie drepată care reprezintă cea mai

bună potrivire dintre metricile în cauză. Coeficientul de corelaţie Kendall nu face această

presupunere deoarece este bazat pe ordinea datelor analizate.

6.1.2 Rezultate şi discuţii

Deşi metricile au fost concepute pentru a măsura aspecte diferite ale unui proces de regăsire, figurile

6.12, 6.19 şi 6.29 indică faptul că există o relaţie puternică între metricile şi

( ), şi ( ), respectiv şi ( ).

Acest lucru nu este surprinzător, deoarece aceste metrici de tipul „intent aware” folosite pentru

regăsirea diversificată sunt bazate pe principiile definite în (Agrawal, et al., 2009), unde o metrică de

tipul „intent aware” analizează fiecare sub-interogare ca o interpretare distinctă a interogării

28

asociate. Metricile standard de evaluare sunt calculate separat în raport cu fiecare interpretare, iar

apoi sunt calculate mediile ponderate peste diversele interpretări pentru a obţine versiunile de tipul

„intent aware” ale metricilor standard. Deşi (Agrawal, et al.) permite atribuirea unei probabilităţi

fiecărei interpretări, experimentele derulate au tratat fiecare interpretare în mod egal. Metricile

şi măsoară acurateţea primelor 20 de poziţii din lista returnată în cazul regăsirii

ad-hoc, respectiv regăsirii diversificate şi încearcă să îmbunătăţească satisfacţia utilizatorului, luând

în considerare comportamentul lui (majoritatea utilizatorilor caută informaţii doar pe prima pagină a

unui motor de căutare). Metricile şi iau în calcul şi cantitatea de documnte

relevante returnate raportată la cantitatea de documente relevante existente pentru un anumit subiect,

adică reapelul. Dacă nu ma sunt documente relevante după o anumită poziţie , atât cât şi

îşi vor păstra valoarea din ultima poziţie care a avut un document relevant. Metricile

şi iau în calcul diferite grade de relevanţă ale documentelor şi reduc rapid

contribuţia documentelor care se află după un document foarte relevant. Probabilitatea ca un

utilizator să termine căutarea creşte odată ce a găsit unul sau mai multe documente foarte relevante.

Totodată, acest lucru presupune că utilizatorul nu este mulţumit de nici un document anterior

documentelor foarte relevante. În timp ce valorile sunt corelate, există diferenţe clare de performanţă

relativă ale experimentelor în raport cu aceste măsuri. Coeficienţii de corelaţie rezultaţi pentru

perechile de metrici de mai sus sugerează faptul că documentele relevante de pe primele 20 de

poziţii joacă un rol important atât în metricile care urmăresc returnarea celor mai relevante

documente în primele poziţii, cât şi metricile care iau în calcul toată lista de documente returnate de

către sistem. Între metricile şi nu există aceeaşi legătură puternică

( ), o posibilă explicaţie fiind faptul că metricile acumulează câştigul şi parametru are un

rol hotărâtor în calculul vectorului de câştig.

Cel mai mare coeficient de corelaţie îl are perechea de metrici şi

( ). Acest coefficient se datorează scopului comun pe care îl au cele două

metrici: returnarea celor mai relevante documente care să acopere toate sub-interogările unui subiect.

Prima metrică reduce rapid contribuţia documentelor care se află după un document foarte relevant,

deoarece interesul utilizatorului se reduce dramatic odată cu satisfacerea nevoii de informaţie, iar a

doua metrică consideră că documentele relevante sunt mai utile când apar mai repede în listă. Totuşi,

metrica reflectă mai bine comportamentul de navigare al utilizatorului şi cuantifică

mai precis satisfacţia lui decât metrica , prin faptul că nu mai ia în considerare

contribuţia documentelor relevante aflate după un document „perfect”.

Rezultatele prezentate sugerează cel puţin două categorii de metrici: metrici cu o puternică

tendinţă de a clasa documentele relevante cât mai sus ( , , şi

) şi metrici care surprind un aspect sumar al performanţei ( şi ).

Metricile şi par să împartă proprietăţi aparţinând ambelor categorii.

Deşi metrica este intens acceptată ca metrică de facto de evaluare a sistemelor de regăsire

a informaţiei, aceasta nu corespunde neapărat modului în care utilizatorii efectuează o căutare. Acest

lucru este îngrijorător deoarece rezultatele indică faptul că corelaţiile dintre cele două categorii de

metrici sunt slabe (coeficientul Kendall având valori mai mici de 0,7).

29

Pentru regăsirea informaţiei pe Web se poate trage următoarea concluzie: dacă obiectivul

utilizatorului nu este clar stabilit, precizia şi reapelul nu pot fi optimizate, fiind metrici contrare.

Astfel, sistemele de regăsire nu reuşesc întotdeauna să răspundă nevoilor, de cele mai multe ori,

ambigue ale factorului uman. Navigarea este o paradigmă puternică şi confortabilă, generând efectul

de serendipitate. Rezultatul unei căutări nu trebuie să fie neapărat foarte bun, foarte exact. Precizia

nu este importantă atâta timp cât cel puţin unele dintre rezultatele de pe prima pagină sunt bune, iar

reapelul nu este important atâta timp cât se obţin cel puţin câteva rezultate concludente.

6.2 Evaluarea modelării şi clusterizării documentelor web

6.2.1 Metrici folosite pentru comparaţie

Măsurarea eficienței şi eficacităţii unui algoritm de clusterizare este o sarcină dificilă. În cadrul

acestui studiu s-au folosit cinci metrici de performanță: precizia, reapelul, măsura F, precizia medie

şi media valorilor medii ale preciziei (MAP) pentru a măsura acurateţea abordării. Primele trei

metrici pot fi aplicate asupra clusterilor obţinuţi după prima fază a algoritmului întrucât nu ţin cont

de ordinea documentelor din cadrul clusterelor, ci se bazează doar pe apartenenţa documentelor la un

anumit cluster. Pentru algoritmii care returnează secvențe ordonate de documente este oportun să se

considere şi ordinea în care documentele sunt returnate. Precizia medie implică calcularea unei

precizii medii în fiecare poziţie care are un document relevant în lista returnată. Aceste metrici au

fost adaptate din regăsirea informaţiei pentru a măsura relevanţa documentelor aflate într-un cluster

la nevoile utilizatorului. Fiind dat un document web, notăm clusterul real de care aparţine cu şi

cel determinat experimental cu . Pentru un cluster determinat experimental, , definim

precizia, reapelul şi măsura F după cum urmează:

( )

(| |)

| | (6.1)

( )

(| |)

| | (6.2)

( ) ( ) ( )

( ) ( ) (6.3)

unde | | este numărul de documente din clusterul și | | este numărul de documente din

clusterul .

6.2.2 Rezultate şi discuţii

S-au efectuat experimente pentru a evalua îmbunătăţirile pe care le aduce algoritmul propus faţă de

regăsirea normală, utilizând ca metricile propuse în secţiunea anterioară. Pentru a evalua într-o

manieră sistematică rezultatele obţinute în urma celor doua faze ale algoritmului şi pentru a procesa

şi sorta manual graful orientat construit în faza a doua a algoritmului primul set de documente a fost

reprezentat de un mic site (S1), cu o colecție de 23 de pagini care are 867 de termeni unici şi 64 de

legături. Al doilea set de test a fost un site mai mare (S2), cu un număr total de documente şi legături

de 3240 şi respectiv 14291.

30

Algoritmul de clusterizare cu factorul de normalizare cosinus este notat cu SCLA(C), iar

algoritmul care folosește normalizarea documentului cu pivot cu SCLA(Lnu). Atunci când este

aplicată regăsirea normală algoritmul este notat cu SCLA(N-C) şi respectiv cu SCLA(N-Lnu).

Rezultatele obţinute în urma regăsirii normale sunt apoi comparate cu rezultatele obţinute în urma

aplicării modelului propus, cu cele două variante. Astfel, se demonstrează îmbunătăţirea obţinută

prin folosirea de ponderi distincte pentru fiecare clasă de tag-uri implicată în calcularea ponderii

unui termen în cadrul documentului web. Evaluarea este efectuată după prima fază a algoritmului şi

este reprezentată ca fiind valoarea medie a acurateței în clusterele de bază.

În cadrul experimentelor pe colecția S1 s-a verificat manual ca fiecare termen să fie clusterizat şi

s-a decis asupra asocierii corecte la un anumit cluster. În acestă etapă de analiză a algoritmului este

rezonabil să se folosească o asemena metodă întrucât s-a urmărit clusterizarea documentelor web cât

mai obiectiv posibil. Pentru prima fază a algoritmului, numărul de clustere (parametru l) a fost dat de

numărul de termeni din cadrul interogării. Site-ul S1 are 23 de documente şi conform relaţiei

precedente numărul de clustere este .

Figura 6.1: Precizia clusterelor de bază pentru colecţia S1

Figura 6.2: Reapelul clusterelor de bază pentru colecţia S1

0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

CL1 CL2 CL3 CL4 S1

Pre

cizi

a

Clusterele colecţiei S1 , respectiv colecţia S1

SCLA( C ) SCLA(Lnu) SCLA(N-C) SCLA(N-Lnu)

0

0.2

0.4

0.6

0.8

1

CL1 CL2 CL3 CL4 S1

Rea

pel

Clusterele colecţiei S1, respectiv colecţia S1

SCLA( C ) SCLA(Lnu) SCLA(N-C) SCLA(N-Lnu)

31

Cum era de aşteptat, rezultatele modelului care foloseşte factorul de normalizare a documentului

cu pivot sunt superioare rezultatelor obţinute cu regăsirea normală. Este interesant de observant

faptul că modelul de document cu factorul de normalizare cosinus furnizează rezultate mai bune faţă

de ambele modele normale de regăsire (cel cu factorul de normalizare cosinus şi cel cu pivot).

Aceste rezultate dovedesc utilitatea metodei abordate. Rezultate asemănătoare au fost obţinute şi

pentru colecţia S2.

Documentele din fiecare cluster obţinut în urma primei faze au fost evaluate şi cu precizia

medie. Rezultatele sunt ilustrate în Figura 6.3.

Figura 6.3: Precizia medie a clusterelor de bază pentru colecţia S1.

După prima fază a algoritmului documentele din acelaşi cluster reprezintă aceeşi arie de

informaţie şi au acelaşi factor de importanţă pentru interogarea utilizatorului. În consecinţă, în faza a

doua, am ordonat documentele dintr-un cluster prin construirea unui digraf şi sortarea topologică a

nodurilor lui, noduri care sunt reprezentate de documentele clusterului, ținând cont de hiper-

legăturile dintre documentele site-ului, care formează arcele digrafului. Sortarea topologică nu poate

fi aplicată asupra unui digraf care are cicluri, drept urmare, trebuie să eliminăm un număr minim de

arce pentru ca digraful să dobândească proprietatea de aciclicitate. În acest scop, considerăm că

arcele care fac legătura dintre nodurile din cluster cu nodurile care nu se află în interiorul clusterului

(nodul out) au o importanţă mai scăzută şi pot fi îndepărtate primele. Digraful pentru primul cluster

de bază din S1 este ilustrat în Figura 6.4.

Figura 6.4: Digraful pentru clusterul de bază CL1 din colecţia S1

0.175

0.18

0.185

0.19

0.195

0.2

0.205

0.21

0.215

0.22

CL1 CL2 CL3 CL4 S1

Pre

cizi

a m

edie

Clusterele colecţiei S1, respectiv colecţia S1

SCLA(Lnu) SCLA(N-Lnu)

32

Numerele asociate muchiilor reprezintă ordinea în care arcele sunt eliminate când sortăm

topologic documentele. Documentele cu cea mai mică importanţă sunt primele în listă. După cum se

observă, digraful are un ciclu reprezentat de nodurile ⟨ ⟩, numărul de arce care întră în

noduri (in-degree) fiind ⟨ ⟩. Deoarece nodul d4 are o muchie care provine de la nodul out,

acest nod este mai puţin important ca nodul d7 şi este ales pentru a sparge ciclul prin eliminarea

arcului care vine din nodul d7 (e74). Lista sortată de documente în clusterul CL1 după spargerea

ciclului este: ⟨ ⟩. Prin eliminarea unui arc se pierde şi o cantitate din

informaţia potenţial folositoare.

6.3 Evaluarea regăsirii informaţiei

6.3.1 Configurarea simulării

Pentru a putea evalua modelul propus în secţiunea 5.3.3, mai întâi, se descriu pe scurt modul de

indexare a colecţiei ClueWeb09, modul de determinare a parametrilor Dirichlet de uniformizare,

valorile ponderilor câmpurilor specifice şi valoarea procentuală optimă pentru filtru de spam. Apoi,

valorile optimie determinate sunt utilizate pentru a testa şi evalua fiecare model din cadrul modelului

agregat propus, precum şi combinaţiile lor.

Pentru experimente s-a utilizat subsetul Category B din colecţia ClueWeb09, care reprezintă un

eşantion de 50 de milioane de pagini în limba engleză din colecţie (5% din întreaga colecţie).

Această colecţie conţine majoritatea paginilor Web importante deoarece paginile Web au fost

colectate pe baza unei liste mari de URL-uri cu un scor PageRank ridicat. Această idee este susţinută

şi de concluziile conferinţei TREC 2010 care sugerează că subsetul Category B conţine, în general,

documente de o calitate mai ridicată faţă de restul colecţiei (Clarke, et al., 2011). În experimentele

prezentate, parametrii sunt determinaţi cu interogările de la TREC Web Track 2009, iar

experimentele sunt efectuate cu interogările oferite de TREC Web Track 2010.

Sistemul ales pentru efectuarea experimentelor a fost Indri 5.1 din cadrul proiectului Lemur,

care a fost modificat pentru indexarea colecţiei ClueWeb09. Indexul a fost construit prin intermediul

unei maşini de calcul având 1.4 GHz CPU, 30 GB de RAM şi aproximativ 5 TB spaţiu liber de

stocare. Construirea indexului pentru subsetul Category B a durat aproximativ 68 de ore. Pe durata

procesului de indexare s-a realizat îndepărtarea cuvintelor din lista stopwords şi efectuarea

procesului de stemming cu stemmerul Krovetz (Krovetz, 1993) deoarece acesta nu generealizează

aşa de mult precum stemmerul Porter. De asemenea, s-au indexat anumite tag-uri HTML sub formă

de câmpuri: tag-ul title sub forma câmpului title, tag-urile h1, h2, h3, h4, h5, h6 sub forma câmpul

heading, tag-ul a sub forma câmpului inlink şi tag-urile strong şi b sub forma câmpului strong. Cu

excepţia tag-ului title, conţinutul întregului document a fost indexat sub forma câmpului body.

Astfel, câmpurile indexate pot fi utilizate pentru regăsire în cadrul limbajului de interogare Indri. În

final, se obţine un index care conţine tot conţinutul text al unui document web şi câmpurile specifice,

supuse regăsirii.

Armstrong (2009) a demonstrat faptul că există şase tehnici care oferă unele îmbunătăţiri asupra

performanţei unui sistem de regăsire a informaţiei. Aceste tehnici sunt prezentate în primele 6

rânduri ale Tabelul 6.2 cu câteva modificări şi adaptări. Armstrong a observat că există o relaţie de

33

aditivitate între numărul de tehnici folosite şi eficienţa de regăsire realizată. Pentru experimentele

următoare se face următoarea presupunere: prin adăugarea modelului bazat pe câmpuri şi a

modelului de filtrare a spam-ului la metodele stabilite de Armstrong, caracteristica de aditivitate se

conservă, iar eficienţa de regăsire creaşte.

Tabelul 6.2: Tehnicile abordate în experimente

Tehnica Descriere

Stoparea

termenilor

Lista standard inclusă în Indri cu cele 418 de cuvinte din limba engleză care

trebuie eliminate (stopwords list).

Stemming Stemmerul Krovetz (Krovetz, 1993).

Uniformizarea

termenului

Uniformizarea Dirichlet (Zhai & Lafferty, 2004) cu parametru µ determinat

pentru fiecare metodă în parte.

Expresii ordonate Ferestre ordonate de proximitate – secvenţe de câte 2 sau 3 termeni de

interogare în care termenii trebuie să apară ordonaţi fără alţi termeni între

fiecare apariţie (Metzler & Croft, 2005).

Expresii

neordonate

Ferestre neordonate de proximitate – pentru fiecare combinaţie de 2 sau 3

termeni de interogare, termenii pot să apară în orice ordine în ferestre cu o

dimensiune maximă de patru ori numărul de termeni ai expresiei (Metzler &

Croft, 2005).

Pseudo-

relevanţa

feedback-ului

Modelul de relevanţă din cadrul sistemului Indri cu 20 de termeni selectaţi

automat din primele 10 documente, ponderea interogării originale fiind 0,5

iar a celei extinse de 0,5.

Expresii bazate pe

câmpuri

Model ponderat implementat pentru a construi interogări dependente de

câmpuri pentru regăsirea textului structurat.

Filtrarea spam-

ului

Filtrarea spam-ului ca pas de post-regăsire (Cormack, et al., 2011).

Primele două tehnici din Tabelul 6.2 – stoparea şi stemmingul termenilor – sunt aplicate tuturor

metodelor deoarece acestea sunt realizate în momentul indexării colecţiei de documente Web.

Metoda de uniformizare este realizată pentru fiecare model conform fazei de determinare a

parametrilor. Fiecare metodă prezentată în Tabelul 6.2 este testată separat obţinând-se experimentele

DM, RM, FM şi SFM. Apoi, se combină fiecare tehnică cu alta, obţinând exerimentele DM+RM,

denumit şi RM3 (Smucker, et al., 2009), DM+FM şi RM+FM. Într-un experiment final, se combină

toate cele patru metode rezultând rularea DRF3. Modelul de filtrare a spam-ului (SFM) este aplicat

opţional, ca un pas de post-regăsire.

6.3.2 Determinarea parametrilor optimi

Determinarea valorilor optime ale parametrilor utilizaţi în experimente se face prin maximizarea

directă a metricii . Deoarece metodele abordate au puţini parametrii, este posibil efectuarea unei

căutări liniare pentru: atingerea parametrului de uniformizare optim, determinarea ponderii

34

interogării de expansiune şi a nivelului optim pentru filtrul de spam. De asemenea, se poate efectua o

căutare de tipul „hill climbing” pentru a determina valorile ponderilor optime ale câmpurilor din

cadrul modelului bazat pe câmpuri, începând cu valorile implicite ale acestor parametrii (λBODY = 1,

λTITLE = 0, λHEADING = 0, λINLINK = 0, λSTRONG = 0).

Deoarece modelul lingvistic are la bază noţiunea de probabilitate, uniformizarea este o problemă

majoră în estimarea modelului lingvistic. Unele cercetări (Zhai & Lafferty, 2001) au concluzionat că

o schemă de uniformizare simplă bazată pe uniformizarea Dirichlet oferă o performanţă foarte bună,

datorită modului eficient în care normalizează termenii interogării în raport cu lungimea

documentului. Toate experimentele utilizează modelul lingvistic Indri şi regula de uniformizare

Dirichlet. De asemenea, (Zhai & Lafferty, 2001) au arătat că uniformizarea Dirichlet depăşeşte

semnificativ uniformizarea Jelinek-Mercer dacă este aplicată asupra activităţilor de regăsire

structurate. Pentru a determina parametru de uniformizare optim s-a efectuat o căutare liniară prin

parcurgerea intervalului 1000 – 8000, cu un pas de 500 şi cu scopul de a maximiza metrica .

Valorile optime sunt prezentate în Tabelul 6.3. Aşa cum se arată în continuare, motivul pentru care

valorile optime ale parametrului de uniformizare pentru subiectele Web Track 2009 şi 2010 sunt

diferite poate fi atribuit faptului că subiectele Web Track 2010 conţin cu 12% mai multe interogări

cu un singur termen decât subiectele WebTrack 2009.

Tabelul 6.3: Parametrul optim de uniformizare Dirichlet pentru interogările Web Track 2009 şi 2010

asupra colecţiei ClueWeb09 Categoria B.

Subiecte DM RM FM RM3 DM+FM RM+FM DRF3

Dirichlet (µ) WT2009 3000 1500 3000 2000 3000 2500 2000

WT2010 4000 2000 4000 2500 4000 3000 2500

Pentru determinarea ponderii optime pentru interogarea extinsă din cadrul modelului de

relevanţă se aplicată acelaşi principiu care este folosit în determinarea parametrului de uniformizare

Dirichlet. Ponderea interogării extinse este căutată în intervalul 0 – 0,9 cu un pas de 0,1. Valoarea

care furnizează cele mai bune rezultate pentru fiecare experiment care implică expansiunea

interogării s-a dovedit a fi . Valorile optime determinate cu ajutorul interogărilor Web

Track 2009 sunt utilizate în experimentele următoare.

Pentru a determina valorile ponderilor câmpurilor specifice se aplică o căutare de tipul „hill

climbing” având drept obiectiv maximizarea metricii MAP. Pe parcursul acestei căutări se foloseşte

parametru de uniformizare Dirichlet cu valoarea standard μ=2500. Valorile optime ale ponderilor

găsite pentru câmpurile specifice (body, title, heading, inlink şi strong) care maximizează metrica

MAP sunt prezentate în Tabelul 6.4. Prin câmpul body se face referire la conţinutul documentului

care este cuprins în tag-ul HTML body.

Nivelul optim al filtrului de spam este determinat în aceeasi manieră ca şi parametrul de

uniformizare. Valoarea procentuală care optimizează metrica MAP este 10%.

35

Tabelul 6.4: Valorile optime ale ponderilor pentru câmpurile specifice pentru interogările Web

Track 2009 şi 2010 împotriva colecţiei ClueWeb09 Category B.

Queries Body Title Heading Inlink Strong

Raw values wt2009 0.95 0.12 0.18 0.14 0.17

wt2010 1.12 0.21 0.13 0.15 0.17

Normalized values wt2009 0.6 0.08 0.12 0.09 0.11

wt2010 0.63 0.12 0.07 0.08 0.1

6.3.3 Rezultate şi discuţii

Din moment ce ne ocupăm de trei modele diferite, prin combinarea lor, vom obţine şapte combinaţii

unice care sunt apoi rulate împotriva colecţiei, iar seturile de documente rezultate sunt evaluate cu

ajutorul metricilor MAP şi P@10 înainte şi după etapa de post-regăsire a filtrării spam-ului. S-a ales

ca metodă de referinţă combinaţia dintre modelul de dependenţă şi modelul de relevanţă, adică

rularea RM3. De asemenea, este furnizată ca referinţă iniţială, pentru toate metodele şi metoda Indri

standard, denumită în continuare rularea Indri.base. Modelul Indri standard se bazează pe o

combinaţie a modelării lingvistice (Ponte & Croft, 1998) cu reţelele de inferenţă (Turtle & Croft,

1991). Rezultatele sunt prezentate în Tabelul 6.5. Semnificaţia statică a fost calculată utilizându-se

metoda Paired Randomization Test (Smucker, et al., 2007). În Tabelul 6.5 se folosesc simbolurile *

şi ** pentru a indica semnificaţia statistică la 90% şi respectiv 95% nivel de încredere.

Tabelul 6.5: Metricile MAP şi P@10 folosind valorile optime ale parametrilor pentru fiecare model

sau combinaţie şi valoarea procentuală optimă a filtrului de spam cu cea mai mare valoare a fiecărei

metrici evidenţiată1.

Runs No Spam Filter Spam Filter at 10%

MAP ∆RM3 P@10 ∆RM3 MAP ∆RM3 P@10 ∆RM3

Indri.base 0.0917 -12.95%**

0.2062 -20.8%**

0.1004 -12.1%* 0.2542 -15.28%

*

DM 0.0972 -7.6% 0.2354 -9.6% 0.1064 -6.86% 0.2833 -5.56%

RM 0.0941 -10.65%**

0.2250 -13.6% 0.1000 -12.42%**

0.2625 -12.5 %*

FM 0.1025 -2.6% 0.2583 -0.8% 0.1095 -4.14% 0.3083 +2.78%

RM3 0.1053 - 0.2604 - 0.1142 - 0.3000 -

DM+FM 0.1091 +3.6% 0.2979 +14.4% 0.1151 +0.75 0.3312 +10.42%

RM+FM 0.1048 -0.46% 0.2792 +7.2%* 0.1089 -4.64% 0.3062 +2.08%

DRF3 0.1181 +12.14%**

0.3188 +22.4%**

0.1246 +9.03%* 0.3438 +14.58%

*

După cum se poate observa, rularea DRF3 oferă cele mai bune rezultate şi conduce la

îmbunătăţiri semnificative ale metricilor MAP şi P@10 în raport cu rularea de referinţă RM3,

1 Coloanele ∆RM3 arată îmbunătăţirile relative ale fiecărei metrici în raport cu metoda de referinţă RM3. Stelele

indică semnificaţia statistică cu un nivel de încredere de 90% (*) şi respectiv 95% (**).

36

arătând astfel că structura documentelor Web poate fi utilizată pentru a îmbunătăţi regăsirea ad-hoc a

informaţiei. Toate rezultatele rulării DRF3 sunt semnificative din punct de vedere statistic. Înainte de

faza de filtrare a spam-ului nivelul de încredere este la 95%, în timp ce după îndepărtarea

documentelor considerate spam nivelul de încredere scade la 90%. Faza de filtrare a spam-ului aduce

o îmbunătăţire substanţială chiar şi celei mai bune rulări: metrica MAP creşte cu 5,5% de la 0,1181

la 0,1246, iar metrica P@10 creşte cu 7,84% de la 0,3188 la 0, 3438.

Figura 6.5: Evoluţia metricii MAP ca funcţie de modele combinate în cadrul mediului Indri

împotriva colecţiei ClueWeb09 Category B înainte şi după faza de filtrare a spam-ului.

Figura 6.6: Evoluţia metricii P@10 ca funcţie de modele combinate în cadrul mediului Indri

împotriva colecţiei ClueWeb09 Category B înainte şi după faza de filtrare a spam-ului.

Figura 6.5 şi Figura 6.6 ilustrează rezultatele obţinute de către metricile MAP şi P@10 ca funcţii

de tehnici combinateîn cadrul mediului Indri. Se poate observa că proprietatea de aditivitate se

conservă şi eficienţa sistemului creşte în mod corespunzător atunci când sunt combinate mai multe

modele.

0.09

0.095

0.1

0.105

0.11

0.115

0.12

0.125

Indri.base DM RM FM RM3 DM+FM RM+FM DRF3

MA

P (

%)

Model

No Spam Filter Spam Filter at 10%

0.2

0.22

0.24

0.26

0.28

0.3

0.32

0.34

0.36

Indri.base DM RM FM RM3 DM+FM RM+FM DRF3

P@

10 (

%)

Model

No Spam Filter Spam Filter at 10%

37

Modelul bazat pe câmpuri conţine câmpurile title, heading, inlink, strong şi body. Ponderile care

optimizează metrica MAP pentru fiecare câmp din modelul bazat pe câmpuri sunt enumerate în

Tabelul 6.4. Dacă se inspectează fiecare câmp în parte, se observă că câmpul inlink are o precizie

ridicată, fapt observat şi de altii (Koolen & Kamps, 2010), (Nguyen & Callan, 2010). Cu toate

acestea, metrica MAP obţinută de primele patru câmpuri este mult mai mică în comparaţie cu cea

obţinută prin câmpul body. Motivul pentru această valoare ar putea fi faptul că nu toate documentele

Web conţin aceste câmpuri şi faptul că câmpul body, pe lângă faptul că include câmpurile heading,

inlink şi strong mai include şi restul de informaţii utile. În plus, când se aplică filtrul de spam,

metrica P@10 a câmpului body se îmbunătăţeşte substanţial, în timp ce precizia câmpurilor title,

heading şi inlink se îmbunătăţeşte mult mai puţin. De asemenea, precizia câmpului strong scade

dupa etapa de filtrare a spam-ului. Aceste variaţii indică faptul că primele patru câmpuri conţin mult

mai puţin spam, în timp ce câmpul body este mult mai predispus la spam, chiar dacă încorporează

aceste câmpuri.

Per ansamblu, modelul DRF3, care combină toate cele patru modele, are performanţe excelente

în ceea ce priveşte eficacitatea regăsirii ad-hoc. În final, se poate observa că utilizarea filtrului de

spam îmbunătăţeşte semnificativ precizia tuturor rezultatelor obţinute.

6.3.4 Concluzii

Abordarea propusă, bazată pe patru modele distincte (denumită DRF3), pentru regăsirea ad-hoc

optimizează direct metrica MAP pentru un set de interogări. Tehnica abordată este evaluate folosind

colecţia ClueWeb09 Category B. În exprerimentele prezentate, metoda propusă, bazată pe patru

modele, depăşeşte semnificativ metoda standatd Indri şi metoda RM3.

În ceea ce priveşte eficienţa rezultatele sunt încurajatoare, dat fiind faptul că rezultatele nu se

bazează pe alte resurse externe, cum ar fi colecţiile specifice sau rezultatele motoarelor de căutare

comerciale pentru expansiunea interogării. Acest lucru dovedeşte faptul că modelul de regăsire bazat

pe câmpuri este competitiv atunci când este folosit împreună cu modelul de dependenţă şi cel de

relevanţă, în ciuda faptului că este simplu, poate fi construit cu uşurinţă folosind limbajul de

modelare Indri şi implică determinarea unor parametrii. Dar, pentru a obţine această îmbunătăţire,

parametrii modelului trebuie determinaţi cu are atenţie.

Studierea modelării bazate pe câmpuri şi agregarea tehnicii cu modelul de dependenţă şi cel de

relevanţă contribuie la stabilirea caracterului general al utilizării lui. În plus, metodele care includ

tehnica bazată pe câmpuri obţin rezultate bune pentru interogările formate dintr-un singur termen, în

comparaţie cu modelele de dependenţă şi de relevanţă care permit documentelor nerelevante să urce

în clasament. Mai mult, filtrarea spam-ului şi-a dovedit utilitatea prin îmbunătăţirea precizie tuturor

rezultatelor, chiar dacă s-a dovedit că, colecţia ClueWeb09 Category B cuprinde documente de

calitate superioară (Clarke, et al., 2011).

Astfel, rezultatele experimentale au confirmat afirmaţia făcută de Armstrong : prin adăugarea

modelului bazat pe câmpuri şi a modelului de filtrare a spam-ului la modelele de dependenţă şi cel

de relevanţă, aditivitatea îmbunătăţirilor asupra preciziei se conservă şi eficienţa sistemului creşte în

mod corespunzător.

39

7. Concluzii

7.1 Concluzii generale

Dezvoltarea haotică şi necontrolată a Web-ului din ultima perioadă a provocat o revoluţie culturală şi

tehnologica fără precedent devenind cea mai mare sursă de informaţii accesibilă publicului din lume.

Tehnicile care au susţinut acest sistem de informare au întâmpinat provocări majore în deservirea

tuturor cerinţelor şi nevoilor tot mai diverse apărute din partea utilizatorilor.

Cercetările desfăşurate în cadrul acestei lucrări au urmărit îmbunătăţirea tehnicilor actuale de

Web mining prin modelarea şi structurarea conţinutului web, precum şi analiza, modelarea şi

optimizarea sistemelor de regăsire a informaţiei.

Modelarea şi structurarea conţinutului web au fost abordate printr-un nou model de reprezentare

a unui document web, respectiv a unui algoritm de clusterizare a documentelor web. Prin ponderarea

corespunzătoare a termenilor şi îmbinarea modelelor de reprezentare web bazate pe tag-uri HTML

cu cele bazate pe legăturile dintre paginile web s-a propus un nou model care îmbunătăţeşte

semnificativ regăsirea informaţiei relevante pentru utilizator. Totodată, acest noul model de

reprezentare a unei pagini web este fructificat de către un algoritm de clusterizare care constă în

două etape distincte. În secţiunea 6.3 s-au studiat în detaliu performanţele algoritmului de

clusterizare în doi paşi propus aplicat peste colecţii limitate de documente web, anume două site-uri.

Pentru a demonstra eficienţa abordării propuse au fost utilizate diferite formule de calcul a ponderii

termenilor, care au avut un impact major asupra noului model de reprezentare a unei pagini web.

Experimentele au fost efectuate pe două seturi de date cu o mare varietate de pagini web şi termeni.

Calitatea rezultatelor a fost probată prin măsurarea a patru parametrii distincţi folosiţi în regăsirea

informaţiei. Astfel, s-a demonstrat experimental faptul că, prin implementarea unor noi abordări in

modelarea documentelor web bazate pe exploararea caracteristicilor limbajului HTML, precum şi

aplicarea unui algoritm de clusterizare adaptat acestora, se obţin rezultate evident îmbunătăţite.

Algoritmul de clusterizare propus este intuitiv, dar ia în considerare doar parţial semantica dintre

documentele web.

Pentru a putea aborda problema căutării pe Web în mod eficient, s-a efectuat un studiu

comparativ cu scopul de a investiga relaţiile dintre principalele metrici de evaluare pentru regăsirea

informaţiei. În acest studiu s-a urmărit determinea metricilor care măsoară în mod corespunzător

nevoia de informaţie a utilizatorului. Pentru a analiza cele două directii din cadrul regăsirii

informaţiei pe Web, s-au considerat atât metrici care se folosesc pentru regăsirea ad-hoc cât şi

metrici care evaluează diversitatea rezultatelor returnate. Rezultatele obţinute sugerează cel puţin

două categorii de metrici: metrici cu o puternică tendinţă de a clasa documentele relevante cât mai

sus ( , , şi ) şi metrici care surprind un aspect mai

general al performanţei ( şi ). Metricile şi par să împartă

caracteristici aparţinând ambelor categorii. Deşi metrica este în general acceptată ca metrică de

bază în evaluare sistemelor de regăsire, aceasta nu reflectă neapărat în totalitate modului în care

utilizatorii efectuează o căutare. Acest lucru este îngrijorător deoarece rezultatele indică faptul că

40

corelaţiile dintre cele două categorii de metrici sunt slabe (coeficientul Kendall având valori mai

mici de 0,7).

Modelarea unui sistem de regăsire s-a făcut printr-o metodă originală (denumită DRF3), bazată

pe patru modele distincte de regăsire, cu scopul de a optimiza direct metrica MAP prin intermediul

unui set de interogări dat. Tehnica abordată este evaluată folosind colecţia ClueWeb09 Category B.

În experimentele prezentate, metoda propusă, depăşeşte semnificativ metodele de referinţă Indri şi

RM3. În ceea ce priveşte eficienţa, rezultatele sunt încurajatoare, dat fiind faptul că rezultatele nu se

bazează pe alte resurse externe, cum ar fi colecţiile specifice sau rezultatele motoarelor de căutare

comerciale pentru expansiunea interogării. Acest lucru dovedeşte faptul că modelul de regăsire bazat

pe câmpuri este competitiv atunci când este folosit împreună cu modelul de dependenţă şi cel de

relevanţă, în ciuda faptului că este simplu, poate fi construit cu uşurinţă folosind limbajul de

modelare Indri şi implică determinarea unor parametrii. Dar, pentru a obţine această îmbunătăţire,

parametrii modelului trebuie determinaţi cu are atenţie. Studierea modelării bazate pe câmpuri şi

agregarea tehnicii cu modelul de dependenţă, cel de relevanţă şi cel de filtrare a spamului contribuie

la stabilirea caracterului general al utilizării lui. În plus, metodele care includ tehnica bazată pe

câmpuri obţin rezultate bune pentru interogările formate dintr-un singur termen, în comparaţie cu

modelele de dependenţă şi de relevanţă care permit documentelor nerelevante să urce în clasament.

Mai mult, filtrarea spam-ului şi-a dovedit utilitatea prin îmbunătăţirea precizie tuturor rezultatelor,

chiar dacă s-a dovedit că, colecţia ClueWeb09 Category B cuprinde documente de calitate superioară

(Clarke, et al., 2011).

Astfel, rezultatele experimentale au confirmat afirmaţia făcută de Armstrong : prin adăugarea

modelului bazat pe câmpuri şi a modelului de filtrare a spam-ului la modelele de dependenţă şi cel

de relevanţă, aditivitatea îmbunătăţirilor asupra preciziei se conservă şi eficienţa sistemului creşte.

7.2 Contribuţii ştiinţifice şi valorificarea rezultatelor

Rezumând cele prezentate în secţiunea 7.1, contribuţiile ştiinţifice şi elementele de originalitate

aduse în cadrul acestei lucrări referă următoarele aspecte din cadrul Web mining:

1. Model de reprezentare a unui document web. Un document web are nevoie de prelucrări

preliminare în vederea obţinerii informaţiei relevante într-un format eficient şi util, astfel

încât să fie apoi procesat automat de către un sistem de analiză a informaţiilor. Modelul de

reprezentare propus îmbunătăţeşte semnificativ regăsirea informaţiei relevante pentru

utilizator prin utilizarea unui factor de normalizare a termenilor din cadrul unui document, o

nouă formulă de calcul a ponderii locale a termenului, care ţine cont de tag-urile HTML şi

luând în considerare legăturile dintre documentele web. Studiul aplicării tehnicilor de pre-

procesare este descris în secţiunea 5.1, iar modelul de reprezentare este detaliat în secţiunea

5.2. Evaluarea experimentală a rezultatelor este prezentată detaliat în secţiunea 6.3. Această

contribuţie a fost iniţial prezentată în (Agavriloaei, et al., 2011a).

2. Algoritm de clusterizare a conţinutului web. Datorită volumului tot mai mare de

documente aflate pe Web, se impune găsirea unor modalităţi eficiente de satisfacere a

41

nevoilor de informaţie a utilizatorilor. Pe baza modelului de document web propus, se

propune un algoritm de clusterizare pentru structurarea unei colecţii de documente web, cu

scopul de a pune în valoare informaţia utilă. Algoritmul aduce în prim plan documentele utile

pentru a satisface nevoia de informaţie a utilizatorul prin clusterizarea ponderilor termnilor

din cadrul colecţiei şi prin sortarea topologică a documentelor din fiecare cluster rezultat.

Formalizarea matematică a algoritmului este introdusă în secţiunea 5.4 şi are la bază

cercetările din (Agavriloaei, et al., 2011a), iar evaluarea detaliată a algoritmului este

prezentată în (Agavriloaei & Craus, 2011b).

3. Determinarea relaţiilor dintre diferite metrici de regăsire a informaţiei luând în

considerare cum reflectă acestea performanţa de căutare a utilizatorului. Regăsirea

informaţiei este puternic fundamentată pe investigarea empirică: pe baza poziţiei unei resurse

relevante din cadrul unei liste ordonate returnate, o varietate de metrici de performanţă a

sistemului pot fi calculate. Studiul comparativ al metricilor din cele două tendinţe de regăsire

actuale (ad-hoc şi diversificată) şi al rezultatelor lor sugerează faptul că există două categorii

distincte de metrici: metrici care se concentrează pe o precizie ridicată în cadrul listei

returnate de un sistem de regăsire şi metrici care au drept scop captarea unui aspect mai

general al performanţei sistemului, de obicei prin includerea reapelului. Analiza critică a

experimentelor prezentate la TREC 2011, precum şi a celor de referinţă sugerează faptul că

performanţa relativă a unui sistem poate diferi în mod semnificativ în funcţie de grupul de

metrici utilizat. Contextul şi metodologia studiului sunt prezentate în capitolul 5 şi sunt

folosite pentru a examina experimentele prezentate la TREC 2011 şi a genera un punct de

pornire pentru experimentele viitoare în cadrul secţiunii 6.2.

4. Model hibrid pentru modelarea unui sistem de regăsire ad-hoc a informaţiei. Unele

tehnici de regăsire – modelul dependenţei (DM) şi cel al relevanţei (RM) – au demonstrat că

pot aduce un anumit grad de performanţă. Celor două modele li se adaugă un model propus,

bazat pe câmpuri (FM) şi un model de filtrare a spam-ului (SFM), pentru a îmbunătăţi

performanţele unui sistem de regăsire ad-hoc. Modelul rezultat, denumit DRF3, are drept

scop obţinerea unei perspective noi asupra rolului pe care structura documentelor web şi

filtrarea spam-ului îl pot avea în creşterea eficienţei sistemelor actuale de regăsire a

informaţiei. Înglobarea modelului bazat pe câmuri (FM) într-un ansamblu de modele de

regăsire este originală şi funrnizează rezultate superioare când este folosit împreună cu

modelele consacrate, dovedind astfel competitivitatea sa. În acelaşi timp, se urmăreşte

confirmarea proprietăţii de aditivitate în sensul propus de (Armstrong, et al., 2009): prin

adăugarea modelului bazat pe câmpuri şi a modelului de filtrare a spam-ului la modelele de

dependenţă şi cel de relevanţă, aditivitatea îmbunătăţirilor asupra preciziei se conservă şi

eficienţa sistemului creşte. Consecinţa directă a acestei proprietăţi este creşterea satisfacţiei

utilizatorului. Modelul propus este prezentat în secţiunea 5.3, iar performanţele soluţiei

propuse sunt amplu dezbătute în secţiunea 6.4. Această contribuţie a fost iniţial prezentată în

(Agavriloaei, et al., 2012).

42

7.3 Direcţii viitoare

În perioada următoare, adoptarea şi utilizarea Web-ului va continua să crească fără încetare, în

primul rând datorită potenţialului comercial uriaş pe care îl are Web-ul. Creşterea şi utilizarea lui tot

mai intensă, va genera un volum tot mai mare de date, care, la rândul său, va pretinde tehnici tot mai

complexe şi rafinate de Web mining. Cercetările viitoare în domeniul Web mining ar trebui să

clarifice câteva din problemele curente, dar să trateze şi unele noi, generate de noile tehnologii care

participă la expansiunea fenomenului web în momentul de faţă. Viitorul procesului de Web mining

ar trebuie să fie unul de analiza predictivă, care încetează să prezică comportamentul utilizatorului

doar pe baza istoricului său.

În primul rând, deşi la ora actuală există o sumedenie de metrici pentru evaluarea fenomenului

web, trebuie întreprinse cercetări mai aprofundate în dezvoltarea unui set cât mai corect de metrici

web, precum şi dezvoltarea procedurilor de măsurare a acestora, astfel încât diferitele fenomene web

să poată fi studiate în amănunt.

În direcţia modelării şi organizării documentelor web, o analiză suplimentară a poziţiilor tag-

urilor HTML în cadrul documentului şi a legăturilor dintre paginile aflate în clustere diferite ar putea

aduce îmbunătăţiri suplimentare ale eficienţei algoritmului de clusterizare. Determinarea numărului

optim de clustere dintr-o colecţie restrânsă, cum este un site, este o altă problema care ar trebui

analizată mai în detaliu.

În direcţia modelării sistemelor de regăsire, se doreşte identificarea unei modalităţi de a

îmbunătăţi eficienţa sistemelor de regăsire prin efectuarea pasului de filtrare a spam-ului înaintea

procesului de regăsire şi chiar a procesului de indexare, ca un pas de pre-procesare. O altă problemă

care trebuie abordată este reducerea valorilor marginale din expansiunea interogării din cadrul

modelului de relevanţă. În acest scop este de dorit identificarea unei modalităţi de a folosi în mod

eficient scorul PageRank pentru a identifica termenii nesemnificativi, dar care au totuşi o pondere

mare în documentele returnate pentru procesul de selecţie.

Tehnicile de data mining pot fi aplicate asupra serviciilor web pentru a le face mai robuste,

scalabile şi eficiente; pentru a înţelege mai bine comportamentul lor, iar cunoştinţele extrage pot fi

folosite pentru diferite optimizări.

43

Bibliografie

1. Adamo, J.-M. (2000). Data Mining for Association Rules and Sequential Patterns. New

York: SpringerVerlag.

2. Agavriloaei, I., & Craus, M. (2010). An Analysis of Web Clustering. Proceedings of 6th

European Conference on Intelligent Systems and Technologies (ECIT 2010), 1-6.

3. Agavriloaei, I., & Craus, M. (2011b). Performance Evaluation of a Two-Step Clustering

Method. Buletinul Institutului Politehnic din Iaşi, ome LVII (LXI)(2), 31–43.

4. Agavriloaei, I., Alexandrescu, A., & Craus, M. (2011a). Improving web clustering through a

new modeling for web documents.

5. Agavriloaei, I., Rauber, A., & Craus, M. (2012). Combination of Dependence, Relevance

and Structure for Effective Web Retrieval. (G. Alam, Ed.) Journal of Applied Sciences,

12(19), 2035-2043.

6. Agrawal, R., Gollapudi, S., Halverson, A., & Ieong, S. (2009). Diversifying search results.

Proceedings of the Second ACM International Conference on Web Search and Data Mining

(pg. 5-14). Barcelona, Spain: ACM.

7. Armstrong, T. G., Moffat, A., Webber, W., & Zobel, J. (2009). Improvements that don't add

up: ad-hoc retrieval results since 1998. CIKM '09 Proceedings of the 18th ACM conference

on Information and knowledge management. New York: ACM.

8. Baeza-Yates, R., Saint-Jean, F., & Castillo, C. (2002). Web Structure, Dynamics and Page

Quality. Proceedings of the 9th International Symposium on String Processing and

Information Retrieval (pg. 117-130). Springer-Verlag.

9. Brin, S., & Page, L. (1998). The anatomy of a large-scale hypertextual Web search engine.

Computer Networks and ISDN Systems 30(1-7), pg. 107-117.

10. Chakrabarti, S., Puniyani, K., & Das, S. (2006). Optimizing scoring functions and indexes

for proximity search in type-annotated corpora. Proceedings of the 15th international

conference on World Wide Web (WWW '06). Edinburgh, Scotland: ACM.

11. Chapelle, O., Metlzer, D., Zhang, Y., & Grinspan, P. (2009). Expected reciprocal rank for

graded relevance. 18th ACM Conference on Information and Knowledge Management, (pg.

621–630).

12. Chisholm, E., & Kolda, T. G. (1999). New Term Weighting Formulas For The Vector Space

Method In Information Retrieval.

13. Cho, J., & Roy, S. (2004). Impact of search engines on page popularity. Proceedings of the

13th international conference on World Wide Web (WWW '04) (pg. 20-29). New York, USA:

ACM.

14. Clarke, C. L., Craswell, N., Soboroff, I., & Cormack, G. V. (2011). Overview of the TREC

2010 Web Track. Proceedings of the Nineteenth Text REtrieval Conference (TREC 2010).

NIST.

15. Clarke, C., Craswell, N., & Soboroff, I. (2004). Overview of the TREC 2004 Terabyte Track.

Proceedings of the Thirteenth Text Retrieval Conference (TREC 2004).

44

16. Cooley, R. (2003). The use of web structure and content to identify subjectively interesting

web usage patterns. ACM Trans. Internet Techn. 3(2), 93-116.

17. Cormack, G. V., Smucker, M. D., & Clarke, C. L. (2011). Efficient and effective spam

filtering and re-ranking for large web datasets. Information Retrieval, 14(5), 441-465.

18. Cutler, M., Deng, H., Maniccam, S., & Meng, W. (1999). A new study on using HTML

structures to improve retrieval. Proceedings of the 11th IEEE International Conference on

Tools with Artificial Intelligence (ICTAI’99) (pg. 406–409). Chicago,: IEEE Computer

Society.

19. Deerwester, S., Dumais, S., Furnas, G., Landauer, T., & Harshman, R. (1991). Indexing by

latent semantic analysis. Journal of the American Society for Information Science 41, 391–

407.

20. Diaz, F. (2009). Integration of news content into web results. Proceedings of the Second

ACM International Conference on Web Search and Data Mining (pg. 182-191). Barcelona,

Spain: ACM.

21. Fayyad, U., Piatetsky-Shapiro, G., Smyth, P., & Uthurusamy, R. (1996). Advances in

Knowledge Discovery and Data Mining. AAAI/MIT Press.

22. Fayyad, U., Reina, C., & Bradle, P. (1998). Initialization of Iterative Refinement Clustering

Algorithms. Knowledge Discovery and Data Mining, 194-198.

23. Fortunato, S., Flammini, A., Menczer, F., & Vespignani, A. (2006). Topical interests and the

mitigation of search engine bias. Proc. Natl. Acad. Sci. USA, 103(34), 12684-12689.

24. Geva, S., & Sahama, T. (2005). The NLP task at INEX 2004. SIGIR Forum 39(1), 50–53.

25. Grossman, D., & Frieder, O. (2004). Information Retrieval - algorithms and heuristics (ed.

2nd). The Information Retrieval Series. Springer.

26. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning: Data

Mining, Inference, and Prediction. (ed. 2nd). Springer-Verlag.

27. Hawking, D., Upstil, T., & Craswell, N. (2004). Toward better weighting of anchors.

Proceedingsof the 27th Annual International ACM SIGIR Conference on Research and

Development in Information Retrieval., (pg. 512–513).

28. Hou, J., & Zhang, Y. (2003). Utilizing hyperlink transitivity to improve web page clustering.

Proceeding ADC '03 Proceedings of the 14th Australasian database conference - Volume 17,

(pg. 49-57).

29. Ino, H., Kudo, M., & Nakamura, A. (2005). Partitioning of Web graphs by community

topology. Proceedings of the 14th international conference on World Wide Web (pg. 661-

669). Chiba, Japan: ACM.

30. Joachims, T. (1999). Making large-scale support vector machine learning practical. În

Advances in kernel methods (pg. 169-184). MIT Press.

31. Jones, K., Walker, S., & Robertson, S. (2000). A probabilistic model of information

retrieval: development and comparative experiments. Inf. Process. Manage., 36(6), 779-808.

45

32. Kamvar, S., Haveliwala, T., Manning, C., & Golub, G. (2003). Extrapolation methods for

accelerating PageRank computations. Proceedings of the 12th international conference on

World Wide Web (WWW '03). Budapest, Hungary: ACM.

33. Kleinberg, J. (1999). Authoritative sources in a hyperlinked environment. Journal of the

ACM46(5), 604-632.

34. Kobayashi, M., & Takeda, K. (2000). Information retrieval on the web. ACM Comput. Surv.

32, 2 (June 2000), pg. 144-173.

35. Koolen, M., & Kamps, J. (2010). The importance of anchor text for ad hoc search revisited.

Proceedings of the 33rd international ACM SIGIR conference on Research and development

in information retrieval, (pg. 122-129).

36. Krovetz, R. (1993). Viewing morphology as an inference process. SIGIR '93 Proceedings of

the 16th annual international ACM SIGIR conference on Research and development in

information retrieval, (pg. 191-202). New York.

37. Kumar, R., Raghavan, P., Rajagopalan, S., & Tomkins, A. (1999). Trawling the Web for

emerging cyber-communities. Proceedings of the eighth international conference on World

Wide Web (pg. 1481-1493). Toronto, Canada: Elsevier North-Holland, Inc.

38. Kummamuru, K., Lotlikar, R., Roy, S., Singal, K., & Krishnapuram, R. (2004). A

hierarchical monothetic document clustering algorithm for summarization and browsing

search results. Proceedings of the 13th international conference on World Wide Web (WWW

'04) (pg. 658-665). New York, USA: ACM.

39. Lancaster, F., & Fayen, E. (1973). Information Retrieval On-Line. Los Angeles, USA:

Melville Publishing Co.

40. Lavrenko, V., & Croft, W. B. (2001). Relevance based language models. SIGIR '01

Proceedings of the 24th annual international ACM SIGIR conference on Research and

development in information retrieval, (pg. 120-127).

41. Lempel, R., & Moran, S. (2000). The stochastic approach for link-structure analysis

(SALSA) and the TKC effect. Comput. Netw., 33(1-6), 387-401.

42. Li, X., Liu, B., & Yu, P. (2006). Discovering overlapping communities of named entities.

Proceedings of the 10th European conference on Principle and Practice of Knowledge

Discovery in Databases (pg. 593-600). Berlin, Germany: ACM.

43. Li, Y., & Chung, S. (2005). Text document clustering based on frequent word sequences.

Proceedings of the 14th ACM international conference on Information and knowledge

management (CIKM '05) (pg. 293-294). ACM.

44. Liu, B. (2011). Web Data Mining. Exploring Hyperlinks, Contents, and Usage Data (Second

Edition). New York: Springer.

45. Liu, Y., Gao, B., Liu, T.-Y., Zhang, Y., Ma, Z., He, S., și alții. (2008). BrowseRank: letting

web users vote for page importance. Proceedings of the 31st annual international ACM

SIGIR conference on Research and development in information retrieval (pg. 451-458).

Singapore, Singapore: ACM.

46

46. MacQueen, J. (1967). Some Methods for classification and Analysis of Multivariate

Observations. Proceedings of 5-th Berkeley Symposium on Mathematical Statistics and

Probability (pg. 281-297). Berkeley: University of California Press.

47. Markov, A., Last, M., & Kandel, A. (2008). The hybrid representation model for web

document classification. Int. J. Intell. Syst., 23(6), 654-679.

48. McSherry, F. (2005). A uniform approach to accelerated PageRank computation.

Proceedings of the 14th international conference on World Wide Web (WWW '05). Chiba,

Japan: ACM.

49. Metzler, D., & Croft, W. B. (2005). A Markov random field model for term dependencies.

SIGIR '05 Proceedings of the 28th annual international ACM SIGIR conference on Research

and development in information retrieval, (pg. 472-479).

50. Molinari, A., Pereira, R., & Pasi, G. (2003). An indexing model of HTML documents.

Proceedings of the 2003 ACM Symposium on Applied Computing (SAC) (pg. 834–840).

Melbourne: ACM.

51. Nguyen, D., & Callan, J. (2010). Combination of evidence for effective web search. The

Nineteenth Text REtrieval Conference (TREC 2010). Gaithersburg, USA.

52. Nie, Z., Zhang, Y., Wen, J.-R., & Ma, W.-Y. (2005). Object-level ranking: bringing order to

Web objects. Proceedings of the 14th international conference on World Wide Web. Chiba,

Japan: ACM.

53. Ordonez, C., & Omiecinski, E. (2004). Efficient Disk-Based K-Means Clustering for

Relational Databases. IEEE Trans. on Knowl. and Data Eng., 16(8), 909-921.

54. Pazzani, M., & Billsus, D. (1997). Learning and revising user profiles: The identification of

interesting. Machine Learning 27, 313–331.

55. Pennock, D., Flake, G., Lawrence, S., Glover, E., & Giles, C. (2002). Winners don't take all:

Characterizing the competition for links on the web. Proc. Natl. Acad. Sci. USA, 5207-5211.

56. Pereira, R., Molinari, A., & Pasi, G. (2005). Contextual weighted representations and

indexing ieee computer society models for the retrieval of HTML documents. Soft

Computing 9(7), 481–492.

57. Ponte, J., & Croft, W. (1998). A language modeling approach to information retrieval.

Proceedings of ACM SIGIR Conf. on Research and Development in Information Retrieval

(SIGIR-1998).

58. Robertson, S., Walker, S., & Hancock-Beaulieu, M. (2000). Experimentation as a way of life

Okapi at TREC. Information Processing and Management 36(1), pg. 95-108.

59. Robertson, S., Zaragoza, H., & Taylor, M. (2004). Simple BM25 extension to multiple

weighted fields. Proceedings of the thirteenth ACM international conference on Information

and knowledge management (pg. 42-49). Washington, USA: ACM.

60. Salton, G. (1971). The Smart Retrieval System. Experiments in Automatic Document

Processing. Prentice Hall, Englewood Cliffs.

61. Salton, G., & McGill, M. (1983). An Introduction to modern information retrieval. Mc-Graw

Hill.

47

62. Smucker, M., Allan, J., & Carterette, B. (2007). A comparison of statistical significance tests

for information retrieval evaluation. Proceedings of the Sixteenth ACM Conference on In-

formation and Knowledge Management (CIKM 2007) (pg. 623-632). Lisboa, Portugal:

ACM.

63. Smucker, M., Clarke, C., & Cormack, G. (2009). Experiments with ClueWeb09: Relevance

Feedback and Web Tracks. Proceedings of the Eighteenth Text REtrieval Conference (TREC

2009).

64. Steinbach, M., Karypis, G., & Kumar, V. (2000). A comparison of document clustering

techniques. Proceedings of KDD Workshop on Text Mining.

65. Tomlin, J. (2003). A new paradigm for ranking pages on the world wide web. Proceedings of

the 12th international conference on World Wide Web (pg. 350-355). Budapest, Hungary:

ACM.

66. Turtle, H., & Croft, W. (1991). Evaluation of an inference network-based retrieval model.

Trans. Inf. Syst., 9, 187-222.

67. Vapnik, V. (1995). The nature of statistical learning theory. Springer-Verlag New York, Inc.

68. Wang, J. (2009). Encyclopedia of data warehousing and mining, Second Edition. New York:

IGI Global.

69. Witten, I. H., Frank, E., & Hall, M. A. (2011). Data Mining: Practical Machine Learning

Tools and Techniques (Third Edition). Morgan Kaufmann.

70. Yang, C., Chen, H., & Hong, K. (2003). Visualization of large category map for Internet

browsing. Decision Support Systems 35(1), 89–102.

71. Zeng, H.-J., He, Q.-C., Chen, Z., Ma, W.-Y., & Ma, J. (2004). Learning to cluster web

search results. Proceedings of the 27th annual international ACM SIGIR conference on

Research and development in information retrieval (SIGIR '04) (pg. 210-217). Sheffield,

United Kingdom: ACM.

72. Zhai, C., & Lafferty, J. (2001). A study of smoothing methods for language models applied

to ad hoc information retrieval. Proceedings of the 24th annual international ACM SIGIR

conference on Research and development in information retrieval, (pg. 334-342). New

Orleans, Louisiana, United States.

73. Zhai, C., & Lafferty, J. (2004). A study of smoothing methods for language models applied

to information retrieval. ACM Transactions on Information Systems (TOIS), (pg. 179-214).

74. Zhao, Y., Karypis, G., & Fayyad, U. (2005). Hierarchical Clustering Algorithms for

Document Datasets. Data Min. Knowl. Discov., 10(2), 141-168.