１. 決定木
樹木モデルによる分類木(決定木)は、計算の速さ、結果の読みやすさ、説明のしやすさなどから多くの分野で応用されている。
決定木は多くのアルゴリズムが提案されている。WEKAには、10種類の樹木に関するアルゴリズムが実装されている。しかし、その中ではデータ形式に特化したものもある。データのへの制約が少ないのはJ48、NBTree、RandomForest、RandomTree、REPTreeなどである。
先月号で、すでに説明したとおり、J48はC4.5のWEKAバージョンである。
NBTreeは、ナイーブベイズの分類器(naive
Bayes classifiers)のアプローチで決定木を生成するアルゴリズムで、Ron Kohavi によって提案された(参考文献[4])。
RandomForestは、ブートストラップというリサンプリングの方法でサブデータを作成し、それぞれのサブデータセットの決定木を組み合わせる方法で、Breimanにより提案されている[2]。WEKAではtreeのカテゴリーに分類しているが、C4.5やCARTのような樹木モデルとは性質が異なる。RandomForestは、後述の集団学習アルゴリズムの一種であると考えるのが適切であろう。
RandomTreeは、説明変数をランダムに、分岐に用いるアルゴリズムである。よって、分岐に用いる変数は重複して用いられ、C4.5やCARTなどより茂る木を生成するのが特徴である。
REPTreeは、ゲインと分散(gain/variance
)の情報を用いて決定・回帰木を構築するアルゴリズムである。C4.5との大きい違いは木の剪定方法で、精度より計算の速さが取り柄である。
多くの決定木の中で、どの決定木の精度が良いかに関しては、幾つかの実証方法があるが、最も理解しやすいのは識別・判別率(あるいは誤り率)である。
本稿では、データマイニングのベンチマークとして使用されているUCIデータを用いて、識別の誤り率で精度を評価することにする。
UCIは、カリフォニア大学アーバイン校(University of California, Irvine)の知識発見の研究者らが蓄積・公開しているデータアーカイブである。WEKA用のUCIデータは次のサイトからダウンロードすることができる。
http://prdownloads.sourceforge.net/weka/datasets-UCI.jar
WEKA用のUCIには37セットのデータがある。その中にはデータのサイズが大きいものもあり、分類器によっては、メモリが500MB以下では計算ができないものもあるので、ここで用いるデータは表1に示すものに限定した。
また、分類器の精度の評価は、多重交差確認法(n=10)の誤り率を用いることにする。
表１にJ48、NBTree、RandomForest、RandomTree、REPTreeの誤り率と比率を示す。
誤り率の平均値が小さいからと言って、その分類器の精度が良いとは限らない。と言うのは、異なるデータセットにおける、誤りの率の差が大きいからである。分類器の精度の比較には、ある分類器を基準とした比率もひとつの指標となる。表１の比率は、J48を基準としている。この比率の値が1より小さいと、誤り率がJ48より低く、その分類器の精度がJ48より良いと評価できる。
表1から分かるように、平均の誤り率が最も低いのは、RandomForest、NBTree、J48の順であり、J48を基準とした比率では、RandomForest、J48、NBTreeの順である。
よって、精度が最も良いのはRandomForestで、J48とNBTreeは大きい差が見られない。
参考のため、各データセットの中で誤り率が少ない順のランキングをまとめたものを表2に示す。例えば、表2の2行目2列目の10はJ48の誤り率が最も低いケースが10回であることである。表2からも分かるように、RandomForestの誤り率が最も低いケースが15で、最も多い。
２. 集団学習
決定木は、高精度の分類器ではないが、計算の速さやその結果の読みやすさに長所を持っている。
日本語では「三人寄れば文殊の知恵」、中国語では「三個臭皮匠、賽過一個諸葛亮」、英語では“Two
heads are better than one．”という熟語がある。これらは、凡人でも多数集まって考えをまとめれば、何とか良い知恵が浮かぶということの意味で用いられている。
このような人間の日常の知恵がデータ解析のアルゴリズムとして提案されている集団学習という方法がある。
集団学習(ensemble
learning)は、決して精度が高くない複数の結果を統合・組み合わせることで精度を向上させるために提案された機会学習方法である。複数の結果の統合・組み合わせの方法としては、分類の問題では多数決、数値の予測の問題では平均が多く用いられている。
集団学習では、異なる重み、あるいは異なるサンプルから単純なモデルを複数作成し、これらを何らかの方法で組み合わせることで、精度と汎化力を両立するモデルを構築する。決定木と関わる最も知られている集団学習アルゴリズムはバッギング(bagging)、ブースティング(boosting)、ランダム森(random forest)である。
(1) バッギング
バッギング(bagging)のbaggingは、bootstrap
aggregatingの頭の文字列を組み合わせた造語である。バッギングは、与えられたデータセットから、ブートストラップ法による複数の学習データセットを作成し、そのデータを用いて作成した分類器を統合・組み合わせる。ブートストラップサンプルはそれぞれ独立で、学習は並列に行うことができる(参考文献[1])。
ブートストラップサンプルは、与えられたデータの経験分布とその推定量に基づいたリサンプリングにより得られたサンプルである。
(2) ブースティング
ブースティング(boosting)は、与えた学習データを用いて学習を行い、その学習結果を踏まえて逐次に重みの調整を繰り返すことで複数の学習結果を求め、その結果を統合・組み合わせ、精度を向上させる方法である(参考文献[3])。ブースティングの中で最も広く知られているのはAdaBoostというアルゴリズムである。
(3) ランダム森
ランダム森(random forest:
RF)は、Baggingの提案者Breimanにより、今世紀の初頭に提案された新しいアルゴリズムである(参考文献[2])。
RFのアルゴリズムを次に示す。
１.
与えられたデータセットからN組のブートストラップサンプルを作成する。
２.
各々のブートストラップサンプルデータを用いて未剪定の最大の決定・回帰木を作成する。ただし、分岐のノードはランダムサンプリングされた変数の中の最善のものを用いる。
３.
全ての結果を統合・組み合わせ(回帰の問題では平均、分類の問題では多数決)、新しい予測・分類器を構築する。
図1 RFのアルゴリズムイメージ
BaggingとRFの大きい違いは、Baggingは全ての変数用いるが、RFでは変数をランダムサンプリングしたサブセットを用いることができるので、高次元データの計算が容易であるである。
ランダムサンプリングする変数の数Mはユーザが自由に設定することができる。Breimanは、Mは変数の数の正の平方根をと取ることを勧めている。
RFは、多くの工夫が施され、次のような長所を持っていると言われている。
主な長所：
² 精度が高い。
² 大きいデータに効率的に作動する。何百、何千の変数でもよい。
² 分類に用いる変数の重要度を推定する。
² 欠損値の推測および多くの欠損値を持つデータの正確さが維持するのに有効である。
² 分類問題における各群の個体数がアンバランスであるデータにおいてもエラーのバランスが保たれる。
² 学習データから生成されたRFは保存して、新たなデータに適応することができる。
² 分類と変数の関係に関する情報を計算する。
² 群間の近似の程度が計算できる。
² 群の情報がないデータにも適応できる。
３．集団学習の精度比較
本項では、決定木に集団学習方法を組み合わせた精度について比較を行うことにする。ここでも前項と同じくUCIのデータセットを用いることにする。ただし、表1に用いたデータの中で、メモリ不足で計算不能なものは除いた。
