Regression Tree

Regression Tree

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


Inhaltsverzeichnis

Funktionsweise

Entscheidungsbaum für das Ziegenproblem

Entscheidungsbäume sind Bäume, bei denen bei jeder Verzweigung die Verzweigungsmöglichkeiten (Äste) mit Wahrscheinlichkeiten versehen sind. Sie 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 entlang des Baumes abwärts. Bei jedem Knoten wird ein Attribut abgefragt und eine Entscheidung getroffen. Diese Prozedur 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. Um dieses zu ermitteln, muss der beste Schnitt (split) gefunden werden, d. h. die Aufteilung der Daten muss so gewählt werden, dass sie nach der Aufteilung möglichst rein sind. Ein Maß für die Reinheit ist die Entropie. Aus der Entropie lässt sich dann berechnen, welches Attribut für den Schnitt den höchsten Informationsgewinn bietet. Ein weiteres Maß für die Bestimmung des besten Schnitts ist der Gini-Index. Das ermittelte Attribut wird nun zur Aufteilung der Daten verwendet, 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 und ihre Generierung ist schnell durchführbar.

Ein weiterer Typus von Entscheidungsbaum

Im Rahmen einer anderen Anwendung werden Entscheidungsbäume von links nach rechts gezeichnet (und umgekehrt berechnet), um Payoffs aus Ausgaben und Einnahmen zu errechnen und die Entscheidung für maximalen Payoff zu optimieren.

Image:Investment Decision Occam s Tree.gif

Bei diesen Entscheidungsbäumen stehen Quadrate für Entscheidungen, Kreise für Möglichkeiten, und Dreiecke terminieren die Zweige. Entscheidungsbäume dieses Typs können mit anderen Verfahren kombiniert werden, im Beispiel oben werden NPV (Net Present Value, Netto-Barwert), lineare Verteilung von Annahmen (Investment #2) und PERT 3-Punkt-Schätzung (Investment #1) verwendet.

Beispiel einer Anwendung

Beispiel:Entscheidungsbaum für das Hochladen von Bildern in Wikipedia

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 wie 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. Ein Phänomen des Entscheidungsbaum ist die Überanpassung. Man hat experimentell festgestellt, dass mit zunehmender Komplexität des Baumes die Klassifikationsgüte abnimmt. Als Lösung für das Problem wird Pruning eingesetzt.

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 hingegen bergen 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 (Tree-Based Neural Network), welche die Regeln der Entscheidungsbäume in die Neuronalen Netze übersetzen.

Algorithmen im Vergleich

Die Methoden der Entscheidungsfindung änderten sich mit dem Aufkommen der aktuellen Algorithmen ziemlich stark in den letzten Jahrzehnten. 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 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 werden sie zum Beispiel in den Statistiksoftwarepaketen GNU R, SPSS und SAS angeboten. Die letzteren beiden Pakete verwenden übrigens – wie die meisten anderen Data Mining-Software-Pakete auch – den CHAID-Algorithmus.

Siehe auch


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • regression tree — noun a) A data analysis method that recursively partitions data into sets each of which are simply modeled using regression methods. b) A classification and regression tree …   Wiktionary

  • tree — 1. noun /tɹiː,tʃɹiː/ a) A large plant, not exactly defined, but typically over four meters in height, a single trunk which grows in girth with age and branches (which also grow in circumference with age). is the tallest living tree in the world.… …   Wiktionary

  • Tree allometry — Tree AllometryDefined as the growth or size of some part of a tree in relation to the growth or size of different parts of a tree.The study of allometry is extremely important in dealing with measurements and data analysis in the practice of… …   Wikipedia

  • Decision tree learning — This article is about decision trees in machine learning. For the use of the term in decision analysis, see Decision tree. Decision tree learning, used in statistics, data mining and machine learning, uses a decision tree as a predictive model… …   Wikipedia

  • Unit-weighted regression — In statistics, unit weighted regression is perhaps the easiest form of multiple regression analysis, a method in which two or more variables are used to predict the value of an outcome. At a conceptual level, the example of weight loss can… …   Wikipedia

  • Nonparametric regression — is a form of regression analysis in which the predictor does not take a predetermined form but is constructed according to information derived from the data. Nonparametric regression requires larger sample sizes than regression based on… …   Wikipedia

  • Poisson regression — In statistics, Poisson regression is a form of regression analysis used to model count data and contingency tables. Poisson regression assumes the response variable Y has a Poisson distribution, and assumes the logarithm of its expected value can …   Wikipedia

  • Logistic Model Tree — LMT (Logistic Model Tree) is an algorithm for supervised learning tasks which is combined with linear logistic regression and tree induction. [Niels Landwehr, Mark Hall, and Eibe Frank, [http://www.cs.waikato.ac.nz/ ml/publications/2003/landwehr… …   Wikipedia

  • S (язык программирования)/Temp — Это временная версия статьи S (язык программирования). После внесения в неё правок нужно объединить эту статью со статьёй S (язык программирования) и заменить её содержимое шаблоном {{db}}. Если статья не подходит под формат Википедии, то её… …   Википедия

  • S (язык программирования) — Эту статью следует викифицировать. Пожалуйста, оформите её согласно правилам оформления статей. У этого термина существуют и другие значения, см. S. S  язы …   Википедия

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”