Ein einfacher Blick auf einige wichtige informationstheoretische Konzepte und deren Verwendung beim Erstellen eines Entscheidungsbaumalgorithmus.
Nach welchen Kriterien sollte ein Entscheidungsbaumalgorithmus Variablen /Spalten aufteilen?
Bevor Sie einen Entscheidungsbaumalgorithmus erstellen, müssen Sie zunächst diese Frage beantworten. Schauen wir uns eine der Möglichkeiten an, diese Frage zu beantworten. Dazu müssen wir einige Schlüsselkonzepte aus der Informationstheorie verstehen und anwenden.
Lassen Sie uns diese Methode untersuchen, indem Sie die folgenden Schritte ausführen:
- Werfen Sie einen sehr kurzen Blick darauf, was ein Entscheidungsbaum ist.
- Definieren und untersuchen Sie die Formel für die Entropie.
- Diskutieren Sie, was ein Bit in der Informationstheorie ist.
- Definieren Sie den Informationsgewinn und verwenden Sie die Entropie, um ihn zu berechnen.
- Schreiben Sie einige grundlegende Python-Funktionen mit den obigen Konzepten.
In der Datenwissenschaft ist der Entscheidungsbaumalgorithmus ein überwachter Lernalgorithmus für Klassifikations- oder Regressionsprobleme. Unser Endziel ist es, historische Daten zu verwenden, um ein Ergebnis vorherzusagen. Im Gegensatz zur linearen Regression können Entscheidungsbäume nichtlineare Wechselwirkungen zwischen Variablen in den Daten erfassen.
Schauen wir uns einen sehr einfachen Entscheidungsbaum an. Nachfolgend finden Sie einen Workflow, mit dem Sie entscheiden können, ob Sie einen Erdnussbutter-Keks essen möchten oder nicht.
In diesem Beispiel kann ein Entscheidungsbaum die Tatsache aufgreifen, dass Sie den Cookie nur essen sollten, wenn bestimmte Kriterien erfüllt sind. Dies ist das ultimative Ziel eines Entscheidungsbaums. Wir wollen weiterhin Entscheidungen treffen(Splits), bis bestimmte Kriterien erfüllt sind. Einmal getroffen, können wir es verwenden, um eine Vorhersage zu klassifizieren oder zu machen. Dieses Beispiel ist sehr einfach mit nur zwei Variablen (Allergie, ruinieren Abendessen). Wenn Sie jedoch einen Datensatz mit Tausenden von Variablen / Spalten haben, wie entscheiden Sie, auf welche Variablen / Spalten am effizientesten aufgeteilt werden soll? Eine beliebte Methode zur Lösung dieses Problems, insbesondere bei Verwendung eines ID3-Algorithmus, besteht darin, Entropie und Informationsgewinn zu verwenden.
Die Aufgabe
Angenommen, wir haben einige Daten und möchten daraus ein Online-Quiz erstellen, das etwas über den Quizteilnehmer vorhersagt. Nachdem wir uns die Beziehungen in den Daten angesehen haben, haben wir uns entschieden, einen Entscheidungsbaumalgorithmus zu verwenden. Wenn Sie noch nie in ein Online-Quiz hineingezogen wurden, können Sie hier Hunderte von Beispielen sehen. Das Ziel des Quiz ist es zu erraten, ob der Quizteilnehmer aus einem der Bundesstaaten des Mittleren Westens Amerikas stammt. Die Fragen im Quiz drehen sich darum, ob sie eine bestimmte Art von Essen mögen oder nicht. Unten finden Sie einen kleinen fiktiven Datensatz mit fünfzehn Einträgen. Jeder Eintrag enthält Antworten auf eine Reihe von Fragen. Die meisten Fragen beziehen sich darauf, ob sie eine bestimmte Art von Essen mochten, in der der Teilnehmer (1) für ja oder (0) für jetzt antwortete. Die letzte Kolumne(„Midwest?“) ist unsere Zielspalte, was bedeutet, dass dies nach dem Erstellen des Entscheidungsbaums die Klassifizierung ist, die wir zu erraten versuchen.
Entropie
Zu get us started wir werden eine Informationstheorie Metrik namens Entropie verwenden. In der Datenwissenschaft wird die Entropie verwendet, um zu messen, wie „gemischt“ eine Spalte ist. Insbesondere wird die Entropie verwendet, um Störungen zu messen. Beginnen wir damit, die Entropie unserer Zielspalte zu finden: „Mittlerer Westen?”.
Es gibt zehn Leute, die im Mittleren Westen leben und fünf Leute, die das nicht tun. Wenn dich jemand fragen würde, wie gemischt die Kolumne ist, könnte man sagen, dass sie irgendwie gemischt war, mit einer Mehrheit (2/3) der Leute aus dem Mittleren Westen. Entropie gibt uns eine Möglichkeit, die Antwort“ irgendwie gemischt“ zu quantifizieren. Je gemischter die (1) s und (0) s in der Spalte sind, desto höher ist die Entropie. Wenn „mittlerer Westen?“ bei gleichen Mengen von (1) s und (0) s wäre unsere Entropie 1. Wenn „mittlerer Westen?“ bestand nur aus (1) s wäre die Entropie 0.
Wir können die folgende Formel verwenden, um die Entropie zu berechnen:
Gehen wir jeden Schritt der Formel durch und berechnen die Entropie für den „Mittleren Westen?” Spalte.
- Wir müssen jeden eindeutigen Wert in einer einzelnen Spalte durchlaufen und i zuweisen. Für dieses Beispiel haben wir 2 Fälle (c) im „Mittleren Westen?“ Spalte, entweder (0) oder (1).
- Wir berechnen dann die Wahrscheinlichkeit, dass dieser Wert in den Daten auftritt. Für den Fall von (1) beträgt die Wahrscheinlichkeit 10/15. Für den Fall von (0) beträgt die Wahrscheinlichkeit 5/15.
- Wir nehmen die Wahrscheinlichkeit jedes Falles und multiplizieren sie mit dem Logarithmus zur Basis 2 der Wahrscheinlichkeit. 2 ist die häufigste Basis, da die Entropie in Bits gemessen wird (dazu später mehr). Die vollständige Erklärung, warum 2 verwendet wird, liegt außerhalb des Umfangs dieses Beitrags, aber ein Benutzer von Stack Exchange bietet eine gute Erklärung. Für den Fall von (1) erhalten wir 10/15*log2(10/15). Für den Fall von (0) erhalten wir 5/15 * log2(5/15).
- Als nächstes nehmen wir unser Produkt aus jedem Fall oben und summieren es zusammen. In diesem Beispiel 10/15*log2(10/15) + 5/15*log2(5/15).
- Schließlich negieren wir die Gesamtsumme von oben, — (10/15*log2(10/15) + 5/15*log2(5/15)).
Sobald wir alle Schritte zusammengefügt haben, erhalten wir Folgendes:
Unsere endgültige Entropie ist .918278. Also, was bedeutet das wirklich?
Informationstheorie und ein bisschen Information
In Zukunft wird es wichtig sein, das Konzept von Bit zu verstehen. In der Informationstheorie wird ein Bit als eine Binärzahl betrachtet, die 0 für keine Information und 1 für ein vollständiges Informationsbit darstellt. Wir können ein bisschen Information als Binärzahl darstellen, weil sie entweder den Wert (1) oder (0) hat. Angenommen, es gibt eine gleiche Wahrscheinlichkeit, dass es morgen regnet (1) oder nicht regnet (0). Wenn ich dir sage, dass es morgen regnen wird, habe ich dir eine Information gegeben.
Wir können uns Entropie auch als Information vorstellen. Angenommen, wir haben einen geladenen sechsseitigen Würfel, der immer auf (3) landet. Jedes Mal, wenn wir den Würfel würfeln, wissen wir im Voraus, dass das Ergebnis (3) sein wird. Wir erhalten keine neuen Informationen, indem wir den Würfel rollen, also ist die Entropie 0. Auf der anderen Seite, wenn der Würfel weit ist und wir eine (3) rollen, gab es eine 1/6 Chance, die (3) zu rollen. Jetzt haben wir Informationen gewonnen. Das Würfeln des Würfels gibt uns also eine Information — auf welcher Seite die Zahl gelandet ist.
Für einen tieferen Einblick in das Konzept von ein paar Informationen können Sie hier mehr lesen.
Wir erhalten weniger als ein „Bit“ an Informationen — nur .918278 – weil es im „Mittleren Westen“ mehr (1) gibt?“ spalte als (0)s. Dies bedeutet, dass wir, wenn wir einen neuen Wert vorhersagen würden, erraten könnten, dass die Antwort (1) ist und häufiger richtig als falsch ist (weil es eine 2/3 Wahrscheinlichkeit gibt, dass die Antwort 1 ist). Aufgrund dieses Vorwissens gewinnen wir weniger als ein volles „Bit“ an Informationen, wenn wir einen neuen Wert beobachten.
Mit Entropie Entscheidungen treffen
Unser Ziel ist es, die beste(n) Variable(n)/Spalte(n) zu finden, auf die man sich beim Erstellen eines Entscheidungsbaums aufteilen kann. Schließlich möchten wir die Variablen / Spalten so lange aufteilen, bis unsere gemischte Zielspalte nicht mehr gemischt ist.
Schauen wir uns zum Beispiel die Entropie des „Mittleren Westens?“ Spalte, nachdem wir unseren Datensatz auf den „potato_salad?” Spalte.
Oben ist unser Datensatz in zwei Abschnitte unterteilt. Auf der linken Seite jeder, der Kartoffelsalat mag. Auf der rechten Seite jeder, der nicht. Wir füllen Fokus auf der linken Seite, die jetzt sieben Menschen aus dem Mittleren Westen und zwei Menschen, die nicht. Durch die Verwendung der Formel für die Entropie auf der linken Spalte Split mittleren Westen ist die neue Entropie .764204. Das ist toll! Unser Ziel ist es, die Entropie zu senken und wir gingen von .918278 zu .764204. Aber wir können hier nicht aufhören, wenn wir uns die rechte Spalte ansehen, ist unsere Entropie gestiegen, da es eine gleiche Menge an (1) s und (0) s gibt. Die Formel für den Informationsgewinn wird das tun. Es gibt uns eine Zahl, um zu quantifizieren, wie viele Informationsbits wir jedes Mal gewonnen haben, wenn wir unsere Daten teilen.
Informationsgewinn
Früher haben wir festgestellt, dass wir Splits wollen, die die Entropie unserer Zielspalte senken. Wenn wir uns auf „potato_salad?“ wir haben diese Entropie im Mittleren Westen gesehen?“ ging auf die linke Seite. Jetzt müssen wir die Gesamtentropie verstehen, wenn wir beide Seiten der Spaltung betrachten. Werfen wir einen Blick auf den Informationsgewinn.
Informationsgewinn wird die folgende Formel verwenden:
Lassen Sie uns aufschlüsseln, was hier vor sich geht.
Wir kehren zu unserem „potato_salad?” Beispiel. Die Variablen in der obigen Formel stellen Folgendes dar:
- T = Ziel, unser „mittlerer Westen?“ column
- A = die Variable(Spalte), die wir testen, „potato_salad?“
- v = jeder Wert in A, jeder Wert in der „potato_salad?“ spalte
- Zuerst berechnen wir die ursprüngliche Entropie für (T) vor dem Split , .918278
- Dann berechnen wir für jeden eindeutigen Wert (v) in der Variablen (A) die Anzahl der Zeilen, in denen (A) den Wert (v) annimmt, und dividieren ihn durch die Gesamtzahl der Zeilen. Für den „potato_salad?“ spalte wir erhalten 9/15 für den eindeutigen Wert von (1) und 6/15 für den eindeutigen Wert von (0).Als nächstes multiplizieren wir die Ergebnisse mit der Entropie der Zeilen, in denen (A) (v) ist. Für den linken Split( Split auf 1 für „potato_salad?“) wir bekommen 9/15 * .764204. Für die rechte Seite des Split ( Split auf 0 für „potato_salad?“) wir bekommen 6/15 * 1.
- Wir addieren alle diese Teilmenge Produkte zusammen, 9/14*.764204 + 6/15 = .8585224.
5. Wir subtrahieren dann von der Gesamtentropie Informationsgewinn zu erhalten, .918278 -.8585224 = .059754
Unser Informationsgewinn ist .059754. Was sagt uns das?
Hier ist eine alternative Erklärung. Wir finden die Entropie jedes Satzes nach dem Split, gewichten sie mit der Anzahl der Elemente in jedem Split und subtrahieren sie dann von der aktuellen Entropie. Wenn das Ergebnis positiv ist, haben wir die Entropie mit unserem Split gesenkt. Je höher das Ergebnis ist, desto mehr haben wir die Entropie gesenkt.
Wir enden mit .059754, was bedeutet, dass wir gewinnen .059754 bits von Informationen durch die Aufteilung unserer Datensatz auf der „potato_salad?“ variable/Spalte. Unser Informationsgewinn ist gering, aber es ist immer noch positiv, weil wir die Entropie auf der linken Seite der Spaltung gesenkt haben.
Jetzt müssen wir diesen Vorgang für jede Spalte wiederholen, die wir verwenden. Anstatt dies von Hand zu tun, schreiben wir etwas Python-Code.
Alles mit Python einwickeln
Nachdem wir den Informationsgewinn verstanden haben, müssen wir diesen Vorgang wiederholen, um die Variable / Spalte mit dem größten Informationsgewinn zu finden. Um dies zu tun, können wir ein paar einfache Funktionen in Python erstellen.
Importieren der Daten
Verwandeln wir unsere obige Tabelle mithilfe der Python Pandas-Bibliothek in einen Datenrahmen. Wir werden Pandas importieren und die Funktion read_csv () verwenden, um einen Datenrahmen mit dem Namen „midwest“ zu erstellen.
import pandas as pd
midwest = pd.read_csv('midwes.csv')
Eine Python-Funktion für die Entropie
Für diese Funktion benötigen wir die NumPy-Bibliothek, um die Funktion bincount() zu verwenden, und das math-Modul, um die Funktion log() zu verwenden.
import numpy
import math
Als nächstes definieren wir unsere Funktion mit einem Parameter. Das angegebene Argument ist die Reihe, Liste oder das NumPy-Array, in dem wir versuchen, die Entropie zu berechnen.
def calc_entropy(column):
Wir müssen den Prozentsatz jedes Falles in der Spalte finden. Wir können die numpy verwenden.bincount() Funktion für diese. Der Rückgabewert ist ein NumPy-Array, in dem die Anzahl der eindeutigen Werte aus der Spalte gespeichert wird, die als Argument übergeben wurde.
counts = numpy.bincount(column)
Wir speichern die Wahrscheinlichkeiten jedes eindeutigen Werts, indem wir das Array „counts“ durch die Länge der Spalte dividieren.
probabilities = counts / len(column)
Wir können dann eine Variable namens „entropy“ initialisieren und auf 0 setzen.
entropy = 0
Als nächstes können wir eine „for-Schleife“ verwenden, um jede Wahrscheinlichkeit in unserem Wahrscheinlichkeitsarray zu durchlaufen und sie mit dem Logarithmus zur Basis 2 der Wahrscheinlichkeit zu multiplizieren.log() -Funktion. Fügen Sie dann jeden Fall zu unserer gespeicherten Entropievariablen hinzu. *stellen Sie sicher, dass Ihre Wahrscheinlichkeit größer als 0 ist, andernfalls gibt log(0) undefined
for prob in probabilities:
if prob > 0:
endtropy += prob * math.log(prob,2)
Schließlich geben wir unsere negierte Entropievariable zurück.
return -entropy
Jetzt alle zusammen:
Großartig! Jetzt können wir eine Funktion zur Berechnung des Informationsgewinns erstellen.
Eine Python-Funktion zur Informationsgewinnung
Wir müssen eine Funktion definieren, die drei Parameter hat, einen für den gesamten Datensatz, einen für den Namen der Spalte, in die wir aufteilen möchten, und einen für den Namen unserer Zielspalte.
def calc_information_gain(data, split_name, target_name):
Als nächstes können wir die Entropiefunktion von früher verwenden, um die ursprüngliche Entropie unserer Zielspalte zu berechnen.
orginal_entropy = calc_entropy(data)
Jetzt müssen wir unsere Spalte aufteilen.
*In diesem Beispiel verwenden wir nur die Variablen/Spalten mit zwei eindeutigen. Wenn Sie eine Variable / Spalte wie „Alter“ aufteilen möchten, gibt es mehrere Möglichkeiten, dies zu tun. Eine Möglichkeit besteht darin, jeden eindeutigen Wert aufzuteilen. Eine andere Möglichkeit besteht darin, die Berechnung des Informationsgewinns zu vereinfachen und die Aufteilung zu vereinfachen, indem nicht für jeden eindeutigen Wert aufgeteilt wird. Stattdessen wird der Median für die Variable / coumn gefunden, auf die aufgeteilt wird. Alle Zeilen, in denen der Wert der Variablen unter dem Median liegt, werden in den linken Zweig und die restlichen Zeilen in den rechten Zweig verschoben. Um den Informationsgewinn zu berechnen, müssen wir nur Entropien für zwei Teilmengen berechnen. Wir werden diese Methode nicht durchgehen, aber sobald die Aufteilung des Medians durchgeführt ist, sind die restlichen Schritte dieselben wie unten beschrieben.
Da die Spalten, mit denen wir arbeiten, nur zwei eindeutige Werte haben, werden wir eine linke und eine rechte Aufteilung vornehmen.
Wir beginnen mit den Pandas.Serie.unique(), um uns ein Array der eindeutigen Werte in der Spalte
values = data.unique()
Als nächstes erstellen wir eine linke und rechte Aufteilung mit „values“.
left_split = data == values]
right_split = data == values]
Jetzt können wir eine Variable initiieren, um von unserer ursprünglichen Entropie zu subtrahieren.
to_subtract = 0
Dann durchlaufen wir jede von unserem Split erstellte Teilmenge, berechnen die Wahrscheinlichkeit der Teilmenge und addieren dann das Produkt aus der Wahrscheinlichkeit und der Entropie der Zielspalte der Teilmenge.
for subset in :
prob = (subset.shape / data.shape)
to_subtract += prob * calc_entropy(subset)
Schließlich können wir die Differenz von to_subract zurückgeben, die von der ursprünglichen Entropie subtrahiert wird.
return original_entropy - to_subtract
Die gesamte Funktion ist unten.
Eine Python-Funktion für den höchsten Informationsgewinn
Unsere letzte Funktion wird eine sein, die den Variablen- / Spaltennamen mit dem höchsten Informationsgewinn zurückgibt.
Wie bereits erwähnt, verwenden wir für dieses Beispiel nur die Spalten mit zwei eindeutigen Werten. Wir speichern diese Spaltennamen in einer Liste, um sie in der Funktion zu verwenden. Um zu dem Punkt zu gelangen, werden wir dies für dieses Beispiel hart codieren, aber in einem großen Datensatz ist es am besten, Code zu schreiben, um diese Liste dynamisch basierend auf den Kriterien zu erstellen, die wir zur Auswahl der Spalten verwenden.
columns =
Lassen Sie uns den letzten Schritt in eine Funktion einschließen, damit wir ihn nach Bedarf wiederverwenden können. Es wird einen Parameter haben, die Liste der Spalten, für die wir den höchsten Informationsgewinn finden möchten.
def highest_info_gain(columns):
Wir initialisieren ein leeres Wörterbuch, um unsere Informationsgewinne zu speichern.
information_gains = {}
Und dann können wir die Liste der Spalten durchlaufen und das Ergebnis in unserem information_gains-Wörterbuch speichern.
for col in columns:
information_gain = calc_information_gain(midwest, col, 'midwest?)
information_gains = information_gain
Schließlich können wir den Schlüssel mit dem höchsten Wert in unserem Wörterbuch zurückgeben.
return max(information_gains, key=information_gains.get)
Jetzt alle zusammen:
Sobald wir unsere letzte Funktion ausführen
print(highest_info_gain(midwest, columns, 'midwest?'))
//sushi
Wir sehen die Variable / Spalte mit dem höchsten Informationsgewinn ist ‘sushi‘?’.
Wir können unten eine Aufteilung auf Sushi visualisieren:
Unsere linke Spalte hat zwei von sechs Personen aus dem Mittleren Westen. Die rechte Spaltung hat acht von neun Menschen aus dem Mittleren Westen. Dies war eine effiziente Aufteilung und senkte unsere Entropie auf beiden Seiten. Wenn wir fortfahren würden, würden wir die Rekursion verwenden, um jeden Split mit dem Ziel zu teilen, jeden Zweig mit einer Entropie von Null zu beenden.
Fazit
Entscheidungsbäume können ein nützlicher Algorithmus für maschinelles Lernen sein, um nichtlineare Wechselwirkungen zwischen Variablen in den Daten zu erfassen. In diesem Beispiel haben wir uns die Anfangsphasen eines Entscheidungsbaum-Klassifizierungsalgorithmus angesehen. Wir haben uns dann drei Konzepte der Informationstheorie angesehen, Entropie, Bit und Informationsgewinn. Durch die Verwendung dieser Konzepte konnten wir einige Funktionen in Python erstellen, um zu entscheiden, welche Variablen / Spalten am effizientesten aufgeteilt werden sollten. Mit einem festen Verständnis dieser Konzepte können wir einen Entscheidungsbaum erstellen.