nelSenso.it

 Applicazioni

• Summazer 1.0
  

  Text Summarization Tool

• Clustezer 1.0
  

  Text Clustering Tool

• IRezer 1.0
  

  Information Retrieval Tool

Articoli

• Rilevamento della semantica nel testo
• Analisi delle Keywords per MdR
• Teoria delle reti semantiche

News

• 
  Registrazione necessaria
  Per usufruire dei tool disponibili su nelSenso.it è necessaria la registrazione (nick e e-mail obbligatorie).
   
  

visualizza tutte le news

Algoritmi e strutture dati per il trattamento automatico del testo

Dalla teoria della Generic Documents Summarization è possibile applicare alcuni principi ed algoritmi alla rilevazione della semantica e classificazione di Keyphrases in "Topical Gropus" (Clustering).
Le strutture dati e le procedure utili a tal fine sono:

• Il grafo bipartito pesato: G(T, S, [W])
• Il principio di reciproco rinforzo.
• Il grafo pesato non-direzionato: G(S, [WS])
• Incorporare la molteplicità delle Keyphrases
• Clustering e funzione costo euclidea (somma dei quadrati)

Il grafo bipartito pesato

Dato un insieme di keyprases (Kp) consideriamo i seguenti due insiemi:

• T={t1, t2, ...tn} = {Insieme dei Termini, ovvero parole "non stop-words", costituenti le frasi dell'insieme Kp}
• S={s1, s2, ...sm} = Kp = {Insieme delle frasi (Sentences)}
• E' possibile definire una struttura denominata "Grafo Bipartito Pesato" (WBG) come:
  WBG = G(T, S, [W])
  
  dove W è la matrice dei pesi, [W] appartiene ad Rmxn, il generico elemento Wij è calcolato come segue:
  
  if sj.exists(ti) then wij = #(ti) in sj
   

Il Principio di reciproco rinforzo

E' inoltre possibile definire la "rilevanza" (saliency score) dei termini u(T) e delle frasi v(S) secondo il seguente principio:

"Un termine è tanto più rilevante quanto più è elevato
 il numero di frasi rilevanti a cui appartiene,
allo stesso tempo, una frase è tanto più rilevante
 quanti più termini rilevanti essa contiene."

La definizione è evidentemente ciclica ma il dilemma si può risolvere se, per esempio, si assume che inizialmente tutte le frasi abbiano un valore di default uguale per tutte (per esempio 1). In tal caso i vettori delle rilevanze possono essere calcolati come:

for each Ti in T
    for each Sj in S
        u(Ti) = (1/p)*Sum[Wij*v(Sj)]
        v(Sj) = (1/p)*Sum[Wij*u(Ti)]
    next j
next i

dove p è un fattore di normalizzazione che garantisce la non negatività di vettori u(T) e v(S), può essere calcolato in due modi:

p = Max{Wij} oppure normalizzati i vettori u è v:
u_N = u / ||u||
v_N = v / ||v||
allora:
p = u_N^T [W] v_N

In questa seconda modalità la convergenza è garantita.

Ordinando, rispettivamente, T ed S per u(T) e v(S) decrescenti possiamo definire come Categorie principali di Keyword i primi K termini (T1, ...Tk) e come Keyphrases più sematicamente rilevanti le prime H sentecences (S1...Sh)

Il grafo pesato non-direzionato

Il calcolo della rilevanza delle keywords e delle sentences può essere più efficace se applicato alla determinazione di gruppi di frasi semanticamente correlate (categorie/cluster). Per il clustering di keyphrases possiamo immaginare un ipercubo i cui vertici rappresentano le frasi e la lunghezza dei lati è inversamente proporzionale al numero di termini in comune fra le keyphrases poste ai relativi vertici (grafo pesato non-direzionato).

Posto S={s1, s2, ...sm} = Kp = {Insieme delle keyphrases}
resta definita la matrice WS dove il generico elemento Wij= # termini in comune fra si e sj
Denotiamo con G(S, WS) il relativo grafo pesato non-direzionato.

Incorporare le molteplicità delle Keyphrases

E' possibile arrichire W con la molteplicità delle Keyphrases, nel senso che è possibile aggiungere ad ogni wij il numero di volte che è stata utilizzata la stessa j-ma Keyphrase (Sj). Attenzione allo "spamming".
 

Clustering K-Means & "funzione costo euclidea":

La j-ma riga della matrice W del grafo bipartito pesato identifica il "sentence vector" della j-ma Keyphrase, in altri termini costituisce l'insieme delle coordinate della j-ma KeyP. Denotiamolo con:

Wj = [ w1, w2, ..., wN]

Lo spazio vettoriale corrispondente può essere scomposto in k sottospazi (cluster) i cui centri di massa identificano i centroidi. Attraverso l'algotimo di clustering K-means è possibile raggruppare tutte le keyphrases in sottoinsiemi  topici (categorie).