ScalaNLPでPageRankを計算する
Scalaでも科学計算が頑張れば出来るかもしれない
ScalaNLPを使ってPageRankを計算してみる
以前はScalalaって名前だったもの
numpyとのチートシートもある
ちなみにpython分からないから意味が無い.
ひとまず今回は小さいサイズでやってみる.
リンク構造は以下のようなものを想定
人によっては分かりやすいように,pythonのnumpyを使う版と一行ずつ比較してみる.
pythonのコードは研究室の資料から転用.
import breeze.linalg._ import breeze.numerics._ // 推移確率行列 // T = mat('0 0 0 0; 1 0 0.5 0; 0 1 0 0; 0 0 0.5 0') val T = DenseMatrix((.0, .0, .0, .0), (1.0, .0, .5, .0), (.0, 1.0, .0, .0), (.0, .0, .5, .0)) // ダンピングファクター // d = 0.85 val d = 0.85 // ページ数 // N = T.shape[0] val N = T.rows // ページランク初期値 // r = mat([1/N for i in range(N)]).T var r = DenseMatrix(Array.fill(N)(1.0/N)).t // 1_n / N // u = r.copy() val u = r.copy // 反復回数 // m = 20 val m = 20 // m回反復してpagerankを計算する // for i in range(m): // r = d*T*r + (1-d)*u for(i <- 1 to m){ r = d*T*r + (1-d)*u } //結果 //python // matrix([[ 0.0375 ], // [ 0.13356605], // [ 0.15104723], // [ 0.10169105]]) scala> r res52: breeze.linalg.DenseMatrix[Double] = 0.037500000000000006 0.1335660511560121 0.15104723020205457 0.10169105115601212
取り敢えず上手くいくことは分かった.
CSCMatrices are not fully supported yet.って記述があるが,大きいやつで一応挑戦してみよう
疎行列用のクラスを使わずに...
ひとまず手元に6万程のページと12万程のリンクを実データを収集して用意した.
追記
DenseMatrixじゃ余裕で無理ですよねーですよね
なんかJavaのライブラリで疎行列を容量食わずに保管・利用出来るような物を探すことも考慮しよう
la4j - Linear Algebra for JavaやColt - Welcomeが有名所なんだろうか
ひとまずScalaNLPのCSCMatrixがどこまで出来るのか試すとこから.
追記その2
CSCMatrix同士の加算が出来なくて挫折.力及ばず...
d*CSCMatrixについては,そのままじゃ行えないがmapValuesを使うと計算出来る
諦めた結果,ひとまずダンピングファクター無視して計算してみる
val builder = new CSCMatrix.Builder[Double](rows=4, cols=4) builder.add(1,2,3.0) .. val mtx = builder.result var pagerank = CSCMatrix(Array.fill(pageCount)(1.0/pageCount) val d = 0.85 for(i <- 1 to 20){ pagerank = mtx * pagerank } for(key <- pagerank.keyIterator){ save(key, pagerank(key)) }
425秒で6万件ページ,12万件リンクのページランク出すの終わった
いかに疎行列だったかがあれ