2.3.6: Einfache Regelsysteme

Die Konstruktion eines ID3-Entscheidungsbaums ging von einer Menge von Attributen aus, die jeweils eine bestimmte Wertemenge haben. Ein Ast eines Entscheidungsbaums lässt sich in eine Menge von durch AND verknüpfte Bedingungen an die Attribute übertragen, die in den Knoten des Asts vorkommen. Dabei können die gleichen Methoden verwendet werden wie beim booleschen Retrieval. 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 (bzw. atomare) Bedingung definiert , die durch Teilmengen von D charakterisiert ist:

(Ai=rj) :=A-1i({r j})={ dD | Ai(d) =rj}

(Ai=rk) (Aj=rl) :=A-1i({r k})A- 1j({rl} )

(Ai=rk) (Aj=rl) :=A-1i({r k})A- 1j({rl} )

(Airk) :=(Ai=rk) :=D\A-1i({ rk})

So wird die Menge der Beispiele aus dem ganz links liegenden Blatt im Baum aus Abbildung 51 durch folgende Bedingungen beschrieben:

(A1=r1) (A2=r4) =A-11({r 1})A- 12({r4} )

Nimmt man weiter an, dass die Beispiele dieses Blatts des Baums aus der Kategorie K_j sind, kann man diesen Ast in eine Regel der Form

IF (A1( d)=r1) (A2(d) =r4) THEN  dKj

(A1=r1) (A2=r4)Kj

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.

Definition 14: 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.

Abbildung 57: Einige Regeln, die sich aus einem Entscheidungsbaum ableiten lassen.

Allerdings ergeben sich bei einem solchen Vorgehen sehr viele Regeln, die in vielen Teilen identisch sind: Die Teile des Baums, die zwei Äste gemeinsam haben, erscheinen auch als gleiche elementare Bedingungen 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, ohne dass ein kompletter Entscheidungsbaum verwendet wird.

2.3.6.1: Entscheidungslisten

2.3.6.2: Ripple-down-Regelmengen

Bei der "manuellen" Konstruktion der Listen in den Beispielen aus den Abbildungen 58 und 59 wurde von den Beispielen und nicht von einem Entscheidungsbaum ausgegangen. Im Prinzip lassen sich Regeln aus einer Trainingsmenge auf folgende einfache Weise gewinnen:

Algorithmus 5: Formale Regelbildung aus Beispielen

Wie man leicht sieht, kann auch dieser formale Algorithmus als ein Beweis der Aussage aus Abschnitt 2.3.5.1 verwendet werden, dass zu jeder endlichen konsistenten Trainingsmenge ein KDD-Verfahren existiert, das einen Algorithmus konstruiert, mit dem die Elemente der Trainingsmenge richtig kategorisiert werden können.

Abbildung 59: Konstruktion eines Ripple-down Sets

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

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