Tema SUPLIMENTARA - Metode Numerice spatele unui... Motor de cautare InTermen de predare: Monday, 7th May, 2012, 23.55 Responsabili tema: Florin Pop (florin.pop@cs.pub.ro) George Popescu (pgpopescu@gmail.com) March 27, 2012

1

Descriere generala

PageRank este un algoritm de analiz a hiperlegturilor din Internet, folosit de a a motorul de cutare Google pentru a acorda o pondere ecrui element dintr-o a a multime de documente interconectate prin hiperlegturi, cu scopul msurrii a a a importantei relative cadrul multimii. Fie un set de N resurse (pagini web). n Fiecare pagin din acest set poate contine link-uri spre alte pagini. Spre unele a pagini vor ndreptate mai multe link-uri dect spre altele. Cu alte cuvinte, un a utilizator (care navigheaz pe Internet, accesnd diverse pagini ampltor) va a a nt a accesa cu o probabilitate mai mare unele resurse, iar alte resurse vor accesate cu o probabilitate mai mic. a Putem spune c paginile care vor vizitate cu o probabilitate mai mare a sunt mai importante dect celelalte (contin informatii mai multe, sunt lucrri a a tiintice mai citate dect altele etc). s a Un motor de cutare va trebui s redirecteze prim-plan paginile cele a a n mai importante (astfel at dac un utilizator caut un ac (anumite informatii, nc a a functie de cuvintele-cheie tastate de acesta) carul cu fn (multimea tuturor n n a paginilor web), atunci aceast sarcin s nu e proverbial de imposibil. Astfel, a a a a un motor de cutare are nevoie de un mod de a msura importanta unei resurse a a din cadrul unui set, i de un algoritm de calcul a acestei importante. Un algoritm s care calculeaz acest factor este PageRank, iar unitatea de msur folosit este a a a a indicele PageRank. Vom nota P R(R) indicele PageRank al resursei R. Pentru a elege cum functioneaz acest algoritm, s ne imaginm c vrem nt a a a a s calculm ct de important este pagina A, de exemplu. S notm cu M (A) a a a a a a multimea tuturor paginilor din care se poate ajunge la pagina A printr-un singur clic. Fie B M (A). Evident, cu ct probabilitatea ca un utilizator s ajung a a a la pagina B este mai mare, cu att probabilitatea de a ajunge la A este mai a mare. De asemenea, cu ct numrul de link-uri detinut de pagina B este mai a a

1

mare (vom nota cu L(B) acest numr) este mai mare, cu att probabilitatea ca a a urmtoarea pagin vizitat s e A este mai mic. Dac lum considerare i a a a a a a a n s celelalte pagini din M (A), precum i probabilitatea ca un utilizator s continue s a navigatul pe Internet (aceast probabilitate este dat de un coecent d), atunci a a formula de a calcula P R(A) (considernd c se tie P R(B), B M (A)) este: a a s P R(A) = 1d +d N P R(B) L(B)

BM (A)

La adresa web [1] (la sectiunea Computation) veti gsi pseudocodul pentru a diferiti algoritmi de a determina coecentii P R. O metoda important folosit in algoritmul de PageRank este bazat pe a a a functiile membru din logica fuzzy. Logica fuzzy ([3]) este o logic care extinde a logica clasic, boolean. Astfel, dac logica boolean o propozitie ia valori a a a n a dintr-o multime a crei cardinal este 2, logica fuzzy valoarea de adevr a unei a n a propozitii [0, 1]. Aceaste valori sunt date de aa-zise functii membru ([5]). s

22.1

Cerintele temei de casaCerinta 1. Algoritmul Iterative (40p)

S presupunem existenta unui program care primete ca date de intrare o a s colectie de N resurse web i determin un graf, reprezentat printr-o list de s a a adiacent. Acest graf va aat a s ntr-un ier, astfel: pe prima linie va dat s numrul N , iar pe urmtoarele linii vor date listele de vecini: o linie va a a ncepe cu numrul nodului (e i acest parametru) pentru care se dau vecinii, a va urma numrul de noduri cu care se a nvecineaz nodul i, iar urmtoarele nua a mere reprezint nodurile cu care se a nvecineaz i. Pe ultimele 2 linii sunt date a valorile val1 i val2 (cte una pe linie; le veti folosi pentru a rezolva cerintele s a urmtoare alte temei). Pentru a rezolva cerintele temei, va trebui s construiti a a matricea de adiacent a acestui graf (notat cu A: A(i, j) = 0, dac nodul i nu a a a se nvecineaz cu nodul j, i 1 altfel). a s S se implementeze algoritmul Iterative descris la adresa [1]. Observatii: a 1. Orice pagin web analizat contine cel putin un link spre o alt pagin web. a a a a Asta nseamn c matricea K (din algoritmul Iterative) este inversabil. a a a 2. Sunt unele pagini mai lungi care au link-uri spre ele nsele (pentru a permite o navigare mai uoar), deci nu toate elementele de pe diagonala s a principal a matricii A sunt 0. analiza efectuat, aceste link-uri nu au a In a nicio semnicatie, deci acestea nu vor intra calcul. Deci A(i, i) = 0, n i {1, 2, . . . , N }. 3. Algoritmul va implementat ierul Iterative.m; functia Iterative n s va primi ca argumente, aceast ordine: numele ierului din care va citi n a s graful, parametrul d (vezi descrierea lui mai sus), parametrul eps (eroarea care apare calculul vectorului P R). Va avea ca dat de ieire vectorul n a s P R. 4. Toate ierele de intrare vor contine pe prima linie numrul N , apoi pe s a urmtoarele N linii matricea de adiacent. a a 2

2.2

Cerinta 2. Algoritmul Algebraic (40p)

S se implementeze algoritmul Algebraic de la adresa [1]. Algoritmul se va a implementa ierul Algebraic.m; functia Algebraic va primi ca argumente, n s aceast ordine: numele ierului de intare (care are structura ierului de n a s s intrare de la Cerinta 1), parametrul d (care are aceeai interpretare ca la Cerintta s 1). Va avea ca dat de ieire vectorul P R. a s Observatie. Pentru a calcula inversa unei matrici, se va folosi algoritmul Gram-Schmidt: e T o matrice (cu n linii i n coloane) inversabil pentru care s a se cere s se determine T 1 . Avem: T = [t1 t2 . . . tn ], iar T 1 = [x1 x2 . . . xn ] i a s T T 1 = In . Deci, T [x1 x2 . . . xn ] = [e1 e2 . . . en ] T xi = ei () unde ei este coloana i din matricea unitate In . Pentru a aa T 1 se va rezolva sistemul () pentru ecare i parte, folosind n algoritmul Gram-Schmidt optimizat. Indicatie. Puteti aplica algoritmul Gram-Schmidt o singur dat, pentru a a a aa Q i R astfel at T = Q R; pe baza matricilor Q i R veti rezolva apoi s nc s cele n sisteme de ecuatii.

2.3

Cerinta 3. Gradul de Apartenenta (20p)x [0, val1 ); x [val1 , val2 ]; x (val2 , 1]

Fie urmtoarea functie membru: a 0, a x + b, u(x) = 1,

unde val1 i val2 sunt date ierul de intrare, aa cum este descris la Cerinta s n s s 1; a i b sunt valori calculate de voi astfel at u(x) s e o functie continu. s nc a a Aceast functie indic gradul de apartenent al paginii a crui PageRank este a a a a x la multimea paginilor importante. S se scrie ierul PageRank.m; functia PageRank primete ca date de ina s s trare, aceast ordine, un nume de ier, parametrul d, parametrul eps. Toti n a s aceti parametrii au interpretarea de mai sus. PageRank.m va scrie un nou s ier, a crui nume este dat de numele ierului primit ca parametru, la care s a s se concateneaz irul .out. Va scrie noul ier, pe prima linie, numrul N as n s a (numrul de pagini web analizate), va calcula vectorul P R folosind primul algoa ritm i-l va scrie ierul .out pe N linii, apoi va calcula vectorul P R folosind s n s al doilea algoritm i-l va scrie ierul .out; se va lsa un rnd gol s n s a a ntre N i s primul vector, i un rnd gol s a ntre cei doi vectori. Dup acest pas, se va ordona a descresctor vectorul P R calculat de cel de-al doilea algoritm (folosind orice a algoritm de sortare, se va nota P R1 acest vector sortat). Se va lsa ierul a n s de ieire un spatiu liber, apoi se vor aa N linii de forma: s s i j F unde i reprezint indici vectorul P R1 (se vor aa ordinea: 1, 2, 3, . . . , N ), a n s n j reprezint nodul a crui PageRank este P R1 (i), iar F = u(P R1 (i)). Practic, a a 3

se va face un clasament al celor mai importante pagini, clasament care interen seaz locul obtinut (adic numrul i), numrul paginii care a obtinut acest loc, a a a a i gradul de apartenent a acestei pagini la multimea paginilor importante. s a

33.1

Exemple de date de intrare si de rezultateExemplu 1

d = 0.85, eps = 0.001; Continutul ierului graf1 este: s 7 1 3 2 2 3 3 3 5 1 4 5 1 5 3 4 6 3 1 7 4 1 0.001 0.95 3 4 2 2 6 4 2 4 5 5 6 7 3 6 7 7 5 3 5

Functia PageRank.m va scrie ierul graf1.out: s 7 0.137730 0.142355 0.156163 0.176215 0.147967 0.119785 0.119785 0.137419 0.142396 0.156189 0.176532 0.147754 0.119855 0.119855 1 2 3 4 5 6 7 4 3 5 2 1 7 6 0.184965 0.163529 0.154641 0.148994 0.143750 0.125242 0.125242

3.2

Exemplu 2

d = 0.85, eps = 0.001; Fiierul graf2 contine: s 4

8 1 2 2 2 5 1 3 4 1 4 5 1 5 6 1 6 3 5 7 5 1 8 3 1 0.08 0.85

3 2 2 2 2 7 2 2

4 7 3 3 8 3 3

5 8 8 5 6 4 7 8 7 8

Functia PageRank.m va scrie ierul graf2.out: s 8 0.185532 0.218111 0.179646 0.077618 0.087414 0.031813 0.078387 0.141480 0.185572 0.218095 0.179872 0.077464 0.087308 0.031919 0.078385 0.141387 1 2 3 4 5 6 7 8 2 1 3 8 5 7 4 6 0.179344 0.137106 0.129704 0.079723 0.009490 0.000000 0.000000 0.000000

4

Detalii de implementare si redactare

Tema de cas va implementa functiile mentionate la ecare cerint parte, a a n astfel: function R = Iterative(nume, d, eps) % Functia care calculeaza matricea R folosind alg. iterativ. % Intrari: 5

% % % % % % %

-> nume: numele fisierului din care se citeste; -> d: coeficentul d, adica probabilitatea ca un anumit navigator sa continue navigarea (0.85 in cele mai multe cazuri) -> eps: eruarea care apare in algoritm. Iesiri: -> R: vectorul de PageRank-uri acordat pentru fiecare pagina.

function R = Algebraic(nume, d) % Functia care calculeaza vectorul PageRank folosind varianta % algebrica de calcul. % Intrari: % -> nume: numele fisierului in care se scrie; % -> d: probabilitatea ca un anumit utilizator sa continue % navigarea la o pagina urmatoare. % Iesiri: % -> R: vectorul de PageRank-uri acordat pentru fiecare pagina. function [R1 R2] = PageRank(nume, d, eps) % Calculeaza indicii PageRank pentru cele 3 cerinte % Scrie fisierul de iesire nume.out Pentru implementarea temei puteti folosi si alte functii denite de voi, dar cele mentionate mai sus sunt obligatorii. Pentru redactarea temei de cas trebuie s ineti cont de urmtoarele asa a t a pecte: codul surs va contine comentarii semnicative i sugestive cu privire la a s implementarea algoritmilor. existenta unui ier readme.txt care va prezenta detaliile legate de im s plementarea i testarea temei. i ierele care compun tema de casa vor incluse s ntr-o arhiv .zip care a respect specicatiile din regulamentul cursului. a tema se va implementa in Maltab i va testat mediul Octave. s a n pentru aceast tem termenul de predare este x i NU este posibil exa a s a tinderea lui.

5

Resurse Web1. http://en.wikipedia.org/wiki/PageRank 2. http://www.cs.huji.ac.il/ csip/CSIP2007-intro.pdf 3. http://en.wikipedia.org/wiki/Fuzzy logic 4. http://www.seattlerobotics.org/encoder/mar98/fuz/index.html 5. http://www.atp.ruhr-uni-bochum.de/rt1/syscontrol/node117.html

6