Pythonでラベル伝搬法を実装した


##前置き

グラフ上のノードのラベルを推定する手法。

`lp.py`は[ここ](http://satomacoto.blogspot.com/2012/07/python.html)を参考にして実装した。というかほとんどそのまま。

`lp_original.py`は[論文](http://pages.cs.wisc.edu/~jerryzhu/pub/thesis.pdf)の２章を参考にして実装した。

`lp_original.py`では連立方程式を解かないで繰り返し繰り返し行列積を計算していく方法も実装した（`lp_iter`）。

##実装
```lp.py
# -*- coding: utf-8 -*-
import sys
from scipy.sparse import *
from scipy.sparse.linalg import spsolve

def load_adjucency(filename,n):
    W = lil_matrix((n,n))
    for line in open(filename, 'r'):
        entries = line.rstrip().split(' ')
        src = int(entries[0])
        dst = int(entries[1])
        W[src,dst] = 1
    return W

def load_labels(filename,n):
    y = lil_matrix((1,n))
    for line in open(filename, 'r'):
        entries = line.rstrip().split(' ')
        nid = int(entries[0])
        label = int(entries[1])
        y[0,nid] = label
    return y

n = int(sys.argv[1])
W = load_adjucency(sys.argv[2],n)
y = load_labels(sys.argv[3],n)

D = dia_matrix((W.sum(0),[0]), W.shape)
L = D - W

I = identity(W.shape[0])

lam = 1
f = spsolve((I + lam * L), y)
print f
```

```lp_original.py
# -*- coding: utf-8 -*-
import sys
from scipy.sparse import *
from scipy.sparse.linalg import spsolve
from sklearn.preprocessing import normalize

def load_matrix(filename,n,m):
    W = lil_matrix((n+m,n+m))
    for line in open(filename, 'r'):
        entries = line.rstrip().split(' ')
        src = int(entries[0])
        dst = int(entries[1])
        W[src,dst] = 1
    W = normalize(W,norm='l1',axis=1)
    Wul = W[n:n+m,0:n]
    Wuu = W[n:n+m,n:n+m]
    return (Wuu,Wul)

def load_labels(filename,n):
    y = lil_matrix((n,1))
    i = 0
    for line in open(filename, 'r'):
        label = int(line.rstrip())
        y[i,0] = label
        i += 1
    return y

def lp_solve(Wuu,Wul,y):
    return spsolve((identity(m) + Wuu), Wul*y)

def lp_iter(Wuu,Wul,y,t=10):
    i = 0
    f = lil_matrix((Wuu.shape[0],1))
    while True:
        f = Wuu * f + Wul * y
        if i > t:
            break
        i += 1
    return f

""" # of labeled nodes """
n = int(sys.argv[1])
""" # of unlabeled nodes """
m = int(sys.argv[2])
""" propagation matrix (row normalized) """
Wuu,Wul = load_matrix(sys.argv[3],n,m)
""" labels of labeled nodes """
y = load_labels(sys.argv[4],n)


print lp_solve(Wuu,Wul,y)
print '============='
print lp_iter(Wuu,Wul,y)
```

##使い方

`lp.py`はノード数、エッジリストのファイルパス、ノードラベルのファイルパスの順で渡して実行する。
使ってるデータは参考にしたブログと同じもの。

```lp.pyの実行例
$ cat edge_list
0 2
2 0
0 4
4 0
0 9
9 0
1 2
2 1
2 3
3 2
3 4
4 3
3 6
6 3
5 9
9 5
6 7
7 6
6 8
8 6
7 9
9 7
$ cat labels
0 1
2 1
4 1
5 -1
6 -1
7 -1
$ python lp.py 10 edge_list labels
[ 0.45966011  0.23023256  0.46046512  0.1519678   0.5372093  -0.57951699
 -0.38980322 -0.51627907 -0.19490161 -0.15903399]
```

---


`lp_original.py`はラベル付きノード数`n`、ラベル無しノード数`m`、エッジリストのファイルパス、エッジリストのファイルパスの順で渡して実行する。

ただし、ノード番号は`0`から`n-1`がラベル付きノード、`n`から`n+m`がラベル無しノードにしなくちゃいけない。

今回の例で`lp.py`に渡すノード番号と`lp_original.py`に渡すノード番号の対応は次のようになっている。

`lp.py` [0,1,2,3,4,5,6,7,8,9]
`lp_original.py` [0,6,1,7,2,3,4,5,8,9]



なので、ラベルファイルの各行には`0`から`n`のラベル付きノードのラベルが書かれている。

この実装の場合、ラベル無しノードからラベル付きノードへのエッジと、ラベル無しノードからラベル無しノードへのエッジしか使わずに済む。

```lp_original.pyの実行例
$ cat edge_list_for_original
9 0
6 1
7 1
7 2
7 4
9 3
8 4
9 5
$ cat labels_for_original
1
1
1
-1
-1
-1
$ python lp_original.py 6 4 edge_list_for_original labels_for_original
[ 1.          0.33333333 -1.         -0.33333333]
=============
  (0, 0)	1.0
  (1, 0)	0.333333333333
  (2, 0)	-1.0
  (3, 0)	-0.333333333333
```

結果は`lp.py`と違うけど、傾向は同じ。