Cost Complexity Pruning で決定木の枝刈りをして過学習を抑える【機械学習】

決定木はとっても解釈性の高い機械学習アルゴリズムで、使い勝手がよいのですが容易に過学習してしまう欠点があります。

バギングなりブースティングなり、決定木のアンサンブルを行うことで過学習を抑え精度を高くすることができるのですが、アンサンブルしてしまうと結果の解釈性が落ちてしまい、またツリーの可視化等もできなくなってしまいます。

そこで、もとの決定木のままでできるだけ過学習を抑えるにはどうしたらいいのか、というところで枝刈りについて少し勉強しましたので、メモを残しておこうと思います。

 

枝刈り(Pruning)には2種類ある

 

枝刈りには、木を構築する前に設定して行うもの(pre-pruning)と、木を構築した後に刈っていくもの(post-pruning)と2種類あります。

前者は、例えば木の深さや、分岐の葉の数を制限するといったことです。sklearn では max_depth 等のハイパーパラメータで調整できます。

今回見る Cost Complexity Pruning は後者のやり方です。他にも、Reduce Error Pruning であるとか Critival Value Pruning 等さまざまあるようです。

 

Cost Complexity Pruning とは

 

Tree Score を設定して、様々なノード数の木に対してスコアが小さくなるようにチューニングする枝刈りの方法です。

Tree Score = 木の不純度の総和 + α x ノードの数

と定義されます。分類木の場合は不純度ですが、回帰木の場合は残差の総和で計算するようです。

木を深くして細かく細分化すればするほど、不純度の総和は小さくなるため、深いほど式の前半箇所は小さくなり、Tree Score が下がります。一方で、木が深くなるほど、ノードの数は増えるため、式の後半部分が大きくなり、Tree Score は大きくなります。

このバランスをとるαの値を見つけます。

 

分類木で実装しながら確認する

 

scikit-learn では ccp_alpha というパラメータでこの α の値を設定できます。

sklearn のドキュメントをさらっていきます。(内容はまんまドキュメントなので、英語に抵抗がなければ元ページを見るのがよいです。ページ下の参考にリンクをのっけています)

cost_complexity_pruning_path というメソッドでは、効果的な alpha の値と、それぞれの時の不純度が返ってきます。

例えば、すべてのサンプルを分類できるように葉を茂らせていくと、一番木は深くなります。そしてその時の Tree Score を最小にする α は、0 です。それでもってその時の不純度は当然 0 です。なので、alpha=0 の時は impurity=0 となっています。

この状態から1個ノードを切ることを考えます。1個ノードを切ると、Tree Score の前半部分の不純度は増加してしまうので、alpha の値が 0 のままではいけません。ノードを切る前と切った後で差が小さくなるようにalpha の値を大きくして調整します。

ということなので、alpha が大きくするとノードの数を減らせる、木を浅くできる、という関係性にあります。

そのあたりをプロットして確認します。

では、このようにして様々な深さにしたときの最適な alpha の値がわかったものの、結局どれを使えばいいの?と疑問に思います。これは、それぞれの alpha の値を設定したときの検証データの正解率等のスコアを見て判断します。

ということで、今回は alpha = 0.011ちょっとくらいにしたときが最も検証データの正解率が高くなるということがわかりましたので、ccp_alpha 引数にはその値を入れてあげるとよい、となります。

それでもって、alpha を設定していないときと比較して、訓練データと検証データの正解率の乖離が縮まり、過学習が抑えられていることが確認できます。

 

参考

 

作ってわかる!アンサンブル学習アルゴリズム入門

Decision Tree-Pruning-Cost Complexity Method

scikit-learn Post pruning decision trees with cost complexity pruning

 

最後まで読んでいただきありがとうございました。