オムライスの備忘録

数学・統計学・機械学習・プログラミングに関することを記す

【機械学習】決定木 / Decision Tree #アルゴリズム編 #01

この記事の読者

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


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

Index

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

単純な識別規則を組み合わせて複雑な識別境界 / 非線形識別空間を取得する手法.

識別関数は、非線形関数となるのが特徴.



 a\ <\ x1\ <\ d かつ  c\ <\ x2\ <\ b なら「グループ 7」 となり、分類結果は「白」.



上図ように、ある特徴軸 (上図でいうと、x1, x2) の「データ値」と「閾値 (上図でいうと、a ~ e) 」の大小関係を判断する過程は、下図のように決定木として表現できる.

構成要素

を構成する要素は、

  • ノード
  • ノードとノードを結ぶリンク



ノードにも種類があり、以下のように呼称する.

  • 一番最初のノードを根ノード
  • 一番末端のノードを終端ノード葉ノード
  • 根ノードでも葉ノードでもないノードを内部ノード



葉ノード以外のノード(非終端ノード)で、閾値判断が行われる.

与えられたデータがどちらのクラスに属するかは、葉ノードが決定する.

ボトムアップトップダウン

  • ボトムアップ的な手法 : ある一つの学習データを正しく識別できる特徴の集合を探して特殊な識別規則を作り、 特徴に対する制約を緩めながら、他の学習データも正しく識別できるよう規則を一般化する.

  • トップダウン的な手法は、まず根ノードですべての学習データをできるだけ誤りの少ないようにクラス分けできる特徴量/軸を探して 特徴量空間を2分割する規則を求め、2分割された空間をさらにそれぞれ2分割する規則を求めることを繰り返して決定木を成長させる手法であり、 分割統治法と呼ばれる.



現在はトップダウン的な手法で決定木を構築するのが主流.

トップダウン的な手法で決定木を学習データから構築するためには、次の要素について考える必要がある.

  1. 各ノードにおいて特徴空間分割規則を構成するための「特徴軸」と「閾値」の選択.
  2. 葉ノードの決定. 一つの葉ノードに一つのクラスの学習データのみが含まれるまで特徴量空間の分割を繰り返し大きな木を作るのか、 あるいは複数のクラスの学習学習データが含まれても良いとするのかの選択. また、大きくなった木の剪定(pruning)をどこまで行うかの選択.
  3. 葉ノードに対する多数決によるクラスの割り当て. (#01)

決定木の方式

決定木の学習に関する代表的な方式には、CART (Classification And Regression Tree) と呼ばれるものと、 ID3 (Iterative Dichotomiser 3) やその後継の C4.5 と呼ばれるものがある.

以下からはCARTを前提に進める.

決定木に関する「定義」と「数式化」

リンクを関数として定義 木は0ではない有限個の正の整数からなる集合  T と、その要素  t \in T から 集合  T \cup \{0\} への2つの関数  left right で構成されている.


CART の決定木は 2分木であり、 left right はそれぞれ左側、右側の次のノード番号を与える関数である.

これらは次の2つの性質を満たす.

木が満たす性質

  1.  t \in T について、以下のいずれかが成り立つ.

    1.  left (t) = right (t) = 0 (葉ノード)
    2.   left (t) > t かつ  right (t) > t (非終端ノード)


  2.  t \in T について、集合  T 内の最小数 (根ノード) を除いて  t = left(s) または、 t = right(s) のどちらかを満たすただ1つの  s \in T が存在する.

     s親ノード t子ノードといい、 s = parent(t) で表す.



木自身を  T で表すことにする.

リンクの番号 ノードの番号は  right(t) = left(t) + 1 が成り立つように付与するものとする.


祖先と子孫

リンクをたどって親の親の関係にあるノードを祖先という. 逆の関係を子孫という.



例えば、ノード  s が、ノード  t の祖先であれば、ノード  t からノード  s への 一意のパスがあって、

 s_{m}\ (=t),\ s_{m-1},\ \cdots,\ s_{1},\ s_{0}\ (=s)



のようなノード達がリンクでつながり、

 s_{m-1}\ =\ parent(s_{m}),\ \cdots\ , s_{0}\ =\ parent(s_{1})



の関係が成り立っている.

パスの長さ

このようなリンクのつながりの長さを、パスの長さといい、
 l(s, t) = m で定義する.



終端ノード(葉ノード)と非終端ノード

木(ノードの集合)  T葉ノード (終端ノード) の集合 \tilde{T} で表し、
差集合  T - \tilde{T}非終端ノードの集合を表す.



部分木

空でない 集合 T の部分集合  T_1に対して、 T_1 から  T \cup \{0\} への2つの関数を


left_{1}(t)
\ = \left\{ \begin{array}{}
left(t) & (left(t) \in T_{1} の場合)\\
0 & (それ以外)
\end{array} \right.


right_{1}(t)
\ = \left\{ \begin{array}{}
right(t) & (right(t) \in T_{1} の場合)\\
0 & (それ以外)
\end{array} \right.


と定義したとき、三つ組み  T_1,\ left_1(t),\ right_1(t) が木を構成するならば、 T_1部分木という.





剪定された部分木 部分木  T_1 の根ノードが  T の根ノードと等しい場合、 T_1剪定された部分木といい、  T_1 \preccurlyeq T で表す.




分枝 (ぶんし) / branch  \forall t \in T に対して、 t とその子孫すべてで構成されている部分木  T_t を、 T の分枝 (branch) とよぶ.




空間 / 領域としての葉ノード(終端ノード)の意味 各葉ノード(終端ノード)  t \in \tilde{T}d 次元特徴空間の1つの分割領域  u (t) \in \mathbb{R}^{d} に対応している.

ここで、以下が成立する.


t,\ s\ \in \tilde{T},\ t \neq s\ \Rightarrow\ u(t)\ \cap\ u(s)\ =\ \emptyset



つまり、異なる葉ノードであれば、対応する空間に重複はない.

また、以下も成立する.


\displaystyle \bigcup_{t\ \in\ \tilde{T}} u(t)\ =\ \mathbb{R}^{d}



つまり、すべての葉ノードの対応する空間の和集合は、特徴量空間に相当する.



決定木では、各領域  u(t)特定のクラスを割り当てて、入力データのクラス分類を行う.

ノードにおける確率

クラスを C_i\ (i\ =\ 1,\ \cdots,\ K) としたとき、あるノード  t が表すクラス  j の事前確率を以下のように計算する.

クラスラベル付きの学習データ集合を \{(x_i,\ t_i)\}\ (i\ =\ 1,\ \cdots,\ N) とする.

この添字がついた t_i は教師データ



事前確率 クラス  j に属する学習データ数を  N_j とすれば、クラス  j の事前確率は、以下のようになる.

 P(C_j)\ =\ \displaystyle \frac{N_j}{N}



特徴量空間は決定木のノードを経るごとに分割されていく.

あるノード  t の領域に属する学習データ数を N(t)とする.

 N(t) 個のデータのうち、 j 番目のクラスに属するデータを  N_j (t) で表す.

 \displaystyle \sum_{j=1}^{K} N_j (t)\ =\ N(t) が成立するのだが、一応ここに記載





同時確率 クラス  j の学習データがノード  t に属する確率は、以下のようになり、

 P(t | C_j)\ =\ \displaystyle \frac{N_j(t)}{N_j}



あるデータが「該当するクラスが  j 」で、「ノード  t に対応する領域 u(t) に属する」 同時確率は、

 P(C_j , t)\ =\ P(C_j) P(t | C_j)\ =\ \displaystyle \frac{N_j (t)}{N}



となる.



ノード t の周辺確率

したがって、ノード t の周辺確率は、

 p(t)\ =\ \displaystyle \sum_{j=1}^{K} p(C_j, t)\ =\ \displaystyle \sum_{j=1}^{K} \displaystyle \frac{N_j (t)}{N}\ =\ \displaystyle \frac{\displaystyle \sum_{j=1}^{K} N_j (t)}{N}
\ =\ \displaystyle \frac{N(t)}{N}



となる.



事後確率  t におけるクラス j の事後確率 (つまり、ノード  t に対応する領域  u(t) に属するデータが、あるクラス  j に該当する確率)は、

 P(C_j | t)\ =\ \displaystyle \frac{p(C_j, t)}{p(t)}\ =\ \displaystyle \frac{N_j (t)}{N (t)}



となる.



最終的な数式の意味としては、

\displaystyle \frac{あるノード t に対応する領域 u(t)に属するデータのうち、クラス C_j に属するデータ}{あるノード t に対応する領域 u(t) に属するデータ数}



となり、そりゃそうかという感じに落ち着く.

クラス分類において、重要なことは入力データ  x がどのクラスに分類されるのか、もしくは各クラスに含まれる確率である.

入力データが決定木の規則によってある葉ノードに当てはまったとき、「どのクラスとして分類される確率」はここでいう事後確率を示す.

この確率を関数と考え、以下のような形式の関数と考えることができる.

 \displaystyle \sum_{m=1}^{M} w_m \phi (x)


そのとき、決定木の事後確率は適応基底関数モデルとして考えることができる.





ノード  t においてクラス識別 / 分類を行う場合、事後確率が最大となるクラスを選ぶ.

識別クラス =  arg \displaystyle \max_{i} P(C_i | t)





ノード  t で学習データはさらに分割され、子ノード  t_L = left (t) t_R = right(t) が生成される.

子ノードへの確率

データ  x がどちらの子ノードに属するかは、確率

 p_{L}(t)\ =\ p(x \in u(t_{L}) | x \in u(t))\ =\ \displaystyle \frac{p(t_{L})}{p(t)}

 p_{R}(t)\ =\ p(x \in u(t_{R}) | x \in u(t))\ =\ \displaystyle \frac{p(t_{R})}{p(t)}

緒定義完了.

参考

書籍

Web サイト

  • 今更感あるけど決定木について調べたのでまとめる