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万件リンクのページランク出すの終わった
いかに疎行列だったかがあれ