Information Gain Rechner

Dieser Onlinerechner berechnet den Information Gain (auch als Kullback-Leibler Divergenz bekannt), die Änderung von Entropie von einem vorherigen Zustand in einen neuenn Zustand, wo bestimmte Informationen als gegeben angesehen wird.

Der untenstehende Onlinerechner analysiert einen Satz von Übungsbeispielen und berechnet dann den Information Gain für jedes Attribut / Merkmal. Wenn Sie nicht sicher sind, worum es hier geht, oder wenn Sie die Formeln dafür sehen wollen, finden die Erklärung unter dem Rechner.

Bitte beachten: Übungsbeispiele sollten als csv Liste eingebeben werden, mit einem Semikolon als Trennung. Die erste Zeile beinhaltet die Beschreibung, zuerst die Attribute / Merkmale und dann die Klassenbeschreibung. Alle folgenden Zeilen sind die Beispiele. Die Standarddaten in dem Rechner sind von dem berühmten Beispiel des Entscheidungsbaum „Soll man Tennis spielen“.

PLANETCALC, Information Gain Rechner

Information Gain Rechner

Zahlen nach dem Dezimalpunkt: 3
Die Datei ist sehr groß; Beim Laden und Erstellen kann es zu einer Verlangsamung des Browsers kommen.

Information Gain und Entscheidungsbaum

Information Gain ist eine Metrik, die besonders hilfreich ist bei der Erstellung eines Entscheidungsbaums. Ein Entscheidungsbaum ist eine Flowchart-ähnliche Struktur, in dem jeder interner Knoten einen “Test” eines Attributes darstellt (z.B. ob ein Münzwurf Kopf oder Zahl ist). Jeder Zweig stellt ein Ergebnis des Tests dar, und jedes Blatt stellt eine Klassenbeschriftung dar (die Entscheidung nach dem all Attribute berechnet worden sind). Der Weg von Wurzel zum Blatt wird durch die Klassifizierungsregel dargestellt. 1

Schauen wir uns mal die Standarddaten des Rechners an.

Attribute die analysiert werden:

  • Vorschau: Sonnig/Bewölkt/Regen
  • Luftfeuchtigkeit: Hoch/Normal
  • Windig: Wahr/Falsch
  • Temperatur: Heiß/Mild/Kühl

Klassenbeschriftung ist:

  • Spielen: Ja/Nein

Durch das Analysieren jedes Attributs, sollte der Algorithmus die folgende Frage beantworten: „Sollen wir Tennis spielen?“ Um so wenig Schritte wie möglich zu benötigen, sollte man die besten Entscheidungsattribut für jeden Schritt wählen – die uns das Maximum von Information geben kann.

Wie kann man Informationen, die jedes Attribut gibt, messen? Eine Möglichkeit ist die Entropiereduktion, und dies ist genau was die Information Gain Metrik tut. .

Gehen wir wieder zurück zu unserem Beispiel. In dem Übungssatz gibt es fünf Beispiele, die mit „Nein“ beschriftet sind, und 9 Beispiele sind „Ja“. Laut der bekannten Shannon-Entropie Formel, ist die derzeitige Entropie folgendermaßen

H=-\frac{5}{14} \log_2\frac{5}{14} - \frac{9}{14} \log_2\frac{9}{14} = 0.94

Jetzt nehmen wir mal an, dass wir ein Beispiel klassifizieren wollen. Wir testen zuerst das Attribut “Windig”. Technisch gesehen führen wir eine Teilung des Attributs “Windig” aus.

Wenn der Wert vom Attribut „Windig“ ist „Wahr“, dann haben wir noch weitere sechs Beispiele. Drei von denen haben die Spielbeschriftung “Ja”, und drei haben die Beschriftung „Nein“.
Deren Entropie ist

H=-\frac{3}{6} \log_2\frac{3}{6} - \frac{3}{6} \log_2\frac{3}{6} = 1

Das heißt, wenn das Attribut “Windig“ „Wahr“ ist, haben wir nun eine größere Unsicherheit als davor.

Falls das Attribut “Windig” nun aber „Flasch“ sein sollte, haben wir acht Beispiele. Sech davon haben die Spielbeschriftung “Ja”, und zwei haben “Nein“.
Deren Entropie ist

H=-\frac{6}{8} \log_2\frac{6}{8} - \frac{2}{8} \log_2\frac{2}{8} = 0.81
Dies ist natürlich besser, als unseren anfänglichen Bits von 0.94 (wenn wir glücklich genug sind, „Falsch“ in unserem Beispiel zu haben).

Um die Entropie-Reduktion zu schätzen, muss man den Durchschnitt der Wahrscheinlichkeit, um den Attributs-Wert „Wahr“ oder „Falsch“ zu erhalten. Wir haben sechs Beispiele mit dem Wert „Wahr“ für das Attribut „Windig“, und acht Beispiele mit dem Wert „Falsch“ desselben Attributs. Daher wäre die Durchschnitts-Entropie nach der Teilung

H_{Windy}=\frac{6}{14} H_{Windy=True} + \frac{8}{14} H_{Windy=False} = 0.429+0.463=0.892

Unsere Anfangsentropie ist 0.94, und die Durchschnittsentropie nach der Teilung des Attributs „Windig“ ist 0.892. Daher ist die Information Gain einer Entropie-Reduktion

IG=H-H_{Windy}=0.048

Die allgemeine Formel für die Information Gains für das Attribut a ist

IG(T,a)=\mathrm {H} (T)-\mathrm {H} (T|a),

wobei gilt
T - ein Satz von Übungsbeispielen, jedes in der Form (\textbf{x},y) = (x_1, x_2, x_3, ..., x_k, y) wo x_a\in vals(a) ein Wert ist von a^{\text{th}} Attribut oder Merkmal des Beispiels und y ist die dazugehörige Klassenbeschriftung,
\mathrm {H} (T|a) - die Entropie von T bedingt auf a (Conditional entropy)

Die bedingte Entropie-Formel ist

{\displaystyle \mathrm {H} (T|a)=\sum _{v\in vals(a)}{{\frac {|S_{a}{(v)}|}{|T|}}\cdot \mathrm {H} \left(S_{a}{\left(v\right)}\right)}.}

wobei
S_{a}{(v)} - der Satz des Übungsbeispiels von T ist, für welche das Attribute a gleich v ist.
Mit diesem Verfahren kann man die Information Gain für jedes Attribut ermitteln und damit herausfindet, dass der höchste Informationszuwachs des „Vorschau“ Attributs 0,247 Bits ist. Daraus können wir nun schließen, dass die Auswahl des Attributs „Windig“ als erste Teilung eine sehr schlechte Idee war, und das in dem Übungsbeispiel man zuerst „Vorschau“ hätte auswählen sollen.

Sie wundern sich eventuell, warum man einen Entscheidungsbaum benötigt, wenn man selber die Entscheidung für jede Kombination von Attributen treffen kann. Natürlich kann man das, aber selbst in diesem einfachen Beispiel, ist die Anzahl vom Möglichkeiten 3*2*2*3=36. Auf der anderen Seite benötigen wir nur eine kleinere Anzahl von Kombination (14 Beispiele) um den Algorithmus einzustellen (den Entscheidungsbaum zu erstellen), und alles wird automatisch berechnet. Das ist der Vorteil vom maschinellen Lernen.

URL zum Clipboard kopiert
PLANETCALC, Information Gain Rechner

Kommentare