統計ER

統計ソフトRの使い方を中心に、統計解析方法の解説をするブログ。ありそうでなかなか見つからないサンプルサイズ計算などニッチな方法について紹介しています。

決定木の剪定 Cost-Complexity Pruningとは?

ブログランキングに参加しています。
まずはぽちぽちっとお願いします。
↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓
にほんブログ村 科学ブログ 数学へ

庭師の仕事ではないが、決定木には剪定(せんてい)という過程がある。

剪定とは何か?

簡単に紹介。

 

 

完璧に分類した決定木は弱点が?

あるデータセットから、決定木を作ったとする。

決定木は、大きく茂らせれば茂らせるほど、きれいに分岐して、分類してくれる。

しかしながら、機械学習の観点から言うと、あまりにきれいに分類してしまうのは好ましくない。

なぜなら、完璧にデータセットを分類できても、ほかのデータセットで試してみると、うまく分類できないから。

これを過学習 overfittingという。

Overfittingした決定木は、汎用性がなく応用が利かない。

 

使える決定木を作るには?

汎用性を持たせて、使える決定木にするために、「剪定 pruning」を行う。

複雑さとあてはまりを犠牲にして、overfittingを避け、汎用性を持たせるのが剪定。

剪定 pruning にはいくつかあるが、代表的なものがcost-complexity pruning。

決定木は、大きくて複雑であればあるほど、誤分類をなくすことができる。

しかし、大きくて複雑すぎるとoverfittingのリスクがある。

この複雑性に罰則をつけたのが、cost-complexity pruning。

 \alphaで表すcomplex parameterを導入する。

 \alpha \times 葉っぱ(ノード)の数(決定木のサイズ)を罰則にする。

 \alphaは、「剪定した決定木の誤分類(大きくなる)と剪定する前の決定木の誤分類(小さい)の差」と「決定木のサイズ - 1」の比。

汎用性高く、サイズは最小限なんだけど、誤分類も最小限のいいところどりの決定木を作ろうという発想。

 

まとめ

きれいに分類できる決定木はoverfittingという弱点がある。

新しいデータで予測する性能が落ちる。

Overfittingを避けるために剪定 pruningがある。

剪定をすることで汎用性がある「使える」決定木が作れる。