Corso di information retrieval

Nei giorni in cui vi prende l'ispirazione hi-tech...prendete in mano la tastiera e sfogatevi qui!

Moderatori: cb_123, tonertemplum

Re: Corso di information retrieval

Messaggiodi Ibanez89 il 16 lug 2008, 21:08

sisi vediamo nel dettaglio
CiAo DanIele...

Immagine
Pentium4 Northwood HT 2.6@3000 "230*13" vcore def [RIP] King Value 512*2 200@230 cas2@3 Ati x800gto2@x850pe powered by Arctic Cooler [RIP] Mother ASRock P4VM900-SATA2 [RIP]
insomma poco alla volta mi si sta bruciando tutto :asd:

Immagine
Avatar utente
Ibanez89
AmdPlanet Guru
AmdPlanet Guru
 
Messaggi: 5563
Iscritto il: 15 apr 2006, 17:31
Località: Corato (BA)

 

Re: Corso di information retrieval

Messaggiodi diegofio il 02 ago 2008, 12:44

LEZIONE #9: PAGERANK

Pagerank è l'algoritmo utilizzato da Google per catalogare le pagine web secondo un punteggio (chiamato appunto pagerank) che ne identifica l'autorevolezza e la rilevanza. Ovviamente oltre al pagerank Google utilizza moltissimi altri (decine) indici, in modo tale da ridurre al minimo possibili "inquinamenti" volti ad aumentare il punteggio di una pagina rispetto ad altre in modo artificiale.

Come sappiamo la rete può essere vista come un grafo in cui i nodi rappresentano le singole pagine web e gli archi i collegamenti tra esse. Per vedere cos'è effettivamente 'sto Pagerank, facciamo un esempio considerando quattro pagine che chiameremo A B C D. Al passo iniziale in pagerank di ognuna è calcolabile come 1/4 ovvero si divide l'unità per il numero di pagine in questione, nel nostro caso quattro. Per ora abbiamo considerato un grafo con quattro nodi non collegati, ma adesso immaginiamo siano presenti i seguenti link:

B -> A
C -> A
D -> A

Il punteggio di A andrà ad aumentare visto che essendo linkata ora da tre pagine, essa viene ad acquistare quella autorevolezza (fornita da altri attraverso i link) che gli consentirà di scalare posizioni nella classifica: il pagerank di A quindi sarà dato dalla somma dei pagerank delle pagine che puntano ad essa, quindi PR(B) + PR(C) + PR (D).

Aumentiamo ora la complessità del grafo introducendo i seguenti link:

B -> C
D -> A
D -> B
D -> C

Ora il pagerank di B influisce meno su A perchè B oltre ad A punta anche a C. Allo stesso modo il pagerank di D influisce su A per un terzo del suo potenziale in quanto solo uno dei tre link di D punta ad A. Quindi PR(A) = PR(B)/2 + PR(C) + PR(D)/3.
La formula generale è molto semplice: per calcolare il pagerank di una generica pagina X basterà considerare tutte le pagine Yi che puntano ad X (possiedono un link verso X) e sommare il loro pagerank, che però andrà diviso di volta in volta per il numero totale di link contenuti nella singola pagina Yi considerata. Se conoscete le sommatorie:

PR(X) = sommatoria_(Yi -> X) [PR(Yi)/#LINK(Yi)]

Se riportate la formula all'esempio, vi accorgerete che è esattamente ciò che abbiamo fatto per calcolare il PR(A).

Il pagerank tuttavia considera nella sua formulazione un utente di internet che si trova in una pagina web: egli avrà una probabilità pari a d (valore detto "dumping factor") di seguire uno dei link presenti nella pagina e una probabilità pari a 1 - d (ricordo che d essendo una probabilità è un valore compreso tra 0 ed 1) di scrivere sulla barra degli indirizzi un url relativo ad una qualsiasi altra pagina del web potenzialmente del tutto scollegata dalla pagina che stava visualizzando in precedenza e di andarla a visitare. Questo fatto viene tenuto in considerazione mediante un fattore correttivo, nell'esempio precedente il pagerank di A diventa:

PR(A) = (1 - d)/N + d * (PR(B)/2 + PR(C) + PD(D)/3)

dove N è il numero totalre di pagine presenti nel grafo, quattro se ci riferiamo allo stesso esempio.
d nella realtà è un valore abbastanza vicino ad 1 percui il secondo addendo di PR(A) conta di più del primo: si tende perciò a dare maggiore importanza nel calcolo del punteggio di una pagina a quanto essa è puntata da altre pagine (dicasi autorevolezza) piuttosto che alla probabilità che essa venga scelta casualmente da un utente tra tutte le pagine del web.
diegofio
AmdPlanet Guru
AmdPlanet Guru
 
Messaggi: 9270
Iscritto il: 29 lug 2005, 09:55

Re: Corso di information retrieval

Messaggiodi Ibanez89 il 02 ago 2008, 18:23

=D> =D> =D> :book: :study: :scratch: ](*,) :-({|=

Continua così :D
CiAo DanIele...

Immagine
Pentium4 Northwood HT 2.6@3000 "230*13" vcore def [RIP] King Value 512*2 200@230 cas2@3 Ati x800gto2@x850pe powered by Arctic Cooler [RIP] Mother ASRock P4VM900-SATA2 [RIP]
insomma poco alla volta mi si sta bruciando tutto :asd:

Immagine
Avatar utente
Ibanez89
AmdPlanet Guru
AmdPlanet Guru
 
Messaggi: 5563
Iscritto il: 15 apr 2006, 17:31
Località: Corato (BA)

Re: Corso di information retrieval

Messaggiodi diegofio il 02 ago 2008, 19:10

il corso è terminato :D
diegofio
AmdPlanet Guru
AmdPlanet Guru
 
Messaggi: 9270
Iscritto il: 29 lug 2005, 09:55

Re: Corso di information retrieval

Messaggiodi Ibanez89 il 02 ago 2008, 21:04

diegofio ha scritto:il corso è terminato :D


:-s :-k sono stato promosso? :cheers:
CiAo DanIele...

Immagine
Pentium4 Northwood HT 2.6@3000 "230*13" vcore def [RIP] King Value 512*2 200@230 cas2@3 Ati x800gto2@x850pe powered by Arctic Cooler [RIP] Mother ASRock P4VM900-SATA2 [RIP]
insomma poco alla volta mi si sta bruciando tutto :asd:

Immagine
Avatar utente
Ibanez89
AmdPlanet Guru
AmdPlanet Guru
 
Messaggi: 5563
Iscritto il: 15 apr 2006, 17:31
Località: Corato (BA)

Precedente

Torna a Guide

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti

cron