Obiettivi
Comprendere un metodo non parametrico per problemi di classificazione e regressione che utilizza la struttura ad albero, di facile interpretazione e utilizzo a scopi decisionali.
Contenuti
Obiettivo esplorativo e obiettivo predittivo
Notazioni e definizioni
L’albero binario
Lo split e criteri di split
L’impurità in un nodo
Il criterio di split in CART e Il Criterio di split TWO-STAGE
Algoritmo FAST
Le regole di arresto
Le regole di assegnazione e decisione
La qualità della regola di decisione
Dall’albero esplorativo all’albero delle decisioni
L’albero delle decisioni in CART e Il pruning del CART
Regola di decisione con gli ensemble
Obiettivo esplorativo della segmentazione binaria
Classificare ricorsivamente un collettivo di unità statistiche o individui in due gruppi tale che siano il più possibilmente omogenei al loro interno rispetto ad una variabile target (o variabile di risposta), numerica o qualitativa, sulla base della migliore divisione dicotomica tra tutte quelle indotte dalle possibili divisioni delle modalità di ciascun predittore.
Il risultato è una struttura ad albero che consente di comprendere la gerarchia di importanza dei predittori nella spiegazione della variabile target, stabilendo per ogni percorso dell’albero, dal nodo radice ai suoi nodi terminali, le interazioni tra predittori nella definizione dei gruppi finali e della loro composizione.
Obiettivo predittivo degli alberi di decisione
Semplificare la struttura ad albero esplorativo fortemente dipendente dai dati utilizzati per la sua costruzione e non generalizzabile a nuove unità statistiche per scopi predittivi.
Il risultato è una regola di decisione o previsione per attribuire una classe (nel caso di variabile target qualitativa) o un valore numerico (nel caso di variabile numerica) ad una nuova unità statistica sulla base delle sole misurazioni di un insieme di predittori.
I dati
Siano date p variabili esplicative (predittori), numeriche e/o qualitative, ed 1 variabile dipendente (variabile target o di risposta), numerica o qualitativa, osservate su un collettivo di N individui.
Solitamente si distingue il campione di apprendimento con il quale si costruisce l’albero esplorativo dal campione test utile per identificare l’albero delle decisioni.
Y: variabile dipendente
Qualitativa C = (j = 1, …, J) classi di risposta
Quantitativa; spazio ; numeri reali
X = (X1, …, Xp): variabili esplicative o predittori
xn= [xn1, ..., xnp] T: misurazioni sull’ennesimo individuo.
Regola di classificazione/previsione:
Y Qualitativa
Partizione di X in J gruppi {A1, … AJ}, tale che per ogni x ∈ Aj
la classe prevista è j: Aj= {x; d(x) = j}
Y Quantitativa
Funzione d(x) definita su X tale che per ogni x: d(x) = y
L’insieme di split candidati
Si definisce per ogni nodo intermedio l’insieme di domande binarie, ossia l’insieme delle divisioni ammissibili, detti split, del gruppo di unità statistiche presenti nel nodo.
Ogni split di unità statistiche è generato dallo split delle modalità di un predittore in due gruppi.
L’insieme di split è il totale di possibili split generati da ciascun predittore.
Se un predittore è qualitativo con K categorie distinte non ordinabili, il numero di possibili split è pari a 2k-1 – 1.
Se un predittore è qualitativo con K categorie ordinabili oppure se è numerico con K valori distinti, il numero di possibili split è K-1.
La scelta del migliore split
Si definisce un criterio di split per suddividere le unità di un nodo intermedio in due sottoinsiemi disgiunti e internamente omogenei rispetto alla variabile di risposta.
Criteri e metodi alternativi: AID, CHAID, CART, C4.5, TWO-STAGE
Si consideri ad esempio una variabile target qualitativa a tre classi di risposta ed un predittore qualitativo con quattro modalità distinte. Nel grafico si illustra uno dei possibili split delle modalità in due gruppi (d,e) e (f,g) così da generare lo split delle (50) unità statistiche presenti nel nodo padre in due gruppi, nel nodo figlio di sinistra”left” (5+15=20) e nel nodo figlio di destra “right” (10+20=30).
Obiettivo
Generare nodi figli che siano “più puri” del nodo genitore.
Classificazione
Generare nodi figli più omogenei ossia con una proporzione minima di individui appartenenti a classi di risposta differenti.
Misura dell’impurità del nodo: Indice di eterogeneità o entropia
Regressione
Generare nodi figli con varianza della variabile dipendente minore della varianza nel nodo genitore.
Misura dell’impurità del nodo: Varianza o devianza
Classificazione ad albero
Quale misura di impurità della variabile di risposta qualitativa nel nodo (t) si considera l’indice di eterogeneità del Gini:
iY(t) = 1 – Σj p2(j|t)
che varia tra zero e (J-1)/J
L’eterogeneità è nulla quando tutte le unità statistiche si concentrano in un’unica classe di risposta, così che il gruppo di unità statistiche è perfettamente omogeneo rispetto alla variabile target.
L’eterogeneità è massima e l’indice vale (J-1)/J quando le unità statistiche si equidistribuiscono perfettamente tra le diverse classi di risposta così che non esiste una sola moda (o classe di risposta prevalente) della variabile target.
Regressione ad albero
Quale misura di impurità della variabile di risposta numerica nel nodo (t) si considera la devianza:
iY(t) = DevY(t)
Criterio di split CART (Classification and Regression Trees, di Breiman, Friedman, Olshen, Stone, 1984)
Il migliore split è scelto massimizzando il decremento di impurità che è dato dalla differenza tra l’impurità della variabile target nel nodo padre e la somma delle impurità nei nodi figli ponderate delle proporzioni di unità che ricadono nel nodo figlio di sinistra e nel nodo figlio di destra rispettivamente:
Δ i(s,t) = iY(t) – [iY(tL)p(tL) + iY(tR) p(tR)
Criterio di split TWO-STAGE (Mola, Siciliano, 1992)
Proprietà: Si dimostra che il decremento di impurità è equivalente, nel caso qualitativo (classificazione ad albero), al numeratore dell’indice di predizione tau di Goodman e Kruskal (versione non simmetrica del noto indice chi-quadrato per l’analisi della dipendenza in tabelle di contingenza), mentre, nel caso quantitativo (regressione ad albero) al numeratore del rapporto di correlazione eta quadro del Pearson.
Pertanto, si può considerare il concetto di “predizione” e gli indici tau ed eta quadro per la scelta del migliore split in luogo del decremento di impurità.
I stadio: Si seleziona il migliore predittore (o in numero ridotto, i migliori predittori, dell’ordine del 10%) massimizzando una misura globale della capacità predittiva del singolo predittore nella spiegazione della variabile target:
II stadio: Il migliore split è scelto tra i soli split generati dal migliore predittore (o dai migliori predittori) massimizzando una misura locale della capacità predittiva del singolo split del migliore predittore nella spiegazione della variabile target:
Proprietà: Si dimostra che la misura globale riferita ad un predittore non è inferiore alla misura locale riferita a tutti i suoi possibili split.
Pertanto, se la misura locale di uno split generato da un predittore X1 è superiore alla misura globale riferita ad un altro predottore X2, certamente il predittore X2 non potrà generare alcuno split migliore!
Algoritmo FAST per accelerare la procedura di ricerca del migliore split senza “provare” tutti i possibili candidati split generati da tutti i predittori.
Si applica iterativamente il criterio TWO STAGE, ossia:
STAGE I: si seleziona il migliore predittore massimizzando la misura globale di predizione
STAGE II: si seleziona il migliore split tra quelli generati dal migliore predittore massimizzando la misura locale
Si interrompe la ricerca fino a quando per il migliore split corrente la misura locale è superiore alla misura globale del predittore susseguente secondo la condizione di arresto:
Nota: L’algoritmo FAST riduce sensibilmente il costo computazionale, in termini di numero di split da provare, rispetto al CART, e il vantaggio è tanto maggiore quanto maggiore è la capacità predittiva gobale di taluni predittori.
La regola di arresto
Si definisce una regola di arresto per decidere se un nodo debba essere dichiarato terminale o meno, ossia continuare o meno la segmentazione delle unità in un nodo.
Usualmente sono tre gli approcci alternativi:
La regola di assegnazione
Si definisce una regola di assegnazione della classe o del valore numerico della variabile di risposta per le unità appartenenti in un nodo terminale.
Usualmente, si considera la classe modale per la classificazione ad albero e la media per la regressione ad albero.
L’etichetta della classe modale o del valore medio assegnata a ciascun nodo terminale, assieme ai diversi percorsi dell’albero esplorativo, consente di spiegare la interazione tra predittori nella spiegazione della variabile target.
La regola di decisione
Si definisce una regola per valutare la qualità della regola di decisione o predizione, considerando l’albero delle decisioni come regola di classificazione/predizione per nuove unità statistiche sulle quali sono note le misurazioni dei soli predittori.
Indagine sugli sbocchi occupazionali dei laureati in Economia e Commercio di Napoli (1997):
La misura della qualità della regola di decisione è fornita nei due casi distinti da:
La loro stima può essere ottenuta utilizzando i dati del campione di apprendimento con il quale si costruisce l’albero esplorativo, altresì considerando i dati di un campione test.
Stima del tasso di errata classificazione/previsione basata sul campione di apprendimento: si calcola l’errata classificazione/previsione in ciascun nodo terminale dell’albero esplorativo.
Stima del tasso di errata classificazione/previsione basata sul campione test: si calcola l’errata classificazione/previsione in ciascun nodo terminale facendo scivolare i dati del campione test nell’albero esplorativo e assegnando loro l’etichetta del nodo terminale in cui finiscono, potendo verificare l’errata classificazione/previsione delle unità facenti parte del campione test.
Stima cross-validation: si determina quale media delle stime basate su campione test, partizionando in v gruppi il collettivo di partenza, ciascun gruppo a turno è utilizzato come campione test rispetto al restante gruppo utilizzato per la costruzione dell’albero esplorativo.
L’albero esplorativo non può essere utilizzato quale regola di decisione per nuove unità statistiche di cui si conoscono le sole misurazioni dei predittori. Ciò per due motivi:
La stima del tasso di errata classificazione/previsione basata sul campione di apprendimento, al crescere del numero di nodi terminali, è una funzione decrescente, proprio perché per il suo calcolo vengono utilizzati gli stessi dati con cui si è costruito l’albero esplorativo.
La stima basata sul campione test, al crescere del numero di nodi terminali, dapprima descresce e poi cresce nuovamente, proprio perché per il suo calcolo vengono utilizzati i dati del campione test per i quali gli split delle branche terminali non discriminano a dovere le nuove unità statistiche.
Per la derivazione dell’albero delle decisioni, la metodologia CART adotta la seguente procedura:
Per il pruning del CART, si associa a ciascun nodo intermedio (t) un coefficiente costo-beneficio o rapporto tra il costo e il beneficio derivante dalla potatura della branca Tt, riducendo i nodi terminali della branca ad uno solo dato da (t).
Il costo “alfa” è rappresentato dalla differenza tra il tasso di errata classificazione/previsione del nodo (t) e il tasso di errata classificazione/previsione dei nodi terminali presenti nella branca Tt.
Il beneficio è dato dalla differenza tra il numero di nodi terminali della branca ed uno, misurando così la semplificazione ottenuta dalla potatura della branca dell’albero.
La branca debole o “weakest link” è il nodo intermedio per il quale il coefficiente costo-beneficio è minimo.
Ogni qualvolta si pota una branca i coefficienti costo-beneficio vanno ricalcolati.
Al fine di determinare stime più accurate del tasso di errata classificazione/previsione è possibile adottare procedure innovative basate su tecniche di ricampionamento statistico (processo ensemble) tali da determinare regole di decisione (e non un albero delle decisioni) a partire da una combinazione di più strutture ad albero.
Tra i vantaggi dei metodi di segmentazione, vi è la possibilità di trattare congiuntamente predittori qualitativi e quantitativi; inoltre, è possibile definire la struttura di relazione tra i predittori e la variabile target prescindendo da una forma parametrica.
I metodi di segmentazione binaria sono tra gli strumenti principali per il data mining in presenza di strutture complesse di dati e con un alto numero di unità statistiche.
Con gli “ensemble” la regola di decisione è ottenuta come combinazione di alberi delle decisioni (“weak learner“)ottenuti ricampionando i dati del campione di apprendimento.
Il bagging è un semplice bootstrap o ricampionamento delle unità statistiche del campione di apprendimento; il boosting ricampiona ad ogni iterazione in maniera da pesare in misura maggiore le unità statistiche mal predette, ottenendo un stima finale più accurata.
1. Introduzione alla statistica per le decisioni di impresa
2. L'organizzazione dei dati statistici
3. L'analisi di regressione lineare multipla
4. I test diagnostici sulla regressione lineare multipla
5. L'uso delle variabili dicotomiche nella regressione
6. Il modello di regressione logistica
7. Modelli Additivi Generalizzati
8. Modelli lineari per l'analisi delle serie storiche
9. Modelli stocastici per l'analisi delle serie storiche
10. L'analisi delle preferenze: introduzione al Multidimensional Scaling
12. Metodi di segmentazione binaria e alberi di decisione
13. Analisi delle Componenti Principali
14. Analisi delle Corrispondenze Multiple
15. Cluster Analysis
Testi consigliati:
Zani, S., Cerioli, A., Analisi dei dati e data mining per le decisioni aziendali, Giuffrè Milano, ultima edizione.
Per saperne di più:
Hastie, T., Friedman J., Tibshirani, R. (2001), “Statistical Learning: Data Mining, Inference and Prediction”, Springer.
Hand, D., Berthold, M. (2007), “Intelligent Data Analysis”, Springer.
Hand, D., Mannila, H., Smyth, P. (2001), “Principles of Data Mining”, The MIT Press.