Automatic Text Segmentation:
Text Relationship Map (Salton 1996)
Ing. Leonardo Rigutini
Dipartimento di Ingegneria dell’Informazione
Università di Siena
Via Roma 53
53100 – SIENA – ITALY
[email protected]
Ing. Rigutini Leonardo – Automatic Text Segmentation: Text Relationship Map
Text Relationship map
• Salton 1996
• Vector space model:
•
•
•
•
Di=(di1 , di2 , … , dit )
dik = peso del termine Tk nel documento Di
Sim( Di , Dj ) =  dik x djk
Sim viene normalizzata in modo da  (0,1)
• Una volta calcolate le similitudini si costruisce la mappa
Ing. Rigutini Leonardo – Automatic Text Segmentation: Text Relationship Map
Text Relationship map
17012
11830
0.49
0.57
0.54
0.24
17016
0.50
8907
0.33
0.38
0.23
19199
0.09
22387
Link under 0.01 ignored
Figure 1: Text Relationship Map: articoli di enciclopedia riguardanti l’energia termo-nucleare
Ing. Rigutini Leonardo – Automatic Text Segmentation: Text Relationship Map
Nodi e archi
• Importanza di un nodo correlata al numero di archi
incidenti:
• Un nodo centrale è caratterizzato da un grande numero di
archi
• Grafo altamente connesso:
• Molti nodi importanti
• Trattazione dell’argomento omogenea
• Grafo debolmente connesso:
• Nodi importanti sparsi
• Piu’ argomenti separati (poca omogeneita’)
• Trattazione cronologica, geografica ecc ...
Ing. Rigutini Leonardo – Automatic Text Segmentation: Text Relationship Map
Grafo altamente connesso
Ing. Rigutini Leonardo – Automatic Text Segmentation: Text Relationship Map
Grafo scarsamente connesso
Ing. Rigutini Leonardo – Automatic Text Segmentation: Text Relationship Map
Automatic Text Decomposition
• Studio delle relazioni tra i nodi del grafo
• Due tipi di analisi:
• Segmenti
unita’ di testo (nodi) omogenee e contigue, altamente
connesse tra loro e poco connesse con i restanti nodi del
grafo.
• Tematiche
unita’ di testo semanticamente omogenee senza vincoli di
adiacenza.
Ing. Rigutini Leonardo – Automatic Text Segmentation: Text Relationship Map
Text Segments - 1
• Trovare gap nelle connessioni tra paragrafi adiacenti
• Vengono eliminati i collegamenti tra nodi distanti oltre
un certo k (Salton pone k=5)
Ing. Rigutini Leonardo – Automatic Text Segmentation: Text Relationship Map
Text Segments - 2
• Non e’ garantita la coerenza del tema trattato
• Molti argomenti possono essere trattati in maniera non
lineare
Per cercare coerenza bisogna rilassare il vincolo di
adiacenza e considerare tutti i collegamenti esistenti
Text Theme
Ing. Rigutini Leonardo – Automatic Text Segmentation: Text Relationship Map
Text Themes
• Si considerano i triangoli presenti nel grafo
• triangolo = insieme di tre nodi mutualmente correlati
• Ogni triangolo e’ rappresentato da
• un vettore centroide Ci=(N1,N4,N8) dove Nk e’ il nodo k
• un valore Si che e’ la media dei vettori del triangolo
• Fusione dei centroidi:
• I triangoli vengono fusi quando la similitudine tra coppie di
centroidi supera una determinata soglia
• Il processo si ripete fino a che nessuna fusione e’ possibile
Ing. Rigutini Leonardo – Automatic Text Segmentation: Text Relationship Map
Text Themes - es
Ing. Rigutini Leonardo – Automatic Text Segmentation: Text Relationship Map
Relazioni tra segmenti e temi
• E’ possibile calcolare gradi di similitudine:
• segment-segment
informazioni sulla struttura del documento (figura 7)
• theme-theme
informazioni sulla centralita’ di alcune tematiche e sulla
particolarita’ di altre (figura 8)
• theme-segment
tipo di documento:
–
–
–
–
singolo tema trattato sotto piu’ punti di vista
piu’ temi scorrelati
un tema centrale e vari paragrafi secondari]
ecc...
Ing. Rigutini Leonardo – Automatic Text Segmentation: Text Relationship Map
Segment-segment
Ing. Rigutini Leonardo – Automatic Text Segmentation: Text Relationship Map
Theme-theme
Ing. Rigutini Leonardo – Automatic Text Segmentation: Text Relationship Map
Theme-segment
1. segmenti & temi abbastanza congruenti:
•
•
•
Tema sviluppato in maniera lineare
parti di testo abbastanza adiacenti
Es.
–
–
–
articoli su un singolo argomento
articoli su piu’ argomenti abbastanza scorrelati e trattati in
maniera cronologica (relazione 1 a 1)
Temi trattati sotto piu’ punti di vista (T  piu’ S)
2. temi e segmenti non congruenti
•
•
Argomento sospeso e ripreso in seguito
Es.
–
Introduzione e succesive spiegazioni
Ing. Rigutini Leonardo – Automatic Text Segmentation: Text Relationship Map
Es. singolo tema
Ing. Rigutini Leonardo – Automatic Text Segmentation: Text Relationship Map
Es. Storie multiple
Ing. Rigutini Leonardo – Automatic Text Segmentation: Text Relationship Map
Es. Tema scorrelato dal resto del documento
Ing. Rigutini Leonardo – Automatic Text Segmentation: Text Relationship Map
Es. grande tema centrale e due piccoli approfondimenti
Ing. Rigutini Leonardo – Automatic Text Segmentation: Text Relationship Map
Text retrieval
• Tecniche standard di recupero possono non essere quelle
migliori
• Quando una query riguarda un tema discontinuo nel
documento, il recupero di segmenti non e’ una buona
soluzione, ma e’ meglio restituire un insieme di segmenti
• Quindi:
• Per strutture semplici  text segment
• Per strutture complesse  text theme
Ing. Rigutini Leonardo – Automatic Text Segmentation: Text Relationship Map
Information retrieval: simple structure
Ing. Rigutini Leonardo – Automatic Text Segmentation: Text Relationship Map
Information retrieval: simple structure
Ing. Rigutini Leonardo – Automatic Text Segmentation: Text Relationship Map
Information retrieval: complex structure
Ing. Rigutini Leonardo – Automatic Text Segmentation: Text Relationship Map
Information retrieval: complex structure
Ing. Rigutini Leonardo – Automatic Text Segmentation: Text Relationship Map