Problem
Entscheidungsbäume teilen Daten in möglichst reine Gruppen auf. Die Gini-Unreinheit misst, wie gemischt die Labels einer Gruppe sind:
Gini = 1 - Σ pₖ²
wobei pₖ der Anteil der Labels der Klasse k ist. Eine Gruppe mit nur einer Klasse hat die Unreinheit 0; eine gleichmäßige Mischung zweier Klassen hat 0.5.
Implementiere gini_impurity(labels).
Eingabe
labels: Die Klassenlabels der Gruppe.
Ausgabe
Gib die Gini-Unreinheit als Dezimalzahl zurück.
Einschränkungen
1 ≤ Länge ≤ 10.000
Jedes Label hat 1 bis 20 Zeichen
Beispiele
Eingabe:
labels = ["yes", "yes", "no", "no"]
Erwartete Ausgabe:
expected = 0.5
Eingabe:
std::vector<std::string> labels = {"yes", "yes", "no", "no"};
Erwartete Ausgabe:
double expected = 0.5;
Eingabe:
string[] labels = new string[] {"yes", "yes", "no", "no"};
Erwartete Ausgabe:
double expected = 0.5;
Erläuterung
Die Hälfte ist yes und die Hälfte no: 1 - (0.5² + 0.5²) = 1 - 0.5 = 0.5, die stärkste Mischung, die eine Gruppe mit zwei Klassen haben kann.
Eingabe:
labels = ["cat", "cat", "cat"]
Erwartete Ausgabe:
expected = 0.0
Eingabe:
std::vector<std::string> labels = {"cat", "cat", "cat"};
Erwartete Ausgabe:
double expected = 0.0;
Eingabe:
string[] labels = new string[] {"cat", "cat", "cat"};
Erwartete Ausgabe:
double expected = 0.0;
Erläuterung
Nur eine Klasse: 1 - 1² = 0. Die Gruppe ist rein.
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Zähle, wie oft jedes Label vorkommt, denn die Unreinheit hängt nur von der Label-Verteilung ab.
Hinweis 2
Wandle die Zählwerte in Anteile der gesamten Gruppe um und miss dann, wie weit die Gruppe von Reinheit entfernt ist.
Hinweis 3
Eine Gruppe mit nur einem Label sollte null ergeben, während eine ausgeglichene Mischung einen größeren Wert liefert.
Erwartete Komplexität
Zeit O(n), zusätzlicher Speicher O(k)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.