JFilter: un sistema di classificazione automatico di testi per il dominio della posta elettronica che implementa un algoritmo fuzzy di classificazione di e-mail.

JFilter: Il fitro anti-spam intelligente

In questo articolo presenteremo 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). L‘area di interesse è quella definita con li termine “apprendimento automatico” (Machine Learning), una disciplina relativa allo studio di algoritmi in grado di simulare processi cognitivi nei calcolatori. Nel seguito forniremo alcuni principi di logica fuzzy e formuleremo l‘algoritmo di classificazione per il dominio della posta indesiderata.

Logica Fuzzy

I computer, così come noi oggi li conosciamo, lavorano internamente secondo schemi di tipo on/off; nella logica classica, un predicato può assumere soltanto due possibili valori: vero o falso, tertium non datur (non esistono vie di mezzo). L‘utilizzo di questa modalità  di decisione binaria ha portato al raggiungimento di grandi risultati tecnologici. Eppure, in molti contesti che riguardano la realtà  quotidiana, essi non sono sufficienti per modellarne alcuni aspetti. In particolare, attraverso la logica binaria non è possibile definire l‘incertezza.
L‘incertezza è una componente molto importante del pensiero umano e del suo modo di percepire l‘ambiente che lo circonda. Quando parliamo per esempio di una persona simpatica o antipatica, spesso ci riferiamo ad essa con affermazioni del tipo abbastanza simpatica, che introducono un certo margine di incertezza (vari livelli di sfumatura).
Nel tentativo di risolvere questo problema, Zadeh teorizzò la cosiddetta logica fuzzy, che altro non è che il tentativo di generalizzare la logica classica a due valori, portandola a schemi molto più vicini al ragionamento umano. Per meglio comprendere l‘idea che sta alla base della logica fuzzy, passiamo ad introdurre il concetto di insieme fuzzy.
Nella teoria classica degli insiemi, detta degli insiemi crisp (“dai contorni bene definiti”), la funzione di appartenenza di un elemento dell‘universo di definizione U ad un dato insieme A è definita come segue:

per ciascun elemento dell‘universo è così possibile stabilire se esso appartiene o non appartiene all‘insieme A. È possibile dunque affermare ad esempio, che tizio è una persona simpatica perché appartiene all‘insieme delle persone simpatiche. Un‘insieme fuzzy (“sfumato”) è un‘estensione di questo concetto, in cui la funzione di appartenenza viene definita come:

In questa nuova ottica, si è in grado non soltanto di affermare se tizio fa parte o meno dell‘insieme delle persone simpatiche, ma si è in grado anche di affermare che esso vi appartiene con grado 0.56 (abbastanza simpatico), modellando così un certo grado di incertezza.
Sulla base della definizione di insieme fuzzy, è possibile costruire un sistema logico, appunto detto logica fuzzy, in cui una proposizione è vera con un certo grado di verità  pari ad esempio a 0.56 (e dunque falsa con grado di falsità  pari a 0.44).
La logica fuzzy gioca un importante ruolo nel campo dell‘information retrieval e del machine learning, mostreremo infatti come una semplice formulazione fuzzy possa essere applicata in un dominio di classificazione automatica di e-mail SPAM.

L‘approccio ML alla classificazione dei testi

Negli anni Ottanta l‘approccio più popolare per la creazione di classificatori automatici di testi, consisteva nella creazione manuale, mediante tecniche di ingegneria della conoscenza, di un sistema esperto capace di prendere una decisione di classificazione. I sistemi esperti di questo tipo consistono di un insieme di regole logiche definite manualmente, una per categoria, del tipo.

if  then

Una formula DNF (“Forma Normale Disgiuntiva”) è una disgiunzione di clausole congiuntive, il documento è classificato nella categoria se e solo se soddisfa la formula, cioè se e solo se soddisfa almeno una delle clausole.
A partire dagli anni Novanta, l‘approccio Machine Learning alla classificazione dei te-sti, ha guadagnato popolarità  ed è divenuto il dominante tra la comunità  scientifica. In questo approccio, un processo induttivo generale (anche chiamato learner), costruisce au-tomaticamente un classificatore per una categoria “C” osservando le caratteristiche di un insieme di documenti classificati manualmente nella categoria “C” oppure “NON C” da un esperto del dominio; da queste caratteristiche, un processo induttivo predice le caratteri-stiche che un nuovo documento non visto dovrebbe avere per essere classificato nella ca-tegoria “C”. Nella terminologia ML, il problema di classificazione è un‘attività  di apprendi-mento supervisionato, essendo l‘apprendimento un processo “supervisionato” dalla cono-scenza delle categorie e dalle istanze di training che appartengono loro.

Metodi di apprendimento

Esistono molte metodologie basate sul machine learning per i filtri anti-spam: modelli generativi su classificatori Naive Bayes, algoritmo di Rocchio (il più popolare metodo di apprendimento in l‘Information Retrieval), k-Nearest-Neighbor, alberi di decisione.
Nel seguito mostreremo l‘algoritmo di Rocchio da cui esamineremo una variante Fuzzy.

Fuzzy Rocchio

Il classificatore Rocchio nasce sull‘algoritmo di relevance-feedback originalmente proposto da Rocchio per il modello di spazio verttoriale per il ritrovamento di informazioni. È stato largamente usato all‘interno di sistemi di classificazioni di testi.
Il modello di spazio vettoriale si propone di valutare il grado di similarità  di un documento d1 rispetto al documento da classificare d2 come la correlazione dei vettori rappresentativi. Questa correlazione può essere quantificata, ad esempio, come il coseno dell‘angolo tra i due vettori.

I pesi dei termini possono essere calcolati in molti modi. L‘idea alla base delle tecniche più efficienti è legata al concetto di cluster, proposto da Salton.
Si pensi ai documenti come a una collezione C di oggetti e ai documenti da classificare come a una vaga specificazione di un insieme A di oggetti. Il problema della TC può essere allora ridotto a quello di determinare quali documenti sono nel set A e quali no; in particolare in un problema di clustering occorre risolvere due sottoproblemi. Occorre determinare quali siano le caratteristiche che meglio distinguono gli oggetti dell‘insieme A dagli oggetti della collezione C (dissimilarità  intercluster).
Nel modello vettoriale “classico” la similarità  intracluster è quantificata misurando la frequenza di un termine k in un documento d: questa viene detta fattore TF (term frequency) e misura quanto un termine descrive i conteunti del documento. La dissimilarità  intercluster è invece quantificata misurando l‘inverso della frequenza di un termine k tra i documenti della collezione (fattore IDF o inverse document frequency).
Inizialmente vengono sommate sia i documenti in forma vettoriale normalizzata degli esempi positivi che degli esempi negativi. La componente lineare della regola di classificazione si esprime con la seguente formula:

Supponiamo inoltre che gli elementi negativi del vettore w abbiano valore pari a 0. Beta è un parametro che regola gli impatti di esempi positivi e negativi. Nel seguito viene mostrato lo pseudocodice dell‘algoritmo:

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

Riassumiamo i passi… Usiamo lo standard di indicizzazione INTRA-CLUSTER/INTER-CLUSTER per rappresentare in forma vettoriale i documenti di testo (normalizzati secondo la frequenza massima di un termine). Per ogni categoria, elaboriamo un vettore “prototipo” dalla somma dei vettori di training della categoria infine assegniamo il documento di test alla categoria col vettore “prototipo” più vicino mediante l‘utilizzo di misure di similarità  Fuzzy.
l valore di similarità  viene calcolato attraverso una nota formulazione di correlazione nota come indice di Jaccard. La formula dell‘indice di Jaccard è: s = c/(p+q-c), dove c rappresenta il numero di individui presenti simultaneamente nelle due popolazioni e p e q gli effettivi di ciascuna di esse. Se si preferisce è possibile definire la misura di jaccard come il rapporto tra unione e intersezione:

La tabella di figura 01 che segue mostra le misure fuzzy tipicamente utilizzate di unione e intersezione grazie ai quali verranno ricavati i valori di correlazione con le categorie HAM e SPAM.

Mostriamo un esempio per chiarire i concetti sino ad ora esposti.
La tabella di figura 2 che segue mostra una situazione in cui il dominio è composto da 4 documenti: d1, d2 appartenenti alla categoria SPAM e d3, d4 alla categoria HAM. I termini totali del dominio sono 6 (t1 … t6) e i valori termine-documento rappresentano la frequenza.

Il primo passo da effettuare è la normalizzazione dei prototipi: sommo e normalizzo i vettori delle categorie SPAM e HAM.

Attraverso questo semplice preprocessamento riusciamo ad ottenere 2 vettori “prototipo” caratteristici, rispettivamente, della categoria SPAM e HAM.

Conclusioni

In questo articolo abbiamo introdotto le basi teoriche per affrontare la questione della classificazione automatica di email spam. Abbiamo esposto alcuni principi cardine della filosofia fuzzy ed infine siamo entrati nel dettaglio di un algoritmo di classificazione fuzzy dicotomico (SPAM vs HAM) per il dominio della posta indesiderata. Nel prossimo articolo vedremo come applicare praticamente i concetti affrontati, studiando l‘implementazione Java di JFilter.