Alberi decisionali: come ottimizzare il mio processo decisionale?

Immaginiamo che stai giocando a una partita di Venti domande. Il tuo avversario ha segretamente scelto un argomento e devi capire cosa ha scelto. Ad ogni turno, puoi fare una domanda sì o no e il tuo avversario deve rispondere in modo veritiero. Come scopri il segreto nel minor numero di domande?

Dovrebbe essere ovvio che alcune domande sono migliori di altre. Ad esempio, chiedere "Può volare?" Poiché la tua prima domanda è probabilmente infruttuosa, mentre chiedere "È vivo?" È un po 'più utile. Intuitivamente, vuoi che ogni domanda restringa significativamente lo spazio di eventuali segreti, portando infine alla tua risposta.

Questa è l'idea di base dietro gli alberi delle decisioni. Ad ogni punto, si considera una serie di domande che possono partizionare il proprio set di dati. Scegli la domanda che fornisce la suddivisione migliore e trovi di nuovo le domande migliori per le partizioni. Ti fermi una volta che tutti i punti che stai prendendo in considerazione appartengono alla stessa classe. Quindi il compito della classificazione è facile. Puoi semplicemente afferrare un punto e buttarlo giù dall'albero. Le domande lo guideranno alla sua classe appropriata.

Termini importanti

L'albero decisionale è un tipo di algoritmo di apprendimento supervisionato che può essere utilizzato in entrambi i problemi di regressione e classificazione. Funziona con variabili di input e output sia categoriche che continue.

Identifichiamo le terminologie importanti sull'albero decisionale, guardando l'immagine sopra:

  • Il nodo radice rappresenta l'intera popolazione o campione. Si divide ulteriormente in 2 o più insiemi omogenei.
  • La divisione è un processo di divisione di un nodo in 2 o più sottonodi.
  • Quando un nodo secondario si divide in ulteriori nodi secondari, viene chiamato nodo decisionale.
  • I nodi che non si dividono si chiamano Terminal Node o Leaf.
  • Quando si rimuovono i nodi secondari di un nodo decisionale, questo processo si chiama potatura. L'opposto della potatura è la scissione.
  • Una sottosezione di un intero albero è chiamata ramo.
  • Un nodo, che è diviso in sottonodi, è chiamato nodo principale dei sottonodi; mentre i sottonodi sono chiamati figlio del nodo genitore.

Come funziona

Qui parlo solo dell'albero di classificazione, che viene utilizzato per prevedere una risposta qualitativa. L'albero di regressione è quello utilizzato per prevedere i valori quantitativi.

In un albero di classificazione, prevediamo che ogni osservazione appartiene alla classe più comune di osservazioni di addestramento nella regione a cui appartiene. Nell'interpretazione dei risultati di un albero di classificazione, siamo spesso interessati non solo alla previsione di classe corrispondente a una particolare regione di nodo terminale, ma anche alle proporzioni di classe tra le osservazioni di addestramento che cadono in quella regione. Il compito di far crescere un albero di classificazione si basa sull'utilizzo di uno di questi 3 metodi come criterio per effettuare le divisioni binarie:

1 - Tasso di errore di classificazione: possiamo definire il "tasso di successo" come la frazione delle osservazioni di allenamento in una determinata regione che non appartengono alla classe più diffusa. L'errore è dato da questa equazione:

E = 1 - argmax_ {c} (π̂ mc)

in cui π̂ mc rappresenta la frazione dei dati di allenamento nella regione R_m che appartiene alla classe c.

2 - Indice Gini: l'indice Gini è una metrica di errore alternativa progettata per mostrare quanto sia “pura” una regione. "Purezza" in questo caso indica la quantità di dati di allenamento in una determinata regione appartiene a una singola classe. Se una regione R_m contiene dati che provengono principalmente da una singola classe c, il valore dell'indice Gini sarà piccolo:

3 - Cross-Entropy: una terza alternativa, simile all'indice Gini, è nota come Cross-Entropy o Devianza:

L'entropia crociata assumerà un valore vicino allo zero se gli π̂ mc sono tutti vicini a 0 o vicino a 1. Pertanto, come l'indice Gini, l'entropia crociata assumerà un valore piccolo se il nodo m-esimo è puro. In effetti, risulta che l'indice di Gini e l'entropia incrociata sono numericamente abbastanza simili.

Quando si costruisce un albero di classificazione, l'indice Gini o l'entropia incrociata vengono in genere utilizzati per valutare la qualità di una particolare divisione, poiché sono più sensibili alla purezza del nodo rispetto al tasso di errore di classificazione. Ognuno di questi 3 approcci potrebbe essere usato durante la potatura dell'albero, ma il tasso di errore di classificazione è preferibile se l'obiettivo è l'accuratezza della previsione dell'albero potato finale.

Implementazione da zero

Esaminiamo l'algoritmo di creazione dell'albero delle decisioni, con tutti i suoi dettagli. Per costruire un albero decisionale, dobbiamo prendere una decisione iniziale sul set di dati per dettare quale funzione viene utilizzata per dividere i dati. Per determinare ciò, dobbiamo provare ogni funzione e misurare quale divisione ci darà i migliori risultati. Successivamente, suddivideremo il set di dati in sottoinsiemi. I sottoinsiemi attraverseranno quindi i rami del primo nodo decisionale. Se i dati sui rami sono della stessa classe, allora li abbiamo classificati correttamente e non è necessario continuare a dividerli. Se i dati non sono gli stessi, è necessario ripetere il processo di suddivisione su questo sottoinsieme. La decisione su come dividere questo sottoinsieme viene presa allo stesso modo del set di dati originale e ripetiamo questo processo fino a quando non abbiamo classificato tutti i dati.

Come suddividiamo il nostro set di dati? Un modo per organizzare questo disordine è misurare le informazioni. Usando la teoria dell'informazione, possiamo misurare le informazioni prima e dopo la divisione. La modifica delle informazioni prima e dopo la divisione è nota come guadagno di informazioni. Quando sappiamo come calcolare il guadagno delle informazioni, possiamo dividere i nostri dati su ogni funzione per vedere quale divisione ci fornisce il massimo guadagno di informazioni. La divisione con il più alto guadagno di informazioni è la nostra migliore opzione.

Per calcolare il guadagno di informazioni, possiamo usare l'entropia di Shannon, che è il valore atteso di tutte le informazioni di tutti i possibili valori della nostra classe. Vediamo il codice Python per questo:

Come puoi vedere, calcoliamo innanzitutto un conteggio del numero di istanze nel set di dati. Quindi creiamo un dizionario le cui chiavi sono i valori nella colonna finale. Se una chiave non è stata rilevata in precedenza, ne viene creata una. Per ogni chiave, teniamo traccia di quante volte si verifica questa etichetta. Infine, utilizziamo la frequenza di tutte le diverse etichette per calcolare la probabilità di tale etichetta. Questa probabilità viene utilizzata per calcolare l'entropia di Shannon e la sommiamo per tutte le etichette.

Dopo aver escogitato un modo per misurare l'entropia del set di dati, abbiamo bisogno di dividere il set di dati, misurare l'entropia sui set divisi e vedere se dividere fosse la cosa giusta da fare. Ecco il codice per farlo:

Questo codice richiede 3 input: i dati su cui dividere, la funzione su cui dividere e il valore della funzione da restituire. Creiamo un nuovo elenco all'inizio ogni volta perché chiameremo questa funzione più volte sullo stesso set di dati e non vogliamo che il set di dati originale venga modificato. Il nostro set di dati è un elenco di elenchi; mentre ripetiamo ogni elemento dell'elenco e se contiene il valore che stiamo cercando, lo aggiungeremo al nostro elenco appena creato. All'interno dell'istruzione if, abbiamo tagliato la funzione su cui ci siamo divisi.

Ora combineremo 2 funzioni: ShannonEntropy e splitDataset per scorrere il set di dati e abbiamo deciso quale funzione è la migliore su cui dividere.

Esaminiamo rapidamente il codice:

  • Calcoliamo l'entropia di Shannon dell'intero set di dati prima che si sia verificata una divisione e assegniamo il valore alla variabile baseEntropy.
  • Il 1 ° per loop scorre su tutte le funzionalità dei nostri dati. Usiamo la comprensione dell'elenco per creare un elenco (featList) di tutte le voci dell'i-esima nei dati o di tutti i possibili valori presenti nei dati.
  • Successivamente, creiamo un nuovo set da un elenco per ottenere i valori univoci (uniqueVals).
  • Quindi, esaminiamo tutti i valori univoci di questa funzione e suddividiamo i dati per ciascuna funzione (dati secondari). La nuova entropia viene calcolata (newEntropy) e sommata per tutti i valori univoci di quella funzione. Il guadagno di informazioni (infoGain) è la riduzione dell'entropia (baseEntropy - newEntropy).
  • Infine, confrontiamo il guadagno di informazioni tra tutte le funzionalità e restituiamo l'indice della migliore funzione su cui dividere (bestFeature).

Ora che possiamo misurare quanto è organizzato un set di dati e possiamo dividere i dati, è tempo di mettere insieme tutto questo e costruire l'albero delle decisioni. Da un set di dati, l'abbiamo diviso in base all'attributo migliore da suddividere. Una volta divisi, i dati attraverseranno i rami dell'albero verso un altro nodo. Questo nodo quindi dividerà nuovamente i dati. Useremo la ricorsione per gestire questo.

Ci fermeremo solo alle seguenti condizioni: (1) esaurire gli attributi su cui dividere o (2) tutte le istanze in un ramo appartengono alla stessa classe. Se tutte le istanze hanno la stessa classe, creeremo un nodo foglia. Tutti i dati che raggiungono questo nodo foglia sono considerati appartenenti alla classe di quel nodo foglia.

Ecco il codice per costruire i nostri alberi decisionali:

Il nostro codice accetta 2 input: i dati e un elenco di etichette:

  • Per prima cosa creiamo un elenco di tutte le etichette di classe nel set di dati e chiamiamo questo elenco di classi. La prima condizione di arresto è che se tutte le etichette di classe sono uguali, restituiamo questa etichetta. La seconda condizione di arresto è il caso in cui non ci sono più funzioni da dividere. Se non soddisfiamo le condizioni di arresto, utilizziamo la funzione selectBestFeatureToSplit per scegliere la funzione migliore.
  • Per creare l'albero, lo memorizzeremo in un dizionario (myTree). Quindi otteniamo tutti i valori univoci dal set di dati per la nostra funzione scelta (bestFeat). Il codice valore univoco utilizza set (uniqueVals).
  • Infine, ripetiamo tutti i valori univoci della nostra funzione prescelta e chiamiamo ricorsivamente createTree () per ogni divisione del set di dati. Questo valore viene inserito nel dizionario myTree, quindi finiamo con molti dizionari nidificati che rappresentano il nostro albero.

Implementazione tramite Scikit-Learn

Ora che sappiamo come implementare l'algoritmo da zero, facciamo uso di scikit-learn. In particolare, useremo la classe DecisionTreeClassifier. Lavorando con il set di dati dell'iride, importiamo prima i dati e li dividiamo in una parte di addestramento e di prova. Quindi costruiamo un modello usando l'impostazione predefinita di sviluppo completo dell'albero (facendo crescere l'albero fino a quando tutte le foglie sono pure). Risolviamo random_state nell'albero, che viene utilizzato internamente per legare:

L'esecuzione del modello dovrebbe fornire una precisione del set di test del 95%, il che significa che il modello ha previsto correttamente la classe per il 95% dei campioni nel set di dati del test.

Punti di forza e di debolezza

Il vantaggio principale dell'utilizzo degli alberi delle decisioni è che sono intuitivamente molto facili da spiegare. Rispecchiano da vicino il processo decisionale umano rispetto ad altri approcci di regressione e classificazione. Possono essere visualizzati graficamente e possono facilmente gestire predittori qualitativi senza la necessità di creare variabili fittizie.

Un altro enorme vantaggio è che gli algoritmi sono completamente invarianti rispetto al ridimensionamento dei dati. Poiché ogni funzione viene elaborata separatamente e le possibili divisioni dei dati non dipendono dal ridimensionamento, per gli algoritmi dell'albero decisionale non è necessaria alcuna pre-elaborazione come la normalizzazione o la standardizzazione delle funzionalità. In particolare, gli alberi decisionali funzionano bene quando abbiamo caratteristiche che sono su scale completamente diverse o un mix di caratteristiche binarie e continue.

Tuttavia, gli alberi delle decisioni generalmente non hanno lo stesso livello di precisione predittiva di altri approcci, poiché non sono abbastanza robusti. Una piccola modifica nei dati può causare una grande modifica nell'albero stimato finale. Anche con l'uso della pre-potatura, tendono a sovrautilizzare e fornire scarse prestazioni di generalizzazione. Pertanto, nella maggior parte delle applicazioni, aggregando molti alberi decisionali, utilizzando metodi come insaccamento, foreste casuali e potenziamento, le prestazioni predittive degli alberi decisionali possono essere sostanzialmente migliorate.

Fonti di riferimento:

  • Introduzione all'apprendimento statistico di Gareth James, Daniela Witten, Trevor Hastie e Robert Tibshirani (2014)
  • Machine Learning In Action di Peter Harrington (2012)
  • Introduzione all'apprendimento automatico con Python di Sarah Guido e Andreas Muller (2016)

- -

Se ti è piaciuto questo pezzo, mi piacerebbe se premi il pulsante di battito delle mani così gli altri potrebbero inciamparvi. Puoi trovare il mio codice su GitHub e altri miei scritti e progetti su https://jameskle.com/. Puoi anche seguirmi su Twitter, inviarmi un'e-mail direttamente o trovarmi su LinkedIn.