4.3.1: Einfache Regelsysteme

Bei der Konstruktion des Entscheidungsbaumes waren wir von einer Menge von Attributen ausgegangen, die jeweils eine bestimmte Wertemenge haben. Mit Hilfe der Attribute läßt sich ein Ast eines Entscheidungsbaums leicht in eine Menge von durch AND verknüpfte Bedingungen an Attribute bringen. Die dabei verwendeten Methoden stimmen mit denen im Booleschen Retrieval überein. Zunächst wird wieder für ein Attribut A_i:D->R_i und einen Wert r_jR_i des Attributs ein Attribut - Wert Paar oder eine elementare oder atomare Bedingung definiert , die durch Teilmengen von D charakterisiert ist:

(A_i=r_j):=A^-1_i({r_j})={dD | A_i(d)=r_j}

(A_i=r_k)(A_j=r_l):=A^-1_i({r_k})A^-1_j({r_l})

(A_i=r_k)(A_j=r_l):=A^-1_i({r_k})A^-1_j({r_l})

(A_ir_k):=(A_i=r_k):=D\A^-1_i({r_k})

Als Beispiel kann die Menge der Beispiele im Blatt des linkesten Asts aus dem Baum in Abbildung _44_ folgendermaßen dargestellt werden: (A₁=r₁)(A₂=r₄)=A^-1₁({r₁})A^-1₂({r₄}) . Nimmt man weiter an, dass die Beispiele dieses Blattes des Baumes aus der Kategorie K_j sind, so kann man diesen Ast in eine Regel der Form

IF (A₁(d)=r₁)(A₂(d)=r₄) THEN dK_j

Abb. 51: Einige Formeln, die sich aus dem Entscheidungsbaum aus Abbildung ableiten lassen

Regeln haben die Vorteile, dass

• sie häufig als Repräsentationsform z. B. in Expertensystemen verwendet werden
• sie für Menschen verständlich sind
• jede einzelne für sich allein verwendet werden kann
• sie sich leicht generalisieren und spezialisieren lassen

Man kann solche Regeln in Normalformen bringen, die eine automatisierte Verarbeitung erleichtern.

4.3.1.1: Normalformen

Die Regeln, die aus einem Entscheidungsbaum gewonnen werden, der durch einen ID3 Algorithmus erzeugt wurde, haben eine noch einfachere Form: sie sind, wie das obige Beispiel, Konjunktionen von elementaren Bedingungen. Diese einzelnen elementaren Bedingungen können wegen der Kommutativität der Durchschnittsbildung beliebig umsortiert werden.

Allerdings ergeben sich bei einem solchen Vorgehen sehr viele Regeln, die in vielen Teilen identisch sind: Die Teile des Baumes, die zwei Äste gemeinsam haben, erscheinen auch als gleiche elementare Bedinungen in den Regeln. Dadurch wird die Anzahl der Regeln aufgebläht und die Abarbeitung beschränkt sich im wesentlichen auf viele Einzelvergleiche. Im folgenden werde einige Verfahren genannt, mit denen der Zugriff effizienter gemacht werden kann.

4.3.1.2: Entscheidungslisten

4.3.1.3: Ripple-down Regelmengen

Bei der "manuellen" Konstruktion der Listen in den Beispielen aus den Abbildungen _52_ und _53_ waren wir von den Beispielen und nicht von einem Entscheidungsbaum ausgegangen. Im Prinzip lassen sich Regeln aus einem Trainingsset auf folgende einfache Weise gewinnen.

4.3.1.4: Formaler Algorithmus zur Regelbildung aus Beispielen

Wie man leicht sieht, kann auch dieser formale Algorithmus als ein Beweis der Aussage aus Abschnitt _4.2.5_ verwendet werden, dass zu jedem endlichen konsistenten Trainingsset ein KDD Verfahren existiert, das einen Algorithmus konstruiert, mit dem die Elemente des Trainingssets richtig kategorisiert werden können.

Abb. 54: Verallgemeinerung einer Bedingung durch Hinzufügen einer elementaren Bedingung zu einer Disjunktion

Abb. 55: Verallgemeinerung von Regeln, die aus einigen Beispielen aus Abbildung gewonnen wurden

4.3.1.5: Top-Down und Bottom-Up Methoden

Im folgenden soll ein Verfahren vorgestellt werden, das den formalen Algorithmus in eine praxistaugliche Form bringt.