Mokabyte

Dal 1996, architetture, metodologie, sviluppo software

  • Argomenti
    • Programmazione & Linguaggi
      • Java
      • DataBase & elaborazione dei dati
      • Frameworks & Tools
      • Processi di sviluppo
    • Architetture dei sistemi
      • Sicurezza informatica
      • DevOps
    • Project Management
      • Organizzazione aziendale
      • HR
      • Soft skills
    • Lean/Agile
      • Scrum
      • Teoria della complessità
      • Apprendimento & Serious Gaming
    • Internet & Digital
      • Cultura & Società
      • Conferenze & Reportage
      • Marketing & eCommerce
    • Hardware & Tecnologia
      • Intelligenza artificiale
      • UX design & Grafica
  • Ultimo numero
  • Archivio
    • Archivio dal 2006 ad oggi
    • Il primo sito web – 1996-2005
  • Chi siamo
  • Ventennale
  • Libri
  • Contatti
Menu
  • Argomenti
    • Programmazione & Linguaggi
      • Java
      • DataBase & elaborazione dei dati
      • Frameworks & Tools
      • Processi di sviluppo
    • Architetture dei sistemi
      • Sicurezza informatica
      • DevOps
    • Project Management
      • Organizzazione aziendale
      • HR
      • Soft skills
    • Lean/Agile
      • Scrum
      • Teoria della complessità
      • Apprendimento & Serious Gaming
    • Internet & Digital
      • Cultura & Società
      • Conferenze & Reportage
      • Marketing & eCommerce
    • Hardware & Tecnologia
      • Intelligenza artificiale
      • UX design & Grafica
  • Ultimo numero
  • Archivio
    • Archivio dal 2006 ad oggi
    • Il primo sito web – 1996-2005
  • Chi siamo
  • Ventennale
  • Libri
  • Contatti
Cerca
Chiudi

Nel numero:

124 dicembre
, anno 2007

JFilter: un filtro antispam intelligente in Java

II parte: classifier4j per la classificazione bay

Avatar

Francesco Saverio Profiti

Francesco Saverio Profiti ha conseguito la laurea in Ingegneria Informatica presso l‘Università degli Studi Roma Tre nel 2003. Durante la sua carriera lavorativa si è occupato, prima da programmatore, poi da analista e infine da architetto di applicazioni di classe enterprise sia in ambiente Java EE sia in ambiente .NET. Si è occupato inoltre di applicazioni basate su tecnologia SMS e VoIP. Ha ricoperto per la Open Informatica s.r.l. il ruolo di Responsabile della Qualità nell

Avatar

Claudio Biancalana

Claudio Biancalana è dottorando in Ingegneria Informatica presso il Dipartimento di Informatica e Automazione dell‘Università degli Studi Roma Tre. L‘attività di ricerca scientifica svolta finora ha riguardato l‘Intelligenza Artificiale e la Categorizzazione Automatica di Testi (ATC, Automated Text Categorization). Dal 2003 collabora attivamente presso il laboratorio di Intelligenza Artificiale dell‘Università degli Studi Roma Tre per progetti di ricerca europei e internazionali.

Dal 2003 si occupa di analisi e sviluppo di applicazioni Enterprise in ambiente Java EE e attualmente cura gli aspetti architetturali per progetti rivolti al mercato della pubblica amministrazione.

MokaByte

JFilter: un filtro antispam intelligente in Java

II parte: classifier4j per la classificazione bay

Francesco Saverio Profiti e Claudio Biancalana

Francesco Saverio Profiti e Claudio Biancalana

  • Questo articolo parla di: Intelligenza artificiale, Java

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.

Figura 1 – La pipeline del procedimento adottato nell‘analisi del documento

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:

Nell‘implementazione proposta, la classe “Fusion” ha la responsabilità  di modellare la tavola di contingenza sulla quale vengono estratti i valori di Recall e Precision: le variabili di istanza a b c d rappresentano rispettivamente i valori f++, f+-, f-+, f–.

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.

 

Facebook
Twitter
LinkedIn
Avatar

Francesco Saverio Profiti

Francesco Saverio Profiti ha conseguito la laurea in Ingegneria Informatica presso l‘Università degli Studi Roma Tre nel 2003. Durante la sua carriera lavorativa si è occupato, prima da programmatore, poi da analista e infine da architetto di applicazioni di classe enterprise sia in ambiente Java EE sia in ambiente .NET. Si è occupato inoltre di applicazioni basate su tecnologia SMS e VoIP. Ha ricoperto per la Open Informatica s.r.l. il ruolo di Responsabile della Qualità nell

Avatar

Claudio Biancalana

Claudio Biancalana è dottorando in Ingegneria Informatica presso il Dipartimento di Informatica e Automazione dell‘Università degli Studi Roma Tre. L‘attività di ricerca scientifica svolta finora ha riguardato l‘Intelligenza Artificiale e la Categorizzazione Automatica di Testi (ATC, Automated Text Categorization). Dal 2003 collabora attivamente presso il laboratorio di Intelligenza Artificiale dell‘Università degli Studi Roma Tre per progetti di ricerca europei e internazionali.

Dal 2003 si occupa di analisi e sviluppo di applicazioni Enterprise in ambiente Java EE e attualmente cura gli aspetti architetturali per progetti rivolti al mercato della pubblica amministrazione.

Francesco Saverio Profiti e Claudio Biancalana

Francesco Saverio Profiti e Claudio Biancalana

Tutti gli articoli
Nello stesso numero
Loading...

Modelli dei casi d‘uso e progettazione del software

II parte: un esempio concreto

Semantic Integration

Quando si incontrano Integrazione e Web semantico

Ruby in azione

I parte: Componente View e Templates in Rails

Copiare con classe

Il pattern Prototype

Il programmatore e le sue api

II parte: Impostare la fase di analisi

Rich Client Application

I parte: Eclipse Rich Client Application

Nella stessa serie
Loading...

JFilter: un filtro antispam intelligente in Java

I parte: introduzione teorica

Mokabyte

MokaByte è una rivista online nata nel 1996, dedicata alla comunità degli sviluppatori java.
La rivista tratta di vari argomenti, tra cui architetture enterprise e integrazione, metodologie di sviluppo lean/agile e aspetti sociali e culturali del web.

Imola Informatica

MokaByte è un marchio registrato da:
Imola Informatica S.P.A.
Via Selice 66/a 40026 Imola (BO)
C.F. e Iscriz. Registro imprese BO 03351570373
P.I. 00614381200
Cap. Soc. euro 100.000,00 i.v.

Privacy | Cookie Policy

Contatti

Contattaci tramite la nostra pagina contatti, oppure scrivendo a redazione@mokabyte.it

Seguici sui social

Facebook Linkedin Rss
Imola Informatica
Mokabyte