Algoritmo dell'albero decisionale: una guida completa

Questo articolo è stato pubblicato come parte di Blogathon sulla scienza dei dati

Fino ad ora abbiamo imparato a conoscere la regressione lineare, la regressione logistica ed erano piuttosto difficili da capire. Cominciamo ora con l'albero delle decisioni e ti assicuro che questo è probabilmente l'algoritmo più semplice in Machine Learning. Non c'è molta matematica coinvolta qui. Poiché è molto facile da usare e interpretare è uno dei metodi più utilizzati e pratici utilizzati nel Machine Learning.

Contenuti

1. Che cos'è un albero decisionale?

2. Esempio di un albero decisionale

3. Entropia

4. Guadagno di informazioni

5. Quando smettere di dividere?

6. Come fermare il sovradattamento?

• profondità massima
• min_campioni_split
• min_campioni_foglia
• max_caratteristiche

7. Potatura

• Post-potatura
• Pre-potatura

8. Note di chiusura

Che cos'è un albero decisionale?

È uno strumento che ha applicazioni che abbracciano diverse aree. Gli alberi decisionali possono essere utilizzati sia per la classificazione che per i problemi di regressione. Il nome stesso suggerisce che utilizza un diagramma di flusso come una struttura ad albero per mostrare le previsioni che risultano da una serie di suddivisioni basate su funzionalità. Inizia con un nodo radice e termina con una decisione presa dalle foglie.

1 Immagine

Prima di saperne di più sugli alberi decisionali, familiarizziamo con alcune terminologie.

Nodi radice – È il nodo presente all'inizio di un albero decisionale da questo nodo la popolazione inizia a dividere secondo varie caratteristiche.

Nodi decisionali – i nodi che otteniamo dopo aver diviso i nodi radice sono chiamati Decision Node

Nodi foglia – i nodi dove non è possibile un'ulteriore scissione sono chiamati nodi foglia o nodi terminali

Sottoalbero – proprio come una piccola porzione di un grafo è chiamata sotto-grafo, allo stesso modo una sotto-sezione di questo albero decisionale è chiamata sotto-albero.

Potatura – non è altro che tagliare alcuni nodi per fermare l'overfitting.

2 Immagine

Esempio di albero decisionale

Comprendiamo gli alberi decisionali con l'aiuto di un esempio.

3 Immagine

Gli alberi decisionali sono capovolti, il che significa che la radice è in alto e quindi questa radice è divisa in vari nodi. Gli alberi decisionali non sono altro che un mucchio di affermazioni if-else in termini profani. Controlla se la condizione è vera e se lo è, passa al nodo successivo collegato a quella decisione.

Nel diagramma sottostante l'albero chiederà prima che tempo fa? È soleggiato, nuvoloso o piovoso? Se sì, passerà alla funzione successiva che è umidità e vento. Controllerà di nuovo se c'è vento forte o debole, se c'è vento debole e piove allora la persona può andare a giocare.

4 Immagine

Hai notato qualcosa nel diagramma di flusso sopra? Vediamo che se il il tempo è nuvoloso allora dobbiamo andare a giocare. Perché non si è diviso di più? Perché si è fermato lì?

Per rispondere a questa domanda, dobbiamo conoscere alcuni altri concetti come l'entropia, il guadagno di informazioni e l'indice di Gini. Ma in termini semplici, posso dire qui che l'output per il set di dati di allenamento è sempre sì per il tempo nuvoloso, poiché non c'è disordine qui non è necessario dividere ulteriormente il nodo.

L'obiettivo dell'apprendimento automatico è ridurre l'incertezza o i disturbi dal set di dati e per questo utilizziamo alberi decisionali.

Ora devi pensare come faccio a sapere quale dovrebbe essere il nodo radice? quale dovrebbe essere il nodo decisionale? quando dovrei smettere di dividere? Per decidere questo, c'è una metrica chiamata "Entropia" che è la quantità di incertezza nel set di dati.

entropia

L'entropia non è altro che l'incertezza nel nostro set di dati o la misura del disordine. Provo a spiegarlo con l'aiuto di un esempio.

Supponi di avere un gruppo di amici che decide quale film possono guardare insieme domenica. Ci sono 2 scelte per i film, uno è “Lucia” e il secondo è "Titanic" e ora ognuno deve dire la sua scelta. Dopo che tutti hanno dato la loro risposta, lo vediamo “Lucy” ottiene 4 voti ed “Titanic” ottiene 5 voti. Quale film guardiamo ora? Non è difficile scegliere 1 film ora perché i voti per entrambi i film sono in qualche modo uguali.

Questo è esattamente ciò che chiamiamo disordine, c'è lo stesso numero di voti per entrambi i film e non possiamo davvero decidere quale film dovremmo guardare. Sarebbe stato molto più facile se i voti per "Lucy" fossero stati 8 e per "Titanic" fossero 2. Qui potremmo facilmente dire che la maggioranza dei voti è per "Lucy", quindi tutti guarderanno questo film.

In un albero decisionale, l'output è principalmente "sì" o "no"

La formula per l'entropia è mostrata di seguito:

qui p₊ è la probabilità di classe positiva

p_- è la probabilità di classe negativa

S è il sottoinsieme dell'esempio di addestramento

In che modo gli alberi decisionali utilizzano l'entropia?

Ora sappiamo cos'è l'entropia e qual è la sua formula. Successivamente, dobbiamo sapere come funziona esattamente in questo algoritmo.

L'entropia misura fondamentalmente l'impurità di un nodo. L'impurità è il grado di casualità; dice quanto siano casuali i nostri dati. UN puro sub-split significa che o dovresti ricevere "sì" o dovresti ricevere "no".

Supponiamo che a caratteristica ha inizialmente 8 “sì” e 4 “no”, dopo il primo divide il nodo sinistro ottiene 5 "sì" e 2 "no" mentre il nodo destro ottiene 3 "sì" e 2 "no".

Vediamo qui che la scissione non è pura, perché? Perché possiamo ancora vedere alcune classi negative in entrambi i nodi. Per creare un albero decisionale, dobbiamo calcolare l'impurità di ciascuna divisione e, quando la purezza è del 100%, lo realizziamo come un nodo foglia.

Per verificare l'impurità della funzione 2 e della funzione 3 prenderemo l'aiuto della formula Entropy.

Fonte immagine: Autore

Per la funzione 3,

Possiamo vedere chiaramente dall'albero stesso che il nodo sinistro ha una bassa entropia o una maggiore purezza rispetto al nodo destro poiché il nodo sinistro ha un numero maggiore di "sì" ed è facile decidere qui.

Ricorda sempre che maggiore è l'Entropia, minore sarà la purezza e maggiore sarà l'impurità.

Come accennato in precedenza, l'obiettivo dell'apprendimento automatico è diminuire l'incertezza o l'impurità nel set di dati, qui utilizzando l'entropia otteniamo l'impurità di un particolare nodo, non sappiamo se l'entropia genitore o l'entropia di un particolare nodo è diminuito oppure no.

Per questo, portiamo una nuova metrica chiamata "Guadagno di informazioni" che ci dice quanto è diminuita l'entropia genitore dopo averla divisa con qualche caratteristica.

Guadagno di informazioni

Il guadagno di informazioni misura la riduzione dell'incertezza data qualche caratteristica ed è anche un fattore decisivo per quale attributo dovrebbe essere selezionato come nodo decisionale o nodo radice.

È solo l'entropia dell'intero set di dati, l'entropia del set di dati a cui vengono date alcune funzionalità.

Per capirlo meglio consideriamo un esempio:
Supponiamo che tutta la nostra popolazione abbia un totale di 30 istanze. Il set di dati serve a prevedere se la persona andrà in palestra o meno. Diciamo che 16 persone vanno in palestra e 14 persone no

Ora abbiamo due funzioni per prevedere se andrà in palestra o meno.

La funzione 1 è "Energia" che assume due valori "Alto e basso"

La funzione 2 è "Motivazione" che assume 3 valori "Nessuna motivazione", "Neutro" e "Altamente motivato".

Vediamo come verrà realizzato il nostro albero decisionale utilizzando queste 2 funzionalità. Useremo il guadagno di informazioni per decidere quale caratteristica dovrebbe essere il nodo radice e quale caratteristica dovrebbe essere posizionata dopo la divisione.

Fonte immagine: Autore

Calcoliamo l'entropia:

Per vedere la media ponderata dell'entropia di ciascun nodo faremo come segue:

Ora che abbiamo il valore di E(Genitore) e E(Parente|Energia), il guadagno di informazioni sarà:

La nostra entropia genitore era vicino a 0.99 e dopo aver esaminato questo valore di guadagno di informazioni, possiamo dire che l'entropia del set di dati diminuirà di 0.37 se rendiamo "Energia" come nostro nodo radice.

Allo stesso modo, lo faremo con l'altra funzione "Motivazione" e calcoleremo il suo guadagno di informazioni.

Fonte immagine: Autore

Calcoliamo qui l'entropia:

Per vedere la media ponderata dell'entropia di ciascun nodo faremo come segue:

Ora che abbiamo il valore di E(Genitore) e E(Genitore|Motivazione), il guadagno di informazioni sarà:

Ora vediamo che la funzione "Energia" offre una riduzione maggiore che è 0.37 rispetto alla funzione "Motivazione". Quindi selezioneremo la funzione che ha il maggior guadagno di informazioni e quindi divideremo il nodo in base a quella funzione.

In questo esempio "Energia" sarà il nostro nodo radice e faremo lo stesso per i sottonodi. Qui possiamo vedere che quando l'energia è "alta" l'entropia è bassa e quindi possiamo dire che una persona andrà sicuramente in palestra se ha un'energia alta, ma cosa succede se l'energia è bassa? Divideremo nuovamente il nodo in base alla nuova funzionalità che è "Motivazione".

Quando smettere di dividere?

Devi farti questa domanda: quando smetteremo di coltivare il nostro albero? Di solito, i set di dati del mondo reale hanno un gran numero di funzionalità, che si tradurranno in un gran numero di divisioni, che a loro volta danno un albero enorme. Tali alberi richiedono tempo per essere costruiti e possono portare al sovradattamento. Ciò significa che l'albero fornirà un'accuratezza molto buona sul set di dati di addestramento ma darà una scarsa accuratezza nei dati di test.

Esistono molti modi per affrontare questo problema attraverso l'ottimizzazione degli iperparametri. Possiamo impostare la profondità massima del nostro albero decisionale usando il profondità massima parametro. Più il valore di profondità massima, più complesso sarà il tuo albero. L'errore di addestramento fuori rotta diminuirà se aumentiamo il profondità massima valore, ma quando i nostri dati di test entrano in gioco, otterremo una precisione molto scarsa. Quindi hai bisogno di un valore che non superi o sottodimensioni i nostri dati e per questo, puoi usare GridSearchCV.

Un altro modo è impostare il numero minimo di campioni per ogni versamento. È indicato da min_campioni_split. Qui specifichiamo il numero minimo di campioni richiesti per fare un versamento. Ad esempio, possiamo utilizzare un minimo di 10 campioni per prendere una decisione. Ciò significa che se un nodo ha meno di 10 campioni, utilizzando questo parametro, possiamo interrompere l'ulteriore suddivisione di questo nodo e renderlo un nodo foglia.

Ci sono più iperparametri come:

min_campioni_foglia – rappresenta il numero minimo di campioni richiesti per essere nel nodo foglia. Più si aumenta il numero, maggiore è la possibilità di overfitting.

max_caratteristiche – ci aiuta a decidere quale numero di caratteristiche considerare quando si cerca la migliore suddivisione.

Per saperne di più su questi iperparametri puoi leggerlo qui.

Potatura

È un altro metodo che può aiutarci a evitare il sovradattamento. Aiuta a migliorare le prestazioni dell'albero tagliando i nodi o i sottonodi che non sono significativi. Rimuove i rami che hanno un'importanza molto bassa.

Ci sono principalmente 2 modi per potare:

(I) Pre-potatura – possiamo smettere di far crescere l'albero prima, il che significa che possiamo potare/rimuovere/tagliare un nodo se ha poca importanza mentre cresce l'albero.

(Ii) Post-potatura – una volta nostro l'albero è costruito fino alla sua profondità, possiamo iniziare a sfoltire i nodi in base al loro significato.

Note finali

Per riassumere, in questo articolo abbiamo appreso degli alberi decisionali. Su quale base l'albero divide i nodi e come fermare l'overfitting. perché la regressione lineare non funziona in caso di problemi di classificazione.

Nel prossimo articolo spiegherò le foreste casuali, che è ancora una nuova tecnica per evitare il sovradattamento.
Per verificare l'implementazione completa degli alberi decisionali, fare riferimento a my Github repository.

Fatemi sapere se avete domande nei commenti qui sotto.

L'autore

I media mostrati in questo articolo non sono di proprietà di Analytics Vidhya e vengono utilizzati a discrezione dell'autore.

Fonti di immagine

1. Immagine 1 – https://wiki.pathmind.com/decision-tree
2. Immagine 2 – https://wiki.pathmind.com/decision-tree
3. Immagine 3 – www.hackerearth.com
4. Immagine 4 – www.hackerearth.com

Leggi Anche

Fonte: https://www.analyticsvidhya.com/blog/2021/08/decision-tree-algorithm/