決定木

決定木とは

決定木は、「この特徴量はある値より小さいか、それ以上か」という問いでデータを次々に2つへ分けていき、分けた先ごとに予測を出す機械学習の手法です。分け方を図に描くと、1本の幹から枝分かれしていく木を上下逆さにした形になるため、この名前で呼ばれます。予測したいものがクラスのときは分類木（classification tree）、数値のときは回帰木（regression tree）と呼び分けます。

木を形づくる部分

• 根ノード: 木の一番上の地点です。すべての観測値がまだ1つの領域にまとまっている状態を表します
• 分岐のノード: 1つの特徴量と1つの閾値を使って、データを2つの領域に分ける地点です
• 葉ノード: それ以上分けない末端です。葉ごとに1つの予測値を持ちます

新しいデータを予測するときは、根から始めて各分岐の問いに答えながら枝をたどり、たどり着いた葉の予測値を答えとして出します。問いを順にたどるだけなので、なぜその予測になったかを人が追いかけやすいモデルです。

再帰的二分割という育て方

決定木の作り方として、ジェームズ（Gareth James）、ウィッテン（Daniela Witten）、ヘイスティ（Trevor Hastie）、ティブシラニ（Robert Tibshirani）の教科書『An Introduction to Statistical Learning』（2013年）は、再帰的二分割（recursive binary splitting）という手順を説明しています。

1. 木の一番上、つまりすべての観測値が1つの領域に属している状態から始めます
2. 予測変数 Xj と閾値 s の組を1つ選び、領域を「Xj < s」の側と「Xj ≥ s」の側の2つに分けます
3. どの組を選ぶかは、分けたあとの RSS（残差平方和）が最も大きく減るものにします。RSS は、各領域の中で実際の値とその領域の予測値との差を2乗し、すべて足し合わせた量で、小さいほど予測が実際の値に近いことを表します
4. 分けてできた領域に対して、同じ手順を繰り返します

このように、上から下へ向かって予測変数の空間を少しずつ区切っていくため、同書はこの手順をトップダウンの方法と呼んでいます。

貪欲な方法と呼ばれる理由

同書は、再帰的二分割を貪欲な（greedy）方法とも呼んでいます。木を育てる各段階で、その時点で最善の分割を選ぶだけで、先の段階でより良い木につながる分割を先読みしないからです。言い換えると、1回ごとの分割の良さだけを見て進む方法なので、でき上がった木が、ありうるすべての木の中で最善である保証はありません。

手法としての登場

同書の第2章は統計的学習の歴史を振り返る中で、1980年代半ばに、ブレイマン（Leo Breiman）、フリードマン（Jerome Friedman）、オルシェン（Richard Olshen）、ストーン（Charles Stone）が分類木と回帰木（classification and regression trees）を導入したと述べています。あわせて、この4人は、モデル選択のための交差検証まで含めた詳細な実装によって手法の威力を示した最初の人々の一部であったとしています。