簡単 0件解決済み 正答率0%

Gini Impurity

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

このチャレンジで学べること

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

問題

翻訳を表示

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.

制約

1 ≤ length ≤ 10,000

Each label is 1 to 20 characters

例

例 1
入力:
labels = ["yes", "yes", "no", "no"]

期待される出力:
expected = 0.5
入力:
std::vector<std::string> labels = {"yes", "yes", "no", "no"};

期待される出力:
double expected = 0.5;
入力:
string[] labels = new string[] {"yes", "yes", "no", "no"};

期待される出力:
double expected = 0.5;

解説

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.

例 2
入力:
labels = ["cat", "cat", "cat"]

期待される出力:
expected = 0.0
入力:
std::vector<std::string> labels = {"cat", "cat", "cat"};

期待される出力:
double expected = 0.0;
入力:
string[] labels = new string[] {"cat", "cat", "cat"};

期待される出力:
double expected = 0.0;

解説

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

解き方のヒント

まずは自分で考えてから、ヒントを 1 つずつ開いてみましょう。

ヒント 1

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

ヒント 2

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

ヒント 3

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

目安の計算量

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

参考資料

この課題はCodeUtility用に調整されています。上記の説明と制約に従ってください。

ランキング

全体ランキング

コーダーごとのいちばん良い合格解答です。速く、メモリが少なく、評価が高い解答ほど上位になります。

まだ合格した解答はありません。解いて 1 位になりましょう。

他の人の解答から学ぶ

コミュニティの解答

まだ公開された解答がありません。この課題を解いて最初の解答を共有しましょう。