Wat is een beslisboom?

Als (aankomend) data scientist/manager wil je weten wat een beslisboom is en welke problemen je met beslisbomen kunt tackelen. Natuurlijk moet je op de hoogte zijn van de oplossingen die ze kunnen aanreiken, maar ook wil je weten welke beperkingen een beslisboom heeft.

Inleiding in beslisbomen: een praktijkvoorbeeld

Eten in een restaurant kan voor behoorlijke problemen zorgen, vooral als er een uitgebreide kaart is. Allereerst is er de vraag of je naast het hoofdgerecht ook een voorgerecht wilt en of je later nog een nagerecht neemt. Bovendien speelt ook nog mee dat niet elke combinatie van voorgerecht en hoofdgerecht even goed smaakt. De verschillende gerechten passen niet altijd goed bij elkaar. Verder speelt mee dat niet elke wijnsoort bij elk gerecht past en dat het misschien nodig is om een andere wijn bij het voorgerecht te bestellen dan dat er gedronken wordt bij het hoofdgerecht.

Een leuk diner, een verzameling lastige keuzes?

Een leuk diner in een goed restaurant ontaardt daarom al snel in een grote verzameling lastige keuzes, waarbij bovendien sommige keuzes bij het voorgerecht bepalend kunnen zijn voor de beschikbare keuzes bij het hoofdgerecht. Bovenal speelt mee dat een eenmaal gedane keuze blijft doorwerken tot aan het eind van de (al dan niet) gezellige avond. Om alle keuzes in beeld te brengen kun je als bezoeker natuurlijk een beslisboom maken.

Hoofdbrekens voor de restauranteigenaar

Evenzo zorgt een dergelijke avond voor de nodige hoofdbrekens bij de restauranteigenaar. Het is altijd de vraag of zijn inkoop enigszins overeenkomt met de bestellingen op die avond. In hoeverre is het mogelijk om de keuzes van elke bezoeker in te schatten en te voorspellen? Welke beslissingen nemen de bezoekers en welke gerechten zijn die desbetreffende avond het meest gewenst? De uiteindelijke keuzes kan de restauranthouder in een beslisboom opnemen.

De ene optie sluit de andere uit bij een beslisboom

Voor zowel de bezoeker als de restauranthouder geldt dat zij te maken hebben met een serie keuzes waarbij de ene optie de andere opties uitsluit, een situatie die veelvuldig voorkomt. De vraag is nu in welke mate je een dergelijke situatie kan toepassen bij het selecteren en combineren van data. Feitelijk wordt de situatie dan omgedraaid: de beslisboom gebruik je niet om informatie in beeld te brengen, maar om beslissingen te nemen.

Welk type probleem lost de beslisboom op?

Een beslisboom is een techniek die een verdeling maakt op basis van elkaar uitsluitende kenmerken. Bij personenauto’s is de kleur van de auto een dergelijk kenmerk. Een blauwe auto is immers niet rood en een rode auto niet blauw of willekeurig welke andere kleur. De kleur is een duidelijk onderscheidend kenmerk van auto’s. In geval van de auto’s kan je de keuze door de beslisboom op twee manieren invullen:

  • Enkelvoudige keuze: hierbij wordt alleen gekozen tussen blauw en niet-blauw.
  • Meervoudige keuze: hierbij is er naast de keuze blauw ook sprake van de keuzes rood, zilver, zwart, wit en overig.

Aan de andere kant is het aantal wielen bij personenauto’s wel een duidelijk kenmerk, maar is het niet geschikt om verschillende auto’s te onderscheiden. Vrijwel alle personenauto’s staan op vier wielen en dat geldt ook voor veel bestelauto’s en een deel van de vrachtwagens, dus dit kenmerk verliest zijn waarde voor het onderscheiden van de verschillende auto’s.

Opleiding Predictive Analytics

Wil je experimenteren met beslisbomen en zelf voorspellende modellen ontwerpen en implementeren? Dan is onze 3-daagse opleiding Big Data Analytics absoluut een aanrader.

naar de opleiding

Is de telling nauwkeurig genoeg?

Het is wel de vraag in hoeverre zeldzame kleuren betrouwbare uitkomsten geven. Het is natuurlijk leuk om een kleur als “British racing green” op te nemen in de lijst. Waarschijnlijk heeft maar een zeer beperkt aantal auto’s die kleur en dan is er altijd de vraag in hoeverre de telling met gebruik van een beslisboom nauwkeurig genoeg is. Resteert de vraag in welke mate je een beperkte verzameling gegevens kunt gebruiken om het gedrag van een grote verzameling te voorspellen. Anders gezegd: gegeven de grootte van de testverzameling, welke nauwkeurigheid is haalbaar en te verantwoorden?

Doe geen uitspraak als iets niet voorkomt

Op een parkeerterrein staan vijf auto’s: een rode, een blauwe, een witte, zwarte en een gele. Op basis van deze gegevens kan je concluderen dat deze vijf kleuren elk een kans Pkleur = 0,20 hebben, waarbij Pkleur de kans aangeeft dat een bepaalde kleur voorkomt. Op grond van deze gegevens lijkt het of er geen groene, bruine en paarse auto’s bestaan. Het is echter niet mogelijk om daar een uitspraak over te doen, omdat niet duidelijk is of auto’s met een andere kleur gewoonweg niet bestaan, of dat ze alleen niet voorkomen in de testverzameling.

Is sprake van een toevallige of een oorzakelijke overeenkomst?

Uiterlijke kenmerken van auto’s worden vaak gebruikt om andere, minder opzichtige eigenschappen op te sporen. Zo zou een redenering kunnen zijn dat rode auto’s vaker een snelheidsbekeuring krijgen dan auto’s met een andere kleur en dat witte auto’s vaker fout geparkeerd staan. Juist bij het opsporen van dergelijke koppelingen is het van groot belang om het onderscheid tussen een toevallige overeenkomst en een oorzakelijke overeenkomst te kunnen maken. Het is dus de vraag hoe deze techniek van opeenvolgende keuzes het best opgezet en uitgewerkt kan worden met een beslisboom.

De oplossingen van een beslisboom

Door opeenvolgende keuzes te maken, wordt een verzameling in een steeds groter aantal deelverzamelingen verdeeld. Door een dergelijk patroon te tekenen, ontstaat een beslisboom. In eerste instantie lijkt deze techniek op een beeldende manier om gegevens in te delen en niet op een methode om informatie te onderzoeken. Toch kan je de zoekboom die ontstaat na analyse van (een deel van) de informatie uitstekend gebruiken om voorspellingen te doen. Door een beslisboom op te zetten voor een bepaald probleem, kun je onderzoeken of de vraagstelling wel valide is, gegeven de beschikbare informatie en de vereiste nauwkeurigheid voldoende is om uitspraken te doen.

Krijgen rode auto’s vaker een bekeuring?

De eerste vraag heeft te maken met de vraagstelling, bijvoorbeeld of rode auto’s vaker een snelheidsbekeuring krijgen dan auto’s met een andere kleur. De beschikbare informatie laat na uitwerking van de beslisboom zien of dit klopt of niet. De tweede vraag gaat over de nauwkeurigheid van de betreffende uitspraak en deze wordt mede bepaald door de grootte van de gebruikte testverzameling en de uitkomsten van de eerste analyse. Om deze vragen verder te beantwoorden, is het noodzakelijk om eerst een beslisboom op te zetten en deze te onderzoeken.

Twee of meer subverzamelingen

Per keuzemoment wordt de verzameling in twee of meer subverzamelingen verdeeld, afhankelijk van het aantal gekozen kenmerken. Voor een verdeling in twee subverzamelingen die verdeeld wordt op eigenschap x1 is dit wiskundig te schrijven als:

  • P X( x1 ) p1
  • P X( x1 )1 p1

Vervolgens worden de ontstane groepen weer opnieuw verdeeld. De groep die eigenschap x1 heeft wordt getest op de aanwezigheid van eigenschap x2, de andere groep op de aanwezigheid van eigenschap x3. Het komt ook voor dat slechts één tak verder uitgewerkt wordt.

Langere en kortere takken

Uitgaande van de menukeuze in een restaurant is het na de keuze “geen voorgerecht” ook niet logisch om alle keuzes van het voorgerecht te vermelden. Dit geldt ook voor de keuze “geen nagerecht” en de lijst met alle nagerechten. Gevolg is dat de beslisboom langere en kortere takken krijgt, maar ook dat sommige keuzes op verschillende plaatsen verschijnen.

Objectieve gronden

De enige openstaande vraag is nu, welke kenmerken komen in aanmerking om te gebruiken bij het opzetten van de beslisboom en in welke volgorde? Uiteindelijk kan je dan voor een aantal kenmerken aangeven wat de kans is op het voorkomen van die combinatie. Het is dan ook van het grootste belang dat je de keuze voor zekere kenmerken steeds op objectieve (lees: door de informatie gedicteerde) gronden baseert en niet op subjectieve (lees: door de data analist bepaalde) gronden. Zeker als er sprake is van een grote hoeveelheid data. Dan is automatisering noodzakelijk.

Entropie is een maatstaf voor wanorde

Centraal in de zoektocht naar de juiste beslisboom voor een verzameling informatie is de entropie H van die verzameling. Entropie kan hier gezien worden als een maat voor de wanorde in de verzameling. Is de hele verzameling informatie gevat in een duidelijk gestructureerde beslisboom, dan geldt H = 0, omdat er dan geen wanorde is. Voor nog niet gestructureerde verzamelingen is de entropie heel hoog.

Algoritme doet zijn werk

Een algoritme dat een verzameling informatie structureert in een beslisboom zal stap voor stap, dus steeds bij het aanmaken van een nieuwe serie takken, de wanorde in de verzameling verminderen. De afname van de entropie per stap in het proces wordt ook wel de informatiewinst (op z’n Engels information gain, afgekort IG) van de stap genoemd. Aan het eind van het proces heeft het algoritme alle beschikbare kenmerken gebruikt en heeft de entropie H de laagst mogelijke waarde voor de gegevensverzameling informatie bereikt.

Deel nieuwe informatie meteen in

Zodra de verzameling informatie is gevangen in een beslisboom, kan je deze gebruiken om nieuwe informatie meteen in te delen. Hierbij wordt aangenomen dat de verzameling informatie die gebruikt is voor het bouwen van de beslisboom representatief is voor alle informatie.

De beperkingen van beslisbomen

Tegenover de intuïtieve juistheid en overzichtelijkheid van de beslisboom staat ook een aantal beperkingen. Een van de belangrijkste beperkingen van de beslisboom is dat de gebruikte verzameling informatie via een beslisboom gestructureerd kan worden. Dit betekent dat elk kenmerk steeds een mogelijkheid biedt om een keuze te maken. Niet elke verzameling laat dit toe. Zo zijn er verzamelingen waar combinaties van kenmerken een veel groter gewicht in de schaal leggen dan de individuele kenmerken. In dat geval is het afleiden van regels (zie hoofdstuk 10 van het boek ‘Succes met Big Data’) een betere en betrouwbaardere techniek.

Snoei de beslisboom terug tot aanvaardbare proporties

Een ander gevaar bij het toepassen van een beslisboom is dat je de boom te gedetailleerd uitwerkt. Hierdoor heeft elk eindpunt van de boom te weinig elementen en daardoor uiteindelijk ook te weinig gewicht. De meeste algoritmen kennen daarom ook een “snoei-optie” die een eenmaal gebouwde boom terugsnoeit naar de minimale vorm die de vereiste nauwkeurigheid eist. Toch zijn dit opties die je met mate en grote voorzichtigheid moet toepassen. Te vaak laat de snoeioptie een boom achter met een triviale oplossing van het probleem.

Interesse in beslisbomen?

Neem vrijblijvend contact met ons op voor een afspraak over de mogelijkheden van Predictive Analytics en een beslisboom.

neem contact met ons op

Plaats review

Geef je mening over dit product of deze dienst

Dit veld is verplicht!
Dit veld is verplicht! optioneel
Dit veld is verplicht! optioneel
Dit veld is verplicht! optioneel
Dit veld is verplicht!
Review verzendenHet formulier bevat fouten.

Een selectie van onze klanten

Word nu ook klant

Wil je ook klant bij ons worden? Wij helpen je maar wat graag verder met beslisboom (beslisbomen) of andere zaken waar je slimmer van wordt.

Gustaaf Vocking, Associate Partner Predictive Analytics & Beslisbomen

GUSTAAF VOCKING

Senior consultant Beslisbomen

neem contact met mij op

Fact sheet

Organisaties geholpen
17992
Trainingen & workshops
17993
Deelnemers opgeleid
17994
Beoordeling klanten
8,9
Consultants & docenten
17995
Kantoren
3
Jaar ervaring
14