LabelSpreadingについて - ハムスターに飼われる院生のブログ

pythonのsklearnで実装できるLabelSpreadingに興味を持ったので、分かったことを書く。

基本的には

に載っている。

超概要

各データをノードとしてエッジでつなぎ、分類のラベルを伝播させていく。

手順は以下の通り

①類似度行列Wを作成する。

　もし、i,jが等しくなかったら

　 $W_{ij}=exp(-||x_i-x_j||/2σ^{2})$

　i,jが等しかったら

　 $W_{ij}=0$

②行列Sを作成する

　ここで、行列Sは、行列Wのi行目の値を成分にもつ対角行列を用いて

　 $S=D^{-1/2}WD^{-1/2}$

　となる。

③ラベルの伝播を繰り返す

　 $F(t+1)=αSF(t)+(1-α)Y$

　を収束するまで繰り返す

　ここで、Yは初期に与えたラベルで、

　例えばデータ1のラベルは0で、データ2のラベルは1、その他のデータにはラベルがついていない、という状況ならば

　Yの1行目は0,1

　2行目は1,0

　そのほかは0,0

　という行列になる。

　また、αは、もとのラベルをどの程度重視するかというパラメータで

　(0,1)の値を持つ

④ラベルを取り出す

　最も確率の高いラベルの列の値が大きくなっているので、

　データ $i$ についてのラベルは、行列 $F$ のi行目の中で、一番値が大きい列ということになる。