imported>Aka: Halbgeviertstrich, Leerzeichen in Überschrift | Weblinks im Text

2018-08-30T14:34:41Z

Halbgeviertstrich, Leerzeichen in Überschrift | Weblinks im Text

Neue Seite

{{Dieser Artikel|behandelt ein Prinzip beim maschinellen Lernen. Die Neuorganisation synaptischer Verbindungen ist im Artikel [[Synapseneliminierung#Pruning|Synapseneliminierung]] beschrieben.}}
'''Pruning''' ist der [[Englische Sprache|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 [[Vereinfachung von Entscheidungsbäumen|Vereinfachen]], Kürzen und Optimieren von [[Entscheidungsbaum|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 [[Schachprogramm]]en).

Wichtige Pruning-Techniken für [[Minimax-Algorithmus|Minimax-]] oder [[Alpha-Beta-Suche]]n, die zur Lösung von Zwei-Personen-[[Nullsummenspiel]]en mit vollständiger Information (wie zum Beispiel Schach) eingesetzt werden können, sind zum Beispiel:
* [[Null-Zug-Suche|Nullmove Pruning]]
* [[Null-Zug-Suche|Verified Nullmove Pruning]]
* [[Alpha-Beta-Suche#Killer-Heuristik|Killer-Heuristik]]
* [[History-Heuristik]]

Pruning wird auch in [[Branch-and-Bound]]-Algorithmen in der [[Optimierung (Mathematik)|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.

[[Kategorie:Theoretische Informatik]]
[[Kategorie:Algorithmus]]
[[Kategorie:Computerschach]]

Pruning - Versionsgeschichte

imported>Aka: Halbgeviertstrich, Leerzeichen in Überschrift | Weblinks im Text