Page Rank in Python

Question

Sono nuovo di Python, e sto cercando di calcolare Page Rank vettore secondo questa equazione in Python:

Dove Pi (k) la pagina-rank vettore dopo k-esima iterazione, G è la matrice Google, H è matrice ipertestuale un è un vettore nodo penzoloni, alfa = 0,85 e e è vettore di quelli.

Il calcolo con G richiede molto tempo, mentre si utilizza la matrice di collegamento ipertestuale H, che è matrice sparsa, dovrebbe richiedere molto meno tempo.

Ecco il mio codice:

for i in range(1, k_steps+1): 
    for j in range(0, len(dictionary_urls)): 
    for k in range(0, len(dictionary_urls)): 
     if matrix_H[k][j] != 0: 
      matrix_pi_k[i][j] += matrix_pi_k[i-1][k] * float(matrix_H[k][j]) 
     alpha_pi_k_a += matrix_pi_k[i-1][k]*float(vector_a[k]) 

    alpha_pi_k_a = alpha_pi_k_a * float(alpha) 
    alpha_pi_k_a = alpha_pi_k_a + float((1- alpha)) 
    alpha_pi_k_a = alpha_pi_k_a/float(len(dictionary_urls)) 
    matrix_pi_k[i][j] = matrix_pi_k[i][j] * float(alpha) 

    matrix_pi_k[i][j] = matrix_pi_k[i][j] + float(alpha_pi_k_a) 
    alpha_pi_k_a = 0 

k_steps è il numero di iterazioni necessario.

dictionary_links contiene tutti gli URL.

Dopo l'esecuzione di codice, matrix_pi_k dovrebbe avere tutto il vettore Pi

Ho calcolato tutte le variabili che intero. Ho ottenuto un tempo di esecuzione usando la matrice H è quasi uguale al tempo di esecuzione usando la matrice G, anche se, in teoria, dovrebbe essere diverso.

Perché? E cosa dovrei cambiare per ridurre il tempo di esecuzione?

Grazie.

Answer 1

Il problema è che si sta moltiplicando una matrice sparsa con un vettore denso utilizzando lo stesso algoritmo di moltiplicazione di matrice-vettore denso. Non vedrai alcun aumento di velocità in questo modo.

Supponiamo di avere una matrice di nxnA (densa o rada) e un n-vettore x. Per calcolare y = Ax, possiamo scrivere:

y = [0]*n 
for i in range(n): 
    for j in range(n): 
     y[i] += A[i,j]*x[j] 

Questo funziona se la matrice A è densa o rada. Supponiamo, tuttavia, che lo A sia scarso. Continuiamo a eseguire il ciclo su tutte le colonne di A per calcolare una singola voce di , anche se la maggior parte delle voci sarà zero. Quindi il ciclo esterno passa attraverso le iterazioni n e anche il ciclo interno passa attraverso le iterazioni n.

Se noi conosciamo quali voci di A sono diverse da zero, possiamo fare molto meglio. Supponiamo di avere un elenco di tutte le voci diverse da zero della riga i, chiamatelo nonzero[i]. Poi possiamo sostituire il ciclo interno con l'iterazione su questa lista:

y = [0]*n 
for i in range(n): 
    for j in nonzero[i]: 
     y[i] += A[i,j]*x[j] 

Così, mentre il nostro ciclo esterno fa n iterazioni, il ciclo interno fa solo il maggior numero di iterazioni in quanto vi sono elementi non nulli.

Questo è dove la velocità viene con moltiplicazione di matrice-vettore sparse.

Utilizzare numpy!

Ma si ha un altro problema: si sta tentando di eseguire la moltiplicazione della matrice con Python puro, che (a causa di controllo del tipo, strutture di dati non contigue, ecc.) È lento. La soluzione è utilizzare numpy, che fornisce algoritmi e strutture dati veloci. Quindi è possibile utilizzare scipy's sparse matrices, poiché implementano per voi la moltiplicazione vettoriale a matrice sparsa veloce.

Esperimento

Siamo in grado di mostrare tutto questo con un rapido esperimento. Per prima cosa generiamo un 10,000 x 10,000 densa matrice A:

>>> import numpy as np 
>>> n = 10000 
>>> A = np.random.sample((n,n)) 

Poi faremo una matrice sparsa B dalla sogliatura A. B è la stessa dimensione come A, ma solo il 10% delle sue voci sono diversi da zero:

>>> B = np.where(A < .1, A, 0).astype(float) 

Ora faremo un denso vettore di moltiplicare A e B con:

>>> x = np.random.sample(n) 
>>> %timeit A.dot(x) 
10 loops, best of 3: 46.7 ms per loop 
>>> %timeit B.dot(x) 
10 loops, best of 3: 43.7 ms per loop 

Si prende il la stessa quantità di tempo per calcolare Ax come per calcolare Bx, anche se B è "sparse". Ovviamente, non è in realtà sparse: è memorizzato come una matrice densa con un numero di voci pari a zero.Rendiamolo scarso:

>>> sparse_B = scipy.sparse.csr_matrix(B) 
>>> 100 loops, best of 3: 12 ms per loop 

C'è la nostra velocità! Ora, solo per divertimento, cosa succede se memorizziamo A come una matrice sparsa, anche se è davvero denso?

>>> sparse_A = scipy.sparse.csr_matrix(A) 
>>> %timeit sparse_A.dot(x) 
10 loops, best of 3: 112 ms per loop 

Ouch! Ma questo è normale, poiché la memorizzazione di A come matrice sparsa potrebbe comportare un sovraccarico durante la moltiplicazione.

Answer 2

Sulla base della sua formula, calcolo della matrice H non sembra più veloce rispetto a matrice G.

Spiegazione:

Si potrebbe voler dare un'occhiata a un introduction to Big O notation.

La parte più a destra (dopo lo +) nella formula consiste solo in un semplice calcolo senza loop e la sua notazione Big O è solo O(1). Il che significa che non dipende dal numero di URL che stai prendendo in considerazione.

Considerando che entrambi i calcoli per H e G sembrano essere almeno O(n^2) (n è il numero di URL).

Edit:

Nella parte profonda annidata del codice, si hanno due istruzioni, una delle quali è subordinato al fatto che matrix_H[k][j] è 0 o meno. Tuttavia, se è 0, che sarà il caso più spesso se H è una matrice sparsa, la seconda istruzione verrà comunque eseguita. Inoltre, si entra comunque nel ciclo.

Questo ti dà ancora una complessità di O(n^2), quindi l'analisi di H non è (molto) più veloce di analizzare G.