Tecniche di Data Mining per la Classificazione – Alberi di Decisione

Date: 2011.03.16 | Category: Data Mining | Tags: WEKA Data Mining

Con il processo di data mining si esplora e si analizza una grande quantità di dati (database molto grandi) con l’obiettivo di ricavare delle informazioni di interesse che sono implicite nei dati. Si utilizzando le tecniche di data mining per scoprire correlazioni tra i dati (regole di associazione), per creare dei classificatori che predicono il valore di una variabile (es. alberi di decisione, reti neurali) oppure per suddividere dei dati che non conosciamo a priori, in gruppi con caratteristiche simili (clustering). Queste sono solo alcune delle tecniche di data mining disponibili in letteratura e saranno quelle trattate a grandi linee in questo articolo.

Classificazione

Con la tecnica di classificazione si apprende un modello per fare una predizione su valore di una variabile. A differenza di altre tecniche, come il clustering, la classificazione richiede la conoscenza a priori dei dati ed è una tecnica supervisionata.

Nella classificazione disponiamo di un insieme di record chiamato “training set” che contiene un attributo speciale che è l’etichetta di classe. L’etichetta di classe rappresenta la categoria a cui quel record appartiene. A partire da questo insieme costruiamo un “modello” delle “categorie e/o classi” che ci permetta di assegnare a queste classi nuovi record che sono sprovviste dell’etichetta di classe, con la massima accuratezza.
Il modello serve quindi a riconoscere e assegnare la categoria corretta ai nuovi record privi di etichetta.

Per validare il modello si usa un pezzo del training set, che si chiama test setche in pratica sono dei record del training set a cui è stata volutamente rimossa l’”etichetta di classe” con lo scopo di valutare come si comporta il classificatore che ho appena creato, cioè se predice la classe corretta. Il test set si usa per valutare l’accuratezza del modello stesso. Quindi apprendo il modello dai dati del training set e poi lo valido con i dati del test set, perché tanto io so quale sarà l’etichetta corretta poiché l’ho rimossa e così posso fare dei confronti.
Per “accuratezza” si intende il numero di record classificati corettamente dal modello rispetto al totale dei record classificati.

Per validare un modello ci sono diverse tecniche: matrice di confusione, matrice costi e misure di richiamo/precisione.

La classificazione ha diversi campi di applicazione:

• Direct Marketing: strategia di promozione mirata (Es. voglio promuovere un nuovo telefono cellulare e voglio trovare i clienti che è più probabile che lo comprino).
• Riconoscimento delle Frodi
• Customer Attrition
• Medicina – Predire il decorso tumorale
• Analisi dei testi
• Concessioni di credito
• Stipulazione Contratti
• Valutazione del rischio in una compagnia di assicurazione
• etc

Esempio di Classificazione

Nella figura è riportato un esempio di classificatore che cerca di predire se una persona sta evadendo il fisco (cheat – barare) nella propria denuncia dei redditi.
Il training set è composto da un data set costituito da attributi di vario tipo (Tid – Transaction ID, Refund che significa “se ha richiesto un rimborso”, Marital Status (stato civile) – Taxable Income (entrate tassabili) e poi Cheat (Sta Barando). Cheat è l’etichetta di classe che il classificatore vuole predire. In questo caso il classificatore si dice booleano perché Cheat può valere solo “Si” oppure “No”.

Dal training set il classificatore apprende il modello. Successivamente prende una porzione del training set, rimuove l’etichetta di classe e li utilizza come dati di test. Tali record saranno dati in pasto al motore del modello che genererà la sua predizione. Si confronta il valore predetto con quello reale per capire quanto è accurato il modello.

Tecniche di Classificazione

• Classificazione basate su Alberi di Decisione
• Classificazione basata su Regole
• Classificazione Associativa
• Classificazione Bayesiana
• Classificazione Instance Based

Slide di Riferimento

Le slide di riferimento prese per questo articolo sono “Data Mining – Classification: Basic Concepts, Decision Trees, and Model Evaluation – Lecture Notes for Chapter 4 – Introduction to Data Mining by Tan, Steinbach, Kumar” e sono scaricabili a questo link.

Alberi di decisione

L’albero di decisione è un modello utilizzato per la classificazione che viene costruito analizzando i vari attributi che descrivono i record che stiamo processando. Grazie ad un test sul valore di un attributo, possiamo suddividere i dati, navigando l’albero dalla radice fino a giungere ad una foglia che è l’etichetta di classe. Gli archi rappresentano il risultato del test sull’attributo.

Nei nodi interni dell’albero si testa una condizione su un attributo di un record. Le foglie dell’albero contengono le etichette di classe.
In figura è riportato un possibile albero di decisione che può essere implementato per predire il problema dell’evasione del fisco proposto prima.

Esempio di funzionamento del modello per classificare un nuovo record

Vediamo come funziona il sistema per un nuovo record da classificare privo di etichetta di classe:

Il nuovo record da classificare è quello che nella figura si chiama “Test Data” e contiene come attributi:

• Refund: no (non ha chiesto un rimborso)
• Marital Status: Married (Stato civile – Sposato)
• Taxable Income: 30K (Entrate Tassabili: 30K)

Questo soggetto sta cercando di evedare il fisco?? Come vedete l’etichetta “Cheat” è “?”

Si parte dalla radice in cui si fa il test sul valore dell’attributo “Refund“, il quale vale “no” e di conseguenza si prosegue sul ramo di destra.

A questo punto si effettua un test sull’attributo “Marital Status” e siccome vale “Married” si prende di nuovo il ramo di destra.

Siamo giunti su un nodo foglia, in cui l’etichetta di classe è “No“. Quindi il soggetto non sta cercando di evadere il fisco.

Come si costruisce un albero di decisione

Il problema è che il punto di partenza è rappresentato dai dati del training set, quindi da questi bisogna riuscire a trovare un criterio che riesca a ricavare/indurre un albero “buono”. Il che non è proprio immediato perché è possibile fare tantissimi alberi a partire da un training set. Ad esempio, rispetto a quello proposto si potrebbe decidere di usare come primo attributo di test (radice) Marital Status e poi dividere per Refund ed infine per Taxable Income. L’esempio del nuovo albero è riportato in figura:

Provare tutto lo spazio di soluzioni, in genere è una soluzione computazionalmente non fattibile a meno che il data set non sia davvero piccolo.
Allora come si fa?
Esistono diversi algoritmi per indurre un albero dal training set:

• Hunt’s Algorithm
• CART
• ID3, C4.5
• SLIQ,SPRINT

Ad esempio l’algoritmo di Hunt (è il più semplice) lavora con una strategia greedy poiché sceglie l’attributo che localmente in quel nodo mi crea delle partizioni più pure in base alla porzione di training set rimasta. Con partizioni pure si intendono le partizioni che contengono tutti record della stessa classe.
Solo sul nodo radice sceglie l’attributo migliore rispetto a quelli che ha a disposizione. Praticamente prende il training set ed iterativamente lo partiziona costruendo l’albero.

Rimane ancora il problema di capire quando un nodo è puro. Per questo scopo sono stati introdotti degli indici di impurità:

• GINI INDEX
• ENTROPIA
• ERRORE DI CLASSIFICAZIONE

Vantaggi Alberi di Decisione

• Sono facili da costruire.
• La classificazione è veloce
• Il modello generato è interpretaile
• L’accuratezza è buona se il data set non è troppo complesso

Svantagi Alberi di Decisione

Possono soffrire del fenomeno dell’overfitting che si verifica quando si creano alberi molto complessi (profondi) che cercano di separare il più possibile elementi di classi differenti. Il classificatore diventa troppo specializzato, è necessario semplificare l’albero con delle tecniche di pre-pruning o post-pruning.

Weka: Waikato Environment for Knowledge Analysis

WEKA è un ambiente software interamente scritto in Java. Un semplice metodo per utilizzare questo software consiste nell’applicare dei metodi di apprendimento automatici (learning methods) ad un set di dati (dataset), e analizzarne il risultato. È possibile attraverso questi metodi, avere quindi una previsione dei nuovi comportamenti dei dati.

Con WEKA potete utilizzare algoritmi di data mining e machine learning realizzati in java:

• Preprocessing
• Classificazione – tramite Albero di decisione J48
• Clustering
• Regole di associazione

Gli algoritmi possono essere eseguiti:

• Tramite linea di comando
• Tramite GUI
• Tramite chiamate all’interno di codice java

Sito del progetto: http://www.cs.waikato.ac.nz/ml/weka/