Einfach 0 gelöst 0% Erfolgsquote

Gini Impurity

Measure how mixed the labels in a group are, the score decision trees use to choose splits.

Das lernst du

  • Measure how mixed a group of labels is
  • Count class proportions
  • Understand how trees choose splits

Problem

Übersetzung anzeigen

Decision trees split data into groups that are as pure as possible. Gini impurity measures how mixed a group's labels are:

Gini = 1 - Σ pₖ²

where pₖ is the fraction of labels equal to class k. A group with a single class has impurity 0; an even mix of two classes has impurity 0.5.

Implement gini_impurity(labels).

Input

labels: The class labels in the group.

Output

Return the Gini impurity as a decimal number.

Einschränkungen

1 ≤ length ≤ 10,000

Each label is 1 to 20 characters

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

Half are yes and half are no: 1 - (0.5² + 0.5²) = 1 - 0.5 = 0.5, the most mixed a two-class group can be.

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

Only one class: 1 - 1² = 0. The group is pure.

So gehst du vor

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

Hinweis 1

Count how often each label appears, because impurity depends only on the label distribution.

Hinweis 2

Convert counts to fractions of the whole group, then measure how far the group is from being pure.

Hinweis 3

A single-label group should give zero, while a balanced mix should give a larger value.

Erwartete Komplexität

O(n) time, O(k) extra space

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.