読者です 読者をやめる 読者になる 読者になる

drilldripper’s blog

機械学習とソフトウェア開発を頑張ってます

ランダムフォレストの理論と重要な特徴量の選定

ランダムフォレストと決定木学習

ランダムフォレストを理解するためには、決定木学習の手法について理解する必要があります。まず最初に決定木学習の理論について説明します。

決定木学習

決定木は親から順に条件分岐を辿っていくことで、結果を得る手法です。下は決定木のイメージです。

決定木学習とはデータの応じて上の図のような決定木を構成し、分類を行う機械学習の手法のことを指します。 f:id:drilldripper:20161005074636p:plain

決定木学習は、データの種類に応じて決定木を成長させていきます。 決定木の分類条件は、データを分類したときの情報利得IG(Infomation Gain)が最大になるようにすることです。情報利得は式(1)で表されます。

{IG(D_p, f) = I(D_p) - \sum_{j=1}^{m}\frac{N_j}{N_p}I(D_j)}\tag{1}

{D_p}は親のデータ、{N}はノード、{j}は注目しているデータを表します。 {m}は木を分割するノード数です。一般的に決定木は二分木として実装されるので、ほとんどの場合は{m=2}となります。

{I}は不純度という指標で、含まれるデータに偏りがあるほど大きな値になります。不純度の計算にはエントロピー、ジニ不純度、分類誤差などが用いられます。今回はエントロピーを使って説明をします。式(2)にエントロピーの式を示します。

{I_H(t) =  -\sum_{i=1}^{c}p(i|t)\log_2 p(i|t)}\tag{2}

{p(i|t)}はデータ数tの中に含まれているデータ数iの割合を表します。

エントロピーはデータのばらつきが大きいほど大きな値となります。例えばサンプル数100個のデータを分類したとき、左の木に100個、右の木に0個に分類すると、エントロピーは最も大きな値である1になります。逆にエントロピーが最も小さくなるのは、左右の木に50個ずつ分類したときで、エントロピーは0になります。

式(1)の{I}エントロピー{I_h}を代入することで情報利得の計算を行います。

ランダムフォレスト

ランダムフォレストは決定木を複数組み合わせて、各決定木の予測結果を多数決することによって結果を得ます。*1

以下にアルゴリズムを示します。

  1. ランダムにデータを抽出する*2

  2. 決定木を成長させる

  3. 1,2ステップを指定回繰り返す

  4. 予測結果を多数決することによって分類閾値(ラベル)を決定する。

ランダムフォレストはパラメータが非常に簡単になるという利点があります。主要なパラメータはサンプリング数と決定木を成長させる際に使用する特徴量の数だけです。決定木の特徴量数は一般的にサンプル数をnとしたときに{\sqrt n} にすると良いと言われています。*3

ランダムフォレストのメリットとデメリット

メリット

  • 特徴量のスケーリングが必要ない(SVMなどの分類手法では必要になる)
  • 考慮するパラメータが少ない
  • 並列化が容易
  • どの特徴量が重要かを知ることができる

デメリット

  • 複雑なデータではSVMなどの分類手法に比べて汎化性能が下がる

Scikit-learnを使って特徴量の重要度にアクセスする

Scikit-learnにはランダムフォレストの実装されています。今回はこの実装を使ってデータを分類行って、特徴量の重要度を調べてみます。 使用する学習データはアヤメの計測データであるIrisデータセットです。以下にソースコードと結果を示します。

from sklearn import datasets
from sklearn.ensemble import RandomForestClassifier
import numpy as np
iris = datasets.load_iris()
feature_names = iris.feature_names

forest = RandomForestClassifier(n_estimators=10000, random_state=0, n_jobs=-1)
forest.fit(iris.data,iris.target)
importances = forest.feature_importances_
print("{0:<20}".format ("feature names"), "importances")

for (feature_name, importance) in zip(feature_names, importances):
    print("{0:<20}".format (feature_name), importance)
feature names        importances
sepal length (cm)    0.0980144976191
sepal width (cm)     0.0232983974998
petal length (cm)    0.439861958314
petal width (cm)     0.438825146567

結果をみるとpetal length(花弁の長さ)が最も重要な指標であり、sepal width( がく片の幅)が最も重要度の低い指標であることがわかります。 この結果は、SVMなどの機械学習アルゴリズムの特徴量選択の参考にすることができます。

参考文献

*1:弱学習器を組み合わせてロバストな学習器を作ることをアンサンブル学習と呼びます

*2:重複を許さないブートストラップ標本の抽出を行う

*3:ただしデータに依存するので、必ずしもこの値が良いというわけではありません

ETロボコンの走行を支える技術

What is ETロボコン

ETロボコンは統一規格のロボット(Mindsorms EV3)を使い、指定されたコースを走行する精度とタイムを競う競技です。UML等で書かれた仕様とアピールポイントをまとめたモデルシートを作成する必要があり、モデルシートも評価の対象となります。

ETロボコン2016公式サイト

統一規格のロボットを使うというルールから分かる通り、ソフトウェアデザインとアルゴリズムに重きが置かれたロボコンと言えます。*1珍しい特徴として、ETロボコンは学生チームと企業チームが同じ土俵で戦います。*2車両開発系や組込系のIT企業も参加するとても熱い競技です。

今回はロボットの走行を支える一般的な技術について書きたいと思います。UMLなどのソフトウェア設計技術も順位決定の重要な要素ですが、今回は触れません。

ライントレース

ロボットは基本的にコースに引かれた黒い線を追いかけて走行します。原始的な手法として、白を検知したら右に旋回し、黒を検知したら左に旋回するという手法があります。下の図ようなイメージです。 f:id:drilldripper:20160925192150p:plain

これは一般にON/OFF制御として知られている手法です。この手法では右と左にしか動作することができないので、ロボットがジグザグな動きとなります。当然安定性が低く速度も遅くなります。これを改善するためにPID制御が用いられます。

PID制御

PID制御(Proportional-Integral-Differential Controller)は古くから使われるフィードバックループの制御手法の一つです。名前の通りフィードバッグの要素として比例値P、微分値I、積分値Dを使います。PID制御は以下の式で表されます。

{  K_pe(t) + K_i \int_0^t e(\tau) \: d\tau + K_d\frac{de(t)}{dt} }  (tを時間、eを入力と目標値の誤差とする)

各項の意味を簡単に説明します。(そのため正確性は少し欠いているかもしれません)

  • Kp値(比例制御):

    • 入力値と目標値(出力したい値)の偏差を計算し、偏差の大きさによって操作量(出力に近づけるための値)を変化させます。
  • Ki値(積分制御):

    • 入力値の目標値の偏差を積分をします。偏差がある状態が長く続くほどこの項は大きくなり、目標値に近づいていきます。
  • Kd値(微分制御)

    • 積分制御の項が大きくなりすぎると、目標値を超えて制御不能になる場合や、目標値の前後を振動してしまう場合があります。そこで微分制御では偏差の微分値を計算することで、急激な変化を捉えて動作を押さえ込みます。

PIDの各パラメータを適切に設定できれば、ロボットを滑らかに走行させることができます。

探索アルゴリズム

走行エリアには難所と呼ばれるアトラクションがあり、クリアするとボーナスポイントを取得できます。難所の一部は探索問題に帰着させることができる場合があります。問題をよく考察してグラフなどのデータ構造に落とし込めば、以下のアルゴリズムが使用できます。*3

計算量や実装難度と相談して、攻略に最適なアルゴリズムを選びましょう。

データ分類(機械学習)

ロボットからは様々なセンサ情報を取得することが出来ます。EV3であればジャイロセンサ、超音波センサ、光センサなどから情報が取得できます。取得したセンサ情報から状況を把握することで、ロボットの次の動作を決定できます。

人間が手動で分類の閾値を決定することもできますが、うまく教師データを作ることができればRandom ForestやSupport Vector Machineなどの機械学習アルゴリズムを活用できる可能性があります。

デッドレコニング(自己位置推定)

競技ではロボットの位置によって動作を変更しなければならないので、ロボットの自己位置を推定する必要があります。センサ情報とロボットの仕様から自己位置を推定する手法を、一般的にデッドレコニングと呼びます。

デッドレコニングは走行距離が長くなると、蓄積した誤差によって自己位置の推定に失敗してしまいます。そのため何らかの工夫で誤差の蓄積をリセットする必要があります。

タスクの制御

ロボットの上で複数の処理を同時に動作させるさせることで、柔軟な処理が可能になります。リアルタイムOSでは処理をタスクと呼ばれる単位に分割して、優先度を決めて動作させるさせることができます。

一般的な並列プログラミングと同様に、排他制御に気を使う必要があります。

おわりに

いろいろ技術を学ぶことができる熱い競技なので、課題*4をクリアできるのであれば参加してみると楽しいと思います。

*1:ETロボコンの正式名称はEmbedded Technology Software Design Robot Contestです。名前からもソフトウェアに重きを置いていることがわかります。

*2:ISUCONなどと同じですね

*3:一瞬「競技プログラミングは役に立たない」の反例かと思ったが、競技の攻略に競技が役立ったと主張するのはだめな気がします

*4:時間、予算、練習場の確保、チームメンバ集めなど

SVMの基本原理と不均衡データに対するパラメータ調整

前回の記事では不均衡データをサンプリングすることで、学習の精度を上げる方法を書きました。今回はSVMのパラメータを調整することで、不均衡データの学習の精度を上げる方法について書こうと思います。
そのためにSVMの基本を理解しておいたほうがよいと思うで、簡単にまとめてみたいと思います。

SVMの基本原理

SVMのイメージは以下のページを見てもらうとわかりやすいと思います。

SVMを使うとなにが嬉しいの?

簡単に言うとSVMの目的は、データを2つのクラスに分離する線を引こうとしたときに、2つのクラスとのユークリッド距離が最も大きくなるようにする(マージンを最大化する)ことです。これだけではわからないと思うので、数式で原理を追ってみます。

正方向の傾きをx_p、負方向の傾きをx_n w をクラスを2つに分離する直線したとき、正の超平面は式(1)、負の超平面は式(2)のように表せます。
w_0 + w^T x_p = 1 \tag{1}
w_0 + w^T x_n = -1\tag{2}
式(1) - 式(2)から式(3)を得ます。

w^T(x_p - x_n) = 2\tag{3}

これをベクトルの長さとして標準化すると式(4)が得られます。

|| w || = \sqrt{\sum_{j=1}^{m} w^2 _ j}\tag{4}

超平面について表した式(3)とベクトルの長さ式(4)から、式(5)が得られます。
\frac{ w^T(x_p - x_n)}{||w||} = \frac{2}{||w||}\tag{5}

左辺は超平面の距離(マージン)なので、右辺を最大化することで最大マージンを得ることができます。
最大マージンを得るためには、式(5)について、式(6)、式(7)の制約を満たすような問題を解く必要があります。

w_0 + w^T x^i \geq 1 \tag{6}
w_0 + w^T x^i < -1 \tag{7}
(iはすべてのデータです)

ただし式(5)の右辺は逆数をとって2乗した\frac{1}{2} ||w||^2を解く方が簡単になることが知られている*1ので、この式を使うことにします。

ここまでがSVMの基本的な原理です。さらにこれを改良して非線形なデータに対しても分類が行えるようにしたいと思います。
制約を緩和するための変数を\zeta*2を式(6)、式(7)に導入して式(8)、式(9)を得ます。

w_0 + w^T x^i \geq 1 - \zeta \tag{8}
w_0 + w^T x^i < -1 + \zeta\tag{9}

これを\frac{1}{2} ||w||^2に当てはめることで式(10)を得ます。
\frac{1}{2} ||w||^2 + C\sum_{i}^{}\zeta^i \tag{10}

これで変数Cの値を変えることで、データの分類に対するペナルティを設定できるようになりました。Cの値を大きくすると誤分類にペナルティを与え、Cの値が小さいときには誤分類を許容するようになります。

不均衡データへの適応

不均衡データの学習がうまくいかない理由は、殆どのデータを偏った大きなクラスに分類することで「正答率」が上がってしまうためです。

例えば天気予報を行うことを考えてみます。天気は一年を通して多くの日が晴れとなるので、仮にすべての日を晴れと予報しても「正答率」は高くなります。しかし当然のことながら、私たちはいつ雨が降るかということが知りたいです。つまり雨の日を晴れの日とご分類するケースをできるだけ少なくしたいということです。これは式(10) においてCの値を大きくするということに値します。

Scikit-learnのSVMではこのCのパラメータを簡単に変更することができます。
以下のように、分類器をインスタンス化するときに引数に設定するだけです。詳しくはドキュメントを読んでみてください。

clf = SVC(kernel='rbf', C=1000)

sklearn.svm.SVC — scikit-learn 0.18.1 documentation

また不均衡データについても公式ドキュメントで触れられているので、目を通しておくといいと思います。
1.4. Support Vector Machines — scikit-learn 0.18.1 documentation

参考文献

*1:二次計画法を使うことで解くことができる

*2:スラック変数といいます

pandasを使った不均衡データの整形

不均衡データ

機械学習を行う上で正例と負例が偏っている学習データを使うと、学習がうまく行きません。サンプル数が多いクラスに引っ張られてしまいます。そのため事前にデータの加工を行うと、結果が良くなることが知られています。

多い方のクラスを少なくする手法をアンダーサンプリング、小さい方のクラスを多くする手法(人工的にデータを作り出す手法)オーバーサンプリングといいます。今回はpandasを使ってアンダーサンプリングを行ってみます。

データのアンダーサンプリング

gista519abe99ebbe9a687b3a1288dfb8995

小さいクラスのデータ数を取得し、大きいクラスからランダムに小さいクラスの個数分データを抽出します。その後データをマージしています。

この方法ではアンダーサンプリングした結果に偏りが生じる可能性があります。学習の精度を向上させたいときはk-meansでデータをクラスタリングを行い、偏りがないようにデータを抽出する必要があります。

スクリーンショット自動化ツール「BindScreen」を作りました

スクリーンショット自動化ツール「BindScreen」

スクリーンショットを自動でとって加工する「BindScreen」を作りました。 ツールとソースコードGitHubからダウンロードすることができます。

BindScreen - Github drilldripper/BindScreen

使用例

次のスライドをこのツールで画像化してみたいと思います。*1

C++の歴史 江添亮 (このスライドはGFDL1.3で配布されています)

今回の設定は以下のようにしてみました。

f:id:drilldripper:20160811220020p:plain

キャプチャ間隔はスクリーンキャプチャを行う間隔です。またキー入力もこの間隔で行われます。

初期化時間はプログラムが実行が始まるまでの時間です。設定した時間の間にキャプチャする画面を前面に表示しておきます。今回はブラウザの要素をキャプチャしますが、多くのブラウザではF11を押すと全画面表示になるので活用するといいと思います。

今回は画像のトリミングを行わずに圧縮を行いたいので、「画像のトリミングを行う」のチェックを外し、「圧縮フォルダを出力する」にチェックを入れます。見開き方向の選択はトリミングを行わない場合はどちらを選んでも出力結果に影響はありません。またこのスライドは右キーで次ページに移動するので、"右キー"を選択して出力先フォルダを設定します。

設定が完了したら実行をクリックしましょう。スライドが終了すると自動的にスクリーンショットの撮影が止まります。

指定したフォルダを確認すると「spread_image」と「spread_complete.zip」が作成されています。試しにspread_imageを開くと以下のような画像が生成されています。

f:id:drilldripper:20160811220042p:plain

f:id:drilldripper:20160811220203p:plain

うまくいきました。

他にもソフトの表示結果のログを画像として記録する用途などで使えると思います。

技術的な話

画像処理

このツールはPythonを使って開発を行いました。画面のキャプチャにはPythonの標準的なツールであるPIL(Python Imaging Library)のforkであるPillowを使っています。PILは開発が停滞していてPython2.7までしか対応していませんが、Pillowは開発が継続的に行われていてPython3以降に対応しています。 また画像の分割や余白の除去もPillowで行っています。

画面キャプチャは変化が無くなった時点で自動的に終了しますが、これは前後の画像のMD5を計算してメッセージダイジェストが同じであれば終了する仕組みになっています。この方法では数ピクセルでも画像が異なっていれば違う画像として判定されます。もし画像の僅かな違いを許容したいのであれば、画像のヒストグラムを比較して閾値で判定を行う方法をとると良いかもしれません。

キーボード入力

キーボード入力はwin32APIであるSendKeysを使ってキーストロークを送信しています。GUIでは上下左右の方向キーのみ対応していますが、CUIAPIを引数に与えれば任意の入力を行うことが出来ます。

SendKeys メソッド - MSDN

このツールがWindows専用ツールになったのはSendKeysAPIを使用しているからです。 xautomationなどを使えばLinuxMacに対応することができますが、依存ライブラリが増えてしまうので今回は使用しませんでした。

GUI

GUIの作成にはPyQt4を使いました。今回初めて使いましたが、さくっとGUIが出来てとても便利でした。PyQtはモジュールが疎結合に作られているので、ボトムアップ的で面白かったです。

このツールはもともとCUIとして作成したので、GUIは引数とオプションを決めてスクリプトに渡す設計にしています。このような作り方にするとCUIが独立して使えるので、バッチ処理ができるのでいい感じですね。

*1:テキストのスライドを画像にしたら逆に使いにくいと思いますが、一例ということで…

PyQtのConnectで引数付きの関数を渡す方法

PyQtではconnectを使ってイベントに対応する関数を呼び出すことが出来ます。しかし引数付きの関数をconnectに直接渡すことは出来ません。以下のようなエラーが発生すると思います。

"TypeError: connect() slot argument should be a callable or a signal, not 'NoneType'"

これを解決するためにはlambdaを使って式にする方法を使います。

以下のようなコードにすればよいでしょう。

# -*- coding: utf-8 -*
from PyQt4.QtCore import *
from PyQt4.QtGui import *
import sys

class MyForm(QMainWindow):
    def __init__(self, parent=None):
        super(MyForm, self).__init__(parent)
        button = QPushButton('Click')
        # エラーが発生する
        # button.clicked.connect(self.on_click("Hello world"))
        # lambdaを使う
        button.clicked.connect(lambda: self.on_click("Hello world"))

        layout = QHBoxLayout()
        layout.addWidget(button)

        main_frame = QWidget()
        main_frame.setLayout(layout)

        self.setCentralWidget(main_frame)

    def on_click(self, str):
        print(str)

if __name__ == "__main__":
    app = QApplication(sys.argv)
    main_window = MyForm()
    main_window.show()
    app.exec_()

競技プログラミングから輸入した普段使いでも便利なC++テンプレート

以下のテンプレートを記述すると、Vectorとpairの中身をcoutで表示できるようになります。

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
template <typename T>
std::ostream &operator<<(std::ostream &out, const std::vector<T> &v) {
if (!v.empty()) {
    out << '[';
    std::copy(v.begin(), v.end(), std::ostream_iterator<T>(out, ", "));
    out << "\b\b]";
  }
  return out;
}
template <typename T1, typename T2>
std::ostream &operator<<(std::ostream &out, const std::pair<T1, T2> &p) {
    out << "[" << p.first << ", " << p.second << "]";
    return out;
}

入力ストリーム << をオーバーロードしてVectorとpairを表示できるようにしています。使用例を以下に示します。

int main(){
    std::pair<int, int> pData(2, 3);
    std::vector<int> vData(5);
    vData[0] = 3;
    vData[1] = 5;
    vData[2] = 7;
    vData[3] = 11;
    vData[4] = 2;
    std::cout << "--Show Vector--" << std::endl;
    std::cout << vData << std::endl;
    std::cout << "--Show Pair--" << std::endl;
    std::cout << pData << std::endl;
    return 0;

}

output

--Show Vector--
[3, 5, 7, 11, 2]
--Show Pair--
[2, 3]

競技プログラミングをやっているとたまに見かけます。

結構便利でPythonでリストをprint()で表示するような感覚でC++の出力を扱えるので、printfデバッグが捗ります。

こんなことをしているから、いつまでたってもデバッガを使いこなせないのかもしれない…。