Pythonでラベル伝搬法を試してみる

ネットワークの構造を予測解析のタスクにはノード判別とリンク予測があります．ノード判別問題は，幾つかのノードについてクラスラベルが与えられているとき，残りのクラスラベルが未知のノードに対してクラスラベルを予測する問題です．

ノード判別手法の最も簡単なもののひとつとしてラベル伝搬法という手法が知られています．ラベル伝搬法のアルゴリズムのひとつを文献1の801ページに基づいて実装してみました．なおラベル伝搬法については文献2の11章にまとまってました．

1. 鹿島, グラフとネットワークの構造データマイニング, 電子情報通信学会誌 93(9), 797-802, 2010.
2. Chapelle, O. et al., Semi-supervised learning, MIT Press, 2006.

ラベル伝搬法は「ネットワーク上で隣り合ったノードは同じクラスに属する」と仮定して未知のノードにラベルを振る半教師あり学習の手法．ここでは +1 と -1 の2種類のクラス判別問題．

• ネットワークの構造は${\bf W}$で表す．${\bf W}$の$i,j$成分は$i$番目のノードと$j$番目のノードにリンクがある(1)か，ない(0)か．
• クラスラベルはベクトル${\bf y}$で表す．ふられてないときは0．
• 予測値はベクトル${\bf f}$で表す．それぞれ[-1,1]の連続値．

で隣り合ったノードの予測値が互いに近くなるように決定するための目的関数は以下．

$\begin{align} J({\bf f})&=\sum_{i=1}^l(y^{(i)}-f^{(i)})^2 + \lambda \sum_{i<j}y^{(i,j)}(f^{(i)}-f^{(j)})^2 \\ &=||{\bf y}-{\bf f}||_2^2+\lambda {\bf f}^T{\bf L}{\bf f} \end{align}$

ただし${\bf L}\equiv {\bf D}-{\bf W}$で${\bf D}$は${\bf W}$の各行の和を対角成分に持つ行列．λは1項目と2項目のバランスを取る定数．1項目は正解に近づけ，2項目は隣合うのノードの予測値を近づけます．

で，この最小化問題の解が

$({\bf I}+\lambda {\bf L}){\bf f}={\bf y}$

の解として求められます．


以下，てけとーにノードクラスとリンクを決めて試してみました．要scipy．

	#!/usr/bin/env python
	# -*- coding: utf-8 -*-
	from scipy.sparse import dok_matrix, dia_matrix, identity
	from scipy.sparse.linalg import spsolve
	# ネットワークの構造
	# ノードiとノードjの間にリンクがあるときW[i,j]=1
	W = dok_matrix((10,10))
	W[0,2] = W[2,0] = 1
	W[0,4] = W[4,0] = 1
	W[0,9] = W[9,0] = 1
	W[1,2] = W[2,1] = 1
	W[2,3] = W[3,2] = 1
	W[3,4] = W[4,3] = 1
	W[3,6] = W[6,3] = 1
	W[5,9] = W[9,5] = 1
	W[6,7] = W[7,6] = 1
	W[6,8] = W[8,6] = 1
	W[7,9] = W[9,7] = 1
	# クラスラベル
	# 与えられていないときは0
	y = dok_matrix([[1, 0, 1, 0, 1, -1, -1, -1, 0, 0]])
	# DはWの各行（もしくは列）の和を対角成分に持つ行列
	D = dia_matrix((W.sum(0),[0]), (10,10))
	# ラプラシアン行列
	L = D - W
	# 単位行列
	I = identity(10)
	# lamb>0は２つの項のバランスを取る定数
	lamb = 1
	# 連立方程式の解を求める
	#[ 0.45966011 0.23023256 0.46046512 0.1519678 0.5372093 -0.57951699
	# -0.38980322 -0.51627907 -0.19490161 -0.15903399]
	f = spsolve((I + lamb * L), y)

view raw label_propagation.py hosted with ❤ by GitHub

以下，結果をD3.jsで可視化しました．

予測前

ブルーとグリーンが予めクラスを与えているノード．オレンジのノードのクラスを予測します．

予測後

λ=1の結果です．node1とnode3はブルー，node8とnode9はグリーンに分けられました．ノードの色の濃さ（白か黒か）でどっちに近いか示しています．