13.3 Beslisbomen
Beslisbomen zijn bomen die gebruikt worden bij het classificeren van voorbeelden. Beginnend bij de wortel wordt, aan de hand van het voorbeeld gekeken hoe in de boom moet worden afgedaald tot in één van de bladeren van de boom, die de klasse van het voorbeeld bevat.
13.3.1 Classificeren met beslisbomen
Beslisbomen vertalen de voorbeelden uit een trainingset in een boomrepresentatie en abstraheren op die wijze kennis uit de voorbeelden. Startend bij de wortel van de boom, wordt op ieder knooppunt een attribuut van de voorbeeldvector getoetst op een bepaalde conditie. Zo worden de voorbeelden uit tabel 13.3.1 gerepresenteerd door de beslisboom in figuur 13.3.1.
Tabel 13.3.1 Gegevensverzameling (gelijk aan de gegevensverzameling in paragraaf 13.1)
voorbeeld | invoervector | klasselabel |
1 | 000 | A |
2 | 001 | B |
3 | 010 | A |
4 | 011 | B |
5 | 100 | A |
6 | 101 | B |
7 | 110 | A |
8 | 111 | B |
Figuur 13.3.1 Een voorbeeld van een beslisboom
De in figuur 13.3.1 getoonde beslisboom is verkregen uit de trainingset door eerst te vertakken op de eerste (meest significante) bit van de vector, vervolgens de tweede bit, en tenslotte de derde (minst-significante) bit. Op iedere vertakking (knooppunt) van de boom wordt er getoetst op de conditie attribuut gelijk aan 1? Vanuit het knooppunt vertakt de boom zich in twee richtingen: links representeert niet voldaan, rechts representeert wel voldaan. Uiteindelijk termineert de boom op het derde niveau in de 8 voorbeelden en hun bijbehorende klasselabels (A of B). De beslisboom in figuur 13.3.1 bevat alle mogelijke voorbeelden (binaire vectoren van lengte 3). Doorgaans wordt een beslisboom verkregen op basis van een representatieve steekproef uit een verzameling en kunnen nieuwe voorbeelden (de voorbeelden in de testset) worden geclassificeerd door op basis van de individuele attributen de beslisboom te doorlopen. De op het laagste niveau aangetroffen klasselabel geldt als de klasse waartoe het voorbeeld behoort.
13.3.2 Representatie van disjunctie van conjuncties
Een beslisboom laat zich direct vertalen in een disjunctie
van conjuncties van de getoetste condities. Zo kan
de beslisboom van figuur 13.3.1 worden gerepresenteerd als:
(bit1 = 0
De beslisboom in figuur 13.3.1 is op een eenvoudige wijze te reduceren tot een kleinere boom. Immers, de classificatie van voorbeelden uit tabel 13.3.1 is direct af te leiden uit de laatste (derde) bit. Een éénlagige beslisboom volstaat voor het representeren van de gehele gegevensverzameling. Om de omvang van een beslisboom te beperken, is het noodzakelijk de individuele attributen te toetsen op de hoeveelheid informatici die ze verstrekken met betrekking tot de classificatie. Een veelgebruikte methode is gebaseerd op de zogenaamde information gain, oftewel de effectiviteit van het toetsen op een bepaald attribuut voor de uiteindelijke classificatie.
Beslisbomen zijn eenvoudig te genereren uit de gegevensverzameling en bijzonder robuust. Bovendien is de boom op eenvoudige wijze te vertalen in een (redelijk) begrijpelijke verzameling van regels. Bekende voorbeelden van beslisboomalgoritmen zijn het
ID3-algoritme en zijn moderne variant C4.5, beide van Quinlan.Het belangrijkste nadeel van beslisbomen is dat ze erg groot kunnen worden voor omvangrijke trainingsets. Een ander nadeel is dat in sommige gevallen de beslisboom zich te specifiek richt op de voorbeelden in de trainingset, waardoor het generaliserend vermogen afneemt. Op dit verschijnsel, dat bekend staat als overfitting, wordt dieper ingegaan in paragraaf 13.5.