| |||||||||||||
2.3.5.10: SuchstrategienBeim 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. Das ist möglich, wenn einige Voraussetzungen erfüllt sind:
Die Idee eines Hill-Climbing-Verfahrens ist nun, von dem Ort aus, an dem man sich gerade befindet (also dem gegenwärtigen Zustand des Algorithmus), 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 (siehe Abbildung 56 ). Abbildung 56: Gütefunktion mit lokalen MaximaUm nicht in einem lokalen Maximum zu landen, kann man versuchen, statt der Entropieregel Verfahren zu finden, die die folgenden Schritte der Entwicklung des Baums 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 exponenziell 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 z.B. verschiedene Bewertungsfunktionen verwendet werden, die sich in unterschiedlichen Situationen bewährt haben. | |||||||||||||
| |||||||||||||
|
Diese Seiten sind urheberrechtlich geschützt. Die Verantwortung für die Inhalte und die Rechte der Online-Version liegen beim Autor Reginald Ferber, Münster (Westf). Die Rechte der gedruckten Version beim dpunkt.verlag, Heidelberg. Die Weiterverwendung von Texten oder Abbildungen - auch auszugsweise - ist ohne die schriftliche Zustimmung des Autors Reginald Ferber bzw. des dpunkt.verlags nicht gestattet.
Es wird darauf hingewiesen, dass die verwendeten Soft- und Hardware-Bezeichnungen sowie Markennamen und Produktbezeichnungen der jeweiligen Firmen im Allgemeinen warenzeichen-, marken-, oder patentrechtlichem Schutz unterliegen. Alle Angaben und Programme wurden mit großer Sorgfalt kontrolliert. Trotzdem kann keinerlei Haftung für Schäden irgendwelcher Art übernommen werden, die sich im Zusammenhang mit der Nutzung dieser Seiten ergeben.
Diese HTML-Datei wurde am 27-10-2003 erzeugt.