Wir beginnen zunächst einmal mit einer Beschreibung davon, was wir unter einem Entscheidungsbaum verstehen. Dazu nehmen wir an, dass ein Objekt bestehend aus vier Merkmalen bezüglich dreier Klassen klassifiziert werden soll. Mit anderen Worten besteht das zu klassifizierende Objekt aus vier Werten:

Anhand dieser Werte soll entschieden werden, ob das Objekt der Klasse 1, 2 oder 3 (wahrscheinlich) angehört. Und genau hier kommt ein Entscheidungsbaum ins Spiel:

Oben beginnend repräsentiert jeder Knoten (blaue Rechtecke) eine Entscheidungsregel: Es ist zu prüfen, ob ein Merkmal des zu klassifizierenden Objekts kleiner oder größer gleich einem Schwellwert ist. Diese Entscheidungsregel kann stets mit entweder ja (wahr) oder nein (falsch) beantwortet werden, um zum nächsten Knoten bzw. zur nächsten Entscheidungsregel zu gelangen. Dies wird so lange wiederholt, bis ein Blatt des Baumes (graue Rechtecke) erreicht ist, welches das Klassifikationsergebnis beinhaltet.

Ein konkretes Beispiel, auf das wir mehrfach zurückgreifen werden, ist die Klassifikation von Schwertlilien: Die Aufgabe lautet, Blumen der Gattung Schwertlilie anhand ihrer Blüten hinsichtlich dreier Arten zu klassifizieren. Dazu werden die Blüten anhand der folgenden vier Merkmale beschrieben:

Anhand dieser Daten werden die Blumen in die folgenden drei Klassen kategorisiert: