4.2.4: Der ID3 Algorithmus

Abb. 44: Entscheidungsbaum nach dem ID3 Algorithmus

Als Beispiel eines Systems, das einen Kategorisierungsalgorithmus aus einer Beispielmenge erzeugt, soll zunächst der ID3 Algorithmus von Ross Quinlan beschrieben werden (Quinlan 1986 [->]). Dieser Algorithmus generiert einen Entscheidungsbaum, also eine Struktur, bei der zur Klassifizierung eines Tupels an der Wurzel begonnen wird und solange Abfragen, die jeweils einen Ast bestimmen, durchgeführt werden, bis ein Blatt des Baumes erreicht ist, das die Klassifizierung des Tupels angibt.

Bei der Konstruktion des Entscheidungsbaumes wird in jedem Knoten ein einzelnes Attribut dazu verwendet, die Menge der Beispiele aufzuteilen, bis die Beispiele einer Teilmenge alle aus einer Kategorie sind. Ein Beipiel ist in Abbildung _44_ gezeigt.

4.2.4.1: Algorithmus im Überblick

4.2.4.2: Formale Beschreibung des ID3 Algorithmus

Abb. 45: Entropiewerte, nach denen die Attribute bei der Konstruktion des ID3 Baums aus den Beispielen aus Abbildung selektiert werden.

4.2.4.3: Kategorisieren mit dem ID3 Algorithmus

Abb. 46: Der ID3 Baum, der sich aus den Beispielen aus Abbildung ergibt, mit den Beispielmengen der Knoten

Abb. 47: Der ID3 Baum aus Abbildung ohne Beispielmengen

Der ID3 Algorithmus ist einer der klassischen Ansätze für Entscheidungsbäume. Er und weitere entschiedungsbaumbasierte Verfahren werden in einer ganzen Reihe von Softwareprodukten angeboten.