Pruning

Begriff und Zweck

Pruning bedeutet in der Informatik das Beschneiden, Vereinfachen und Optimieren von Entscheidungs- oder Suchbäumen. Im maschinellen Lernen soll es vor allem Overfitting verhindern oder verringern. Overfitting liegt hier vor, wenn ein Entscheidungsbaum nicht nur relevante Zusammenhänge, sondern auch Noise aus den Trainingsdaten übernimmt. Noise sind falsche Attributwerte oder Klassenzugehörigkeiten, die Datensätze verfälschen und den Baum unnötig vergrößern.

Beim Pruning werden überflüssige Knoten und Teilbäume entfernt oder durch Blätter ersetzt. Dadurch sinkt die Komplexität des Entscheidungsbaums. Außerdem kann sich die Klassifizierungsgenauigkeit bei zuvor ungesehenen Objekten verbessern. Dabei ist es möglich, dass die Genauigkeit am Testset schlechter wird, während die allgemeine Treffsicherheit der Klassifizierungseigenschaften des Baumes steigt.

Pre-Pruning und Post-Pruning

Pruningverfahren für Entscheidungsbäume werden in Pre-Pruning und Post-Pruning eingeteilt.

Beim Pre-Pruning wird die vollständige Induktion des Training-Sets verhindert. Induktion bezeichnet hier den Aufbau eines Entscheidungsbaums aus Trainingsdaten. Dazu erhält der Induktionsalgorithmus ein Stopp()-Kriterium. Mögliche Kriterien sind eine maximale Baumtiefe oder die Bedingung Information Gain(Attr) > minGain. Der Information Gain bewertet, wie nützlich ein Attribut für die Aufteilung der Daten ist. Pre-Pruning gilt als effizienter, weil nicht zunächst ein vollständiger Baum erzeugt wird, sondern der Baum von Anfang an klein bleibt. Ein gemeinsames Problem dieser Methoden ist der Horizont-Effekt: Das Stopp()-Kriterium kann die Induktion unerwünscht früh abbrechen, obwohl spätere Verzweigungen noch nützliche Informationen liefern könnten.

Beim häufiger eingesetzten Post-Pruning wird zunächst ein Baum aufgebaut und anschließend vereinfacht. Knoten oder Teilbäume werden dabei durch Blätter ersetzt. Post-Pruning-Verfahren lassen sich außerdem danach unterscheiden, ob sie den Baum von unten nach oben oder von oben nach unten bearbeiten.

Bearbeitung von unten oder oben

Bottom-Up-Pruning beginnt an den tiefsten Knoten des Baumes. Das Verfahren bewegt sich rekursiv nach oben und prüft die Relevanz jedes einzelnen Knotens für die Klassifizierung. Ist ein Knoten nicht relevant, wird er entfernt oder durch ein Blatt ersetzt. Ein Vorteil besteht darin, dass keine relevanten Teilbäume verloren gehen können. Zu diesen Verfahren gehören Reduced Error Pruning (REP), Minimum Cost-Complexity-Pruning (MCCP) und Minimum Error Pruning (MEP).

Top-Down-Pruning beginnt dagegen an der Wurzel und folgt der Baumstruktur nach unten. Ein Relevanz-Check entscheidet, ob ein Knoten für die Klassifizierung aller n Items wichtig ist. Wird bereits an einem inneren Knoten beschnitten, kann dadurch ein vollständiger Teilbaum wegfallen, ohne dass dessen einzelne Bestandteile auf ihre Relevanz geprüft werden. Ein Vertreter ist das Pessimistic Error Pruning (PEP), das bei ungesehenen Items gute Ergebnisse erzielen kann.

Pruning in Suchverfahren

Auch Suchalgorithmen beschneiden Bäume. Bei dieser Vorwärtsabschneidung werden Teilbäume nicht weiter untersucht, wenn die bereits gesammelten Daten erkennen lassen, dass sie das gesuchte Objekt nicht enthalten. Beim spekulativen Pruning wird dies lediglich angenommen. Ein Anwendungsgebiet sind Schachprogramme.

Für Minimax- oder Alpha-Beta-Suchen werden unter anderem Nullmove Pruning, Verified Nullmove Pruning, die Killer-Heuristik und die History-Heuristik eingesetzt. Minimax- und Alpha-Beta-Suchen dienen der Lösung von Zwei-Personen-Nullsummenspielen mit vollständiger Information, beispielsweise Schach.

Pruning kommt außerdem in Branch-and-Bound-Algorithmen der mathematischen Optimierung vor. Ein Teilbaum wird dort nicht betrachtet, wenn die Schranke für seine bestmögliche Lösung bereits schlechter ist als eine bekannte Lösung. Die Suche spart dadurch Arbeit, ohne einen Teilbaum weiter auszuwerten, der keine bessere Lösung liefern kann.

Weitere Anwendung

In Forensoftware bezeichnet Pruning eine Einstellung zum automatischen Löschen alter Themen beziehungsweise Topics. Dies soll Speicherplatz sparen, die CPU-Last verringern und dadurch die Geschwindigkeit des Forums erhöhen.