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/