In questo ultimo articolo della serie presenteremo nel dettaglio un sistema di classificazione automatico di testi per il dominio della posta elettronica: JFilter, un modulo Java che implementa un algoritmo fuzzy di classificazione di documenti (e-mail).
Metodo di rappresentazione
La rappresentazione che proponiamo nel nostro sistema si basa sull‘approccio “bag of word”: la vista logica dei documenti è rappresentata da un insieme di parole chiave, le quali possono essere estratte direttamente dal testo della e-mail, senza conoscerne il significato ma facendo riferimento solamente alla morfologia del token estratto.
Nella figura viene mostrato il procedimento adottato nell‘estrazione delle feature del documento da analizzare.
Nella pipeline mostrata in figura, il documento (e-mail) viene elaborato da un processo di “stemming” (o normalizzazione, che riduce diverse parole alla loro comune radice grammaticale, in inglese “stem”) e con l‘identi?cazione di gruppi di nomi (che elimina aggettivi, avverbi e verbi). Queste elaborazioni, dette di text operation riducono la complessità della rappresentazione del documento, permettendo di passare dalla vista logica full text (senza alcun processamento) a quella dell‘insieme delle parole chiave.
Ipotizzando di dividere il documento in “parole” (word) conosciute e riconoscibili (anche su basi statistiche), possiamo utilizzare la metrica definita da TF-IDF (Term Frequency, Inverse Document Frequency), tecnica statistica utilizzata nell‘information retrival e nel text mining.
Nel termine TF si evidenzia la frequenza con cui una determinata “parola” appare in un documento; tale valore può anche essere pesato in base a determinati criteri, ad esempio per alleggerire il peso di “parole” ricorrenti.
Il termine IDF è la misura del peso del termine, relativamente al corpus dei documenti, e viene ottenuto dividendo il numero di tutti i documenti per il numero dei documenti contenti la “parola” in oggetto, e prendendone il logaritmo.
Chiaramente è necessario un insieme elevato di stringhe pertinenti (il corpus dei documenti) per avere delle misure valide relativamente a un documento in input.
Applicando un vector space model (VSM), nel quale ogni documento è rappresentato da un vettore, dove la dimensione è data dal numero di termini distinti, possiamo utilizzare lo schema TD-IDF insieme al concetto di similarità coseno (descritto nella prima parte) per definire distanze fra documenti.
Tipicamente la definizione dei termini dipende dall‘applicazione e anche in questo caso le diverse tecniche utilizzate per dimensionare il dominio e separare i termini sono parametri chiave nella determinazione del risultato.
Nell‘implementazione proposta, il documento da analizzare viene “tokenizzato” (suddiviso in token che nel nostro caso sono parole); dopo aver elaborato (e ridotto) l‘elenco delle parole, è necessario indicizzarle. La forma di indice utilizzata è l‘inverted index. Un inverted index è un meccanismo orientato alle parole per indicizzare una collezione di testo, al ?ne di velocizzare l‘operazione di ricerca. La struttura dell‘inverted index è composta da due elementi: il vocabolario e le occorrenze. Il vocabolario è l‘insieme di tutte le parole del testo; per ognuna di queste è conservata una lista di tutte le posizioni nel testo dove essa compare. L‘insieme di tutte queste liste viene chiamato occorrenze.
Con riferimento all‘implementazione proposta la classe ‘SparseVector‘ si occupa della gestione del vettore sparso dove vengono memorizzati i valori di frequenza dei termini;
...
public void addTerm(String term, double value)
{
Double inc = new Double(value);
if (map.containsKey(term))
{
double app = ((Double)map.get(term)).doubleValue()+value;
inc = new Double(app);
}
if (inc>maxValue)
{
maxValue = inc;
maxWord = term;
}
map.put(term,inc);
}
...
Il Corpus preso in esame è suddiviso in 2 categorie (SPAM, HAM), durante la lettura delle email preclassificate necessarie alla fase di apprendimento, la base di conoscenza annotata è memorizzata all‘interno di una struttura dati definita dalla classe ‘AnnotedDocs‘ dove in ogni email, viene descritta la relativa classe di appartenenza:
public class AnnotedDocs
{
private Map<String, MultiLabel> docs;
public AnnotedDocs()
{
docs = new HashMap<String, MultiLabel>();
}
public void addDoc(String name, String label)
{
if (docs.containsKey(name))
((MultiLabel)docs.get(name)).addLabel(label);
else
{
MultiLabel ml = new MultiLabel(name,label);
docs.put(name, ml);
}
}
public List getLabels(String name)
{
return (docs.get(name)).getLabels();
}
}
Riproponiamo l‘algoritmo Fuzzy descritto nel precedente articolo:
TRAIN
Sia l‘insieme delle categorie {c1,c2,...,cn}
For i from 1 to n leti pi = <0,0,...,0> (inizializzazione)
For each esempio di training <x,c(x)> in D
Let d = vettore INTRA-CLUSTER/INTER-CLUSTER per il doc x
Let i = j: (ci=c(x))
(somma di tutti i vettori in ci per ottenere pi)
Let pi = pi + d
TEST
Dato un documento di test x
Led d = vettore INTRA-CLUSTER/INTER-CLUSTER per x
Let m = -2 (inizializzazione)
For i from 1 to n:
(calcola la similarità col vettore prototipo)
Let s = fuzzySim(d, pi) similarità fuzzy
if (s>m)
Let m = s
Let r = ci (aggiorna il più simile)
Return class r
L‘implementazione dell‘algoritmo è interamente contenuta all‘interno della classe “Centroids” che si occupa di modellare i centroidi e le metriche di similitudine fra vettori:
...
public double getMembership(String dictTerm, String category)
{
double value = 0.0;
for(int i=0; i<centroids.length; i++)
{
Centroid centroid = centroids[i];
if (category.equals(centroid.getCategory()))
value = centroid.getSv().getFreq(dictTerm);
}
return value;
}
public double sim(Document doc, String category)
{
double res = 0.0;
Iterator iter = doc.getSparseVector().getTerms().iterator();
while(iter.hasNext())
{
String word = (String)iter.next();
double mem1 = getMembership(word, category);
double mem2 = doc.getMembership(word);
res = res + Jaccard.jaccardSim(mem1, mem2);
}
return res;
}
...
l valori di similarità vengono calcolati attraverso una nota formulazione di correlazione conosciuta come indice di Jaccard (rapporto fra unione e intersezione); l‘implementazione è definita dalla seguente classe “Jaccard”, in cui con getTNorm si specifica il metodo per ottenere i valori di unione mentre con getTConorm i valori di intersezione.
public class Jaccard
{
private static double getTNorm(double x, double y) { ... }
private static double getTConorm(double x, double y) { ... }
public static double jaccardSim(double x, double y) { ... }
{
double ret = 0.0;
double num = getTNorm(x, y);
double den = getTConorm(x, y);
if (num!=0 || den!=0)
ret = getTNorm(x,y)/getTConorm(x,y);
return ret;
}
}
Prestazioni dell‘algoritmo (modelli di costo)
Le misure di performance più utilizzate nel contesto della classificazione di e-mail fanno riferimento alla “tavola di contingenza” delle predizioni su un test set indipendente dal training utilizzato in fase si apprendimento. La tavola di contingenza fornisce la predizione per la classificazione binaria:
Figura 2 – Tabella di contingenza per la predizione
Ogni cella della tabella rappresenta una delle quattro possibili situazioni per la predizione per un esempio di ingresso. Le celle diagonali contano le frequenza delle predizioni corrette; quelle fuori dalla diagonale mostrano la frequenza delle predizioni errate. La somma di queste celle eguaglia il numero totale delle predizioni.
Sebbene i modelli di costo risolvano i problemi di distribuzioni non equilibrate di esempi fra classi, non risultano intuitivamente interpretabili. Una valutazione più dettagliata può essere fornita con gli indicatori di Recall e Precision.
Definiamo la Recall della regola del nostro classificatore Fuzzy come la probabilità che un documento con etichetta SPAM sia classificato correttamente; dalla tavola di contingenza possiamo esprimere questa misura come:
La precision della regola del classificatore Fuzzy è la probabilità che un documento classificato come SPAM sia invece classificato correttamente:
public class Fusion
{
public int a;
public int b;
public int c;
public int d;
...
public double getRecall()
{
return (((double) a)/(double)(a+c));
}
public double getPrecision()
{
return (((double) a)/(double)(a+b));
}
...
}
Conclusioni
In questo articolo siamo entrati nel dettaglio dell‘implementazione di un algoritmo di classificazione fuzzy dicotomico (SPAM vs HAM) per il dominio della posta indesiderata.
I sorgenti allegati (scaricabili dal menu in alto a sinistra) forniscono la soluzione completa al problema posto, e rimandiamo alla loro documentazione per una descrizione specifica delle soluzioni tecniche adottate.