Mittel 0 gelöst 0% Erfolgsquote

Informationsgewinn

Berechne, wie stark die Aufteilung nach einem Merkmal die Entropie verringert, das Kriterium hinter ID3-Entscheidungsbäumen.

Das lernst du

  • Die Entropie vor und nach einem Split berechnen
  • Teilmengen nach ihrer Größe gewichten
  • Das informativste Merkmal wählen

Problem

Die Entropie misst die Unsicherheit einer Menge von Labels: H(S) = -Σ pₖ × log₂(pₖ), wobei pₖ der Anteil der Labels der Klasse k ist. Der Informationsgewinn gibt an, wie stark die Entropie sinkt, wenn man die Menge nach einem Merkmal aufteilt:

IG = H(labels) - Σ (|Sᵥ| / |S|) × H(Sᵥ)

wobei Sᵥ die Labels der Beispiele enthält, deren Merkmal gleich v ist. Entscheidungsbäume wählen das Merkmal mit dem größten Gewinn.

Implementiere information_gain(feature, labels).

Eingabe

feature: Der Merkmalswert jedes Beispiels.

labels: Das Klassenlabel jedes Beispiels (gleiche Länge).

Ausgabe

Gib den Informationsgewinn in Bit als Dezimalzahl zurück.

Einschränkungen

1 ≤ Länge ≤ 10.000

Jeder Wert und jedes Label hat 1 bis 20 Zeichen

Beispiele

Beispiel 1
Eingabe:
feature = ["sunny", "sunny", "rain", "rain"]
labels = ["no", "no", "yes", "yes"]

Erwartete Ausgabe:
expected = 1.0
Eingabe:
std::vector<std::string> feature = {"sunny", "sunny", "rain", "rain"};
std::vector<std::string> labels = {"no", "no", "yes", "yes"};

Erwartete Ausgabe:
double expected = 1.0;
Eingabe:
string[] feature = new string[] {"sunny", "sunny", "rain", "rain"};
string[] labels = new string[] {"no", "no", "yes", "yes"};

Erwartete Ausgabe:
double expected = 1.0;

Erläuterung

Die Labels sind halb yes und halb no, also H = 1 Bit. Die Aufteilung nach Wetter ergibt zwei reine Gruppen (jeweils H = 0), also ist der Gewinn 1 - 0 = 1: Das Merkmal verrät alles.

Beispiel 2
Eingabe:
feature = ["a", "b", "a", "b"]
labels = ["yes", "yes", "no", "no"]

Erwartete Ausgabe:
expected = 0.0
Eingabe:
std::vector<std::string> feature = {"a", "b", "a", "b"};
std::vector<std::string> labels = {"yes", "yes", "no", "no"};

Erwartete Ausgabe:
double expected = 0.0;
Eingabe:
string[] feature = new string[] {"a", "b", "a", "b"};
string[] labels = new string[] {"yes", "yes", "no", "no"};

Erwartete Ausgabe:
double expected = 0.0;

Erläuterung

Die Gruppen a und b enthalten jeweils noch ein yes und ein no (H = 1), also ist der Rest 0.5 × 1 + 0.5 × 1 = 1 und der Gewinn 1 - 1 = 0: Das Merkmal ist nutzlos.

So gehst du vor

Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.

Hinweis 1

Miss zuerst die Unsicherheit der Labels vor jedem Split und vergleiche sie dann mit der Unsicherheit in jeder Feature-Gruppe.

Hinweis 2

Gruppiere Samples nach Feature-Wert, zähle die Labels pro Gruppe und kombiniere die Entropie jeder Gruppe nach ihrem Anteil an den Daten.

Hinweis 3

Achte auf wiederholte Werte und den Fall, dass eine Gruppe nur ein Label hat, denn dann ist ihr Entropiebeitrag null.

Erwartete Komplexität

Zeit O(n), zusätzlicher Speicher O(n)

Referenzen

Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

Noch keine bestandene Lösung. Löse sie und hol dir Platz eins.

Von anderen lernen

Community-Lösungen

Noch keine veröffentlichten Lösungen. Löse die Aufgabe und teile als Erster eine Lösung.