Curs nr. 11 - Web Mining Tehnici Graph Mining.pdf

Notiuni recapitulative Descrierea problemei Notiuni fundamentale Algoritmi si metode de analiza a grafurilor Discutii Bibliografie

Regasirea Informatiilor pe WEBCurs 11: Web Mining Tehnici Graph Mining

s.l. dr. ing. Alexandru [email protected]

Facultatea de Automatica si Calculatoare, Iasi

an universitar: 2014 2015

RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 1/ 24


Cuprins

1 Notiuni recapitulative

2 Descrierea problemei

3 Notiuni fundamentaleDefinitii

4 Algoritmi si metode de analiza a grafurilorBackward link countForward link countAlgoritmul PageRankAlgoritmul HITS

5 Discutii



Recapitulare grafuri

Completati definitiile

1 Un graf reprezinta ... . Pentru un graf, se defineste gradul unui nod ca fiind... .

2 Un digraf reprezinta ... . Pentru un digraf, se defineste gradul interior alunui nod ca fiind ... si gradul exterior al unui nod ca fiind ... .

3 Un graf bipartit reprezinta ... .

4 Doua grafuri sunt izomorfe daca ... .



Ce se poate rezolva utilizand tehnici de graph mining?

Scenariul interactiunii cu utilizatorul

Utilizatorul introduce un set de cuvinte cheie.

Pe baza acestor cuvinte cheie se aplica o metoda de cautare pentru a obtineun set de rezultate.

Rezultatele pasului anterior, sortate n ordinea relevantei, sunt prezentateutilizatorului.

Intrebarea pentru care dorim sa aflam raspunsul

CUM DETERMIN RELEVANTA DOCUMENTELOR STOCATE RELATIV LAUN SET DE CUVINTE CHEIE?



Definitii

Definitii

Graph Mining

Analiza structurala (sau analiza datelor de structura eng: structure miningsau structured data mining) reprezinta acea metoda de analiza a datelor ce seaxeaza pe modul de organizare a seturilor de date. Graph Mining (analizagrafurilor) reprezinta un caz particular de analiza structurala.

Tipuri de analiza a grafurilor [6]

axate pe obiecte (varfuri) axate pe legaturi (muchii)ierarhizarea obiectelor predictia existentei unor link-uriclasificarea obiectelor predictia tipului de link

clusterizarea obiectelor predictia numarului de link-uriidentificarea unui anumit obiect

axate pe grafuri n ansambluidentificarea subgrafurilor frecvente

clasificarea grafurilor



Definitii

Exemple Graph Mining

Ierarhizarea obiectelor [6]

1 Dat fiind un set de pagini/documente WEB ce satisfac un anumit criteriu decautare, care este ordinea acestora din punct de vedere al conectivitatii ncadrul WWW?

2 Dat fiind un grup de autori/co-autori si o lista de lucrari, care sunt grupurilede lucru si/sau ariile de interes?

3 Data fiind o retea sociala, care este cel mai popular membru al retelei?



Definitii

Definitii (2)

Site director

Site-ul director (hub) reprezinta acel tip de site/pagina web ce furnizeaza unnumar foarte mare de legaturi catre pagini considerate relevante din punct devedere al informatiei.

Site autoritate

Site-ul autoritate reprezinta acel tip de site/pagina web ce contine informatiirelevante pentru domeniul pentru care a fost dezvoltat.



Backward link count

Backward link count

Principiul metodei

Intuitiv, o pagina referita de un numar mare de pagini este considerata a fimai relevanta decat una referita de un numar mai mic de link-uri (n acelasicontext).

Metoda se bazeaza practic pe principiul citarii.

Metrica metodei

Pentru o pagina oarecare P, scorul este dat de numarul paginilor care o refera(WEB-ul mapat ca digraf : gradul interior al nodului P).

Dezavantaj

Nu se poate cunoaste topologia exacta a WEB-ului.



Forward link count

Forward link count

Principiul metodei

O pagina ce refera un numar mare de pagini WEB este considerata o paginavaloroasa.

Exemple de astfel de pagini/documente WEB: directoarele WEB.

Metrica metodei

Pentru o pagina oarecare P, scorul este dat de numarul paginilor referite de P(WEB-ul mapat ca digraf : gradul exterior al nodului P).

Poate fi utila pentru...

... identificarea, n conjunctie cu alti factori, a paginilor de tip index de resurseWEB.



Algoritmul PageRank

Algoritmul PageRank

Generalitati

Familie de algoritmi orientati pe asignarea de valori numerice ponderatepentru paginile WEB n vederea obtinerii unor informatii de tip relevanta.

Algoritmii au fost dezvoltati de Larry Page si Sergey Brin 1998.

Corelati cu alte metrici, sunt la baza motorului de cautare Google ndeterminarea relevantei/importantei unei pagini.

PageRank marca nregistrata a Google.

Procesul PageRank patent atribuit Universitatii Stanford



Algoritmul PageRank

Algoritmul PageRank (2)

Principiul algoritmilor

Sistem de votare : Daca pagina A indica pagina B, atunci pagina B a primit unvot de ncredere din partea paginii A.

O pagina pentru care nu exista voturi nu poate fi consideratarelevanta.

Algoritmi recursivi : PageRank-ul unei pagini depinde de numarul si de metricaPageRank a paginilor care o refera.

Motorul de cautare Google

Este orientat pe ponderarea voturilor.

Se bazeaza pe faptul ca voturile primite din partea unor pagini cu un gradridicat de ncredere sunt mai valoroase.

2005 implementeaza un nou atribut pentru elementul HTML link:

rel=nofollow (elementul anchor).



Algoritmul PageRank


Scenariu 1

Avem o subpartitie din WEB formata din4 documente WEB primul documenteste referit de toate celelalte.

Formula de calcul

PR(A) = PR(B) + PR(C ) + PR(D) (1) Figura 1: Subpartitie graf WEB(modelul simplist)



Algoritmul PageRank


Scenariu 2

Avem o subpartitie din WEB formata din4 documente WEB legaturile dintrepagini sunt date de Figura 2.

Formula de calcul

Ecuatia (1) devine:

PR(A) =PR(B)

2+PR(C )+

PR(D)

3(2) Figura 2: Subpartitie graf WEB

(modelul extins)



Algoritmul PageRank


Formula de calcul cazul simplist

In cazul general, ecuatia (2) devine:

PR(A) =PA

PR(P)

LC (P), (3)

unde: LC (P) indica numarul de legaturi ce pleaca din pagina P (gradul exterior alnodului P).

Considerente suplimentare

Un vot indirect are un coeficient de ncredere mai scazut decat un votdirect, deci voturile sunt transferate dupa un anumit coeficient d numitfactor de amortizare.

Nivelul initial de ncredere este acelasi pentru toate paginile: 1d .



Algoritmul PageRank


Formula de calcul cazul simplist (2)

Ecuatia (3) devine:

PR(A) = (1 d) + d PA

PR(P)

LC (P)(4)

Observatii:

Parametrul PageRank (PR) este un parametru dinamic.

In conditiile n care toate paginile analizate primesc initial o aceeasi valoare aPR, daca PR se recalculeaza permanent pentru toate paginile indexate,atunci valorile PR vor tinde spre stabilizare.



Algoritmul PageRank


Formula de calcul cazul complex

Presupune navigarea paginilor WEB prin salturi.

Dupa ce a fost atins un anumit numar de link-uri (pornind de la o paginainitiala), se va alege spre vizitare o alta pagina selectata aleator (modelulrandom surfer).Valoarea PageRank (PR) ar reprezinta n acest caz numarul de accesari alpaginii respective ntr-un eventual browser WEB.

Tranzitiile ntre legaturile prezente n aceeasi pagina sunt n mod egalprobabile.

Tranzitiile aleatoare pentru toate nodurile WEB au aceeasi probabilitate:q = (1 d) = 0.15.



Algoritmul PageRank


Formula de calcul cazul complex (2)

In aceste conditii, ecuatia (4) se rescrie ca:

PR(A) =q

N+ (1 q)

PA

PR(P)

LC (P), (5)

unde

N reprezinta numarul total de pagini din multimea de lucru.



Algoritmul PageRank



Considerand ecuatia (5), pentru o multime de N pagini valorile PageRank se vordetermina utilizand:

R =

qNqN

...qN

+ (1 q)

l(p1, p1) l(p1, p2) ... l(p1, pN)

l(p2, p1) l(p2, p2) ... l(p2, pN)

... ... ... ...

l(pN , p1) l(pN , p2) ... l(pN , pN)

R (6)



Algoritmul PageRank



In ecuatia (6) s-au utilizat urmatoarele notatii:

R reprezinta vectorul PageRank al multimii de pagini de lucru:

R =

PR(p1)

PR(p2)

...PR(pN)

l(pi , pj) reprezinta functia de adiacenta:

l(pi , pj) =

{0, daca pagina pj nu indica pagina piN

i=1 l(pi , pj) = 1



Algoritmul HITS

Algoritmul HITS

Generalitati

Algoritmul a fost dezvoltat de Kleinberg, n 1998.

Denumirea completa: Hypertext Induced Topic Search

SCOP: determinarea site-urilor autoritate si a celor de tip director pe unanumit subdomeniu, prin analiza unei subpartitii a WEB-ului.

Principiul algoritmului

Site-urile director (hub-uri) indica mai multe autoritati.

Autoritatile sunt referite de mai multe site-uri director.



Algoritmul HITS

Algoritmul HITS (2)

Scopul algoritmului

Algoritmul analizeaza structura subgrafului S determinat de o anumitainterogare pentru a identifica site-urile director si pe cele autoritate inclusen S .

Subgraful S se construieste astfel:

fie R multimea de pagini rezultat pentru o anumita interogare;initial: S R;se adauga la S toate paginile indicate de pagini incluse n R;se adauga la S toate paginile care indica pagini incluse n R.



Algoritmul HITS

Algoritmul HITS (3)

Algoritmul iterativ

Pentru fiecare pagina p din S, se mentin 2 valori:

Scorul autoritate: ap (n cadrul unui vector a, locatia p).Scorul hub: hp (n cadrul unui vector h, locatia p).

Initial: ap = hp = 1

Actualizarea vectorilor a si h se realizeaza conform ecuatiilor de mai jos:

ap =q:qp

hq (7)

hp =q:pq

aq (8)

Vectorii sunt memorati n forma normalizata.



Discutii

Problema

Fara a calcula efectiv, care sunt, conform ecuatiei (4), valorile PageRank pentru 2pagini ce se indica una pe alta?



Bibliografie

1 M. Craus et al., Regasirea Informatiilor pe WEB, Editura POLITEHNIUM,Iasi 2005, capitolul 4

2 Two Crows Corporation. Introduction to Data Mining and KnowledgeDiscovery, third edition, 2005

3 Usama Fayyad, Gregory Piatetsky-shapiro & Padhraic Smyth. From DataMining to Knowledge Discovery in Databases. AI Magazine, vol. 17, pages37 54, 1996.

4 Christopher D. Manning, Prabhakar Raghavan and Hinrich Schutze,Introduction to Information Retrieval, Cambridge University Press. 2008

5 Raymond J. Mooney Information Retrieval and Web Search (note de curs)

6 Robert Sanderson, Data Mining [note de curs Graph Mining, Web Mining],Dept. of Computer Science, University of Liverpool, 2008

7 Wikipedia: Graph Mining


Notiuni recapitulativeDescrierea problemeiNotiuni fundamentaleDefinitii

Algoritmi si metode de analiza a grafurilorBackward link countForward link countAlgoritmul PageRankAlgoritmul HITS

Discutii

Curs nr. 11 - Web Mining Tehnici Graph Mining.pdf

Documents

Transcript of Curs nr. 11 - Web Mining Tehnici Graph Mining.pdf