Induktion von Entscheidungsbäumen Seminar Data Mining am Fachgebiet Datenbanken und Informationssysteme Sommersemester 2007 Betreuer: Hendrik Warneke 26.06.2007

Induktion von Entscheidungsbäumen

Seminar Data Mining am Fachgebiet Datenbanken und Informationssysteme

Sommersemester 2007

Betreuer: Hendrik Warneke

26.06.2007

Mirko Stratmann

Induktion von Entscheidungsbäumen | 26.06.2007 | Folie 2Mirko Stratmann

Agenda

Motivation für Klassifikation Entscheidungsbäume Induktion von Entscheidungsbäumen

Splitting-Kriterien Abbruchkriterien Overfitting Pruning-Methoden

Zusammenfassung


Motivation für Klassifikation

bisher: Assoziationsregeln

Nun: Klassifikation aus Daten Prognosen für die Zukunft ableiten Beispiele: Finanzbranche, Medizin, Energie schnellere, sicherere Prognose

Vorgehensweise Ableiten von explizitem Wissen aus Daten kompakte Repräsentation von Wissen

Wir verwenden dazu Entscheidungsbäume


Entscheidungsbäume

Entscheidungsbäume sind Bäume Innere Knoten: Attribute Kanten: Tests Blätter: Klassen

Attribute kategorisch numerisch

Tests führen zu Split

Klassen sollen zugeordnet werden


Beispiel: Datengrundlage


Beispiel: Entscheidungsbaum

nicht alle Attribute wurden zum Aufbau des Entscheidungsbaums genutzt Klassifikationsgenauigkeit ist 1 für Beispieldaten


Beispiel: Klassifikationsregeln

Aus Entscheidungsbäume lassen sich Klassifikationsregeln ableiten: Für jedes Blatt: Und-Verknüpfung aller Tests auf dem Pfad


Induktion von Entscheidungsbäumen

Konstruktion eines Entscheidungsbaums aus einer Menge von klassifizierten Datensätzen meist: Teilen dieser Menge in Trainingsdatenmenge

und Testdatenmenge Ermitteln des Klassifikationsfehlers auf Testdatenmenge

2 Phasen: Growing & Pruning Growing: (Top-Down) Aufbau des Baums mit Hilfe von Splitting-

Kriterien bis Abbruchkriterium erfüllt dazu rekursives Partitionieren des Traingsdatenraums

Pruning: (Bottom-up) “Stutzen” des Baums für bessere Klassifikationsperformance


Splitting-Kriterien

Ein weiterer Entscheidungsbaum für unser Beispiel…


Splitting-Kriterien (2)

Ziele Baum möglichst klein und kompakt gute Klassifikationsgenauigkeit

Auswahl des besten Splits erforderlich Eigentlich: Betrachte alle möglichen Splits: auch Teilmengensplits hier Vereinfachung: immer komplette Splits und nur für Tests der Form

Attribut = Wert

Splitting-Kriterien bewerten Splits InformationGain GiniGain u.v.m.


InformationGain

zunächst: Maß für den Informationsgehalt einer Darstellung Informationstheorie: Shannon’sche Entropie

y: Zielattribut S: Trainingsdatenmenge σy=cj

S: Menge der Datensätze aus S mit Klasse cj


Maß für die Veränderung der Entropie

y: Zielattribut S: Trainingsdatenmenge ai: mögliches Attribut für den Split

σai=ci,jS: Menge der Datensätze aus S mit Attribut ai hat Wert vi,j

InformationGain


Entwicklung am Beispiel – Vor dem ersten Split


Entwicklung am Beispiel (2)

Split nach Aussicht bringt größten Informationsgewinn


Entwicklung am Beispiel (3) – Nach dem ersten Split


Gini

Maß für die Unreinheit

y: Zielattribut S: Trainingsdatenmenge σy=cj

S: Menge der Datensätze aus S mit Klasse cj


GiniGain

Maß für die Abnahme der Unreinheit

y: Zielattribut S: Trainingsdatenmenge ai: mögliches Attribut für den Split

σai=ci,jS: Menge der Datensätze aus S mit Attribut ai hat Wert vi,j


GiniGain vs. InformationGain

InformationGain und Gini liefern hier ähnliche Ergebnisse!


Overfitting

Klassifikationsgenauigkeit

Je länger die Growing-Phase, desto besser die Klassifikationsgenauigkeit→ auf den Trainingsdaten

Trainingsdaten fehlende Werte nicht repräsentative Auswahl falsch klassifizierte Datensätze Rauschen

Überanpassung an Trainingsdaten zeigt Overfitting-Effekt


Overfitting (2)

fehlerhaft klassifizierter Datensatz

verfeinerter Entscheidungsbaum durch fehlerhaften Datensatz


Overfitting (3)

( aus: Ester, Sander: Knowledge Discovery in Databases)“fully-grown tree” kann so nicht sinnvoll sein!

Aber wie sollte man das Abbruchkriterium wählen?


Abbruchkriterien

Growing des Entscheidungsbaums bis zu AbbruchkriteriumTypische Beispiele:

Alle Datensätze der Trainingsdatenmenge haben den gleichen Wert für dasZielattribut

Die maximale Höhe des Entscheidungsbaums ist erreicht Die Zahl der Fälle (Datensätze) in den untersten Knoten ist geringer als die

minimale Anzahl von Fällen für Elternknoten Falls der Knoten gesplittet würde, dann wäre die Zahl der Fälle eines oder

mehrerer Kindknoten geringer als die minimale Zahl an Fällen pro Kindknoten Das beste Ergebnis eines Splitting Kriteriums ist unter einem gewissen

Schwellwert


Pruning

Festlegen von geeigneten Abbruchkriterien schwierig:Pruning kann die Klassifikationsgenauigkeit erhöhen

Reduced Error Pruning Trainingsmenge und Testmenge Prüfen, ob Prunen eines Knotens die Klassifikationsperformance auf

Testdatenmenge verbessert Zurückschneiden so lange der Klassifikationsfehler abnimmt

→


Ansatz: Berücksichtigung der Kostenkomplexität

α: Kostenkomplexitätsparameterε: Funktion, die Fehler auf den Trainingsdaten berechnet|leaves(T)| : Anzahl der Blätter von Baum T

T(α) ist der Teilbaum, der die Kostenkomplexität unter Bezug auf α minimiert

Minimal Cost-Complexity Pruning


anschaulich: Anstieg der Fehlerrate pro gepruntem Blatt

Vorgehen Konstruiere Folge von Teilbäumen T1, … , Tk

dabei ist T1 der durch Growing ermittelte Baumund Tk der Teilbaum ist, der nur aus der Wurzel besteht

Prüfe für jeden Teilknoten von Ti den Kostenkomplexitätsparameter αund prune den Knoten, bei dem α minimimal ist und erhalte so Ti+1

Bestimme für die Folge T1, … , Tk die Klassifikationsgenauigkeit und wähle den Teilbaum mit dem geringsten Fehler auf den Testdaten

Minimal Cost-Complexity Pruning (2)


Welche Pruning-Methode ist die beste?

Es gibt viele weitere Pruning-Methoden

Performancetests der Pruningmethoden zeigen Manche Methoden wie Minimal Cost-Complexity Pruning neigen zu

Over-Pruning Manche Methoden neigen zu Under-Pruning Zurückschneiden so lange der Klassifikationsfehler abnimmt “There ain't no such thing as a free lunch”

Es gibt keine Pruning-Methode die in jedem Fall den besten Entscheidungsbaum liefert


Kleiner historischer Systemvergleich

ID3 (Iterative Dichotonomiser 3, Quinlan 1986) nutzt InformationGain als Splitting-Kriterium kein Pruning weiterentwickelt: C4.5 (1993)

CART (Classification and Regression Trees, Breiman 1984) Besonderheit: erzeugt (binäre) Regressionsbäume nutzt Minimal Cost-Complexity Pruning

Nicht für große Datenmengen geeignet, dafür eigene Algorithmen wie SLIQ und SPRINT


Bewertung von Entscheidungsbaumklassifikatoren

Entscheidungsbäume sind selbsterklärend und von Experten überprüfbar können mit kategorischen und numerischen Attributen

umgehen sind fehlertolerant (falsche und fehlende Datensätze,

Rauschen) viele Algorithmen treffen nur diskrete Vorhersagen

Attribute sollten möglichst relevant sein


Zusammenfassung

Motivation für Klassifikation Entscheidungsbäume Induktion von Entscheidungsbäumen

Splitting-Kriterien Abbruchkriterien Overfitting Pruning-Methoden

Zusammenfassung


Danke für Ihre Aufmerksamkeit!

Fragen?

Fragen?

Fragen?Fragen?

Fragen?

?


Literatur und Quellen

L. Rokach, O. Maimon: Kapitel 9 Decision Trees in: The Data Mining andKnowledge Discovery Handbook, Springer 2005, 165-192

J.R. Quinlan: Induction of Decision Trees, Machine Learning Vol. 1, Num. 1,S. 81-106, Springer 1986, 81-106

M. Ester, J. Sander: Knowledge Discovery in Databases, Springer 2000

M. Lusti: Data Warehousing und Data Mining, Springer 1999

I.H. Witten, E. Frank: Data Mining, Hanser 2001

J. Han, M. Kamber: Data Mining - Concepts and Techniques, Morgan Kaufmann 2006

L. Breiman, J.H. Friedman, R.A. Olshen, C.J. Stone: Classification of Regression Trees, Wadsworth 1984


Wann haben der Ausgangsbaum und der geprunte Baum die gleiche Kostenkomplexität?

für einen bestimmten Wert von α

Anschaulich: der Anstieg der Fehlerrate pro gepruntem Blatt, also ein Maß dafür, welchen Anstieg des Klassifikationsfehlers auf den Trainingsdaten wir für die Verringerung der Komplexität des Baums in Kauf nehmen müssen.

Anhang: Minimal Cost-Complexity Pruning


Anhang: verschiedene Splits (1)


Anhang: verschiedene Splits (2)

InformationGain und Gini liefern ähnliche Ergebnisse!

Documents

Induktion von Entscheidungsbäumen Seminar Data Mining am Fachgebiet Datenbanken und Informationssysteme Sommersemester 2007 Betreuer: Hendrik Warneke 26.06.2007