Informationsgewinn

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:
labels = ["no", "no", "yes", "yes"]
feature = ["sunny", "sunny", "rain", "rain"]

Erwartete Ausgabe:
expected = 1.0

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

Erwartete Ausgabe:
double expected = 1.0;

Eingabe:
string[] labels = new string[] {"no", "no", "yes", "yes"};
string[] feature = new string[] {"sunny", "sunny", "rain", "rain"};

Erwartete Ausgabe:
double expected = 1.0;

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

Erwartete Ausgabe:
expected = 0.0

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

Erwartete Ausgabe:
double expected = 0.0;

Eingabe:
string[] labels = new string[] {"yes", "yes", "no", "no"};
string[] feature = new string[] {"a", "b", "a", "b"};

Erwartete Ausgabe:
double expected = 0.0;

Referenzen

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

• scikit-learn, Decision trees: mathematical formulation
• Stanford CS229 Machine Learning, lecture notes