Вычисление вероятностей путешествия с помощью умножения матриц

СТАТЬЯ

Вычисление вероятностей путешествия с помощью умножения матриц

Из Книжного лагеря по Data Science Леонарда Апельцина

В этой статье обсуждается, как смоделировать имитацию трафика и вычислить вероятность путешествия.

Получите скидку 40% на Data Science Bookcamp, введя fccapeltsin в поле кода скидки при оформлении заказа на manning.com.

Наше моделирование трафика можно смоделировать математически, используя матрицы и векторы. Мы разделим этот процесс на простые, управляемые части. Рассмотрим, например, машину, которая собирается выехать из города 0 в один из соседних городов. Есть G.degree(0) соседние города на выбор. Следовательно, вероятность путешествия из города 0 в любой соседний город равна 1 / G.degree(0). Ниже мы вычислим эту вероятность.

Листинг 1. Расчет вероятности поездки в соседний город

num_neighbors = G.degree(0)
 prob_travel = 1 / num_neighbors
 print("The probability of traveling from Town 0 to one of its "
       f"{G.degree(0)} neighboring towns is {prob_travel}")

Вероятность путешествия из города 0 в один из 5 соседних городов составляет 0,2.

Если мы находимся в Городе 0, а Город i - это соседний город, то с вероятностью 20% мы путешествуем из города 0 в Город i. Конечно, если город i не является соседним городом, то вероятность падает до нуля. Мы можем отслеживать вероятности для всех возможных i, используя вектор v. Значение v[i] будет равно 0,2, если i находится в G[0], и 0 в противном случае. Вектор v называется вектором перехода, поскольку он отслеживает вероятность перехода из города 0 в другие города. Есть несколько способов вычислить вектор перехода. Мы могли бы:

Запустите np.array ([0.2, если i в G [0] иначе 0 для i в G.nodes])

Каждый элемент ith будет равен 0,2, если i находится в G[0], и 0 в противном случае.

Запустите np.array ([1, если i в G [0], иначе 0 для i в G.nodes]) * 0.2.

Здесь мы просто умножаем 0.2 на двоичный вектор, который отслеживает наличие или отсутствие ребер, связанных с G[0].

Выполните M[:,0] * 0.2, где M - матрица смежности.

Каждый столбец матрицы смежности отслеживает двоичное присутствие или отсутствие ребер между узлами. Следовательно, столбец 0 M будет равен массиву в предыдущем примере.

Третье вычисление - самое простое. Конечно, 0.2 равно 1 / G.degree(0). Как мы обсуждали в начале этого раздела, степень также может быть вычислена путем суммирования по столбцу матрицы смежности. Таким образом, мы также можем вычислить вектор перехода, запустив M[:,0] / M[:,0].sum().

Давайте вычислим вектор перехода, используя все перечисленные методики.

В настоящее время матрица смежности M хранится с переменной adjacency_matrix. Однако эта матрица не учитывает удаленную границу между Городом 3 и Городом 9. Следовательно, мы пересчитаем матрицу, запустив adjacency_matrix = nx.to_numpy_array(G).

Листинг 2. Вычисление вектора перехода

transition_vector = np.array([0.2 if i in G[0] else 0 for i in G.nodes])
  
 adjacency_matrix = nx.to_numpy_array(G) (1)
 v2 = np.array([1 if i in G[0] else 0 for i in G.nodes]) * 0.2
 v3 = adjacency_matrix[:,0] * 0.2
 v4 = adjacency_matrix[:,0] / adjacency_matrix[:,0].sum() (2)
  
 for v in [v2, v3, v4]:
     assert np.array_equal(transition_vector, v) (3)
  
 print(transition_vector)

❶ Мы повторно вычисляем матрицу смежности, чтобы учесть ранее удаленное ребро.

❷ Здесь мы вычисляем вектор перехода непосредственно из столбца матрицы смежности.

❸ Здесь мы вычисляем вектор перехода непосредственно из столбца матрицы смежности.

[0.  0.  0.  0.2 0.2 0.  0.2 0.2 0.  0.  0.  0.  0.  0.2 0.  0.  0.  0.
  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0.  0. ]

Мы можем вычислить вектор перехода для любого Town i, запустив M[:,i] / M[:,i].sum(), где M - матрица смежности. Более того, мы можем вычислить все эти векторы одновременно, запустив M / M.sum(axis=0). Операция делит каждый столбец матрицы смежности на соответствующую степень. Конечным результатом является матрица, столбцы которой соответствуют векторам переходов. Эта матрица называется матрицей перехода. Матрицу также обычно называют матрицей Маркова в честь Андрея Маркова, российского математика, изучавшего случайные процессы. Теперь вычислим матрицу перехода. Исходя из наших ожиданий, нулевой столбец нашего результата должен соответствовать Town 0’s transition_vector.

Листинг 3. Вычисление матрицы перехода

transition_matrix = adjacency_matrix / adjacency_matrix.sum(axis=0)
 assert np.array_equal(transition_vector, transition_matrix[:,0])

Наша матрица переходов обладает замечательным свойством. Это позволяет нам вычислить вероятность путешествия в каждый город всего за несколько строк кода! Если мы хотим узнать вероятность оказаться в Town i после 10 остановок, нам просто нужно:

Инициализируйте вектор v, где v равно np.ones(31) / 31.
Обновите v до значения transition_matrix @ v за 10 итераций.
Вернуть v[i].

Позже мы создадим это удивительное свойство с нуля. А пока давайте докажем наши утверждения, вычислив вероятности путешествия в Города 12 и 3 с помощью матричного умножения. Мы ожидаем, что эти вероятности равны 0.051 и 0.047, исходя из наших предыдущих наблюдений.

Листинг 4. Вычисление вероятностей путешествия с использованием матрицы перехода

v = np.ones(31) / 31
 for _ in range(10):
     v = transition_matrix @ v
  
 for i in [12, 3]:
     print(f"The probability of winding up in Town {i} is {v[i]:.3f}.")

Наши ожидания подтверждаются. Мы можем смоделировать транспортный поток, используя серию умножений матриц. Эти умножения служат основой для определения центральности PageRank, что является наиболее выгодным показателем важности узлов в истории. Центральное место в рейтинге страниц было изобретено основателями Google. Они использовали его для ранжирования веб-страниц, моделируя онлайн-путь пользователя как серию случайных щелчков по интернет-графику. Эти переходы по страницам аналогичны автомобилю, который проезжает по случайно выбранным городам. Более популярные веб-страницы имеют более высокую вероятность посещения. Это понимание позволило Google обнаруживать релевантные веб-сайты полностью автоматически. Таким образом, Google смогла превзойти своих конкурентов и стать компанией с оборотом в триллион долларов. Иногда наука о данных может хорошо окупаться.

Центральность PageRank легко вычислить, но не так-то просто вывести. Тем не менее, используя базовую теорию вероятностей, мы можем продемонстрировать, почему повторяющиеся умножения на 35_ прямо дают вероятности перемещения.

Расчет центрального рейтинга страниц с помощью NetworkX

Функция вычисления центральности PageRank включена в NetworkX. Вызов nx.pagerank(G) вернет сопоставление словаря между идентификаторами узлов и их значениями центральности. Напечатаем центральное значение PageRank для Town 12. Будет ли оно равно 0,051?

Листинг 5. Расчет центрального рейтинга страниц с помощью NetworkX

centrality = nx.pagerank(G)[12]
 print(f"The PageRank centrality of Town 12 is {centrality:.3f}.")
 The PageRank centrality of Town 12 is 0.048.

Напечатанное значение PageRank составляет 0,048, что немного ниже ожидаемого. Разница связана с небольшой настройкой, которая обеспечивает работу PageRank во всех возможных сетях. Напомним, что PageRank изначально предназначался для моделирования случайных кликов с помощью графа веб-ссылок. Граф веб-ссылок имеет направленные ребра, что означает, что некоторые веб-страницы могут не иметь исходящих ссылок. Таким образом, интернет-пользователь может застрять на тупиковой странице, если он полагается на исходящие ссылки для перемещения по сети. Чтобы противостоять этому, разработчики PageRank предположили, что пользователь в конечном итоге устанет нажимать веб-ссылки. Затем этот пользователь перезапустил бы свое путешествие, перейдя на совершенно случайную веб-страницу. Другими словами, они телепортируются к одному из len(G.nodes) узлов интернет-графа. Разработчики PageRank запрограммировали телепортацию на 15% трансверсальных случаев. Телепортация гарантирует, что пользователь никогда не застрянет на узле без исходящих ссылок.

В нашем примере с дорожной сетью телепортация аналогична вызову службы вертолета. Представьте, что в 15% посещений города нам надоедает местность. Затем мы вызываем вертолет, который прилетает и уносит нас в совершенно случайный город. В воздухе наша вероятность долететь до любого города равна 1 / 31. После приземления мы арендуем машину и продолжаем путь по существующей сети дорог. Следовательно, в 15% случаев мы летаем из города i в города j с вероятностью 1 / 31. В остальных 85% случаев мы поедем из города i в города j с вероятностью transition_matrix[j][i]. Следовательно, фактическая вероятность путешествия равна средневзвешенному transition_matrix[j][i] и 1 / 31. Соответствующие веса 0.85 и 0.15. Мы можем вычислить средневзвешенное значение, используя функцию np.average. Мы также можем вычислить это значение напрямую, запустив 0.85 * transition_matrix[j][i] + 0.15 / 31.

Взяв средневзвешенное значение по всем элементам матрицы перехода, вы получите совершенно новую матрицу перехода. Давайте введем эту новую матрицу в нашу compute_stop_likelihoods функцию. После этого мы напечатаем вероятность нового путешествия Town 12. Мы ожидаем, что эта вероятность снизится с 0,051 до 0,048.

Листинг 6. Включение случайной телепортации в нашу модель

new_matrix = 0.85 * transition_matrix + 0.15 / 31 (1)
 stopiprobabilities = compute_stop_likelihoods(new_matrix, 10)
  
 prob = stopiprobabilities[12]
 print(f"The probability of winding up in Town 12 is {prob:.3f}.")

❶ Мы умножаем transition_matrix на 0.85 , а затем прибавляем 0.15 / 31 к каждому элементу. См. Раздел 13 для более подробного обсуждения арифметических операций над 2D-массивами NumPy.

Вероятность оказаться в Городе 12 - 0,048.

Наш новый результат согласуется с результатом NetworkX. Останется ли этот результат стабильным, если мы увеличим количество остановок с 10 до 1000? Давайте разберемся. Мы введем 1000 стопов в compute_stop_likelihoods. После этого мы проверим, равен ли PageRank Town 12 по-прежнему 0,048.

Листинг 7. Вычисление вероятности после 1000 остановок

prob = compute_stop_likelihoods(new_matrix, 1000)[12]
 print(f"The probability of winding up in Town 12 is {prob:.3f}.")
 The probability of winding up in Town 12 is 0.048.

Центральность по-прежнему равна 0,048. Десяти итераций было достаточно для сходимости к стабильному значению. Почему это так? Что ж, наше вычисление PageRank - это не что иное, как многократное умножение матрицы и вектора. Все элементы умноженного вектора имеют значения от 0 до 1. Возможно, это звучит знакомо. Наше вычисление PageRank почти идентично алгоритму степенной итерации, который мы представили в Разделе 14. Степенная итерация многократно берет произведение матрицы и вектора. В конце концов, произведение сходится к собственному вектору матрицы. Напоминаем, что собственный вектор v матрицы M - это специальный вектор, где norm(v) == norm(M @ v). Обычно для достижения сходимости достаточно десяти итераций. Следовательно, наши значения PageRank сходятся, потому что мы проводим мощную итерацию! Кроме того, это доказывает, что наш вектор центральности является собственным вектором матрицы перехода. Таким образом, центральность PageRank необъяснимо связана с красивой математикой, лежащей в основе уменьшения размеров.

Для любого графика G мы вычисляем его центральные позиции в рейтинге страниц, используя следующую последовательность шагов:

Сначала мы получаем матрицу смежности графа M.
Затем мы преобразуем матрицу смежности в матрицу перехода, запустив M = M / M.sum(axis=0).
Впоследствии мы обновляем M, чтобы разрешить случайную телепортацию. Это делается путем взятия средневзвешенного значения M и 1 / n, где n равно количеству узлов в графе.

Обычно веса устанавливаются на 0,85 и 0,15. Следовательно, средневзвешенное значение равно 0.85 * M + 0.15 / n.

Наконец, мы возвращаем наибольший (и единственный) собственный вектор M.

Мы можем вычислить собственный вектор, запустив v = M @ v примерно через 10 итераций. Первоначально для вектора v задано значение np.ones(n) / n.

Марковские матрицы связывают теорию графов с теорией вероятностей и теорией матриц. Кроме того, их можно использовать для кластеризации сетевых данных с помощью процедуры, называемой марковской кластеризацией.

ДЛЯ СПРАВКИ: Общие вычисления централизованности NetworkX:

G.in_degree(i): возвращает внутреннюю степень узла i в ориентированном графе.

G.degree(i): возвращает степень узла i в неориентированном графе.

nx.pagerank(G): возвращает сопоставление словаря между идентификаторами узлов и их центральным рейтингом PageRank.

Это все для этой статьи.

Если вы хотите узнать больше о книге, вы можете ознакомиться с ней на нашей браузерной платформе liveBook здесь.

Вычисление вероятностей путешествия с помощью умножения матриц

СТАТЬЯ