4.2.15: Suchstrategien

Beim ID3 Algorithmus wird in jedem Knoten eine (endgültige) Entscheidung getroffen, welches Attribut zur Aufteilung der Beispielmenge verwendet wird. Als Auswahlkriterium wird dabei die eher allgemeine Entropieregel verwendet. Diese heuristische Entscheidung garantiert nicht, dass dadurch insgesamt ein optimaler Baum konstruiert wird. Sie kann nur versuchen, an dem jeweiligen Punkt die beste Entscheidung zu treffen. Dieses Vorgehen wird Hill-Climbing Verfahren genannt.

Solche Verfahren gehen davon aus, dass die Algorithmen bzw. deren Teile, die im Laufe eines KDD-Verfahrens entwickelt werden, einen Raum aufspannen, und zu jedem Algorithmus eine Bewertung in Form einer reellen Zahl gegeben ist, die seine "Güte" angibt. Idee des Verfahrens ist es, unter verschiedenen kleinen Änderungen des Algorithmus diejenige auszuwählen, die die beste Güte hat. Dazu muß angenommen werden, dass

• auf dem Raum der Algorithmen eine Metrik existiert
• die Bewertungsfunktion stetig bezüglich dieser Metrik ist
• der Abstand zu einem Algorithmus, der durch einen Schritt in der Konstruktion erreicht werden kann, beschränkt (und klein) ist,

Die Idee eines Hill Climbing Verfahrens ist nun, von dem Ort, an dem man sich gerade befindet, (also dem gegenwärtigen Zustand des Algorithmus aus) den Schritt zu tun, bei dem der Gütewert am meisten steigt. Dieses Verfahren kann bei einer ungünstigen "Gütelandschaft" natürlich auf einen kleinen Hügel statt auf den höchsten Berg führen, sprich ein lokales Maximum erreichen statt eines globalen (Vergl. Abbildung 50 ).

Abb. 50: Gütefunktion mit lokalen Maxima

Um nicht in einem lokalen Maximum zu landen, kann man versuchen, statt der Entropieregel Verfahren zu finden, die die folgenden Schritte der Entwicklung des Baumes einbeziehen. Im Extremfall kann ein optimaler Baum natürlich dadurch gefunden werden, dass man alle möglichen Bäume konstruiert, sie nach einem gegebenen Kriterium bewertet und den besten auswählt. Diese vollständige Suche stößt aber sehr schnell an Grenzen, da die Anzahl der Bäume mit der Anzahl der Attribute und Attributwerte exponentiell wächst.

Ein Kompromiss zwischen den beiden Verfahren berechnet jeweils eine begrenzte Anzahl von aussichtsreichen Alternativen, vergleicht deren Güte und wählt schließlich die beste aus. Dieses Verfahren wird Beam-Search genannt. Die Auswahlkriterien für die Verfahren, die weiterverfolgt werden sollen, können dabei verschiedene Sichtweisen und Eigenschaften berücksichtigen. So können zum Beispiel verschiedene Bewertungsfunktionen verwendet werden, die sich in unterschiedlichen Situationen bewährt haben.