C4.5 è uno tra i più noti e utilizzati algoritmi di classificazione basati su alberi, sia per la sua relativa intuitività, sia per il buon rapporto qualità – prestazioni – costo computazionale. Come molte tecniche di Data Mining a carattere predittivo, sfrutta informazioni note e attraverso calcoli matematici e statistici fornisce una stima per i casi non ancora osservati.
Come descritto in [Q93], il processo di creazione dell’albero seguito dal C4.5 si compone di due passi principali: l’accrescimento dell’albero (growing process) e la sua potatura (pruning process).
Partendo da un training set (insieme di esempi preclassificati), sotto forma di vettori caratteristici e loro valori, C4.5 costruisce l’albero dividendo lo spazio delle alternative in sottoinsiemi sempre più piccoli in modo da soddisfare dei criteri di scelta. Il processo di costruzione, nella sua globalità, prevede la divisione dei nodi, la determinazione dei nodi terminali e l’assegnamento del valore della classe a questi nodi.
L’idea principale è quella di partizionare il training set in modo tale che possano essere ridotte di molto le informazioni necessarie per classificare un dato esempio. In breve si vuole minimizzare l’informazione necessaria (misurata in numero di attributi in un cammino) a classificare in modo corretto nuove istanze.
Formalmente, sia S il training set, |S| il numero di casi nell’insieme S e freq(Ci,S) il
numero di casi in S che fanno parte dell’i-esima classe (i=1, ...,N), l’informazione media necessaria per identificare la classe di un dato esempio è data da:
2 1 - log | | k j j j freq(C ,S) freq(C ,S) info(S) * | S | S = =
∑
Equazione 2.1- Informazione media per identificare la classe di un dato esempio
Quindi, l’informazione necessaria ed attesa, prima di dividere un insieme S in n sottoinsiemi {Si} in accordo con il risultato del test TestA, è:
A n i Test i i=1 | S | info (S)= * info(S ) | S |
∑
Equazione 2.2 - Informazione prima di dividere l’insieme
Un’altra quantità importante è il gain, che misura il guadagno in termini di informazione, che si ottiene partizionando S in accordo a TestA e si calcola come
A
A Test
gain(Test )= info(S) - info (S)
Equazione 2.2 - Information Gain
Il gain rappresenta la differenza tra l’informazione necessaria per identificare un elemento di S e l’informazione necessaria per identificare un elemento di S dopo che è stato ottenuto il valore dell’attributo A, cioè è il guadagno di informazione ottenuto grazie all’attributo A.
Gain ratio criterio, calcolato come gain ratio(Test )= gain (Test ) split info( TestA A A), esprime la proporzione di informazione generata dalla divisione che appare
vantaggiosa per la classificazione.
2 1 | | | | - log | | n i i A i S S split info(Test ) * | S | S = =
∑
Equazione 2.3 - SplitInfo, informazione generata dalla divisione di un sottoinsieme
rappresenta la potenziale informazione generata dividendo S in n sottoinsiemi. Pur utilizzando gain ratio criterion, un caso critico si ha quando si generano divisioni
near-trivial a causa della scarsità di informazioni sulla divisione. Per risolvere
questo problema, C4.5 introduce la restrizione che il valore del guadagno per un test candidato non deve essere più piccolo del valore medio del guadagno di tutti i test esaminati.
Questa nozione di guadagno viene utilizzata per allineare gli attributi e per costruire gli alberi di decisione in cui, ad ogni nodo, sia associato l'attributo con maggior guadagno fra gli attributi non ancora considerati nel percorso dalla radice fino al punto considerato.
Lo scopo di questo ordinamento è di creare degli alberi di decisione piccoli, in modo da essere in grado di classificare nuove istanze in pochi passi (classificare usando minor informazione possibile ottenendo quindi un modello più generale che possa essere utilizzato con profitto per classificare istanze che non appartengono all’insieme dei dati di training).
La figura 2.3 mostra lo pseudo-codice dell’algoritmo per la costruzione dell’albero usato dal C4.5.
FormTree(T)
1. ComputeClassFrequency(T); 2. if OneClass or FewCases
return a leaf;
create a decision node N; 3. ForEach Atribute A
ComputeGain(A);
4. N.test = AttributeWithBestGain; 5. if N.test is continuos
find Threshold;
6. ForEach T’ in the splitting of T
7. if T’ is Empty Child of N is a leaf else 8. Child of N = FormTree(T’); 9. ComputeErrors of N; return N
Figura 2.3 - Pseudo-codice dell’algoritmo per la costruzione dell’albero usato dal C4.5
Sia T il training set, il numero di casi in T che fanno parte dell’i-esima classe (i=1, ...,N) ovvero freq(Ci,T) è calcolato al passo (1).
Se tutti i casi (2) in T appartengono alla stessa classe C (oppure il numero dei casi j
in T è più piccolo di un certo valore ), allora il nodo è una foglia etichettata con la classe C . L’errore di classificazione della foglia è dato dalla somma dei pesi dei j
casi in S la cui classe non è C . Se T contiene casi appartenenti a due o più classi j (3) allora si calcola l’information gain di ciascun attributo. Nel caso di attributi discreti, l’information gain è relativo allo splitting dei casi presenti in T in
sottoinsiemi con valori dell’attributo distinti. Invece nel caso di attributi di tipo continuo, l’information gain è relativo allo splitting di T in due soli sottoinsiemi, uno contenente tutti i casi il cui valore dell’attributo è minore uguale di una certa soglia (soglia locale), e l’altro contenente i casi in cui il valore dell’attributo è maggiore della soglia. Tale soglia viene calcolata durante il calcolo dell’information gain.
L’attributo il cui valore dell’information gain è più alto (4) viene selezionato come prossimo nodo. Inoltre nel caso venga selezionato come prossimo nodo un attributo di tipo continuo, viene scelto come soglia (5) il valore più grande appartenente all’attuale training set inferiore alla soglia locale.
Un nodo ha s figli se T1…..T sono i sottoinsiemi ottenuti dallo splitting tramite il s
test sull’attributo selezionato (6). Ovviamente, s = 2 quando l’attributo selezionato è di tipo continuo, e s = h per attributi di tipo discreto, dove h è il numero dei valori distinti dell’attributo selezionato.
Per i = [1..s], se T è vuoto, (7) il figlio del nodo corrente diviene una foglia, i
etichettata con la classe più frequente nel training set del nodo padre.
Se T non è vuoto, si riapplica l’intero algoritmo ma questa volta con training set i T i
(8) ( invece che T ), più tutti quei casi in T con valori dell’attributo selezionato sconosciuti.
I casi con valori dell’attributo selezionato sconosciuti vengono replicati in ciascun nodo figlio con i loro pesi uguale alla somma dei pesi dei casi in T con valori i conosciuti fratto il numero dei casi in T con valori dell’attributo selezionato conosciuti.
Infine si calcolano i possibili errori derivanti dalla classificazione (9) in ciascun nodo, come la somma degli errori dei nodi figlio.
La fase più costosa a livello computazionale è quella di costruzione dell’albero; infatti, la semplificazione e la valutazione consistono semplicemente nell’attraversare l’albero e, rispettivamente, controllare le condizioni di pruning o predire la classe per una data istanza.
Eccetto che per piccoli training set, il tempo necessario per la semplificazione e valutazione è una piccola frazione del tempo totale di classificazione, per cui verrà considerato il tempo di costruzione.
La costruzione di un singolo nodo richiede in media i seguenti passi:
|T| per calcolare la frequenza della classe;
nd*|T| per calcolare l’information gain ratio per attributi discreti;
nc*(log|T|+1) per ordinare i casi in T e per calcolare il guadagno gainv e
l’information gain ratio;
p*|TS|/2 per cercare la soglia nell’intero training set partendo dalla soglia locale.
(s+1)*T per caricare i casi in memoria per il calcolo dei sottoinsiemi associati ai nodi figli.
dove:
• |T| è la cardinalità di T;
• nc è il numero di attributi continui;
• nd è il numero di attributi discreti non ancora selezionati come nodi
antecedenti;
• s il numero di insiemi di splitting;
• p la probabilità che un nodo selezionato sia continuo.
Questo porta al seguente numero di passi: * log |
(
| 1)
* | |(
2)
2* | | c d TS n T p s n T + + + + + .Facendo una stima anche della memoria necessaria a contenere le informazioni, si ha che l’algoritmo richiede |TS|*(na+5) parole di memoria, dove na è il numero di
attributi. A questo va aggiunta anche la memoria necessaria per memorizzare l’albero di decisione e le strutture dati ausiliarie [Rug00].
Nei prossimi paragrafi vedremo alcune tra le più note implementazioni del C4.5.