|
Поскольку PageRank, имеет отношение к вероятности просмотра страниц, то для лучшего понимания, стоит обратиться к такому разделу теории случайных процессов как теории Марковских процессов.
Под Марковским процессом подразумевается процесс, для которого вероятность находиться в данном состоянии, на данном этапе процесса можно вывести из информации о предшествующем состоянии. Цепью Маркова называется Марковский процесс, для которого каждое конкретное состояние зависит только от непосредственно предыдущего. Число состояний цепи Маркова конечно, а вероятности перехода из одного состояния в другое не зависят от времени.
Следуя из определения можно сказать, что рассматриваемый нами процесс поведения абстрактного пользователя сети является Марковским, и даже более того, является Цепью Маркова.
Теперь рассмотрим, какие условия определяют цепь Маркова:
Во-первых, у цепи имеется матрица вероятностей перехода:
|
P= |
p11 |
p12 |
...... |
p1N |
|
p21 |
p22 |
...... |
p2N |
|
.................................................. |
|
pN1 |
pN2 |
........ |
pNN |
(3).
где pij – вероятность перехода из состояния i в состояние j за один шаг процесса.
Матрица (3) обладает следующими свойствами:
а) ∑pij = 1 j=1…N. (свойство, вытекающее из замкнутости системы);
б) pij ³ 0 " i,j.
Во-вторых, у цепи Маркова имеется вектор начальных вероятностей, который описывает начальное состояние системы:
P(0) = < P01, P02,..,P0n > (4)
Обозначим шаги (этапы) процесса за t = 0, 1,…..
Если P(0) это вектор начальных вероятностей, то P(t) – это вероятностный вектор на шаге t. Значение P(t+1) зависит от P(t). Формула расчета в матричном виде выглядит следующим образом:
P(t+1) = P(t) ∙P (5).
Отсюда следует, что:
P(t) = P(0) ∙Pt (6).
В теории цепей Маркова показано, что в пределе, при t стремящемся к бесконечности, вероятности состояний стремятся к определенным предельным значениям, которые удовлетворяют соотношению:
P(*)=P(*)∙P (7).
Из (7) становится очевидным, следующее важное свойство предельных векторов вероятностей P(*). Заключается оно в том, что P(*) является единственным и не зависит от вектора начальных вероятностей P(0) и определяются только матрицей вероятностей перехода.
Теперь рассмотрим применение данной теории для системы из нашего примера (Рис. 1. Часть I).
Матрица вероятностей перехода будет выглядеть следующим образом, т.е. также как и матрица при расчете PageRank матричным способом:
|
P= |
A |
B |
C |
D |
|
0 |
1/3 |
1/3 |
1/3 |
|
1 |
0 |
0 |
1 |
|
1 |
0 |
0 |
0 |
|
0 |
1 |
0 |
0 |
(9)
Первая строка матрицы свидетельствует о следующем: со страницы A можно перейти на B, C, и D. Вероятность того, что после A пользователь выберет C равна 1/3. Вероятность выбора D или C тоже равна 1/3.
Вторая строка значит, что со страницы B можно попасть только на A, вероятность этого перехода равна 1. Третья строка – с C можно попасть только на A, вероятность перехода равна 1. Четвертая строка – с D можно попасть только на B, вероятность перехода равна 1.
Для нашей системы вектор начальных вероятностей выглядит следующим образом (поскольку в нашей сети четыре страницы и пользователь может оказаться на люьбой из них с одинаковой вероятностью):
P(0) = < 1/4, 1/4, 1/4, 1/4>.
Для расчета вектора P(1) применим формулу (5), т.е. P(0) умножим на матрицу вероятностей перехода. Получим P(1) = <0,5; 0,3333; 0,0833; 0,0833>.
Для вектора P(2) формула (5) имеет следующий вид: P(2) = P(1) ∙P. После расчета получаем значения P(2) = <0,4167; 0,25; 0,167; 0,167>.
Рассчитывая значения P(t) по формуле (5) мы найдем t, для которого выполняется равенство (7). Т.е. мы рассчитаем значение предельного вектора вероятностей P(*), который не зависит от вектора начальных вероятностей P(0) и определяется только матрицей вероятностей перехода.
В нашем случае P(*) = <0,429; 0,286; 0,143; 0,143>.
Таким образом, после достаточно большого количества переходов со страницы на страницу уже не имеет значения с какой страницы пользователь начал просмотр, поскольку в результате он окажется на странице A с вероятностью 0,429, на странице B с вероятностью 0,286, на страницах C и D с вероятностями 0,143 (или можно сказать, что 42% пользователей будут на странице A, 29% будут на странице B и на страницах C и D будет по 14% посетителей).
Теперь с полученным вектором P(*) произведем следующие действия:
0.85∙4P(*) + (1-0,85)
Проведем расчеты:
Для А: 0,85∙4∙0,429 + 0,15 = 1,607.
Для B: 0,85∙4∙0,286 + 0,15 = 1,12.
Для C: 0,85∙4∙0,143 + 0,15 = 0,635.
Для D: 0,85∙4∙0,143 + 0,15 = 0,635.
Получается что, рассчитав предельный вектор вероятностей P(*), умножив его на единичный вектор, умноженный на 4d, и прибавив к нему единичный вектор, умноженный на (1-d), мы получили значении практически равные значениям PR, рассчитанным в первой части статьи.
Сравним два алгоритма (расчет PageRank матричным способом и нахождение предельного вектора P(*) Цепи Маркова) в общем случае. Различие заключается лишь в том, что при расчете значений PR за начальный берется единичный вектор и вводится зависимость PR от коэффициента затухания. А для расчета P(*) начальный вектор состоит из значений 1/N, где N – количество страниц. Именно поэтому, умножив полученный вектор P(*) на N и d, а также прибавив (1-d) мы получили значения близкие к значениям PR.
Автор: Марченко Светлана
Источник: www.icweb.ru
|
