2.3.9.1.1: Sequenzielle Elimination und Auswahl

Zwei klassische Verfahren sind die Elimination oder auch sequenzielle Rückwärtselimination (Sequential Backward Elimination, SBE) und die Auswahl oder auch sequenzielle Vorwärtsauswahl (Sequential Foreward Selection SFS). Bei der Elimination beginnt man mit allen Attributen und lässt dasjenige Attribut weg, bei dem dadurch die Güte der Auswahl am wenigsten leidet. Es handelt sich also um ein Top-down-Verfahren. Dafür müssen zwei Kriterien angegeben werden. Zum einen braucht man (genauso wie beim ID3) ein Maß für die Güte der Auswahl, zum anderen braucht man ein Kriterium, wann das Verfahren abgebrochen werden soll. Dazu werden häufig einfache Heuristiken, wie die prozentuale Verschlechterung der Güte einer Auswahl, verwendet, die mit Grenzen für die maximale und minimale Anzahl von Attributen kombiniert werden.

Die sequenzielle Vorwärtsauswahl verfährt genau andersherum: Zunächst wird das Attribut gesucht, mit dem einzeln die beste Auswahl gebildet werden kann. Dann wird das Attribut hinzugefügt, durch das die Auswahl am stärksten verbessert werden kann. Es handelt sich also um ein Bottom-up-Verfahren. Auch hier braucht man ein Güte- und ein Abbruchkriterium.

Bei der Berechnung der Güte müssen für jedes Attribut die Koeffizienten neu optimiert werden. Das ist für viele Koeffizienten meistens aufwändiger als für wenige. Insofern ist bei der Auswahl mit geringerem Rechenaufwand zu rechnen als bei der Elimination. Andererseits kann man annehmen, das die Elimination die bessere Methode ist, weil aus einem "vollständig informierten Zustand" heraus eliminiert wird, während die Auswahl von gar keiner Information ausgehen kann. Diese Annahme wurde in der Untersuchung von Brodley und Utgoff (1995) [->] allerdings nicht bestätigt.

Auswahl und Elimination lassen sich in einfacher Weise zu einem weiteren Verfahren verbinden, dem Heuristischen Sequenziellen Suchverfahren (Heuristic Sequential Search, HSS). Dazu führten Brodley und Utgoff zunächst den ersten Schritt beider Verfahren durch und verglichen die Güte der Ergebnisse. Dann entschieden sie sich für das Verfahren, dessen Güte im ersten Schritt besser war.