Une technique pour estimer l'étiquette d'un nœud sur un graphe.
lp.py a été implémenté en référence à here. Ou plutôt, presque tel quel.
lp_original.py a été implémenté en se référant au chapitre 2 de Paper.
Dans lp_original.py, nous avons également implémenté une méthode pour calculer le produit matriciel itératif et itératif sans résoudre les équations simultanées ( 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 est exécuté en passant le nombre de nœuds, le chemin du fichier de la liste d'arêtes et le chemin du fichier de l'étiquette du nœud dans cet ordre.
Les données utilisées sont les mêmes que celles du blog auquel j'ai fait référence.
lp.Exemple d'exécution de 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 est exécuté en passant le nombre de nœuds étiquetés n, le nombre de nœuds non étiquetés m, le chemin du fichier de la liste des bords et le chemin du fichier de la liste des bords dans cet ordre.
Cependant, les numéros de nœuds doivent être de "0" à "n-1" en tant que nœuds étiquetés et de "n" à "n + m" en tant que nœuds non étiquetés.
Dans cet exemple, la correspondance entre le numéro de nœud transmis à «lp.py» et le numéro de nœud transmis à «lp_original.py» est la suivante.
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]
Par conséquent, chaque ligne du fichier d'étiquettes contient les étiquettes des nœuds étiquetés de «0» à «n».
Avec cette implémentation, vous devez uniquement utiliser l'arête du nœud sans étiquette au nœud étiqueté et l'arête du nœud sans étiquette au nœud sans étiquette.
lp_original.Exemple d'exécution de 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
Le résultat est différent de «lp.py», mais la tendance est la même.
Recommended Posts