機械学習における決定木
定義
決定木decision treeは木構造を持ち、入力されたデータの特徴量に従って分岐を繰り返し最終的に出力値を求める機械学習手法を指す。
説明
決定木は古典的な機械学習手法の中でも直感的で理解しやすく、その応用も多岐にわたる。教師なし学習にk-平均クラスタリングがあるとすれば、教師あり学習には決定木があると言っても過言ではない。
素数当て問題
決定木が木構造でどのように働くかを理解するために「1から10までの自然数のうち素数を当てる問題」を想像してみる。決定木は各ノードの質問に従ってデータを分割し、結果的に「自然数を見て素数と判定するか」を決定する。
- ($A$): このノードは木のルートrootだ。該当する数が $3n-1$ の形で表されるかを尋ねる。$2, 5, 8$ がここに属する。
- ($B_{1}$): 該当する数が $7$ より小さいかを尋ねる。$2, 5$ はすべて素数で、$8$ は合成数なのでこのノードはリーフleafノードになる。
- ($B_{2}$): 該当する数が $2^{n} -1$ の形で表されるかを尋ねる。$1, 3, 7$ がここに属する。その他のケースはすべて合成数だ。
- ($C$): 該当する数が $2$ より大きいかを尋ねる。$3, 7$ はすべて素数で、$1$ は合成数なのでこのノードはリーフノードになる。
このような構造に従って、$x$ をこの木に入れれば $x$ が素数かどうかを決定できる。しかしこの例からもわかるように決定木は過学習に弱い性質があり、与えられたデータ $1, \cdots , 10$ に対しては100%の精度を示したが、直ちに $x = 11$ は ($B_{1}$) ノードで合成数と判定されるだろう。これは決定木が真に素数の規則を学習できず—データの本質的な特徴を捉えられず表面的な性能にのみ固執した結果、一般化された推論能力を備えられなかったためである。
CART アルゴリズム 1
もちろん上の例のように人が直接木を設計することはなく、実際には CARTClassification And Regression Tree というアルゴリズムで木を構築する。基本的にCARTはデータのある特徴を二分することを繰り返すバイナリ探索的な分岐戦略で性能を向上させる。
分類問題
分類問題の場合は次のようにジニ不純度Gini impurityもしくはエントロピーを損失関数として最小化する方式で木を構築する。 $$ G \left( D \right) = 1 - \sum_{k=1}^{C} p_{k}^{2} = \sum_{k=1}^{C} p_{k} \left( 1 - p_{k} \right) $$ ここで $p_{k}$ はデータ $D$ に属するクラス $k$ の割合を示す。ノードで分類されるデータが純粋であるほどジニ不純度は小さくなり、決定木がデータをうまく分類していると見なす。
ここで再び過学習の話は避けられない。素数当て問題で見たように決定木はデータ中で一度しか現れないケースのための分岐を作ってしまうことがあり、ほとんどのデータに対していかようにも分岐を増やして無理やりデータに合わせることが可能だ。ジニ不純度が低いということは分類結果が純度の高い複数のサブセットに分かれているということであり、必ずしもそのデータの本質を把握しているわけではない点に注意する必要がある。
回帰問題
決定木は本来的には分類器の性質を持つが、CARTの名の通り分類あるいは回帰問題の両方に用いることができる。回帰問題では特徴を分割して各領域で従属変数の平均を予測値として用い、損失関数には平均二乗誤差mean squared errorを使う。図では $x$ という特徴を $x_{1}$ より小さいか、$x_{2}$ より大きいか、あるいはその間かで三つの領域に分け、各領域でオレンジ色で示された平均を用いている。
しかしやはり過学習の危険が潜んでいる。上の図では決定木がデータを三つの領域に分けて非線形な関係をうまく捉えているように見えるが、次のように区間をさらに細かく分割することでトレーニングデータにおける損失をさらに小さくすることができる。
このような無理な当てはめには際限がないため、その性能は常に疑ってかかるべきだ。決定木に習熟するために最も重要なのは第一に、第二に、第三に過学習への警戒心である。
剪定
剪定pruningとは文字どおり決定木の枝を切り落とすことで、前述のように過度にケースを分けて生じる過学習を防ぐための戦略だ。剪定の方法は大きく事前と事後に分けられる。
- 事前剪定: 木を構築する際に、一定の深さ以上に木が成長しないように制約をかけたり、ノードに含まれるデータ数が一定以下になったらそれ以上分岐しない等の制約を課す方法。
- 事後剪定: 一度木を全部構築した後、検証データでの性能がかえって低下しているノードを見つけてそのノードを切り落とす方法。
関連
Breiman, L., Friedman, J., Olshen, R. A., & Stone, C. J. (2017). Classification and regression trees. Chapman and Hall/CRC. https://doi.org/10.1201/9781315139470 ↩︎