PageRankの計算
Posted feedbacks - Haskell
GSLHaskellというライブラリを使った
see: GSLHaskell
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | import Data.Complex
import Data.List
import GSL.LinearAlgebra.Algorithms (eigR)
import GSL.LinearAlgebra.Matrix (fromLists, toColumns)
import GSL.LinearAlgebra.Vector (toList)
testdata = [[2,3,4,5,7],[1],[1,2],[2,3,5],[1,3,4,6],[1,5],[5]]
pageRank = normalize -- 確率ベクトルへの正規化
. map realPart -- 実数部分の取り出し
. toList -- GSLモジュールのベクトルデータからリストに変換
. head -- 最大固有値に対応する固有ベクトルの取り出し
. toColumns -- 固有ベクトルのリストに変換
. snd -- 固有ベクトル(行列データ形式)
. eigR -- 固有値計算
. fromLists -- GSLモジュールの行列データに変換
. transMat -- 遷移確率行列へ変換
. list2mat -- 隣接リストから隣接行列へ変換
list2mat xs = map (fillup [1..genericLength xs]) xs
where fillup xs [] = map (const 0) xs
fillup (x:xs) yys@(y:ys) | x < y = 0 : fillup xs yys
| otherwise = 1 : fillup xs ys
transMat = transpose . map (normalize . map fromInteger)
normalize xs = map (/s) xs where s = sum xs
{-
*Main> pageRank testdata
[0.3035143769968052,0.16613418530351437,0.14057507987220447
,0.10543130990415339,0.17891373801916938,4.4728434504792317e-2
,6.070287539936104e-2]
-}
|
ところてん
#3404()
Rating0/0=0.00
詳しい導出方法はGoogle の秘密 - PageRank 徹底解説の3章に載っていますが、 簡単に説明すると
という流れになります。
Pythonで表現すると下のようになります。 ?????の部分は空行を入れて10行でしたので 何百行ものコードになってしまった場合は きっとお題の趣旨から外れていると思います。 このお題の趣旨は「行列計算ライブラリを使って」PageRankを計算することなので、 自力で固有値の計算を実装することは求められていません。
data = { 1: [2, 3, 4, 5, 7], 2: [1], 3: [1, 2], 4: [2, 3, 5], 5: [1, 3, 4, 6], 6: [1, 5], 7: [5], } ????? print pagerank # [0.303514376997, 0.166134185304, 0.140575079872, # 0.105431309904, 0.178913738019, 0.0447284345048, # 0.0607028753994]このお題はところてんさんの「行列演算系のお題が欲しい」という要望を元に考えたものです。ありがとうございました。[ reply ]