Titelblatt des Buchs
Reginald Ferber Information Retrieval
Suchmodelle und Data-Mining-Verfahren für Textsammlungen und das Web

Position im Angebot Information Retrieval -> Wissensgewinnung mit Data-Mining-Methoden -> Kategorisieren -> Rahmenbedingungen für Lernalgorithmen
Stichwörter dieser Seite Hill-Climbing, vollständige Suche, Beam-Search
Navigation Zurück ]    [ Inhalt ]    [ Stichwörter ]    [ Feedback ]    [ Home ]

2.3.5.10: 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.

Das ist möglich, wenn einige Voraussetzungen erfüllt sind:

  • Im Raum der Algorithmen gibt es eine Metrik. Das heißt, dass zwischen zwei Algorithmen ein Abstand berechnet werden kann.
  • Die Bewertungsfunktion ist stetig bezüglich dieser Metrik.
  • Der Abstand zu einem Algorithmus, der durch einen Schritt in der Konstruktion erreicht werden kann, ist beschränkt (und klein).
Wenn diese Bedingungen erfüllt sind, bildet die Bewertungsfunktion eine "Gütelandschaft" mit Bergen und Tälern über dem Raum der möglichen Algorithmen. Gesucht wird der Algorithmus mit der besten Bewertung (Güte), also der "höchste Berg" in dieser Landschaft.

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 ).

Pfeil als Kennzeichnung einer Unterueberschrift Abbildung 56: 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 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.

Navigation Zurück ]    [ Inhalt ]    [ Stichwörter ]    [ Feedback ]    [ Home ]
Position im Angebot Information Retrieval -> Wissensgewinnung mit Data-Mining-Methoden -> Kategorisieren -> Rahmenbedingungen für Lernalgorithmen
Dieser Abschnitt und seine Unterabschnitte
Inhalt Stichwörter in der Reihenfolge ihres AuftretensStichwörter alphabetisch sortiert
2.3.5.10Suchstrategien
Abb. 56 Gütefunktion mit lokalen Maxima
Hill-Climbing, vollständige Suche, Beam-Search Beam-Search, Hill-Climbing, vollständige Suche

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.