August 6, 2012

LIBSVMを使ってノード判別問題を解いてみる

以前ラベル伝搬法を使って解いたノード判別問題SVM (Support Vector Machine)のライブラリlibsvmを使って解いてみます.

ノード判別問題は半教師あり学習のひとつで

  • 一部のノードのクラス,リンク構造がわかっている.
  • すべてのノードのクラスを推定したい.

という設定です.データは以前と同じものを使います.



libsvmのダウンロードとインストール

下のサイトのDownload LIBSVMからzip fileかtar.gzをダウンロードします.

http://www.csie.ntu.edu.tw/~cjlin/libsvm/

解凍したら

% make
で実行ファイル svm-scale, svm-train, svm-predict が生成されます.Windowsでのやり方もREADMEを見れば書いてあると思います.どこでも実行できるようにするためにはPATHの通った場所に置く必要がありますが,今回は別に移動しなくても大丈夫.



SVMの実行

今回は訓練データもテストデータもそんなに大きくないのでSVMについて何にも知らなくても使えるeasy.pyを使って分類してみました.

easy.pyではgnuplotの場所を指定しているのでHomebrewのようなパッケージ管理ソフトを使ってgnuplotなどをインストールした場合はeasy.pyを編集する必要があります.

たとえば

% which gnuplot
/usr/local/bin/gnuplot
であったらeasy.pyの19行目を以下のように変更します.

gnuplot_exe = "/usr/bin/gnuplot"
gnuplot_exe = "/usr/local/bin/gnuplot"



入力データ

以前と同じもの.と思ったけど,ソースノードとターゲットノードが同じ時はリンクありにすべきかリンクなしにすべきか…(今回はリンクありとした.)

ブルーとグリーンがクラスのわかってるノード.オレンジのノードのクラスを含めてすべてのクラスを予測したい.


libsvmに合わせてフォーマットを変える.

<label> <index1>:<value1> <index2>:<value2> …
.
.
.
インデックスは1から始まることに注意.たとえばnode0のインデックスは1,node1のインデックスは2.

訓練データはわかっているものだけ.
% cat links
1 1:1 3:1 5:1 10:1
1 1:1 2:1 3:1 4:1
1 1:1 4:1 5:1
-1 6:1 10:1
-1 4:1 7:1 8:1 9:1
-1 7:1 8:1 10:1

テストデータはすべて.
% cat links.t
1 1:1 3:1 5:1 10:1
0 2:1 3:1
1 1:1 2:1 3:1 4:1
0 3:1 4:1 5:1 7:1
1 1:1 4:1 5:1
-1 6:1 10:1
-1 4:1 7:1 8:1 9:1
-1 7:1 8:1 10:1
0 7:1 9:1
0 1:1 6:1 8:1 10:1



実行

toolsに移動してeasy.pyを使ってSVMで分類.
easy.pyはRBFカーネルのSVMでスケーリング,パラメータ選択,訓練,予測までやってくれる.

% cd tools
% ./easy.py links links.t



結果

% cat links.t.predict
1
1
1
1
1
-1
-1
-1
-1
-1

可視化したもの.



参考

"A Practical Guide to Support Vector Classification", http://www.csie.ntu.edu.tw/~cjlin/papers/guide/guide.pdf
上記事の日本語解説資料, http://d.hatena.ne.jp/sleepy_yoshi/20120624/