ZAWWW-2st1.2-w13.tresc-1.0-Slajd20

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Losowy spacer (2)

Losowy spacer (2)


Niech v oznacza wektor prawdopodobieństw przebywania w dowolnym dokumencie indeksowanej sieci. Stan początkowy wektora v nie ma żadnego znaczenia. Najczęściej inicjalizuje się pozycje wektora v pewną niską wartością, obrazującą jednostajne prawdopodobieństwo rozpoczęcia losowego spaceru w dowolnym dokumencie sieci. Dysponując wektorem v i macierzą stochastyczną M można wyliczyć rozkład prawdopodobieństwa przebywania w każdym dokumencie po wykonaniu jednego kroku, rozkład ten jest dany przez wektor v '= Mv . Zakładając nieskończony ciąg kroków, rozkład prawdopodobieństwa przebywania w dowolnym dokumencie w dowolnej chwili spaceru losowego jest dany przez granicę M(M(M(…M( Mv )…) ) ). A zatem, wektor wynikowy (po nieskończonej liczbie kroków) to wektor własny (ang. principal eigenvector) macierzy M. Wartości tego wektora (czyli prawdopodobieństwa przebywania w dowolnym dokumencie w dowolnej chwili spaceru losowego) nazywamy wartościami PageRank dokumentów. W algorytmie PageRank wartość i-tej pozycji wektora własnego macierzy M stanowi ważność i-tego dokumentu.


<< Poprzedni slajd | Spis treści | Następny slajd >>