eNTSCHEIDUNGSBÄUME

Question 1

Einordnung in das CRISP-DM Referenz-Modell

Answer 1

Modeling Phase (Phase 4)

Question 2

Aufbau einfacher Entscheidungsbaum

Answer 2

2 Attribute, 2 Klassen

Question 3

Entscheidungsbaum: Basisalgorithmus

Answer 3

• WENN alle Datensätze in E zur selben Klasse C gehören
  DANN ist C das Ergebnis SONST:
  -> wähle ein Attribut A mit den Werten w 1 , w n
  -> partitioniere E in E 1 , …, E n abhängig von den Wertausprägungen des Attributes A;
  -> konstruiere Unterbäume T 1 , …, T n für E 1 , …, E n
  -> das Ergebnis ist der Baum T mit der Wurzel A und den beschrifteten Kanten w 1 , …, w n zu den Unterbäumen T 1 , …, T n
• Der Algorithmus wird rekursiv wieder auf die jeweiligen Unterbäume T i angewendet, solange bis jeder Knoten nur noch nicht weiter unterscheidbare Datensätze (einer Klasse) enthält.

Question 4

Warum ist ein einfacher, kleinerer Baum mit wenig Blättern (der die Datensätze korrekt klassifiziert) besser als ein Größerer?

Answer 4

• Verhinderung von Überanpassung ( Overfitting)
• Das Ziel ist, nicht die Trainingsdaten zu approximieren sondern ein allgemeines Konzept der Klassifikation beliebiger Daten (Testdaten) zu erlernen
• Stichwort: „
  Occam‘s razor “ (die einfachste Theorie/Hypothese präferieren, die den Sachverhalt,
  in unserem Fall die Daten, repräsentiert)

Question 5

Was bedeutet EFFIZIENTES Attribut?

Answer 5

• Notwendigkeit einer Bewertungsfunktion , die den Informationsgehalt der einzelnen Attribute (z.B. InformationGain ), bewertet, danach das „beste“ Attribut auswählt und so top down den Entscheidungsbaum induziert.
• Baum soll in die Breite statt in die Tiefe wachsen!
  -> Informationstheorie

Informationsgehalt
* I(x)= −log2(px)
* p = Auftrittswahrscheinlichkeit des Ereignisses

Question 6

Alternative
Bewertungsmaße : GainRatio

Answer 6

• der InformationGain = Entropie (Parent) Gewichteter Σ (Entropie Children )) führt meist dazu, dass Attribute mit vielen Wertausprägungen bevorzugt werden
• hat man z.B. ein kategorisches Attribut wie „Tag des Monats“ mit 31 Wertausprägungen, wird dieses voraussichtlich als das „beste“ Attribut zur Erstellung des Baumes verwendet
• hier hilft eine Normierung des InformationGains mit der Entropie der Verteilung der
  Datensätze auf die Verzweigungen (Intrinsic information of a split IntI
  Definition: GainRatio = InformationGain / IntI

Question 7

Alternative
Bewertungsmaße : Gini Index

Answer 7

• populärste Alternative zum InformationGain
• wird in CART ( Classification And Regression Trees, Breiman 84)) verwendet
• Impurity Messure (statt Entropie)
• gewichteter Summe des Gini Index (statt gewichteter Summe Entropie)
• GiniGain wird dann analog zum InformationGain definiert

Question 8

Umgang
mit unbekannten Attributwerten (Heuristiken)

Answer 8

• Datensatz hat fehlenden Attributwert bei Attribut A,
• ersetze den fehlenden Wert durch den Extra Wert „Null“ oder „Feld”
• ersetze den fehlenden Wert durch den häufigsten Wert der anderen Datensätze, bei reellwertigen Attributen durch Mittelwert, Median, …,
• ersetze den fehlenden Wert durch den häufigsten Wert genau der Datensätze, die die gleiche Klassenzugehörigkeit besitzen (nur Trainingsdaten),
• wenn bei einer Klassifikation im Knoten n das Attribut A getestet wird, dann wähle genau den häufigsten Attributwert (Wert, der am häufigsten bei den Datensätzen vorkommt, die auch durch diesen Knoten n getestet werden Trainings und/oder Testmenge kann hier eingesetzt werden!).

Question 9

Entscheidungsbaum
bei reellwertigen Attributen
Bewertung aller möglichen “Cut Points”

Answer 9

• sei A ein Attribut und sei 𝑉1,𝑉2,… 𝑉𝑛eine sortierte Sequenz von n Attributwerten, die in der zu splittenden Datensatz Menge C enthalten sind,
• jedes Paar 𝑉𝑖,𝑉𝑖+1bildet einen potentiellen Cut Point 𝑉𝑖+𝑉𝑖+12, der diese Menge in zwei Teilmengen unterteilt, d.h. 𝑛−1mögliche Splits,
• der InformationGain (oder auch ein anderes Bewertungsmaß) dieser Unterteilung wird dann genauso berechnet, wie im Falle der kategorischen Attribute (Cut-Point sorgt für 2 Kategorien, d.h. kleiner bzw. größer als Cut Point),
• InformationGain für den besten Cut Point ist dann InformationGain für das Attribut,
• hoher Aufwand bei der Berechnung! (Frage: Bei m Attributen, wie hoch maximal?)

Question 10

Entscheidungsbaum
bei reellwertigen Attributen
Multi way Splits ( d.h . mehrere “Cut Points” pro Attribut

Answer 10

• Split anhand eines kategorischen Attributs „nutzt“ die gesamte Information dieses Attributs,
• d.h. auf dem Weg von der Baumwurzel bis zu einem Blatt kommt dieses Attribut nur einmal vor … und muss bei einer Klassifikation nur einmal getestet werden,
• bei Binärsplits eines reellwertigen Attributs ist dies anders; hier kann das Attribut bzgl. unterschiedlicher Werte (binäre Cut Points) mehrfach vorkommen,
• Nachteil: der Baum lässt sich schwieriger interpretieren,
• Auswege:
  -> vorherige Diskretisierung reellwertiger Attribute (CRISP Phase Data Preparation
  -> Multi way Splits anstatt Binärsplits:
  bei der Bewertung eines reellwertigen Attributs
  späteres Zusammenfassen von hintereinander erfolgten
  Binärsplits

Question 11

Überanpassung (Overfitting)

Answer 11

• Basisalgorithmus von ID3 konstruiert einen Baum, der perfekt die Trainingsdaten klassifiziert,
• durch Fehler (engl. Noise) in den Trainingsdaten oder bei einem zu kleinem Trainingsdatensatz führt das meist zu einer Überanpassung (eng. Overfitting ) an die Trainingsdaten
• 2 Methoden, um Overfitting zu vermeiden:
  1. Pre Pruning : Stoppen der Baumentwicklung, bevor alle Trainingsdaten perfekt klassifiziert werden (Problem: Wann genau stoppen?)
  -> Stopp dann, wenn zu wenig Daten im Child Knoten sind (absolut oder relativ im Vergleich zur gesamten Datensatzanzahl)
  -> Stopp dann, wenn die Anzahl der Datensätze einer Klasse im Child Knoten zu gering ist (z.B. absolut weniger als 30)
  -> ist schneller

2. Post Pruning : Vollständige Entwicklung des Baumes und danach ein „Abschneiden“ von Teilbäumen (d.h. Zusammenfassung zu einem Blatt).
   -> erfordert Trainings und Validierungsdaten (z.B. im Verhältnis 2/3 zu 1/3)
   -> Baum wird basierend auf Trainingsdaten vollständig entwickelt
   -> mit Hilfe der Validierungsdaten werden die Teil Bäume von unten nach oben bewertet (z.B. mittels ROC) und ggf. zu einem Blatt zusammengefasst,
   -> ist genauer

Question 12

Scoring

Answer 12

• Basisalgorithmus von ID3 konstruiert einen Baum, der perfekt ( Overfitting) die Trainingsdaten klassifiziert (diskrete Klassifikation)
• durch Pruning verhindert man Overfitting durch vorzeitiges Stoppen der Baum Entwicklung oder durch die Zusammenfassung von Teilbäumen zu Blättern,
• die in den Blättern enthaltene Klassenverteilung der Datensätze kann dann als Score Wert für eine probabilistische Klassifikation der Testmenge verwendet werden,
• z.B. 𝑆𝑐𝑜𝑟𝑒𝐵𝑙𝑎𝑡𝑡=𝐴𝑛𝑧𝑎ℎ𝑙 𝐷𝑎𝑡𝑒𝑛𝑠ä𝑡𝑧𝑒 𝐾𝑙𝑎𝑠𝑠𝑒 𝑋(𝐵𝑙𝑎𝑡𝑡)/𝐴𝑛𝑧𝑎ℎ𝑙 𝑎𝑙𝑙𝑒𝑟 𝐷𝑎𝑡𝑒𝑛𝑠ä𝑡𝑧𝑒(𝐵𝑙𝑎𝑡𝑡)
• für die (diskrete) Klassifikation wird dann genau der Score Wert berechnet, wo die Klassen getrennt werden (via ROC Analyse und Kosten –/Nutzen Rechnung der Klassifikation siehe Vorlesung ROC Chart Analyse).

Question 13

Verschiedene Arten von Entscheidungsbäumen

Answer 13

• Achsenparallele ( univariate ) Bäume
  -> ID3: Quinlan, C4.5: Quinlan
  -> Split jeweils nur an einem einzigen Attribut x i
  -> Numeric x i: Binary split : x i > w m
  -> Discrete x i: n way split for n possible values
• Schiefe (multivariate lineare) Bäume
  -> OC1: Murthy
  -> Split nutzt alle Attribute als Linearkombination (allg. Hyperebene)
• Nichtlineare multivariate Bäume
  -> NDT Non Linear Decision Trees
  -> Split nutzt alle Attribute in Form einer nichtlinearen Hyperfläche