Informationsvinst, liksom Gini Impurity, är ett mått som används för att träna beslutsträd. Specifikt mäter dessa mått kvaliteten på en uppdelning. Säg till exempel att vi har följande data:
Vad händer om vi gör en delning vid x=1,5x = 1,5x=1,5?
Denna ofullständiga delning bryter upp datasetetet i dessa grenar:
- Vänstra grenen, med 4 blå.
- Högre gren, med 1 blått och 5 gröna.
Det är tydligt att denna uppdelning inte är optimal, men hur bra är den? Hur kan vi kvantifiera kvaliteten på en uppdelning?
Det är där informationsvinsten kommer in.
Förvirrad? Är du inte säker på vad beslutsträd är eller hur de tränas? Läs början av min introduktion till Random Forests och Decision Trees.
Informationsentropi
För att komma till informationsvinst måste vi först prata om informationsentropi. I samband med utbildning av beslutsträd kan entropi grovt sett betraktas som hur stor varians data har. Till exempel:
- En datamängd med enbart blått skulle ha en mycket låg (i själva verket noll) entropi.
- En datamängd med blandat blått, grönt och rött skulle ha en relativt hög entropi.
Här är hur vi beräknar informationsentropin för ett dataset med CCC-klasser:
E=-∑iCpilog2piE = -\sum_i^C p_i \log_2 p_iE=-i∑Cpilog2pi
där pip_ipi är sannolikheten för att slumpmässigt välja ett element i klass iii (i.d.v.s. den andel av datasetet som utgörs av klass iii).
Det enklaste sättet att förstå detta är med ett exempel. Betrakta ett dataset med 1 blått, 2 grönt och 3 rött: . Då
E=-(pblog2pb+pglog2pg+prlog2pr)E = -(p_b \log_2 p_b + p_g \log_2 p_g + p_r \log_2 p_r)E=-(pblog2pb+pglog2pg+prlog2pr) E=-(16log2(16)+26log2(26)+36log2(36))=1.46\begin{aligned}E &= -(\frac{1}{6} \log_2(\frac{1}{6}) + \frac{2}{6} \log_2(\frac{2}{6}) + \frac{3}{6} \log_2(\frac{3}{6}))) \\&= \boxed{1.46} \\\end{aligned}E=-(61log2(61)+62log2(62)+63log2(63))=1.46
Hur är det med ett dataset med alla en färg? Ta 3 blå färger som exempel: . Entropin skulle vara
E=-(1log21)=0E = -(1 \log_2 1) = \boxed{0}E=-(1log21)=0 Informationsvinst
Det är äntligen dags att besvara den fråga vi ställde tidigare: hur kan vi kvantifiera kvaliteten på en uppdelning?
Låt oss betrakta denna uppdelning igen:
För uppdelningen hade vi 5 blå och 5 gröna, så entropin var
Ebefore=-(0.5log20.5+0.5log20.5)=1\begin{aligned}E_{before} &= -(0,5 \log_2 0,5 + 0,5 \log_2 0,5) \\&= \boxed{1} \\\end{aligned}Ebefore=-(0.5log20.5+0.5log20.5)=1
Efter uppdelningen har vi två grenar.
Vänstra grenen har 4 blåa färger, så Eleft=0E_{left} = \boxed{0}Eleft=0 eftersom det är en datauppsättning av alla en färg.
Den högra grenen har 1 blå och 5 gröna, så
Eright=-(16log2(16)+56log2(56))=0,65\begin{aligned}E_{right} &= -(\frac{1}{6} \log_2 (\frac{1}{6}) + \frac{5}{6} \log_2 (\frac{5}{6}))) \\&= \boxed{0.65} \\\end{aligned}Eright=-(61log2(61)+65log2(65))=0.65
Nu när vi har entropierna för båda grenarna kan vi bestämma kvaliteten på uppdelningen genom att vikta entropin för varje gren med hur många element den har. Eftersom den vänstra grenen har 4 element och den högra grenen har 6, viktar vi dem med 0,40,40,4 respektive 0,60,60,6:
Esplit=0,4∗0+0,6∗0,65=0,39\begin{aligned}E_{split} &= 0,4 * 0 + 0,6 * 0,65 \\&= \boxed{0,39} \\\\end{aligned}Esplit=0.4∗0+0.6∗0.65=0.39
Vi började med Ebefore=1E_{before} = 1Ebefore=1 entropi före spliten och är nu nere på 0.390.390.39! Informationsvinst = hur mycket entropi vi tagit bort, så
Gain=1-0.39=0.61\text{Gain} = 1 – 0.39 = \boxed{0.61}Gain=1-0.39=0.61
Detta är logiskt: högre informationsvinst = mer entropi borttagen, vilket är vad vi vill. I det perfekta fallet skulle varje gren innehålla endast en färg efter uppdelningen, vilket skulle innebära noll entropi!
Sammanfattning
Informationsentropi kan ses som hur oförutsägbar en datamängd är.
- En uppsättning med endast en klass (låt oss säga blått ) är extremt förutsägbar: allt i den är blått. Detta skulle ha låg entropi.
- En uppsättning med många blandade klasser är oförutsägbar: ett givet element kan ha vilken färg som helst! Detta skulle ha hög entropi.
Den egentliga formeln för att beräkna informationsentropi är:
E=-∑iCpilog2piE = -\sum_i^C p_i \log_2 p_iE=-i∑Cpilog2pi
Informationsvinsten beräknas för en uppdelning genom att subtrahera de viktade entropierna för varje gren från den ursprungliga entropin. När man tränar ett beslutsträd med hjälp av dessa mått väljs den bästa uppdelningen genom att maximera informationsvinsten.
Vill du lära dig mer? Kolla in min förklaring av Gini Impurity, ett liknande mått, eller min djupgående guide Random Forests for Complete Beginners.