PageRankアルゴリズムおよびPython実装(簡潔版)
13912 ワード
簡単に述べる
PageRankは少し神化されていますが、実は公式は簡単です.
文書ディレクトリ概要 アルゴリズム モデル定義 Flowバージョン Google Formula を実現
アルゴリズム#アルゴリズム#
主に2つに分けられます. The ‘Flow’ formula The Google formula
モデル定義
多くのウェブページ、直接リンク関係が存在して、Gに設定して、N*Nのマトリックス
ここではまず,無権無ループ図,すなわちエッジに方向があり,重みが同じであり,自分から自分のエッジ(ループ)に至ることはないことを考慮する. Nはノード数またはページ数 である. G[i][j]=1で表され、i->jにはエッジ がある.
Flowバージョン
r i = ∑ ( j = 1 ) a n d ( j − > i ) N r j d j r_i =\sum_{(j=1) and (j -> i)}^N{\frac{r_j}{d_j}} ri=(j=1)and(j−>i)∑Ndjrj
数学の書き方は
r = M ∗ r r = M * r r=M∗r である.
アルゴリズムの流れ:すなわち、各点のスコア をランダムに初期化する.その後、反復: 各点のスコアは、彼を指すすべてのノードのスコアからこのノードの出度数で除算する によって求められる.
Flowバージョンでは、2つの重要な問題が発生します. Dead End:たとえば2つのポイントしかなく、エッジは Spider Traps:循環指向、例えば を回転します.
Google Formula
さっき言った2つの問題はGoogle Formulaでよく改善されました.はTeleportという概念を提案し、意念転移とも呼ばれる.
簡単です.つまり、各ノードがランダムに任意の点にジャンプする確率がある場合です.さらにMapReduceの概念を結びつけて、Googleはこのようにemmmmを発家しました
r i = β ∗ ∑ ( j = 1 ) a n d ( j − > i ) N r j d j + ( 1 − β ) ∗ 1 N r_i =\beta *\sum_{(j=1) and (j -> i)}^N{\frac{r_j}{d_j}} + (1 -\beta) *\frac{1}{N} ri=β∗(j=1)and(j−>i)∑Ndjrj+(1−β)∗N1
直接的な数学表現:
r = A ∗ r A = β ∗ M + ( 1 − β ) ∗ [ 1 N ] N ∗ N r = A * r\\A =\beta * M + (1-\beta) * [\frac{1}{N}]_{N*N} r=A∗rA=β∗M+(1−β)∗[N1]N∗N
Googleの簡略化された数学表現:
r = β ∗ M ∗ r + [ 1 N ] N r =\beta * M * r + [\frac{1}{N}]_N r=β∗M∗r+[N1]N である.
問題:直接的な数学表現はもっと簡潔になりますが、多くのAは必ず稠密なマトリクスで空間をO(N^2)に消費します.このようにサイトが数億に達する場合、これは現実的ではありません. でGoogleが簡略化したバージョンでは同じまばらなMを記録するだけで、1/Nは1つの数であり、rというベクトルの各要素に加えるだけでよい(簡単な数学変形は、工業的に生じる価値が大きく異なる.数学を研究する兄弟たちに感心する) インプリメンテーション
同じ2つの異なるバージョンを実装します.
共通のモデルがあります
パッケージのインポート:
データの作成:
GtoM: FlowバージョンのPageRank
テスト:
出力: Google Formula
同じデータテストの下:
テスト:
出力:
PageRankは少し神化されていますが、実は公式は簡単です.
文書ディレクトリ
アルゴリズム#アルゴリズム#
主に2つに分けられます.
モデル定義
多くのウェブページ、直接リンク関係が存在して、Gに設定して、N*Nのマトリックス
ここではまず,無権無ループ図,すなわちエッジに方向があり,重みが同じであり,自分から自分のエッジ(ループ)に至ることはないことを考慮する.
Flowバージョン
r i = ∑ ( j = 1 ) a n d ( j − > i ) N r j d j r_i =\sum_{(j=1) and (j -> i)}^N{\frac{r_j}{d_j}} ri=(j=1)and(j−>i)∑Ndjrj
数学の書き方は
r = M ∗ r r = M * r r=M∗r
i->j,M[j][i]=1/djがある場合、NOは0 アルゴリズムの流れ:
A->Bで、BはDead ENDです.この時になって点数が出なくなった.A->B->A.では、この点数はこの間Google Formula
さっき言った2つの問題はGoogle Formulaでよく改善されました.
簡単です.つまり、各ノードがランダムに任意の点にジャンプする確率がある場合です.さらにMapReduceの概念を結びつけて、Googleはこのようにemmmmを発家しました
r i = β ∗ ∑ ( j = 1 ) a n d ( j − > i ) N r j d j + ( 1 − β ) ∗ 1 N r_i =\beta *\sum_{(j=1) and (j -> i)}^N{\frac{r_j}{d_j}} + (1 -\beta) *\frac{1}{N} ri=β∗(j=1)and(j−>i)∑Ndjrj+(1−β)∗N1
直接的な数学表現:
r = A ∗ r A = β ∗ M + ( 1 − β ) ∗ [ 1 N ] N ∗ N r = A * r\\A =\beta * M + (1-\beta) * [\frac{1}{N}]_{N*N} r=A∗rA=β∗M+(1−β)∗[N1]N∗N
Googleの簡略化された数学表現:
r = β ∗ M ∗ r + [ 1 N ] N r =\beta * M * r + [\frac{1}{N}]_N r=β∗M∗r+[N1]N
i->j,M[j][i]=1/djがある場合、NOは0 問題:
同じ2つの異なるバージョンを実装します.
共通のモデルがあります
パッケージのインポート:
import numpy as np
import random
データの作成:
def create_data(N, alpha=0.5): # random > alpha, then here is a edge.
G = np.zeros((N, N))
for i in range(N):
for j in range(N):
if i == j:
continue
if random.random() < alpha:
G[i][j] = 1
return G
G = create_data(10)
GtoM:
def GtoM(G, N):
M = np.zeros((N, N))
for i in range(N):
D_i = sum(G[i])
if D_i == 0:
continue
for j in range(N):
M[j][i] = G[i][j] / D_i # watch out! M_j_i instead of M_i_j
return M
M = GtoM(G, 10)
def PageRank(M, N, T=300, eps=1e-6):
R = np.ones(N) / N
for time in range(T):
R_new = np.dot(M, R)
if np.linalg.norm(R_new - R) < eps:
break
R = R_new.copy()
return R_new
テスト:
values = PageRank(M, 10, T=2000)
values
出力:
array([0.09972576, 0.09193927, 0.07843151, 0.09125886, 0.08925602,
0.10407245, 0.09623654, 0.13851257, 0.13086464, 0.07970237])
def PageRank(M, N, T=300, eps=1e-6, beta=0.8):
R = np.ones(N) / N
teleport = np.ones(N) / N
for time in range(T):
R_new = beta * np.dot(M, R) + (1-beta)*teleport
if np.linalg.norm(R_new - R) < eps:
break
R = R_new.copy()
return R_new
同じデータテストの下:
テスト:
values = PageRank(M, 10, T=2000)
values
出力:
array([0.09815807, 0.09250429, 0.08376235, 0.09300133, 0.09324628,
0.10108776, 0.09855127, 0.13019363, 0.12458992, 0.0849051 ])