2.3.6.3: Top-down- und Bottom-up-Methoden

Der ID3-Algorithmus beginnt die Suche nach Regelmäßigkeiten mit allen Beispielen der Trainingsmenge, also einer Menge, die durch keine Bedingung beschränkt ist und daher eine sehr allgemeine Beschreibung hat. Diese Beispielmenge wird so lange durch Bedingungen an Attributwerte differenziert, bis die Kategorien genau gefunden sind. Das heißt, bis durch geeignete Vereinigung der Beispielmengen, die den einzelnen Knoten zugeordnet sind, die Kategorien erzeugt werden können. Man bezeichnet dieses Vorgehen als Top-down-Methode: Beginnend mit der allgemeinsten Beschreibung aller Beispiele werden die Beschreibungen durch Hinzufügen von Bedingungen an zusätzliche Attribute immer weiter ausdifferenziert, bis sie gerade die Regeln der Trainingsmenge beschreiben.

Der oben beschriebene formale Algorithmus zur Regelbildung aus Beispielen beschreitet den umgekehrten Weg, eine Bottom-up-Methode: Beginnend mit den Beispielen der gesuchten Kategorien in der Trainingsmenge werden die Regeln so lange wie möglich verallgemeinert, ohne dass dabei die Kategorisierung verletzt wird. Regeln in konjunktiver Normalform können verallgemeinert werden, indem in den Disjunktionen elementare Bedingungen hinzugefügt werden oder in den Konjunktionen Glieder weggelassen werden.