Einfach 0 gelöst 0% Erfolgsquote

Gini-Unreinheit

Miss, wie gemischt die Labels einer Gruppe sind, das Kriterium, mit dem Entscheidungsbäume Aufteilungen wählen.

Das lernst du

  • Messen, wie gemischt eine Gruppe von Labels ist
  • Klassenanteile zählen
  • Verstehen, wie Bäume Splits wählen

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

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

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

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.