ジニ不純度とエントロピー
決定木の各ノードの不純度の指標には、主に、ジニ不純度（Gini impurity）、エントロピー（entropy）などがある
以下、決定木のあるノード$ tにおけるそれぞれの不純度を示す。
$ p(i|t)は、ノード$ tでクラス$ iのデータが選ばれる確率。これは、決定木の学習における計算では、ノード$ tにて所属している全データの中でのクラス$ iのデータの割合を用いる。
ジニ不純度（Gini impurity）
ジニ係数（Gini index）ともいわれる
$ I_G(t) = \sum_{j \ne i} p(i|t)p(j|t) = \sum^c_{i=1} p(i|t)(1-p(i|t)) = 1 - \sum^c_{i=1} p(i|t)^2
これの解釈
ノード$ tでクラス$ iのデータが選ばれる確率が$ p(i|t)で、それがクラス$ j (\ne i)に間違われる確率が$ p(j|t)なので、$ \sum_{j \ne i} p(i|t)p(j|t)はノード$ tにおける誤り率を示す
また、クラス$ iを1、それ以外を0とするベルヌーイ試行を考えると、$ p(i|t)(1-p(i|t))はそのベルヌーイ分布の分散となるので、すべてのクラスに関する分散の和を与えている、とも捉えられる
データのクラス分布とジニ不純度の大小の関係
ジニ不純度が最大になるのは、各クラスが一様に分布している場合
2クラスの場合、20個のデータがノード$ tに所属している場合、10:10の割合でクラスが分布するときジニ不純度は最大になる
$ p(i|t) = 1/2となるので、$ 1 - ((1/2)^2 + (1/2)^2) = 1/2
逆に、ノード$ tのすべてのデータどれか1つのクラスである場合、ジニ不純度は最小（0）になる
2クラスの場合、一方のクラスは$ p = 1、もう片方のクラスは$ p = 0となるので、$ 1 - (1^2 + 0^2) = 0
エントロピー（entropy）
交差エントロピーまたは逸脱度ともいわれる
$ I_H(t) = -\sum^c_{i=1} p(i|t) \log_2 p(i|t)
$ -\log_2 p(i|t)（情報量）の期待値をとったものがエントロピー（上の式）
情報量と情報エントロピー（平均情報量）については別途学習しておくとよいです（重要な概念）
事象が不確かであるほどエントロピーは高くなる
データのクラス分布とエントロピーの大小の関係
（同じ不純度を示す指標なので当然だが）ジニ係数と同じ傾向をもつ
エントロピーが最大になるのは、各クラスが一様に分布している場合
たとえば2クラスであれば、20個のデータがノード$ tに所属している場合、10:10の割合でクラスが分布するときエントロピーは最大（1）になる
逆に、ノード$ tのすべてのデータどれか1つのクラスである場合、エントロピーは最小（0）になる