Pessimistic Error Pruning (PEP)<\/h2>\n\n\n\n
Beim Pessimistic Error Pruning Algorithmus handelt es sich um einen Top-Down<\/strong>-Pruningalgorithmus. Das bedeutet, wir beginnen mit der Wurzel und \u00fcberpr\u00fcfen dann von oben nach unten f\u00fcr jeden Entscheidungsknoten, ob dieser relevant f\u00fcr das Endergebnis ist oder abgeschnitten werden sollte. F\u00fcr jeden Knoten t berechnen wir dabei Folgendes:<\/p>\n\n\n\n Gepruned wird nun, wenn die Summe aus Standard Error und Fehler des Subtrees gr\u00f6\u00dfer oder gleich dem Fehler des Knotens ist. Der Knoten t macht dann n\u00e4mlich als Blattknoten weniger Fehler als der Subtree.<\/p>\n\n\n\n Dies wird an folgendem Beispiel veranschaulicht:<\/p>\n\n\n\n Wir betrachten eine Datenbank, die verschiedene Arten von Iris-Blumen beinhaltet und diese anhand von deren verschiedenen Bl\u00fctenblatt- und Kelchblattgr\u00f6\u00dfen klassifiziert. Die 150 Blumen kann man dabei in drei Unterarten sortieren (Setosa, Virginica, Versicolor). Zuerst haben wir diese nun mithilfe eines Entscheidungsbaumes mithilfe der Attribute klassifiziert. Im Folgenden werden die beiden Algorithmen auf diesen Baum angewendet und es wird dann erkl\u00e4rt, was bei dem Pruning jeweils passiert.<\/p>\n\n\n\n F\u00fcr den Pessimistic Error Pruning Algorithmus (PEP) schauen wir uns daf\u00fcr beispielhaft folgende 3 Knoten in dem dargestellten Baum an. Mit Knoten A sehen wir zuerst die Wurzel. Da es sich bei dem Algorithmus um einen Top-Down Algorithmus handelt, ist die Wurzel auch aus Sicht des Algorithmus der erste Knoten, der betrachtet wird. Da hier 40 + 39 = 79 Samples nicht der Mehrheitsklasse (blau markiert) zugeordnet wurden, erhalten wir einen Fehler von 79.5 (inklusive der Kontinuit\u00e4tskorrektur) f\u00fcr den Wurzelknoten. Der Fehler des Subtrees betr\u00e4gt beim Wurzelknoten 4, da wir von diesem insgesamt 8 Blattknoten erreichen k\u00f6nnen, die jeweils einen Fehler von 0 haben. Der Standarderror betr\u00e4gt mit Einbezug der insgesamt 120 Samples, die im Wurzelknoten betrachtet werden, etwa 1.97. Da der Fehler des Wurzelknotens mit 79.5 also gr\u00f6\u00dfer als die Summe aus dem Fehler des Subtrees und des Standarderrors (4 + 1.97 = 5.97) ist, ist das Pruningkriterium also nicht erf\u00fcllt und es wird nicht geprunt. Betrachten wir nun die beiden Knoten im Baum, die das Pruningkriterium erf\u00fcllen: Blattknoten B hat 1 von 37 falsch zugeordnete Samples, also einen Knoten-Fehler von 1.5, sowie 3 erreichbare Blattknoten mit jeweils einem Knoten-Fehler von 0, was einen Subtree-Fehler von 1.5 und einen Standarderror von etwa 1.19 ergibt. Somit ist das Pruningkriterium erf\u00fcllt, da der Knoten-Fehler kleiner als die Summe aus Subtree-Fehler und Standarderror ist (1.5 < 1.5 + 1.19). Bei Knoten C ist dies mit 1.5 < 1 + 0.99 ebenfalls der Fall. Bei den Knoten wird also jeweils geprunt, also die darunter liegenden Teilb\u00e4ume abgeschnitten. Die Knoten werden dadurch zu Blattknoten. Durch diesen Vorgang wird der Baum nicht nur kompakter, sondern die Accuracy verbessert sich auch von 93% auf etwa 97%.<\/p>\n\n\n\n Der andere Algorithmus den wir betrachten, durchl\u00e4uft den Baum andersherum (Bottom-Up<\/strong>). Der Baum wird von unten nach oben durchlaufen \u2013 also von den Bl\u00e4ttern zu der Wurzel, wobei zus\u00e4tzlich eine andere Formel verwendet wird, um unsere Knoten zu bewerten.<\/p>\n\n\n\n Das Grundprinzip ist hierbei, dass wir den Fehler von einem Elternknoten mit seinen Kinderknoten vergleichen. Dadurch pr\u00fcfen wir, ob die Kinderknoten den Fehler verbessern werden oder nicht. Wenn die Kinder einen geringeren Fehler haben, tragen sie positiv zum Ergebnis bei und werden behalten. Wenn der Fehler der Kinder allerdings gr\u00f6\u00dfer ist, wird durch sie das Ergebnis schlechter und die Kindknoten deswegen entfernt. Um den Fehler von dem Elternknoten zu berechnen, benutzen wir einen Parameter m, der urspr\u00fcnglich den Einfluss von der a-priori Wahrscheinlichkeit pai<\/sub>, dass ein Sample nicht in einer bestimmten Klasse ist, bestimmt:<\/p>\n\n\n\n Zur Vereinfachung verwenden wir als pai<\/sub> einfach 1\/Anzahl der Klassen k und f\u00fcr m ebenfalls die Anzahl der Klassen. Dadurch verschwindet die a-priori Wahrscheinlichkeit pai<\/sub> aus unserer Formel f\u00fcr die Berechnung des Fehlers: <\/p>\n\n\n\n Um diesen Fehler mit dem von den Kindknoten vergleichen zu k\u00f6nnen, m\u00fcssen wir die Fehler der Kinder miteinander verrechnen. Dabei ist es wichtig, dass der Knoten, der \u00fcber mehr Samples entscheidet, auch mit einer h\u00f6heren Gewichtung bewertet wird. Diese Gewichte bestimmen den Einfluss der jeweiligen Kindknoten. Das Gewicht beschreibt die Wahrscheinlichkeit, dass ein Sample in den jeweiligen Kindknoten geht. Wie anfangs schon erw\u00e4hnt, muss jetzt der Fehler der Kinder gr\u00f6\u00dfer sein als der des Elternknotens, damit wir den Subtree abschneiden k\u00f6nnen.<\/p>\n\n\n\n Nun wird dieses Prinzip an dem gleichen Baum demonstriert wie bei dem ersten Algorithmus:<\/p>\n\n\n\n Da MEP ein Bottom-up Algorithmus ist, betrachten wir zuerst die Blattknoten, welche in der Abbildung mit A und B beschriftet sind. Um zu entscheiden, ob diese ein Teil des Baumes bleiben oder abgeschnitten werden, m\u00fcssen wir ihren gemeinsamen gewichteten Fehler mit dem von dem Elternknoten vergleichen. Die Kinder haben beide jeweils das gleiche Gewicht und den gleichen Fehler, da beide ein Sample haben, was in dem jeweiligen Knoten richtig klassifiziert wird. Der gemeinsame Fehler lautet in dem Fall 1\/2. Der Fehler von dem Elternknoten der beiden (Knoten C) ist 3\/5. Dementsprechend wird der Fehler bei den Kindknoten A und C minimiert, weshalb diese im Baum bleiben.<\/p>\n\n\n\n Mit dem n\u00e4chsten Schritt gehen wir einen Knoten h\u00f6her und vergleichen nun Knoten D und C mit ihrem Elternknoten E. D und C haben jeweils einen Fehler von 0,082 und E einen Fehler von 0,075. In diesem Fall ist es jetzt also andersherum. Die Kinder des Knotens E verschlechtern den Fehler und sind deswegen unbrauchbar f\u00fcr unseren Entscheidungsbaum. Dementsprechend werden sie abgeschnitten und der Decision Tree verkleinert.<\/p>\n\n\n\n Die restlichen Abgleiche im Baum f\u00fchren dazu, dass nicht weiter gepruned wird und unser Entscheidungsbaum ist damit fertig.<\/p>\n\n\n\n Beide Algorithmen haben dasselbe Grundprinzip, bei welchem die Bedeutung von Knoten bewertet werden. Der gr\u00f6\u00dfte Unterschied ist die Bearbeitungsrichtung. Grunds\u00e4tzlich gelten die Top-down Verfahren als risikoreicher, da wichtige Branches unkontrolliert abgeschnitten werden k\u00f6nnten. PEP sorgt in dem Fall durch das Pruningkriterium daf\u00fcr, dass meistens in den richtigen Situationen und auch ausreichend gepruned wird. Auf der anderen Seite ist in der Minimum-Error-Algorithmus au\u00dferdem sehr vorsichtig und pruned vergleichsweise selten, weshalb kaum nennenswerte Verbesserungen eintreten. Dementsprechend ist der MEP-Algorithmus in den meisten F\u00e4llen die schlechtere Wahl, obwohl es sich um das risiko\u00e4rmere Prinzip handelt. <\/p>\n\n\n\n Dies sieht man sehr anschaulich ich dem folgenden Beispiel:<\/p>\n\n\n\n Es handelt sich hierbei um einen Datensatz zur Klassifikation von Brustkrebs, bei welchem anhand von verschiedenen Attributen wie beispielsweise der Gr\u00f6\u00dfe oder Konkavit\u00e4t eines Tumors eine Einordnung in gutartige und b\u00f6sartige Tumore ermittelt wird.<\/p>\n\n\n\n Die beiden Algorithmen k\u00f6nnen Entscheidungsb\u00e4ume dieses Datensatzes k\u00fcrzen. Als PEP auf einen Entscheidungsbaum dieses Datensatzes angewendet wird, wurde die Anzahl der Bl\u00e4tter von 19 auf 8 reduziert, was deutlich zeigt, dass der Baum \u00fcbersichtlicher geworden ist. Zus\u00e4tzlich ist die Fehlerrate geringer geworden, da von den Daten, auf denen der Baum getestet wurde, 2 zus\u00e4tzliche Samples korrekt klassifiziert wurden.<\/p>\n\n\n\n MEP hat bei dem dort angewendeten Baum lediglich von 15 Bl\u00e4ttern auf 13 gek\u00fcrzt und hatte keine Verbesserung in der Fehlerrate. Dementsprechend stellen wir fest, dass auch bei diesem Datensatz PEP bessere Ergebnisse liefert.<\/p>\n\n\n\n Abschlie\u00dfend kann man sehen, dass es sehr relevant sein kann, f\u00fcr welche Algorithmen man sich genau entscheidet, obwohl beide das gleiche Ziel haben. Kleinste Unterschiede in Algorithmen k\u00f6nnen einen Einfluss auf das Endergebnis haben, welches in unserem Fall bei dem Pessimistic-Error-Pruning Algorithmus definitiv besser ist. Allerdings ist es wichtig zu erw\u00e4hnen, dass diese Algorithmen nicht die einzigen Pruning Algorithmen sind und f\u00fcr verschiedene B\u00e4ume\/Anwendungen verschiedene Algorithmen in Frage kommen k\u00f6nnen. Es gilt also genau abzuw\u00e4gen, welchen Algorithmus man f\u00fcr ein spezifisches Problem verwendet.<\/p>\n\n\n\n Verwendete Datasets:<\/p>\n\n\n\n Sowohl das Iris Dataset als auch das Brustkrebs Dataset, mit welchen wir die Entscheidungsb\u00e4ume erstellt haben, stammen von scikit-learn:<\/p>\n\n\n\n Iris Blumen: https:\/\/scikit-learn.org\/stable\/auto_examples\/datasets\/plot_iris_dataset.html<\/a> <\/p>\n\n\n\n\n
![\"-](\"https:\/\/lamarr-institute.org\/wp-content\/uploads\/formel_fraundwingenfeld_2.png\" "\\"\\"")
<\/figure>\n\n\n\n![\"-](\"https:\/\/lamarr-institute.org\/wp-content\/uploads\/\/2_MinimumErrorPruning-1024x576.jpg\" "\\"\\"")
Entscheidungsbaum zur Klassifizierung von Iris-Blumen mit Entscheidungsknoten (blau) und Blattknoten (rot). Die roten Trennlinien stellen die durchgef\u00fchrten Pruningschritte des Pessimistic Error Pruning Algorithmus dar.
\u00a9 Michelle Fraund und Julia Wingenfeld<\/figcaption><\/figure>\n\n\n\nMinimum Error Pruning (MEP)<\/h2>\n\n\n\n
![\"-](\"https:\/\/lamarr-institute.org\/wp-content\/uploads\/formel_2_fraundwingenfeld_2.png\" "\\"\\"")
<\/figure>\n\n\n\n![\"-](\"https:\/\/lamarr-institute.org\/wp-content\/uploads\/formel_3_fraundwingenfeld_2.png\" "\\"\\"")
<\/figure>\n\n\n\n![\"-](\"https:\/\/lamarr-institute.org\/wp-content\/uploads\/\/2_PessimisticErrorPruning-1024x576.jpg\" "\\"\\"")
Entscheidungsbaum zur Klassifizierung von Iris-Blumen mit Entscheidungsknoten (blau) und Blattknoten (rot). Die rote Trennlinie stellt den durchgef\u00fchrten Pruningschritt des Minimum Error Pruning Algorithmus dar.
\u00a9 Michelle Fraund und Julia Wingenfeld<\/figcaption><\/figure>\n\n\n\nVergleich der beiden Algorithmen<\/h2>\n\n\n\n
![\"-](\"https:\/\/lamarr-institute.org\/wp-content\/uploads\/\/Vergleich_PEP_MEP_eng-1024x576.png\" "\\"\\"")
Grobe Darstellung zweier Entscheidungsb\u00e4ume zur Veranschaulichung des Gr\u00f6\u00dfenunterschieds nach Anwendung der beiden Pruningverfahren. Zu sehen sind Entscheidungsknoten basierend auf verschiedenen Attributen wie z.B. der Tumorgr\u00f6\u00dfe (blau) und die Blattknoten zur Klassifikation in gutartig (gr\u00fcn) und b\u00f6sartig (rot).
\u00a9 Michelle Fraund und Julia Wingenfeld<\/figcaption><\/figure>\n\n\n\nFazit<\/h2>\n\n\n\n