Post on 16-Sep-2015
transcript
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 ARCHIPalexandru.archip@cs.tuiasi.ro
Facultatea de Automatica si Calculatoare, Iasi
an universitar: 2014 2015
RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 1/ 24
Notiuni recapitulative Descrierea problemei Notiuni fundamentale Algoritmi si metode de analiza a grafurilor Discutii Bibliografie
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
RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 2/ 24
Notiuni recapitulative Descrierea problemei Notiuni fundamentale Algoritmi si metode de analiza a grafurilor Discutii Bibliografie
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 ... .
RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 3/ 24
Notiuni recapitulative Descrierea problemei Notiuni fundamentale Algoritmi si metode de analiza a grafurilor Discutii Bibliografie
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?
RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 4/ 24
Notiuni recapitulative Descrierea problemei Notiuni fundamentale Algoritmi si metode de analiza a grafurilor Discutii Bibliografie
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
RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 5/ 24
Notiuni recapitulative Descrierea problemei Notiuni fundamentale Algoritmi si metode de analiza a grafurilor Discutii Bibliografie
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?
RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 6/ 24
Notiuni recapitulative Descrierea problemei Notiuni fundamentale Algoritmi si metode de analiza a grafurilor Discutii Bibliografie
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.
RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 7/ 24
Notiuni recapitulative Descrierea problemei Notiuni fundamentale Algoritmi si metode de analiza a grafurilor Discutii Bibliografie
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.
RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 8/ 24
Notiuni recapitulative Descrierea problemei Notiuni fundamentale Algoritmi si metode de analiza a grafurilor Discutii Bibliografie
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.
RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 9/ 24
Notiuni recapitulative Descrierea problemei Notiuni fundamentale Algoritmi si metode de analiza a grafurilor Discutii Bibliografie
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
RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 10/ 24
Notiuni recapitulative Descrierea problemei Notiuni fundamentale Algoritmi si metode de analiza a grafurilor Discutii Bibliografie
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).
RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 11/ 24
Notiuni recapitulative Descrierea problemei Notiuni fundamentale Algoritmi si metode de analiza a grafurilor Discutii Bibliografie
Algoritmul PageRank
Algoritmul PageRank (3)
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)
RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 12/ 24
Notiuni recapitulative Descrierea problemei Notiuni fundamentale Algoritmi si metode de analiza a grafurilor Discutii Bibliografie
Algoritmul PageRank
Algoritmul PageRank (4)
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)
RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 13/ 24
Notiuni recapitulative Descrierea problemei Notiuni fundamentale Algoritmi si metode de analiza a grafurilor Discutii Bibliografie
Algoritmul PageRank
Algoritmul PageRank (5)
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 .
RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 14/ 24
Notiuni recapitulative Descrierea problemei Notiuni fundamentale Algoritmi si metode de analiza a grafurilor Discutii Bibliografie
Algoritmul PageRank
Algoritmul PageRank (6)
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.
RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 15/ 24
Notiuni recapitulative Descrierea problemei Notiuni fundamentale Algoritmi si metode de analiza a grafurilor Discutii Bibliografie
Algoritmul PageRank
Algoritmul PageRank (7)
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.
RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 16/ 24
Notiuni recapitulative Descrierea problemei Notiuni fundamentale Algoritmi si metode de analiza a grafurilor Discutii Bibliografie
Algoritmul PageRank
Algoritmul PageRank (8)
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.
RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 17/ 24
Notiuni recapitulative Descrierea problemei Notiuni fundamentale Algoritmi si metode de analiza a grafurilor Discutii Bibliografie
Algoritmul PageRank
Algoritmul PageRank (9)
Formula de calcul cazul complex (4)
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)
RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 18/ 24
Notiuni recapitulative Descrierea problemei Notiuni fundamentale Algoritmi si metode de analiza a grafurilor Discutii Bibliografie
Algoritmul PageRank
Algoritmul PageRank (10)
Formula de calcul cazul complex (5)
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
RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 19/ 24
Notiuni recapitulative Descrierea problemei Notiuni fundamentale Algoritmi si metode de analiza a grafurilor Discutii Bibliografie
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.
RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 20/ 24
Notiuni recapitulative Descrierea problemei Notiuni fundamentale Algoritmi si metode de analiza a grafurilor Discutii Bibliografie
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.
RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 21/ 24
Notiuni recapitulative Descrierea problemei Notiuni fundamentale Algoritmi si metode de analiza a grafurilor Discutii Bibliografie
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.
RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 22/ 24
Notiuni recapitulative Descrierea problemei Notiuni fundamentale Algoritmi si metode de analiza a grafurilor Discutii Bibliografie
Discutii
Problema
Fara a calcula efectiv, care sunt, conform ecuatiei (4), valorile PageRank pentru 2pagini ce se indica una pe alta?
RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 23/ 24
Notiuni recapitulative Descrierea problemei Notiuni fundamentale Algoritmi si metode de analiza a grafurilor Discutii Bibliografie
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
RIWeb 2014 2015/C11: Web Mining: Tehnici Graph Mining 24/ 24
Notiuni recapitulativeDescrierea problemeiNotiuni fundamentaleDefinitii
Algoritmi si metode de analiza a grafurilorBackward link countForward link countAlgoritmul PageRankAlgoritmul HITS
Discutii