Return to site

Entscheidungsbäume

· ML Algorithmen

Einleitung

Entscheidungsbäume sind als solche auch außerhalb von Künstlicher Intelligenz und Machine Learning bekannt. Sie bilden einen Geschäftsprozess bzw. ein Regelwerk als Reihe von Entscheidungen in einer Baumstruktur ab. Meistens handelt es sich hierbei um die Klassifizierung eines Objekts, beispielsweise ob ein Kunde kreditwürdig ist oder nicht oder ob ein Fahrzeug ein PKW oder ein LKW ist.

Was ist ein Baum?

Ein Baum besteht aus Knoten, die durch Pfade verbunden sind. Der oberste Knoten wird Wurzelknoten genannt und dort beginnt der Prozess. An jedem Knoten wird eine bestimmte Eigenschaft des Objektes geprüft. Für jedes Ergebnis gibt es einen Pfad zu einem neuen Knoten. Diese folgenden Knoten werden Kindknoten genannt, ein Knoten heißt relativ zu seinen Kindknoten Elternknoten. Diese Struktur wiederholt sich solange, bis wir bei einem sogenannten Blatt ankommen. Blätter sind Knoten, die keine Kindknoten haben und müssen bei einem Entscheidungsbaum immer eine Klasse enthalten.

Vorteile von Entscheidungsbäumen

Aus Trainingsdatensätzen können ML-Programme einen Entscheidungsbaum lernen. Dabei zieht ein Algorithmus anhand der Daten Schlüsse darüber, welche Eigenschaften eines Objekts zu welcher Klasse führen. Der Vorteil von Entscheidungsbäumen ist dabei, dass sie auch von Menschen erstellt werden und eine intuitive Darstellung von Regeln und Abläufen bilden. Menschen können den Baum daher auch händisch prüfen und aus ihm Schlüsse ziehen. Gleichzeitig können diese Regeln von Maschinen effizient und schnell verarbeitet werden, da die Struktur eines Entscheidungsbaums im Gegensatz zu anderen Machine Learning Verfahren wie Neuronalen Netzen wesentlich simpler ist.

Nachteile von Entscheidungsbäumen

Entscheidungsbäume werden nicht fortlaufend erweitert, sondern immer unter Berücksichtigung aller Trainingsbeispiele neu gelernt. Da sich Entscheidungsbäume jedoch an den Regeln aus den Beispieldaten orientieren, wie in der obigen Abbildung zu sehen, brauchen sie nur wenige Datensätze, um gelernt zu werden. Das macht sie jedoch auch anfälliger für "Rauschen", also Datensätze, die aufgrund statistischer Phänomene falsche Daten aufweisen. Der Entscheidungsbaum versucht dabei, sich an die falschen Daten anzupassen, auch "Overfitting" genannt. Dadurch werden eventuell falsche Regeln gelernt, wodurch der Baum eventuell unbekannte Beispiele falsch klassifiziert. An dieser Stelle helfen zunächst mehr Datensätze, jedoch wird der Baum dann auch größer und deswegen kompliziert und unleserlich.
Zur Abhilfe stehen verschiedene Verfahren zur Verfügung, die in der Praxis kombiniert werden. Zum einen werden Entscheidungsbäume beim Lernen bzw. nach dem Lernen "zugeschnitten" (engl. "pruning") und umorganisiert. Da die Struktur und die Effizienz eines Entscheidungsbaums in der Praxis jedoch auch von der Reihenfolge der Trainingsbeispiele und damit praktisch vom Zufall abhängt, verwendet man sogenannte "Random Forests". Dieser Algorithmus wird in einem nachfolgenden Artikel behandelt.

Regressionsbäume

Regression bedeutet, dass die vorherzusagende Größe nicht aus diskreten Klassen besteht, sondern ein fortlaufender Wert ist. Verglichen zu anderen statistischen Methoden wie der linearen Regression modelliert ein Regressionsbaum keinen linearen Zusammenhang zwischen mehreren Variablen, sondern nähert beliebige Zusammenhänge zwischen Ein-und Ausgabe an, indem sie den Raum in Regionen unterteilt, dessen Grenzen achsenparallel verlaufen. Dies wird im Beispiel "Bestimmung der Körpergröße anhand von Alter und Geschlecht" nochmal anschaulich erklärt. Regressionsbäume haben den Vorteil, dass sie einen beliebigen nicht-linearen Zusammenhang abbilden können. Genau wie Kassifikationsbäume leiden Regressionsbäume jedoch häufig unter "Overfitting".

Populäre Algorithmen

Zu den bekanntesten Algorithmen gehören CART, ID3 und C4.5, wobei C4.5 eine verbesserte Version von ID3 ist. ID3 und C4.5 wurden von Ross Quinlan entwickelt. C4.5 hat in der Industrie einen Nachfolger namens C5.0, jedoch tauchen CART, ID3, C4.5 und weitere Algorithmen in verschiedenen Open Source Programmen und Technologien auf. Die Unterschiede ergeben sich in Abhängigkeit von dem zu modellierenden Problem, meist in geringen Unterschieden in der Effizienz oder der Genauigkeit.

Beispiel 1: Ist dieses Fahrzeug ein PKW oder LKW?

Dies ist ein Beispiel für einen Klassifikationsbaum. Normalerweise werden für das Training eines Baums je nach Problemstellung hunderte Trainingsbeispiele gesammelt, zur Anschaulichkeit verwenden wir in diesem Beispiel nur wenige Datenpunkte mit den folgenden Features:

  • Länge des Fahrzeugs in Metern
  • Automarke
  • PS-Anzahl
  • Gewicht in Tonnen
Die Klassen sind dementsprechend "PKW" und "LKW". Die Frage ist nun, welche Größe wir vorhersagen möchten, in unserem Falle ob es sich bei einem Fahrzeug um einen PKW handelt oder um einen LKW. Um einen Baum aus den Beispielen zu lernen, wird zunächst jedes Attribut darauf geprüft, ob es repräsentativ für unsere Vorhersage ist. Beispielsweise sind alle Fahrzeuge, die länger als 7 Meter sind, LKWs. Die Länge ist also ein gutes Maß im Gegensatz zu der Marke, denn es existieren von manchen Marken sowohl PKWs als auch LKWs. Auch die PS des Fahrzeugs ist ein suboptimaler Indikator, denn angenommen, wir gehen davon aus, dass alle Fahrzeuge mit mehr als 600PS LKWs sind, würden Sportwagen fälschlicherweise als PKW klassifiziert. Nimmt man im zweiten Schritt jedoch die Marke dazu, lassen sich die Beispiele trennen.
Wie der Baum am Ende aussieht, hängt vom verwendeten Algorithmus, der maximal erlaubten Tiefe des Baums und der Reihenfolge der Betrachtung der Attribute. Daraus ergeben sich verschiedene Möglichkeiten für einen gelernten Baum, die in der nachfolgenden Abbildung dargestellt sind.

Beispiel 2: Bestimmung der Körpergröße anhand des Alters

Ein Beispiel für einen Regressionsbaum ist die Vorhersage der Größe abhängig vom Alter. In diesem Beispiel könnte der resultierende Regressionsbaum je nach erlaubter Maximaltiefe wie folgt aussehen:

Dieser Regressionsbaum unterteilt den Raum in verschiedene Regionen, die sowohl im Baum, als auch in einem Punktdiagramm zu sehen sind. Der Wert jeder Region gibt die Durchschnittsgröße der Region wieder. Je tiefer der Baum sein darf, desto feiner werden die Unterteilungen. Werden sie jedoch zu fein, kommt es zu Overfitting.

Weiterführende Literatur

Dieser Artikel soll nur einen kurzen Einstieg in die Funktionsweise von Entscheidungsbäumen liefern. Weiterführende Informationen zu diesem und weiteren Themen lassen sich in den Ressourcen finden, die wir auf KI-Business zusammengestellt haben. Für eine Vertiefung dieses Themas ist insbesondere der Grundlagenteil geeignet.

All Posts
×

Almost done…

We just sent you an email. Please click the link in the email to confirm your subscription!

OK