|
| Fig. 1. Acht berekenbare kenmerken (attributen) van lettervormen |
De vraag is dus of het mogelijk of het onderscheid klinker of medeklinker (in feite een klankgebaseerd klasse-onderscheid) ook uit de lettervormen is af te leiden. Figuur 1 laat zien welke vormkenmerken een denkbeeldige patroonherkenner met grote zekerheid kan detecteren:
|
|
| Fig. 1. Acht berekenbare kenmerken (attributen) van lettervormen |
We gaan er van uit dat de aanwezigheid van deze kenmerken dusdanig betrouwbaar kan worden berekend uit het letterbeeld, dat we uit kunnen gaan van logische proposities (aanwezig? 1/0). In de echte wereld is het erg lastig om dit te realiseren. Denk bijv. aan de rafelige pixel-patronen op een slecht overgekomen fax of aan handgeschreven letters. Het is ook maar een voorbeeld. Het bestand 'letters-naar-klinkers.txt' bevat de tabel met deze voorbeeldgegevens.
[Attributen] 8 bovenstok onderstok gesloten kruising puntje bovenopen onderopen puntig [Voorbeelden met binaire attribuutwaarden] 26 [klinker?] a 0 0 1 0 0 0 0 0 yes b 1 0 1 0 0 0 0 0 no c 0 0 0 0 0 0 0 0 no d 1 0 1 0 0 0 0 0 no e 0 0 1 0 0 0 0 0 yes f 1 0 0 1 0 0 0 0 no g 0 1 1 0 0 0 0 0 no h 1 0 0 0 0 0 1 0 no i 0 0 0 0 1 0 0 0 yes j 0 1 0 0 1 0 0 0 no k 1 0 0 0 0 1 1 0 no l 1 0 0 0 0 0 0 0 no m 0 0 0 0 0 0 1 0 no n 0 0 0 0 0 0 1 0 no o 0 0 1 0 0 0 0 0 yes p 0 1 1 0 0 0 0 0 no q 0 1 1 0 0 0 0 0 no r 0 0 0 0 0 0 0 0 no s 0 0 0 0 0 0 0 0 no t 1 0 0 1 0 0 0 0 no u 0 0 0 0 0 1 0 0 yes v 0 0 0 0 0 1 0 1 no w 0 0 0 0 0 1 1 1 no x 0 0 0 1 0 1 1 0 no y 0 1 0 0 0 1 0 0 no z 0 0 0 0 0 0 0 0 no |
Gebruik deze data als test voordat je aan de restaurantgegevens begint. Het aantal voorbeelden is hier klein (26) en je kunt je programma dus goed testen.
dectree l < letters-naar-klinkers.txt
Toepassen van het programma moet leiden tot perfecte klassificatie. Zijn alle attributen even belangrijk? Hieronder een voorbeeld van een run:
> dectree l < letters-naar-klinkers.txt Training set bov ond ges kru pun bov ond pun no no yes no no no no no Yes yes no yes no no no no no No no no no no no no no no No yes no yes no no no no no No no no yes no no no no no Yes yes no no yes no no no no No no yes yes no no no no no No yes no no no no no yes no No no no no no yes no no no Yes no yes no no yes no no no No yes no no no no yes yes no No yes no no no no no no no No no no no no no no yes no No no no no no no no yes no No no no yes no no no no no Yes no yes yes no no no no no No no yes yes no no no no no No no no no no no no no no No no no no no no no no no No yes no no yes no no no no No no no no no no yes no no Yes no no no no no yes no yes No no no no no no yes yes yes No no no no yes no yes yes no No no yes no no no yes no no No no no no no no no no no No bepaal knoop 1 N= 26 Attr 1 bovenstok N+ 7 P+ 0.27 N- 19 P- 0.73 P+_ok 0.00 P-_ok 0.74 G= 0.392 N= 26 Attr 2 onderstok N+ 5 P+ 0.19 N- 21 P- 0.81 P+_ok 0.00 P-_ok 0.76 G= 0.360 N= 26 Attr 3 gesloten N+ 8 P+ 0.31 N- 18 P- 0.69 P+_ok 0.38 P-_ok 0.89 G= 0.358 N= 26 Attr 4 kruising N+ 3 P+ 0.12 N- 23 P- 0.88 P+_ok 0.00 P-_ok 0.78 G= 0.332 N= 26 Attr 5 puntje N+ 2 P+ 0.08 N- 24 P- 0.92 P+_ok 0.50 P-_ok 0.83 G= 0.323 N= 26 Attr 6 bovenopen N+ 6 P+ 0.23 N- 20 P- 0.77 P+_ok 0.17 P-_ok 0.80 G= 0.295 N= 26 Attr 7 onderopen N+ 6 P+ 0.23 N- 20 P- 0.77 P+_ok 0.00 P-_ok 0.75 G= 0.376 N= 26 Attr 8 puntig N+ 2 P+ 0.08 N- 24 P- 0.92 P+_ok 0.00 P-_ok 0.79 G= 0.319 Best attribute= 1=bovenstok Gbest= 0.392 Yes antwoord van dit attribuut is perfect, maar correspondeert met output No b d f h k l t (over: 19 voorbeelden) bepaal knoop 2 N= 19 Attr 2 onderstok N+ 5 P+ 0.26 N- 14 P- 0.74 P+_ok 0.00 P-_ok 0.64 G= 0.307 N= 19 Attr 3 gesloten N+ 6 P+ 0.32 N- 13 P- 0.68 P+_ok 0.50 P-_ok 0.85 G= 0.260 N= 19 Attr 4 kruising N+ 1 P+ 0.05 N- 18 P- 0.95 P+_ok 0.00 P-_ok 0.72 G= 0.192 N= 19 Attr 5 puntje N+ 2 P+ 0.11 N- 17 P- 0.89 P+_ok 0.50 P-_ok 0.76 G= 0.190 N= 19 Attr 6 bovenopen N+ 5 P+ 0.26 N- 14 P- 0.74 P+_ok 0.20 P-_ok 0.71 G= 0.174 N= 19 Attr 7 onderopen N+ 4 P+ 0.21 N- 15 P- 0.79 P+_ok 0.00 P-_ok 0.67 G= 0.275 N= 19 Attr 8 puntig N+ 2 P+ 0.11 N- 17 P- 0.89 P+_ok 0.00 P-_ok 0.71 G= 0.218 Best attribute= 2=onderstok Gbest= 0.307 Yes antwoord van dit attribuut is perfect, maar correspondeert met output No g j p q y (over: 14 voorbeelden) bepaal knoop 3 N= 14 Attr 3 gesloten N+ 3 P+ 0.21 N- 11 P- 0.79 P+_ok 1.00 P-_ok 0.82 G= 0.463 N= 14 Attr 4 kruising N+ 1 P+ 0.07 N- 13 P- 0.93 P+_ok 0.00 P-_ok 0.62 G= 0.107 N= 14 Attr 5 puntje N+ 1 P+ 0.07 N- 13 P- 0.93 P+_ok 1.00 P-_ok 0.69 G= 0.173 N= 14 Attr 6 bovenopen N+ 4 P+ 0.29 N- 10 P- 0.71 P+_ok 0.25 P-_ok 0.60 G= 0.075 N= 14 Attr 7 onderopen N+ 4 P+ 0.29 N- 10 P- 0.71 P+_ok 0.00 P-_ok 0.50 G= 0.286 N= 14 Attr 8 puntig N+ 2 P+ 0.14 N- 12 P- 0.86 P+_ok 0.00 P-_ok 0.58 G= 0.160 Best attribute= 3=gesloten Gbest= 0.463 Yes antwoord van dit attribuut is perfect, en correspondeert met output Yes a e o (over: 11 voorbeelden) bepaal knoop 4 N= 11 Attr 4 kruising N+ 1 P+ 0.09 N- 10 P- 0.91 P+_ok 0.00 P-_ok 0.80 G= 0.344 N= 11 Attr 5 puntje N+ 1 P+ 0.09 N- 10 P- 0.91 P+_ok 1.00 P-_ok 0.90 G= 0.574 N= 11 Attr 6 bovenopen N+ 4 P+ 0.36 N- 7 P- 0.64 P+_ok 0.25 P-_ok 0.86 G= 0.328 N= 11 Attr 7 onderopen N+ 4 P+ 0.36 N- 7 P- 0.64 P+_ok 0.00 P-_ok 0.71 G= 0.451 N= 11 Attr 8 puntig N+ 2 P+ 0.18 N- 9 P- 0.82 P+_ok 0.00 P-_ok 0.78 G= 0.375 Best attribute= 5=puntje Gbest= 0.574 Yes antwoord van dit attribuut is perfect, en correspondeert met output Yes i (over: 10 voorbeelden) bepaal knoop 5 N= 10 Attr 4 kruising N+ 1 P+ 0.10 N- 9 P- 0.90 P+_ok 0.00 P-_ok 0.89 G= 0.547 N= 10 Attr 6 bovenopen N+ 4 P+ 0.40 N- 6 P- 0.60 P+_ok 0.25 P-_ok 1.00 G= 0.675 N= 10 Attr 7 onderopen N+ 4 P+ 0.40 N- 6 P- 0.60 P+_ok 0.00 P-_ok 0.83 G= 0.610 N= 10 Attr 8 puntig N+ 2 P+ 0.20 N- 8 P- 0.80 P+_ok 0.00 P-_ok 0.88 G= 0.565 Best attribute= 6=bovenopen Gbest= 0.675 No antwoord van dit attribuut is perfect, en correspondeert met output No c m n r s z (over: 4 voorbeelden) bepaal knoop 6 N= 4 Attr 4 kruising N+ 1 P+ 0.25 N- 3 P- 0.75 P+_ok 0.00 P-_ok 0.67 G= 0.311 N= 4 Attr 7 onderopen N+ 2 P+ 0.50 N- 2 P- 0.50 P+_ok 0.00 P-_ok 0.50 G= 0.500 N= 4 Attr 8 puntig N+ 2 P+ 0.50 N- 2 P- 0.50 P+_ok 0.00 P-_ok 0.50 G= 0.500 Best attribute= 7=onderopen Gbest= 0.500 Yes antwoord van dit attribuut is perfect, maar correspondeert met output No w x (over: 2 voorbeelden) bepaal knoop 7 N= 2 Attr 4 kruising N+ 0 P+ 0.00 N- 2 P- 1.00 P+_ok 0.00 P-_ok 0.50 G= 0.000 N= 2 Attr 8 puntig N+ 1 P+ 0.50 N- 1 P- 0.50 P+_ok 0.00 P-_ok 0.00 G= 1.000 Best attribute= 8=puntig Gbest= 1.000 Yes antwoord van dit attribuut is perfect, maar correspondeert met output No No antwoord van dit attribuut is perfect, maar correspondeert met output Yes u v (over: 0 voorbeelden) bepaal knoop 8 N= 0 Attr 4 kruising N+ 0 P+ 0.00 N- 0 P- 0.00 P+_ok 0.00 P-_ok 0.00 G= 1.000 Best attribute= 4=kruising Gbest= 1.000 (over: 0 voorbeelden) Niet geclassificeerd:
Interpretatie: er wordt een volgorde van attributen gekozen die leidt tot een vrij lineaire boom. Elk attribuut selecteert perfect een bepaalde subset van de letters van het alfabet. Aan het eind blijkt dat het attribuut kruising overbodig is, want alle letters zijn dan al geklassificeerd als klinker of medeklinker. Figuur 2 geeft hieronder de beslissingsboom grafisch weer:
|
| Fig. 2. De resulterende correcte beslissingsboom. |
L.Schomaker / mei 2002
