4.4.1.1.1: Sequentielle Elimination und Auswahl

Zwei klassische Verfahren sind die Elimination oder auch sequentielle rückwärts Elimination ( Sequential Backward Elimination SBE) und die Auswahl oder auch sequentielle vorwärts Auswahl ( Sequential Foreward Selection SFS).

Bei der Elimination beginnt man mit allen Attributen und läßt 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 z. B. 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 z. B. die prozentuale Verschlechterung der Auswahl verwendet, die mit Grenzen für die maximale und minimale Anzahl von Attributen kombiniert werden.

Die sequentielle vorwärts Auswahl verfährt genau andersherum: Zunächst wird das Attribut gesucht, mit dem einzeln die beste Auswahl gebildet werden kann, dann wird dazu 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ütekriterium 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 aufwendiger 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 unbedingt bestätigt.

Auswahl und Elimination lassen sich in einfacher Weise zu einem weiteren Verfahren verbinden, dem Heuristischen Sequentiellen 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 Auswahlen. Dann entschieden sie sich für das Verfahren, dessen Güte im ersten Schritt besser war.