Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Roberta Siciliano » 12.Metodi di segmentazione binaria e alberi di decisione


Obiettivi e contenuti

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 e obiettivo predittivo

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.

Notazioni e definizioni

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’albero binario


Lo split

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

Esempio di split

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).


Criteri di split

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

L’impurità in un nodo

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)

Il criterio di split in CART

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

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:

\gamma_{Y|X}(t)=\frac{\Delta_{Y|X}(t)}{i_Y(t)}=1-\sum_{h=1}^Hi_{Y|X\equiv x_h}(t)p_{X\equiv x_h}(t)\biggl / i_Y (t)

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:

\gamma_{Y|s}(t)=\frac{\Delta i_{Y|s}(t)}{i_Y(t)}=1-\left[i_{Y|s=0}(t)p_{s=0}(t_L)+i_{Y|s=1}(t)p_{s=1}(t_R)\right]\Biggl / i_y (t)

Algoritmo FAST

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:

\gamma^{(v)}_{Y|s}(t)\geq \gamma^{v+1}_{Y|X*}(t)

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.

Le regole di arresto

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:

  1. numerosità minima delle unità in un nodo, ossia si dichiara terminale un nodo se comprende meno di una percentuale prefissata di unità statistiche che formano l’intero collettivo
  2. test statistico per valutare sulla base di un campione indipendente se lo split contribuisce significativamente a generare due sottogruppi internamente omogenei ed esternamente eterogenei rispetto alla variabile target
  3. pruning, ossia si costruisce l’albero totalmente espanso, lo si pota in maniera progressiva tagliando i “rami deboli” (“weakest link“) sulla base di un coefficiente costo/beneficio opportunamente definito, così da pervenire ad una sequenza innestata di sottoalberi dai quali scegliere l’albero delle decisioni per nuove unità

Le regole di assegnazione e decisione

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.

Esempio

Indagine sugli sbocchi occupazionali dei laureati in Economia e Commercio di Napoli (1997):

  • Variabile di risposta a due classi (voto finale alla laurea alto/basso)
  • Predittori:caratteristiche socio-demografiche dei laureati, piano di studio, diploma etc.
Esempio di albero

Esempio di albero


La qualità della regola di decisione

La misura della qualità della regola di decisione è fornita nei due casi distinti da:

  • il tasso di errata classificazione, per la classificazione ad albero: si calcola come somma delle unità malclassificate in ciascun nodo terminale dell’albero divisa per il totale delle unità del collettivo
  • il tasso di errata previsione o errore quadratico medio, per la regressione ad albero: si calcola come somma delle devianze interne nei nodi terminali dell’albero divisa per il totale delle unità del collettivo

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.

Dall’albero esplorativo all’albero delle decisioni

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:

  • complessità: l’albero esplorativo solitamente comprende un numero alto di nodi terminali comportando difficoltà interpretative
  • overfitting: l’albero esplorativo è costruito utilizzando i dati del campione di apprendimento così che le branche terminali dell’albero riflettono caratteristiche particolari dei dati impiegati piuttosto che relazioni sottostanti realmente esistenti tra la variabile di risposta ed i predittori

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.

L’albero delle decisioni in CART

Per la derivazione dell’albero delle decisioni, la metodologia CART adotta la seguente procedura:

  • Si costruisce l’albero totalmente espanso, ossia l’albero esplorativo con una percentuale molto bassa di unità statistiche in ciascun nodo terminale
  • Si identifica una sequenza innestata di sottoalberi, potando a turno la branca più debole dell’albero partendo da quello totalmente espanso fino ad arrivare al nodo radice
  • Si seleziona l’albero delle decisioni tra i sottoalberi ottenuti dalla potatura dell’albero totalmente espanso, individuando l’albero per il quale la stima del tasso di errata classificazione/previsione basata su un campione test è minima oppure è compatibile con il minimo (nel senso che si potrà preferire un albero con un numero inferiore di nodi terminali il cui tasso di errata classificazione/previsione rientra in un intervallo di fiducia costruito sul valore minimo prefissando l’errore standard dalla stima)
Selezione dell’albero delle decisioni

Selezione dell'albero delle decisioni


Il pruning del CART

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.

Esempio di branca da potare

Esempio di branca da potare


Aspetti innovativi

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.

Compromesso tra più alberi delle decisioni

Compromesso tra più alberi delle decisioni


Regola di decisione con gli “ensemble”

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.

Procedura di ri-campionamento

Procedura di ri-campionamento


I materiali di supporto della lezione

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.

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion