Capitolo 1: Introduzione
3
in modo efficiente, con conseguente spreco di risorse e spesso anche con
duplicazione delle informazioni stesse.
Al fine di fornire una soluzione a tali problemi sono stati fatti molti tentativi nei
due filoni di ricerca relativi e precisamente del Text Classification (TC) e
dell�Information Retrieval (IR).
La Classificazione di Testi (TC) � il processo che consente di associare testi in
linguaggio naturale ad una categoria tematica scelta tra un insieme di categorie
predeterminato. Se l�operazione di classificazione � gestita interamente dal
sistema senza l�interazione con l�utente, la classificazione si dice automatica
1
.
Il processo di classificazione (TC) � usato in pi� contesti. Ad esempio:
l�indicizzazione automatica dei documenti al fine del loro recupero efficiente, la
disambiguazione di termini, il filtraggio di documenti e in generale in tutte le
applicazioni in cui � richiesta un�organizzazione tematica dei documenti.
Il recupero delle informazioni (IR) �� il processo coinvolto nella rappresentazione,
nella memorizzazione, nella ricerca e nel recupero di informazioni rilevanti
rispetto ad una richiesta di informazioni effettuata da un utente� [P. Ingwersen et
al. �95].
L�obiettivo dei sistemi di IR � �condurre l�utente a quei documenti che meglio
soddisfano la sua richiesta di informazioni� [Belking et al. �92].
In passato i sistemi per il recupero di informazioni erano incentrati su basi di dati
bibliografiche ed erano basati su approcci booleani, cio� veniva verificato se la
parola desiderata fosse contenuta o meno nell�insieme dei documenti esistenti.
Oggi tuttavia la situazione � sicuramente progredita. Le tecniche di recupero
(retrieval) basate su IR sono adottate nella maggior parte dei servizi che
coinvolgono la ricerca di informazioni, a partire da Internet stesso (vedi per
esempio Lycos, infoseek). Molte delle caratteristiche che erano considerate troppo
1
In seguito ogni qual volta � specificato il termine �classificazione� si intende:
classificazione automatica
Capitolo 1: Introduzione
4
esoteriche per l�utente individuale, come richieste in linguaggio naturale, risultati
ordinati per rilevanza, pesatura dei termini, �., vengono ora fornite in modo
naturale.
In generale l�IR non � ristretta ad una specifica tipologia di documenti che siano
essi testuali, grafici od addirittura animazioni, ma nella maggior parte dei casi le
informazioni trattate sono contenute in documenti di tipo testuale. In questo caso
gli oggetti trattati possono essere lettere, documenti di ogni tipo, articoli di
giornale, libri, sommari medici, articoli di ricercatori, oppure descrizioni in
linguaggio naturale di oggetti pi� complessi. In questa tesi vengono considerate
solo fonti testuali (o descrizioni in linguaggio naturale di altri tipi di oggetti), e di
conseguenza solo i problemi inerenti al recupero di documenti scritti in linguaggio
naturale.
Un sistema di classificazione e recupero dei documenti � incentrato su due
funzionalit� principali:
• la classificazione dei documenti, cio� l�individuazione del gruppo di
documenti pi� simili (rispetto al contenuto) al documento dato.
• la ricerca dei documenti a seguito di un�interrogazione di un utente.
Ci� significa che nella realizzazione di un tale sistema i problemi che si devono
affrontare sono essenzialmente:
• come interpretare i documenti e le interrogazioni scritti in linguaggio
naturale al fine di:
o �capire� di cosa trattano
o selezionare le parti che meglio li descrivono, scartando i termini
meno significativi
o tradurli in un formato comprensibile per gli altri moduli del sistema
• come individuare la categoria in cui classificare il documento
• come individuare i documenti che meglio soddisfano le richieste
dell�utente
Capitolo 1: Introduzione
5
1.2 Obiettivo della tesi
Lo scopo di questa tesi � la realizzazione di un sistema di classificazione per
documenti testuali ed un sistema di ricerca tale da permettere il recupero di
documenti a seguito di interrogazioni dell�utente.
Quindi si � deciso di realizzare:
1. un sistema di classificazione per documenti scritti in lingua inglese che
avesse prestazioni paragonabili con quelle presenti in letteratura.
2. un sistema di recupero che permettesse agli utenti di formulare
interrogazioni in linguaggio naturale controllato.
Questo sistema � stato sviluppato nell�ambito del progetto ECOLNET
2
presso il
Laboratorio di Ricerca e sviluppo di Engineering Ingegneria Informatica S.p.a.,
rispettando i requisiti di questo progetto.
L�obiettivo pi� generale di ECOLNET � quello di sviluppare un sistema
collaborativo che consenta lo scambio di informazioni sia sotto forma di
documenti che di dati, al fine di proporre una nuova strategia basata sul concetto
di collaborazione per le aziende di media e piccola dimensione in
contrapposizione al fenomeno della fusione tra grandi aziende che in questi ultimi
anni sta caratterizzando l�evoluzione del mercato. Secondo l�approccio di
ECOLNET, le piccole e medie aziende pur mantenendo la loro indipendenza,
possono allargare il loro mercato attraverso la creazione di una rete di
cooperazione.
2
ECOLNET-11061 (European COLlaboration NETwork) � un progetto di ricerca cofinanziato dalla
Comunit� Europea nell�ambito del V programma quadro sulla Societ� della Tecnologia
dell�Informazione IST (Information Societies Technology)
Capitolo 1: Introduzione
6
1.3 Risultati raggiunti
Gli obiettivi preposti sono stati completamente raggiunti. Infatti nella tesi � stato
realizzato un classificatore automatico ed innovativo di documenti scritti in
inglese, le cui prestazioni sono in linea con quelle degli altri sistemi presenti in
letteratura. L�innovazione principale deriva dall�uso di un sistema di pesatura dei
termini introdotto per la prima volta in questa tesi. La realizzazione di tale
classificatore � stata possibile anche grazie all�uso di un modulo per
l�elaborazione linguistica implementato in una precedente tesi [Fabriani �00].
Inoltre � stato costruito un sistema di ricerca dei documenti in cui le interrogazioni
degli utenti possono essere sottomesse in linguaggio naturale controllato.
1.4 Struttura della tesi
La tesi � strutturata in quattro capitoli, escluso il presente, e diverse appendici. Il
codice � contenuto in un volume separato.
Il secondo capitolo riguarda lo stato dell�arte, cio� tutto ci� che esiste ed � stato
realizzato o studiato nel campo della classificazione di documenti e del recupero
degli stessi. Viene descritto il metodo pi� usato nella rappresentazione dei
documenti, e vengono esposti gli algoritmi di classificazione pi� citati in
letteratura ed i modelli esistenti su cui si basa il recupero dei documenti.
Il terzo capitolo descrive in dettaglio il sistema che � stato realizzato, spiega la
procedura con la quale sono state estratte le informazioni dai documenti, il
metodo scelto per la classificazione, come sono state gestite le interrogazioni in
linguaggio naturale e l�algoritmo realizzato per la ricerca.
Il quarto capitolo descrive i metodi esistenti per valutare i sistemi di
classificazione e di recupero di documenti, gli esperimenti realizzati al fine di
stimare la validit� del sistema realizzato e di confrontare i risultati con quelli di
altri sistemi presenti in letteratura o realizzati nell�ambito del progetto.
Nel quinto capitolo sono state raccolte le conclusioni del presente lavoro.
Capitolo 1: Introduzione
7
1.5 Notazioni e convenzioni tipografiche
• italic font per tutti i termini un lingua inglese, per le variabili e per le i
nomi di procedure, di sistemi e aziende.
• �parole tra virgolette� per l�uso di termini non formalmente corretti per
esprimere un concetto ma che lo rappresentano in modo pi� intuitivo o per
indicare espressioni straniere.
• lo pseudocodice � scritto in italic font e contenuto in un rettangolo.
• [rif.]: i riferimenti bibliografici sono specificati tra parentesi quadre.
1.6 Ringraziamenti
Lo svolgimento di questa tesi � stata possibile grazie alla collaborazione e alla
disponibilit� del Laboratorio di Ricerca e Sviluppo di Engineering Ingegneria
Informatica S.p.a. che mi ha messo a disposizione l�attrezzatura e la
documentazione necessaria, ed al suo direttore Dott. Dario Avallone al quale
vanno i miei ringraziamenti.
Un ringraziamento particolare al Dott. Stefano De Panfilis, mio correlatore, al
Dott. Andrea Manieri, al Dott. Piero Corte e al Dott. Francesco Torelli per i
preziosi suggerimenti e consigli. Ringrazio anche le altre persone che sono state di
supporto alla realizzazione di questa tesi, in particolare il Dott. Alessandro
Rinaldi.
Desidero infine ringraziare la Prof.ssa Paola Velardi, relatrice della tesi, per il suo
interessamento, per avermi fornito consigli e materiale e per avermi dato la
possibilit� di svolgere la tesi presso una societ� esterna.
2
CLASSIFICAZIONE E RECUPERO DI
DOCUMENTI:
LO STATO DELL’ARTE
2.1 Architettura di un sistema di classificazione e
recupero documenti
La Figura 1 descrive lo schema di un processo generico di classificazione e di
recupero dei documenti; come si pu� notare lo schema � diviso in due parti: il
sistema di classificazione e il sistema di recupero dei documenti.
Capitolo 2: Classificazione e recupero dei documenti: lo stato dell�arte
9
documenti
operazioni
sul testo
testo
pesatura dei
termini
insieme di termini
DATABASE
termini
pesati
assegnamento ID
ai documenti
documenti
numero del
documento
user
interface
interrogazioni
interpretazione
query
stemming
query
termini della query
parole ridotte
alla radice
RICERCA
ranking
insieme di
documenti
rilevanti
documenti
rilevanti
ordinati
classificazione
descrittori delle
classi
Figura 1: il processo di classificazione e recupero dei documenti
sistema
di
classificazione
sistema di
recupero dei
documenti
Capitolo 2: Classificazione e recupero dei documenti: lo stato dell�arte
10
Le funzioni di un sistema di classificazione sono:
1. le operazioni sul testo necessarie per produrre una rappresentazione del
documento.
2. la pesatura dei termini che consiste nell�assegnare un valore che sancisce
l�importanza dei termini che lo rappresentano.
3. la classificazione che permette l�assegnamento dei documenti a un insieme
di categorie preesistenti. La classificazione di un nuovo documento �
possibile solo dopo una fase iniziale di apprendimento (training). Questa
fase di apprendimento si basa su un insieme di esempi chiamati �training
example� che sono documenti precedentemente classificati manualmente
da utenti esperti. Tramite quest�ultimi il sistema �apprende� un modello di
classificazione generando un insieme di descrittori delle classi che
permettono di classificare i nuovi documenti.
Le funzioni di un sistema di recupero dei documenti sono:
1. la possibilit� per l�utente di sottomettere delle interrogazioni (query), che
vengono prima interpretate (interpretazione delle query) tramite
l�individuazione delle parole chiavi e la trasformazione della query in
un�espressione.
2. la riduzione di tutti i termini alla radice (stemming).
3. la ricerca nel database per individuare i documenti rilevanti.
4. l�ordinamento per rilevanza (ranking) di tutti i testi recuperati in modo
che i pi� �simili� alla query compaiano in cima alla lista, e possano essere
mostrati all�utente; naturalmente non viene mostrato l�intero documento,
ma un collegamento ad esso, in modo tale che se l�utente � interessato, pu�
recuperare il documento in modo veloce.
Il sistema di recupero, per essere funzionante, richiede che i documenti siano stati
memorizzati nella base dati in seguito alla classificazione.
Si pu� notare che sia i documenti che le query vengono analizzati allo stesso
modo, cio� una query pu� essere vista come un particolare documento.
Capitolo 2: Classificazione e recupero dei documenti: lo stato dell�arte
11
2.2 Metodi di rappresentazione del contenuto di un
documento
2.2.1 Descrizione del problema
Prima che un sistema automatico di recupero delle informazioni (Information
Retrieval, IR) possa realmente funzionare l�informazione deve essere gi�
memorizzata nel computer. Tuttavia memorizzare l�intero testo di un documento,
cio� la sua rappresentazione in linguaggio naturale, non � utile ai fini del sistema,
poich� un elaboratore non � in grado di comprendere tale linguaggio. Si deve
perci� memorizzare una rappresentazione strutturata del documento, derivata
manualmente o automaticamente da esso. Il punto di partenza del processo di
analisi del testo pu� essere l�intero documento, un breve riassunto (abstract), un
titolo o una lista di parole. Con questo processo si produce una rappresentazione
del documento in una forma che il sistema � in grado di gestire [van Rijsbergen
�79].
2.2.2 Rappresentazione dei documenti
I modelli classici di classificazione e di recupero dei documenti considerano
ciascun documento come descritto da un insieme di parole chiavi rappresentative,
chiamate termini indice. Un termine indice � una parola la cui semantica aiuta a
ricordare il tema trattato dal documento. Quindi i termini indice sono usati per
riassumere il contenuto del documento, in generale sono nomi, ma possono essere
usati anche aggettivi e verbi. Dato un insieme di termini indice, si pu� notare che
non tutte le parole sono egualmente utili per descrivere i documenti, infatti ci sono
dei termini indice pi� vaghi di altri; decidere l�importanza di un termine per
riassumere il contenuto di un documento non � una cosa banale. Malgrado queste
difficolt� ci sono delle propriet� di un termine indice che sono facilmente
misurabili, e che sono utili per valutare le potenzialit� di un termine. Si consideri
per esempio una collezione che contiene centomila documenti. Una parola che
appare in ciascuno dei centomila documenti � completamente inutile come
Capitolo 2: Classificazione e recupero dei documenti: lo stato dell�arte
12
termine indice poich� non discrimina tra un documento e un altro. D�altro canto,
una parola che compare in soli cinque documenti � abbastanza utile poich�
restringe considerevolmente lo spazio dei documenti interessanti. Quindi, termini
indice distinti, hanno rilevanza diversa al fine di descrivere il contenuto di un
documento, e questo effetto � catturato attraverso l�assegnamento di un peso
numerico a ciascun termine indice di un dato documento. Perci� sia t
i
un termine
indice, d
h
un documento e w
i,h
≥ 0 il peso associato alla coppia (t
i
,d
h
) che
quantifica l�importanza del termine indice nella descrizione della semantica del
documento.
Definizione 1 Sia M il numero di termini indice in un sistema e t
i
un generico
termine indice. T = {t
1
,........,t
M
} � l�insieme dei termini indice. Un peso w
i,h
> 0 �
associato a ciascun termine t
i
di un documento d
h
. Per un termine indice che non
compare nel testo del documento d
h
, w
i,h
= 0. Ad ogni documento d
h
� associato
un vettore
h
d
ρ
rappresentato da ),......,,(
,,2,1 hMhhh
wwwd =
ρ
. Inoltre sia g
i
la
funzione che restituisce il peso associato al termine indice t
i
dato un vettore
h
d
ρ
(
hihi
wdg
,
)( =
ρ
).
Per la definizione 1 vale l�assunzione che in generale nei sistemi di pesatura i pesi
dei termini indice sono considerati mutuamente indipendenti, cio� conoscere il
peso della coppia (t
i
,d
h
) non ci d� informazioni circa il peso associato alla coppia
(t
i+1
,d
h
). Questa � una semplificazione poich� le ricorrenze dei termini indice non
sono in realt� scorrelate [Baeza et al. �99].
L�estrazione dei termini indice dal documento e la creazione della struttura che lo
rappresenta � chiamata indicizzazione.
Questo modello, che � il pi� comune usato in letteratura per la rappresentazione
dei documenti, � chiamato Vector Space Model [Salton et al. �83].
I documenti possono quindi essere rappresentati da una matrice W le cui M righe
rappresentano i termini t
1
,...,t
M
, le cui N colonne sono i documenti d
1
,......,d
N
e
l�elemento w
i,h
rappresenta il peso del termine t
i
nel documento d
h
.
Capitolo 2: Classificazione e recupero dei documenti: lo stato dell�arte
13
Esempio:
DOC 1 2 3
cat 1 0 1
dog 1 1 0
lion 0 1 0
In Figura 2 si pu� vedere la rappresentazione grafica dell�esempio di Tabella 1 per
un dizionario di tre parole: i tre assi sono le parole del dizionario: cat, dog e lion,
ed i tre documenti sono indicizzati rispettivamente come <cat, dog>, <dog,lion>,
<cat>. Tale rappresentazione in generale � in uno spazio N-dimensionale, dove N
� il numero di termini del dizionario (in questo caso � tridimensionale).
CAT
DOG
LION
doc 2
doc3
doc 1
Tabella 1: Matrice rappresentante tre documenti: doc1, doc2 e doc3
Figura 2: Vettori delle caratteristiche nello spazio delle parole
Capitolo 2: Classificazione e recupero dei documenti: lo stato dell�arte
14
2.2.3 La scelta dei termini indice
Come si � gi� detto non tutte le parole sono ugualmente significative per
rappresentare la semantica di un testo, infatti una parte delle parole del documento
non descrivono il contenuto, ad esempio gli articoli, le preposizioni, i pronomi...,
mentre alcune parole sono pi� significative di altre. Perci� usare tutti i termini che
formano i documenti introduce troppo �rumore� nei processi di classificazione e
di retrieval. D�altra parte scegliere i termini pi� significativi di un testo non �
un�operazione banale.
In passato l�indicizzazione veniva fatta manualmente da una persona (utente
esperto) che leggeva i documenti, o un riassunto di essi, e decideva quali termini
dovevano rappresentarne il contenuto e quali potevano essere scartati. Era
sicuramente il miglior metodo per trovare i termini indice di un documento, ma la
crescente quantit� di documenti da indicizzare e il continuo miglioramento delle
tecniche di indicizzazione automatiche, cio� totalmente svolte dal calcolatore,
hanno fatto preferire quest�ultime.
Le tecniche di indicizzazione automatiche possono usare approcci linguistici,
statistici, o una miscela di entrambi.
Gli approcci linguistici entrano nel merito del significato e in base a questo
decidono se scartare o meno il termine, gli approcci statistici, invece, si basano su
informazioni statistiche estratte dal testo, senza effettuare un preprocessamento
linguistico del testo stesso.
Oggi tuttavia, approcci statistici puri sono usati solo nei casi in cui si vuole
rimanere totalmente indipendenti dalla lingua, poich� si � notato che criteri
statistici associati a semplici tecniche linguistiche (es. stemming 2.2.3.2.C)
aumentano l�efficienza del sistema.
2.2.3.1 Approcci statistici
Gli approcci statistici si basano sull�idea di Luhn [Luhn �58], pioniere
nell�indicizzazione automatica di testi, secondo la quale la frequenza delle parole
in un documento in linguaggio naturale fornisce un�utile misura del significato
Capitolo 2: Classificazione e recupero dei documenti: lo stato dell�arte
15
della parola. Inoltre, la posizione relativa della parola all�interno di una frase ha
importanza al fine di determinare il significato stesso della frase.
L�assunzione che la frequenza dei dati possa essere usata per estrarre le parole e le
frasi che rappresentano un documento si basa sulla legge di Zipf [Zipf �49].
Quest�ultima pu� essere sintetizzata affermando che il rapporto tra grado (rank) e
frequenza di ogni parola in un testo � costante. In particolare, sia f
t
la frequenza
del termine t in un dato testo e sia r
t
il grado del termine una volta che tutti i
termini sono stati ordinati in maniera decrescente in base alla loro frequenza
(ovvero il termine di frequenza massima ha grado = 1, mentre il secondo ha grado
= 2, e cos� via), cio� che le parole pi� frequentemente usate avranno un grado pi�
basso, mentre quelle usate raramente avranno un grado pi� alto.
Grado(r) Term Frequency(f)
1 the 69,971
2 of 36,411
3 and 28,852
4 to 26,149
5 a 23,237
6 in 21,341
7 that 10,595
8 is 10,099
9 was 9,816
10 he 9,543
La legge di Zipf si esprime con:
r
t
f
t
(r) = c
dove c � una costante dipendente dalla lingua.
Per la lingua inglese c tende a N/10, dove N � il numero delle parole nella
collezione.
Tabella 2: Illustrazione della legge di grado-frequenza :
(numero di parole in totale: 1,000,000)
Capitolo 2: Classificazione e recupero dei documenti: lo stato dell�arte
16
Tale legge implica che un termine con f ricorrenze ha r approssimativamente 0.1N
/ f
t
, con 0.1 costante per la lingua inglese.
Questa legge � stata spiegata citando un �principio generale di minimo sforzo�
che rende pi� semplice, per colui che parla o scrive, ripetere certe parole invece di
fare sforzi per trovare nuove parole da usare. La legge considera anche il fatto che
le parole pi� frequenti tendono ad essere parole poco significative e facili da
trovare, cio� con basso costo d�uso.
Luhn definisce due soglie, una minima e una massima, in modo tale da
distinguere tre intervalli: uno di alta, uno di media e uno di bassa frequenza.
Le parole ad alta frequenza sono di solito �parole generiche�, come articoli e
preposizioni, le parole a bassa frequenza sono invece quelle �rare� e non danno un
contributo significativo per comprendere il contenuto del documento; quindi tutte
le parole che si trovano nei due intervalli di alta e bassa frequenza non vengono
considerate nel processo di indicizzazione del documento.
Quindi, per applicare tale teoria alla rappresentazione dei documenti � necessario:
• calcolare la frequenza del termine k nel documento i, freq
ik
• determinare la frequenza totale della collezione:
•
∑
=
ikk
freqtotalFreq per i=1,2,...,n.
• Ordinare i termini rispetto alla frequenza della collezione
• Definire due soglie, una per eliminare i termini ad alta frequenza e una per
eliminare i termini a bassa frequenza
• usare i termini rimanenti come indice
Figura 3: Analisi della significativit� delle parole
Parole non
significative:
alta frequenza
Parole non
significative:
bassa frequenza
parole pi�
significative
parole in ordine descrescente
in base alla frequenza
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
