決定木の基本的な考え方

マイニング手法としてクラス（質的な目的変数）を分類予測するとき，よく用いられる手法として決定木があります*1．
データマイニングというと決定木という印象をもっている方も多いことと思います．
決定木は，分類予測に至る道筋を一意に表現できるため，その了解性は非常に高いと言えます．

決定木の学習

決定木学習は，訓練データを属性-値の組で分けていく過程を木構造で表される分類器とするものです．
ある分割指標を用いて，入力された訓練データを分割して，さらに分割されたデータで指標を計算して...と繰り返し，小さいデータに分割と指標の計算が適用されます．
この仕組みを分割統治（divide and conquer）と呼びます．

シンプルに決定木学習の動作を挙げると以下のようになります．

データ分割指標の計算
データ分割基準（節）の作成
分割したデータの作成

決定木学習では，上記の1〜3を再帰的に繰り返して，終了条件を満たすまですべての訓練データから分割データを作成していきます．
終了条件は，分割したデータのデータ数や分割指標に閾値を用います．もちろん，クラスが一意になれば，終了です．
終了条件を満たしたデータは，”葉”にあたります．

ここで，それぞれの決定木学習アルゴリズムで異なるのは，データ分割指標と分割基準の選択および作成方法です．
決定木学習では，データを分割することによって，分割対象データが分割後にクラスの偏りが大きくなるようにします．
これが，ID3/C4.5では情報利得（比）であり，CARTではジニ係数であったりします．

データ分割基準の選択と作成では，属性値の扱いでアルゴリズム毎に相違があります．
数値属性に対しては，何回分割基準として用いるか，あるいは，どのような関係演算子を用いるか，が考えるべき点となります．
離散属性に対しては，複数の離散値ごとに分岐を作成するか，グループとするか，も異なります．
また，欠損値の扱いはどのようなデータ分割指標を用いるか，によっても異なります．
分割基準（属性と属性値とその関係）のことを”節”と呼びます．

なお，決定木学習ではデータを分割していきますので，葉に近く用いられる分割基準（属性）ほど説明力が小さくなります．
この説明力の小さい分割基準が汎化性能を低下させる過学習（over-fitting）を防ぐため，「枝刈り」という操作が必要となります．

決定木による予測

決定木が学習できると，ルートの分割基準から順にテストデータの属性と値に基づいて分岐をたどっていき，葉に割り当てられたクラスを予測クラスとします．
決定木による予測では，どの基準が当てはまるか，一意に決まりますので，if-thenルール集合による予測のような競合解消は生じません．
ただし，テストデータの分割基準にあたる属性の値が欠損していた場合には，作成時に分岐のしやすさを分割後のデータ数の割合などとして与えておき，葉に到達するまでの合計重みなどで予測クラスの確信度とすることもあります．