中級 0件解決済み 正答率0%

情報利得

特徴量で分割したときにエントロピーがどれだけ減るかを計算します。ID3 決定木の基準です。

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

  • 分割前後のエントロピーを計算する
  • 部分集合を大きさで重み付けする
  • 最も情報量の多い特徴量を選ぶ

問題

原文(英語)を表示

エントロピーはラベル集合の不確かさを測ります:H(S) = -Σ pₖ × log₂(pₖ)。pₖ はクラス k のラベルの割合です。情報利得は、集合を特徴量で分割したときにエントロピーがどれだけ下がるかです。

IG = H(labels) - Σ (|Sᵥ| / |S|) × H(Sᵥ)

ここで Sᵥ は、特徴量が v であるサンプルのラベルです。決定木は情報利得が最も高い特徴量を選びます。

information_gain(feature, labels) を実装してください。

入力

feature: 各サンプルの特徴量の値。

labels: 各サンプルのクラスラベル(同じ長さ)。

出力

情報利得をビット単位の小数で返してください。

制約

1 ≤ 長さ ≤ 10,000

各値とラベルは 1 〜 20 文字

例

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

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

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

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

解説

ラベルは半分が yes、半分が no なので H = 1 ビット。天気で分割すると純粋な2グループ(それぞれ H = 0)になるので、利得は 1 - 0 = 1 です。この特徴量ですべてがわかります。

例 2
入力:
feature = ["a", "b", "a", "b"]
labels = ["yes", "yes", "no", "no"]

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

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

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

解説

グループ a と b はどちらも yes と no を1つずつ含む(H = 1)ので、残りは 0.5 × 1 + 0.5 × 1 = 1、利得は 1 - 1 = 0 です。この特徴量は役に立ちません。

解き方のヒント

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

ヒント 1

分割前にまずラベルの不確実性を測り、その後で各特徴グループ内の不確実性と比較します。

ヒント 2

特徴値ごとにサンプルをまとめ、各グループ内のラベル数を数えて、データ比率で各グループのエントロピーを合成します。

ヒント 3

重複値や、1種類のラベルしかないグループに注意してください。その場合、そのグループのエントロピー寄与は 0 です。

目安の計算量

時間 O(n)、追加メモリ O(n)

参考資料

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

ランキング

全体ランキング

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

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

他の人の解答から学ぶ

コミュニティの解答

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