この記事の読者

機械学習・マシンラーニングの手法の１つである「決定木 / Decision Tree」について知りたい.

キーワード・知ってると理解がしやすい

ベルヌーイ試行
決定木 / Decision Tree #まとめ編
- yhayato1320.hatenablog.com

Index

Index
決定木アルゴリズム / Decision Tree
ノード分割規則
- 不純度 / Cost
- 分割の終焉
参考
- 書籍
- Web サイト

決定木アルゴリズム / Decision Tree

#01 では、決定木の「概要」、「定義と数式化」、「クラスの割り当て」などを記した.

#アルゴリズム編 #01
- yhayato1320.hatenablog.com

#02 では、「ノード分割規則」について記す.

また、使用する変数や関数、定義は、#01 のものを参照する.

ノード分割規則

各ノード $t$ における $d$ 次元特徴量空間の最適な分割は、特徴軸ごとに可能な考え得る分割を、 不純度 (impurity)と呼ばれる評価関数で評価し選択する.

ある特徴軸が連続値の属性をもつ場合でも、学習データ数が $N$ であれば、たかだか $N-1$ 個の離散的な分割候補点があるだけである.

これは、隣り合った2点の中間を、その特徴軸の分割候補点のひとつとすればよいということだが、過学習を起こすのはここら辺かねぇ

また、特徴が名義尺度や順序尺度の場合(離散的な場合)は、それらのカテゴリ数の分割候補点があるのみである.

要するに、特徴軸 / 変数が「連続的」でも「離散的」でも、分割候補点は「離散的」に扱えるよって

不純度 / Cost

あるノード $t$ の分割規則を構成するときは、これらすべての候補点を不純度で評価する.

選ばれる分割点は、ひとつの特徴軸のひとつの分割点のみである.

したがって、決定木で得られる分割領域は、 $d$ 次元空間の特徴軸に直行する $d - 1$ 次元超平面で囲まれた領域となる.

不純度 / Cost ノード $t$ (の分割規則)の不純度を

$I (t)\ =\ \phi (\ P(C_1 | t),\ \cdots,\ P(C_K | t)\ )$

と定義する.

ここで、関数 $\phi\ (z_1,\ \cdots,\ z_K$ は、 $z_i\ \geq 0,\ \displaystyle \sum_{i=1}^{K} z_i\ =\ 1$ に対して次の3つの性質を満たせばよい.

不純度の性質

$\phi ()$ は、すべてのクラス $i\ =\ 1,\ \cdots,\ K$ に対して、事後確率 $z_i\ =\ \displaystyle \frac{1}{K}$ のとき、すなわちどのクラスの事後確率も一様に等しいとき最大になる.

$\phi ()$ は、あるクラス $i$ について $z_i\ =\ 1$ となり、 $j \neq j$ のときは、すべて $z_j\ =\ 0$ , すなわち、ただひとつのクラスに定まるとき最小になる.

$\phi()$ は、 $(z_1,\ \cdots,\ z_K)$ に関して対照な関数である.

代表的な不純度を表す関数として、次のようなものが提案されている.

代表的な不純度 / Cost を表す関数

ノード $t$ における誤り率
$I (t)\ =\ 1\ -\ \displaystyle \max_i P(C_i | t)$

交差エントロピーまたは逸脱度 (deviance)
$I (t)\ =\ - \displaystyle \sum_{i=1}^{K} P(C_i | t) \log P(C_i | t)$

ジニ係数 (Gini Index)
$\begin{align} I (t)\ &=\ \displaystyle \sum_{i=1}^{K} \sum_{j \neq i} P(C_i | t) P(C_j | t) \\ &=\ \left(\displaystyle \sum_{i=1}^{K} P(C_i | t) \right)^{2}\ -\ \displaystyle \sum_{i=1}^{K}P(C_i | t)^{2} \\ &=\ 1\ -\ \displaystyle \sum_{i=1}^{K} P(C_i | t)^{2} \\ &=\ \displaystyle \sum_{i=1}^{K} P(C_i | t) (1\ -\ P(C_i | t)) \end{align}$

誤差関数
- クロスエントロピー
- yhayato1320.hatenablog.com

誤り率のイメージ

ジニ係数は次のように解釈することができる.

ノード $t$ で $i$ 番目のクラスのデータが選ばれる確率 $P(C_i | t)$ で、それが $j \neq i$ のクラスに間違われる確率が $P(C_j | t)$ なので、 $\displaystyle \sum_{i=1}^{K} \sum_{j \neq i} P(C_i | t) P(C_j | t)$ は、ノード $t$ における誤り率となっている.

簡易的に例を用いて考えると