Basi di dati distribuite
Prof. M.T. PAZIENZA
a.a. 2003-2004
WEB SPIDERS /CRAWLERS
PERSONALIZZATI
Web Spiders
Definizione:
I web spider sono dei tool che attraversano lo
spazio d’informazione del web seguendo
cammini ipertestuali per trovare documenti
attraverso
• il protocollo standard HTTP o
• qualunque altro metodo.
Web Spiders
Introduzione
Il Web continua a crescere a dismisura: le sue
dimensioni e la sua dinamicità rendono sempre
più difficile trovare informazione utile anche
all’interno di un stesso sito web.
Bassi valori di recall e pagine obsolete diventano
sempre più frequenti
Web Spiders
Motivazioni (1)
Le dimensioni enormi rendono impossibile
collezionare tutte le pagine, indicizzarle e
mantenere aggiornati gli indici al variare dei
contenuti.
Inoltre i risultati della ricerca mancano di
indicazioni personalizzate per l’utente
Web Spiders
Motivazioni (2)
Su Web è difficile limitare la ricerca di informazioni utili
su un sito particolare. La maggior parte dei motori di
ricerca indicizza solo alcune pagine di ciascun sito, per
cui la recall è bassa e talvolta capita che nessun
documento utile venga ritrovato
Anche se i più importanti siti hanno motori di ricerca
interni, la ricerca è da questi ultimi condotta secondo
schemi propri e predefiniti e non secondo il modello
utente.
Web Spiders
Motivazioni (3)
La maggior parte dei motori di ricerca indicizza solo una
parte (max. 16%) delle pagine esistenti su tutto il web,
per cui la recall è bassa a preescindere da ogni altra
considerazione.
Poichè ciascun motore di ricerca usa propri e predefiniti
algoritmi di ricerca, indipendentemente dalla titpologia
sia dei siti che degli utenti, la ricerca risulta
inefficiente e poco efficace.
Web Spiders
Motivazioni (4)
A causa dell’alto numero di accessi giornalieri, i
vari motori di ricerca cominciano a non avere
capacità di calcolo sufficienti a supportare tutte le
richieste di informazione da parte degli utenti.
Diminuiscono i controlli (esiste ancora la pagina? È
possibile classificare le pagine ritrovate?...)
Web Spiders
Soluzione proposta
Definire web-search tools castomizzati che
siano in grado di supportare l’utente
localizzando i siti interessanti in maniera più
efficace e dotandosi di maggiori capacità di
calcolo per migliorare le prestazioni.
Web Spiders
Soluzione proposta: Approcci
Analisi basata sul contenuto (utile soprattutto
per gestire la variabilità dei contenuti su web)
Analisi basata sulla struttura (produce risultati
valutabili numericamente)
Analisi basata sul contenuto
Il contenuto di una pagina viene analizzato per indurre
informazioni e verificarne l’interesse per la ricerca.
Tecniche di indicizzazione sono usate per estrarre i
concetti chiave identificati in un testo
• Il titolo fornisce una prima valutazione di rilevanza
• Alle parole in esso contenute viene assegnato un
ruolo più significativo
• L’esistenza di una terminologia aiuta ad identificare
il dominio di conoscenza
Analisi basata sulla struttura
L’analisi dei link uscenti da una pagina permette di
avere utili informazioni sulla sua tipologia.
L’assunzione di partenza è:
se l’autore di una pagina A la collega ad una pagina B,
allora sta evidenziando implicitamente un
collegamento semantico tra le due
se la pagina B è nota nel suo contenuto, si può inferire
un contenuto simile per A
se una pagina contiene molti link, la pagina è molto
importante
…
Web Spiders
Soluzione proposta
Tipologie di tools:
• Web search engines and spiders
• Monitoring e filtering
• Indexing e categorization
Web Search Engines
General-purpose search engines (ciascuno con proprie
caratteristiche ed algoritmi di ricerca)
E.g., AltaVista, Google, Lycos, NorthernLight
Web directory (i siti vengono raggruppati in categorie,
quindi si crea una gerarchia)
E.g., Yahoo!
Meta-search engines (si connettono a vari altri motori di
ricerca ed integrano i risultati ottenuti; utili quando
una ricerca copre vari siti)
E.g., MetaCrawler, DogPile
….
Web Search Engines
…
Domain-specific / client-side search engines (vengono
collezionate pagine e si percorrono i link in esse
contenuti per raffinare il processo; poichè il software
gira sulla macchina client, si può allocare più tempo di
cpu e più memoria a supporto del processo di ricerca.
Questi tool permettono un maggior controllo ed una
personalizzazione della ricerca da parte dell’utente)
E.g., BuildingOnline, LawCrawler
Monitoring e filtering
A causa della dinamicità del web è importante
monitorare i siti per riconoscere
cambiamenti e filtrare le informazioni
indesiderate.
Nel caso l’utente possa specificare le sue
specifiche esigenze informative, possono
essere definiti tool per filtrare i risultati
Monitoring e filtering
Agenti intelligenti personalizzati possono essere
utilizzati per monitorare i siti web, riconoscere le
informazioni e filtrarle secondo i requisiti utente.
Metodologie di machine learning vengono
ampiamente implementate in agenti intelligenti
allo scopo di imparare le preferenze dell’utente (e
quindi utilizzarle nelle fasi di filtraggio delle
informazioni non utili).
Indicizzazione
I documenti testuali vengono indicizzati per
migliorare l’attività di ricerca
Algoritmi per l’indicizzazione automatica sono
comunemente usati per l’identificazione di
concetti all’interno di testi.
Allo scopo vengono usate metodologie di analisi
linguistica dei testi; il riconoscimento di frasi
nominali è ampiamente usato per indicizzare in
base a frasi, piuttosto che a sole parole.
Categorizzazione
I tool di categorizzazione supportano l’utente nell’attività
di classificazione dei documenti in differenti
categorie; esistono 2 approcci:
1. I documenti sono categorizzati in base agli attributi
del singolo documento (es. frequenza dei termini
presenti nella query); i documenti trovati vengono
organizzati in base alla dimensione, argomenti trattati,
autore,…
2. I documenti sono categorizzati in base alle similarità
tra documenti (i documenti vengono raggruppati in
regioni fornendo una mappa dove ogni regione
contiene docuumenti simili )
Categorizzazione – Sessione utente
1. Viene inserito dall’utente l’indirizzo del sito e la
chiave di ricerca
2. Vengono visualizzati i risultati della query con gli
indirizzi dei siti contenenti l’informazione cercata
3. Vengono identificate le noun phrase all’interno dei
documenti e l’utente può selezionare le frasi che
preferisce siano usate per la categorizzazione
4. Le mappe risultanti vengono visualizzate all’utente (i
passi 3 e 4 possono essere ripetute pe rmigliorare il
processo complessivamente.
CI Spider
CI Spider colleziona pagine in tempo reale da
siti specificati dall’utente, quindi effettua
indicizzazioni e categorizzazioni su di essi
per fornire all’utente una vista d’insieme dei
siti ritenuti interessanti.
(per dettagli vedasi l’articolo “Personalized spiders for web
search and analysis”, autori: M. Chau, D. Zeng e H. Chen
da cui sono tratte le slides che seguono)
CI Spider
1. Enter Starting URLs and
Search Terms.
2. Search results from
spiders are displayed
dynamically.
3. Noun Phrases
are extracted from
the web pages and
user can select
preferred phrases
for categorization.
4. A Topic Map (SOM) based on the
phrases selected is generated.
Steps 3 and 4 can be iterated to
refine the results.
Meta spider
Meta Spider, ha funzionalità simili a quelle di
CI spider, ma al posto di effettuare una
visita breadth-first su un sito web specifico,
si connette a differenti motori di ricerca ed
integra i risultati ottenuti.
(per dettagli vedasi l’articolo “Personalized spiders for web
search and analysis”, autori: M. Chau, D. Zeng e H. Chen
da cui sono tratte le slides che seguono)
Meta Spider
1. Choose among 6 Search
Engines and enter Search
Terms.
2. Search results from
different search engines
are displayed.
2.1. Every result page
is retrieved from the
Internet to verify that it
is accessible and
contains the search
terms.
3. Noun Phrases are extracted
from the web pages; user can
select preferred phrases for
categorization.
4. A Topic Map (SOM) is generated
based on the phrases selected.
Steps 4 and 5 can be iterated to
refine the results.
Architettura di CI e Meta spider
Aspetti di Personalizzazione
In CI e Meta spider, l’utente può :
• Scegliere di far effettuare una ricerca avanzata
• Specificare il numero di pagine che devono essere
trovate
• I domini di ricerca (indirizzi, es. gov. Edu., com.)
• Selezionare le frasi che devono essere usate per
l’analisi a supporto della produzione delle mappe
finali
• Definire un dizionario personalizzato contenente i
termini che si vuole o non si vuole includere nei
risultati dell’analisi linguistica per la produzione di
mappe
Misure di valutazione
• Theme Precision:
number of correct themes identified by the subject
number of all themes identified by the subject
• Theme Recall:
number of correct themes identified by the subject
number of all themes identified by the expert judges
• Time:
time subject needed to perform the search
• Qualitative analysis/Questionnaire
Misure di valutazione
Velocità ed efficienza (attualmente i tool più
sofisticati sono capaci di scaricare più di 10
milioni di documenti al giorno per workstation)
Politica di spidering (politica adottata
nell’accedere a parte o tutte le pagine di un sito)
Information retrieval (quali algoritmi ed euristiche
adottare per ritrovare documenti più
efficacemente)
Applicazioni
Ricerca personale e personalizzata
Costruzione di collezioni di documenti
specifici
Archiviazione di pagine
Statistica su web
….