Wir haben bislang erarbeitet, was ein Entscheidungsbaum ist und wie Objekte bestehend aus Merkmalen anhand von Entscheidungsregeln (Knoten der Bäume) einer Klasse (Blätter der Bäume) zugeordnet werden können. Zudem haben wir erkannt, dass ein Entscheidungsbaum den Raum der Objekte in Rechtecke (zwei Merkmale), rechteckige Würfel (drei Merkmale) bzw. rechteckige Hyperwürfel (mehr als drei Merkmale) aufteilt.
Unsere eigentliche Aufgabe besteht jedoch darin, einen Entscheidungsbaum zur Lösung einer Klassifikationsaufgabe zu erzeugen.
Dazu nehmen wir an, dass Trainingsdaten zur Verfügung stehen. Wie üblich handelt es sich dabei um eine Reihe von Objekten, bei denen das Klassifikationsergebnis bekannt ist:
| Merkmal 1 | Merkmal 2 | ... | Merkmal n | Label | |
| Objekt 1 | Wert | Wert | ... | Wert | Index der Klasse |
| Objekt 2 | Wert | Wert | ... | Wert | Index der Klasse |
| ... | ... | ... | ... | ... | |
| Objekt m | Wert | Wert | ... | Wert | Index der Klasse |
Unser Ziel besteht nun darin, einen Entscheidungsbaum zu bestimmen, sodass sämtliche Objekte der Trainingsdaten korrekt klassifiziert werden. Dies bedeutet:
Ein Entscheidungsbaum, der auf Basis von Trainingsdaten bestimmt wird, erfüllt stets die Eigenschaft, dass sämtliche Objekte der Trainingsdaten korrekt klassifiziert werden.
Es sei bereits bemerkt, dass die Eigenschaft zuvor im Allgemeinen weder bei neuronalen Netzen noch bei der Nächste-Nachbarn-Klassifikation erfüllt ist.
Bei der Klassifikationsaufgabe zur Bestimmung von Schwertlilien haben wir es mit Daten der folgenden Gestalt zu tun:
| Kelchblattlänge | Kelchblattbreite | Kronblattlänge | Kronblattbreite | Label | |
| Objekt 1 | Wert in cm | Wert in cm | Wert in cm | Wert in cm | Index der Art |
| Objekt 2 | Wert in cm | Wert in cm | Wert in cm | Wert in cm | Index der Art |
| ... | ... | ... | ... | ... | ... |
| Objekt m | Wert in cm | Wert in cm | Wert in cm | Wert in cm | Index der Art |