WEKA: classification

a.a. 2008/2009
Sistemi Informativi per le Decisioni LS
Classificazione con Weka
Boaretti Martini Tassinari
indice
0 – Introduzione
1 – Principi base di classificazione
2 – Il package weka.classifier
3 – Algoritmi di classificazione: J48, RepTree e M5rules
4 – Classificazione con Weka.. Operativamente..
5 – Case study: Supporto alla gestione di call center
17/03/2009
Sistemi Informativi per le Decisioni
2
Boaretti Martini Tassinari
Classificazione con Weka
KDD – lo scenario
…facciamo il
giochino di “Ok
il prezzo è
giusto”…
CLASSIFICAZIONE
CLUSTERING
REGOLE ASSOCIATIVE
17/03/2009
Sistemi Informativi per le Decisioni
3
Boaretti Martini Tassinari
Classificazione con Weka
Principi base di classificazione
Obiettivo: estrarre modelli che descrivono classi di dati per:
– predire valori categorici
– predire valori continui
Processo:
1.costruzione del modello a partire da un insieme predeterminato di classi o
concetti (training set)
2.predizione delle classi per i dati del test set (validazione del modello)
3.predizione delle classi per nuovi dati
NB: Stimare l’accuratezza del classificatore
17/03/2009
Sistemi Informativi per le Decisioni
4
Boaretti Martini Tassinari
Classificazione con Weka
Il package weka.classifiers
• Contiene implementazioni degli algoritmi più comunemente
utilizzati per classificazione e predizione numerica.
• La classe più importante è Classifier, che definisce la struttura
generale di un qualsiasi schema di classificazione o
predizione;
• Contiene due metodi, buildClassifier() e classifyInstance(), che
debbono essere implementati da tutti gli algoritmi di
apprendimento,
• Ogni algoritmo di apprendimento è una sottoclasse di
Classifier e ridefinisce questi metodi.
17/03/2009
Sistemi Informativi per le Decisioni
5
Boaretti Martini Tassinari
Classificazione con Weka
Tipi di Classificazione (I)
Categoria di classificatore
Strumenti usati
Bayes
Reti bayesiane
Functions
Regressione lineare,reti neurali, SVM
Lazy
Somiglianza
Meta
Bagging, Boosting, Stacking, Regression via classification,
Classification via regression, Cost sensitive classification
Mi
Algoritmi per dati multi-istanze
Misc
Creazione di intervalli di caratteristiche e assegnazione
di punteggi alla classe in base alle caratteristiche
presenti per l’istanza (peso locale)
Trees
Alberi decisionali
Rules
Regole associative
17/03/2009
Sistemi Informativi per le Decisioni
6
Boaretti Martini Tassinari
Classificazione con Weka
Tipi di Classificazione (II)
Reti Bayesane
 Una Rete Bayesiana (Bayesian Network) rappresenta la distribuzione della probabilità
congiunta di un insieme di variabili.
La B.N. viene risolta mediante specifici algoritmi, basandosi sullo stato delle variabili osservabili e
delle probabilità a-priori rappresentate dagli archi nelle relazioni fra variabili, valutando le
probabilità a-posteriori degli stati incogniti. In questo senso le B.N. possono essere considerate
come uno strumento di investigazione e previsione.
Matematicamente, una Rete Bayesiana è
un grafo aciclico orientato in cui:
• nodi = variabili o stati;
• archi = relazioni di dipendenza statistica
tra le variabile e le distribuzioni locali di
probabilità dei nodi foglia rispetto ai valori
dei nodi padre.
Schema della relazione fra un nodo ed i padri in una generica rete bayesiana.
• La mancanza di un arco fra due nodi riflette la loro indipendenza condizionale.
• Al contrario, la presenza di un arco dal nodo Xi al nodo Xj può essere interpretata come il fatto
che Xi sia causa diretta di Xj.
17/03/2009
Sistemi Informativi per le Decisioni
7
Boaretti Martini Tassinari
Classificazione con Weka
Tipi di Classificazione (III)
Rete Neurale
INPUT
17/03/2009
Sistemi Informativi per le Decisioni
In ogni nodo
intermedio il dato di
input viene
rielaborato secondo
determinate
funzioni, fino ad
ottenere l’output.
NODI INTERMEDI
OUTPUT
8
Boaretti Martini Tassinari
Classificazione con Weka
Tipi di Classificazione (IV)
Lazy
somiglianza
• Instance-based= classifica l’istanza comparandola ad un
database di esempi preclassificati.
• Idea di base= istanze simili avranno classificazione simile
• Problema= come definire “istanze simili” e “classificazioni
simili”???
• Alcuni algoritmi:
 Nearest neighbour (il più semplice)
 IB1, IB2 ecc (continui miglioramenti del precedente)
 K* (entropia come misura di distanza)
17/03/2009
Sistemi Informativi per le Decisioni
9
Boaretti Martini Tassinari
Classificazione con Weka
Tipi di Classificazione (V)
Meta
=metodo euristico per la risoluzione di una classe di problemi di calcolo mediante la combinazione di dati-utente e una
procedura black-box - di solito l'euristica stessa - nella speranza di ottenere una più efficiente o più robusta
procedura. Il nome unisce il prefisso greco "meta" ( "oltre", qui nel senso di "livello superiore") e "euristico" (da
ευρισκειν, heuriskein, "per trovare").
Esempi:
•
Bootstrap aggregation (bagging) è un meta-algoritmo per migliorare l'apprendimento automatico di classificazione
e modelli di regressione in termini di stabilità e precisione di classificazione. Si riduce anche la varianza e
contribuisce a evitare overfitting. Anche se di solito è applicato a modelli di albero di decisione, esso può essere
utilizzato con qualsiasi tipo di modello.
Dato un training set D di dimensione n, bagging genera m Di nuovi insiemi di dimensione n' ≤ n, con istanze di
campionamento da D in modo uniforme e con la sostituzione. Con il campionamento con la sostituzione, è
probabile che alcune istanze saranno ripetute in ogni Di. Se n' = n, allora per n grande il set Di dovrebbe avere il
63,2% di esempi unici di D, il resto sono doppioni.
Il risultato è detto campione di bootstrap. Gli m modelli sono adattati con gli m campioni di bootstrap e combinati con
una media di uscita (per regressione) o in fase di voto (per la classificazione).
•
Boosting è un algoritmo di machine learning per l'esecuzione di algoritmi di apprendimento supervisionato. Si
basa sulla questione posta da Kearns: può una serie di weak learners creare un unico strong learner? Un weak
learner è definito come un classificatore che è solo di poco correlato con la vera classificazione. Al contrario, un
strong learner è un classificatore che arbitrariamente è ben correlato con la vera classificazione.
La maggior parte degli algoritmi di boosting consiste nel potenziare iterativamente i classificatori deboli nei
confronti di una distribuzione e aggiungerli ad un classificatore forte finale. Quando vengono aggiunti sono
tipicamente ponderati in qualche modo, che è di solito legato alla precisione del weak learner stesso. Dopo che un
weak learner è aggiunto, i dati vengono nuovamente pesati: istanze classificate male guadagno di peso, quelle
classificate correttamente perdono peso. Pertanto, i futuri weak learners si concentrano maggiormente sulle
istanze che i precedenti weak learners classificavano erroneamente.
17/03/2009
Sistemi Informativi per le Decisioni
10
Boaretti Martini Tassinari
Classificazione con Weka
Tipi di Classificazione (VI)
Multi - Istanze
È una tecnica di classificazione supervisionata caratterizzata da:
-Multi istanze
-Una sola class label osservabile per tutte le istanze
Formato dei dati:
 bag-id - attributo nominale; unico identificatore per ogni bag
 bag - attributo relazionale; contiene le istanze
 class - class label
Esempio:
Nell’esempio che segue, gli attributi f1 - f166 sono raccolti all’interno di un unico
attributo, quello relazionale
17/03/2009
Sistemi Informativi per le Decisioni
11
Boaretti Martini Tassinari
Classificazione con Weka
FORMATO “TRADIZIONALE”
FORMATO MULTI-ISTANZA
attributo relazionale
Classificazione con weka (I)
1. Selezionare il Classificatore e
impostare le opzioni “principali”
es. Choose>Classifier>tree>j48;
Tastosinistro:Options:
binarySplits>true; confidenceFactor=0,25..
2. Test Options
a) Training set: il classificatore è valutato in base alla correttezza della
predizione effettuata sulle istanze usate per produrre il modello;
b) Test set supplementare: il classificatore è valutato grazie a un
test set supplementare appositamente caricato da file;
c) Cross-validation: i record vengono suddifisi in un certo numero di
folds (inserito tramite il campo Folds). Ogni fold “a turno” funge da test
set (la parte restante dei dati fa il train) e infine si calcola il mean square
error
d) Percentage split: il classificatore è valutato in base alla correttezza
della predizione effettuata su una % di dati tenuti da parte
appositamente per il testing. La % desiderata è inserita tramite il campo
Percentage Split.
NB: sarebbe utile in fase di preprocessign andare ad applicare il filtro
“randomize” per “mescolare” l’ordine delle tuple.
Altre opzioni possono essere selezionate tramite il tasto More options
17/03/2009
Sistemi Informativi per le Decisioni
13
Boaretti Martini Tassinari
Classificazione con Weka
Classificazione con weka (II)
3. Selezionare la Class Attribute
Abbiamo diversi tipi di classificatori in Weka: alcuni
possono predire soltanto attributi Categorici, altri
predicono soltanto attributi Numerici (Regression
Tree), alcuni riescono a predire entrambe le
tipologie di dati. Di default come Class Attribute
(ovvero l’attributo oggetto della predizione) viene
preso l’ultimo attributo presente nella base dati.
Tuttavia è possibile selezionarne uno diverso dalla
lista apribile sotto la Test Option.
4. Prova del classificatore - Start
17/03/2009
Sistemi Informativi per le Decisioni
14
Boaretti Martini Tassinari
Classificazione con Weka
Classificazione con weka (III)
5. Output classificatore
a) Run information: il programma di apprendimento
opzioni, nome della relazione, n°istanze, attributi e le
modalità di prova che sono stati coinvolti nel processo.
b) Classifier model (full training set): Il testo del modello di
classificazione che è stato prodotto sull’intero training
set.
c) I risultati della scelta sulle Test Options sono così ripartiti:
c.1 Summary. un elenco di statistiche che riassume come
il classificatore è stato in grado di predire la classe delle
istanze del Test set
c.2. Detailed Accuracy By Class: informazioni dettagliate
sulla precisione ci ogni classe di predizione
c.3. Confusion Matrix: mostra il numero di casi che sono
stati assegnati a ciascuna classe. In particolare sulla
diagonale si indivuano i valori classificati correttamente,
vicerversa nelle restanti celle si individuano gli errori di
predizione.
c.4. Source code: codice sorgente (opzionale tramite
More Options).
17/03/2009
Sistemi Informativi per le Decisioni
15
Boaretti Martini Tassinari
Classificazione con Weka
Classificazione con weka (IV)
6. Lista dei Risultati – Result List
In tale lista (in basso a sinistra) sono disponibili i risultati
ottenuti coi diversi classificatori provati. Ogni voce della lista
permette di:
a) Visualizzare la Classifier Output
b) Eliminare il risultato prodotto (canc)
c) Effettuare una delle seguenti operazioni disponibili
cliccando il pulsante destro del mouse:
View in main/separate window
Save result buffer
Save/Load model
Re-evaluate model on current test set.
Visualize classifier errors
Visualize tree or Visualize graph
Visualize margin curve
Visualize threshold curve
Visualize cost curve
Plugins
17/03/2009
Sistemi Informativi per le Decisioni
16
Boaretti Martini Tassinari
Classificazione con Weka
J48 (I)
Class for generating a pruned or unpruned C4.5 decision tree
Il classificatore J48 è un discendente del C4.5 classifier, il quale si basa sul seguente
algoritmo:
1. si utilizza un sottoinsieme del dataset (chiamato “finestra") scelto casualmente
come training set;
2. si utilizza la finestra corrente per la costruzione di un albero di decisione con
tecniche che fanno uso della teoria dell'informazione;
3. si verifica l'errore di classicazione dell'albero costruito sui dati rimanenti (test set);
4. si incrementa la dimensione della finestra aggiungendo dei pattern che sono stati
classificati erroneamente, fino a un numero massimo stabilito;
5. si ripetono iterativamente i passi 2, 3 e 4 fino a quando si ottiene un albero che
classifica correttamente tutti i pattern del training set, oppure quando il tasso
d'errore dell'ultimo albero costruito risulta maggiore a o uguale a quello dell'albero
precedente;
6. si può poi effettuare un'operazione di pruning sull'albero di decisione ottenuto.
17/03/2009
Sistemi Informativi per le Decisioni
17
Boaretti Martini Tassinari
Classificazione con Weka
J48 (II)
ID3 (l’algoritmo base del C4.5) usa l’Information Gain per ordinare gli attributi sui quali costruire
l’albero:
dove
freq(Ci,S) è la frequenza della classe Ci nel set S
Ti rappresenta un subset del set T (assumendo di splittare su X)
L’approccio è di scegliere per lo split l’attributo X col massimo Gain.
Questo criterio può essere migliorato perché produce una forte distorsione a favore delle prove
che hanno molti risultati. Così C4.5 cerca di normalizzare questo fenomeno nel seguente modo:
Gain-ration(X) = Gain(X)/ Split-info(X)
Quando l’albero è costruito e non è possibile farlo crescere ulteriormente inizia la fase di
“potatura”:
Pruning: consiste nel sostituire con un nodo foglia un sottoalbero. La sostituzione è opportuna
quando il tasso di errore previsto nel subtree è maggiore rispetto a quello della singola foglia. Per
fare Pruning si utilizza il confidenceFactor
17/03/2009
Sistemi Informativi per le Decisioni
18
Boaretti Martini Tassinari
Classificazione con Weka
J48 (III)
OPTIONS
• binarySplits : da la possibilità di fare split categorici.
• confidenceFactor : è usato per il pruning: serve per decidere se tagliare o meno un
determinato sottoalbero; a valori maggiori del condence-factor corrisponde un
albero più complesso;
• Debug : se vero, il classificatore può dare informazioni addizionali in console.
• minNumObj : il numero minimo di istanze per foglia.
• numFolds : determina la quantità di dati usati per ridurre l’errore dovuto al
pruning. Una partizione (fold) è usata per il pruning, il resto per sviluppare l’albero.
• reducedErrorPruning : se tale campo viene settato, si effettua un reduced-error
pruning invece del pruning di default C.4.5 pruning.
• saveInstanceData : per salvare il training set per la visualizzazione.
• Seed : il seme usato per mescolare i dati quando il “reduced-error pruning” viene
settato.
• subtreeRaising : serve per “raccogliere” il sottoalbero che è stato potato.
• unpruned :se non si vuole “potare”.
• useLaplace : attenuazione basata su Laplace
17/03/2009
Sistemi Informativi per le Decisioni
19
Boaretti Martini Tassinari
Classificazione con Weka
REPtree
Fast decision tree learner
Costruisce un decision o regression tree usando l’information gain (o variance) e pota i rami
usando un reduced-error pruning. Genera solo valori per attibuti numerici. I valori mancanti
sono trattati dalla suddivisione in pezzi delle corrispondenti istanze.
OPTIONS
• Debug
• maxDepth : la massima profondità di albero (-1 per nessuna restrizione).
• minNum : il minimo peso totale di peso delle istanze in una foglia.
• minVarianceProp : la minima proporzione della varianza su tutti i dati che ha bisogno di
essere presente in un nodo, al fine di poter effettuare lo split negli alberi di regressione.
• noPruning : per effettuare o no potature.
• numFolds : Determina la quantità di dati usati per il pruning. (Solo una partizione di dati è
usata per fare pruning, il resto dei dati vengono usati per ricavare le regole.)
• seed : Il seme utilizzato per “randomizzare” i dati.
17/03/2009
Sistemi Informativi per le Decisioni
20
Boaretti Martini Tassinari
Classificazione con Weka
M5rules (I)
•
•
•
•
•
Questo motodo permette di generare Regole associative da Alberi di decisione.
Un tree learner è applicato interamente al training dataset in modo da sviluppare
un albero con potature (pruned).
Successivamente si va alla ricerca della miglior foglia tramite le regole ai nodi, in
modo da poter scartare le parti di albero non selezionate dal dato. Tutte le istanze
corrispondenti alla regola sono rimosse dal dataset. Il processo è applicato
ricorsivamente alle istanze rimanenti e termina quando tutte le istanze sono
scoperte da una o più regole.
L’approccio sul quale si basa M5rules è di costruire un modello di sottoalbero da
ogni nodo e trovare la miglior foglia della regola.
Costruire alberi parziali permette di migliorare l’efficienza computazionale, allo
stesso modo non si va ad intaccare l’accuratezza e il peso delle regole.
17/03/2009
Sistemi Informativi per le Decisioni
21
Boaretti Martini Tassinari
Classificazione con Weka
M5rules (II)
OPTIONS
•
•
•
•
•
buildRegressionTree : se si vuole generare delle regression tree/rule invece di un
semplice model tree/rule.
debug : se vero, il classificatore può dare informazioni addizionali in console.
minNumInstances : il minimo numero di istanze da consentire a un nodo foglia.
unpruned : se devono essere generati alberi/regole non potate
useUnsmoothed : se vogliamo usare predizioni “non smorzate”.
Come si misura la bontà delle regole generate?
Accanto a ogni regola sono presenti due valori:
[coverage / % root mean square error]
• Coverage: copertura, cioè il numero di istanze che soddisfano tale regola
Dove:
•
17/03/2009
Sistemi Informativi per le Decisioni
22
Yi = actual class value for example i
yi = class value predicted by the linear model at a leaf
Nr = the number of examples covered by a leaf
Y = is the mean class value
N = is the total number of examples
Boaretti Martini Tassinari
Classificazione con Weka
In collaborazione con:
17/03/2009
Sistemi Informativi per le Decisioni
Boaretti Martini Tassinari
Classificazione con Weka
Obiettivo
Sviluppo di un software per la previsione, l’ottimizzazione e la simulazione al fine
del supporto alla gestione di call center e sportelli.
Problema iniziale
Studio di fattibilità per lo sviluppo di uno strumento di forecasting delle richieste, si
vuole prevedere le chiamate al call center o gli arrivi allo sportello in ogni mezzora
dell’orario di apertura.
In fase di analisi del problema è stata considerata la possibilità di predire tale
fenomeno, che risulta influenzato da molte dimensioni, con la tecnica della
classificazione quantitativa (tramite metodologie di regressione lineare).
Utilizzo di Weka come software per la creazione dell’albero di decisione
17/03/2009
Sistemi Informativi per le Decisioni
24
Boaretti Martini Tassinari
Classificazione con Weka
FASE 1
FASE 2
• Preparazione dei dati di input
• Creazione del modello di previsione (WEKA)
• Validazione del modello tramite test set
FASE 3 • Scelta del modello di classificazione più opportuno
FASE 4
FASE 5
• Sviluppo di un eseguibile per effettuare previsioni
• Forecasting di nuovi oggetti (previsione di nuove richieste)
17/03/2009
Sistemi Informativi per le Decisioni
25
Boaretti Martini Tassinari
Classificazione con Weka
Dipendenze del fenomeno
• Mese (gennaio, febbraio, ecc);
• Giorno del mese (1,2,3,ecc);
• Giorno della settimana (lunedì, martedì, ecc);
• Giorno festivo o feriale;
• Numero di fascia (orario) di arrivo;
• Numero di giorni trascorsi dall’ultima bollettazione.
Sono disponibili i dati consuntivi di un call center per i mesi di gennaio e
febbraio, questi dati vengono estratti dal database di HeraComm (GEMI) e
convertiti in un file arff, formato utilizzato da Weka per la generazione
dell’albero.
E’ stato anche creato un file csv con gli stessi dati, questo verrà utilizzato in
futuro come input per l’eseguibile di previsione.
17/03/2009
Sistemi Informativi per le Decisioni
26
Boaretti Martini Tassinari
Classificazione con Weka
17/03/2009
Sistemi Informativi per le Decisioni
27
Boaretti Martini Tassinari
Classificazione con Weka
Si è cercato di individuare:
• gli attributi che potessero evidenziare correlazioni esistenti tra i dati (es giorno della
settimana modellato come attributo categorico);
• un set di algoritmi che meglio modellassero il fenomeno delle chiamate al call center;
• i parametri che permettessero una maggiore generalità del problema.
Analisi comparativa di test set error e training set error per ogni algoritmo selezionato
in precedenza.
Selezione dell’algoritmo (e quindi del modello) con cui modellare la realtà
17/03/2009
Sistemi Informativi per le Decisioni
28
Boaretti Martini Tassinari
Classificazione con Weka
E’ stato realizzato un eseguibile (scritto in C) che permettesse di leggere in ingresso un
file csv (creato nella fase 1) contenente dei record (nuovi oggetti) rappresentanti
nuove fasce orarie per cui determinare la quantità di chiamata e ne effettuasse la
predizione.
E’ stato utilizzato l’eseguibile creato in precedenza per eseguir la predizione del mese
di marzo.
17/03/2009
Sistemi Informativi per le Decisioni
29
Boaretti Martini Tassinari
Classificazione con Weka
GENNAIO
DATO CONSUNTIVO
DATO FORECAST
450
400
350
300
250
200
150
100
50
0
-50
Media afflussi = 122,3
Mean Absolute Error = 17.23 (14,0%)
17/03/2009
Sistemi Informativi per le Decisioni
30
Boaretti Martini Tassinari
Classificazione con Weka
FEBBRAIO
DATO CONSUNTIVO
DATO FORECAST
350
300
250
200
150
100
50
0
-50
Media afflussi = 124,1
Mean Absolute Error = 19.30 (15,5%)
17/03/2009
Sistemi Informativi per le Decisioni
31
Boaretti Martini Tassinari
Classificazione con Weka
Grazie per l’attenzione!
17/03/2009
Sistemi Informativi per le Decisioni
Boaretti Martini Tassinari
33
Boaretti Martini Tassinari
Classificazione con Weka