決定木アルゴリズムを実装してみる
目次
はじめに
前回までで決定木アルゴリズムがわかったので、ここでは実際にコーディングして、学習結果をscikit-learnの結果と比較してみたいと思います。
学習した決定木をどのように保持しようか悩んで色々検索していたら、自作した決定木のコードを公開しているサイトを発見したので参考にさせて頂きました。
参考にさせて頂いたサイトでは、再帰呼び出しを使って学習した決定木を保存していて、非常にシンプルでカッコよかったので私も真似してみることにしました。やっぱり人の書いたコードを読むと非常に勉強になりますね。
再帰呼び出し
自分自身を実行する関数を再帰関数といい、再帰関数内の自分自身の実行箇所を再帰呼び出しと言います。
以下再帰関数の例です。再帰の深さをカウントしてプリントします。
自分自身を呼び続けるので、どこかでif文で抜けてやらないと無限ループになります。
余談ですがDAOショックでもハッカーが使った手法で、再帰呼び出しで子DAOをスプリットしまくったとか。。お陰で大損こいちゃいました。忌まわしい記憶です。
決定木で実装する時は、ノードクラスを作ってやり、自分の子ノードを格納するメンバ変数を持たせ、自分を分割して子ノードを生成するメンバ関数を再帰関数化してやればいいです。
自分で書いててもチョット何言ってるかわからないので、絵で描くと以下のようなイメージです。
自分の子ノードとなるメンバ変数が、更に孫ノードとなるメンバ変数を持ち、更に曽孫ノードとなるメンバ変数を持ち、、の様に永遠に子ノードを生成します。
以下は上記のチャート図をそのままコードに落としたものです。再帰の深さが3になったら再帰ループを抜ける様にしています。
決定木のチャート図
決定木でどのようにトレーニングサンプルが分割されているかを確認するには、チャート図にしてやるとよくわかります。
scikit-learnの決定木インスタンスをGraphVizというツールを使ってチャート図で表示する方法があるみたいです。
以下のサイトを参考にさせていただきました。
Windowsのインストーラgraphviz-2.38.msiです。
インストーラーがパスを設定してくれないので、インストール後は自分でパスを設定(環境変数PathにC:\Program Files (x86)\Graphviz2.38\binを追加)しておきます。
LinuxやMacでも使えるみたいですね。試してないですがやることはほぼ一緒だと思います。
決定木インスタンスは一旦dotというテキスト形式に変換されるみたいなので、それをチャート図形式に変換するPythonモジュールpydotplusも必要です。pipでインストールしておきます。
pip install -U pydotplus
恐らくpydotplusモジュールの中で、GraphVizを実行していると思われます。
決定木で使われる乱数
scikit-learnで決定木学習を実施すると、同じトレーニングサンプルで学習しているにもかかわらず、学習結果が異なることがあります。
要するにどこかで乱数を使っているわけですが、どこで使うのかずっと不思議に思っていました。
調べてみたところ、どうやら各特徴量で情報利得を計算する時に使われているみたいです。
前回のアヤメの例で、4種類ある特徴量のそれぞれで情報利得が最大となる質問を調べてみた時に、petal lengthとpetal widthで最大情報利得が同じになってしまい、どちらの特徴量でトレーニングサンプルを分割するべきか迷ってしまったのですが、scikit-learnではここでランダム選択をするみたいです。
まあ理にかなっていますね。自作スクリプトにはこちらも考慮するようにしました。
特徴量の重要度
決定木では、情報利得が最大になるようにノードを分割していきますが、情報利得とはある特徴量でノードを分割した時に得られる情報量という意味なので、情報利得の大きさで分割する特徴量の重要度というものを考えることができます。
得られる情報量が多いほどその特徴量の重要度が高く、トレーニングサンプルをよりピュアに分けることができます。
反対に重要度が低い特徴量でノードを分割すると、子ノードの不純度は高いままなので学習が中々進みません。また、トレーニングサンプルに重要度が低い特徴量がある状態で最後まで決定木のノードを分割した場合、過学習に陥ってしまう可能性も高いです。
トレーニングサンプルの特徴量数が膨大で学習に時間がかかる場合は、前もって少ないトレーニングサンプルで学習を実施し、各特徴量の重要度を求めておくことで、重要度が低い特徴量をトレーニングサンプルから省くことができます。
scikit-learnでは、分割が発生したノードにおける情報利得をノード内のサンプル数で重み付けして、各特徴量ごとに全て足しこむことで、特徴量の重要度を算出しているようです。
以下、具体的に数式で表してやります。
今、決定木中で番目の特徴量
で分割が発生したノードの集合を
とします。
に含まれるノード
の中のトレーニングサンプルの個数を
とすると、
番目の特徴量
の重要度
は情報利得
を使って以下の式で表されます。
scikit-learnの決定木では特徴量の重要度は、デフォルト設定では正規化されており、feature_importances_という名前で決定木インスタンスのメンバ変数として格納されています。
トレーニングサンプル中の特徴量数をとすると、正規化された特徴量の重要度
は以下の式で計算されます。
こちらも自作スクリプトで考慮していきます。
自作スクリプト
例によってアヤメのデータを使って、自作版とscikit-leran版で学習結果を比較してみました。
アヤメのデータの70%を学習用、30%をテスト用に分けて、学習とテストを実施します。
簡単の為、特徴量はsepal lengthとpetal lengthの2つで実施しました。
以下のスクリプトを実行すると、自作版とscikit-leran版のそれぞれで学習後のテスト結果のスコアと特徴量の重要度を数値でプリントし、決定領域と決定木チャート図をpngファイルで出力します。
テスト結果のスコア比較
my decision tree score:0.933333333333 scikit-learn decision tree score:0.933333333333
93%と正答率が高く、自作版とscikit-learn版で一致してますね。いいですね。
main関数内の19、20行目で、決定木のMax深さmax_depthと乱数のシードrandom_stateを設定しています。(scikit-learnの決定木で指定する引数と変数名を合わせました。)
max_depth = Noneで最大までノードを分割します。scikit-learnではデフォルトでmax_depth = Noneになっており、インスタンス生成時に何も引数を指定しないとMaxまで子ノードを生成します。デフォルト設定では過学習だったんですね(それにしてはアヤメのテスト結果のスコアは高いですが)。。
random_state = 3としてますが、実は自作版とscikit-learn版で結果が一致するように選んでます。random_state = Noneにすると、乱数のシード自体がランダムに設定されるので毎回実行結果が異なります。scikit-learnのデフォルト設定はrandom_state = Noneです。
特徴量の重要度比較
自作スクリプトでは204行目のTreeAnalysisが特徴量の重要度算出クラスです。
my decision tree feature importance:
sepal length (cm) : 0.0557222081576
petal length (cm) : 0.944277791842
sklearn decision tree feature importance:
sepal length (cm) : 0.0557222081576
petal length (cm) : 0.944277791842
こちらも合ってますね。sepal lengthの重要度がpetal lengthに比べて随分ひくいですね。トレーニングサンプルからsepal lengthを省いて良いってことでしょうか？
特徴量がpetal length一つだけになってしまいますが本当に大丈夫でしょうか？後で確かめてみましょう。
決定領域比較
自作版の決定領域
scikit-learn版の決定領域
こちらも自作版とscikit-learn版でほぼ一致してますね。嬉しいですね。
決定木チャート図比較
自作版のチャート図
やはり、どのように分割されているかチャート図で確認したかったので自作版のチャート図作成頑張りました。(257行目のTreeStructureがチャート図作成クラスです。)
色はどう設定するかわからなかったので自作版は全部白です。
scikit-learn版のチャート図
深さ4番目以降の分割が微妙に違いますね。まあ最大情報利得がかぶった場合は、乱数で分割する特徴量を選択するのでこれくらいの違いは仕方ないですね。
重要度が低い特徴量をトレーニングサンプルから省いてみる
sepal lengthの重要度がpetal lengthに比べて随分ひくいので、トレーニングサンプルからsepal lengthを省いてpetal lengthのみで学習を実施してみました。
テスト結果のスコア比較
my decision tree score:0.911111111111 scikit-learn decision tree score:0.911111111111
特徴量が一つしかないのに正答率が91%もあります。本当に省いてよかったみたいです。
特徴量の重要度比較
my decision tree feature importance:
petal length (cm) : 1.0
sklearn decision tree feature importance:
petal length (cm) : 1.0
まあ、正規化されているので特徴量が一つしか無いときは、1.0以外取りようがありません。
決定領域比較
自作版の決定領域
scikit-learn版の決定領域
決定領域で確認すると納得の結果ですね。確かに省いて良さそうですね。
決定木チャート図比較
自作版のチャート図
scikit-learn版のチャート図
見事に一つの特徴量だけで決定木が出来上がっていますね。面白いですね。
