キャンセル
次の結果を表示 
次の代わりに検索 
もしかして: 
AI Experience Japan l バーチャルイベント l 2020年7月14日(火) 登録受付中

決定木のABC

Highlighted
データサイエンティスト
データサイエンティスト

DataRobotを使用したことがある読者の方に中には、XGBoostLightGBMで高精度なモデルを構築できた経験がある方が多いと思います。本資料は、pdfで無料公開にもなっているAn introduction to statistical learningをもとに、決定木の基礎についてまとめたものです。ジニ係数やエントロピーとは何か、そしてBaggingBoostingがなぜ必要になるのかについてまとめています。各章のタイトルはあえてAn introduction to statistical learningのものを使用しております。章によっては簡単にまとめるだけにとどまったり、分かりやすさのためにAn introduction to statistical learningに記載していない追加情報も掲載しております。

 

8.1 The Basics of Decision Trees

まず、回帰問題と分類問題に対して、それぞれ決定木がどのようにアプローチしていくかに分けて解説していきます。

8.1.1 Regression Trees (回帰問題)

 

Kei_0-1587709271794.png

Kei_1-1587709282537.png

決定木は、図のように分岐をいくつか使用して予測を行う手法です。分岐された後のR1, R2, R3はterminal nodes(ノード)またはleaves()と呼ばれています。

Prediction via Stratification of the Feature Space

R1,R2は下記の評価関数(RSS:残差平方和)が最小になるように決定するのが基本的な考え方です。各ノードに対してのRSSの和をとっているところだけが異なって見えますが、重回帰モデルと考え方は同じですね。

Kei_2-1587709292880.png

しかしながら、全ての考えられる分割方法を試すのは現実的ではないので、top-down, greedey approach (トップダウンの貪欲法)という方法が採用されます。これはrecursive binary splittingとも呼ばれています。なぜ"トップダウン""貪欲"かというと、ツリーの最も上の階層(トップ)から、その階層の中で最もいい分け方を決めていくからです(貪欲に目の前の利益だけを考えていきます)1つ上の階層に戻って、分け方を決め直すことはしません。最限なく分けていくことができるので、例えば1つのノード()に含まれる最小の数が5となるようにするといったルールが適用されます。

Tree Pruning

 

ノードの数を増やすと過学習の問題に陥るため、ノードの数が増えると評価関数にペナルティを課す方法が1つの有効な手段です。

Kei_3-1587709312379.png

上式はlassoの式と似ていますね。α|T|を使用することで、ツリーの複雑性を抑制します。cost complexity pruningweakest link pruning と呼ばれる方法です。

8.1.2 Classification Trees

分類問題の場合も基本的な考え方は同じですが、評価関数は分類問題用に変更する必要があります。単純なclassification erro rate(正解率)を使用すると、単純に各ノードの予測値は常に多くのサンプルをもつクラスに割り当ててしまえばいいことになってしまいます。少数のサンプルのデータに対してもしっかり対応してあげることが重要になってきます。分割する際の評価関数としては、それらを考慮したGini係数やエントロピーが一般的に使用されます。An introduction to statistical learningの説明は少し高度であったため、少し噛み砕いて説明していきます。

ジニ係数

ある領域Rmでのジニ係数は、クラス数をKとした際に下記のように定義されます。

 

Kei_8-1587709146886.png

式をいきなり見てもわからないと思うので、少しずつ紐解いていきます。まず、どういった分け方が好ましいかを考えていきましょう。下図のような2つのケースがあった際に、各ノードが目指すべき状態はどちらでしょうか。ノードの中の予測値は全て同じになるため、パターンAを全て青と予測すると、オレンジと赤のサンプルは間違って青と判定されてしまいます。一方右のケースだと全て正しく青と予測できるので、右のようなノードになることを目指していきます。

Kei_7-1587709126590.png

 

 

パターンAは色々なものが混ざっているように見えます。混ざっていることが問題になりそうなので、数学的にその不純度(混ざり度)を定義していきたいと思います。まず、他のクラス()が混ざっていても、そのサンプルが多くなければそれほど問題にはならなそうです。パターンAの場合、オレンジより赤の方が邪魔にならなそうなことは感覚的にわかると思います。ですので、下記のようにまず各クラス()の割合(確率)を計算します。

 

Kei_6-1587709102262.png

次に各クラスの気持ちになって考えてみましょう。青にとっては残りの4個が邪魔であり、オレンジにとっては7個、赤に至っては9個も邪魔なものが存在することになります。自分のクラス以外のサンプルがどれほどあるかも重要になってきそうなので、その割合(確率)を求めていきます。その確率は自分以外の確率となるので、先ほどの確率を利用するとそれぞれ、

Kei_1-1587708875310.png

と計算することができます。算出した2種類の確率を同時に考えた値がまさしくジニ係数です。今回のケースの場合、ジニ係数の式は下記のようになります。

Kei_2-1587708973555.png

パターンAの場合、ジニ係数は

Kei_3-1587708989030.png

となり、パターンBの場合のジニ係数は、

Kei_5-1587709036673.png

と計算されます。ジニ係数は、完全に純粋な場合は0となるような定義になっています。簡便すぎる例で説明しましたが、ジニ係数の気持ちは不純度を定式化したところにあります。ジニ係数が大きいほど不純度が高くなりますので、決定木の分類問題でジニ係数を使用する場合は、全体のジニ係数小さくなるように分割していきます。具体的には、子となるノードのジニ係数の平均が(各ノードのサンプル数で荷重平均をとります)が、親のジニ係数よりもできるだけ小さくなるような分割を考えます。

 

Kei_1-1587709419134.png

上の図の例でいくと、Ipが親のジニ係数で、Kei_2-1587709453478.pngが子ノードの全体のジニ係数にあたります。

Kei_0-1587709396858.png

が最大となるような分割を考えていくことで、不純度の小さいノードを作成してしていくことができます。この差分のことをgain (情報利得)と呼びます。「gainが最大になるように分割を決める」と書かれた資料が多くあるかと思いますが、その説明がまさしくここにあたります。

エントロピー

ある領域Rmでのジニ係数は、クラス数をKとした際に下記のように定義されます。

 

Kei_3-1587709525951.png

ジニ係数と似ていますね。対数は1をとると0になるので(1-p)と同じ意味合いを持っています。ですので、実際数学的にジニ係数と似たような振る舞いをします。なお、情報理論で出てくるエントロピーと同じ定義となっています。

8.1.3 Trees Versus Linear Models

決定木とシンプルな重回帰モデルの比較ですが、どちらが優れているということはなく、データの性質によってモデルの予測性能が異なります。

  • もし下図の上段のようにデータが線形に従うような場合、決定木ではその線形性を多くのノードで表現する必要があるので、シンプルな重回帰モデルの方が性能がよくなります。
  • 逆に下図の下段のようなケースだと、分割して予測を行う決定木の方が性能が高くなります。

Kei_4-1587709556392.png

8.2 Bagging, Random Forests, Boosting

8.2.1 Bagging

分割をすることで推定される予測値は、分割のされ方によって値が大きく変わる可能性があります。推定される予測値が安定しない(分散が大きい)と汎化性能が高くならないので、分散を抑える工夫が必要となります。そこで使用されるのが、BootstrapBaggingです。これらの手法は決定木だけに使用されるものではなく、一般的に多くの統計的手法で使用されています。

予測の分散を小さくする方法(安定した予測値を得る方法)として、一つのデータセットからの予測値を使用するのではなく、いくつかのデータセットの予測値の平均値を使用する方法があります。数学的に表現すると、分散がσであるデータセットがN個あるとすると、N個のデータセットの平均値の分散はσ/Nとなり、確かに分散が小さくなることが確認できます。

実際には、異なるデータセットを用意することはできないので、1つのデータセットからリサンプリングを繰り返して、いくつかのデータセットを作成します(あるサンプルが複数のサブセットに入ることを許しています)。これがBootstrapです。そして、作成したいくつかのサブセットでそれぞれモデルを作成し、そこから得られた予測値を平均する方法をBaggingと言います。

Kei_5-1587709614352.png

Variable Importance Measures

多くのケースでモデルには解釈可能性が求められます。決定木では、ある特徴量を用いた分割でどれだけRSSが減少したか、またGini係数(or エントロピー)が減少したかを各特徴量毎に積算することで、その特徴量がどれほど重要かを理解することができます。

Kei_6-1587709642222.png

最も影響度が大きい特徴量を100とした際に、他の特徴量の重要度を示したグラフが上の図になります。DataRobotではインサイトから確認することができます(特徴量のインパクトと似ていますが、定義が異なることに注意してください)

8.2.2 Random Forests

ランダムフォレストはBaggingと非常に類似した手法です。Baggingの問題点を考えてみましょう。Baggingではデータセットをいくつかのサブセットに分割し、複数の多様なモデルを作成する方法でしたが、もし非常に目的変数の説明力の高い特徴量が存在した場合、どのモデルも似たような予測値となってしまい、Baggingの威力が発揮されません。その問題を解決するために、各サブセットで全ての特徴量を使用せず、さらにいくつかの特徴量だけを使用する手法がRandom Forestsです。一般に各サブセットで使用する特徴量の数は全特徴量の数の平方根になるように設定されます(Rの関数だと分類は平方根、回帰であれば3分の1の値が使用されるなどの違いがあるので、使用する関数のデフォルト値を確認してみて下さい)

 

8.2.3 Boosting

予測を改善する方法として、Boostingという方法もあります。BoostingBaggingと同様に決定木だけに使用されるものではなく、一般的に多くの統計的手法で使用されています。Baggingは複数のモデルを並列に作成して平均する手法でしたが、Boostingは複数のモデルを直列に作成していく方法です。Boostingでは、まずシンプルなモデルを作成して予測値を算出します。次にその予測値と実測値の誤差を作成するモデルを作成します。予測値と実測値の誤差を予測するモデルをどんどん作成していく方法がBoostingです。下記がBoostingのアルゴリズムとなります。

 

Kei_7-1587709659671.png

誤差を予測するモデルをどんどん足し上げていくイメージなのですが、予測値をそのまま足すと値が実測値周辺で大きくブレる可能性があるので、予測値にλ(<1)をかけて少しずつ足していくイメージです。直列につなげる決定木の数B、先ほどの減衰率λ、また各モデルの分割数dをパラメータとして設定する必要があります。

 

終わりに

この資料を読んで一つ決定木の理解が深くなりましたら幸いです。もっと詳しく知りたい方は是非An introduction to statistical learningを読んでみて下さい!

2件の返信2
Highlighted
リニアアクチュエータ

@Kei さん

ありがとうございます。勉強になりました。

最近とあるところで、アルゴリズム毎の決定境界の違いを可視化した図を作ったので、
参考に添付させて頂きます。

アルゴリズムの数式が理解できなくても、雰囲気としてアルゴリズムの特性を理解
できる点で、決定境界の可視化は有益だし、好きですねw

どういった予測の特性(入力の変化量に対する出力の反応性、外挿の考慮等)を
求めるかを検討する際にも、こういった図は、便利だな。と思います。

      決定木(lightGBM) Logistic  Regression
mc_db.pnglr.png
木的な条件分岐を感じさせる
ギザギザした感じ

線形アルゴリズムだけに、
境界も線ですね。

 

Highlighted
データサイエンティスト
データサイエンティスト

@ShinichiroOhno -san,

ありがとうございます!

 

境界面のイメージがあると、

事前に変数間の関係が物理法則や社会ルールで決まっている場合、

変数間の関係を意識して、適切な境界面を作ることができますし、

 

またコロナに影響されるこのご時世、

外挿でどう振る舞うかもしっかりイメージを持っておくことが非常に重要になりますよね。

 

イメージできるものはしっかりイメージを持つことが大事ですね!