Pruning

Pruning ist der englische Ausdruck für das Beschneiden (Zurechtstutzen) von Bäumen und Sträuchern. In der Informatik im Umfeld des maschinellen Lernens wird der Ausdruck für das Vereinfachen, Kürzen und Optimieren von Entscheidungsbäumen verwendet.

Die Idee des Pruning entstammt ursprünglich aus dem Versuch, das sog. Overfitting bei Bäumen zu verhindern, die durch induziertes Lernen entstanden sind. Overfitting bezeichnet die unerwünschte Induktion von Noise in einem Baum. Noise bezeichnet falsche Attributwerte oder Klassenzugehörigkeiten, welche Datensets verfälschen und so Entscheidungsbäume unnötig vergrößern. Durch das Pruning der Bäume werden die unnötigen Sub-Bäume wieder gekürzt.

Pruning im Umfeld des maschinellen Lernens

Pruningverfahren lassen sich nach zwei Arten teilen (Pre- und Post-Pruning).

Pre-Pruning-Verfahren verhindern eine vollständige Induktion des Training-Sets durch Austausch eines Stopp()-Kriteriums im Induktionsalgorithmus (z. B. max. Baumtiefe oder Information Gain(Attr) > minGain). Pre-Pruning-Methoden gelten als effizienter, da dabei nicht ein gesamtes Set induziert wird, sondern Bäume von Beginn an klein bleiben. Prepruning-Methoden haben ein gemeinsames Problem, den Horizont-Effekt. Darunter ist das unerwünschte, vorzeitige Abbrechen der Induktion durch das Stopp()-Kriterium zu verstehen.

Post-Pruning (oder nur Pruning) ist das häufigst eingesetzte Verfahren, Bäume zu vereinfachen. Dabei werden Knoten und Teilbäume durch Blätter ersetzt, um die Komplexität zu verbessern. Durch Pruning lässt sich nicht nur die Größe entscheidend verringern, sondern auch die Klassifizierungsgenauigkeit ungesehener Objekte verbessern. Zwar kann es der Fall sein, dass die Genauigkeit der Zuordnung am Testset schlechter wird, die Treffsicherheit der Klassifizierungseigenschaften des Baumes jedoch insgesamt steigt.

Die Verfahren werden anhand deren Vorgehensweise im Baum (Top-Down bzw. Bottom-Up) unterschieden.

Bottom-Up-Pruning

Diese Verfahren starten am letzten Knoten im Baum (an der tiefsten Stelle). Rekursiv nach oben folgend bestimmen sie die Relevanz jedes einzelnen Knotens. Ist die Relevanz für die Klassifizierung nicht gegeben, fällt der Knoten weg bzw. wird durch ein Blatt ersetzt. Der Vorteil ist, dass durch dieses Verfahren keine relevanten Sub-Bäume verloren gehen können. Zu diesen Verfahren zählt das Reduced Error Pruning (REP), das Minimum Cost-Complexity-Pruning (MCCP) oder das Minimum Error Pruning (MEP).

Top-Down-Pruning

Im Gegensatz zum Bottom-Up-Verfahren setzt diese Methodik an der Wurzel des Baumes an. Der Struktur nach unten folgend wird ein Relevanz-Check durchgeführt, welcher entscheidet, ob ein Knoten für die Klassifizierung aller n Items relevant ist oder nicht. Durch Beschneiden des Baums an einem inneren Knoten kann es passieren, dass ein gesamter Sub-Baum (ungeachtet dessen Relevanz) wegfällt. Zu diesen Vertretern gehört das Pessimistic Error Pruning (PEP), welches durchaus gute Resultate bei ungesehenen Items bringt.

Suchverfahren

Bei Suchverfahren verwendet man verschiedene Pruning-Methoden zur Vorwärtsabschneidung von Suchbäumen, wenn der Algorithmus auf Grund der bereits gesammelten Daten weiß (bzw. bei spekulativem Pruning davon ausgeht), dass diese Teilbäume das gesuchte Objekt nicht enthalten (angewandt zum Beispiel bei Schachprogrammen).

Wichtige Pruning-Techniken für Minimax- oder Alpha-Beta-Suchen, die zur Lösung von Zwei-Personen-Nullsummenspielen mit vollständiger Information (wie zum Beispiel Schach) eingesetzt werden können, sind zum Beispiel:

• Nullmove Pruning
• Verified Nullmove Pruning
• Killer-Heuristik
• History-Heuristik

Pruning wird auch in Branch-and-Bound-Algorithmen in der mathematischen Optimierung angewandt. Hier wird ein Teilbaum des Suchbaums nicht betrachtet, falls die Schranke für die beste mögliche Lösung in diesem Teilbaum schlechter ist als eine bereits bekannte Lösung.

Weitere Gebiete

Bei Forensoftware ist Pruning eine Einstellung, die das automatische Löschen von alten Themen (Topics) bewirkt, um Speicherplatz zu sparen, die CPU-Last zu verringern und dadurch die Schnelligkeit des Forums zu erhöhen.

Quellenverweise

• L. A. Breslow and D. W. Aha, Simplifying Decision Trees: A Survey, The Knowledge Engineering Review, Vol 12 (1), 1997, pp. 1–47.
• J. R. Quinlan, Induction of Decision Trees, Machine Learning 1, Kluwer Academic Publishers, 1986, pp. 81–106.