Practicumopdracht 3: Decision tree learning

Doel van de opdracht

Implementeren van een eenvoudig machine learning algorithme.

Opdracht a

Implementeer het decisiontree-learning algoritme uit figuur 18.7, en met daarin een choose-attribute functie die dat attribuut kiest dat de meeste informatie kan leveren, zoals beschreven wordt in paragraaf 18.4.
De boom uit het boek zal niet gebruikt worden, omdat deze niet binair is. Dit levert veel implementatieproblemen op. De nieuwe boom is wel binair, en staat onderaan deze pagina.
Er is een template in pascal beschikbaar. Deze bevat een attribuut generator, die random 'situaties' genereert. Lees de code en het commentaar goed. De voorbeelden zijn geimplementeerd als array[1..n] of example. Het is natuurlijk veel mooier om een lijst te gebruiken, maar veel van jullie hadden wat moeite met pointers, vandaar deze wat lompe oplossing, die helaas weer enkele andere problemen oplevert. Als je het aankunt: probeer een lijst te gebruiken. Voor prologgers: Je kan dit programma wel runnen om te kijken wat het oplevert. Ook de code kan als inspiratiebron werken.
Varieer de grootte van de training set en kijk of jou decisiontree lijkt op diegene van het net. De trainingsset varieren betekent niet dat je het aantal voorbeelden groter maakt, maar dat je een groter percentage van de 200 voorbeelden gebruikt om te trainen. De overige voorbeelden gebruik je om te testen. Het gebruiken van de trainingsset als testset is bij machine learning niet vaak toegestaan. Hier zeker niet.
Krijg je dezelfde boom als die op het net? Zo nee, klopt je programma niet, of is er iets anders aan de hand? Mensen die het boek goed gelezen hebben kunnen deze vraag nu al beantwoorden.

Opdracht b

Nu het algorithme klaar is, is het nuttig om het op een andere dataset uit te proberen. Verzin hiervoor zelf een mogelijk probleem (moet dus een ja/nee probleem zijn). Verander het attributes type en de WillWait functie om jou probleem te representeren.
Mogelijke voorbeelden voor problemen zijn in het boek te vinden, zoals beslissen of iemand een credit-kaart krijgt (opg. 15.4), beslissen of je gaat rijden na een groen stoplicht (18.3).

Inleveren

Je moet een listing van je algorithme inleveren, voorzien van kort commentaar, een kort verslagje waarin je de theoretische achtergrond en de verschillende functies/procedures toelicht, de uitvoer van opdracht 3a (enkele afgedrukte bomen, gemaakt na verschillende groottes trainingssets), een beschrijving van je probleem in 3b met daarbij de in- en uitvoer van het algortihme.