決定木についてメモ

決定木

two-class boosted decision tree というのが出てきて、なんじゃそりゃ、と思ったので調べたのでメモ。 boostingとdecision treeについて分かればよいことはすぐ分かった。 boostingは難しそうなので、とりあえずdecision treeについて。

decision tree

決定木。 名前の通り木構造で、葉以外のノードはdecision nodesと呼ばれる。 各decision nodeからは2本以上の枝が伸びていて、これがデータの分類を表す。 葉ノードは分類の最終的な結果を表す。 葉ノードの持つ情報がクラス名であれば、決定木を使った分類*1が可能になる。 数値であれば、（離散的ではあるが）回帰分析ができる。

ID3 algorithm

データをもとに決定木を構成するアルゴリズム*2。 たとえば、「天気」と「気温」と「湿度」と「風の強さ」と「野球の試合が行われたかどうか」の30日分のデータをもとに、前の4つの項目が与えられたときに「野球の試合を行うかどうか」を決定する決定木を構成する場合、 前の4つの項目について

• その項目を使って分類したときに、情報がどれだけ整理されるか

を表す量*3を計算する。 その量が「天気」で最大になる場合、決定木の根ノードは「天気」となる。 天気で分類したそれぞれのデータについて、再び同様の計算を行い、さらに分類していくことで決定木が得られる。

C4.5 algorithm

ID3を改良したアルゴリズム。 現在ではふつう、ID3よりはこちらのほうが使われるらしい。 ちゃんと調べていないけど、ID3との違いは、上で述べた「情報の整理される度を表す量」を正規化*4するところだけっぽい。

参考

■ID3 Algorithm http://www.cise.ufl.edu/~ddd/cap6635/Fall-97/Short-papers/2.htm

■Decision Tree Regression http://www.saedsayad.com/decision_tree_reg.htm 説明はわかりやすいが、通常ID3と言った場合に使われるものとは違う量を使っている*5ことに注意。

*1:clusteringではなく、classificationのほう

*2:名前はIterative Dichotomiser 3の略らしい。dichotomiseという単語を、これを調べるまで見たことがなかった。

*3:information gain. エントロピーの説明も含めてそのうちちゃんと整理して書きたい

*4:どういう操作がどういう意味でそう呼ばれているのかは知らない。information gainとあわせて調べて書きたい

*5:information gainの代わりにSDRという量を使っている。分類後の各グループの標準偏差をもとに計算される。何か根拠があって同じ結果が得られることが保証されるのかもしれないが確認していない