Hallo wereld,
Dit keer ga ik jullie wat uitleggen over decision trees oftewel beslissingsbomen. Want, zonder beslissingsbomen kan je geen random forest maken.
In mijn eerdere bericht over random forests had ik jullie al in grote lijnen uitgelegd hoe deze werken. Zoals ik al zei, decision trees leren data te categoriseren aan de hand van een model met knooppunten en vertakkingen. Bij elk knooppunt word een data punt aan een bepaalde test onderworpen om te beslissen naar welk volgende knooppunt de data gaat voor een volgende test. In het voorbeeld dat ik had gegeven kun je bijvoorbeeld een object hebben met de volgende eigenschappen: snelheid: 9001 km/u, lengte: 2m.
Als we willen weten wat dit is dan kunnen we het testen met onze beslissingsboom. Is de snelheid hoger dan 60 km/u? Ja. Dus is het geen vogel en moeten we de vraag stellen: Is de lengte langer dan 3m? Nee. Dus het is ook geen vliegtuig, het is Superman!
Maar, hoe maak je nou zo’n beslissingsboom? Nou, die in het voorbeeld heb ik gewoon helemaal zelf bedacht. Maar wat als je nou niet zo geweldig slim bent, of de data wat ingewikkelder is? Dan heb je een computer algoritme nodig dat de beslissingsboom voor je maakt op basis van gelabelde data.
Want, het is een supervised learning algoritme, weet je nog? Dat betekent in dit geval dus dat je het moet trainen door het gelabelde data te voeren. We zouden de bovenstaande beslissingsboom dus kunnen genereren door het algoritme een hele hoop datarijen met eigenschappen van vogels, vliegtuigen en superman te voeren. In dit geval data rijen met drie kolommen: snelheid, lengte en een label. Op basis van die data kan het computer algoritme dan een beslissingsboom berekenen die het label kan raden voor nieuwe datapunten.
Hoe goed die beslissingsboom is hangt echter af van de kwaliteit van de data. Zowel de relevantie als de juistheid van de data. Geef je het bijvoorbeeld alleen maar kleuren in plaats van snelheden en lengtes dan zal het het waarschijnlijk een stuk minder goed doen. Ook het verkeerd labelen van de data zal weinig goeds uithalen. En ook geldt vaak: hoe meer data, hoe beter!
Maar hoe werkt dat algoritme dan? Nou, het stappenplan is als volgt:
1. Bereken voor de gegeven dataset voor alle mogelijke criteria (alle mogelijke waardes voor alle variabelen) de kwaliteit van de resulterende splijting van gegevens uit.
2. Kies het criterium uit dat de beste splijting oplevert. (De splijting die de data zo goed mogelijk verdeeld in de gewenste categorieën.) Dit is het criterium voor het eerste knooppunt.
3. Herhaal voor de resulterende datasets totdat alle data compleet zuiver gespleten is in de gewenste categorieën. Dan zijn er dus alleen nog bladeren. (Of als de boom de maximum lengte bereikt heeft.)
Hoe wordt de kwaliteit van de splijting bepaalt? Nou hier zijn verschillende manieren voor. Een ervan is de Gini index. De Gini index is een statistische maatstaf voor de ongelijkheid binnen een verdeling. Hij wordt vooral in de economie gebruikt om de inkomensongelijkheid te berekenen, maar kan ook gebruikt worden om de kwaliteit van de splijting van onze dataset te bepalen. De Gini index is een getal dat een waarde heeft tussen 0 en 1. Een waarde van 0 komt overeen met volkomen gelijkheid, een waarde van 1 met volkomen ongelijkheid. In ons geval komt 0 overeen met een perfecte splijting en 1 overeen met een compleet waardeloze. In het geval van 2 categorieën zou een score van 1 betekenen dat we precies de helft van onze datapunten in de juiste en de andere helft in de onjuiste categorie zouden plaatsen. Daar schieten we dus niets mee op. Een score van 0 daarentegen zou betekenen dat we onze datapunten allemaal in aparte categorieën hebben geplaatst.
Met 3 categorieën, zoals in ons voorbeeld, wordt het iets ingewikkelder en hebben we al minimaal 2 knooppunten nodig om alle data te kunnen categoriseren. De eerste splijting kan namelijk nooit perfect zijn aangezien er 3 categorieën zijn en maar 2 mogelijke subsets. Ook is het lang niet altijd het geval dat we meteen een perfecte splijting vinden, ongeacht het aantal categorieën. We zijn dus bij elke splijting op zoek naar de laagst mogelijke gini index mogelijk en gaan gewoon net zo lang door totdat we de perfecte boom hebben (met een gini index van 0 in elk blad), of dat onze boom te groot wordt.
Een andere veelgebruikte is de information gain (informatie toename). De information gain is een maat voor de afname van entropie in een verzameling. De entropie is gelijk aan 0 voor een compleet homogene verzameling en 1 voor een evenredig verdeelde verzameling. Een toename van de information gain staat gelijk tot een afname van entropie. En dat betekent dus dat de verzameling puurder wordt, wat precies is wat we willen. We willen dat er alleen maar vogels in ons eerste blad terechtkomen, en geen vliegtuigen!
Nu zijn er natuurlijk ook formules voor deze getallen, en om die uit te leggen zou ik makkelijk een heel nieuw bericht kunnen schrijven. Ik ga dit echter voorlopig denk ik niet doen. Wil je weten hoe ze worden uitgerekend, Google is je vriend. Maar ik zal er natuurlijk ook een van gebruiken in mijn eigen implementatie van de random forest wijnproever, aangenomen dat dit gaat lukken. Ik ben er van overtuigd dat ik er uiteindelijk wel uit zal komen, maar hoe lang dit nog gaat duren is moeilijk te zeggen.
Het nadeel van deze beslissingsbomen is wel dat ze de neiging hebben om data te overfitten. Dat wil zeggen, ze leren de trainingsdata zo goed te classificeren dat ze het slecht doen voor nieuwe gegevens, die net wat anders is. Ze leren de oefentoetsen perfect uit hun hoofd, maar weten niet hoe ze andere sommen op moeten lossen. Een oplossing hiervoor is snoeien (pruning). Dat houdt in dat we er gewoon een aantal takken afhalen zodat de boom wat minder gefixeerd is op details. Maar een andere en betere oplossing is het bundelen van een aantal variaties van deze bomen in een random forest. Maar, dat is alles voor nu,
Tot de volgende keer.