Facultatea de electronica, telecomunicatii si tehnologia informatiei

4.Web structure mining

Ceea ce diferentiaza World Wide Web de alte colectii de documente este ca Web-ul, in afara de documentele pe care le contine, este puternic caracterizat de hiperlegaturile care inter-conecteaza aceste documente. In consecinta, Web-ul poate fi imaginat ca un graf, a carui structura consta din noduri – reprezentate de paginile Web – si din muchii – reprezentate de hiperlegaturile care fac legatura intre doua pagini. Web structure mining poate fi privit ca si procesul descoperirii informatiei de structura din Web. Acest tip de mining poate fi, mai departe, impartit in doua ramuri, aceasta impartire avand la baza tipul datelor structurale folosite:

• 
  Hiperlegaturile: o hiperlegatura este o unitate structurala care conecteaza o pagina Web cu o alta locatie, fie in cadrul aceleiasi pagini Web, fie cu o pagina Web diferita. O hiperlegatura care face legatura cu un fragment diferit al aceleiasi pagini se numeste Intra-Document Hyperlink, iar o hiperlegatura care conecteaza doua pagini diferite se numeste Inter-Document Hyperlink.
  
• 
  Structura documentului: continutul unei pagini Web poate fi organizat intr-un format cu structura arborescenta, pe baza tag-urilor HTML si XML din codul paginii. In acest domeniu, eforturile s-au concentrat pe extragerea automata a structurilor DOM (document object model) din documente.
  

In scopul de a face mai usoara navigarea in aceasta structura haotica, sunt folosite motoare de cautare, lansandu-se interogari pe baza unor termeni/cuvinte cheie specifice. La inceput, cand cantitatea de informatie continuta de Web nu avea aceste proportii uriase, motoarele de cautare foloseau liste construite manual, care acopereau topici populare. Era intretinut un index care continea o lista pentru fiecare cuvant al tuturor paginilor Web care-l contineau. Acest index era folosit pentru a raspunde interogarilor utilizatorilor. Dupa cativa ani, cand Web-ul a evoluat, incluzand milioane de pagini, intretinerea manuala a unor astfel de indecsi a devenit foarte scumpa. Motoarele de cautare automate bazate pe potrivirea de cuvinte dadeau rezultate de ordinul sutelor (sau chiar mai mult) de pagini Web, cele mai multe dintre ele de calitate slaba. Nevoia de a categorisi cumva rezultatele dupa importanta si relevanta a devenit mai mult decat evidenta.

Pentru a rezolva aceasta problema, motoare de cautare precum AltaVista, Lycos, Infoseek, HotBot si Excite au introdus cateva euristici simple pentru a realiza categorisirea paginilor. Aceste euristici luau in considerare de cate ori aparea termenul cautat in document, daca aparea la inceputul textului sau in zone considerate mai importante (precum antetele, textul cursiv).

Totusi, designerii Web au incercat curand sa traga avantaje din acest mod de categorisire, incluzand cuvinte sau fraze de multe ori sau in locuri invizibile, astfel incat paginile sa fie favorizate de motoarele de cautare. Aceasta practica se numeste spamming si a devenit un motiv pentru motoarele de cautare de a incerca sa gaseasca moduri mai avansate de a categorisi paginile Web.

Principala realizare in domeniul cercetarii cautarii pe Web s-a produs prin luarea in considerare a caracterizarii si a evaluarii unei pagini de catre alti oameni. Aceasta se face prin intermediul structurii de link-uri a Web-ului, considerandu-se legaturile care trimit la pagina. Cei mai importanti algoritmi care au la baza aceasta idee sunt PageRank si HITS.

Intuitia din spatele analizei link-urilor este ca o pagina Web este mai importanta/populara daca multe alte pagini trimit catre ea. Totusi, este considerata foarte importanta daca este referita de pagini de incredere. Si invers, o pagina care trimite catre alte pagini este de incredere daca aceste pagini referite sunt importante.

4.1.PageRank

PageRank a fost dezvoltat de Brin si Page in timpul doctoratului lor la Universitatea Stanford. Furnizeaza un mod mai sofisticat de calcul al importantei unei pagini Web decat simpla socoteala a numarului de pagini care au un link care sa o refere. Astfel, daca o referinta vine de la o pagina importanta, atunci aceasta are o pondere mai mare decat referintele care vin de la pagini mai putin cunoscute.

Primul lucru care trebuie calculat este numarul link-urilor care fac referinta la fiecare pagina Web. Acesta nu este cunoscut apriori, fiind folosita o parcurgere aleatoare a grafului: se viziteaza o pagina, apoi se urmaresc echiprobabil link-urile acesteia catre alte pagini. La final, fiecare pagina va avea o rata de vizitare, care va defini importanta sa. Totusi, “surferul” poate intalni bucle (pagini care se refera una pe cealalta) sau poate vizita o pagina care sa nu aiba nici un link catre alta pagina. Pentru a intampina aceste situatii, surferul urmareste echiprobabil unul dintre link-urile de iesire cu probabilitate de 90%, in timp ce, cu o probabilitate de 10%, viziteaza (aleator) alta pagina. Astfel, surferul nu va ramane niciodata blocat local.

Urmatoarea ecuatie calculeaza PageRank-ul unei pagini:

unde t1-tn sunt paginile care trimit catre pagina A, C este numarul de legaturi spre afara pe care le are o pagina, iar d este un factor de rotunjire, setat de obicei la 0.85.

Cu alte cuvinte, o pagina contribuie la valoarea PageRank a fiecarei pagini pe care o refera cu o valoare ceva mai mica decat propriul PageRank. Aceasta valoare este aceeasi pentru toate paginile referite. Deci, sunt importante atat PageRank-ul paginii care trimite catre alta, cat si numarul total de link-uri pe care pagina le contine. Cu cat numarul de link-uri este mai mare, cu atat valoarea din PageRank cu care contribuie este mai mica. Algoritmul trebuie executat de cateva ori recursiv inainte de a atinge echilibrul.

PageRank este algoritmul din spatele celui mai popular motor de cautare – Google.