Der Informationsgewinn ist wie die Gini-Unreinheit eine Metrik, die zum Trainieren von Entscheidungsbäumen verwendet wird. Insbesondere messen diese Metriken die Qualität einer Aufteilung. Angenommen, wir haben die folgenden Daten:
Was wäre, wenn wir eine Aufteilung bei x=1,5x = 1,5x=1,5 vornehmen würden?
Diese unvollkommene Aufteilung unterteilt unseren Datensatz in die folgenden Zweige:
- Linker Zweig, mit 4 Blauen.
- Rechter Zweig, mit 1 Blau und 5 Grüns.
Es ist klar, dass diese Aufteilung nicht optimal ist, aber wie gut ist sie? Wie kann man die Qualität einer Aufteilung quantifizieren?
Da kommt der Informationsgewinn ins Spiel.
Verwirrt? Sie wissen nicht, was Entscheidungsbäume sind oder wie sie trainiert werden? Lesen Sie den Anfang meiner Einführung in Random Forests und Entscheidungsbäume.
Informationsentropie
Bevor wir zum Informationsgewinn kommen, müssen wir zuerst über Informationsentropie sprechen. Im Zusammenhang mit dem Training von Entscheidungsbäumen kann man sich die Entropie ungefähr so vorstellen, wie viel Varianz die Daten haben. Ein Beispiel:
- Ein Datensatz, der nur aus Blautönen besteht, hätte eine sehr niedrige Entropie (sogar null).
- Ein Datensatz mit einer Mischung aus Blautönen, Grüntönen und Rottönen hätte eine relativ hohe Entropie.
Wir berechnen die Informationsentropie für einen Datensatz mit CCC-Klassen folgendermaßen:
E=-∑iCpilog2piE = -\sum_i^C p_i \log_2 p_iE=-i∑Cpilog2pi
wobei pip_ipi die Wahrscheinlichkeit der zufälligen Auswahl eines Elements der Klasse iii ist (d. h. der Anteil des Datensatzes an der Gesamtmenge).d. h. der Anteil des Datensatzes, der aus der Klasse iii besteht).
Am einfachsten lässt sich dies anhand eines Beispiels verstehen. Betrachten wir einen Datensatz mit 1 Blau, 2 Grüntönen und 3 Rottönen: . Dann
E=-(pblog2pb+pglog2pg+prlog2pr)E = -(p_b \log_2 p_b + p_g \log_2 p_g + p_r \log_2 p_r)E=-(pblog2pb+pglog2pg+prlog2pr) E=-(16log2(16)+26log2(26)+36log2(36))=1.46\begin{aligned}E &= -(\frac{1}{6} \log_2(\frac{1}{6}) + \frac{2}{6} \log_2(\frac{2}{6}) + \frac{3}{6} \log_2(\frac{3}{6})) \\&= \boxed{1.46} \\\\end{aligned}E=-(61log2(61)+62log2(62)+63log2(63))=1.46
Was ist mit einem Datensatz mit nur einer Farbe? Nehmen wir als Beispiel 3 Blautöne: . Die Entropie wäre
E=-(1log21)=0E = -(1 \log_2 1) = \boxed{0}E=-(1log21)=0
Informationsgewinn
Endlich ist es an der Zeit, die Frage zu beantworten, die wir vorhin gestellt haben: wie können wir die Qualität einer Aufteilung quantifizieren?
Betrachten wir noch einmal diesen Split:
Vor dem Split hatten wir 5 Blaue und 5 Grüne, also war die Entropie
Ebefore=-(0.5log20.5+0.5log20.5)=1\begin{aligned}E_{before} &= -(0,5 \log_2 0,5 + 0,5 \log_2 0,5) \\\&= \boxed{1} \\\\end{aligned}Ebefore=-(0.5log20.5+0.5log20.5)=1
Nach dem Split haben wir zwei Zweige.
Der linke Zweig hat 4 Blautöne, also Eleft=0E_{left} = \boxed{0}Eleft=0, weil es ein Datensatz mit nur einer Farbe ist.
Der rechte Zweig hat 1 Blau und 5 Grüntöne, also
Eright=-(16log2(16)+56log2(56))=0.65\begin{aligned}E_{right} &= -(\frac{1}{6} \log_2 (\frac{1}{6}) + \frac{5}{6} \log_2 (\frac{5}{6})) \\&= \boxed{0.65} \\\end{aligned}Eright=-(61log2(61)+65log2(65))=0.65
Nun, da wir die Entropien für beide Zweige haben, können wir die Qualität der Aufspaltung bestimmen, indem wir die Entropie jedes Zweiges danach gewichten, wie viele Elemente er hat. Da der linke Zweig 4 Elemente hat und der rechte Zweig 6, gewichten wir sie mit 0,40.40.4 bzw. 0,60.60.6:
Esplit=0,4∗0+0,6∗0,65=0,39\begin{aligned}E_{split} &= 0,4 * 0 + 0,6 * 0,65 \\&= \boxed{0.39} \\\end{aligned}Esplit=0.4∗0+0.6∗0.65=0.39
Wir begannen mit Ebefore=1E_{before} = 1Ebefore=1 Entropie vor der Aufspaltung und sind jetzt bei 0.390.390.39! Informationsgewinn = wie viel Entropie wir entfernt haben, also
Gewinn=1-0.39=0.61\text{Gewinn} = 1 – 0.39 = \boxed{0.61}Gewinn=1-0.39=0.61
Das macht Sinn: höherer Informationsgewinn = mehr entfernte Entropie, was wir ja wollen. Im Idealfall würde jeder Zweig nach der Aufteilung nur eine Farbe enthalten, was einer Entropie von Null entspräche!
Zusammenfassung
Die Informationsentropie kann als Maß für die Unvorhersehbarkeit eines Datensatzes angesehen werden.
- Ein Satz mit nur einer Klasse (z. B. blau) ist extrem vorhersehbar: Alles darin ist blau. Dies hätte eine niedrige Entropie.
- Eine Menge mit vielen gemischten Klassen ist unvorhersehbar: ein bestimmtes Element könnte jede Farbe haben! Dies hätte eine hohe Entropie.
Die eigentliche Formel zur Berechnung der Informationsentropie lautet:
E=-∑iCpilog2piE = -\sum_i^C p_i \log_2 p_iE=-i∑Cpilog2pi
Der Informationsgewinn wird für eine Aufteilung berechnet, indem die gewichteten Entropien der einzelnen Zweige von der ursprünglichen Entropie abgezogen werden. Beim Training eines Entscheidungsbaums mit diesen Metriken wird die beste Aufteilung durch Maximierung des Informationsgewinns ausgewählt.
Wollen Sie mehr erfahren? Schauen Sie sich meine Erklärung der Gini-Unreinheit, einer ähnlichen Metrik, oder meinen ausführlichen Leitfaden Random Forests for Complete Beginners an.