Get best of the week

Entropie: Wie Entscheidungsbäume Entscheidungen treffen

Eine Übersetzung des Artikels wurde vor Beginn des Kurses für maschinelles Lernen vorbereitet .



Sie sind ein Data Science-Spezialist, der derzeit einen Lernpfad verfolgt. Und Sie haben einen langen Weg zurückgelegt, seit Sie Ihre erste Codezeile in Python oder R geschrieben haben. Sie kennen Scikit-Learn wie Ihre Westentasche. Jetzt sitzt du mehr auf Kaggle als auf Facebook. Sie sind nicht neu darin, atemberaubende zufällige Wälder und andere Ensemblemodelle von Entscheidungsbäumen zu erstellen, die hervorragende Arbeit leisten. Trotzdem wissen Sie, dass Sie nichts erreichen werden, wenn Sie sich nicht umfassend entwickeln. Sie möchten tiefer gehen und die Feinheiten und Konzepte verstehen, die den beliebten Modellen des maschinellen Lernens zugrunde liegen. Nun, ich auch.

Heute werde ich über das Konzept der Entropie sprechen - eines der wichtigsten Themen in der Statistik. Später werden wir über das Konzept des Informationsgewinns (Informationsgewinn) sprechen und herausfinden, warum diese grundlegenden Konzepte die Grundlage dafür bilden, wie Entscheidungsbäume aus den erhaltenen Daten erstellt werden.

Gut. Lassen Sie uns jetzt übertreten.

Was ist Entropie? In einfachen Worten ist Entropie nichts anderes als ein Maß für Unordnung. (Es kann auch als Maß für die Reinheit angesehen werden, und bald werden Sie sehen, warum. Aber ich mag das Durcheinander mehr, weil es cooler klingt.) Die

mathematische Formel der Entropie lautet wie folgt:


Entropie. Es wird manchmal als H geschrieben.

Hier ist p i die Frequenzwahrscheinlichkeit eines Elements / einer Klasse i unserer Daten. Nehmen wir zur Vereinfachung an, wir haben nur zwei Klassen: positiv und negativ. Dann nehme ich entweder den Wert "+" oder "-". Wenn wir insgesamt 100 Punkte in unserem Datensatz hätten, von denen 30 zur positiven Klasse und 70 zur negativen Klasse gehörten, wäre p + 3/10 und p- wird 7/10 sein. Hier ist alles einfach.

Wenn ich die Entropie der Klassen aus diesem Beispiel berechne, erhalte ich dies mit der obigen Formel: Die



Entropie beträgt ungefähr 0,88. Dieser Wert wird als ziemlich hoch angesehen, dh wir haben ein hohes Maß an Entropie oder Störung (dh einen niedrigen Reinheitsgrad). Die Entropie wird im Bereich von 0 bis 1 gemessen. Abhängig von der Anzahl der Klassen in Ihrem Datensatz kann der Wert der Entropie mehr als 1 betragen, dies bedeutet jedoch, dass der Grad der Störung extrem hoch ist. Der Einfachheit halber haben wir im heutigen Artikel eine Entropie im Bereich von 0 bis 1.

Schauen Sie sich die folgende Tabelle an.



Auf der X-Achse wird die Anzahl der Punkte aus der positiven Klasse in jedem Kreis und auf der Y-Achse die entsprechenden Entropien reflektiert. Sie können sofort die umgekehrte U-Form des Diagramms bemerken. Die Entropie ist im Extremfall am kleinsten, wenn der Kreis im Prinzip keine positiven Elemente enthält oder wenn nur positive Elemente darin sind. Das heißt, wenn die Elemente in einem Kreis identisch sind, ist die Störung 0. Die Entropie ist in der Mitte des Diagramms am höchsten, wobei positive und negative Elemente innerhalb des Kreises gleichmäßig verteilt sind. Hier wird die größte Entropie oder Störung erreicht, da es keine vorherrschenden Elemente gibt.

Gibt es einen Grund, warum die Entropie unter Verwendung des Logarithmus zur Basis 2 gemessen wird, oder warum wird die Entropie zwischen 0 und 1 gemessen und nicht in einem anderen Bereich? Nein, es gibt keinen Grund. Dies ist nur eine Metrik. Es ist nicht so wichtig zu verstehen, warum dies geschieht. Es ist wichtig zu wissen, wie das, was wir oben bekommen haben, berechnet wird und wie es funktioniert. Entropie ist ein Maß für Verwirrung oder Unsicherheit, und das Ziel von Modellen für maschinelles Lernen und Data Science-Spezialisten im Allgemeinen besteht darin, diese Unsicherheit zu verringern.

Jetzt wissen wir, wie das Chaos gemessen wird. Als nächstes benötigen wir einen Wert, um die Reduzierung dieser Störung in den zusätzlichen Informationen (Attribute / unabhängige Variablen) der Zielvariablen / -klasse zu messen. Hier kommt der Informationsgewinn oder Informationsgewinn ins Spiel. Aus mathematischer Sicht kann es wie folgt geschrieben werden:



Wir subtrahieren einfach die Entropie Y von X von der Entropie Y, um die Abnahme der Unsicherheit über Y zu berechnen, vorausgesetzt, es gibt Informationen über X über Y. Je stärker die Unsicherheit abnimmt, desto mehr Informationen können von Y über X

erhalten werden. Schauen wir uns ein einfaches Beispiel der Kontingenztabelle an Gehen Sie näher an die Frage heran, wie Entscheidungsbäume mithilfe von Entropie und Informationsgewinn entscheiden, auf welcher Grundlage Knoten im Lernprozess für Daten gebrochen werden sollen.

Beispiel: Konjugationstabelle



Hier ist unsere Zielvariable Liability , die nur zwei Werte annehmen kann: "Normal" und "Hoch".. Wir haben auch nur ein Zeichen, das als Bonität bezeichnet wird. Es verteilt die Werte in drei Kategorien: „Ausgezeichnet“ , „Gut“ und „Schlecht“ . Insgesamt wurden 14 Beobachtungen gemacht. 7 von ihnen gehören zur Klasse der normalen Haftung und 7 weitere zur Klasse der hohen Haftung . Dies ist eine Teilung an sich.

Wenn wir uns die Gesamtsumme der Werte in der ersten Zeile ansehen, werden wir sehen, dass wir 4 Beobachtungen mit einem ausgezeichneten Wert basierend auf der Bonität haben . Darüber hinaus kann ich sogar sagen, dass meine Zielvariable durch die Bonität „Ausgezeichnet“ gebrochen wird . Unter den Beobachtungen mit dem Wert "Ausgezeichnet" nach AttributBonität , es gibt 3, die zur Klasse der normalen Haftung gehören, und 1, die zur Klasse der hohen Haftung gehören . Ebenso kann ich ähnliche Ergebnisse für andere Bonitätswerte aus der Kontingenztabelle berechnen .

Zum Beispiel verwende ich die obige Kontingenztabelle, um die Entropie unserer Zielvariablen unabhängig zu berechnen und dann ihre Entropie unter Berücksichtigung zusätzlicher Informationen aus dem Attribut " Bonität" zu berechnen . So kann ich berechnen, wie viele zusätzliche Informationen mir die Bonität für die Zielvariable Haftung geben wird .

Also lasst uns anfangen.



Die Entropie unserer Zielvariablen ist 1, was maximale Unordnung aufgrund der gleichmäßigen Verteilung der Elemente zwischen „Normal“ und „Hoch“ bedeutet . Der nächste Schritt besteht darin, die Entropie der Haftungszielvariablen unter Berücksichtigung zusätzlicher Informationen aus der Bonität zu berechnen . Dazu berechnen wir die Haftungsentropie für jeden Ratingwert und addieren sie anhand des durchschnittlichen gewichteten Beobachtungsverhältnisses für jeden Wert. Warum wir den gewichteten Durchschnitt verwenden, wird klarer, wenn wir über Entscheidungsbäume sprechen.



Wir haben die Entropie unserer Zielvariablen mit dem Attribut Bonität erhalten. Jetzt können wir den informativen Haftungsgewinn aus der Bonität berechnen, um zu verstehen, wie informativ diese Funktion ist.



Die Kenntnis der Bonität hat uns geholfen, die Unsicherheit unserer Zielvariablen für die Haftung zu verringern.. Ist das nicht ein gutes Zeichen, das funktionieren sollte? Geben Sie uns Informationen über die Zielvariable? Genau aus diesem Grund verwenden Entscheidungsbäume Entropie und Informationsgewinn. Sie bestimmen, nach welchem ​​Kriterium die Knoten in Zweige unterteilt werden sollen, um sich der Zielvariablen bei jeder nachfolgenden Partition zu nähern und um zu verstehen, wann die Baumkonstruktion abgeschlossen sein muss! (zusätzlich zu Hyperparametern wie maximaler Tiefe natürlich). Lassen Sie uns im folgenden Beispiel anhand von Entscheidungsbäumen sehen, wie dies alles funktioniert.

Beispiel: Entscheidungsbaum

Schauen wir uns ein Beispiel für die Erstellung eines Entscheidungsbaums an, mit dem Ziel, vorherzusagen, ob das Guthaben einer Person abgeschrieben wird oder nicht. Die Bevölkerung wird 30 Exemplare sein. 16 werden zur Abschreibungsklasse gehören , die anderen 14 werden"Nicht abschreibbar" . Wir werden zwei Zeichen haben, nämlich "Balance" , die zwei Werte annehmen können: "<50K" oder "> 50K" und "Residence" , die drei Werte annehmen kann : "OWN" , "RENT" oder "OTHER" . Ich werde zeigen, wie der Entscheidungsbaumalgorithmus entscheidet, welches Attribut zuerst gebrochen werden soll und welches Attribut informativer ist, dh die Unsicherheit der Zielvariablen unter Verwendung des Konzepts der Entropie und des Informationsgewinns am besten beseitigt.

Symptom 1: Gleichgewicht



Hier gehören die Kreise zur Klasse „Abschreibung“ , und die Sterne entsprechen der Klasse „Nicht-Abschreibung“ . Partitionieren eines übergeordneten Stamms nach AttributenBalance gibt uns 2 Erbenknoten. Im linken Knoten befinden sich 13 Beobachtungen, wobei 12/13 (Wahrscheinlichkeit 0,92) Beobachtungen aus der Klasse "Abschreibung" und nur 1/13 (Wahrscheinlichkeit 0,08) Beobachtungen aus der Klasse "Nichtabschreibung" . Im rechten Knoten befinden sich 17 von 30 Beobachtungen, wobei 13/17 (Wahrscheinlichkeit 0,76) Beobachtungen aus der Klasse „Abschreibung“ und 4/17 (Wahrscheinlichkeit 0,24) Beobachtungen aus der Klasse „Nicht-Abschreibung“ .

Lassen Sie uns die Entropie der Wurzel berechnen und sehen, um wie viel der Baum die Unsicherheit verringern kann, indem er eine auf Balance basierende Partition verwendet .



Ein auf Balance basierender Split ergibt einen Informationsgewinn von 0,37. Zählen wir dasselbe für das Residenzzeichenund vergleichen Sie die Ergebnisse.

Symptom 2: Residenz



Wenn Sie einen Baum basierend auf der Residenz teilen, erhalten Sie 3 Erbenknoten. Der linke Nachkommenknoten erhält 8 Beobachtungen, wobei 7/8 (Wahrscheinlichkeit 0,88) Beobachtungen aus der Abschreibungsklasse und nur 1/8 (Wahrscheinlichkeit 0,12) Beobachtungen aus der Nichtabschreibungsklasse . Der durchschnittliche Nachfolgeknoten erhält 10 Beobachtungen, wobei 4/10 (Wahrscheinlichkeit 0,4) Beobachtungen aus der Abschreibungsklasse und 6/10 (Wahrscheinlichkeit 0,6) Beobachtungen aus der Nichtabschreibungsklasse . Der rechte Erbe erhält 12 Beobachtungen, wobei 5/12 (Wahrscheinlichkeit 0,42) Beobachtungen aus der Abschreibungsklasse und 7/12 (Wahrscheinlichkeit 0,58) Beobachtungen aus der Nichtabschreibungsklasse. Wir kennen die Entropie des übergeordneten Knotens bereits, daher berechnen wir einfach die Entropie nach der Partition, um den Informationsgewinn aus dem Residence- Attribut zu verstehen .



Der Informationsgewinn aus dem Balance- Attribut ist fast dreimal höher als aus der Residenz ! Wenn Sie sich die Diagramme noch einmal ansehen, werden Sie feststellen, dass die Partitionierung nach Balance sauberere Nachkommenknoten ergibt als nach Residence . Der Knoten ganz links in der Residenz ist zwar auch ziemlich sauber, aber hier kommt der gewichtete Durchschnitt ins Spiel. Trotz der Tatsache, dass der Knoten sauber ist, weist er die geringste Anzahl von Beobachtungen auf, und sein Ergebnis geht bei der allgemeinen Neuberechnung und Berechnung der Gesamtentropie gemäß der Residenz verloren. Dies ist wichtig, da wir nach dem allgemeinen Informationsgehalt des Attributs suchen und nicht möchten, dass das Endergebnis durch den seltenen Wert des Attributs verzerrt wird.

Das Balance- Attribut selbst enthält mehr Informationen zur Zielvariablen als Residence . Dadurch wird die Entropie unserer Zielvariablen reduziert. Der Entscheidungsbaumalgorithmus verwendet dieses Ergebnis, um die erste Aufteilung gemäß Balance vorzunehmenum später zu entscheiden, auf welcher Basis die folgenden Knoten zerstört werden sollen. In der realen Welt erfolgt bei mehr als zwei Merkmalen die erste Aufschlüsselung nach dem informativsten Merkmal, und dann wird bei jeder nachfolgenden Aufteilung der Informationsgewinn für jedes zusätzliche Merkmal nachgezählt, da er nicht mit dem Informationsgewinn von jedem Merkmal einzeln identisch ist. Entropie und Informationsgewinn sollten berechnet werden, nachdem eine oder mehrere Partitionen aufgetreten sind, was sich auf das Endergebnis auswirkt. Der Entscheidungsbaum wiederholt diesen Vorgang, wenn er in der Tiefe wächst, bis er entweder eine bestimmte Tiefe erreicht oder eine Art Aufteilung zu einem höheren Informationsgewinn über einen bestimmten Schwellenwert hinaus führt, der auch als Hyperparameter angegeben werden kann!

Das ist alles! Jetzt wissen Sie, welche Entropie, welcher Informationsgewinn und wie sie berechnet werden. Jetzt verstehen Sie, wie der Entscheidungsbaum selbst oder als Teil eines Ensembles Entscheidungen über die beste Reihenfolge der Partitionierung nach Attributen trifft und entscheidet, wann beim Lernen der verfügbaren Daten aufgehört werden soll. Wenn Sie jemandem erklären müssen, wie Entscheidungsbäume funktionieren, hoffe ich, dass Sie diese Aufgabe angemessen bewältigen.

Ich hoffe, Sie haben aus diesem Artikel etwas Nützliches für sich gelernt. Wenn ich etwas verpasst oder mich falsch ausgedrückt habe, schreibe mir darüber. Ich werde dir sehr dankbar sein! Danke.


Erfahren Sie mehr über den Kurs.

More articles:


All Articles