Klassifikations- und Regressionsbäume (Decision Trees)

Datenanalytische Verfahren zur Klassifikation nominaler oder numerischer Variablen auf Grundlagen der mathematischen Informationstheorie (Entropie und GINI Impurity). Ein Entscheidungsbaum ist ein nichtparametrischer überwachter Lernalgorithmus, der sowohl für Klassifizierungs- (bei Nominalvariablen) als auch für Regressionsaufgaben (bei metrischen Variablen) verwendet wird. Er verfügt über eine hierarchische, baumartige Struktur, die aus einem Wurzelknoten, Zweigen, internen Knoten und Blattknoten besteht. Man kann drei grundlegende Arten von Algorithmen unterscheiden: ID3, C4.5 und CART - Algorithmen (s.u.).

• ID3: Ross Quinlan wird die Entwicklung von ID3 zugeschrieben, was eine Abkürzung für „Iterative Dichotomiser 3" ist. Dieser Algorithmus nutzt Entropie und Informationsgewinn als Metriken zur Bewertung der Aufteilung der Kandidaten. Auf einige von Quinlans Forschungsarbeiten zu diesem Algorithmus aus dem Jahr 1986 kann hier (PDF, 1,3 MB) (Link führt zu einer anderen Seite) zugegriffen werden.
• C4.5: Dieser Algorithmus gilt als spätere Iteration der ID3-Algorithmus, der ebenfalls von Quinlan entwickelt wurde. Dieser Algorithmus kann Informationsgewinn oder Gewinnverhältnisse verwenden, um Teilungspunkte innerhalb der Entscheidungsbäume zu bewerten.
• CART: Der Begriff CART ist eine Abkürzung für „Classification and Regression Trees" und wurde von Leo Breiman eingeführt. Dieser Algorithmus verwendet typischerweise die Gini-Impurity, um das ideale Attribut für die Aufteilung zu identifizieren. Die Gini-Unreinheit misst, wie oft ein zufällig ausgewähltes Attribut falsch klassifiziert wird. Bei der Bewertung mit Gini-Unreinheit ist ein niedrigerer Wert besser.