Massimo Aria » 14.Alberi di Classificazione

Gli alberi di classificazione

Gli alberi di classificazione (o di segmentazione) rappresentano una metodologia che ha l’obiettivo di ottenere una segmentazione gerarchica di un insieme di unità statistiche mediante l’individuazione di “regole” (o “percorsi”) che sfruttano la relazione esistente tra una classe di appartenenza e le variabili rilevate per ciascuna unità.

Essi vengono utilizzati per individuare l’appartenenza di unità statistiche alle classi di una variabile dipendente conoscendo i valori o le modalità di una o più variabili esplicative (albero esplorativo).
La regola individuata viene successivamente impiegata per classificare nuove unità statistiche di cui si ignora la categoria di appartenenza (albero decisionale).

Idea chiave della segmentazione

L’idea di base dalla segmentazione binaria è quella di partizionare ricorsivamente un insieme di unità statistiche in gruppi sempre più fini, cioè di numerosità inferiore, e sempre più omogenei internamente (rispetto alla distribuzione della variabile risposta).

Si determina in tal modo una partizione finale del gruppo iniziale presente al nodo radice in sottogruppi disgiunti ed esaustivi rappresentati dai nodi terminali dell’albero.
Per definizione infatti i nodi terminali rappresenteranno un grado di omogeneità interna maggiore rispetto al gruppo di partenza.
Il ruolo di generatore delle possibili partizioni, o split, viene assunto dai predittori, i quali caratterizzano il passaggio delle unità statistiche da un nodo ai suoi discendenti.

Alberi esplorativi e decisionali

La segmentazione può essere d’ausilio per soddisfare due obiettivi:

1. esplorativo, finalizzato principalmente alla individuazione e descrizione delle relazioni esistenti tra le diverse variabili esplicative e l’appartenenza ad una classe piuttosto che ad un’altra della variabile di risposta.
2. decisionale, finalizzato alla costruzione di un albero che consenta di per classificare nuove unità statistiche per le quali non è nota la classe di appartenenza ma unicamente le modalità assunte per le variabili esplicative.

Differenze tra cluster analysis e segmentazione

Una struttura ad albero, output della procedura di segmentazione, a prima vista sembra presentare numerosi elementi di contatto con il dendrogramma di una cluster analysis gerarchica.

In realtà le due tecniche presentano differenze sostanziali sia negli obiettivi che nelle modalità di analisi.
La finalità della cluster è quella di accorpare le unità statistiche in gruppi o classi che sono ignote all’analista. Tale raggruppamento avviene attraverso la ricerca di gruppi in cui le osservazioni siano omogenee rispetto alle p variabili X osservate.

Diversamente, in un albero di classificazione, i gruppi a cui le unità appartengono sono già noti a priori in una variabile indicata con Y, e ciò che la metodologia vuole individuare sono le relazioni tra le p variabili esplicative X che spiegano il perché un osservazione appartenga ad una classe della Y piuttosto che ad un’altra.

Tale struttura di relazioni, una volta definita, consente anche di predire, per nuove unità statistiche, la classe di appartenenza quando questa non sia nota a priori. Questi due differenti approcci sono noti in letteratura come:

• classificazione supervisionata
  • Come nel caso degli alberi di classificazione in cui la ricerca della partizione è guidata (supervisionata) dalla conoscenza a priori della Y
• classificazione non supervisionata
  • Come nel caso della cluster analysis in cui la ricerca della partizione è effettuata unicamente sulla base della somiglianza delle unità rispetto alle caratteristiche osservate (le variabili X).

Ruolo delle variabili

Le differenze tra metodi supervisionati e non supervisionati traggono ragione dal differente ruolo giocato dalle p variabili osservate sugli n oggetti da classificare.
Un ruolo simmetrico nel clustering, un ruolo asimmetrico nella classificazione supervisionata.
Infatti in questo ultimo caso dei p caratteri misurati sugli oggetti, uno di essi gioca il ruolo di variabile discriminate o dipendente sintesi della classificazione degli oggetti nota a priori.

Obiettivo dell’analisi supervisionate è quindi spiegare come la conoscenza delle modalità assunte dalle n unità sulle restanti p-1 variabili (dette variabili esplicative) possa spiegare l’appartenenza ad uno o ad un altro dei gruppi.

Le fasi della procedura

Ogni procedura di segmentazione è caratterizzata da un certo numero di fasi che guidano la costruzione dell’albero:

• Creazione dell’insieme degli split, cioè dell’insieme dei potenziali tagli binari (ottenuti attraverso le variabili esplicative) che consentono di dividere le unità contenute in un nodo padre in due insiemi che formano i nodi figli;
• Il criterio di partizione, passaggio fondamentale consistente in un algoritmo di partizione ricorsivo che genera, a partire dal nodo radice, gruppi sempre più omogenei internamente ed eterogenei esternamente;
• La regola di arresto della procedura, essenziale per il controllo della dimensione dell’albero finale;
• L’assegnazione della risposta, che si esplica con l’assegnazione di una classe o di un valore alle unità presenti in un nodo terminale;
• La potatura dell’albero, che consente di individuare, a partire dall’albero finale, un sottoalbero ottimale che posa essere utilizzato a fini decisionali.

Tra le numerose tecniche di classificazione ad albero note in letteratura, il contributo statistico più rilevante è quello della metodologia CART (Classification and Regression Trees) proposta da Brieman e al. nel 1984.
Nel proseguo la trattazione delle diverse fasi della procedura sono descritte seguendo tale approccio.

Il criterio di partizione

Questa fase rappresenta il punto chiave di ogni procedura di segmentazione ad albero.
Essa consiste nella individuazione, tra l’insieme di tutti i possibili split generati nella fase precedente, del taglio binario “migliore” rispetto ad un dato criterio statistico.

Nella metodologia CART, il criterio statistico che guida la scelta del migliore split si basa sul concetto di decremento di impurità.

Essendo l’obiettivo della segmentazione quello di ottenere via via nodi sempre più puri, si individua tra tutti i possibili tagli, lo split ottimo come quello che massimizza la riduzione di impurità che si ottiene tagliando un nodo padre in due nodi figli.

Il decremento di impurità ad un nodo t ottenuto con uno split s, si definisce come:

Dove i_Y(t) è il grado di impurità nel nodo padre t
i_Y(t_L) è il grado di impurità nel nodo figlio di sinistra e p(t_L) è la proporzione di unità contenute nel nodo di sinistra.
i_Y(t_R) è il grado di impurità nel nodo figlio di destra e p(t_R) è la proporzione di unità contenute nel nodo di destra.

Il migliore split s* è quello che massimizza il decremento di impurità

Il criterio di partizione (segue)

L’algoritmo CART quindi, ad ogni nodo e fino a che la costruzione dell’albero non si conclude, genera l’insieme S di tutte le possibili partizioni binarie (split), calcola il decremento di impurità e determina la miglior partizione cui è associato il massimo decremento di impurità.

In sostanza, l’algoritmo CART si compone dei seguenti passi:
Passo 1. si genera l’insieme S di tutte le possibili partizioni binarie ottenute dal set di predittori X;
Passo 2. per ogni split s dell’insieme S si calcola il decremento di impurità;
Passo 3. si determina la miglior partizione a cui é associato il massimo decremento di impurità.

L’algoritmo é applicato ad ogni nodo fino a che la costruzione dell’albero non si arresta.
Il costo computazionale di questa metodologia é molto elevato. Infatti basti pensare al caso in cui i predittori impiegati sono in numero sostanzioso ed inoltre parte di essi sono in scala numerica o nominale. In questo caso il numero di split S che deve essere generato ad ogni nodo é considerevole soprattutto se si pensa che ogni volta per ognuno di esso, l’algoritmo deve calcolare il decremento di impurità per poi selezionare la migliore partizione.

Misure di impurità

La metodologia CART adotta quale misura d’impurità, per gli alberi di classificazione, l’indice H di eterogeneità di Gini.

Esso si definisce in generale come:

Dove f_j rappresenta la frequenza relativa di osservazioni la cui modalità della variabile è pari a j.

Nell’ambito della segmentazione binaria, l’impurità in un nodo sarà quindi pari a:

Dove  è la misura di impurità in un generico nodo t
e   è la proporzione di unità nel nodo t che appartengono alla j-esima classe della variabile di risposta Y.

Regole d’arresto

Le regole d’arresto della procedura rappresentano l’insieme di criteri che determinano quando un nodo debba essere dichiarato terminale e quindi non più partizionabile in ulteriori nodi figli.

Esse consistono nelle seguenti condizioni: “Un nodo t diventa terminale se”

a) La numerosità dello stesso è inferiore ad una certa soglia prefissata;
Si fissa una soglia minima per il numero di osservazioni contenute in un nodo padre o eventualmente nei nodi figli generati da questo. La regola serve ad ottenere alberi i cui nodi non siano espressione di singole o pochissime unità fornendo così percorsi poco informativi;

b) Il grado di impurità del nodo t è al di sotto di una certa soglia prefissata;
Se il nodo ha un grado di purezza elevato allora sue ulteriori partizioni non produrranno alcun miglioramento nell’accuratezza della struttura ma unicamente uno svantaggio misurato dalla crescita della complessità dell’albero.

Regole d’arresto (segue)

c) Il massimo decremento di impurità (ottenuto dal migliore split) è inferiore ad una certa soglia prefissata;
Un nodo è dichiarato “terminale” se la riduzione dell’impurità conseguibile mediante la suddivisione del nodo stesso risulta inferiore ad una soglia prefissata. In questo modo si pone un freno alla crescita di branche il cui contributo alla purezza dell’albero è praticamente nullo;

d) La complessità dell’albero ha superato una certa soglia prefissata.
Un’ulteriore regola d’arresto definisce la dimensione massima della taglia dell’albero al fine di limitarne l’espansione. La taglia può essere definita in termini di numero di nodi terminali che è anche pari al numero di suddivisioni (nodi interni) più uno, ma anche in riferimento al numero di livelli dell’albero che danno una misura della profondità della struttura.

Assegnazione della risposta e qualità della regola

Con i metodi di segmentazione si perviene ad una struttura ad albero i cui nodi terminali costituiscono una partizione del campione iniziale in gruppi “puri” al loro interno.

Nell’interpretazione dell’albero esplorativo, si seguiranno i diversi percorsi della struttura gerarchica individuando le diverse interazioni tra predittori che conducono le unità a cadere in un nodo terminale piuttosto che in un altro.
Ciascun nodo terminale sarà etichettato attribuendo la classe modale di risposta della Y tra le unità presenti nel nodo stesso.
In tal modo, si definiranno ad esempio i diversi percorsi che conducono alla stessa classe di risposta.

La qualità di una regola o percorso che porta ad un nodo terminale è valutata attraverso la misura del tasso di errata classificazione definito come la proporzione di osservazioni mal classificate in un dato nodo t.

“Le osservazioni in un nodo terminale si considerano mal classificate quando la loro classe di risposta è diversa da quella modale”.

Es. Si immagini che la Y assuma solo due modalità Y=A e Y=B.
Se in un nodo terminale vi sono 100 osservazioni (n_t=100) di cui 80 assumono la modalità A della Y e le restanti 20 la modalità B, allora la risposta modale è A, quindi il tasso di mal classificati sarà pari a: 20/100 cioè il 20%.

“La qualità di un nodo, e più in generale di un albero, sarà tanto più elevata
quanto minore sarà il tasso di osservazioni mal classificate”

Tasso di mal classificati di un albero

Il tasso di mal classificati di una struttura ad albero T si definisce come la proporzione di mal classificati dell’intero campione:

R(T)= numero di mal classificati / numero di osservazioni considerate

Ovvero sarà pari alla media ponderata dei tassi di mal classificati dell’insieme TR di nodi terminali che compongono la struttura:

Definizione dell’albero decisionale

Gli alberi esplorativi non possono essere impiegati a scopi decisionali di classificazione per nuove unità.
La procedura di segmentazione conduce infatti ad un albero accurato per il campione impiegato per la sua costruzione, nel senso che il tasso d’errore sarà tanto più basso quanto maggiore è la dimensione dell’albero; ma una dimensione molto elevata della struttura può condurre con facilità ad alti tassi di errore di classificazione per nuove unità.

Si rende pertanto necessaria una procedura di induzione dell’albero che da una parte lo semplifichi e dall’altra consideri l’accuratezza di previsione per nuove unità.

Tale procedura prende il nome di pruning (potatura).

Il pruning si prefigge l’obiettivo di individuare le branche meno rilevanti o addirittura dannose per il processo decisionale e di rimuoverle.

Il pruning

Il pruning della metodologia CART è un metodo che genera una sequenza ottimale nidificata di sottoalberi potati tra i quali ne viene selezionato uno finale quale regola di decisione per nuove unità.

Molto sinteticamente, la procedura di pruning opera nel modo seguente:
Si definisce una misura che tenga conto del trade-off tra il costo (l’aumento della impurità dell’albero) e il beneficio (semplificazione della struttura) legato alla potatura di un albero.
Tale misura alfa, detta parametro di costo complessità è calcolata ad ogni nodo interno dell’albero:

Dove al numeratore si misura la crescita di mal classificati come differenza tra il tasso al nodo t (che se potato diventerebbe terminale) e quello del ramo T_t che diparte da t. Mentre al denominatore si misura la riduzione della complessità della struttura in termini di riduzione del numero di nodi terminali.

Ad ogni passo verrà potato il ramo il cui nodo di partenza presenta l’alfa minimo dell’intera struttura ad albero.

In questo modo, ripetendo iterativamente la procedura, si otterrà una sequenza di alberi, via via più piccoli, tutti potenzialmente candidati ad essere scelti come albero decisionale. Facendo scivolare in ognuno di essi un nuovo campione di dati (il campione test) si potrà scegliere l’albero migliore come quello che minimizza il tasso di errata classificazione del campione test.

Un esempio applicativo: il credit scoring

Un classico esempio di applicazione della segmentazione binaria si ha in problemi di credit scoring, ove si supponga che una banca abbia classificato un gruppo di clienti in due classi, rispettivamente “meritevoli del prestito” e “non meritevoli” e che abbia registrato un insieme di indicatori utili a questo tipo di classificazione, come ad esempio l’età del cliente, la situazione familiare, la condizione lavorativa, la situazione economica, etc.

Il dataset esaminato proviene dall’archivio dati del software statistico SPAD 5.5.

Esso è composto da 468 unità statistiche che hanno effettuato una richiesta di concessione di credito presso una banca francese.

La variabile di risposta Y è il tipo di cliente che assume modalità “meritevole” e “non meritevole” del credito.

Le variabili esplicative (o predittori) sono 11 tutte di natura qualitativa ordinale o nominale.

La descrizione delle variabili e delle modalità assunte è riportata nella slide successiva.

L’analisi di segmentazione è effettuata attraverso l’utilizzo del software Tree Harvest (Aria e al. 2004).

Il dataset analizzato

Rappresentazione dell’albero esplorativo

Esempio del calcolo del decremento di impurità

L’albero decisionale

L’albero esplorativo ottenuto dall’analisi presenta una struttura con 34 nodi terminali.

La procedura di pruning (illustrata nella slide successiva) costruisce la sequenza di sottoalberi candidati a diventare l’albero decisionale.

Come si può vedere dal grafico il tasso di errata classificazione calcolato sul campione di apprendimento (linea blu) decresce continuamente al crescere della dimensione dell’albero, fino a raggiungere il minimo con l’albero esplorativo (albero massimamente espanso).
Al contrario il tasso di errata classificazione calcolato sui nuovi dati (linea rossa) decresce inizialmente per poi riprendere a crescere da una certa taglia dell’albero in poi. Ciò perché l’albero diventa troppo complesso e mal si adatta ad essere un classificatore generale che funziona in maniera accurata anche con nuovi dati.

L’albero decisionale si sceglie come quello che minimizza questo tasso.
Nell’esempio il migliore albero secondo tale criterio è quello con 18 nodi terminali rappresentato nell’area bassa della slide successiva.

L’albero decisionale (segue)