Facile 0 résolus 0 % de réussite

Gini Impurity

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

Ce que vous allez apprendre

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

Problème

Afficher la traduction

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.

Contraintes

1 ≤ length ≤ 10,000

Each label is 1 to 20 characters

Exemples

Exemple 1
Entrée :
labels = ["yes", "yes", "no", "no"]

Sortie attendue :
expected = 0.5
Entrée :
std::vector<std::string> labels = {"yes", "yes", "no", "no"};

Sortie attendue :
double expected = 0.5;
Entrée :
string[] labels = new string[] {"yes", "yes", "no", "no"};

Sortie attendue :
double expected = 0.5;

Explication

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.

Exemple 2
Entrée :
labels = ["cat", "cat", "cat"]

Sortie attendue :
expected = 0.0
Entrée :
std::vector<std::string> labels = {"cat", "cat", "cat"};

Sortie attendue :
double expected = 0.0;
Entrée :
string[] labels = new string[] {"cat", "cat", "cat"};

Sortie attendue :
double expected = 0.0;

Explication

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

Comment l'aborder

Essayez d'abord seul, puis ouvrez les indices un par un.

Indice 1

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

Indice 2

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

Indice 3

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

Complexité attendue

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

Références

Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.

La meilleure solution validée de chaque codeur. Les plus rapides, les plus légères et les mieux notées passent devant.

Aucune solution validée pour l'instant. Résolvez-le et prenez la première place.

Apprenez des autres

Solutions de la communauté

Aucune solution publiée pour l'instant. Résolvez ce défi pour partager la première.