Vereinfachung von Entscheidungsbäumen

Entscheidungsbäume (Decision Trees) stammen aus dem Umfeld des maschinellen Lernens, der Künstlichen Intelligenz und des Knowledge Engineering. Sie werden dazu verwendet, Klassifizierungsaufgaben zu modellieren und abzubilden. Bäume werden meist durch Induktion aufgebaut. Die Induktion von Bäumen ist ein NP-vollständiges Problem, weshalb Bäume nicht nachweislich optimal induziert werden können. Daraus ergibt sich das Problem, dass Bäume oft nicht das Idealmaß zwischen Komplexität (Menge an Knoten) und Genauigkeit (predictive accuracy) aufweisen.

Es gibt mehrere Methoden und Ansätze, Bäume zu vereinfachen und dabei die Klassifizierungseigenschaften zu verbessern. Es lässt sich jedes beliebige Datenset (ohne Noise) in Form einer Baumstruktur modellieren, sodass jedes Objekt richtig zugeordnet wird. Ein guter Baum zeichnet sich dadurch aus, eine Vielzahl an ungesehenen Objekten den richtigen Klassenvariablen zuzuweisen, ohne dabei unnötige Komplexität aufzubauen.

In Breslow und Aha sind Motivatoren für die Vereinfachung von Entscheidungsbäumen aufgezählt.

• Manche Bäume schaffen es nicht Zusammenhänge des Datensets kurz und prägnant darzustellen. Andere Modellierungskonzepte würden sich besser eignen.
• Fehler in den Grunddaten (Noise) erzeugen Überanpassung (Overfitting) in Bäumen. Der Baum bildet beides ab: die Zieldefinition und den Noise. Eine höhere Anzahl an Knoten ist die Folge.
• Subbaum Replikation: Teilbäume kommen mehrfach vor.
• Große Bäume sind speziell bei ungesehenen Objekten fehleranfälliger als kleine.

Ansätze der Vereinfachung von Bäumen

Fünf Kategorien der Vereinfachung von Entscheidungsbäumen

• Baumgröße wird verändert (Pruning, incremental treesizing)
• Veränderung des Test-Raums (Data-Driven, Hypothesis-Driven)
• Veränderung der Test-Suche (Auswahlkriterien, Lookahead-Suche)
• Datenbankrestriktionen (Fall- oder Attribut-Selektion)
• Alternative Datenstrukturen (Regeln oder Graphen)

Veränderung der Baumgröße

Pruning beschreibt das Vereinfachen der Baumstruktur durch das Ersetzen von Teilbäumen und Knoten durch Blätter. (Siehe Wikipedia-Artikel Pruning)

Modifikationen im Test-Raum

Bei diesem Ansatz werden einfache Tests (Abfragen in Knoten z. B. humidity = true) durch nicht-triviale Tests ersetzt. Abfragen in Knoten werden durch mathematische Operatoren (numerisch oder logisch) derart verknüpft, dass ganze Teilbäume durch geschicktes Umformen in einem einzelnen Knoten abgefragt werden können (z. B. humidity = true (und) rain = false). Durch diese Operationen ist es möglich einen singulären Pfad durch einen Teilbaum in einer Abfrage einer bestimmten Klasse zuzuweisen. Ist die (und)-verknüpfte Abfrage wahr, wird die Klasse "Positiv" zugewiesen, sonst die Klasse "Negativ". Die Art der Abfrage wird multivarianter Test genannt, da mehrere Attribute gleichzeitig geprüft werden können. Im Gegensatz zu univarianten Tests, wie sie in trivialen Bäumen vorkommen, kann maximal eine Variable (Attribut) in einem Knoten abgefragt werden.

Durch das Verknüpfen der Abfragen ergibt sich eine neue Metrik für die Komplexität der Bäume: Diese ist bei multivarianten Tests die Summe aus Attributen, internen Knoten und Blättern.

Synergieeffekte der multivarianten Tests können sein:

• deutliche Reduktion der Komplexität
• höhere Genauigkeit bei Vorhersagen
• Durch zwei verknüpfte Tests kann mehr Informationsgewinn erzielt werden, wie durch zwei sequenzielle Abfragen. (Information gain)

Data-Driven Test-Konstruktion

Beinhaltet logische und nummerische Konstruktionsoperatoren.

Numerisch

Zur Konstruktion der multivarianten Tests werden numerische Operatoren verwendet: (+, -, ×, ÷ etc.) Diese Klassifikatoren sind lineare, multivariante Tests und werden Perzeptrone genannt. Ein Perzeptron kann wie auch andere Tests nur binäre Ausgänge besitzen. Die Knoten werden auf einer sogenannten Hyperebene (Hyperplane) kombiniert. Dadurch werden kleinere Bäume mit gleicher Genauigkeit realisierbar. (Hyperplane merging) Ein bekannter Vertreter der Perceptron Trees ist der PT2 (Erweiterung des P.-T.) mit Komplexitätsklasse von O(n²).

Logisch

Hierbei werden logische Operatoren verwendet wie z. B. Konjunktion, Disjunktion oder Negation, um Attributabfragen logisch zu verknüpfen. Die Komplexität liegt hierbei bei O(m2^f), für f-features und m-Kombinationen.

Hypothesis-Driven Test-Konstruktion

Bei diesen Verfahren werden Vorteile der Feature interaction (Attribute A und B haben keinen Informationsgewinn für die Klasse C, jedoch hat A x B (x=ein beliebiger Operator) einen deutlichen höheren Information gain als A und B getrennt) bereits bei der Induktion des Baumes verwendet (Konstruktive Induktion). Die Konstruktion von Tests (A x B in einem Knoten) wird während der Induktion evaluiert um von Beginn an ideale Klassifikationseigenschaften herzustellen. Diese Methode wird erfolgreich verwendet, um die Replikation von Teilbäumen zu verhindern.

Kombinierte Attribute werden nach deren gemeinsamen Information gain gereiht um möglichst effiziente Klassifizierungseigenschaften zu erzielen. Ein Vertreter dieser Methodik ist CIRTE, ein auf ID3 basierter Klassifikator, welcher mehr Genauigkeit und kleine Bäume als ID3 produziert. Die Komplexität wird dadurch nicht verringert. (O(m2^(Ci-1)) für i mögliche Attribute)

Modifikation der Test-Suche

Bei diesem Ansatz werden unterschiedliche Selektionskriterien eingesetzt, stetiger Verteilungen diskretisiert und erweiterte Suchmethoden eingesetzt.

Andere Selektionskriterien

Dieser Ansatz verändert die Suche nach den Tests. Die gängigen (primitiven) Selektionskriterien (selection measures) sind z. B. die Entropie eines Attributs (E(A)), der Informationsgehalt IV(A), der Informationsgewinn (gain(A)) durch einen Split. Bereits etwas besser eignet sich der Gain Ration von A, der neben dem Informationsgewinn auch den Informationsverlust durch einen Split berücksichtigt. (gain(A)/IV(A) = GainRatio(A))

Gängige Verfahren sind z. B. die Minimum description length (mdl-measure), die weak theory learning measure (wtlm) bzw. die KS-Distanz.

Umgang mit stetigen Attributen

Weiters werden stetige Attribute zu diskreten Attributen diskretisiert. Algorithmen, wie z. B. der ID3 können nicht mit stetigen Attributwerten umgehen. Daher muss eine stetige Verteilung vor der Induktion in n-Subräume (Cluster) aufgeteilt werden. Im Idealfall werden die Intervallgrenzen der ni so gewählt, dass der Informationsgewinn maximal ist. Bsp. Eine Tabelle speichert die Einkommensverteilung von Personen. Anstatt jedes Gehalt als einen Attributswert aufzufassen (der keinen Informationsgewinn für die Klassenzuweisung bringt), wird die Gehaltstabelle diskretisiert, sodass die Gehälter den Clustern (low, medium und high) zugeordnet werden können. Daraus entsteht ein Informationsgewinn für einen möglichen Split.

Erweiterte Suchfunktionen

Die Lookahead-Suche analysiert mögliche Teilbäume bereits bei der Induktion bis zu einem gewissen Level (j) hinab und wirkt gegen den Horizont-Effekt. An der Stelle d (für Höhe im Baum) wird bereits der (z. B.) GainRatio() für alle Teilbäume bis d+j errechnet. So kann evaluiert werden, ob das weitere Aufspannen des Baums bis d+j sinnvoll ist. Nach jedem Schritt der Induktion wird die Lookahead-Suche ausgeführt. Bei hohem Grad an feature-interaction bringt die Suche 30 % mehr Genauigkeit, sonst aber kaum Vorteile. Die Komplexität dafür ist jedoch extrem hoch mit O(f^d n^d), für f features, n cases und d für Baumtiefe.

Datenbankrestriktionen

Die Vereinfachungsansätze basieren auf zwei grundlegenden Ideen. Einerseits kann die Datenbasis durch Eliminierung von Cases (Zeilen), andererseits durch Entfernen von Features (Spalten) erfolgen. Die entsprechenden Datensätze werden vor Induktion des Baumen entfernt, wenn diese keinen Nutzen für die Klassifikation von Objekten bringen.

Case Selection

Die bekannteste Form der Case-Selektion ist die Windowing-Technik, wie sie bei Qinlan's ID3 zur Anwendung kommt. Ein zufällig ausgewähltes Sub-set an Daten C' (Window) wird induziert (T'). Der nicht verwendete Teil wird zum Testen des Baum T' verwendet. Einige der falsch klassifizierten Objekte aus C-C' werden zum Window hinzugefügt um nochmals einen Baum zu erzeugen. Wenn alle Items richtig klassifiziert wurden, stoppt die Prozedur und T' wird T.

Ein anderer Algorithmus, der auf C4.5 aufsetzt, ist der ROBUST-C4.5. Dabei wird ein Baum T' mit allen Objekten induziert, ge-pruned und getestet. Alle falsch klassifizierten Objekte werden an dem Startset entfernt und ein neuer Baum wird induziert. Diese Iterationen werden so lange ausgeführt, bis alle c aus C richtig zugeordnet wurden. Das Ergebnis ist ein im Mittel 29 % kleinerer Baum als bei ID3 mit ein wenig mehr Genauigkeit.

Feature Selection

Auch hier gibt es zwei konträre Vorgehensweisen einen Baum zu induzieren. Die erste Variante startet mit einem Attribut, induziert einen Baum und testet diesen anschließend. Der Vorgang wird so lange durchgeführt (mit immer einem Attribut mehr), bis die Genauigkeitsmetrik im Test wieder fällt. Dann ist ein semi-optimaler Baum gefunden. Die andere Option ist es mit allen Attributen zu starten und bei jeder Iteration ein Attribut zu entfernen. Wie zuvor ist ein fertiger Baum dann gefunden, wenn die Testergebnisse schlechter werden. Ergebnis dieser Vorgehensweisen sind im Mittel bis zu 50 % kleinere Bäume mit gleicher Genauigkeit, wie bei ID3.

Alternative Datenstrukturen

Eine gängig Form zur Vereinfachung ist es, Bäume in andere Modellierungskonzepte zu übertragen. Oft ist es der Fall, dass dadurch kleinere, schnellere und genauere Modelle gefunden werden können. Eine der möglichen Strukturen sind Entscheidungsgraphen (Decision Graphs). (siehe Wikipedia-Artikel Graphentheorie)

Vorteile der Graphen gegenüber den Bäumen

Vorteile der Graphen gegenüber den Bäumen sind:

• Ein Blatt kommt nur ein Mal vor. (Doppelte Blätter werden verbunden)
• Keine Teilbaum-Replikation
• Leichter zu verstehen

Literatur

• L. A. Breslow and D. W. Aha, Simplifying Decision Trees: A Survey, The Knowledge Engineering Review, Vol 12 (1), 1997, pp. 1–47.
• J. R. Quinlan, Induction of Decision Trees, Machine Learning 1, Kluwer Academic Publishers, 1986, pp. 81–106.