Quali criteri dovrebbe utilizzare un algoritmo dell’albero decisionale per dividere variabili / colonne?

Prima di costruire un algoritmo ad albero decisionale il primo passo è rispondere a questa domanda. Diamo un’occhiata a uno dei modi per rispondere a questa domanda. Per fare ciò avremo bisogno di capire un uso alcuni concetti chiave dalla teoria dell’informazione.

Esaminiamo questo metodo seguendo i seguenti passaggi:

1. Dai un’occhiata molto breve a cos’è un albero decisionale.
2. Definire ed esaminare la formula per l’entropia.
3. Discuti cosa c’è un po ‘ nella teoria dell’informazione.
4. Definisci il guadagno di informazioni e usa l’entropia per calcolarlo.
5. Scrivere alcune funzioni di base Python utilizzando i concetti di cui sopra.

Nella scienza dei dati, l’algoritmo dell’albero decisionale è un algoritmo di apprendimento supervisionato per problemi di classificazione o regressione. Il nostro obiettivo finale è quello di utilizzare i dati storici per prevedere un risultato. A differenza della regressione lineare, gli alberi decisionali possono rilevare interazioni non lineari tra variabili nei dati.

Diamo un’occhiata a un albero decisionale molto semplice. Di seguito è riportato un flusso di lavoro che può essere utilizzato per prendere una decisione sull’opportunità o meno di mangiare un biscotto al burro di arachidi.

In questo esempio, un albero di decisione può prendere sul fatto che si deve mangiare solo il cookie se vengono soddisfatti determinati criteri. Questo è l’obiettivo finale di un albero decisionale. Vogliamo continuare a prendere decisioni (divisioni) fino a quando determinati criteri non sono soddisfatti. Una volta incontrato possiamo usarlo per classificare o fare una previsione. Questo esempio è molto semplice usando solo due variabili (allergia, rovinare la cena). Ma, se hai un set di dati con migliaia di variabili/colonne, come decidi quali variabili/colonne sono le più efficienti da dividere? Un modo popolare per risolvere questo problema, specialmente se si utilizza un algoritmo ID3, è utilizzare l’entropia e il guadagno di informazioni.

Il compito

Diciamo che abbiamo alcuni dati e vogliamo usarlo per fare un quiz online che predice qualcosa circa il quiz taker. Dopo aver esaminato le relazioni nei dati, abbiamo deciso di utilizzare un algoritmo ad albero decisionale. Se non sei mai stato risucchiato in un quiz online, puoi vedere centinaia di esempi qui. L’obiettivo del quiz sarà quello di indovinare se il taker quiz è da uno degli stati del Midwest dell’America. Le domande del quiz ruoteranno intorno se a loro piace un certo tipo di cibo o no. Di seguito è riportato un piccolo set di dati fittizio con quindici voci. Ogni voce ha le risposte a una serie di domande. La maggior parte delle domande riguarda se gli è piaciuto un certo tipo di cibo, in cui il partecipante ha risposto (1) per sì o (0) per ora. L’ultima colonna (“midwest?”) è la nostra colonna di destinazione, il che significa che una volta costruito l’albero delle decisioni, questa è la classificazione che stiamo cercando di indovinare.

Entropia

Per iniziare facciamo un teoria dell’informazione metrica chiamata entropia. Nella scienza dei dati, l’entropia viene utilizzata come un modo per misurare quanto sia “mista” una colonna. In particolare, l’entropia viene utilizzata per misurare il disturbo. Iniziamo trovando l’entropia della nostra colonna di destinazione, ” midwest?”.

Ci sono dieci persone che vivono nel midwest e cinque persone che non lo fanno. Se qualcuno stava per chiederti quanto sia mista la colonna, potresti dire che era un po ‘ mista, con una maggioranza(2/3) delle persone del midwest. L’entropia ci dà un modo per quantificare la risposta “sorta di misto”. Più sono mescolati i (1)s e (0) s nella colonna, maggiore è l’entropia. Se ” midwest?”se avessimo quantità uguali di (1) s e (0)s, la nostra entropia sarebbe 1. Se ” midwest?”consisteva solo di (1)s l’entropia sarebbe 0.

è possibile utilizzare la seguente formula per calcolare l’entropia:

Andiamo attraverso ogni fase della formula e calcolare l’entropia di “midwest?” colonna.

1. Dobbiamo scorrere ogni valore univoco in una singola colonna e assegnarlo a i. Per questo esempio, abbiamo 2 casi (c) nel “midwest?”colonna, (0) o (1).
2. Calcoliamo quindi la probabilità che quel valore si verifichi nei dati. Per il caso di (1), la probabilità è 10/15. Per il caso di (0), la probabilità è 5/15.
3. Prendiamo la probabilità di ogni caso e la moltiplichiamo per la base logaritmo 2 della probabilità. 2 è la base più comune perché l’entropia è misurata in bit(ne parleremo più avanti). La spiegazione completa del motivo per cui viene utilizzato 2 è fuori dallo scopo di questo post, ma un utente su stack exchange offre una buona spiegazione. Per il caso di(1), otteniamo 10/15 * log2(10/15). Per il caso di (0), otteniamo 5/15 * log2(5/15).
4. Successivamente, prendiamo il nostro prodotto da ogni caso sopra e lo sommiamo insieme. Per questo esempio, 10/15 * log2(10/15) + 5/15*log2(5/15).
5. Infine, neghiamo la somma totale dall’alto — – (10/15*log2(10/15) + 5/15 * log2 (5/15)).

una Volta che abbiamo messo i passaggi, tutte insieme, otteniamo il seguente:

il Nostro finale di entropia .918278. Quindi, cosa significa veramente?

Teoria dell’informazione e un po ‘ di informazioni

Andando avanti sarà importante capire il concetto di bit. Nella teoria dell’informazione, un bit è pensato come un numero binario che rappresenta 0 per nessuna informazione e 1 per un bit completo di informazioni. Possiamo rappresentare un po ‘ di informazioni come un numero binario perché ha il valore (1) o (0). Supponiamo che ci sia una probabilità uguale che piova domani (1) o non piova(0). Se ti dico che domani pioverà, ti ho dato un po ‘ di informazioni.

Possiamo anche pensare all’entropia come informazione. Supponiamo di avere un dado a sei lati caricato che atterra sempre su (3). Ogni volta che rotoliamo il dado, sappiamo in anticipo che il risultato sarà (3). Non otteniamo nuove informazioni rotolando il dado, quindi l’entropia è 0. D’altra parte, se il dado è lontano e rotoliamo un (3) c’era una possibilità di 1/6 nel rotolare il (3). Ora abbiamo acquisito informazioni. Quindi, rotolare il dado ci dà un po ‘ di informazioni — da che parte è atterrato il numero.

Per un tuffo più profondo nel concetto di un po ‘ di informazioni, si può leggere di più qui.

Otteniamo meno di un “bit” di sole informazioni .918278-perché ci sono più (1) s nel “midwest?”colonna di (0)s. Ciò significa che se prevedessimo un nuovo valore, potremmo indovinare che la risposta è (1) e avere ragione più spesso che sbagliata (perché c’è una probabilità 2/3 che la risposta sia 1). A causa di questa conoscenza preliminare, otteniamo meno di un “bit” completo di informazioni quando osserviamo un nuovo valore.

Usando l’entropia per prendere decisioni

Il nostro obiettivo è trovare le migliori variabili / colonne da dividere quando si costruisce un albero decisionale. Alla fine, vogliamo continuare a dividere le variabili/colonne fino a quando la nostra colonna di destinazione mista non è più mista.

Ad esempio, diamo un’occhiata all’entropia del “midwest?”colonna dopo aver diviso il nostro set di dati sul” potato_salad?” colonna.

Sopra, il nostro set di dati è diviso in due sezioni. Sul lato sinistro, tutti coloro che amano l’insalata di patate. Sul lato destro tutti quelli che non lo fanno. Riempiamo l’attenzione sul lato sinistro che ora ha sette persone del midwest e due persone che non lo sono. Usando la formula per l’entropia sulla colonna del midwest diviso a sinistra la nuova entropia è .764204. E ‘ fantastico! Il nostro obiettivo è quello di abbassare l’entropia e siamo andati da .918278 a .764204. Ma, non possiamo fermarci qui, se guardiamo la colonna di destra la nostra entropia è salita poiché ci sono una quantità uguale di (1)s e (0)s. Quello di cui abbiamo bisogno è un modo per vedere come l’entropia cambia su entrambi i lati della divisione. La formula per ottenere informazioni lo farà. Ci dà un numero per quantificare quanti bit di informazioni che abbiamo guadagnato ogni volta che dividiamo i nostri dati.

Guadagno di informazioni

In precedenza abbiamo stabilito che vogliamo divisioni che abbassino l’entropia della nostra colonna di destinazione. Quando ci siamo divisi su ” patato_salad?”abbiamo visto quell’entropia nel” midwest?”è andato giù sul lato sinistro. Ora dobbiamo capire l’entropia totale abbassata quando guardiamo entrambi i lati della divisione. Diamo un’occhiata al guadagno di informazioni.

Il guadagno di informazioni utilizzerà la seguente formula:

Lasciate che la ripartizione cosa sta succedendo qui.

Torneremo alla nostra ” patato_salad?” esempio. Le variabili nella formula di cui sopra rappresenteranno quanto segue:

• T = Target, il nostro “midwest?”column
• A = la variabile (colonna) che stiamo testando,” potato_salad?”
• v = ogni valore in A, ogni valore nel ” potato_salad?”colonna

1. In primo luogo, calcoleremo l’entropia originale per (T) prima della divisione,.918278
2. Quindi, per ogni valore univoco (v) nella variabile (A), calcoliamo il numero di righe in cui (A) assume il valore (v) e lo dividiamo per il numero totale di righe. Per la ” patato_salad?”colonna otteniamo 9/15 per il valore univoco di (1) e 6/15 per il valore univoco di (0).
3. Quindi, moltiplichiamo i risultati per l’entropia delle righe dove (A) è (v). Per la divisione sinistra (divisione su 1 per ” potato_salad?”) otteniamo 9/15 * .764204. Per il lato destro della divisione ( divisione su 0 per ” potato_salad?”) otteniamo 6/15 * 1.
4. Aggiungiamo tutti questi sottoinsiemi prodotti insieme, 9/14*.764204 + 6/15 = .8585224.

5. Quindi sottraiamo dall’entropia complessiva per ottenere guadagno di informazioni,.918278 -.8585224 = .059754

Il nostro guadagno di informazioni è .059754. Questo cosa ci dice?

Ecco una spiegazione alternativa. Stiamo trovando l’entropia di ogni set post-split, ponderandola per il numero di elementi in ogni split, quindi sottraendo dall’entropia corrente. Se il risultato è positivo, abbiamo abbassato l’entropia con la nostra divisione. Più alto è il risultato, più abbiamo abbassato l’entropia.

Finiamo con .059754, il che significa che ci guadagniamo .059754 bit di informazioni dividendo il nostro set di dati sul ” potato_salad?”variabile / colonna. Il nostro guadagno di informazioni è basso, ma è ancora positivo, perché abbiamo abbassato l’entropia sul lato sinistro della divisione.

Ora dobbiamo ripetere questo processo per ogni colonna che stiamo usando. Invece di farlo a mano scriviamo del codice Python.

Avvolgendo il tutto con Python

Ora che comprendiamo il guadagno di informazioni, abbiamo bisogno di un modo per ripetere questo processo per trovare la variabile / colonna con il maggiore guadagno di informazioni. Per fare ciò, possiamo creare alcune semplici funzioni in Python.

Importazione dei dati

Trasformiamo la nostra tabella sopra in un DataFrame usando la libreria Python pandas. Importeremo i panda e useremo la funzione read_csv () per creare un DataFrame chiamato “midwest”.

import pandas as pd
midwest = pd.read_csv('midwes.csv')

Una funzione Python per Entropia

Per questa funzione, avremo bisogno della libreria NumPy per usare la funzione bincount() e il modulo math per usare la funzione log ().

import numpy
import math

Successivamente, definiremo la nostra funzione con un parametro. L’argomento dato sarà la serie, la lista o la matrice NumPy in cui stiamo cercando di calcolare l’entropia.

def calc_entropy(column):

Dovremo trovare la percentuale di ciascun caso nella colonna. Possiamo usare il numpy.funzione bincount() per questo. Il valore restituito è un array NumPy che memorizzerà il conteggio di ogni valore univoco dalla colonna passata come argomento.

counts = numpy.bincount(column)

Memorizzeremo le probabilità di ogni valore univoco dividendo l’array “counts” per la lunghezza della colonna.

probabilities = counts / len(column)

Possiamo quindi inizializzare una variabile chiamata “entropia” e impostarla su 0.

entropy = 0

Successivamente, possiamo usare un “for loop” per scorrere ogni probabilità nel nostro array di probabilità e moltiplicarla per il logaritmo base 2 di probabilità usando la matematica.funzione log (). Quindi, aggiungi ogni caso alla nostra variabile entropia memorizzata. * assicurati di controllare che la tua probabilità sia maggiore di 0 altrimenti log(0) restituirà undefined

for prob in probabilities:
if prob > 0:
endtropy += prob * math.log(prob,2)

Infine, restituiremo la nostra variabile entropia negata.

return -entropy

Tutti insieme ora:

Grande! Ora possiamo costruire una funzione per calcolare il guadagno di informazioni.

Una funzione Python per ottenere informazioni

Dovremo definire una funzione che avrà tre parametri, uno per l’intero set di dati, uno per il nome della colonna su cui vogliamo dividere e uno per il nome della nostra colonna di destinazione.

def calc_information_gain(data, split_name, target_name):

Successivamente, possiamo usare la funzione entropia di prima per calcolare l’entropia originale della nostra colonna di destinazione.

orginal_entropy = calc_entropy(data)

Ora dobbiamo dividere la nostra colonna.

* Per questo esempio useremo solo le variabili / colonne con due univoci. Se si desidera dividere su una variabile/colonna come “age”, ci sono diversi modi per farlo. Un modo è quello di dividere su ogni valore unico. Un altro modo è semplificare il calcolo del guadagno di informazioni e rendere più semplici le suddivisioni non suddividendo per ogni valore univoco. Invece, la mediana viene trovata per la variabile/coumn divisa su. Tutte le righe in cui il valore della variabile è inferiore alla mediana andranno al ramo sinistro e il resto delle righe andrà al ramo destro. Per calcolare il guadagno di informazioni, dovremo solo calcolare le entropie per due sottoinsiemi. Non cammineremo attraverso questo metodo, ma una volta eseguita la divisione sulla mediana, il resto dei passaggi sarebbe lo stesso descritto di seguito.

Poiché le colonne con cui stiamo lavorando hanno solo due valori univoci, faremo una divisione a sinistra e una divisione a destra.

Inizieremo usando i panda.Serie.unique () per darci una matrice dei valori univoci nella colonna

values = data.unique()

Successivamente, creeremo una divisione sinistra e destra usando “valori”.

left_split = data == values]
right_split = data == values]

Ora possiamo avviare una variabile per sottrarre dalla nostra entropia originale.

to_subtract = 0

Quindi eseguiremo l’iterazione di ogni sottoinsieme creato dalla nostra divisione, calcoleremo la probabilità del sottoinsieme e quindi aggiungeremo il prodotto della probabilità e l’entropia della colonna target dei sottoinsiemi.

for subset in :
prob = (subset.shape / data.shape)
to_subtract += prob * calc_entropy(subset)

Infine, possiamo restituire la differenza di to_subract sottratta dall’entropia originale.

return original_entropy - to_subtract

L’intera funzione è sotto.

Una funzione Python per il più alto guadagno di informazioni

La nostra funzione finale sarà quella che restituirà il nome della variabile / colonna con il più alto guadagno di informazioni.

Come accennato in precedenza, stiamo usando solo le colonne con due valori univoci per questo esempio. Memorizzeremo i nomi delle colonne in un elenco da utilizzare nella funzione. Per arrivare al punto, lo codificheremo duramente per questo esempio, ma in un set di dati di grandi dimensioni, sarebbe meglio scrivere codice per creare questo elenco in modo dinamico in base ai criteri che usiamo per scegliere le colonne.

columns = 

Avvolgiamo il passaggio finale in una funzione in modo da poterlo riutilizzare secondo necessità. Avrà un parametro, l’elenco delle colonne che vogliamo trovare il più alto guadagno di informazioni per.

def highest_info_gain(columns):

Inizializzeremo un dizionario vuoto per memorizzare i nostri guadagni di informazioni.

information_gains = {}

E quindi possiamo scorrere l’elenco delle colonne e memorizzare il risultato nel nostro dizionario information_gains.

for col in columns:
information_gain = calc_information_gain(midwest, col, 'midwest?)
information_gains = information_gain

Infine, possiamo restituire la chiave del valore più alto nel nostro dizionario.

return max(information_gains, key=information_gains.get)

Tutti insieme ora:

Una volta eseguita la nostra funzione finale

print(highest_info_gain(midwest, columns, 'midwest?'))
//sushi

vediamo la variabile/colonna con il più alto guadagno di informazioni è ‘sushi?’.

Possiamo visualizzare una divisione su sushi di seguito:

La nostra divisione a sinistra ha due persone su sei dal midwest. La divisione destra ha otto delle nove persone del midwest. Questa è stata una divisione efficiente e ha abbassato la nostra entropia su entrambi i lati. Se dovessimo continuare useremmo la ricorsione per continuare a dividere ogni divisione con un obiettivo per terminare ogni ramo con un’entropia pari a zero.

Conclusione

Gli alberi decisionali possono essere un utile algoritmo di apprendimento automatico per rilevare interazioni non lineari tra variabili nei dati. In questo esempio, abbiamo esaminato le fasi iniziali di un algoritmo di classificazione dell’albero decisionale. Abbiamo quindi esaminato tre concetti di teoria dell’informazione, entropia, bit e guadagno di informazioni. Usando questi concetti siamo stati in grado di costruire alcune funzioni in Python per decidere quali variabili/colonne erano le più efficienti da dividere. Con una solida conoscenza di questi concetti, possiamo andare avanti per costruire un albero decisionale.