PageRank Python-Implementierung, Algorithmus

Question

Ich versuche, diese matlab implementation in Python zu schreiben, aber ich verstehe nicht, ein paar Momente:

last_v = Einsen (N, 1) * inf;

Erhalten wir hier einen Vektor, der alle Unendlichkeiten enthält? In diesem Fall, während die Bedingung sofort falsch und wir erhalten keine Wiederholungen:

während (norm (v - last_v, 2)> v_quadratic_error)

Was verstehe ich falsch machen ?

Dies ist die Art und Weise ist, habe ich versucht, es zu tun:

from numpy import * 
def pagerank(M,d,v_quadratic_error): 
count = 0 
N=M.shape[1] 
v=random.rand(N,1) 
v=v/linalg.norm(v) 
ainf=array([[inf]]) 
last_v = dot(ones((N,1)),ainf) 
R = d*M + ((1-d)/N * ones((N,N))) 
while linalg.norm(v-last_v,2) > v_quadratic_error: 
    last_v = v 
    v = dot(R,v) 
    count+=1 
    print 'iteration #', count 
return v 

Answer 1

In Matlab/Octave:

octave:4> last_v = ones(N, 1) * inf; 
octave:10> norm(v - last_v, 2) 
ans = Inf 
octave:13> norm(v - last_v, 2) > v_quadratic_error 
ans = 1 

In Python:

In [139]: last_v = np.dot(np.ones((N,1)),ainf) 
In [140]: np.linalg.norm(v - last_v, 2) 
Out[140]: nan 
In [141]: np.linalg.norm(v - last_v, 2) <= v_quadratic_error 
Out[141]: False 

So ist die Bedingung wahr in Matlab/Octave, aber der ähnlichen Ausdruck in Python ist False. In Python statt

while linalg.norm(v-last_v,2) > v_quadratic_error: 

verwendet, könnte man

while True: 
    last_v = v 
    ... 
    if np.linalg.norm(v - last_v, 2) <= v_quadratic_error: break 

verwenden Dies garantiert, dass der Ablauf der Ausführung des while-loop mindestens einmal eintritt, und dann bricht, wenn die Bedingung wahr ist. Zu diesem Zeitpunkt wird last_v einen endlichen Wert haben, so dass das Problem NaN versus Inf vermieden wird.

---

import numpy as np 

def pagerank(M, d, v_quadratic_error): 
    count = 0 
    N = M.shape[1] 
    while True: 
     v = np.random.rand(N, 1) 
     if (v != 0).all(): break 
    v = v/np.linalg.norm(v) 
    R = d * M + ((1 - d)/N * np.ones((N, N))) 
    while True: 
     last_v = v 
     v = np.dot(R, v) 
     count += 1 
     print('iteration # {}: {}'.format(count, np.isfinite(v))) 
     if np.linalg.norm(v - last_v, 2) <= v_quadratic_error: break 
    return v 

M = np.array(np.mat('0 0 0 0 1 ; 0.5 0 0 0 0 ; 0.5 0 0 0 0 ; 0 1 0.5 0 0 ; 0 0 0.5 1 0')) 
print(pagerank(M, 0.80, 0.001)) 

Ausbeuten (so etwas wie)

[[ 0.46322263] 
[ 0.25968575] 
[ 0.25968575] 
[ 0.38623472] 
[ 0.48692059]] 

Answer 2

Ja, Sie haben Recht, wird die Linie um einen Vektor von Unendlichkeiten zu ergeben. Man könnte inf auch direkt verwenden: https://de.mathworks.com/help/matlab/ref/inf.html ->inf(N,1).

Der Zustand wird aber nicht falsch ergeben, warum sollte es? Bitte werfen Sie einen Blick auf die euklidische Norm: https://en.wikipedia.org/wiki/Euclidean_distance -> Die Norm eines Vektors von inf des (subtrahierte durch einige zufällige Werte, die effektiv noch einen Vektor von Infs nachgeben) wird inf Ausbeute wieder, so

inf > v_quadratic_error 

wird wahr sein. Innerhalb der Schleife wird last_v überschrieben, und daher wird es in den nächsten Iterationen konvergieren.