scikit.learn手法徹底比較！ 決定木編

機械学習 scikit Python

今回は決定木を用いて手書き文字データの分類を行う.

決定木の詳細はあらゆる所で解説されているので適当に調べて欲しい. このPDFを参考にしたけど, いい資料かは微妙.
決定木は各節に質問が, 葉にクラスラベルが結び付けられている木（データ構造の木）である. 各節では入力ベクトルのある次元の値に関する質問があり(ex. 入力ベクトルの１次元目は5以上か？), 新たなデータを分類する際は, その質問に対する答えによって, データはその節の左右に振り分けられる. それを再帰的に繰り返すと, データは各葉に振り分けられ, そのデータのクラスラベルは, 葉に割り当てられたクラスラベルになる.

学習段階では, その木の形と節に割り当てる質問を探索する. どのような質問がいいかは, その質問によるデータ集合の不純度(Impurity)の変化によって判断する. 不純度は確率変数の分布に対して割り当てられる量である. k個の値を取る確率変数の確率分布をとすると, 不純度は性質として

  • はとなるような確率分布において最小になる
  • は全てのに対してとなるような確率分布において最大になる

を持つ. つまり確率が偏る程, 不純度は小さい値となり, 確率が均等になる程, 不純度は大きな値となる. 不純度として使える関数はいくつか種類があるが, エントロピーが最も有名だろう.

訓練集合中で, クラスラベルの各値がどの程度出現するかを確率分布によって表現することができる. 質問前の全データ集合で定義される確率分布の不純度と, 質問後に二つに別れたデータ集合, それぞれの不純度を平均したものとを比較し, 最も不純度が減少するような質問が望ましい. なぜなら, 不純度が小さなデータ集合は同じクラスラベルのものを多く含んでおり, そのようなデータ集合を生み出す質問はそのクラスを抽出する能力が高いと考えられるからだ.

このようにして訓練集合全体を質問の連続によって再帰的に分類していき, 葉に達するとその葉に属する訓練データから, その葉に結びつけるクラスラベルを決定する.

sklearnにおける決定木

さて, 手法の説明はこのぐらいにしてscikit.learnにおける決定木について述べる. scikit.learnではDecisionTreeClassifierを用いて決定木による分類を行う. 分類性能を左右するパラメーターは

  • criterion : 不純度としてどのような関数を使うか. entropy(エントロピー)とgini(ジニ係数)がある.
  • max_depth : 決定木を構成する際の, 決定木の深さの上限
  • min_split : データを分割しながら決定木を構成する際, 節に割り当てられたデータ数がmin_split以下になるとそれ以上分割しない

max_depthとmin_splitはオーバーフィッティングを防ぐために設定する. あまりにデータ数わりあての小さい葉を認めると, ノイズに弱くなりやすいらしい.

実験では各criterion(entropy, gini)ごとに, max_depthを[5,10,20,40,NoLimit]から, min_splitを[1,5,10,20,40]から5-foldクロスバリデーションで最適なパラメーターに設定し, 性能を計測した.

criterion=entropyの場合

データ数 正答率 学習時間(sec) 平均予測時間(msec)
1000 0.6624 0.5122 0.00187
3000 0.7466 1.6600 0.00106
5000 0.7817 2.7806 0.00202
10000 0.8079 5.5169 0.00199
20000 0.8412 10.7413 0.00169

criterion=giniの場合

データ数 正答率 学習時間(sec) 平均予測時間(msec)
1000 0.6924 0.1841 0.00188
3000 0.7362 0.7163 0.00108
5000 0.7729 1.2658 0.00203
10000 0.8033 2.6406 0.00204
20000 0.8293 6.9938 0.00175

まず, 正答率に着目すると概ねentropyの方が少し高いがこの程度では差があると言えるか怪しい. また, データ数が増えるに従って正答率は上昇し続けているので, もっとデータ数を増やすと更なる性能上昇が見込めそう.

学習時間はデータ数に対して線形で増加するようだ. giniの方が一貫して低く, 計算コストが低いことが伺える. 一方, 平均予測時間はデータ数に関係なくわりと早い. そして当たり前だがcriterionとはあまり関係がない.

次にクロスバリデーションの感想. このデータではmin_split=1, max_depth=NoLimitという全くオーバーフィッティング対策をしないセッティングでも性能の劣化は生じなかった. 一方, max_depth=5としたときは大きな性能の劣化が生じた. 計算時間もあまりパラメーターに依存しなかったが, max_depth=5のときは少し早かった. criterion=entropy, N=10000のときのクロスバリデーション結果を記載しておく.

分類性能

min_split＼max_depth 5 10 20 40
1 0.6855 0.8058 0.8029 0.8029
5 0.6855 0.8041 0.8018 0.8018
10 0.6855 0.8041 0.8027 0.8027
20 0.6855 0.8003 0.7993 0.7993
40 0.6855 0.7894 0.7881 0.7881

計算時間

min_split＼max_depth 5 10 20 40
1 4.15 6.23 6.27 6.33
5 4.11 6.05 6.31 6.32
10 4.05 5.87 6.18 6.12
20 3.91 5.92 6.05 6.07
40 4.02 5.77 5.87 6.00

その他のパラメーター

ここまでで触れていないDecisionTreeClassifierのいくつかのパラメーターについて説明する.

  • max_features : どのような質問がいいか探索する際に, 入力ベクトルの各次元ごとに質問を試し, 不純度の減少度を比較するのだが, 全部の次元で試すのは計算コストがかかるので, ランダムにmax_features個だけ試す
  • min_density : 用いるデータ数の割合が, min_densityより小さくなった場合, データのコピーが発生する. その代わり, maskによる除外サンプルの計算が不要になるので計算速度は速くなる
  • compute_importances : 入力ベクトルの各次元がどの程度エラーの削減に寄与したかを計算するかどうか（あまりちゃんと調べていない）

max_featuresは例えば"sqrt"に設定すると, sqrt(次元数)個の次元の中から, 質問するのに最適な次元を選択する. この設定を試してみたところデータ数1万, criterion=entropyで分類性能が76.2%と大きく劣化した. これは考えてみれば当たり前で, この画像データの場合, 情報をあまり含んでいない次元（隅の方とか）が存在するためと思われる.

min_densityは上の説明だけではわかりづらい. コードを読めば一目瞭然である.

if n_node_samples / X.shape[0] <= min_density:
  X = X[sample_mask]
  sample_mask = np.ones((X.shape[0],), dtype=np.bool)

sklearnのDecisionTreeの実装では, 現在の分岐に関わる要素を取り出すのにsample_mask変数を用いて, 必要になった際にその都度取り出すことでメモリコピーを防いでいる. しかし, これは毎回データを取り出すためにオーバーヘッドが生じるため, メモリ使用量とそのオーバーヘッドのトレードオフを制御するのがmin_densityである.

上のコードでは, Xは入力ベクトル全体の集合なのだが, 入力ベクトルの個数中, n_node_samples(今回の分岐に関わるデータ数)の割合がmin_density以下の場合, sample_maskでデータを取り出すのを辞め, 現在使っているデータをコピーし入力ベクトル全体とみなすことで, それ以降の取り出しの手間を省いている.

実験としてmin_density=1.0, つまり毎回コピーするようにしてみたが, このデータでは１割程度の性能改善にしかならなかった.

おまけ実験

公式ヘルプには「次元削減手法を試してみろ」とあるので, 次元削減手法として確率的PCA(主成分分析)と, 入力ベクトルの各次元ごとにラベルとの関連度(本当はちょっと違うが)を調べ上位のもののみを残すSelectKBestを用いて実験を行なってみた. なお, criteria=entropy, データ数1万とする.

まず, PCAで次元削減を行った. 結果は以下の表である. 次元削減時間はPCAにかかった時間である. またoriginalは, 次元削減を行わない際の結果である.

次元数 正答率 次元削減時間 学習時間(sec) 平均予測時間(msec)
10 0.764 22.06 0.68 0.00023
30 0.781 22.30 1.93 0.00025
50 0.779 22.52 3.20 0.00027
100 0.772 23.08 6.39 0.00033
200 0.770 24.26 12.84 0.00068
original(784) 0.808 0.00 5.52 0.00200

PCAによる次元削減によって正答率は残念ながら大きく減少してしまう. 次元削減時間も非常に大きく, 計算量の削減にも寄与しない.

次元削減時間は削減後の次元数にほとんど依存しない. 一方, 学習時間は次元数に対して線形となる. そして, 次元数200のときは次元削減を行わない場合よりも学習時間が大きくなってしまう. 決定木の実装詳細を知らないので原因は不明であるが, 元のデータはスパースなのがPCAによってスパースでなくなるのが学習時間を延ばしていると推測している.

次に, SelectKBestで次元削減を行った. PCAは各特徴(次元)の線形結合を新たな特徴として用いることで次元削減を行うが, こちらは一部の特徴のみを使うことで次元削減を行う.

次が次元削減を行うコードである.

transformer = feature_selection.SelectKBest(feature_selection.f_classif, k=feature_components)
transformer.fit(datas, labels)
datas = transformer.transform(datas)

feature_componentsに削減後の次元数を与える. 今回の場合, ここに50などを指定しても次元数は274になってしまう. これは, 同じぐらい重要な特徴は全部取り込んでしまう実装になっているためである.

次元300で試した結果が次の表である.

次元数 正答率 次元削減時間 学習時間(sec) 平均予測時間(msec)
300 0.812 0.410 3.403 0.00092
original 0.808 0.00 5.52 0.00200

正答率を維持したまま次元削減時間, 学習時間をあわせても時間が短縮されており, 次元削減として有効に働いていることが分かる.

まとめ

やはりSVMなどに比べると性能が低い. ただ, K近傍法に比べて性能が大きく劣るのは意外だった. 決定木とK近傍法の対比としてこちらの資料では

  • K近傍法は領域を区切るときに, 入力した値のみを問題にしている. 一方で決定木はラベルを考慮している
  • K近傍法は全領域において同じkを用いている. これは領域によって適した値が変わるはずである. 一方, 決定木は領域の区切り方は場所によって様々なサイズを取りうる

としている. これらの利点を活かすにはデータ数が不足していたのかもしれない.

補足情報として, sklearnでは, 決定木にpruning(枝かり)の機能がない. これは, 学習データの一部をよけておき, それぞれの節の分岐が性能向上に寄与するかどうかをそのデータでチェックし, 結果によってはその節を取り除くことで, 過学習を防ぐ枠組みである. これを用いるとおそらく, そこまでmin_splitなどを気にする必要がなくなるため, 結構不便かも知れない.