La costruzione di un albero di classificazione avviene attraverso un procedimento ricorsivo, che si basa su euristiche o misure statistiche, per determinare l’attributo da inserire in un nodo.
Algorithm Create_decision _tree
/* Genera un albero di decisione da un dato training set */
Input : samples, attribute_list;
/* Rappresentano rispettivamente il training set e la lista di attributi significativi su cui costruire l’albero. Per semplicità di esposizione dell’algoritmo, si suppone che tutti i sample siano rappresentati da attributi a valori discreti */
Output : decision tree;
1. crea un nodo N;
2. if sanples sono tutti nella stessa classe C then 3. return N come foglia etichettata con la classe C; 4. if attribute_list è vuoto then
5. return N come foglia etichettata con la classe più comune in samples; 6. seleziona test_attribute da attribute_list; // si sceglie quello con
information gain maggiore
7. etichetta il nodo N con test_attribute;
8. foreach valore conosciuto ai di test_attribute
9. costruisci un arco dal nodo N per la condizione test_attribute = ai; 10. si = insieme delle tuple in samples che soddisfano la condizione
test_attribute = ai; 11. if si è vuoto then
12. attacca un foglia etichettata con la classe più comune in samples; 13. else
14. attacca il nodo ritornato da Create_decision _tree(si,
attribute_list – test _attribute);
Riassumendo, per la costruzione di un albero di classificazione (o di decisione), sono quindi necessarie due fasi :
1. Tree induction (Fase di costruzione) 2. Tree pruning (Fase di potatura) Vediamole in dettaglio.
Tree induction
L’algoritmo base per la costruzione di un albero di classificazione è un algoritmo di tipo greedy che attraverso un approccio top-down ed utilizzando la tecnica divide et impera, costruisce ricorsivamente il classificatore.
L’algoritmo è mostrato in figura 2.1, i suoi concetti base sono i seguenti :
• L’albero inizia con un singolo nodo rappresentante il training sample (1).
• Se i samples appartengono tutti alla stessa classe, allora il nodo diviene una foglia etichettata con classe alla quale appartengono i samples (2), (3).
• In caso contrario l’algoritmo utilizza una misura basata sull’entropia,
information gain1,come euristica, al fine di selezionare l’attributo che meglio
separerà i samples in classi individuali (6). Tale attributo diviene il
decision_attribute o test_attribute (7). Per semplicità di esposizione si
suppone che tutti i sample siano rappresentati da attributi a valori discreti.
• Viene creato un arco per ogni valore conosciuto del test_attribute, e l’insieme dei samples viene partizionato di conseguenza (8),(9),(10).
1
La misura dell’information gain è utilizzata per selezionare un test attribute ad ogni nodo dell’albero. Tale misura viene generalmente indicata con il nome di misura di selezione attributo o
misura della bontà dello split. L’attributo con infomation più alto (o maggiore riduzione di entropia)
viene scelto come test attribute per il nodo attuale. Questo attributo minimizza l’informazione necessaria per classificare i sample nelle partizioni risultanti, e riflette la minore casualità o “impurità” in queste partizioni .
Questo tipo di approccio teorico all’informazione minimizza il numero di test attesi necessari per classificare un oggetto, e garantisce che venga trovato un albero più semplice (ma non necessariamente il più semplice).
• L’algoritmo usa lo stesso processo ricorsivamente per formare un albero di decisione per i samples di ogni partizione. Una volta che un attributo occorre ad un nodo, non è necessario riconsiderarlo nei nodi discendenti (13).
• La ricorsione si ferma quando si verifica una delle seguenti condizioni :
Tutti i samples per un dato nodo appartengono alla stessa classe (2),(3).
Non ci sono ulteriori attributi con cui suddividere ulteriormente i
samples (4). In questo caso per assegnare una classe alla foglia
risultante si utilizza la tecnica del major voting (5), ovvero la classe che ricorre più frequentemente nei samples.
Non ci sono samples per l’arco etichettato test_attribute = a (11). i Anche in questo caso viene creata una foglia etichettata con la classe di maggioranza presente nei samples (12).
Tree pruning
Si pota l’albero costruito al passo 1, eliminando rami dovuti a rumore o fluttuazioni statistiche. I metodi di potatura, cercano di risolvere problemi di overfitting sui dati. In generale possiamo riscontrare più politiche, basate su considerazione statistiche, per attuare questa seconda fase. Le più adottate sono :
a) prepruning. Secondo questo approccio, un albero viene potato interrompendo la sua costruzione nella fase iniziale, ovvero decidendo di non dividere o partizionare ulteriormente il subset di training sample ad un dato nodo. Al momento dell’interruzione il nodo diventa foglia. Tale foglia può contenere la classe più frequente tra i subset sample o la distribuzione di probabilità di tali sample.
b) postpruning. In base a questo metodo i rami vengono tagliati da un albero adulto, ed il nodo di un albero viene potato rimuovendo i suoi rami. Un esempio di approccio postpruning è l’algoritmo “cost complexity”. In questo caso, il nodo più basso non potato diventa foglia ed è etichettato in base alla classe più frequente dei rami precedenti. Per ogni nodo “non-foglia” nell’albero, l’algoritmo calcola il tasso di errore atteso che potrebbe verificarsi se il sottoalbero del nodo venisse potato. Il tasso di errore è calcolato utilizzando i tassi di errore per ogni ramo combinato con il peso secondo la proporzione delle osservazioni su ogni ramo. Se la potatura di un nodo conduce ad un maggior tasso di errore, il sottoalbero viene mantenuto, altrimenti viene potato. Dopo aver generato un set di alberi potati progressivamente, un test set indipendente è utilizzato per stimare l’accuratezza di ogni albero. Viene preferito l’albero di classificazione che minimizza il tasso di errore atteso.
In letteratura sono presenti un gran numero di algoritmi per l’estrazione di alberi di classificazione, la maggior parte dei quali implementano una strategia di tipo top- down, ovvero partendo dalla radice. Una volta costruito il classificatore, ne valuteremo la sua qualità.