ID3 und C4.5

Wie Attribute wählen?

Erinnerung: CAL2/CAL3

• Zyklische Iteration durch die Trainingsmenge
• Ausschließlich aktuelles Objekt betrachtet
• Reihenfolge der "richtigen" Attributwahl bei Verzweigung unklar

=> Betrachte stattdessen die komplette Trainingsmenge!

Erinnerung Entropie: Maß für die Unsicherheit

• Entropie $H(S)$ der Trainingsmenge $S$: relative Häufigkeit der Klassen zählen

• Mittlere Entropie nach Betrachtung von Attribut $A$

  $$ R(S, A) = \sum_{v \in \operatorname{Values}(A)} \frac{|S_v|}{|S|} H(S_v) $$

• Informationsgewinn durch Betrachtung von Attribut $A$

  $$ \begin{array}{rcl} \operatorname{Gain}(S, A) &=& H(S) - R(S, A)\\[5pt] &=& H(S) - \sum_{v \in \operatorname{Values}(A)} \frac{|S_v|}{|S|} H(S_v) \end{array} $$

$R(S,A)$ ist die Unsicherheit/nötige Bits nach Auswahl von Attribut A. Je kleiner $R(S,A)$, um so kleiner die verbleibende Unsicherheit bzw. um so kleiner die Anzahl der nötigen Bits zur Darstellung der partitionierten Trainingsmenge nach Betrachtung von Attribut $A$ ...

=> Je kleiner $R(S,A)$, um so größer der Informationsgewinn

Informationsgewinn: Kriterium zur Auswahl von Attributen

1. Informationsgewinn für alle Attribute berechnen
2. Nehme Attribut mit größtem Informationsgewinn als nächsten Test

Informationsgewinn für $x_2$ am höchsten => wähle $x_2$ als nächsten Test

Entscheidungsbaumlerner ID3 (Quinlan, 1986)

def ID3(examples, attr, default):
    # Abbruchbedingungen
    if examples.isEmpty():  return default
    if examples.each(class == A):  return A  # all examples have same class
    if attr.isEmpty():  return examples.MajorityValue()

    # Baum mit neuem Test erweitern
    test = MaxInformationGain(examples, attr)
    tree = new DecisionTree(test)
    m = examples.MajorityValue()
    for v_i in test:
        ex_i = examples.select(test == v_i)
        st = ID3(ex_i, attr - test, m)
        tree.addBranch(label=v_i, subtree=st)
    return tree

[Russell2020]: Man erhält aus dem "Learn-Decision-Tree"-Algorithmus [Russell2020, S. 678, Fig. 19.5] den hier vorgestellten ID3-Algorithmus, wenn man die Funktion $\operatorname{Importance}(a, examples)$ als $\operatorname{InformationGain}(examples, attr)$ implementiert/nutzt.

Hinweis: Mit der Zeile if examples.each(class == A): return A soll ausgedrückt werden, dass alle ankommenden Trainingsbeispiele die selbe Klasse haben und dass diese dann als Ergebnis zurückgeliefert wird. Das "A" steht im obigen Algorithmus nur symbolisch für die selbe Klasse! Es kann also auch ein anderes Klassensymbol als "A" sein ...

Beispiel ID3

• $x2$ höchsten Information Gain
• $x2=0$ => Beispiele 1,2 => A
• $x2=1$ => Beispiele 3,4,5,6 => Information Gain berechnen, weiter teilen und verzweigen

Beobachtung: $\operatorname{Gain}$ ist bei mehrwertigen Attributen höher

• Faire Münze:

  • Entropie = $H(\operatorname{Fair}) = -(0.5 \log_2 0.5 + 0.5 \log_2 0.5) = 1 \operatorname{Bit}$

• 4-seitiger Würfel:

  • Entropie = $H(\operatorname{Dice}) = -4\cdot(0.25 \log_2 0.25) = 2 \operatorname{Bit}$

=> $\operatorname{Gain}$ ist bei mehrwertigen Attributen höher

Damit würden Attribute bei der Wahl bevorzugt, nur weil sie mehr Ausprägungen haben als andere.

Anmerkung: Im obigen Beispiel wurde einfach die Entropie für zwei "Attribute" mit unterschiedlich vielen Ausprägungen betrachtet, das ist natürlich kein $\operatorname{Gain}(S, A)$. Aber es sollte deutlich machen, dass Merkmale mit mehr Ausprägungen bei der Berechnung des Gain für eine Trainingsmenge einfach wegen der größeren Anzahl an Ausprägungen rechnerisch bevorzugt würden.

C4.5 als Verbesserung zu ID3

Normierter Informationsgewinn: $\operatorname{Gain}(S, A) \cdot \operatorname{Normalisation}(A)$

C4.5 kann zusätzlich u.a. auch noch mit kontinuierlichen Attributen umgehen, vgl. en.wikipedia.org/wiki/C4.5_algorithm.

In einem Paper (DOI 10.1007/s10115-007-0114-2) wurde der Algorithmus zu den "Top 10 algorithms in data mining" ausgewählt.

Im Wikipedia-Artikel Information Gain finden Sie weitere Informationen zum "Informationsgewinn" (Information Gain).

Ein anderer, relativ ähnlich arbeitender Entscheidungsbaumlerner ist der CART (Classification And Regression Tree)-Algorithmus, wobei der Begriff "CART" allerdings oft auch einfach allgemein für "Entscheidungsbaumlerner" genutzt wird.

Hierzu drei lesenswerte Blog-Einträge:

• Deep dive into the basics of Gini Impurity in Decision Trees with math Intuition
• Decision Trees, Explained
• Decision Tree Algorithm With Hands-On Example

Beispiele zur Normierung bei C4.5

• Faire Münze:

  • Entropie = $H(\operatorname{Fair}) = -(0.5 \log_2 0.5 + 0.5 \log_2 0.5) = 1 \operatorname{Bit}$
  • Normierung: $1/(0.5 \log_2 (1/0.5) + 0.5 \log_2 (1/0.5)) = 1/(0.5 \cdot 1 + 0.5 \cdot 1) = 1$
  • Normierter Informationsgewinn: $\operatorname{Gain}(S, A) \cdot \operatorname{Normalisation}(A) = 1 \operatorname{Bit} \cdot 1 = 1 \operatorname{Bit}$

• 4-seitiger Würfel:

  • Entropie = $H(\operatorname{Dice}) = -4\cdot(0.25 \log_2 0.25) = 2 \operatorname{Bit}$
  • Normierung: $1/(4\cdot 0.25 \log_2 (1/0.25)) = 1/(4\cdot 0.25 \cdot 2) = 0.5$
  • Normierter Informationsgewinn: $\operatorname{Gain}(S, A) \cdot \operatorname{Normalisation}(A) = 2 \operatorname{Bit} \cdot 0.5 = 1 \operatorname{Bit}$

=> Normierung sorgt für fairen Vergleich der Attribute

Anmerkung: Auch hier ist die Entropie natürlich kein $\operatorname{Gain}(S, A)$. Das Beispiel soll nur übersichtlich deutlich machen, dass der "Vorteil" von Attributen mit mehr Ausprägungen durch die Normierung in C4.5 aufgehoben wird.

Wrap-Up

• Entscheidungsbaumlerner ID3
  • Nutze Information Gain zur Auswahl des nächsten Attributs
  • Teile die Trainingsmenge entsprechend auf ("nach unten hin")
• Verbesserung durch Normierung des Information Gain: C4.5