hvilke kriterier skal en beslutningstrealgoritme bruke til å dele variabler / kolonner?

før du bygger en beslutningstrealgoritme, er det første trinnet å svare på dette spørsmålet. La oss ta en titt på en av måtene å svare på dette spørsmålet. For a gjore det ma vi forst bruke noen viktige begreper fra informasjonsteori.

la oss undersøke denne metoden ved å ta følgende trinn:

1. Ta en veldig kort titt på Hva Et Beslutningstre er.
2. Definer og undersøk Formelen For Entropi.
3. Diskuter Hva Litt er i informasjonsteori.
4. Definer Informasjonsgevinst og bruk entropi til å beregne Den.
5. Skriv noen Grunnleggende Pythonfunksjoner ved hjelp av de ovennevnte konseptene.

i datavitenskap er beslutningstrealgoritmen en veiledet læringsalgoritme for klassifiserings-eller regresjonsproblemer. Vårt endelige mål er å bruke historiske data for å forutsi et utfall. I motsetning til lineær regresjon kan beslutningstrær plukke opp ikke-lineære interaksjoner mellom variabler i dataene.

La oss se på et veldig enkelt beslutningstre. Nedenfor er en arbeidsflyt som kan brukes til å ta en beslutning om å spise en peanøttsmørkake eller ikke.

ikke å spise en cookie

i dette eksemplet kan et beslutningstre plukke opp det faktum at du bare skal spise informasjonskapselen hvis visse kriterier er oppfylt. Dette er det endelige målet med et beslutningstre. Vi ønsker å fortsette å ta beslutninger (splittelser) til visse kriterier er oppfylt. Når vi er møtt, kan vi bruke den til å klassifisere eller lage en prediksjon. Dette eksemplet er veldig grunnleggende ved å bruke bare to variabler(allergi, ødelegger middag). Men hvis du har et datasett med tusenvis av variabler/kolonner, hvordan bestemmer du hvilke variabler / kolonner som er mest effektive å dele på? En populær måte å løse dette problemet på, spesielt hvis DU bruker EN ID3-algoritme, er å bruke entropi og informasjonsgevinst.

Oppgaven

La oss si at vi har noen data, og vi vil bruke den til å lage en online quiz som forutsier noe om quiz-takeren. Etter å ha sett på relasjonene i dataene har vi besluttet å bruke en beslutning treet algoritme. Hvis du aldri har blitt sugd inn i en online quiz, kan du se hundrevis av eksempler her. Målet med quiz vil være å gjette om quiz taker er fra En Av Usas midtvesten stater. Spørsmålene i quizen vil dreie seg om de liker en bestemt type mat eller ikke. Nedenfor har et lite fiktivt datasett med femten oppføringer. Hver oppføring har svar på en rekke spørsmål. De fleste spørsmål handler om om de likte en bestemt type mat, hvor deltakeren svarte (1) for ja eller (0) for nå. Den siste kolonnen («midtvesten?») er vår målkolonne, noe som betyr at når beslutningstreet er bygget, er dette klassifiseringen vi prøver å gjette.

entropi

for å komme i gang vil vi bruke en informasjonsteori metrisk kalt entropi. I datavitenskap brukes entropi som en måte å måle hvordan «blandet» en kolonne er. Spesielt er entropi brukt til å måle lidelse. La oss starte med å finne entropien til vår målkolonne, » midtvesten?”.

vår målkolonne,»midtvesten?»

det er ti personer som bor i midtvesten og fem personer som ikke gjør det. Hvis noen skulle spørre deg hvor blandet kolonnen er, kan du si at det var slags blandet, med et flertall(2/3) av folket fra midtvesten. Entropi gir oss en måte å kvantifisere svaret på» slags blandet». Jo mer blandet (1)s og (0)s i kolonnen er, jo høyere entropi. Hvis » midtvesten?»hadde like mengder (1) s og (0) s vår entropi ville være 1. Hvis » midtvesten?»besto bare av (1) s entropien ville være 0.

vi kan bruke følgende formel til å beregne entropi:

la oss gå gjennom hvert trinn i formelen og beregne entropien for «midtvesten?” kolonne.

1. Vi må iterere gjennom hver unik verdi i en enkelt kolonne og tilordne den til i. For dette eksemplet har vi 2 tilfeller (c) i «midtvesten?»kolonne, enten (0) eller (1).
2. vi beregner deretter sannsynligheten for at verdien forekommer i dataene. For tilfelle av (1) er sannsynligheten 10/15. For tilfellet av (0) er sannsynligheten 5/15.
3. vi tar sannsynligheten for hvert tilfelle og multipliserer den med logaritmebasen 2 av sannsynligheten. 2 er den vanligste basen fordi entropi måles i biter(mer om det senere). Den fulle forklaringen på hvorfor 2 brukes er utenfor omfanget av dette innlegget, men en bruker på stack exchange gir en god forklaring. For tilfelle av(1) får vi 10/15*log2(10/15). For tilfelle av (0) får vi 5/15*log2(5/15).
4. Deretter tar vi vårt produkt fra hvert tilfelle over og summerer det sammen. For dette eksemplet, 10/15 * log2(10/15) + 5/15 * log2 (5/15).
5. Til slutt negerer vi summen ovenfra,- — 10/15 * log2(10/15) + 5/15 * log2 (5/15)).

Når vi setter trinnene alle sammen får vi nedenfor:

vår endelige entropi er .918278. Så, hva betyr det egentlig?

Informasjonsteori og Litt Informasjon

Fremover vil det være viktig å forstå begrepet bit. I informasjonsteori er en bit tenkt som et binært tall som representerer 0 for ingen informasjon og 1 for en full bit av informasjon. Vi kan representere litt informasjon som et binært tall fordi det enten har verdien (1) eller (0). Anta at det er like stor sannsynlighet for at det regner i morgen (1) eller ikke regner (0). Hvis jeg forteller deg at det vil regne i morgen, jeg har gitt deg en bit av informasjon.

vi kan også tenke på entropi som informasjon. Anta at vi har en lastet seks-sidig dør som alltid lander på (3). Hver gang vi ruller terningen, vet vi på forhånd at resultatet blir (3). Vi får ingen ny informasjon ved å rulle terningen, så entropi er 0. Pa den annen side, hvis terningen er langt og vi ruller en (3) var det en 1/6 sjanse i a rulle den (3). Nå har vi fått informasjon. Dermed ruller terningen oss en bit informasjon-hvilken side nummeret landet på.

for et dypere dykk inn i begrepet litt informasjon, kan du lese mer her.

vi får mindre enn en » bit » av informasjon — bare .918278-fordi det er flere (1) s i «midtvesten?»kolonne enn (0) s. Dette betyr at hvis vi forutså en ny verdi, kunne vi gjette at svaret er (1) og være riktig oftere enn feil (fordi det er en 2/3 sannsynlighet for at svaret er 1). På grunn av denne forkunnskapen får vi mindre enn en full» bit » av informasjon når vi observerer en ny verdi.

Bruke Entropi Til Å Ta Beslutninger

Vårt mål Er å finne den beste variabelen / kolonnen(e) å dele på når du bygger et beslutningstre. Til slutt vil vi fortsette å dele variablene / kolonnene til vår blandede målkolonne ikke lenger er blandet.

for eksempel, la Oss se på entropien til » midtvesten?»kolonne etter at vi har delt datasettet vårt på» potato_salad?” kolonne.

splitt på»potetsalat?»kolonne

Ovenfor er datasettet vårt delt i to seksjoner. På venstre side, alle som liker potetsalat. På høyre side alle som ikke gjør det. vi fyller fokus på venstre side som nå har syv personer fra midtvesten og to personer som ikke er det. Ved å bruke formelen for entropi på venstre delt midtvesten kolonne den nye entropien er .764204. Dette er flott! Vårt mål er å senke entropien og vi gikk fra .918278 til .764204. Men vi kan ikke stoppe der, hvis vi ser på høyre kolonne, gikk vår entropi opp da det er like mye (1) s og (0) s. Det vi trenger er en måte å se hvordan entropien endres på begge sider av splittelsen. Formelen for informasjon gevinst vil gjøre det. Det gir oss et tall for å kvantifisere hvor mange biter av informasjon vi har fått hver gang vi dele våre data.

Informasjon Gain

Tidligere vi etablert vi ønsker deler som senker entropi av våre mål kolonne. Når vi deler på » potato_salad?»vi så at entropi i» midtvesten?»gikk ned på venstre side. Nå må vi forstå den totale entropien senket når vi ser på begge sider av splittelsen. La oss ta en titt på informasjon gevinst.

informasjon gevinst vil bruke følgende formel:

la oss bryte ned hva som skjer her.

vi går tilbake til vår » potato_salad?” eksempel. Variablene i formelen ovenfor vil representere følgende:

• T = Target, vår » midtvesten?»kolonne
• A = variabelen (kolonne) vi tester,» potato_salad?»
• v = hver verdi I A, hver verdi i » potetsalat?»kolonne

1. først beregner vi orginal entropi for (T) før splittelsen .918278
2. deretter beregner vi for hver unik verdi (v) i variabel (A) antall rader der (A) tar verdien (v), og deler den med totalt antall rader. For » potato_salad?»kolonne vi får 9/15 for den unike verdien av (1) og 6/15 for den unike verdien av (0).
3. neste multipliserer vi resultatene med entropien av radene der (A) er (v). For venstre splitt (delt på 1 for » potato_salad?») vi får 9/15 * .764204. For høyre side av splitten (delt på 0 for » potato_salad?») vi får 6/15 * 1.
4. vi legger til alle disse delsettproduktene sammen, 9/14*.764204 + 6/15 = .8585224.

5. Vi trekker deretter fra den generelle entropien for å få informasjonsgevinst .918278 -.8585224 = .059754

vår informasjon gevinst er .059754. Hva forteller det oss?

her er en alternativ forklaring. Vi finner entropien til hvert sett etter splitt, veier det med antall elementer i hver splitt, og trekker deretter fra dagens entropi. Hvis resultatet er positivt, har vi senket entropi med splittelsen vår. Jo høyere resultatet er, jo mer har vi senket entropi.

vi ender opp med .059754, noe som betyr at vi vinner .059754 biter av informasjon ved å dele datasettet vårt på » potato_salad?»variabel / kolonne. Vår informasjon gevinst er lav, men det er fortsatt positivt som er fordi vi senket entropien på venstre side av splitten.

nå må vi gjenta denne prosessen for hver kolonne vi bruker. I stedet for å gjøre dette for hånd, la oss skrive Litt Python-kode.

Pakke Det Hele Opp Med Python

Nå som vi forstår informasjonsgevinst, trenger vi en måte å gjenta denne prosessen for å finne variabelen / kolonnen med den største informasjonsgevinsten. For å gjøre dette kan vi lage noen enkle funksjoner i Python.

Importere Dataene

la oss slå vårt overbord til En DataFrame ved Hjelp Av Python pandas-biblioteket. Vi vil importere pandaer og bruke read_csv () – funksjonen til å lage En DataFrame som heter «midwest».

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

En Python-Funksjon for Entropi

for denne funksjonen trenger Vi numpy-biblioteket for å bruke bincount () – funksjonen og mattemodulen for å bruke log () – funksjonen.

import numpy
import math

Deretter definerer vi vår funksjon med en parameter. Argumentet gitt vil være serien, listen eller NumPy array der vi prøver å beregne entropien.

def calc_entropy(column):

vi må finne prosentandelen av hvert tilfelle i kolonnen. Vi kan bruke numpy.bincount () – funksjonen for dette. Returverdien er En NumPy array som vil lagre tellingen av hver unik verdi fra kolonnen som ble sendt som et argument.

counts = numpy.bincount(column)

vi lagrer sannsynlighetene for hver unik verdi ved å dele» teller » – arrayet med lengden på kolonnen.

probabilities = counts / len(column)

Vi kan deretter initialisere en variabel som heter «entropi» og sette den til 0.

entropy = 0

Deretter kan vi bruke en» for loop » for å sløyfe gjennom hver sannsynlighet i vår sannsynlighetsgruppe og multiplisere den med logaritmebasen 2 av sannsynlighet ved hjelp av matematikken.logg () – funksjonen. Deretter legger du til hvert tilfelle i vår lagrede entropivariabel. * pass på å sjekke sannsynligheten er stor enn 0 ellers logg (0) vil returnere udefinert

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

Til Slutt vil vi returnere vår negerte entropi variabel.

return -entropy

Alle sammen nå:

Flott! Nå kan vi bygge en funksjon for å beregne informasjon gevinst.

En Python-Funksjon for Informasjonsgevinst

vi må definere en funksjon som vil ha tre parametere, en for hele datasettet, en for navnet på kolonnen vi vil dele på, og en for navnet på vår målkolonne.

def calc_information_gain(data, split_name, target_name):

Deretter kan vi bruke entropifunksjonen fra tidligere for å beregne den opprinnelige entropien til målkolonnen.

orginal_entropy = calc_entropy(data)

nå må vi dele vår kolonne.

*for dette eksemplet vil vi bare bruke variablene / kolonnene med to unike. Hvis du vil dele på en variabel / kolonne som «alder», er det flere måter å gjøre dette på. En måte er å dele på hver unik verdi. En annen måte er å forenkle beregningen av informasjonsgevinst og gjøre splittene enklere ved ikke å splitte for hver unik verdi. I stedet er medianen funnet for variabelen / coumn blir delt på. Eventuelle rader der verdien av variabelen er under medianen, går til venstre gren, og resten av radene går til høyre gren. For å beregne informasjonsgevinst må vi bare beregne entropier for to undergrupper. Vi vil ikke gå gjennom denne metoden, men når splittelsen på medianen er utført, vil resten av trinnene være de samme som beskrevet nedenfor.

siden kolonnene vi jobber med bare har to unike verdier, vil vi gjøre en venstre splitt og en høyre splitt.

vi begynner med å bruke pandaene.Rekke.unique() for å gi oss en rekke unike verdier i kolonnen

values = data.unique()

neste, vil vi opprette en venstre og høyre splitt ved hjelp av «verdier».

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

nå kan Vi starte en variabel for å trekke fra vår opprinnelige entropi.

to_subtract = 0

da vil vi iterere gjennom hver delmengde opprettet av vår splitt, beregne sannsynligheten for delmengden, og deretter legge til produktet av sannsynligheten og delmengdene målkolonens entropi.

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

Til Slutt kan vi returnere forskjellen på to_subract som trekkes fra den opprinnelige entropien.

return original_entropy - to_subtract

hele funksjonen er under.

En Python-Funksjon for Den Høyeste Informasjonsgevinsten

Vår endelige funksjon vil være en som vil returnere variabelen / kolonnenavnet med den høyeste informasjonsgevinsten.

som nevnt tidligere bruker vi bare kolonnene med to unike verdier for dette eksemplet. Vi lagrer disse kolonnenavnene i en liste som skal brukes i funksjonen. For å komme til det punktet vil vi hardt kode dette for dette eksemplet, men i et stort datasett, ville det være best å skrive kode for å bygge denne listen dynamisk basert på kriteriene vi bruker til å velge kolonnene.

columns = 

la oss pakke det siste trinnet i en funksjon slik at vi kan gjenbruke det etter behov. Det vil ha en parameter, listen over kolonner vi vil finne den høyeste informasjonsgevinsten for.

def highest_info_gain(columns):

Vi vil intialisere en tom ordbok for å lagre våre informasjonsgevinster.

information_gains = {}

Og så kan vi iterere gjennom listen over kolonner og lagre resultatet i vår information_gains ordbok.

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

Endelig kan vi returnere nøkkelen til den høyeste verdien i vår ordbok.

return max(information_gains, key=information_gains.get)

Alle sammen nå:

når vi utfører vår endelige funksjon

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

vi ser variabelen / kolonnen med den høyeste informasjon gevinst er ‘sushi?’.

vi kan visualisere en splitt på sushi nedenfor:

vår venstre splitt har to personer ut av seks fra midtvesten. Høyre split har åtte av de ni personer fra midtvesten. Dette var en effektiv splitt og senket vår entropi på begge sider. Hvis vi skulle fortsette, ville vi bruke rekursjon for å fortsette å splitte hver splitt med et mål å avslutte hver gren med en entropi på null.

Konklusjon

Beslutningstrær kan være en nyttig maskinlæringsalgoritme for å plukke opp ikke-lineære interaksjoner mellom variabler i dataene. I dette eksemplet så vi på begynnelsen stadier av en beslutning treet klassifisering algoritme. Vi så på tre informasjonsteori begreper, entropi, bit, og informasjon gevinst. Ved å bruke disse konseptene kunne vi bygge noen funksjoner i Python for å bestemme hvilke variabler/kolonner som var mest effektive å dele på. Med en fast forståelse av disse konseptene, kan vi gå videre for å bygge et beslutningstre.