|
|
|
|
Der ID3 Algorithmus beginnt die Suche nach Regelmäßigkeiten mit allen Beispielen des Trainingssets, also einer Menge, die durch keine Bedingung beschränkt ist und daher eine sehr allgemeine Beschreibung hat. Diese Beispielmenge wird solange durch Bedingungen an Attributwerte differenziert, bis die Kategorien genau gefunden sind. D. h. 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 des Trainingssets beschreiben.
Der oben beschriebene formale Algorithmus beschreitet den umgekehrten Weg, eine Bottom-up Methode: beginnend mit den Beispielen der gesuchten Kategorien im Trainingsset werden die Regeln solange 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 (Siehe Abbildung _54_ ) oder in den Konjunktionen Glieder weggelassen werden.
|
|
|
|