In diesem Abschnitt erläutern wir zunächst, wie ein Entscheidungsbaum unter Verwendung von Trainingsdaten aufgebaut werden kann. Dies machen wir anhand des folgenden Beispiels:
Die erste Entscheidungsregel (Knoten 1) wird spezifiziert, indem sämtliche Objekte der Trainingsdaten berücksichtigt werden. Wie genau die Entscheidungsregel spezifiziert werden kann, besprechen wir im nachfolgenden Abschnitt. Wichtig ist jedoch folgende Eigenschaft:
Eine Entscheidungsregel muss stets so aufgebaut sein, sodass die Menge der (relevanten) Objekte in zwei nicht leere Mengen aufgeteilt wird.
Die Entscheidungsregel zum Knoten 2 berücksichtigt nun nur die Objekte der Trainingsdaten, bei denen die Entscheidungsregel 1 mit ja beantwortet werden kann. Analog berücksichtigt Knoten 3 genau den anderen Teil der Trainingsdaten, also sämtliche Objekte, bei denen Entscheidungsregel 1 mit nein beantwortet wird.
Im nächsten Schritt wird an Knoten 4 eine Entscheidungsregel aufgestellt, bei der nur die Objekte der Trainingsdaten herangezogen werden, bei denen Entscheidungsregel 1 mit ja und Entscheidungsregel 2 mit nein beantwortet werden kann.
Diese Vorgehensweise setzt sich entsprechend fort, wobei wir feststellen können:
Von Knoten zu Knoten wird die Anzahl der relevanten Objekte der Trainingsdaten kleiner.
Zudem wird jeweils geprüft, ob nach einer Entscheidungsregel alle relevanten Objekte derselben Klasse angehören. Falls dies der Fall ist, so wird kein Knoten samt Entscheidungsregel definiert, sondern ein Blatt des Baumes mit entsprechender Klasse. Am Beispiel von Blatt A gehören alle Objekte der Trainingsdaten, bei denen die Entscheidungsregeln 1 und 2 mit ja beantwortet werden, derselben Klasse an.
Falls ein Entscheidungsbaum auf die zuvor beschriebene Art und Weise aufgebaut wird, dann werden per Konstruktion sämtliche Objekte der Trainingsdaten korrekt klassifiziert.
Offen ist nach wie vor die Frage, wie Entscheidungsregeln algorithmisch spezifiziert werden können. Dies beantworten wir gleich. Zuvor lässt sich aber bereits die nachfolgende Aufgabe lösen, um die Vorgehensweise zum Aufbau eines Entscheidungsbaumes zu vertiefen. Die Aufgabe ist durchaus ein wenig anspruchsvoll und knifflig, es lässt sich daran jedoch viel lernen. Verwendet werden sollen die folgenden Trainingsdaten:
| x1 | x2 | Label | |
| Objekt 1 | 1.0 | 2.0 | rot |
| Objekt 2 | 6.0 | 2.0 | blau |
| Objekt 3 | 1.0 | 9.0 | blau |
| Objekt 4 | 9.0 | 6.0 | rot |
| Objekt 5 | 4.0 | 3.0 | rot |
| Objekt 6 | 4.0 | 7.0 | blau |