L' albero decisionale dell'apprendimento è un metodo basato sull'uso di un albero decisionale come modello predittivo. Viene utilizzato in particolare nel data mining e nell'apprendimento automatico .
In queste strutture ad albero, le foglie rappresentano i valori della variabile di destinazione ei rami corrispondono a combinazioni di variabili di input che portano a questi valori. Nell'analisi delle decisioni, è possibile utilizzare un albero decisionale per rappresentare esplicitamente le decisioni prese ei processi che le conducono. Nell'apprendimento e nel data mining, un albero decisionale descrive i dati ma non le decisioni stesse, l'albero sarebbe utilizzato come punto di partenza per il processo decisionale.
È una tecnica di apprendimento supervisionato : utilizziamo un set di dati di cui conosciamo il valore della variabile target per costruire l'albero (i cosiddetti dati etichettati), quindi estrapoliamo i risultati al set di dati di test. Gli alberi decisionali sono tra gli algoritmi più popolari nell'apprendimento automatico .
L'apprendimento dell'albero decisionale è un metodo classico nell'apprendimento automatico . Il suo scopo è creare un modello che preveda il valore di una variabile di destinazione dal valore di diverse variabili di input.
Una delle variabili di input viene selezionata in ogni nodo interno (o nodo interno che non è terminale) dell'albero secondo un metodo che dipende dall'algoritmo e che verrà discusso in seguito. Ciascun bordo di un nodo figlio corrisponde a un insieme di valori di una variabile di input, in modo che l'insieme di bordi dei nodi figlio copra tutti i valori possibili della variabile di input.
Ciascuna foglia (o nodo terminale dell'albero) rappresenta un valore della variabile obiettivo o una distribuzione di probabilità dei vari valori possibili della variabile obiettivo. La combinazione dei valori delle variabili di input è rappresentata dal percorso dalla radice alla foglia.
L'albero è generalmente costruito separando l'insieme di dati in sottoinsiemi in base al valore di una caratteristica di input. Questo processo viene ripetuto su ogni sottoinsieme ottenuto ricorsivamente, quindi è un partizionamento ricorsivo.
La ricorsione viene completata in un nodo quando tutti i sottoinsiemi hanno lo stesso valore della caratteristica di destinazione o quando la separazione non migliora più la previsione. Questo processo è chiamato top-down induction of decision tree (TDIDT), è un algoritmo avido poiché cerchiamo in ogni nodo dell'albero la condivisione ottimale, al fine di ottenere la migliore condivisione possibile sull'intero albero decisionale. Questa è la strategia più comune per apprendere gli alberi decisionali dai dati.
Nel data mining, gli alberi decisionali possono aiutare nella descrizione, categorizzazione o generalizzazione di un set di dati fisso.
Il set di formazione viene solitamente fornito sotto forma di record del tipo:
La variabile designa la variabile obiettivo che si cerca di prevedere, classificare o generalizzare. Il vettore è costituito da variabili di input, ecc. che vengono utilizzati per questo scopo.
Esistono due tipi principali di alberi decisionali nel data mining:
Il termine Classification and Regression Tree Analysis ( CART , dopo l'acronimo) è un termine generico che si riferisce alle procedure precedentemente descritte e introdotte da Breiman et al .. Gli alberi utilizzati nel caso di regressione e nel caso di classificazione presentano somiglianze ma anche differenze, soprattutto per quanto riguarda la procedura utilizzata per determinare le separazioni dei rami.
L'apprendimento dell'albero decisionale consiste nella costruzione di un albero da un set di apprendimento composto da tuple etichettate. Un albero decisionale può essere descritto come un diagramma di flusso di dati (o diagramma di flusso ) in cui ogni nodo interno descrive un test su una variabile di apprendimento, ogni ramo rappresenta un risultato del test e ogni foglia contiene il valore della variabile di destinazione (un tag di classe per alberi di classificazione, un valore numerico per alberi di regressione).
Solitamente, gli algoritmi per la costruzione degli alberi decisionali vengono costruiti dividendo l'albero dall'alto alle foglie scegliendo ad ogni passo una variabile di input che consenta la migliore condivisione dell'insieme di oggetti, come descritto in precedenza. Per scegliere la variabile di separazione su un nodo, gli algoritmi testano le diverse possibili variabili di input e selezionano quella che massimizza un dato criterio.
Caso di alberi di classificazioneNel caso degli alberi di classificazione, questo è un problema di classificazione automatica . Il criterio di valutazione della partizione caratterizza l'omogeneità (o il guadagno in omogeneità) dei sottoinsiemi ottenuti per divisione dell'insieme. Queste metriche vengono applicate a ciascun sottoinsieme candidato ei risultati vengono combinati (ad esempio, mediati) per produrre una misura della qualità della separazione.
Esiste un gran numero di tali criteri, i più utilizzati sono l'entropia di Shannon , l'indice di diversità di Gini e le loro varianti.
Caso di alberi di regressione
Nel caso degli alberi di regressione , può essere applicato lo stesso schema di separazione, ma invece di ridurre al minimo il tasso di errore di classificazione, cerchiamo di massimizzare la varianza interclasse (per avere sottoinsiemi i cui valori della variabile-obiettivo sono ampiamente dispersi possibile). In generale, il criterio utilizza il test del chi quadrato .
OsservazioniAlcuni criteri consentono di tenere conto del fatto che la variabile-obiettivo assume valori ordinati, utilizzando misure appropriate o euristiche.
Ogni insieme di valori della variabile di segmentazione produce un nodo figlio. Gli algoritmi di apprendimento possono differire in base al numero di nodi figli prodotti: alcuni (come CART ) producono sistematicamente alberi binari, e quindi cercano la partizione binaria che ottimizza il criterio di segmentazione. Altri (come CHAID ) cercano di creare i raggruppamenti più rilevanti in base a criteri statistici. A seconda della tecnica, otterremo alberi più o meno larghi. Affinché il metodo sia efficace, è necessario prestare attenzione a non suddividere eccessivamente i dati in modo da non produrre gruppi di personale troppo piccoli, che non corrispondono a nessuna realtà statistica.
Nel caso di variabili di segmentazione continua, il criterio di segmentazione scelto deve essere adeguato. In generale, i dati vengono ordinati in base alla variabile da elaborare, quindi vengono testati i diversi punti di cut-off possibili valutando il criterio per ogni caso, il punto di cut-off ottimale sarà quello che massimizza il criterio di segmentazione.
Non è sempre desiderabile in pratica costruire un albero le cui foglie corrispondano a sottoinsiemi perfettamente omogenei dal punto di vista della variabile obiettivo. La formazione, infatti, viene svolta su un campione che si spera sia rappresentativo di una popolazione. La sfida di qualsiasi tecnica di apprendimento è riuscire a catturare informazioni utili sulla struttura statistica della popolazione, escludendo le caratteristiche specifiche del set di dati studiato. Più complesso è il modello (più grande è l'albero, più rami ha, più foglie ha), più si corre il rischio di vedere questo modello non estrapolabile a nuovi dati, vale a dire per dare un conto della realtà che si cerca di apprendere.
In particolare, nel caso estremo in cui l'albero ha tante foglie quanti sono gli individui nella popolazione (di record nel dataset), l'albero quindi non commette errori su questo campione poiché sposa tutte le sue caratteristiche, ma non può essere generalizzato a un altro campione. Questo problema, chiamato sovrallenamento o overshooting ( overfitting ), è un argomento classico dell'apprendimento automatico e del data mining.
Cerchiamo quindi di costruire un albero che sia il più piccolo possibile garantendo al contempo le migliori prestazioni possibili. Seguendo il principio della parsimonia , più piccolo è un albero, più stabile sarà nelle sue previsioni future. È necessario fare un trade-off tra prestazioni e complessità nei modelli utilizzati. Per prestazioni comparabili, preferiremo sempre il modello più semplice, se vogliamo essere in grado di utilizzare questo modello su nuovi campioni.
Il problema dell'overfitting dei modelliPer eseguire l'arbitrato performance / complessità dei modelli utilizzati, le prestazioni di uno o più modelli vengono valutate sui dati utilizzati per la sua costruzione (il / i campione / i di addestramento), ma anche su uno (o più) campioni di validazione : dati etichettati disponibili ma che si decide volontariamente di non utilizzare nella costruzione dei modelli.
Questi dati sono trattati come i dati di test, la stabilità delle prestazioni dei modelli su queste due tipologie di campione consentirà di giudicare il suo overfitting e quindi la sua capacità di essere utilizzato con un rischio controllato di errore in condizioni reali dove i dati non è noto in anticipo.
Nel grafico a fianco si osserva l'evoluzione dell'errore di aggiustamento di un albero decisionale in funzione del numero di foglie dell'albero (che qui misura la complessità). Notiamo che se l'errore diminuisce costantemente sul campione di apprendimento, da un certo livello di complessità, il modello si allontana dalla realtà, una realtà che cerchiamo di stimare sul campione di validazione (indicato come campione di prova nel grafico) .
Nel caso degli alberi decisionali, sono stati considerati diversi tipi di soluzioni algoritmiche per cercare di evitare il più possibile l'apprendimento eccessivo dei modelli: le tecniche di pre o post potatura degli alberi.
Alcune teorie statistiche cercano di trovare l'ottimo tra l'errore commesso sul campione di allenamento e quello fatto sul campione di prova. La teoria della minimizzazione del rischio strutturato di Vapnik-Chervonenkis (o SRM), utilizza una variabile chiamata dimensione VC, per determinare l'ottimo di un modello. Può quindi essere utilizzato per generare modelli che assicurino il miglior compromesso tra qualità e robustezza del modello.
Queste soluzioni algoritmiche sono complementari alle analisi comparative di prestazioni e stabilità effettuate sui campioni di addestramento e validazione.
Pre-potaturaLa prima strategia che può essere utilizzata per evitare alberi decisionali eccessivi consiste nel proporre criteri di arresto durante la fase di espansione. Questo è il principio della pre-potatura. Quando il gruppo è di dimensioni troppo piccole, o quando l'omogeneità di un sottoinsieme ha raggiunto un livello sufficiente, si ritiene che non sia più necessario separare il campione. Un altro criterio spesso riscontrato in questo contesto è l'utilizzo di un test statistico per valutare se la segmentazione introduce un input significativo di informazioni per la previsione della variabile target.
Post-potaturaLa seconda strategia consiste nel costruire l'albero in due fasi: produciamo prima l'albero le cui foglie sono il più possibile omogenee in una fase di espansione, utilizzando una prima frazione del campione di dati (campione d 'apprendimento da non confondere con la totalità dei il campione, chiamato in inglese il crescente set per risolvere l'ambiguità), quindi l'albero viene ridotto, affidandosi ad un'altra frazione dei dati per ottimizzare le prestazioni dell'albero è la fase di post-potatura. A seconda dei casi, questa seconda parte dei dati è designata dal termine campione di convalida o campione di prova, introducendo confusione con il campione utilizzato per misurare le prestazioni del modello. Il termine campione di potatura permette di designarlo senza ambiguità, è la traduzione diretta del nome inglese di potatura set .
I dati disponibili sono spesso incompleti, nel senso che solo una parte delle variabili di input è disponibile per un record. In questo caso sono possibili diverse possibilità:
Nel caso di alberi di classificazione, la regola di assegnazione deve essere specificata nei fogli una volta che l'albero è stato costruito. Se le foglie sono omogenee, non c'è ambiguità. Se così non fosse, una semplice regola è quella di decidere la classe del foglio secondo la classe maggioritaria, quella più rappresentata.
Questa tecnica molto semplice è ottimale nel caso in cui i dati provengano da una selezione casuale non distorta nella popolazione; la matrice dei costi di errata allocazione è unitaria (simmetrica): allocando opportunamente a costo zero, e allocando erroneamente i costi 1 a prescindere dal caso. Al di fuori di questo quadro, la regola della maggioranza non è necessariamente giustificata ma è facile da usare nella pratica.
Alcune tecniche, chiamate metodi set ( tutti i metodi ), migliorano la qualità o l'affidabilità della previsione costruendo diversi alberi decisionali dai dati:
Gli alberi decisionali sono talvolta combinati tra loro o con altre tecniche di apprendimento: analisi discriminante, regressioni logistiche, regressioni lineari, reti neurali ( percettrone multistrato , rete di funzioni di base radiale ) o altre.
Vengono messe in atto procedure di aggregazione delle prestazioni dei diversi modelli utilizzati (quali le decisioni consensuali) per ottenere le massime prestazioni, controllando il livello di complessità dei modelli utilizzati.
Rispetto ad altri metodi di data mining, gli alberi decisionali presentano diversi vantaggi:
D'altra parte, presenta alcuni inconvenienti:
In un albero decisionale, tutti i percorsi dalla radice alle foglie utilizzano il connettore AND . In un grafico decisionale, possiamo anche utilizzare il connettore OR per connettere più percorsi utilizzando la lunghezza minima del messaggio (MML). In generale, i grafici decisionali producono grafici con meno foglie rispetto agli alberi decisionali.
Di algoritmi evolutivi vengono utilizzati per evitare la separazione che porta all'ottimo locale.
Si può anche campionare l'albero utilizzando i metodi MCMC in un paradigma bayesiano .
L'albero può essere costruito utilizzando un approccio dal basso verso l'alto (dal basso verso l'alto).
Esistono diversi algoritmi per la creazione di alberi decisionali, tra cui:
ID3 e CART sono stati inventati indipendentemente nei decenni 1970-1980, ma utilizzano approcci simili per apprendere gli alberi decisionali dal set di apprendimento.
Tutti questi algoritmi si distinguono per i criteri di segmentazione utilizzati, per i metodi di potatura implementati, per il modo in cui gestiscono i dati mancanti nei predittori.
Molti software di data mining offrono librerie per implementare uno o più algoritmi di apprendimento dell'albero decisionale. Ad esempio, il software Open Source R contiene diverse implementazioni di CART, come rpart, party e randomForest, il software gratuito Weka e Orange (e il suo modulo orngTree) o la libreria Python gratuita scikit-learn ; ma anche Salford Systems CART, IBM SPSS Modeler, RapidMiner, SAS Enterprise Miner, KNIME, Microsoft SQL Server [1] .