ランダムフォレスト(乱数の森)

ランダムフォレストとは

乱数の森(ランダムフォレスト)とは、決定木(後述)を寄せ集めて実現される学習アルゴリズムです。ランダムフォレストを簡潔に表現すれば、「多数決のアルゴリズム」と呼べます。

Random Forest ( ランダムフォレスト、乱数の森のイメージ図)

アルゴリズムは比較的簡単で、決定木を適当に何本か作り、質問を投げかけます。答えた木の多数決により解が決まります。

例えば50本の決定木があったとして、40本の木がある質問に対してYesと答えた場合、この質問の回答はYesとなります。そして回答の正当性は80%で…という結果も得ることができます。ランダムフォレストの良いところは、木の数が確率で返答としても参考にできるところです。

以上のようにランダムフォレスト自体は解りやすいのですが、実装する上では決定木を理解することが必要です。

決定木とは

決定木は学習アルゴリズムの1つで、質問してYes、Noで分岐していき、木構造を作成することで完成されます。

「完全に答えが出るまで分岐させ、これ以上分岐できないのであれば、そこで終わり」

というアルゴリズムです。決定木のいいところは、分岐点を見ていくと、何故その判断に至ったのか論理的に理解しやすいところです。たとえば、以下のような決定木のとき、最終的な状態(leaf)はどのような項目(質問)により分類されたか、がわかるのです。

決定木
Fig2. 役員か平社員か早期退職者の決定木の例

上記をみると役職の理由(平社員、管理職)が視覚的にわかります。学習後はこのような木ができて、なぜこうなったのかが理解しやすいのが決定木の良いところなのです。

決定木の作り方

「ある集合をなるべく偏りがあるように2つに分断する。」

これをくり返していくことで木を作成していきます。偏りという概念には「情報エントロピー」を使います。

偏りとは、例えばYES、NOという回答が混ざっている状態から、YESとNOの2つの集合に綺麗に分けてやることです。他にも例えば「いちごミルク」から「いちご」と「ミルク」に偏ってわけたい(混ざった状態から、混ざってない状態に戻す)ことを偏りをつくるといいます。

Fig3. 偏りを作る例。質問Yの方が質問Xよりうまく偏りがある。質問Zは完璧ではないものの、結構精度が高く偏りがもとめられる。どれが、偏りが高いかを定量的に表すために情報エントロピーを利用する。

完全に混ざった状態はエントロピーが高い状態(乱雑な状態)であるといいます。逆に偏りがある状態をエントロピーが低い状態(偏った状態)と呼びます。なるべくエントロピーが低く低くなるような分岐状態(偏りがあるような分岐)を作っていくこと、これが決定木をつくる上で重要なことです。

偏るためには質問を用意します。質問は何でも良いですが、自分で用意する必要があります。先の例(Fig.2)であれば、今までの従業員の結果(役職)をもとに、彼らへの質問を用意しておくのです。質問の内容はたくさんあると思います。それこそ性別、勤続年数、宗教、出身地、出身校、目の色、頭髪、身長、体重などなど。(コンプライアンス的に引っかかるものもありますが、)こうした質問を用意しておいて、うまく分けることができたら(偏りを作れたら)良い質問だったということになります。

情報エントロピー

偏ったかどうかという判定に情報エントロピーを使うと言いましたが、それはとても便利だからです。情報エントロピーの数式は次の式となります。

情報エントロピーの式 : -\sum{P\log_2{P}}   (1.1)

Pには数値が0−1までの数値が入ります。

情報エントロピーの値が元の集合の情報エントロピー値より低くならないのであれば、木はそれ以上枝を作りません。

情報エントロピーについて具体例で考える

先の式(1.1)を掘り下げましょう。男女の集合の中から、ある質問をして「男」と分割した時のエントロピーを考えます。決定木では質問の後は必ず2クラスに別れます(グループA, グループBとする)。

グループAに男が存在する割合をP(x)とすれば、グループBに男が存在する割合は必ず1-P(x)となります。(2クラスしかないため)したがって男性側だけの情報エントロピーは、

P(x) * log_2{ P(x) }  (グループAに男:GroupA(男))

(1-P(x)) * log_2{ (1-P(x)) } (グループBに男:GroupB(男))

この2つを足して、マイナスをしたのが、男性側の情報エントロピーです。

さて、男性がうまく分割しても、女性は分割出来ていない場合もあるかもしれません。女性にも男性と全く同じ質問をして、女性側のエントロピーも求めます。グループAに女が存在する割合をP(y)とします。同様に2クラスしかないため1-P(y)がグループBに女性がいる割合です。

P(y) * log_2{ P(y) } (グループAに女:GroupA(女))

(1-P(y)) * log_2{ (1-P(y)) }  (グループBに女:GroupB(女))

最終的にこの4つをすべてを足しこんで、マイナスした値-( GroupA(男)+GroupB(男)+GroupA(女)+GroupB(女) )が結果的な情報エントロピーとなります。(男女別情報エントロピーの合計,のマイナス)

今は男女になりましたが、昨今性別が増えています。性別が増えた場合も同様に足しこんでマイナスをすれば、最終的な情報エントロピーがでます。

上記でlogの底が2であることに注意してくだい。コンピューターで計算する際は変換公式によりlog_2{x}=\frac{log_e{x}}{fog_e{2}}を利用しましょう。

決定木は必ずノードで2つに分割するので、結局その場合のある要素の情報エントロピーは次の式となります。

Entropy = - ( x * \frac{\log_e{x}}{\log_e{2}} + ( 1-x) * \frac{\log_e{1-x}}{\log_e{2} }) (2)

上記の情報エントロピーをGnuPlotで出力すると以下になります。

確率Pが0.5の時に上に凸の山なりのカーブを描きます。(最大値を示します)。0.5はランダムな状態(乱雑な状態)、分割がうまく行かなかったことを表します。ランダムであれば一番高い値となる、これが情報エントロピーです。情報エントロピーは前述の通り、低ければ低いほど偏りがあるという事になるのです。

こうして出来た決定木をあつめて、ランダムフォレストは作成されます。ランダムフォレストを作成する際の注意点は、同じ決定木を作らないようにすることです。質問を違う順番でしたり、パターンを用意したり、様々な試行を行わなければなりません。多数決のアルゴリズムですので、それこそ多種多様な決定木があるほうが良いのです。

最後に

実は、決定木ではかならず2分割されると書きましたが、実際にはエントロピーを使うと3分割、4分割も出来ます。ただ、乱数の森を使う場合あまり意味がないものとなるでしょう。解析や判断も複雑になるため、基本的には2分割の決定木を使ったランダムフォレストで十分な精度が出ます。

実は、ランダムフォレストは非常に強力です。これ一本で(何本もありますが)本当に様々なことが出来ます。機械学習の仲間と話しますが、これだけでもいいと思うくらいです。

その昔、回帰木というものがありました。これは連続した値を扱えるところが素晴らしかったのですが、木を作るのに時間がかかるデメリットやオーバーフィッティングのデメリットがありました。ランダムフォレストをつかえば、何本の木が返答したというような確率を使うことで、あたかも連続したデータも扱えるようになってしまったのです。しかもオーバーフィッティングはありません。じゃあ、回帰木をつかったランダムフォレストは更に精度が高くなるのでは!?と思うかもしれませんが、実際にはあんまり変わりません。よくよく考えれば、回帰木のランダムフォレストって、意味も正直わからないですしね。(重回帰分析の重みの平均みたいなイメージになりますよね。。。)

参考サイト

https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%B3%E3%83%80%E3%83%A0%E3%83%95%E3%82%A9%E3%83%AC%E3%82%B9%E3%83%88

おすすめ記事


投稿者: 等々力 康弘

画像処理エンジニア。組み込みソフト出身。 株式会社モルフォにてR&D部門、主に機械学習業務に携わり、顔認識&顔検出のアルゴリズム開発に従事。国内特許数件、国際特許1件。 モルフォ社退社後、株式会社Dynaptico創業(CEO)。アメリカ人、スウェーデン人と3名とフードデリバリーサイトmaishoku.comを立ち上げる。社長業の他、開発業務においてバックグラウンド関連全般(Djangoを用いいたバックエンドサーバ&APIサーバーの作成、 リバースプロキシなどの負荷分散サーバ関連、OCRプログラムの作成、CISCOルータの管理, 、seleniumを用いたテストサーバーの構築、Androidアプリの開発等々)に携わる。 2019年DynapticoのCEOを辞職。 2020年2月にComputer Scienceに特化した株式会社OctOpt創業。 OSはUbuntu。Appleが苦手。Swiftのバージョンアップ対応とか死ぬほど嫌い。 Python/C++/C Twitter: @rocky_house シフト自動調整スケジュールサイトをVue.js+graphene djangoで構築. https://www.allshifter.com

コメントを残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です