決定木を構築するとは、現有的なサンプルデータに基づいて木構造を生成することです。ここでは、最も簡単なケース、つまりサンプルデータの特徴がすべて離散的である場合を考えます。以下の通りです。

    上記のようなサンプルがあると仮定して、根ノードから始めてどのようにして決定木を構築するのでしょうか？

    第一段階：分割属性を決定する（つまり、サンプルデータのどの特徴を基に分割するか）。

    ここで最適な分割特徴を決定する方法は、決定木全体の重要な部分です。最適な分割特徴の選択は、分割後の各ノードのデータの「純度」を最大化するという目標に基づいています。つまり、その特徴を基に分類した後の分岐ノードに含まれるサンプルができるだけ同一のクラスに属するようにすることです。適切な特徴を判断ノードとして選ぶことで、迅速な分類が可能になり、決定木の深さを減らすことができます。

    この「純度」をどのように定量化するのでしょうか？

    1.情報利得

    情報エントロピーの定義を示します。サンプルをDで表すとします。

    ここで、piはi番目のクラスが全訓練データ中に現れる確率を表し、このクラスに属する要素の数を訓練データの要素の総数で割った値として推定することができます。Mはクラスの数で、上の例では債務返済能力の有無で、m = 2です。

    エントロピーはサンプルの混乱度を表し、サンプルデータが無秩序で混乱しているほど、エントロピーは大きくなります。分割特徴の前後でサンプルデータのエントロピーの変化を比較することで、サンプルの純度の変化を判断することができます。