Studio di euristiche per il miglioramento di algoritmi di ranking per il World-Wide Web Università...

Studio di euristiche per il Studio di euristiche per il miglioramento di algoritmi di miglioramento di algoritmi di

ranking per il World-Wide Webranking per il World-Wide Web

Università degli Studi di MilanoUniversità degli Studi di MilanoCorso di Laurea in InformaticaCorso di Laurea in Informatica

Marco OlivoMarco Olivo, A.A. 2002/2003, A.A. 2002/2003

Linee di sviluppoLinee di sviluppo

Due linee direttrici di ricerca:Due linee direttrici di ricerca:► Ideazione e realizzazione di nuovi algoritmi Ideazione e realizzazione di nuovi algoritmi

di di rankingranking per il recupero più mirato di per il recupero più mirato di informazioneinformazione

► Tecniche per l’aggregazione di risultati e per Tecniche per l’aggregazione di risultati e per la valutazione efficiente dei la valutazione efficiente dei matchmatch


Algoritmi di ranking già esistentiAlgoritmi di ranking già esistenti

Implementazione di algoritmi già esistenti: Implementazione di algoritmi già esistenti: PageRank, ProximityPageRank, Proximity

► PageRank funziona PageRank funziona sul grafosul grafo: più una pagina : più una pagina è puntata, più è rilevante (misura è puntata, più è rilevante (misura esogena esogena della popolarità)della popolarità)

► Proximity funziona Proximity funziona sul testosul testo: più nella : più nella pagina le parole richieste sono vicine, più la pagina le parole richieste sono vicine, più la pagina è rilevante (misura pagina è rilevante (misura endogena endogena dell’importanza, relativamente alla richiesta)dell’importanza, relativamente alla richiesta)


… … da soli non bastanoda soli non bastano

Problema:Problema: PageRank + Proximity non PageRank + Proximity non bastano: i risultati sono piuttosto scarsi e bastano: i risultati sono piuttosto scarsi e deludentideludenti

Soluzione:Soluzione: servono (anche) altre tecniche, servono (anche) altre tecniche, quali punteggio ai titoli, punteggio alle URL, quali punteggio ai titoli, punteggio alle URL, punteggio al testo con cui le pagine sono punteggio al testo con cui le pagine sono riferite (riferite (ancoreancore))


Nuovi algoritmi di ranking: TitleRankNuovi algoritmi di ranking: TitleRank

► Si assegna un punteggio ai titoli delle Si assegna un punteggio ai titoli delle pagine: i titoli sono spesso un “riassunto” pagine: i titoli sono spesso un “riassunto” del contenuto delle paginedel contenuto delle pagine

► Il punteggio viene assegnato in maniera Il punteggio viene assegnato in maniera dipendente dalla prossimità: più le parole dipendente dalla prossimità: più le parole richieste sono vicine nel titolo, più il richieste sono vicine nel titolo, più il punteggio della pagina è elevatopunteggio della pagina è elevato


Nuovi algoritmi di ranking: URLRankNuovi algoritmi di ranking: URLRank

Cercando il nome di un sito si desidera di Cercando il nome di un sito si desidera di solito vedere comparire il dominio associato: solito vedere comparire il dominio associato: va dato un punteggio anche agli indirizziva dato un punteggio anche agli indirizzi

““comune di milano” comune di milano” www.comunedimilano.itwww.comunedimilano.it

► Si ricercano le parole contenute nelle URL Si ricercano le parole contenute nelle URL tramite un TST (tramite un TST (ternary search treeternary search tree))

► Si assegna un punteggio basato sulla Si assegna un punteggio basato sulla prossimitàprossimità


Nuovi algoritmi di ranking: AnchorRankNuovi algoritmi di ranking: AnchorRank

Le pagine a volte sono note per qualcosa che Le pagine a volte sono note per qualcosa che non dicono esplicitamente di trattarenon dicono esplicitamente di trattare

““agenzia stampa ansa” agenzia stampa ansa” www.ansa.itwww.ansa.it

sono le pagine che vi si riferiscono ad usare sono le pagine che vi si riferiscono ad usare queste parole nelle ancorequeste parole nelle ancore

bisogna estrarre il testo dalle bisogna estrarre il testo dalle ancore ancore per per trovare le pagine correttetrovare le pagine corrette


AggregazioneAggregazione

Problema:Problema: come aggregare i punteggi dei come aggregare i punteggi dei vari algoritmi?vari algoritmi?

Idea:Idea: generare una combinazione lineare di generare una combinazione lineare di risultatirisultati

Pregi:Pregi:► è facile effettuare esperimenti variando i è facile effettuare esperimenti variando i

coefficienticoefficienti► pulizia di progettazionepulizia di progettazione


Valutazione veloce (1)Valutazione veloce (1)

Problema:Problema: cercare cercare tuttetutte le pagine che le pagine che contengono una parola può essere costosocontengono una parola può essere costoso

Due motivi:Due motivi:► la parola è presente in molti documenti (es. la parola è presente in molti documenti (es.

“milano”)“milano”)► la parola è presente più volte nei documenti la parola è presente più volte nei documenti

(es. “la”)(es. “la”)



Soluzione:Soluzione: la valutazione dei la valutazione dei match match (Proximity) deve essere “tagliata” oltre una (Proximity) deve essere “tagliata” oltre una certa soglia (è meglio se le pagine sono certa soglia (è meglio se le pagine sono ordinate in maniera decrescente secondo un ordinate in maniera decrescente secondo un punteggio statico, ad es. PageRank)punteggio statico, ad es. PageRank)

si usano operatori si usano operatori lazylazy per trovare i match per trovare i match

Ci interessano i primi N risultati con una Ci interessano i primi N risultati con una precisione data: quando tagliare?precisione data: quando tagliare?

simulazione con simulazione con queryquery fittizie fittizieMarco OlivoMarco Olivo, A.A. 2002/2003, A.A. 2002/2003


Per esempio, se ci interessano i primi 400 risultati di Per esempio, se ci interessano i primi 400 risultati di PageRank + Proximity con precisione 95%:PageRank + Proximity con precisione 95%:


inviluppo convessoinviluppo convesso

approssimazioneapprossimazione

DemoDemo

► 20M+ di pagine web tratte da .it20M+ di pagine web tratte da .it► 5 giorni per recuperarle5 giorni per recuperarle► 2 giorni macchina per indicizzarle2 giorni macchina per indicizzarle

proviamoproviamo qualche interrogazione… qualche interrogazione…


ConclusioniConclusioni

► sviluppati algoritmi per migliorare la ricercasviluppati algoritmi per migliorare la ricerca► sviluppata tecnica per aggregare i risultati sviluppata tecnica per aggregare i risultati

restituiti da questi algoritmirestituiti da questi algoritmi► sviluppate tecniche di valutazione veloce dei sviluppate tecniche di valutazione veloce dei

matchmatch► implementazione implementazione completa completa delle tecniche delle tecniche

suddette in un motore di ricerca suddette in un motore di ricerca sperimentalesperimentale

Grazie per l’attenzioneGrazie per l’attenzioneMarco OlivoMarco Olivo, A.A. 2002/2003, A.A. 2002/2003

Studio di euristiche per il miglioramento di algoritmi di ranking per il World-Wide Web Università...

Documents

Transcript of Studio di euristiche per il miglioramento di algoritmi di ranking per il World-Wide Web Università...