2018-02-10

決定木を実装せんと欲す

というか実装してみました。

https://gist.github.com/youchan/185c56328e4244f1aaa02017bd6d4897

【初・中級者向け】ランダムフォレストとアンサンブル学習 #2 - connpass

という勉強会というかセミナーがありまして、ランダムフォレストについて学んだので決定木の実装をしてみようと思いました。 (フォレストにしてみたいので、Kaggleあたりから程よい課題をみつけられたらやってみようかと思います。)

課題はセミナーのなかでもあつかったscikit-learnのこれ

学習データのirisはなんと、red-datasetsというgemでRubyから使いやすい形で提供されています。

結果、このように

Decision Tree

scikit-learnの結果となんだか違うぞー……

プログラムを見るとわかりますが、ツリーをつくるのに単純に平均情報量の大きいものを採用しています。(グリーディなアルゴリズムです)
単純にこのアルゴリズムでやるとなかなかリーフが決まらずに下図のような長大なツリーになってしまいます。

Over fitting

このような繰り返しを防ぐために枝刈りをしてしまいます。(56行目)

枝刈りをするほかにも、最大の深さを決めてその中で最適な解を探すようなアルゴリズムも考えられるでしょう。(深さの制約があれば線形計画法で解くこともできるでしょう。)
scikit-learnはそのようなアルゴリズムであろうことが予想されます。
このへんの詳しい資料を見つけられなかったのですがscikit-learnのコードを読むなりすれば参考になるでしょう。
今回はナイーブに実装してみたということでここらへんで。

前回のCKY法同様、ちょっと合間時間に実装できるような小さな問題をちょこちょこ解いて機械学習力をちょっとでも上げていこうかなと思ってます。
つぎは何やろうかなー?