Entscheidungsbaum

Entscheidungsbäume sind eine spezielle Darstellungsform von Entscheidungsregeln. Sie veranschaulichen aufeinanderfolgende hierarchische Entscheidungen. Sie haben eine Bedeutung in der

• Wahrscheinlichkeitsrechnung mit bedingten Wahrscheinlichkeiten (Beispiel bei Absolute Häufigkeit),
• im Data-Mining und
• Entscheidungstheorie:in der ärztlichen Entscheidungsfindung (Medizin) und in der Notfall-Medizin w:Emergency medical service (engl.).

Funktionsweise

Entscheidungsbäume beginnen mit einem Stamm, an dessen Ende sich eine Verzweigung befindet, die in mehrere - mit Wahrscheinlichkeiten versehene - wiederum verzweigte Äste führt. Jeder Endpunkt des Baums ist durch einen eindeutigen Weg erreichbar.

Entscheidungsbäume werden verwendet, um besser und mit weniger Fehlern eine Entscheidung treffen zu können. Im binären Entscheidungsbaum wird eine Serie von Fragen gestellt, welche alle mit Ja oder Nein beantwortet werden können. Diese Serie ergibt ein Resultat, welches durch eine Regel bestimmt ist. Die Regel ist einfach ablesbar, wenn man von der Wurzel her den Ästen des Baumes folgt, bis man zu einem bestimmten Blatt gelangt, welches das Resultat der Fragereihe darstellt.

Entscheidungsbäume trennen die Daten in mehrere Gruppen, welche jeweils durch eine Regel mit mindestens einer Bedingung bestimmt werden.

Um eine Klassifikation abzulesen, geht man dem Baum entlang abwärts. Bei jedem Knoten wird ein Attribut abgefragt und ein Entscheid getroffen. Dieses Prozedere wird so lange fortgesetzt, bis man ein Blatt erreicht.

Generiert werden die Entscheidungsbäume üblicherweise im Top-Down-Prinzip. Bei jedem Schritt wird das Attribut gesucht, mit welchem man die Daten am besten klassifizieren kann. Dieses Attribut wird zur Aufteilung der Daten gebraucht, so dass man die verbliebenen, noch nicht klassifizierten Daten, in weiteren Schritten separat betrachten kann. Entscheidungsbäume werden deshalb auch Klassifikationsbäume genannt.

Entscheidungsbäume können als Systeme zur Regelinduktion angesehen werden. Sie sind einfach und verständlich präsentierbar. Ihre Generierung ist schnell durchführbar.

Beispiel einer Anwendung

Eine Bank möchte mit einer Direct Mailing- Aktion einen neuen Service verkaufen. Um den Gewinn zu maximieren, sollen mit der Aktion diejenigen Haushalte angesprochen werden, welche der Kombination von demografischen Variablen entsprechen, die der entsprechende Entscheidungsbaum als optimal erklärt hat. Dieser Prozess wird Data Segmentation oder auch Segmentation Modeling genannt.

Der Entscheidungsbaum liefert also gute Tipps, wer positiv auf den Versand reagieren könnte. Dies erlaubt der Bank, nur diejenigen Haushalte anzuschreiben, welche der Zielgruppe entsprechen.

Vor- und Nachteile

Die mögliche Größe der Entscheidungsbäume kann sich negativ auswirken. Jede einzelne Regel ist zwar leicht abzulesen, den Gesamtüberblick zu haben ist jedoch sehr schwierig. Es wurden deshalb so genannte Pruning-Methoden entwickelt, welche die Entscheidungsbäume auf eine vernünftige Größe kürzen. Beispielsweise kann man die maximale Tiefe der Bäume beschränken oder eine Mindestanzahl der Objekte pro Knoten festlegen.

Oft bedient man sich der Entscheidungsbäume nur als Zwischenschritt zu einer effizienteren Darstellung des Regelwerkes. Um zu den Regeln zu gelangen, werden durch verschiedene Verfahren unterschiedliche Entscheidungsbäume generiert. Dabei werden häufig auftretende Regeln extrahiert. Die Optimierungen werden überlagert, um einen robusten, allgemeinen und korrekten Regelsatz zu erhalten. Dass die Regeln in keinerlei Beziehungen zueinander stehen und dass widersprüchliche Regeln erzeugt werden können, wirkt sich nachteilig auf diese Methode aus.

Ein großer Vorteil von Entscheidungsbäumen ist, dass sie gut erklärbar und nachvollziehbar sind. Dies erlaubt dem Benutzer, das Ergebnis auszuwerten und Schlüsselattribute zu erkennen. Dies ist vor allem nützlich, wenn die Qualität der Daten nicht bekannt ist. Die Regeln selber können ohne großen Aufwand in eine einfache Sprache wir SQL übernommen werden.

Wirksamkeit und Fehlerrate

Die Wirksamkeit eines Entscheidungsbaumes kann an der Anzahl Prozentpunkte abgelesen werden, welche die Daten korrekt klassifizieren. Einige Regeln funktionieren besser als andere.

Kombination mit Neuronalen Netzen

Entscheidungsbäume werden häufig als Basis für Neuronale Netze verwendet. Sie brauchen nicht so viele Beispiele wie die Neuronalen Netze. Dafür können sie ziemlich ungenau sein, besonders wenn sie klein sind. Große Bäume bergen hingegen die Gefahr, dass etliche Beispiele bei den Trainingsfällen nicht gesehen und registriert werden. Deshalb versucht man Entscheidungsbäume mit Neuronalen Netzen zu kombinieren. Daraus entstanden die so genannten TBNN, welche die Regeln der Entscheidungsbäume in die Neuronalen Netze übersetzen.

Algorithmen im Vergleich

Die Methoden der Entscheidungsfindung änderten sich ziemlich stark in den letzten Jahrzehnten, mit dem Aufkommen der aktuellen Algorithmen. Einige Fachbegriffe wie Wurzel, Kante, Knoten u.ä._ wurden allerdings schon sehr früh benutzt. Noch nicht sehr alt sind die verschiedenen Algorithmen, die zur Berechnung der Entscheidungsbäume verwendet werden.

Die Praxis unterscheidet verschiedene unterschiedliche Baumtypen. Am bekanntesten sind die CARTs (Classification And Regression Trees) und die CHAIDs (Chi-square Automatic Interaction Detectors). In letzter Zeit häufig verwendet wurde auch der C4.5-Algorithmus. Früher wurde stattdessen oft der ID3-Algorithmus verwendet.

Anwendungsprogramme

Es gibt etliche Anwendungsprogramme, die Entscheidungsbäume implementiert haben. So zum Beispiel die beiden Statistiksoftwarepakete SPSS und SAS. Beide verwenden übrigens - wie die meisten anderen Data Mining-Software-Pakete auch - den CHAID-Algorithmus.

Siehe auch

Künstliche Intelligenz, Maschinelles Lernen, Neuronales Netz, Top-Down Induction of Decision Trees

Weblinks

• http://www.medical-cybernetics.de/methods/decis-theory/