låt oss gå igenom varje steg i formeln och beräkna entropin för ”Midwest?” kolumn.

1. Vi måste iterera genom varje unikt värde i en enda kolumn och tilldela det till i. För det här exemplet har vi 2 Fall (c) i ”midwest?”kolumn, antingen (0) eller (1).
2. vi beräknar sedan sannolikheten för att värdet inträffar i data. För fallet med (1) är sannolikheten 10/15. För fallet med (0) är sannolikheten 5/15.
3. vi tar sannolikheten för varje fall och multiplicerar den med logaritmbasen 2 av sannolikheten. 2 är den vanligaste basen eftersom entropi mäts i bitar(mer om det senare). Den fullständiga förklaringen till varför 2 används är utanför ramen för detta inlägg, men en användare på stack exchange erbjuder en bra förklaring. För fallet med (1) får vi 10/15*log2(10/15). För fallet med (0) får vi 5/15*log2(5/15).
4. därefter tar vi vår produkt från varje fall ovan och summerar den tillsammans. För detta exempel, 10/15 * log2(10/15) + 5/15*log2 (5/15).
5. slutligen negerar vi den totala summan ovanifrån, — (10/15*log2(10/15) + 5/15*log2(5/15)).

När vi sätter stegen tillsammans får vi nedan:

vår slutliga entropi är .918278. Så, vad betyder det egentligen?

informationsteori och lite Information

framåt är det viktigt att förstå begreppet bit. I informationsteori betraktas en bit som ett binärt tal som representerar 0 för ingen information och 1 för en fullständig bit av information. Vi kan representera lite information som ett binärt tal eftersom det antingen har värdet (1) eller (0). Antag att det finns lika stor sannolikhet för att det regnar imorgon (1) eller inte regnar(0). Om jag säger att det kommer att regna imorgon, har jag gett dig en bit information.

Vi kan också tänka på entropi som information. Antag att vi har en laddad sexsidig dö som alltid landar på (3). Varje gång vi rullar tärningen vet vi på förhand att resultatet blir (3). Vi får ingen ny information genom att rulla munstycket, så entropi är 0. Å andra sidan, om munstycket är långt och vi rullar en (3) fanns det en 1/6 chans att rulla (3). Nu har vi fått information. Således ger rullande munstycket oss en bit information – vilken sida numret landade på.

för ett djupare dyk i begreppet lite information kan du läsa mer här.

vi får mindre än en ”bit” av information — bara .918278-eftersom det finns fler (1)s i ”midwest?”kolumn än (0) s. det betyder att om vi förutspådde ett nytt värde kunde vi gissa att svaret är (1) och vara rätt oftare än fel (eftersom det finns en 2/3 Sannolikhet för att svaret är 1). På grund av denna förkunskap får vi mindre än en fullständig ”bit” information när vi observerar ett nytt värde.

använda entropi för att fatta beslut

vårt mål är att hitta den bästa variabeln/kolumnerna att dela på när man bygger ett beslutsträd. Så småningom vill vi fortsätta dela variablerna/kolumnerna tills vår blandade målkolumn inte längre är blandad.

låt oss till exempel titta på entropin i ” midwest?”Kolumn Efter att vi har delat vår dataset på” potato_salad?” kolumn.

ovan är vår dataset uppdelad i två sektioner. På vänster sida, alla som gillar potatisallad. På höger sida alla som inte gör det. vi fyller fokus på vänster sida som nu har sju personer från mellanvästern och två personer som inte är det. genom att använda formeln för entropi på vänster delad mellanvästkolumn är den nya entropin .764204. Det här är fantastiskt! Vårt mål är att sänka entropin och vi gick från .918278 till .764204. Men vi kan inte stanna där, om vi tittar på den högra kolumnen gick vår entropi upp eftersom det finns lika mycket (1)s och (0)s. vad vi behöver är ett sätt att se hur entropin förändras på båda sidor av splittringen. Formeln för informationsvinst kommer att göra det. Det ger oss ett nummer för att kvantifiera hur många bitar av information vi har fått varje gång vi delar upp våra data.

Informationsvinst

tidigare etablerade vi att vi vill ha splittringar som sänker entropin i vår målkolumn. När vi delar på ” potato_salad?”vi såg den entropin i” Mellanvästern?”gick ner på vänster sida. Nu måste vi förstå den totala entropin sänkt när vi tittar på båda sidor av splittringen. Låt oss ta en titt på informationsvinst.

information gain kommer att använda följande formel:

låt oss bryta ner vad som händer här.

vi går tillbaka till vår ”potato_salad?” exempel. Variablerna i ovanstående formel representerar följande:

• t = Target, vår ” midwest?”kolumn
• A = variabeln (kolumnen) vi testar,” potato_salad?”
• v = varje värde i A, varje värde i ” potato_salad?”kolumn

1. först beräknar vi den ursprungliga entropin för (T) före splittringen,.918278
2. sedan beräknar vi för varje unikt värde (v) i variabel (A) antalet rader där (A) tar värdet (v) och delar det med det totala antalet rader. För ” potato_salad?”kolumn vi får 9/15 för det unika värdet av (1) och 6/15 för det unika värdet av (0).
3. därefter multiplicerar vi resultaten med entropin av raderna där (A) är (v). För vänster split (split på 1 för ”potato_salad?”) vi får 9/15*.764204. För den högra sidan av split (split på 0 för ”potato_salad?”) vi får 6/15 * 1.
4. vi lägger till alla dessa delmängdsprodukter tillsammans, 9/14*.764204 + 6/15 = .8585224.

5. Vi subtrahera sedan från den totala entropin för att få information vinst,.918278 -.8585224 = .059754

vår informationsvinst är .059754. Vad säger Det oss?

här är en alternativ förklaring. Vi hittar entropin för varje uppsättning post-split, väger den med antalet objekt i varje split och subtraherar sedan från den aktuella entropin. Om resultatet är positivt har vi sänkt entropi med vår splittring. Ju högre resultatet är desto mer har vi sänkt entropi.

vi slutar med .059754, vilket innebär att vi får .059754 bitar av information genom att dela upp vår datamängd på ” potato_salad?”variabel / kolumn. Vår informationsvinst är låg, men det är fortfarande positivt vilket beror på att vi sänkte entropin på vänster sida av splittringen.

nu måste vi upprepa denna process för varje kolumn vi använder. Istället för att göra detta för hand låt oss skriva lite Python-kod.

förpacka allt med Python

Nu när vi förstår informationsvinst behöver vi ett sätt att upprepa denna process för att hitta variabeln/kolumnen med den största informationsvinsten. För att göra detta kan vi skapa några enkla funktioner i Python.

importera Data

låt oss göra vår ovanstående tabell till en DataFrame med Python pandas-biblioteket. Vi importerar pandor och använder funktionen read_csv () för att skapa en DataFrame med namnet ”midwest”.

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

en Python-funktion för entropi

För den här funktionen behöver vi numpy-biblioteket för att använda bincount () – funktionen och math-modulen för att använda log () – funktionen.

import numpy
import math

därefter definierar vi vår funktion med en parameter. Argumentet som ges kommer att vara Serien, listan eller NumPy-arrayen där vi försöker beräkna entropin.

def calc_entropy(column):

Vi måste hitta procentandelen av varje fall i kolumnen. Vi kan använda numpy.bincount () funktion för detta. Returvärdet är en NumPy-array som lagrar räkningen av varje unikt värde från kolumnen som skickades som ett argument.

counts = numpy.bincount(column)

Vi lagrar sannolikheten för varje unikt värde genom att dividera matrisen” counts ” med kolumnens längd.

probabilities = counts / len(column)

Vi kan sedan initiera en variabel som heter” entropi ” och ställa in den till 0.

entropy = 0

därefter kan vi använda en” för loop ” för att slinga genom varje Sannolikhet i vår sannolikhetsgrupp och multiplicera den med logaritmbasen 2 av sannolikhet med hjälp av matematiken.logga () funktion. Lägg sedan till varje fall i vår lagrade entropivariabel. * var noga med att kontrollera att din sannolikhet är stor än 0 annars kommer log(0) att returnera odefinierad

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

slutligen returnerar vi vår negerade entropivariabel.

return -entropy

alla tillsammans nu:

bra! Nu kan vi bygga en funktion för att beräkna informationsvinst.

en Python-funktion för Informationsvinst

Vi måste definiera en funktion som har tre parametrar, en för hela datasetet, en för namnet på kolumnen vi vill dela på och en för namnet på vår målkolumn.

def calc_information_gain(data, split_name, target_name):

därefter kan vi använda funktionen entropi från tidigare för att beräkna den ursprungliga entropin i vår målkolumn.

orginal_entropy = calc_entropy(data)

nu måste vi dela upp vår kolumn.

*i det här exemplet använder vi bara variablerna/kolumnerna med två unika. Om du vill dela på en variabel/kolumn som ”ålder” finns det flera sätt att göra detta. Ett sätt är att dela på varje unikt värde. Ett annat sätt är att förenkla beräkningen av informationsvinst och göra splittringar enklare genom att inte dela för varje unikt värde. Istället hittas medianen för variabeln/coumn som delas på. Alla rader där värdet på variabeln ligger under medianen går till vänster gren och resten av raderna går till höger gren. För att beräkna informationsvinst behöver vi bara beräkna entropier för två delmängder. Vi kommer inte att gå igenom den här metoden men när delningen på medianen utförs skulle resten av stegen vara densamma som beskrivs nedan.

eftersom kolumnerna vi arbetar med bara har två unika värden kommer vi att göra en vänster split och en höger split.

vi börjar med att använda pandorna.Rad.unik () för att ge oss en matris med de unika värdena i kolumnen

values = data.unique()

därefter skapar vi en vänster och höger delning med ”värden”.

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

Nu kan vi initiera en variabel för att subtrahera från vår ursprungliga entropi.

to_subtract = 0

sedan kommer vi att iterera genom varje delmängd skapad av vår split, beräkna sannolikheten för delmängden och lägg sedan till produkten av sannolikheten och delmängderna målkolumnens entropi.

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

slutligen kan vi returnera skillnaden mellan to_subract som subtraheras från den ursprungliga entropin.

return original_entropy - to_subtract

hela funktionen är nedan.

en Python-funktion för den högsta Informationsvinsten

vår slutliga funktion kommer att vara en som returnerar variabeln/kolumnnamnet med den högsta informationsvinsten.

som tidigare nämnts använder vi bara kolumnerna med två unika värden för detta exempel. Vi lagrar dessa kolumnnamn i en lista som ska användas i funktionen. För att komma till den punkten kommer vi svårt att koda detta för det här exemplet men i en stor dataset är det bäst att skriva kod för att bygga den här listan dynamiskt baserat på de kriterier vi använder för att välja kolumnerna.

columns = 

låt oss slå in det sista steget i en funktion så att vi kan återanvända det efter behov. Det kommer att ha en parameter, listan över kolumner vi vill hitta den högsta informationsvinsten för.

def highest_info_gain(columns):

vi initierar en tom ordbok för att lagra våra informationsvinster.

information_gains = {}

och sedan kan vi iterera genom listan över kolumner och lagra resultatet i vår information_gains-ordbok.

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

slutligen kan vi returnera nyckeln till det högsta värdet i vår ordbok.

return max(information_gains, key=information_gains.get)

alla tillsammans nu:

När vi utför vår slutliga funktion

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

Vi ser variabeln / kolumnen med den högsta informationsvinsten är ’sushi?’.

Vi kan visualisera en splittring på sushi nedan:

vår vänstra Split har två personer av sex från mellanvästern. Rätt split har åtta av de nio personer från Mellanvästern. Detta var en effektiv splittring och sänkte vår entropi på båda sidor. Om vi skulle fortsätta skulle vi använda rekursion för att fortsätta dela varje delning med ett mål att avsluta varje gren med en entropi på noll.

slutsats

beslutsträd kan vara en användbar maskininlärningsalgoritm för att plocka upp icke-linjära interaktioner mellan variabler i data. I det här exemplet tittade vi på början av en beslutsträdklassificeringsalgoritm. Vi tittade sedan på tre informationsteoribegrepp, entropi, bit och informationsvinst. Genom att använda dessa begrepp kunde vi bygga några funktioner i Python för att bestämma vilka variabler/kolumner som var mest effektiva att dela på. Med ett fast grepp om dessa begrepp kan vi gå vidare för att bygga ett beslutsträd.