Informaatiovoitto, kuten Gini-epäpuhtaus, on metriikka, jota käytetään päätöspuiden kouluttamiseen. Tarkemmin sanottuna nämä metriikat mittaavat jaon laatua. Oletetaan esimerkiksi, että meillä on seuraava aineisto:
Mitä jos tekisimme jaon kohdassa x=1.5x = 1.5x=1.5?
Tämä epätäydellinen jako jakaa datakokonaisuutemme seuraaviin haaroihin:
- Vasemmanpuoleinen haarautuminen, jossa on 4 sinistä.
- Oikea haara, jossa on 1 sininen ja 5 vihreää.
On selvää, että tämä jako ei ole optimaalinen, mutta kuinka hyvä se on? Miten voimme kvantifioida hajautuksen laadun?
Tässä kohtaa informaatiovoitto astuu kuvaan.
Hämmentynyt? Etkö tiedä, mitä päätöspuut ovat tai miten niitä koulutetaan? Lue johdantoni alku satunnaismetsistä ja päätöspuista.
Informaatioentropia
Ennen kuin pääsemme informaatiovoittoon, meidän on ensin puhuttava informaatioentropiasta. Päätöspuiden kouluttamisen yhteydessä entropiaa voidaan karkeasti ajatella niin, että se tarkoittaa sitä, kuinka paljon varianssia datassa on. Esimerkiksi:
- Tietoaineistolla, jossa on vain sinisiä sävyjä, olisi hyvin alhainen (itse asiassa nolla) entropia.
- Tietoaineistolla, jossa on sekaisin sinisiä, vihreitä ja punaisia sävyjä, olisi suhteellisen korkea entropia.
Näin lasketaan informaatioentropia tietokokonaisuudelle, jossa on CCC-luokkia:
E=-∑iCpilog2piE = -\sum_i^C p_i \log_2 p_iE=-i∑Cpilog2pi
jossa pip_ipi on todennäköisyys, jolla satunnaisesti poimitaan luokan iii elementti (i.eli luokan iii osuus aineistosta).
Helpoin tapa ymmärtää tämä on esimerkki. Tarkastellaan aineistoa, jossa on 1 sininen, 2 vihreää ja 3 punaista: . Tällöin
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
Entäpä aineisto, jossa kaikki ovat yksivärisiä? Tarkastellaan esimerkkinä 3 sinistä: . Entropia olisi
E=-(1log21)=0E = -(1 \log_2 1) = \boxed{0}E=-(1log21)=0
Informaatiovoitto
Viimein on aika vastata aiemmin esittämäämme kysymykseen: miten voimme mitata jaon laatua?
Katsotaanpa tätä jakoa uudelleen:
Ennen jakoa meillä oli 5 sinistä ja 5 vihreää, joten entropia oli
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
Jakoamisen jälkeen meillä on kaksi haaraa.
Vasemmanpuoleisessa haarassa on 4 sinistä, joten Eleft=0E_{left} = \boxed{0}Eleft=0, koska se on datasetti, jossa on vain yksi väri.
Oikeassa haarassa on 1 sininen ja 5 vihreää, joten
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
Nyt kun meillä on molempien haarojen entropiat, voimme määrittää jaon laadun painottamalla kummankin haaran entropiat sillä, kuinka monta elementtiä sillä on. Koska vasemmanpuoleisessa haarassa on 4 elementtiä ja oikeanpuoleisessa haarassa 6 elementtiä, painotamme niitä vastaavasti 0.40.40.4:llä ja 0.60.60.6:lla:
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
Aloitimme Ebefore=1E_{before} = 1Ebefore=1 entropialla ennen jakautumista ja nyt olemme laskeneet 0.390.390.39! Informaatiovoitto = kuinka paljon entropiaa poistimme, joten
Gain=1-0.39=0.61\text{Gain} = 1 – 0.39 = \boxed{0.61}Gain=1-0.39=0.61
Tässä on järkeä: korkeampi informaatiovoitto = enemmän poistettua entropiaa, mitä me haluamme. Täydellisessä tapauksessa jokainen haara sisältäisi jakamisen jälkeen vain yhden värin, jolloin entropia olisi nolla!
Yhteenveto
Informaatioentropiaa voidaan ajatella niin, että se kertoo, kuinka arvaamaton tietokokonaisuus on.
- joukko, jossa on vain yksi luokka (vaikkapa sininen ), on äärimmäisen ennustettava: kaikki siinä oleva on sinistä. Tällä olisi alhainen entropia.
- Monien sekaluokkien joukko on arvaamaton: tietty elementti voi olla minkä värinen tahansa! Tällä olisi korkea entropia.
Tosiasiallinen kaava informaatioentropian laskemiseksi on:
E=-∑iCpilog2piE = -\sum_i^C p_i \log_2 p_iE=-i∑Cpilog2pi
Informaatiovoitto lasketaan jakaumalle vähentämällä alkuperäisestä entropiasta kummankin haaran painotetut entropiat. Kun päätöspuuta koulutetaan näitä mittareita käyttäen, paras jako valitaan maksimoimalla informaatiovoitto.
Tahdotko oppia lisää? Tutustu selitykseeni Gini Impuritystä, samanlaisesta metriikasta, tai syvälliseen oppaaseeni Random Forests for Complete Beginners.