Tagarchief: Decision Tree

  • Home   /  
  • Berichten getagd "Decision Tree"

Run Forest Run!

Hallo wereld,

Vandaag kan ik met trots aankondigen dat mijn Random Forest applicatie af is! Ik moet toegeven, ik begon te twijfelen of deze dag ooit nog zou komen. Maar, de aanhouder wint.

Het was echter niet de bedoeling om alleen een Random Forest te maken. De bedoeling was om hem te vergelijken met die van de scikit-learn library. In het bijzonder de applicatie van de EliteDataScience tutorial. Om dat te kunnen doen moest ik nog wat extra aanpassingen maken. Ten eerste moest de data verdeeld worden in een training- en testset. Vervolgens moest alle data gestandaardiseerd worden. Daarnaast moesten er ook nog wat statistische gegevens berekend worden om de prestatie van het algoritme te peilen.

Dit heb ik dan (onder andere) gedaan voor een random forest met 50 bomen met maximale diepte van 20 en een sample grootte van 100. Dat wil zeggen, er zijn 50 beslissingsbomen gemaakt met maximaal 20 lagen van vertakkingen, die gegroeid zijn op basis van 100 willekeurig geselecteerde gegevensrijen uit de trainingset. Daarnaast werden dan ook nog voor elk van die bomen slechts willekeurig 3 kwart van de kolommen geselecteerd. Dit zorgt voor extra variatie tussen de bomen. Deze bomen doen dan elk hun voorspelling en de voorspelling met de meeste stemmen wint.

Het resultaat is een model dat met succes de data van de rode wijn laadt en modelleert, met een r2-score van 0.31 (vs 0.47) en een mean-squared-error van 0.5 (vs 0.33). Ter herhaling, de r2 score geeft aan hoe goed de fit van het model is. De mean-squared-error geeft aan hoe nauwkeurig het model is. Oftewel, mijn model is een slechtere fit en minder nauwkeurig. Dit was echter te verwachten, aangezien mijn model niet automatisch getuned wordt en ik de hyperparameters willekeurig gekozen heb.

Daarnaast heb ik ook de nauwkeurigheid van het model laten uitrekenen, welke 0.67 was. Niet al te slecht dus, het raadt het 2 van de 3 keer goed. Voor het sk-learn model is dit echter niet direct uit te rekenen aangezien deze in tegenstelling tot mijn model geen categorische maar numerieke voorspellingen maakt. Hierdoor zijn alle voorspellingen automatisch niet exact juist, en moet ik dus de afgeronde waardes gebruiken. Als ik dat doe, krijg ik verrassend genoeg een nauwkeurigheid van slechts 0.69. Slechts 2 procent nauwkeuriger dan mijn eigen model!

Hoe dan ook is mijn missie geslaagd. Ik heb mijn eigen Random Forest algoritme gemaakt, en het vergeleken met het model van de EliteDataScience tutorial. Hiermee heb ik niet alleen veel geleerd over de werking van het Random Forest algoritme, ik heb ook mijn vaardigheid met Python enorm verbeterd!

De code kun je hier vinden. Ook heb ik de winesnobloader aangepast om de nauwkeurigheid uit te rekenen. In de toekomst zal ik misschien wat dieper ingaan op de werking en/of wat tutorials geven voor het maken van deze en mijn andere applicaties. Op het moment heb ik echter een probleem met mijn geluidsopname-kwaliteit, dus hoe ik dat ga doen weet ik nog niet. Maar, dat is alles voor nu.

Tot de volgende keer!

 

Worstelen met bomen

Hallo wereld,

Mijn missie om een random forest te maken met Python bleek een stuk lastiger dan ik aanvankelijk had gedacht. Maar, ik heb het nog niet op gegeven. En, hoewel ik er de afgelopen maand een beetje teveel omheen heb gedraaid ben ik er nog steeds mee bezig geweest. En vooral de afgelopen week heb ik weer wat vooruitgang gemaakt.

Na het maken van mijn eerste versie voor een beslissingsboom algoritme had ik namelijk een video met een link naar de voorbeeldcode gevonden op Youtube. In dit voorbeeld wordt ook een beslissingsboom met Python gemaakt, maar de programmeur pakt het toch allemaal net wat beter aan dan ik zelf deed. Het belangrijkste verschil is dat hij gebruikt maakte van recursie, dus ik besloot opnieuw te beginnen en ook een beslissingsboom met recursie te maken. Ik had hierbij het voornemen om alleen de informatie in de video te gebruiken en de voorbeeldcode te negeren.

En, dit was me redelijk goed gelukt, maar toen ik de beslissingsboom net zoals in mijn vorige applicatie probeerde te tekenen raakte ik in de problemen. De bomen werden succesvol gemaakt, wat ik kon zien door het resultaat in tekst te printen, maar om hem (recursief) te tekenen, dat wilde me maar niet lukken. Ondanks mijn vele pogingen.

Als je zelf ervaring hebt met het werken met grote lappen code dan weet je misschien wel hoe moeilijk het kan zijn om een groot project weer op te pakken nadat je er een tijd niet aan gewerkt hebt. Je bent vergeten wat alles ook alweer precies doet, en wat je precies nog allemaal moest doen. Als je dan niet de tijd neemt om je code weer grondig te bestuderen alsof je hem voor het eerst ziet dan kan je veel tijd verspillen. Niets wil werken, je snapt niet waarom, en je staart met frustratie en wanhoop naar je grote lap met code en vraagt je af of je niet beter opnieuw kan beginnen.

Uiteindelijk heb ik dan toch maar de moeite genomen om mijn code weer opnieuw te bestuderen. Regel voor regel. Functie voor functie. En bij al deze functies erbij gezet wat ze ook alweer precies deden. Hierdoor had ik eindelijk weer een goed begrip van hoe alles precies ook alweer werkte en was de code niet zo intimiderend meer.

En toen heb ik toch ook maar de voorbeeldcode erbij gepakt en kwam ik erachter dat daarbij niet eens de moeite werd gedaan om de boom te tekenen. In plaats daarvan werd de boom wel heel netjes met recursie geprint en gebruikt voor het maken van voorspellingen. Deze methodes heb ik dan maar aangepast en aan mijn programma toegevoegd.

Het resultaat is een efficiënte, overzichtelijke en werkende applicatie voor het maken van classificatie (maar geen regressie) bomen. Mocht je vergeten zijn wat dat betekent, het houdt in dat de boom in staat is om data in categorieën te plaatsen, maar nog niet in staat is om (exacte) numerieke voorspellingen te doen.

Aanvankelijk dacht ik regressie nodig zou hebben voor de wijndata, maar nadat ik de moeite had genomen om de data te onderzoeken kwam ik erachter dat er maar vijf verschillende cijfers voor de wijnkwaliteit waren in de gehele dataset: 3 tot en met 8. Dus, het enige wat nu nog te doen staat is het implementeren van deze beslissingsboom in een random forest algoritme. En de resultaten te vergelijken met die van de Random Forest Wijnproever zoals die op EliteDataScience geïmplementeerd was. Zou moeten lukken.

Hoe dan ook ben ik al ver gekomen tijdens het werken aan deze beslissingsboom. Mijn aanvankelijke doel voor dit project was het leren begrijpen en maken van random forests. Tot mijn eigen verbazing las ik zelf in mijn eerste bericht bij dit project terug dat ik nog niet eens van plan was om een Data Scientist te worden op dit punt. Maar, uiteindelijk verschoof het hoofddoel van dit project naar het leren programmeren met Python voor Data Science.

En, ik heb een hele hoop over Python geleerd tijdens het maken van deze beslissingsboom. Het zelf kunnen maken van een random forest is echter niet meer mijn belangrijkste leerdoel, het is slechts een project voor het oefenen met Python. Uiteindelijk is het belangrijker dat ik leer te werken met de libraries van Python voor het analyseren van data en het trainen van machine learning algoritmes. En daar zal ik dan ook na dit project mee verder gaan.

Maar, dat is alles voor nu.

Tot de volgende keer!

Project update: De eerste boompjes

Hallo wereld

Het is weer hoog tijd voor een project update. Mijn missie om een Random Forest te maken in Python gaat nog steeds door. Na uren van het vergroten van mijn kennis over beslissingsbomen, oefenen met Python en prutsen met Python is het me eindelijk gelukt om een werkende applicatie te maken! Er is nog een hele hoop werk te doen, maar de eerste boompjes hebben hun blaadjes gespreid.

Zoals ik al eerder had gezegd, mijn ervaring met Python was beperkt toen ik aan dit project begon. De helft van de uitdaging in dit project zat hem dan ook in het leren om te programmeren met Python. Echter, ik was ook geen complete beginner. Ik had al ervaring met Java en mezelf eerder al genoeg aangeleerd over Python om mijn eerste applicatie te maken: Conway’s Game of Life.

Deze manier van leren programmeren met het maken van een specifieke applicatie in gedachten is in mijn ogen HEEL BELANGRIJK. Want, als je niet weet WAT je wil programmeren en simpelweg het doel stelt om een programmeertaal te leren dan zul je nooit slagen. Je kunt een programmeertaal immers NOOIT helemaal leren! Zelfs een doel als “de basis principes van Python leren” is in mijn ogen nog steeds te vaag en je zult je daarbij eerst eens goed af moeten vragen:

  • Wat zijn die basis principes?
  • Waarom wil ik ze leren?
  • Wat kan ik ermee maken?

Aldus had ik opnieuw het doel om meer over Python te leren met een specifieke applicatie in gedachten. Om dit doel te behalen moest ik wel eerst mijn kennis van de basis syntax een beetje herhalen en aanvullen. Om dat te doen had ik onder andere deze video gekeken, waarin Python in 40 minuten wordt uitgelegd, op advies van EliteDataScience. Wees gewaarschuwd echter, hoewel het meeste wat in deze video wordt uitgelegd best nuttig is, is de kwaliteit niet overal even goed. Aan het eind van de video kwam ik namelijk in de problemen met niet werkende code vanwege een typefout. Nou, dat was mijn eigen schuld natuurlijk, maar toen ik daar op stackoverflow een vraag over stelde kwam ik erachter dat een significant aantal ervaren Python programmeurs de manier waarop hij een aantal dingen deed vrij slecht vonden. In het bijzonder ging het om zijn onhandige manier van het benoemen van variabelen, en zijn manier van het declareren van classes en het implementeren van inheritance. Als geheel is de video echter nog steeds nuttig als spoedcursus, maar wees dus gewaarschuwd dat het niet allemaal even geweldig is.

Daarna ging ik verder met het volgende advies op EliteDataScience. Ze verwezen naar een leuke puzzelpagina waarbij je puzzels kunt oplossen met Python. Hoewel dit in het begin heel leuk was werkte om de een of andere reden een van mijn oplossingen niet helemaal en kon ik de volgende pagina (derde geloof ik?) niet vinden. Ik kwam wel op een of andere forum pagina die mij informeerde dat ik de oplossing juist had, maar de url voor de volgende pagina werkte echter niet voor mij. Dus opnieuw, wees gewaarschuwd.

Maar ja, genoeg daarover. Terug naar het hoofd onderwerp, het project. Waar begin ik? Nou, ik ga er even van uit dat jullie al up-to-date zijn met hoe beslissingsbomen werken. Is dit niet het geval, lees dan misschien beter eerst even mijn eerdere bericht over de werking van beslissingsbomen. De code is te vinden op Github, maar ik denk dat het het handigst is om uit te leggen hoe het allemaal werkt in een video.

Hieronder staat ook nog een selectie van een aantal van de vele bronnen die ik gebruikt heb gedurende dit project tot dusver. Dat is alles voor nu.

 

Tot de volgende keer!

Bronnen:

Een boom tegelijk

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.

Door de bomen het bos zien

Hallo wereld!

Wat zijn random forests?

Hoe werken ze?

Waar worden ze voor gebruikt?

Nou, laat ik eerst een stap terug doen en wat uit leggen over machine learning en decision trees. Random forests zijn namelijk machine learning algoritmes die zijn opgebouwd uit decision trees.

Machine learning

Machine learning is het subgebied binnen kunstmatige intelligentie dat zich bezig houdt met het bedenken en trainen van algoritmes die leren van gegevens. Het zijn programma’s met een aantal variabele parameters die zich aan passen aan een dataset om een zo effectief mogelijk eindprogramma te realiseren.

Het is te vergelijken met de manier waarop wij leren. Op basis van de gebeurtenissen in ons verleden passen wij ons gedrag aan voor de gebeurtenissen in de toekomst.

Soms krijgen wij hier begeleiding bij, van ouders en leraren, die ons vertellen wat we wel of niet moeten of kunnen doen. Op andere momenten zoeken we het zelf uit, met vallen en opstaan. Zo is het ook met machine learning. Je hebt daarbij supervised (onder toezicht) en unsupervised (zonder toezicht) leren. Decision trees (beslissingsbomen) vallen onder de supervised categorie.

Wat houdt dit in?

Nou, je moet het algoritme in principe les geven. Je geeft het een gelabelde dataset, dat wil zeggen een dataset met de gewenste antwoorden bijgevoegd. Bijvoorbeeld een verzameling van plaatjes van honden en katten met de labels hond of kat. Op basis van die gelabelde data kan het algoritme dan leren wat het verschil is tussen honden en katten en nieuwe plaatjes zelf leren categoriseren.

De twee hoofdtaken binnen supervised learning zijn classificatie en regressie. Bij classificatie wordt de data gecategoriseerd, net zoals bij het voorbeeld met honden en katten. Bij regressie wordt er een continue waarde aan toegedeeld. Bijvoorbeeld een algoritme dat de leeftijd van een mens of dier op basis van een foto bepaalt.

 

Decision Trees

Decision trees zijn machine learning algoritmes die leren data te categoriseren aan de hand van een model met knooppunten en vertakkingen. Bij elk knooppunt wordt een datapunt getest op een bepaalde variabele en op basis daarvan wordt bepaald naar welk volgende knooppunt het gaat voor de volgende test. Uiteindelijk komt het dan uit bij een eindknooppunt, een blad (leaf). Hierbij wordt het datapunt dan gelabeld binnen een een bepaalde klasse (of een continue waarde in het geval van regressie).

Een voorbeeld?

Hierbij zijn de vierkanten dan dus de knooppunten, de lijntjes de takken en de rondjes de bladeren. Hoe bepaalt het algoritme wat de criteria zijn waar op getest wordt in de knooppunten?

Brute kracht in principe. Bij elk knooppunt wordt voor elke variabele voor een groot aantal waarden getest tot wat voor split het zou zorgen in de dataset. Uiteindelijk wordt dan gewoon de split gekozen die de data het beste opsplitst. Dit proces wordt herhaald tot de gekozen eindcriteria bereikt worden (bijvoorbeeld de maximale lengte voor de boom).

Decision trees hebben echter de vervelende gewoonte om data te ‘overfitten‘. Ze vormen zichzelf op een manier die heel nauwkeurig de trainingset kan modeleren, maar doen dit zo overdreven dat ze het slecht doen voor nieuwe gegevens. Ze leren de antwoorden in plaats van de patronen. Om dit te voorkomen kun je de decision trees ‘snoeien’. Dit houdt in dat je hem kleiner maakt zodat hij niet te gefocust raakt op de details. Maar er zijn ook andere oplossingen, en een daarvan is het random forest algoritme.

 

Random Forest

Een random forest is precies dat wat de naam al suggereert: een verzameling van (random) beslissingsbomen. Er wordt een verzameling van decision trees gegenereerd met random variaties in de trainingset en input variabelen. Deze decision trees krijgen dan elk een stem. In het geval van classificatie wordt het uiteindelijke antwoord bepaald door de meerderheid van die stemmen. In het geval van regressie wordt het gemiddelde genomen. Op deze manier wordt voorkomen dat het model overfit raakt, iets wat vooral een risico is voor trainingsets met veel variabelen en weinig datapunten. Random forests daarentegen kunnen daar over het algemeen uitstekend mee omgaan.

Dit en het feit dat ze over het algemeen vrij simpel te trainen zijn maakt ze erg populair. Ze doen het vooral goed voor classificatie maar zijn ook geschikt voor regressie. Ze worden gebruikt bij allerlei toepassingen op allerlei gebieden. Ze worden gebruikt door banken om kandidaten voor een lening te beoordelen. Ze worden gebruikt op de beurs om trends te voorspellen. Ze worden gebruikt in computer visie, bijvoorbeeld voor X-box connect. En nog veel meer.

En dat is het!

Simpel nietwaar? Natuurlijk komt er wat meer bij kijken als je zo’n decision tree of random forest zelf wilt implementeren en trainen. Maar daarover later meer. Ik wil er namelijk eerst voor zorgen dat je het grote plaatje duidelijk hebt. Door de bomen het bos zien aldus. Bovendien heb ik de details zelf ook nog niet allemaal op een rijtje. Een boom tegelijk planten en zo. Maar, dat is alles voor nu.

 

Tot de volgende keer!