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
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.
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.