Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Walter Balzano » 6.Indicizzazione e recupero dei documenti di testo


Indicizzazione e Recupero dei documenti di Testo

  • Introduzione
  • Differenze IR e DBMS
  • Indicizzazione automatica e modello booleano per il recupero
  • Retrieval con modello spazio vettoriale
  • Retrieval con modello probabilistico
  • Recupero basato su cluster
  • Metodi IR non tradizionali
  • Misurazione delle prestazioni
  • Tecniche di IR a confronto
  • I motori di Ricerca WWW

Introduzione

IR: tecniche di recupero delle informazioni.
Rilevanza storica: grandezza del volume dei dati (es: librerie digitali).
Il testo è impiegato come strumento manuale di annotazione sfruttabile da un IR.

Concetti di base:

  • rappresentazione delle query e dei documenti;
  • IR con diversi modelli di rappresentazione dei documenti ma simili processi di indicizzazione;
  • tecniche di confronto tra documenti e query;
  • modelli maggiormente usati:
    • match esatto (modello booleano);
    • spazio vettoriale;
    • modello probabilistico;
    • modello su Cluster (raggruppamento);
  • query con linguaggio naturale:
    • (problemi di lingua ed ambiguità linguistica);
  • tecniche di Intelligenza Artificiale.

Differenze IR e DBMS

DBMS:

  • struttura omogenea dei record;
  • componenti del record: gli attributi;
  • un record è definito completamente ed univocamente dai propri attributi;
  • retrieval con match esatto (Query ↔ Valore dei campi dei records).

IR:

  • records non strutturati;
  • attributi non prefissati;
  • indicizzazione del documento:
    • keywords;
    • descrittori;
    • Indici (soggettivi ed equivoci);
  • dipendenza dal modello di rappresentazione dei documenti;
  • retrieval con match approssimato o parziale.

Processo base del document retrieval

Schema generale del document retrieval.
Fonte: “modificata, tratta da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc., © 1999 by Artech House, Inc.”

Schema generale del document retrieval. Fonte: “modificata, tratta da Guojun Lu, Multimedia Database Management Sysyems, Norwood, MA: Artech House, Inc., © 1999 by Artech House, Inc.”


Indicizzazione automatica e retrieving booleano


Struttura file

Problema della scelta della rappresentazione della conoscenza:

  • flat file:
    • (ASCII, EBCDIC);
    • ricerca lineare;
    • grep, awk, …;
    • poco efficiente;
  • inverted files;
  • signature files:
    • generazione di “impronte” [signature];
    • metodo hash;
    • confronto tra le signature della query e del documento;
  • allberi;
  • grafi.

Inverted files

L’inverted file contiene un insieme di righe di testo
Ogni riga contiene:

  • il termine che si vuole cercare;
  • una sequenza di puntatori a documenti e/o records che contengono quel termine.

La parola “inverted” spiega quindi l’inversione del verso di ricerca: Prima la chiave e poi il documento che contiene la chiave.

Il processo di ricerca è più efficiente rispetto il flat-file: non si analizzano i documenti interi ma solo l’inverted file da cui si ricavano i collegamenti ai documenti che contengono la chiave (o soddisfano la query).

Query con metodo inverted files.

Query con metodo inverted files.

Esempi di query complesse.

Esempi di query complesse.


Inverted files con operazioni estese

E’ possibile raffinare la ricerca supponendo che sia significativa:

  • la differenza di importanza (peso) tra un termine e un altro;
  • la posizione in cui un termine compare;
  • la frequenza in cui un termine compare all’interno di un documento.

Definiamo 2 nuovi operatori quali “WITHIN SENTENCE” e “ADJACENT” con il seguente significato:

  • Term i WITHIN SENTENCE Term j
    • I Term i e j sono presenti nella stessa frase del record recuperato
  • Term i ADJACENT Term j
    • I Term i e j confinanti nel record recuperato

Struttura generale dell’inverted file esteso

Inverted file esteso: struttura generale.

Inverted file esteso: struttura generale.


Indicizzazione automatica

Il processo di indicizzazione del file di testo prevede diverse fasi; lo scopo principale è quello di filtrare il testo in modo da ottimizzare la significatività delle informazioni da considerare per le ricerche.
Fasi di filtraggio:

  • stop words: elementi insignificanti per la ricerca come “articoli”, “preposizioni”,…;
  • stemming: termine comune per parole analoghe. Esempio: “pescare”, “pescatore”, “pesce” → “pesc” (nota: un termine troppo breve potrebbe non esser significativo);
  • thesaurus: possibilità di sostituire diversi termini simili che compaiono nel testo con un unico termine (usando un vocabolario). Esempio: “lavare”, “pulire”, “detergere” → “lavare”;
  • weighting: i termini che compaiono nel testo hanno diversa importanza valutata tramite frequenze di occorrenza; il risultato della ricerca viene mostrato in ordine di frequenza. Nota: la frequenza di un termine ottenuto dopo un’operazione di stemming o di thesaurus è data dal numero delle occorrenze dei termini che il nuovo termine rappresenta.

Indicizzazione automatica

Esempio di fasi di filtraggio di un file.

Esempio di fasi di filtraggio di un file.


Indicizzazione automatica (stop words)

Esempi di STOP Words.

Esempi di STOP Words.


Retrieval con modello spazio vettoriale

Il modello spazio vettoriale presume l’esistenza di un determinato insieme di termini che rappresentino i Documenti e le Query: un documento Di ed una Query Qj sono definite nel seguente modo:

Di = [Ti1, Ti2,.....Tik,.......TiN]
Qj = [Qj1, Qj2,...Qjk,.......QjN]

In cui:
Tik è il peso del k-esimo termine relativo al documento i;
Qjk è il peso del k-esimo termine relativo alla query j;
N è il numero totale di termini usati nel documento e nella Query.

Retrieval con modello spazio vettoriale (segue)

Il calcolo di similarità “combina” i valori dei vettori di caratteristiche ottenendo così un valore di sintesi eventualmente normalizzato
Nota: lo scopo della normalizzazione è quello di ottenere un parametro di valutazione che sia indipendente dalle dimensioni N dei vettori.
Di fatto il valore di S(Di, Qj) normalizzato. corrisponde al valore del coseno dell’angolo che formano i due vettori Di e Qj .

Calcolo della similarità:

S (D {_i}, Q {_i}) =\Sigma_{ K=1}^{ N}}} T{_{ik}} \cdot Q {_{jk}}

Calcolo della similarità normalizzata:

{S(D{_i}, Q{_j})}=\frac {\Sigma _{K=1}^N T_{jk} \cdot Q_{jk}} \sqrt {\Sigma _{K=1}^N T_{jk}^2 \cdot \Sigma _{K=1}^N Q_{jk}^2

Misurazioni delle prestazioni

Parameteri di valutazione:

  • velocità di ricerca;
  • recall: capacità di recuperare informazioni rilevanti dal database. Si definisce come rapporto tra il numero dei documenti rilevanti recuperati ed il numero totale di elementi rilevanti nel database;
  • precisione: misura l’accuratezza dei documenti recuperati. Si definisce come rapporto tra il numero di documenti rilevanti recuperati ed il numero totale di documenti recuperati.
Calcolo di precisione e recall.

Calcolo di precisione e recall.

Rappresentazione grafica di precisione e recall.

Rappresentazione grafica di precisione e recall.


Misurazioni delle prestazioni (segue)

Nella pratica, i parametri di valutazione recall e precisione vengono valutati in modo congiunto, ed una buona prestazione è indice di un oculato compromesso.
Tipicamente quanto maggiore è la recall tanto minore risulta la precisione: infatti quanto maggiore è lo sforzo della query per prelevare tutti i documenti rilevanti, tanto maggiore sarà la probabilità che in output andranno anche documenti non rilevanti (e quindi imprecisione). Viceversa: quanto maggiore è la precisione tanto minore risulta la recall: per evitare di prendere elementi non rilevanti si finisce inevitabilmente per non prelevare qualche documento rilevante.

Esempi di recall e precisione.

Esempi di recall e precisione.

Esempio: il sistema “B” è migliore  di “A”.

Esempio: il sistema “B” è migliore di “A”.


Tecniche di IR a confronto

L’indicizzazione automatica ha una prestazione simile a quella manuale ed un reale miglioramento si ottiene combinando entrambe le tecniche.
Impiegando un insieme di query simili la performance del recupero mediante confronti (match) parziali si è dimostrata essere migliore del match booleano esatto.
Il modello probabilistico e spazio vettoriali hanno performance analoghe.
Le tecniche di recupero basate su cluster e sul modello probabilistico hanno performance analoghe ma recuperano insiemi diversi di documenti.
Se al primo tentativo non si è riusciti a recuperare documenti rilevanti allora l’uso di Relevance feedback consente un reale miglioramento della prestazione.
L’uso di uno specifico dominio di conoscenza e del profilo utente che effettua la query, produce un significativo miglioramento della prestazione.

I motori di Ricerca WWW

I motori di ricerca sul WWW costituiscono molto probabilmente il tipo di applicazione più utilizzato sul Web.
I documenti Web sono memorizzati come ipertesti in formati quali HTML.

I documenti sono strutturati in NODI, LINK ed ANCHOR:

  • generalmente ogni nodo rappresenta un singolo concetto o un idea;
  • i Link collegano diversi nodi;
  • le aree evidenziate “cliccabili” sono dette ANCHOR ed indicano l’esistenza di un LINK;
  • selezionando un ANCHOR si attiva il LINK corrispondente e il NODO cui fa riferimento viene caricato e visualizzato.

Un ipertesto è un modo di organizzare l’informazione che permette un accesso non sequenziale.
L’Ipermedia è una stensione dell’ipertesto in cui le ancore e nodi possono essere ti tipo qualsiasi.
Il WWW è una estensione geografica dell’ipermedia.

Esempio di ipertesto.

Esempio di ipertesto.


Modello di Comunicazione

Diverse sono le regole di base che governano la comunicazione (i protocolli):
HTTP, HTTPs, FTP, FTPs, ….

Mediante l’interfaccia di un browser, il client effettua la richiesta di un documento al server che attraverso il versatile strato delle CGI (Common Gateway Interface) accede a svariate librerie di funzioni e/o servizi.

Finita l’elaborazione sul server i risultati vengono reindirizzati al client che ne aveva fatto richiesta.

Distribuzione delle applicazioni in architetture client/server.

Distribuzione delle applicazioni in architetture client/server.


Il Web

URL (Uniform Resource Locator): indirizzo che univocamente identifica ogni documento della rete:

Protocoll://Servername[:port]/Path/Document-name
Es.: http://www.na.infn.it/~wbalzano/index.html
ftp://ftp.monash.edu.au/pub/internet/readme.txt

Crawler (detto anche spider o robot): tipo di bot (programma o script che automatizza delle operazioni) che analizza i contenuti di una rete (o di un database) per conto di un motore di ricerca nel Web.
Solitamente acquisisce una copia testuale di tutti i documenti visitati e li inseriscono in un indice.
Si basa su una lista di URL da visitare fornita dal motore di ricerca (basata su indirizzi suggeriti dagli utenti o su liste precompilata dai programmatori stessi).
Durante l’analisi di un URL, identifica tutti gli hyperlink presenti nel documento e li aggiunge alla lista di URL da visitare.

Esempi di nomi degli spider dei principali motori di ricerca.

Esempi di nomi degli spider dei principali motori di ricerca.


Il Web (segue)

Poiché i documenti selezionati sono comunque tanti, per poterli mostrare all’utente è necessario comunque organizzarli (Ranking).
Poiché i documenti selezionati sono comunque tanti, la caratteristica di precisione del motore è più importante della caratteristica di recall (anche perché partendo dai “pochi” documenti selezionati, posso navigare e raggiungere gli altri documenti).
Un modo per organizzare i documenti, assegnando loro dei pesi, è basato sulla formattazione del testo HTML.

Recupero, analisi e ranking dei documenti.

Recupero, analisi e ranking dei documenti.


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion