div >

hvilke kriterier skal en beslutningstræalgoritme bruge til at opdele variabler/kolonner?

før du bygger en beslutningstræalgoritme, er det første skridt at besvare dette spørgsmål. Lad os se på en af måderne at besvare dette spørgsmål på. For at gøre det bliver vi nødt til at forstå en anvendelse et par centrale begreber fra informationsteori.

lad os undersøge denne metode ved at tage følgende trin:

1. tag et meget kort kig på, hvad et beslutningstræ er.
2. definere og undersøge formlen for entropi.
3. Diskuter, hvad der er lidt i informationsteori.
4. Definer Informationsgevinst og brug entropi til at beregne det.
5. Skriv nogle grundlæggende Python-funktioner ved hjælp af ovenstående begreber.

i datalogi er beslutningstræalgoritmen en overvåget læringsalgoritme til klassificering eller regressionsproblemer. Vores endelige mål er at bruge Historiske data til at forudsige et resultat. I modsætning til lineær regression kan beslutningstræer opfange ikke-lineære interaktioner mellem variabler i dataene.

lad os se på et meget simpelt beslutningstræ. Nedenfor er en arbejdsgang, der kan bruges til at træffe en beslutning om, hvorvidt man skal spise en jordnøddesmørkage eller ej.

i dette eksempel kan et beslutningstræ hente det faktum, at du kun skal spise cookien, hvis visse kriterier er opfyldt. Dette er det ultimative mål for et beslutningstræ. Vi vil fortsætte med at træffe beslutninger (splittelser), indtil visse kriterier er opfyldt. Når vi er mødt, kan vi bruge det til at klassificere eller lave en forudsigelse. Dette eksempel er meget grundlæggende ved kun at bruge to variabler ( allergi, ødelægge middag). Men hvis du har et datasæt med tusindvis af variabler/kolonner, hvordan bestemmer du hvilke variabler/kolonner der er mest effektive at opdele på? En populær måde at løse dette problem på, især hvis du bruger en ID3-algoritme, er at bruge entropi og informationsgevinst.

opgaven

lad os sige, at vi har nogle data, og vi vil bruge dem til at lave en online test, der forudsiger noget om testpersonen. Efter at have set på forholdene i dataene har vi besluttet at bruge en beslutningstræalgoritme. Hvis du aldrig er blevet suget ind i en online test, kan du se hundredvis af eksempler her. Målet med undersøgelsen er at gætte, om spørgeren er fra en af Amerikas midtveststater. Spørgsmålene i testen vil dreje sig om, om de kan lide en bestemt type mad eller ej. Nedenfor har et lille fiktivt datasæt med femten poster. Hver post har svar på en række spørgsmål. De fleste spørgsmål handler om, om de kunne lide en bestemt type mad, hvor deltageren svarede (1) For ja eller (0) for nu. Den sidste kolonne (“Midtvesten?”) er vores målkolonne, hvilket betyder, at når beslutningstræet er bygget, er det den klassifikation, vi forsøger at gætte.

entropi

for at komme i gang bruger vi en informationsteori metrisk kaldet entropi. I datalogi bruges entropi som en måde at måle, hvor “blandet” en kolonne er. Specifikt bruges entropi til at måle lidelse. Lad os starte med at finde entropien i vores målkolonne, “Midtvesten?”.

Der er ti mennesker, der bor i Midtvesten og fem mennesker, der ikke gør det. hvis nogen skulle spørge dig, hvor blandet kolonnen er, kan du sige, at den var slags blandet, med et flertal(2/3) af befolkningen fra Midtvesten. Entropi giver os en måde at kvantificere svaret på” slags blandet”. Jo mere blandet (1)s og (0) s i søjlen er, desto højere er entropien. Hvis ” Midtvesten?”havde lige store mængder af (1)s og (0) S ville vores entropi være 1. Hvis ” Midtvesten?”bestod kun af (1) s entropien ville være 0.

Vi kan bruge følgende formel til at beregne entropi:

lad os gennemgå hvert trin i formlen og beregne entropien for”Midtvesten?” kolonne.

1. Vi er nødt til at gentage gennem hver unik værdi i en enkelt kolonne og tildele den til i. I dette eksempel har vi 2 tilfælde (c) i “Midtvesten?”kolonne, enten (0) eller (1).
2. Vi beregner derefter sandsynligheden for, at denne værdi forekommer i dataene. I tilfælde af (1) er sandsynligheden 10/15. I tilfælde af (0) er sandsynligheden 5/15.
3. Vi tager sandsynligheden for hvert tilfælde og multiplicerer det med logaritmen base 2 af sandsynligheden. 2 er den mest almindelige base, fordi entropi måles i bits(mere om det senere). Den fulde forklaring på, hvorfor 2 bruges, er uden for rammerne af dette indlæg, men en bruger på stakudveksling giver en god forklaring. I tilfælde af(1) får vi 10/15*log2(10/15). I tilfælde af (0) får vi 5/15*log2(5/15).
4. dernæst tager vi vores produkt fra hvert enkelt tilfælde ovenfor og opsummerer det sammen. For dette eksempel 10/15 * log2(10/15) + 5/15*log2 (5/15).
5. endelig negerer vi den samlede sum ovenfra, — (10/15*log2(10/15) + 5/15*log2(5/15)).

Når vi sætter trinene sammen, får vi nedenstående:

div >

vores endelige entropi er .918278. Så, hvad betyder det egentlig?

informationsteori og lidt Information

fremadrettet vil det være vigtigt at forstå begrebet bit. I informationsteori betragtes en smule som et binært tal, der repræsenterer 0 for ingen information og 1 for en hel smule information. Vi kan repræsentere en smule information som et binært tal, fordi det enten har værdien (1) eller (0). Antag, at der er lige stor sandsynlighed for, at det regner i morgen (1) eller ikke regner(0). Hvis jeg fortæller dig, at det regner i morgen, har jeg givet dig en smule information.

Vi kan også tænke på entropi som information. Antag, at vi har en lastet seks-sidet matrice, som altid lander på (3). Hver gang vi ruller matricen, ved vi på forhånd, at resultatet bliver (3). Vi får ingen nye oplysninger ved at rulle matricen, så entropi er 0. På den anden side, hvis matricen er langt, og vi ruller en (3) der var en 1/6 chance i rullende (3). Nu har vi fået oplysninger. Dermed, rullende matrisen giver os en smule information-hvilken side nummeret landede på.

for et dybere dykke ind i begrebet lidt information, kan du læse mere her.

Vi får mindre end en “bit” af information — kun .918278-fordi der er flere (1)s i “Midtvesten?”kolonne end (0) s. Dette betyder, at hvis vi forudsagde en ny værdi, kunne vi gætte, at svaret er (1) og være rigtigt oftere end forkert (fordi der er en 2/3 Sandsynlighed for, at svaret er 1). På grund af denne forudgående viden får vi mindre end en fuld “bit” information, når vi observerer en ny værdi.

brug af entropi til at træffe beslutninger

vores mål er at finde de bedste variabler/kolonner, der skal opdeles, når du bygger et beslutningstræ. Til sidst vil vi fortsætte med at opdele variablerne/kolonnerne, indtil vores blandede målkolonne ikke længere er blandet.

lad os for eksempel se på entropien i ” Midtvesten?”kolonne efter at vi har delt vores datasæt på” potato_salad?” kolonne.

ovenfor er vores datasæt opdelt i to sektioner. På venstre side, alle der kan lide kartoffelsalat. På højre side alle, der ikke gør det. vi fylder fokus på venstre side, som nu har syv personer fra Midtvesten og to personer, der ikke er. ved at bruge formlen for entropi i venstre split Midtvesten kolonne den nye entropi er .764204. Det er fantastisk! Vores mål er at sænke entropien, og vi gik fra .918278 til .764204. Men vi kan ikke stoppe der, hvis vi ser på højre kolonne, gik vores entropi op, da der er en lige stor mængde (1)s og (0)s. hvad vi har brug for er en måde at se, hvordan entropien ændres på begge sider af splittelsen. Formlen for information gevinst vil gøre det. Det giver os et tal for at kvantificere, hvor mange bits information vi har fået hver gang vi deler vores data.

Informationsgevinst

tidligere etablerede vi, at vi ønsker splittelser, der sænker entropien i vores målkolonne. Når vi delt på “potato_salad?”vi så den entropi i” Midtvesten?”gik ned på venstre side. Nu skal vi forstå den samlede entropi sænket, når vi ser på begge sider af splittelsen. Lad os tage et kig på information gain.

Informationsgevinst bruger følgende formel:

lad os nedbryde, hvad der foregår her.

Vi går tilbage til vores ” potato_salad?” eksempel. Variablerne i ovenstående formel repræsenterer følgende:

• t = mål, vores ” Midtvesten?”kolonne
• A = variablen (kolonne) vi tester, “potato_salad?”
• v = hver værdi i A, hver værdi i ” potato_salad?”kolonne

1. først beregner vi den orginale entropi for (T) før splittelsen,.918278
2. derefter beregner vi for hver unik værdi (v) i variabel (a) antallet af rækker, hvor (a) tager værdien (v) og deler den med det samlede antal rækker. For ” potato_salad?”kolonne får vi 9/15 for den unikke værdi af (1) og 6/15 for den unikke værdi af (0).
3. dernæst multiplicerer vi resultaterne med entropien af rækkerne, hvor (A) er (v). Til venstre split( split på 1 for ” potato_salad?”) vi får 9/15*.764204. Til højre side af split ( split på 0 for ” potato_salad?”) vi får 6/15 * 1.
4. Vi tilføjer alle disse delmængde produkter sammen, 9/14*.764204 + 6/15 = .8585224.

5. Vi trækker derefter fra den samlede entropi for at få informationsgevinst, .918278 -.8585224 = .059754

vores information gevinst er .059754. Hvad fortæller det os?

Her er en alternativ forklaring. Vi finder entropien for hvert sæt post-split, vægter det med antallet af elementer i hver split, og trækker derefter fra den nuværende entropi. Hvis resultatet er positivt, har vi sænket entropi med vores split. Jo højere resultatet er, jo mere har vi sænket entropi.

vi ender med .059754, hvilket betyder, at vi vinder .059754 bits information ved at opdele vores datasæt på ” potato_salad?”variabel / kolonne. Vores informationsgevinst er lav, men det er stadig positivt, hvilket skyldes, at vi sænkede entropien på venstre side af splittelsen.

nu skal vi gentage denne proces for hver kolonne, vi bruger. I stedet for at gøre dette i hånden lad os skrive nogle Python kode.

indpakning af det hele med Python

nu hvor vi forstår informationsgevinst, har vi brug for en måde at gentage denne proces for at finde variablen / kolonnen med den største informationsgevinst. For at gøre dette kan vi oprette et par enkle funktioner i Python.

import af dataene

lad os gøre vores ovenstående tabel til en DataFrame ved hjælp af Python pandas-biblioteket. Vi importerer pandaer og bruger funktionen read_csv() til at lave en DataFrame med navnet “Midtvesten”.

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

en Python-funktion til entropi

til denne funktion har vi brug for numpy-biblioteket for at bruge bincount () – funktionen og matematikmodulet til at bruge log () – funktionen.

import numpy
import math

dernæst definerer vi vores funktion med en parameter. Argumentet givet vil være serien, listen eller NumPy array, hvor vi forsøger at beregne entropien.

def calc_entropy(column):

Vi skal finde procentdelen af hvert tilfælde i kolonnen. Vi kan bruge numpy.bincount () funktion til dette. Returværdien er et numpy-array, der gemmer optællingen af hver unik værdi fra den kolonne, der blev sendt som et argument.

counts = numpy.bincount(column)

Vi gemmer sandsynlighederne for hver unik værdi ved at dividere arrayet “tæller” med længden af kolonnen.

probabilities = counts / len(column)

Vi kan derefter initialisere en variabel med navnet “entropi” og indstille den til 0.

entropy = 0

dernæst kan vi bruge en “for loop” til at løbe gennem hver Sandsynlighed i vores sandsynlighedsarray og multiplicere den med logaritmen base 2 af sandsynlighed ved hjælp af matematikken.log () funktion. Tilføj derefter hvert tilfælde til vores lagrede entropivariabel. * sørg for at kontrollere, at din sandsynlighed er stor end 0 ellers vil log(0) returnere udefineret

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

endelig returnerer vi vores negerede entropivariabel.

return -entropy

alt sammen nu:

fantastisk! Nu kan vi opbygge en funktion til beregning af informationsgevinst.

en Python-funktion til Informationsgevinst

Vi bliver nødt til at definere en funktion, der har tre parametre, en for hele datasættet, en for navnet på den kolonne, vi vil opdele, og en for navnet på vores målkolonne.

def calc_information_gain(data, split_name, target_name):

dernæst kan vi bruge entropifunktionen fra tidligere til at beregne den oprindelige entropi i vores målkolonne.

orginal_entropy = calc_entropy(data)

nu skal vi opdele vores kolonne.

*i dette eksempel bruger vi kun variablerne/kolonnerne med to unikke. Hvis du vil opdele på en variabel/kolonne som “alder”, er der flere måder at gøre dette på. En måde er at opdele på hver unik værdi. En anden måde er at forenkle beregningen af informationsgevinst og gøre splittelser enklere ved ikke at opdele for hver unik værdi. I stedet findes medianen for variablen/coumn, der opdeles på. Alle rækker, hvor værdien af variablen er under medianen, går til venstre gren, og resten af rækkerne går til højre gren. For at beregne informationsgevinst skal vi kun beregne entropier for to undergrupper. Vi går ikke gennem denne metode, men når opdelingen på medianen er udført, vil resten af trin være den samme som beskrevet nedenfor.

da de kolonner, vi arbejder med, kun har to unikke værdier, foretager vi en venstre opdeling og en højre opdeling.

Vi starter med at bruge pandaerne.Række.unik () for at give os en række af de unikke værdier i kolonnen

values = data.unique()

dernæst opretter vi en venstre og højre opdeling ved hjælp af “værdier”.

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

nu kan vi starte en variabel til at trække fra vores oprindelige entropi.

to_subtract = 0

så gentager vi gennem hver delmængde oprettet af vores split, beregner sandsynligheden for delmængden og tilføjer derefter produktet af sandsynligheden og delmængderne målkolonnens entropi.

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

endelig kan vi returnere forskellen på to_subract, der trækkes fra den oprindelige entropi.

return original_entropy - to_subtract

hele funktionen er nedenfor.

en Python-funktion til den højeste Informationsgevinst

vores endelige funktion vil være en, der returnerer variablen/kolonnenavnet med den højeste informationsgevinst.

som tidligere nævnt bruger vi kun kolonnerne med to unikke værdier til dette eksempel. Vi gemmer disse kolonnenavne på en liste, der skal bruges i funktionen. For at komme til det punkt vil vi hårdt kode dette for dette eksempel, men i et stort datasæt ville det være bedst at skrive kode for at opbygge denne liste dynamisk baseret på de kriterier, vi bruger til at vælge kolonnerne.

columns = 

lad os pakke det sidste trin i en funktion, så vi kan genbruge det efter behov. Det vil have en parameter, listen over kolonner, vi ønsker at finde den højeste informationsgevinst for.

def highest_info_gain(columns):

Vi initialiserer en tom ordbog for at gemme vores informationsgevinster.

information_gains = {}

og så kan vi gentage gennem listen over kolonner og gemme resultatet i vores informations_gains ordbog.

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

endelig kan vi returnere nøglen til den højeste værdi i vores ordbog.

return max(information_gains, key=information_gains.get)

alt sammen nu:

Når vi udfører vores endelige funktion

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

Vi ser variablen/kolonnen med

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

den højeste information gevinst er ‘Sushi?’.

Vi kan visualisere en splittelse på sushi nedenfor:

vores venstre split har to personer ud af seks fra Midtvesten. Den rigtige opdeling har otte ud af de ni personer fra Midtvesten. Dette var en effektiv splittelse og sænkede vores entropi på begge sider. Hvis vi skulle fortsætte, ville vi bruge rekursion til at fortsætte med at opdele hver splittelse med et mål om at afslutte hver gren med en entropi på nul.

konklusion

beslutningstræer kan være en nyttig maskinlæringsalgoritme til at hente ikke-lineære interaktioner mellem variabler i dataene. I dette eksempel, vi kiggede på begyndelsesstadierne i en beslutningstræklassificeringsalgoritme. Vi kiggede derefter på tre informationsteori begreber, entropi, bit og informationsgevinst. Ved at bruge disse begreber var vi i stand til at opbygge et par funktioner i Python for at bestemme, hvilke variabler/kolonner der var mest effektive at opdele på. Med en fast forståelse af disse begreber kan vi gå videre til at opbygge et beslutningstræ.