Decision Trees sind ein sehr beliebtes Tool im Maschinellen Lernen (ML). Hierbei handelt es sich um eine hierarchische, baumartige Struktur, die den Prozess der Entscheidungsfindung graphisch darstellt. Sie können dabei helfen, Entscheidungen zu treffen oder die eigenen Entscheidungen sinnvoll zu erklären und für andere zu veranschaulichen. Allerdings wird die Menge an Daten, die wir benutzen, um diese Entscheidungen zu treffen, immer größer und dadurch auch die Entscheidungsfindung immer komplexer. Durch Pruning kann man die Entscheidungsbäume kürzen und somit weiterhin übersichtlich halten.
Wofür werden Decision Trees eingesetzt?
Decision Trees können in vielen verschiedenen Bereichen zum Einsatz kommen. Ihre Aufgabe besteht dabei allgemein darin, eine Menge an Datenobjekten zu klassifizieren oder Regeln anhand von vorhandenem Wissen darzustellen. Anwendungsbeispiele wären hierbei die Klassifizierung von Bankkunden hinsichtlich ihrer Kreditwürdigkeit, wobei Attribute zur Entscheidungsfindung z.B. der Besitz eines Hauses oder der Familienstand sein könnten. Ein anderes Beispiel wäre die Zuordnung passender Produktempfehlungen für Kunden eines Onlineshops basierend auf deren vorherigen Interessen und Einkäufen. Im Bereich der Medizin könnten Entscheidungsbäume außerdem für die Klassifizierung von Tumoren in gutartig und bösartig verwendet werden. Hierbei könnten Attribute z.B. die Größe oder Textur des Tumors sein.
Der Aufbau von Decision Trees
Der Baum beginnt mit einem initialen Wurzelknoten, von dem verschiedene Pfade über unterschiedlich viele Entscheidungsebenen zu den Blattknoten führen, welche die letztendlichen Entscheidungen repräsentieren. Jeder vorherige Zwischenschritt, welcher durch den jeweiligen inneren Knoten dargestellt wird, steht hierbei für eine Entscheidugsregel über ein Attribut. Bei dieser handelt es sich entweder um eine binäre Ja-Nein-Entscheidung oder eine mehrschichtige Entscheidung für beispielsweise jeden Attributwert. Dies wird anhand eines Restaurantbesuchs in folgendem Beispiel verdeutlicht: Bei diesem steht man vor der Entscheidung, ob man in einem vollen Restaurant auf einen freien Tisch warten sollte oder nicht. Für die Entscheidungsfindung betrachtet der Baum Attribute wie den Preis des Essens, ob man hungrig ist oder auch wie voll das Restaurant ist. Bei Ersterem handelt es sich hierbei um eine Entscheidung zwischen mehreren Attributwerten (drei Preisstufen). Folgt man nun den zutreffenden Entscheidungskanten bis zu einem Blattknoten, gibt dieser wieder, ob es sinnvoller ist zu warten oder nicht zu warten.
Die Selektion der Attribute für den jeweiligen Entscheidungsknoten erfolgt hierbei durch die Maximierung des Informationsgewinns. Dieser wird mithilfe der Entropie und dem verbleibenden Informationsbedarf nach der Attributauswahl berechnet. Als Attribut für den Entscheidungsknoten wird nun jenes gewählt, welches den höchsten Informationsgewinn (Gain) erzielt, diesen also maximiert.
Die Vor- und Nachteile von Decision Trees
Wie wir gerade gesehen haben, sind Entscheidungsbäume in vielen Bereichen anwendbar und dabei in ihrem Aufbau sehr anschaulich und leicht nachzuvollziehen. Daher eigenen sie sich beispielsweise auch gut für die Arbeit und den Austausch mit Partnern, die im Bereich Machine Learning unerfahren sind. Des Weiteren funktionieren sie sowohl für kategorische als auch numerische Datentypen. Die Art des Entscheidungsknotens muss dabei gegebenenfalls angepasst werden. Ein weiterer Vorteil ist die Kombinierbarkeit zu sogenannten Entscheidungswäldern, also einem Ensemble aus Entscheidungsbäumen, wobei die finale Entscheidung z.B. durch einen Mehrheitsentscheid der einzelnen Ergebnisse hervor geht. Ein Beispiel hierfür sind sogenannte Random Forests, welche mehrere verschiedene, unkorrelierte Entscheidungsbäume nach dem Bagging-Prinzip zur Klassifikation nutzen. Zudem spricht für die Verwendung von Decision Trees, dass weniger Data Cleaning notwendig ist, also die Daten vorher nicht großartig bearbeitet werden müssen, verglichen mit anderen Data Modeling Techniken. Allerdings kann der Baum unter Umständen trotzdem noch durch Rauschen beeinflusst werden, wenn er beispielsweise zu sehr an das Trainingsdataset angepasst ist. Man spricht hierbei von Overfitting. Außerdem problematisch wird die Verwendung von Decision Trees bei zu komplexen Datasets. Hierbei kann der Baum schnell sehr groß und unübersichtlich werden. Die positive Eigenschaft, dass die Struktur leicht verständlich ist, geht in diesem Fall verloren.
Was ist Decision Tree Pruning?
Durch Big Data kommt es immer häufiger dazu, dass Decision Trees zu groß und dadurch weniger gut interpretierbar werden. Um dem entgegenzuwirken, dass Decision Trees zu groß und komplex werden, bietet sich an, nur die wichtigsten Entscheidungen zu verwenden. Wir können also unwichtige und repetitive Unterscheidungen weglassen, um den Baum kleiner und übersichtlicher zu halten. Diesen Vorgang nennt man Pruning.
Wichtig ist dabei, dass wir nur Zweige abschneiden, die nicht mehr relevant für uns sind und somit das Ergebnis nicht verschlechtern, sondern im besten Fall sogar verbessern. Abgeschnitten werden also meistens nur jene Zweige, durch die ein bestimmtes Kriterium erfüllt werden. Dieses Kriterium gibt je nach Algorithmus mit unterschiedlichen Vorgehensweisen an, dass der jeweilige Zweig irrelevant ist und den Fehler verschlechtert oder nicht verbessert. In verschiedenen Algorithmen kann man also das Kriterium und zum Beispiel die Durchlaufrichtung an das gegebene Beispiel anpassen.
Welche Arten von Pruning gibt es?
Diese allgemeinen Unterschiede bei Pruning Algorithmen werden im Folgenden genauer erläutert.
Es gibt zwei Möglichkeiten einen Entscheidungsbaum zu prunen. Zunächst kann man einen bereits fertigen Entscheidungsbaum betrachten und Zweige, die nicht mehr gebraucht werden, nachträglich abschneiden. Hierbei spricht man vom Post-Pruning. Die andere Variante ist das sogenannte Pre-Pruning, bei dem schon während der Erstellung des Entscheidungsbaums redundante oder weniger wichtige Äste weggelassen werden.
Post-Pruning wird häufiger benutzt und ersetzt Subtrees durch Knoten, wenn sie als überflüssig angesehen werden. Da es schon zu Beginn einen fertigen Entscheidungsbaum gab, kann man nach dem Pruning die Verbesserungen in Accuracy und Komplexität bei dem gepruntem Baum sehen und mit dem originalen Baum vergleichen.
Pre-Pruning benutzt ein Stopp-Kriterium, wodurch der Baum nicht weiter ausgebildet wird. Ein Beispiel eines solchen Stopp-Kriteriums ist die Tiefe des Baumes. Es wird also vorgegeben, wie viele Entscheidungsknoten hintereinander maximal erstellt werden dürfen. Der Vorgang gilt allgemein als sehr effizient, da der Baum von Anfang an klein gehalten wird und nicht der komplette Datensatz zum Einsatz kommt. Allerdings kann dies dazu führen, dass zu früh geschnitten wird, ohne alle Informationen zu betrachten und deshalb wichtige Informationen verloren gehen. Dieser Effekt wird Horizont Effekt genannt.
Die Richtung, in der man den Baum beim Post-Pruning durchgeht, wird Bottom-Up beziehungsweise Top-Down Pruning genannt. Dies beschreibt, wie die Namen vorgeben, die jeweilige Durchlauf-Richtung des Algorithmus, d.h. von der Wurzel zu den Blättern oder umgekehrt.
Bottom-Up startet beim tiefsten Punkt und wandert dann rekursiv nach oben, während Top-Down Pruning von der Wurzel aus nach unten zu den Blättern geht. Das bildet fürs Top-Down Pruning ein Risiko, dass Subtrees abgeschnitten werden, obwohl sich darunter noch relevante Knoten befinden.
Pruning macht Decision Trees auch weiterhin übersichtlich
Entscheidungsbäume sind also ein praktisches Tool zur einfachen Veranschaulichung von Entscheidungsprozessen zur Klassifikation oder der Darstellung von Regeln. Gerade in der heutigen Zeit von immer größer werdenden Mengen an Daten kann es allerdings zu Problemen kommen, da der Baum ebenfalls zu komplex bzw. unübersichtlich werden kann. Pruning kann helfen, dem entgegenzuwirken und Zweige im Baum entfernen, die zur Ergebnisfindung nicht benötigt werden und daher redundant sind.
Sie möchten das Thema Prinung weiter vertiefen? In unserem nächsten Blog-Beitrag widmen wir uns dem Thema Pruningalgorithmen [später verlinken], in welchem wir die beiden Algorithmen Pessimistic Error Pruning und Minimum Error Pruning gegenüberstellen.
