Een simpele blik op enkele van de belangrijkste Informatie in Theorie concepten en hoe ze te gebruiken bij het bouwen van een Decision Tree Algoritme.
welke criteria moet een beslissingsboomalgoritme gebruiken om variabelen/kolommen te splitsen?
voordat u een beslissingsboomalgoritme bouwt, moet u eerst deze vraag beantwoorden. Laten we eens kijken naar een van de manieren om deze vraag te beantwoorden. Om dit te doen moeten we begrijpen een gebruik van een paar sleutelbegrippen uit de informatietheorie.
laten we deze methode onderzoeken door de volgende stappen te nemen:
- bekijk heel kort wat een beslissingsboom is.
- definieer en onderzoek de formule voor entropie.
- bespreek wat een Bit is in de informatietheorie.
- definieer Informatiewinst en gebruik entropie om deze te berekenen.
- schrijf enkele basis Python functies met behulp van de bovenstaande concepten.
in data science is het beslissingsboomalgoritme een begeleid leeralgoritme voor classificatieproblemen of regressieproblemen. Ons einddoel is om historische gegevens te gebruiken om een uitkomst te voorspellen. In tegenstelling tot lineaire regressie, kunnen beslissingsbomen niet-lineaire interacties tussen variabelen in de gegevens oppikken.
laten we eens kijken naar een zeer eenvoudige beslissingsboom. Hieronder is een workflow die kan worden gebruikt om een beslissing te nemen over het al dan niet eten van een pindakaas cookie.
in dit voorbeeld kan een beslissingsboom zien dat u het cookie alleen moet eten als aan bepaalde criteria wordt voldaan. Dit is het uiteindelijke doel van een beslissingsboom. We willen beslissingen blijven nemen(splitsingen) totdat aan bepaalde criteria is voldaan. Eenmaal ontmoet kunnen we het gebruiken om te classificeren of een voorspelling te doen. Dit voorbeeld is zeer basic met behulp van slechts twee variabelen (allergie, ruïneren diner). Maar, als je een dataset hebt met duizenden variabelen/kolommen hoe beslis je dan welke variabelen / kolommen het meest efficiënt zijn om op te splitsen? Een populaire manier om dit probleem op te lossen, vooral als het gebruik van een ID3-algoritme, is het gebruik van entropie en informatiewinst.
de taak
laten we zeggen dat we wat gegevens hebben en dat we deze willen gebruiken om een online quiz te maken die iets voorspelt over de quiz nemer. Na het bekijken van de relaties in de data hebben we besloten om een beslissingsboom algoritme te gebruiken. Als je nog nooit meegezogen bent in een online quiz, kun je hier honderden voorbeelden zien. Het doel van de quiz zal zijn om te raden of de quiz nemer is uit een van Amerika ‘ s midwest Staten. De vragen in de quiz draait om of ze van een bepaald soort voedsel houden of niet. Hieronder staat een kleine fictieve dataset met vijftien ingangen. Elk item heeft antwoorden op een reeks vragen. De meeste vragen gaan over of ze graag een bepaald type voedsel, waarin de deelnemer antwoordde (1) Voor ja of (0) voor nu. De laatste column (“midwest?”) is onze doelkolom, wat betekent dat zodra de beslissingsboom is gebouwd, dit de classificatie is die we proberen te raden.
entropie
om te beginnen zullen we een informatietheoretische metriek gebruiken die entropie wordt genoemd. In data science wordt entropie gebruikt als een manier om te meten hoe “gemengd” een kolom is. Specifiek, entropie wordt gebruikt om wanorde te meten. Laten we beginnen met het vinden van de entropie van onze doel kolom, “midwest?”.
er wonen tien mensen in het Midwesten en vijf mensen die dat niet doen. als iemand je zou vragen hoe gemengd de kolom is, zou je kunnen zeggen dat het een soort mix was, met een meerderheid(2/3) van de mensen uit het Midwesten. Entropie geeft ons een manier om het antwoord” soort van gemengd”te kwantificeren. Hoe meer de (1)s en (0)s in de kolom gemengd zijn, hoe hoger de entropie. Als ” midwest?”had gelijke hoeveelheden (1)s en (0)s onze entropie zou 1 zijn. Als ” midwest?”bestond alleen uit (1)s de entropie zou 0 zijn.
We kunnen de volgende formule gebruiken om entropie te berekenen:
laten we elke stap van de formule doorlopen en de entropie berekenen voor de “Midwest?” kolom.
- We moeten elke unieke waarde in een enkele kolom herhalen en deze toewijzen aan i. Voor dit voorbeeld hebben we 2 gevallen (c) in de ” midwest?”kolom, hetzij (0) of (1).
- we berekenen dan de kans dat die waarde in de gegevens voorkomt. Voor het geval van (1) is de kans 10/15. Voor het geval van (0) is de kans 5/15.
- We nemen de waarschijnlijkheid van elk geval en vermenigvuldigen het met de logaritme basis 2 van de waarschijnlijkheid. 2 is de meest voorkomende base omdat entropie wordt gemeten in bits (daarover later meer). De volledige uitleg waarom 2 wordt gebruikt valt buiten het bereik van dit bericht, maar een gebruiker op stack exchange biedt een goede uitleg. Voor het geval van(1) krijgen we 10/15*log2 (10/15). Voor het geval van (0) krijgen we 5/15*log2(5/15).
- vervolgens nemen we ons product uit elk geval hierboven en tellen het samen. Voor dit voorbeeld, 10/15 * log2(10/15) + 5/15*log2 (5/15).
- ten slotte ontkennen we de totale som van boven, – (10/15 * log2 (10/15) + 5/15 * log2 (5/15)).
Zodra we de stappen die wij allemaal samen voor de hieronder:
Onze laatste entropie is .918278. Dus, wat betekent dat echt?
informatietheorie en een beetje informatie
in de toekomst zal het belangrijk zijn om het begrip bit te begrijpen. In de informatietheorie wordt een bit gezien als een binair getal dat 0 vertegenwoordigt voor geen informatie en 1 voor een volledig bit. We kunnen een beetje informatie weergeven als een binair getal omdat het ofwel de waarde (1) of (0) heeft. Stel dat er een gelijke kans is dat het morgen regent (1) of niet regent (0). Als ik je vertel dat het morgen gaat regenen, heb ik je een beetje informatie gegeven.
We kunnen entropie ook als informatie beschouwen. Stel dat we een geladen zeszijdige dobbelsteen hebben die altijd op (3) landt. Elke keer dat we de dobbelsteen rollen, weten we vooraf dat het resultaat zal zijn (3). We krijgen geen nieuwe informatie door de dobbelsteen te rollen, dus entropie is 0. Aan de andere kant, als de dobbelsteen is ver en we rollen a (3) was er een 1/6 kans in het rollen van de (3). Nu hebben we informatie. Dus, het rollen van de dobbelsteen geeft ons een beetje informatie-aan welke kant het nummer landde op.
voor een diepere duik in het concept van een beetje informatie, kunt u hier meer lezen.
we krijgen minder dan één” bit ” van alleen informatie .918278-omdat er meer (1)s in de ” midwest?”kolom dan (0)s. dit betekent dat als we een nieuwe waarde zouden voorspellen, we zouden kunnen raden dat het antwoord (1) is en vaker gelijk dan verkeerd (omdat er een 2/3 kans is dat het antwoord 1 is). Door deze voorkennis krijgen we minder dan een volledige “bit” aan informatie wanneer we een nieuwe waarde waarnemen.
entropie gebruiken om beslissingen te nemen
ons doel is om de beste variabele(s) / kolom(s) te vinden om op te splitsen bij het bouwen van een beslissingsboom. Uiteindelijk willen we de variabelen/kolommen blijven splitsen totdat onze gemengde doelkolom niet langer gemengd is.
bijvoorbeeld, laten we eens kijken naar de entropie van de ” midwest?”kolom nadat we onze dataset op de “potato_salad?” kolom.
hierboven is onze dataset opgesplitst in twee secties. Aan de linkerkant, iedereen die van aardappelsalade houdt. Aan de rechterkant iedereen die dat niet doet. we vullen de focus op de linkerkant die nu zeven mensen uit het Midwesten heeft en twee mensen die dat niet zijn. door de formule voor entropie te gebruiken in de linker gesplitste midwest kolom is de nieuwe entropie .764204. Dit is geweldig! Ons doel is om de entropie te verlagen en we gingen van .918278 tot .764204. Maar, we kunnen hier niet stoppen, als we kijken naar de rechter kolom onze entropie ging omhoog omdat er een gelijke hoeveelheid van (1)s en (0)s. wat we nodig hebben is een manier om te zien hoe de entropie verandert aan beide zijden van de splitsing. De formule voor informatiewinst zal dat doen. Het geeft ons een aantal om te kwantificeren hoeveel bits informatie we hebben opgedaan elke keer dat we onze gegevens splitsen.
Informatieversterking
eerder hebben we vastgesteld dat we splitsingen willen die de entropie van onze doelkolom verlagen. Toen we splitsten op ” potato_salad? we zagen die entropie in het Midwesten?”ging naar beneden aan de linkerkant. Nu moeten we begrijpen dat de totale entropie verlaagd is als we naar beide kanten van de splitsing kijken. Laten we eens kijken naar informatieverwerving.
Informatieversterking gebruikt de volgende formule:
Let de ineenstorting wat hier gaande is.
We gaan terug naar onze ” potato_salad?” bijvoorbeeld. De variabelen in de bovenstaande formule vertegenwoordigen het volgende:
- T = Target, onze ” midwest?”column
- A = de variabele (kolom) die we testen,” potato_salad?”
- v = elke waarde in A, elke waarde in de ” potato_salad?”column
- eerst berekenen we de orginale entropie voor (T) voor de splitsing , .918278
- vervolgens berekenen we voor elke unieke waarde (v) in variabele (A) het aantal rijen waarin (A) de waarde (v) aanneemt en delen we deze door het totale aantal rijen. Voor de ” potato_salad?”kolom krijgen we 9/15 voor de unieke waarde van (1) en 6/15 voor de unieke waarde van (0).
- vervolgens vermenigvuldigen we de resultaten met de entropie van de rijen waar (A) (v) is. Voor de linker split (split op 1 Voor ” potato_salad?”) we krijgen 9/15 * .764204. Voor de rechterkant van de split (split op 0 voor ” potato_salad?”) we krijgen 6/15 * 1.
- we voegen al deze subsetproducten bij elkaar, 9/14*.764204 + 6/15 = .8585224.
5. We trekken dan af van de totale entropie om informatie te krijgen, .918278 -.8585224 = .059754
onze informatiewinst is .059754. Wat zegt ons dat?
Hier is een alternatieve uitleg. We vinden de entropie van elke set na de splitsing, wegen het met het aantal items in elke splitsing, dan aftrekken van de huidige entropie. Als het resultaat positief is, hebben we de entropie verlaagd met onze splitsing. Hoe hoger het resultaat is, hoe meer we de entropie hebben verlaagd.
we eindigen met .059754, wat betekent dat we winnen .059754 bits van informatie door het splitsen van onze dataset op de ” potato_salad?”variabele / kolom. Onze informatiewinst is laag, maar het is nog steeds positief, omdat we de entropie aan de linkerkant van de splitsing hebben verlaagd.
nu moeten we dit proces herhalen voor elke kolom die we gebruiken. In plaats van dit met de hand te doen, laten we wat Python code schrijven.
het geheel wordt afgesloten met Python
nu we informatieversterking begrijpen, hebben we een manier nodig om dit proces te herhalen om de variabele / kolom met de grootste informatieversterking te vinden. Om dit te doen, kunnen we een paar eenvoudige functies maken in Python.
importeren van de Data
laten we onze bovenstaande tabel omzetten in een DataFrame met behulp van de Python panda ‘ s bibliotheek. We zullen panda ‘ s importeren en de read_csv() functie gebruiken om een DataFrame te maken met de naam “midwest”.
import pandas as pd
midwest = pd.read_csv('midwes.csv')
een Python-functie voor entropie
voor deze functie hebben we de NumPy-bibliotheek nodig om de bincount () – functie te gebruiken en de math-module om de log () – functie te gebruiken.
import numpy
import math
vervolgens definiëren we onze functie met één parameter. Het gegeven argument zal de reeks, lijst, of NumPy array zijn waarin we proberen de entropie te berekenen.
def calc_entropy(column):
We moeten het percentage van elk geval in de kolom vinden. We kunnen de numpy gebruiken.bincount () functie hiervoor. De return waarde is een NumPy array die de telling van elke unieke waarde uit de kolom die werd doorgegeven als argument zal opslaan.
counts = numpy.bincount(column)
We slaan de waarschijnlijkheden van elke unieke waarde op door de” counts ” array te delen door de lengte van de kolom.
probabilities = counts / len(column)
We kunnen dan een variabele genaamd” entropy ” initialiseren en instellen op 0.
entropy = 0
vervolgens kunnen we een” for loop ” gebruiken om door elke waarschijnlijkheid in onze waarschijnlijkheidsarray te lusenen deze te vermenigvuldigen met de logaritme basis 2 van waarschijnlijkheid met behulp van de wiskunde.log () functie. Voeg vervolgens elk geval toe aan onze opgeslagen entropievariabele. * controleer of je kans groot is dan 0 anders geeft log(0) undefined
for prob in probabilities:
if prob > 0:
endtropy += prob * math.log(prob,2)
ten slotte retourneren we onze negated Entropy variabele.
return -entropy
nu samen:
geweldig! Nu kunnen we een functie bouwen om informatiewinst te berekenen.
een Python-functie voor Informatieversterking
We moeten een functie definiëren die drie parameters heeft, één voor de volledige dataset, één voor de naam van de kolom die we willen splitsen, en één voor de naam van onze doelkolom.
def calc_information_gain(data, split_name, target_name):
vervolgens kunnen we de entropiefunctie van eerder gebruiken om de oorspronkelijke entropie van onze doelkolom te berekenen.
orginal_entropy = calc_entropy(data)
nu moeten we onze kolom splitsen.
*in dit voorbeeld gebruiken we alleen de variabelen / kolommen met twee unieke. Als u wilt splitsen op een variabele/kolom zoals “leeftijd”, zijn er verschillende manieren om dit te doen. Een manier is om te splitsen op elke unieke waarde. Een andere manier is om de berekening van informatiewinst te vereenvoudigen en splitsingen eenvoudiger te maken door niet te splitsen voor elke unieke waarde. In plaats daarvan wordt de mediaan gevonden voor de variabele / coumn die wordt opgesplitst. Alle rijen waar de waarde van de variabele onder de mediaan ligt, gaan naar de linker tak en de rest van de rijen gaat naar de rechter tak. Om informatie te verkrijgen, hoeven we alleen entropieën te berekenen voor twee deelverzamelingen. We zullen niet lopen door deze methode, maar zodra de splitsing op de mediaan wordt uitgevoerd de rest van de stappen zou hetzelfde zijn als hieronder beschreven.
omdat de kolommen waarmee we werken slechts twee unieke waarden hebben, maken we een links-en een rechts-splitsing.
we beginnen met de panda ‘ s.Reeks.unique() om ons een array te geven van de unieke waarden in de kolom
values = data.unique()
vervolgens maken we een links en rechts split met behulp van “values”.
left_split = data == values]
right_split = data == values]
nu kunnen we een variabele initiëren om af te trekken van onze oorspronkelijke entropie.
to_subtract = 0
dan zullen we herhalen door elke subset gemaakt door onze splitsing, berekenen de waarschijnlijkheid van de subset, en voeg dan het product van de waarschijnlijkheid en de entropie van de subsets doel kolom.
for subset in :
prob = (subset.shape / data.shape)
to_subtract += prob * calc_entropy(subset)
ten slotte kunnen we het verschil retourneren dat to_subract wordt afgetrokken van de oorspronkelijke entropie.
return original_entropy - to_subtract
de volledige functie staat hieronder.
een Python-functie voor de hoogste Informatiewinst
onze uiteindelijke functie zal er een zijn die de variabele/kolomnaam met de hoogste informatiewinst retourneert.
zoals eerder vermeld gebruiken we alleen de kolommen met twee unieke waarden voor dit voorbeeld. We slaan die kolomnamen op in een lijst om te gebruiken in de functie. Om tot het punt te komen zullen we dit hard coderen voor dit voorbeeld, maar in een grote dataset, zou het het beste zijn om code te schrijven om deze lijst dynamisch op te bouwen op basis van de criteria die we gebruiken om de kolommen te kiezen.
columns =
laten we de laatste stap in een functie wikkelen zodat we het kunnen hergebruiken als dat nodig is. Het heeft één parameter, de lijst met kolommen waar we de hoogste informatiewinst voor willen vinden.
def highest_info_gain(columns):
We zullen een leeg woordenboek intialiseren om onze informatiewinst op te slaan.
information_gains = {}
en dan kunnen we de lijst met kolommen herhalen en het resultaat opslaan in ons woordenboek information_gains.
for col in columns:
information_gain = calc_information_gain(midwest, col, 'midwest?)
information_gains = information_gain
tenslotte kunnen we de sleutel van de hoogste waarde in ons woordenboek teruggeven.
return max(information_gains, key=information_gains.get)
All together now:
zodra we onze uiteindelijke functie uitvoeren
print(highest_info_gain(midwest, columns, 'midwest?'))
//sushi
zien we de variabele/kolom met de hoogste informatiewinst is ‘sushi?’.
We kunnen hieronder een splitsing op sushi visualiseren:
onze linkersplit heeft twee van de zes mensen uit het Midwesten. De rechter split heeft acht van de negen mensen uit het Midwesten. Dit was een efficiënte splitsing en verlaagde onze entropie aan beide kanten. Als we doorgaan zouden we recursie gebruiken om elke splitsing te blijven splitsen met een doel om elke branch te beëindigen met een entropie van nul.
conclusie
beslissingsbomen kunnen een nuttig algoritme voor machine learning zijn om niet-lineaire interacties tussen variabelen in de gegevens op te pikken. In dit voorbeeld hebben we gekeken naar de beginstadia van een beslissingsboomclassificatie-algoritme. Vervolgens keken we naar drie concepten van de informatietheorie: entropie, bit en informatiewinst. Door deze concepten te gebruiken konden we een paar functies in Python bouwen om te beslissen welke variabelen/kolommen het meest efficiënt waren om op te splitsen. Met een stevige greep op deze concepten, kunnen we vooruit om een besluit boom te bouwen.