決定木分析についてざっくりまとめ_理論編
概要
こんにちは、yoshimです。当エントリは「Machine Learning Advent Calendar 2017」の11日目のエントリです。
今回は教師あり学習の１手法である「決定木分析（decision tree）」をご紹介します。
目次
1.決定木分析とは
まず、決定木分析とはなんなのか、ということをざっくり説明しようと思います。 決定木分析は、「段階的にデータを分割していき、木のような分析結果を出力する」ものです。 言葉だけではイメージがつかないと思いますが、具体的には下記のような分析結果を出力します。
機械学習に興味がある方なら見たことがあるのではないでしょうか？ 決定木分析ではこの画像のように上からデータを分割していき、データを各クラスに分類していきます。 また、この画像を見ていただくとわかるかと思いますが、決定木分析は「分析結果の解釈が容易」という素晴らしい特徴を持っています。
下記は昨年弊社にて実施したアドベントカレンダーにて決定木分析について説明した記事になります。
本エントリーの説明でわかりづらい点があるようでしたらこちらもご参照ください。
決定木モデルを作る #alteryx #03 | Alteryx Advent Calendar 2016
2.特徴
「決定木分析」の概要の説明は以上にして、続いて決定木分析の特徴をご説明します。
A.解釈が容易
最初に見てもらったイメージの通り、処理結果が解釈しやすく妥当性を判断しやすい点が決定木分析の一番の強みです。 決定木分析を単独で実行する際は、そのモデルを利用してどうこうするというよりも、「データが分割されていく流れをなんとなく把握する」ことが目的となることが多いようです。 また、その他の機械学習モデルと比較すると処理内容についても比較的簡単に理解できます。 （深入りしなければ、です）
B.数値、カテゴリデータが混在していてもOK
説明変数には数値データ、カテゴリデータ等の様々なデータ型が利用可能です。 例えば、顧客の性別等のカテゴリデータや、購入金額等の数値データの両方をモデル作成時の説明変数として利用可能です。
C.必要な前処理が少ない
決定木分析では、「データを分割する指標」として特徴量を使うので、データの前処理（スケーリング等）に伴う負担がかなり軽減されます。
D.過剰適合しやすく汎化性能が低い
これはネガティブな特徴なのですが、決定木分析はどうしてもモデル作成時に利用したデータに対して「過剰適合」してしまいがちです。
なので、汎化性能の向上を目的とするなんらかの対策が必要となります。
（木の深さの設定、アンサンブル学習であるランダムフォレストや勾配ブースティング等のアルゴリズムを使う等）
E.「分類」にも「回帰」にも利用可能
今回のエントリーでは「分類」でご紹介しますが、目的変数を変えることで「回帰」もできます。 決定木分析は「分類」に使われる際は「分類木」、回帰に使われる時は「回帰木」と呼ばれます。
3.処理の流れ
続いて、処理の流れについてざっくり説明します。 出てくる言葉の意味については次節にて簡単に説明しますので、まずはざっくりと処理の流れを理解していきましょう。 決定木分析における処理の流れは、下記の通りです。
1.データを分割する基準を決定する
まずはデータを分割する基準を決定する必要があります。 ここでは、もっとも「綺麗にデータを分割できる」基準を選ぶことになります。 もっとも綺麗にデータを分割できるってどういうことだよ、という話ですがこれは例えばクラス分類だった場合は「クラスAはこっち、クラスBはこっち」といった具合にしっかり分割できるようにする、ということです。 例えば、会員100人分（男性50人、女性50人）のデータがあったとして、これを「男性50人」のノード、「女性50人」のノードの2つに分割できたら、それは綺麗にデータを分割できている、と言えます。
もう少し厳密に言うと、「情報利得」が最大となる基準を選択することとなります。 この「情報利得」を計算するためには、「不純度」という概念を考慮する必要があるのですが、この２つについてはこの後に説明します。
2.データを分割する
先ほど選択した基準に基づいてデータを分割します。 例えば、「会員の性別が男性かどうか」、「血中脂肪値が○以上かどうか」といった基準でデータを分割していきます。 データの分割は、決定木分析のアルゴリズムによって「２つに分割」、「２つ以上に分割」の2パターンに分かれます。
3.設定した基準になるまで、1,2を繰り返す
決定木分析では、「どれだけ深くまで分析を進めるのか」といったことを考慮する必要があります。 適度な深さで分析を止めないと分析に用いたデータに過剰に適合してしまう「オーバーフィッティング」という現象が発生してしまい汎化性能が低下してしまいます。
なので、あまり深くなりすぎる前に分析を止める（決定木分析では、これを「剪定」と呼びます）必要があるのですが、「どれだけ深くまで分析を進めるのか」を制御する方法がいくつか存在します。その方法についてもメジャーなものを後ほどご紹介します。
以上から、決定木分析をする際は「情報利得」、「不純度」、「剪定方法」という3つの要素を考慮する必要があることがわかります。 この後では、これらについて簡単に説明していこうと思います。
４.情報利得と不純度
まず、データを分割する基準を決定するために用いられる「情報利得」と「不純度」について説明いたします。 まずそれぞれ「大まかにどんな概念なのか」を説明し、その後に具体的な数式をご紹介します。
それぞれの概念は下記の通りです。
情報利得:分割の良さ（分割前の不純度 - 分割後の不純度）
不純度: どれだけごちゃごちゃしているか
これだとばっくりすぎるので、もう少し丁寧に説明します。
まず「情報利得」についてですが、これは「データ分割の前後を比較してどれだけ綺麗にデータを分割できたか」を数値化したものです。
例えば、会員100人分（男性50人、女性50人）のデータがあったとして、これをなんらかの基準に基づいて分割して「○○という特徴があるなら男性、○○という特徴があるなら女性」という風に分割したいとします。この時、「会員の居住都道府県が東京都か否か」といった基準でデータを分割した結果が、「男性20人、女性20人」、「男性30人、女性30人」といったノードに分割されたとします。この時、結局目的として分割には全く貢献していないため、「分割の良さ」は悪いと言えます。
一方、例えば「すた丼が好きかどうか」という基準でデータを分割した結果、「男性50人」、「女性50人」といったように綺麗に分割できたとしましょう。この場合は、「情報利得」はとても大きい値となります。
ちなみに、「情報利得」を数式化すると下記の通りです。 これは、ノードXを分割した結果、Y1,Y2のノードに分割された場合の情報利得についての計算式を言葉にしてみたものです。
(ノードXを分割したことによる情報利得) = (分割前の不純度) - (分割後の不純度)
(右辺) = (ノードXの不純度) - (ノードY1の割合) * (ノードY1の不純度) - (ノードY2の割合) * (ノードY2の不純度)
数式にすると下記の通りですね。 ちなみに、IG(X,Y1,Y2)はノードXをY1、Y2に分割することによる情報利得を、p()は各ノードの割合を、E()はそれぞれの不純度とします。 [latex] IG(X,Y1,Y2) = E(X) - (p(Y1)*E(Y1) + p(Y2)*E(Y2)) [/latex]
「情報利得」の概念については以上です。この「情報利得」は計算するためには上記の式の通り、「不純度」の理解が不可欠です。 なので、続いては「不純度」の説明をいたします。
「不純度」は「どれだけごちゃごちゃしているか」を数値化したものです。
例えば、会員100人分（男性50人、女性50人）のデータがあったとして、これだと複数のクラスのデータがそれぞれ同じ割合で存在しているので、とても不純な状態なので不純度は大きい値を取ります。逆に、これがなんらかの基準で分割されて「男性50人」、「女性50人」のノードに綺麗に分割された場合は、それぞれのノードは「純粋」な状態と呼ばれます。つまり不純度0です。
この例のように、データが完全に綺麗に分割されている状態では不純度は0になりますが、「1つのノードに複数のクラスのデータが、それぞれそれなりの割合で存在」していると不純度は大きくなります。
この「不純度」という指標については色々な計算方法がありますが、よく使われる「不純度」の指標について2つほど説明します。
「不純度」の概念については上記の通りなので、各数式が意図するところは同じなので、「概念がわかればいい」という方は読み飛ばしていただいても大丈夫です。
ここから少し話が細かくなります...。
1.交差エントロピー
ノードtのエントロピーは下記の式より求めます。
（ノードtのエントロピー） = (ノードtにおけるクラス1の割合) * (-log(ノードtにおけるクラス1の割合)) + (ノードtにおけるクラス2の割合) * (-log(ノードtにおけるクラス2の割合)).....(全クラスについて繰り返し計算して足し算)
数式的に表現すると下記のイメージですね。
（ノードtにおけるエントロピーをE(t)と表現。iはクラスを、Nはノードtに存在する全クラス数を意味する。）
[latex] E(t) = - \sum_{i=1}^{N} {p(i|t) * log(p(i|t))} [/latex]
2018年9月5日に修正しました。 数式部分に「マイナスの符号」が抜けていたため、追加しました。「ymdsmn」様、ご指摘ありがとうございます。
数式を見てもらえるとわかるかと思いますが、特定のノードにクラスが１つしか存在しない場合、エントロピーは0になります。
2.ジニ不純度
「ジニ不純度」は下記の計算式より求めます。
（ノードtのジニ不純度) = 1 - (ノードtにおけるクラス1の割合)^2 - (ノードtにおけるクラス2の割合)^2...(ノードtにおける全クラスについて繰り返し計算して足し算)
（２０１８年５月７日までは上記のように記載しておりましたが、nekotan様のご指摘を受け修正いたしました。第２項以降をカッコで囲っておりましたが、markdownの記述方法的に問題があったようです。）
（ノードtのジニ不純度) = 1 - (ノードtにおけるクラス1の割合)^2 + (ノードtにおけるクラス2の割合)^2.....(ノードtにおける全クラスについて繰り返し計算して足し算)
数式的に表現すると下記の通りです。（ノードtにおけるジニ不純度をJ(t)と表現。iは各クラスを、Nはノードtに存在する全クラス数を、p()は割合を意味する。） [latex] J(t) = 1 - \sum_{i=1}^{N} p(i|t)^2 [/latex]
交差エントロピーと同様に、特定のノードにクラスが１つしか存在しない場合、ジニ不純度は０になります。
以上で、「データを分割する基準」を判断するために使う要素である、「情報利得」と「不純度」についての説明を終わります。 続いて、「決定木分析をどれだけ深くまでやるのか」といったことを制御する「剪定」の方法についてご説明します。
5.剪定方法
決定木分析において「汎化性能」を得るためには「剪定」をすることで木の深さを制限する必要があります。 なぜなら、もし剪定をせずに木の深さに制限をかけなかった場合、「モデル作成に利用したデータ」に対して過剰に適合してしまい、「新しいデータ」に対する精度が低くなってしまうからです。 また、決定木分析をする目的として「なんとなくデータが分割されていく過程を目視したい」といった場合もありますが、そのような際にも木があまりにも深いと理解が難しくなってしまいます。 なので、**決定木分析をする上では、「剪定」はほぼ必須と言っても良いものなのですが、ここで「剪定」の有名どころについてご説明します。
考慮すべき要素
剪定をする際は、「木の深さ」、「終端ノード数」、「各ノードに含まれるデータ点数」、「誤り率」等の要素を考慮することが一般的です。 「木の深さ」、「終端ノード数」は大きくなりすぎないように、「各ノードに含まれるデータ点数」、「誤り率」は小さくなりすぎないようにすることが目的です。
剪定方法
有名どころである「コスト複雑度枝刈」についてご説明します。
「コスト複雑度枝刈」は「誤り率」、「終端ノード数」の2つの要素を用いた剪定方法です。
概要については下記の記事をご参照ください。
決定木モデルを作る #alteryx #03 | Alteryx Advent Calendar 2016
ざっくり言うと、「部分木の評価関数が閾値を超えた場合は枝刈りする」といったものです。
（データ分割にとってあまり有用でない部分木を剪定）
そのほかにも剪定方法には色々と種類があるみたいなのですが、私が把握できていないのでここでは説明できません。 申し訳ございません。
6.決定木分析におけるメジャーなアルゴリズムの紹介
決定木分析にもいくつかのアルゴリズムがあるのですが、よく使われるアルゴリズムを2つご紹介します。
1.CART
RやPython等での実装が容易なため、よく利用されるアルゴリズムです。 このアルゴリズムでは、各ノードから「２つに分岐」させます。 不純度として「ジニ不純度」を利用することが多いが、最近は「情報利得」などを用いることもある。
Web上での「決定木分析を解説する」、といったエントリーはCARTアルゴリズムの解説である場合が多いですね。
2.C4.5（C5.0）
とてもよく使われるアルゴリズムです。 CARTでは2つにしか分岐させられないが、C4.5では３つ以上にも分岐が可能です。 交差エントロピーと交差エントロピーから求める「Gain比」を利用して、ノードを分割する際に利用する特徴量を判断しています。 ここでは詳しく説明しませんが、C４.５のアルゴリズムについてはこちらの文献を参考にしてください。
7.まとめ
長くなってしまいましたが、これで「決定木分析」についての解説を終わります。 決定木分析は、分析結果の解釈や実装が容易であり、複数の決定木を組み合わせることで「ランダムフォレスト」や「GBDT(Gradient Boosting Decision Tree)」といったより強力なアルゴリズムに発展させることができる、とても素晴らしい分析モデルです。 また、もし試しに実装してみたいと思った時もweb上に参考となる情報が山ほど落ちていますし、PythonやRでの実装がとても簡単なので、「機械学習を何か実装してみたい」という方にはおすすめです。
決定木分析の発展形である「ランダムフォレスト」や「GBDT(Gradient Boosting Decision Tree)」については、16,17日目にエントリーをあげる予定なので、もしよろしかったらご覧ください。
明日は、実際に決定木分析をPythonで実装してみようと思います。 以上、お付き合いいただきましてありがとうございました。
