決定木の基礎
はじめに
決定木は分類や回帰のために広く用いられるモデルである。データを特徴量に基づいて再帰的に分割し、木構造を構築することで予測を行う。シンプルで可視化が容易である点が特徴である。機械学習においては、教師あり学習の非線形モデルに該当する。本稿では、分類木を中心に解説する。回帰木の場合、エントロピーではなく分散を指標にして不純度を減らすだけの違いとなる。
1. 決定木の基本構造
決定木は入力空間を条件分岐によって分割し、それぞれの領域を葉ノードに対応させる。分類問題においては各葉ノードが特定のクラスに対応し、回帰問題においては各葉ノードが数値予測値に対応する。
ある$d$次元のサンプル $\mathbf{x} \in \mathbb{R}^d$ に対し、決定木は以下のように予測を行う。写像の形なので非常にシンプルな式であり、要は予測値は特徴量をうまくわけることで生成される。
\hat{y} = f(\mathbf{x}; \theta) ※θは各ノードで情報利得を最大化
ここで $\theta$ は木の構造（分割特徴量、しきい値、葉ノードの値）を表すパラメータである。
なお、ここでのセミコロンは「数式上の慣習的な区切り」であり、引数（入力変数）とパラメータ（モデルを決める値）を区別するために使った。
2. 不純度の定義
決定木の分割は、各ノードの「純粋さ」を最大化するように設計される。この純粋さの尺度が不純度である。代表的な不純度指標にはジニ不純度とエントロピーがある。
2.1 ジニ不純度
ジニ不純度は次の式で定義される。
\text{Gini}(t) = 1 - \sum_{k=1}^{K} p_{k}^2
ここで $p_k$ はノード $t$ におけるクラス $k$ の出現確率である。ジニ不純度は「ランダムにサンプルを一つ選んだときに誤分類される確率」に対応する直感的な指標である。
2.2 エントロピー
エントロピーは情報理論に基づく不確実性の尺度である。
S(t) = - \sum_{k=1}^{K} p_{k} \log_2 p_{k}
値が大きいほどクラスが混在しており、情報の不確実性が高いことを意味する。
ここでエントロピーの式の解釈をしたい。結論から言うと、自己情報量$log_2 p_{k}$(ある事象から得られる“驚き”の大きさ)の期待値である。解釈のためにまず、$1bit$で表すことができる状態を考える。$1bit(0または1)$で表すことができる状態は$2$通りである。$n$ $bit$の場合、$2^n$通りの状態を表すことができる。これをビット数$I$と状態$W$を数式で紐づけると
W=2^I⇔I=log_2W
となる。また、サイコロの出目のように、各状態$W$の確率は等確率であり$P$とすると、$W=1/P$であるため、
I=log_2\frac{1}{P}=-log_2P
となる。この$I$を自己情報量と呼ぶ。起こりにくい事象ほど大きな情報量が必要という理解で良い。自己情報量は各事象(サイコロで言えば、特定の目1が出る局所的な事象)に対する量であり、確率分布全体を代表するものではない。そこで、確率分布全体に対してどう表現すればよいだろうか。結論から言うと、上式の情報エントロピー$S$で表すことができる。
自己情報量と情報エントロピーの違い：「ただの平均」ではなぜダメなのか？
2.2.1 「ただ平均」と「期待値」の違い
情報エントロピーは「自己情報量の平均」であるが、平均の取り方には注意が必要である。
- 誤りやすい考え方
全ての事象の自己情報量を等しく平均する。
\frac{1}{K}\sum_{i=1}^K I(x_i)
- 正しい定義
各事象の発生確率を重みとして平均を取る（期待値）。
H(X) = \sum_i P(x_i) \, I(x_i) = -\sum_i P(x_i)\log P(x_i)
2.2.2 具体例：くじ引き
「当たり 1%、ハズレ 99%」のくじを考えると、なぜただの平均ではなく、期待値をとるべきか明確になる。
- 当たりの自己情報量
I(\text{当たり}) = -\log(0.01) \approx 6.64
- ハズレの自己情報量
I(\text{ハズレ}) = -\log(0.99) \approx 0.014
**(1)ただ平均した場合
\frac{6.64 + 0.014}{2} \approx 3.33
これではまるで「毎回 3.33 ビットの情報が得られる」と言っていることになるが、実際にはほとんどハズレばかりなので直感に反する。
**(2)確率で重み付けした場合（正しいエントロピー）
H = 0.01 \times 6.64 + 0.99 \times 0.014 \approx 0.080
実際には 1 回の試行から得られる平均情報量はごく小さい。したがって、期待値の形式が現実をよく反映している。
2.3 不純度まとめ
- 自己情報量は ある事象から得られる“驚き”の大きさ を表す。
- 情報エントロピーは 自己情報量を確率で重み付けした期待値 である。
- 単純平均では全ての事象が等確率であると仮定してしまい、現実の確率分布を反映できない。
したがって情報エントロピーは、分布全体の不確実性を測る正しい指標となる。
3. 情報利得（Information Gain）とは何か？
3.1. 決定木と不純度
決定木は「データをできるだけ純粋に分ける」アルゴリズムである。
その純粋さがどれだけ上がったかの指標として 情報利得 が使われる。
決定木は「情報利得が最大になる分割」を選んでノードを成長させていく。
3.2. 情報利得の定義
あるノード $(t)$ を特徴量 $(X_j)$ で分割したとき、
親ノードの不純度と子ノードの不純度を比較し、改善度を次のように定義する：
Gain(t, X_j) = 不純度(t) - \Bigg( \frac{N_L}{N_t} 不純度(t_L) + \frac{N_R}{N_t} 不純度(t_R) \Bigg)
- $(不純度(t))$：親ノードの不純度
- $(不純度(t_L), 不純度(t_R))$：子ノードの不純度
- $(N_t)$：親ノードのサンプル数
- $(N_L, N_R)$：子ノードのサンプル数
3.3. なぜ重み付き平均なのか？
なぜ上式の子ノードの不純度に$N_L/N_t$と$N_R/N_t$という係数をかけるか分かりにくい。
もし重みをつけなければ、極端なケースで誤解が生じる。
例：親ノードに100サンプルがあり、分割すると
- 左ノード：99サンプル（不純度 = 0.5）
- 右ノード：1サンプル（不純度 = 0.0）
単純平均すると
\frac{0.5 + 0.0}{2} = 0.25
となり、「良い分割」に見えてしまう。
しかし実際には 99 サンプルがまだバラバラであるため、改善はほとんどない。
重み付き平均を使うと：
\frac{99}{100}\times 0.5 + \frac{1}{100}\times 0.0 = 0.495
となり、「改善がほとんど無い」ことを正しく反映できる。
3.4. 数値例
親ノードの不純度が 0.5 のとき、分割後に次のようなノードができたとする：
- 左ノード（4サンプル）：不純度 = 0.0
- 右ノード（6サンプル）：不純度 = 0.3
すると情報利得は
Gain = 0.5 - \Big( \frac{4}{10}\times 0.0 + \frac{6}{10}\times 0.3 \Big)
= 0.5 - 0.18 = 0.32
この分割によって不純度が 0.32 だけ減少したことを意味する。
3.5. 結局情報利得とは?
- 情報利得 = 分割前の不純度 − 分割後の不純度の重み付き平均
- 値が大きいほど「その特徴量で分割するとデータをきれいにできた」ことを意味する
実装する際のコードはGithubで公開済。
https://github.com/med-chem/decision-tree-sample-code-for-my-learning