Привет, Хабр!
На связи участник профессионального сообщества NTA Кухтенко Андрей.
В интернете постоянно что‑то рекомендуют: посмотреть новое видео, добавить друга или купить товар. Как работают эти алгоритмы, расскажу в посте ниже и реализую рекомендательную систему с помощью графов.
Принцип работы
Начну с разбора принципа работы рекомендательной системы на основе графов.
Представим граф:
Алгоритм анализирует существующие связи и на их основе предлагает соединить вершины, которые не связаны ребром, например, так:
В публикации опишу три алгоритма, которые позволяют выявлять вероятные связи.
Анализ датафрейма и подготовка данных
Для анализа буду использовать датасет связей героев «Игры престолов»:
https://www.kaggle.com/code/mmmarchetti/game‑of‑thrones‑network‑analysis/input
Представлю, что сагу написал не Дж. Мартин, а какой‑нибудь идеалист, живущий в мире розовых пони, где все сосуществуют в мире и согласии, а связи в датасете отображают наличие дружбы между персонажами. Попробую выбрать одного из них и найти для него новых друзей.
Импорт библиотек. Работать буду с networkx:
import networkx as nx
import pandas as pd
import random
import operatorСоздание графа:
g = nx.Graph()Загружаю данные в датафрейм:
df = pd.read_csv('got_df.txt')
df
Беру только поля Source, Target. Поле Type указывает на направленность графа (в моём случае все ненаправленные), weight — это прочность связи, для задачи предлагаю игнорировать этот параметр, book — порядковый номер книги.
Создаю граф:
edges= df[['Source', 'Target']].values.tolist()
graph = nx.Graph(edges)
nodes = len(graph.nodes()) Посчитаю количество друзей у каждого персонажа и выведу список по убыванию:
friends_cnt = {x:len(graph[x]) for x in graph.nodes()}
sorted_desc = sorted(friends_cnt.items(), key=operator.itemgetter(1), reverse = True)
sorted_desc
Самыми общительными оказались семейство Ланнистеров, с затесавшимся среди них Джоном Сноу. Очевидно, им помощь не нужна. Попробую найти более скромного персонажа с проблемами в общении. На ум приходит немногословный, но добрый великан Ходор:
Одиннадцать друзей — не густо, особенно по сравнению с лидерами. Подходит.
Для начала присвою каждому персонажу индекс и создам граф на основе этих индексов.
mapping = {node:idx for idx, node in enumerate(graph.nodes())}
mapped_graph = nx.Graph()
for edge in graph.edges():
mapped_graph.add_edge(mapping[edge[0]], mapping[edge[1]])
mapping_reverse = dict((v,k) for k,v in mapping.items()) Конвертирую граф в словарь формата ID персонажа: [ID персонажей друзей]:
dict_graph = nx.convert.to_dict_of_lists(mapped_graph)Узнаю индекс Ходора:
mapping['Hodor']Ответ — 78.
Объявляю переменную person и присваиваю ей значение, равное индексу Ходора:
person = 78Подготовка завершена, приступаю к реализации.
Алгоритм 1 – Подсчет количества общих соседей
Получаю список соседей исследуемой вершины, а затем сравниваю со списком соседей каждой другой вершины на расстоянии через одну. Чем больше общих соседей, тем больше вероятность наличия не выявленной связи.
Пишу функцию:
def neights_count(graph, node):
'''Список для сохранения результата подсчета соседей'''
cnt_neis = [0] * len(graph)
'''Список соседей исследуемой вершины'''
node_neighbours = set(graph[node])
'''Словарь для списка вершин, не связанных с node, и их соседей'''
after_one_neigh_dict = {}
'''Заполнение словаря after_one_neigh_dict'''
for u in graph[node]:
for v in graph[u]:
after_one_neigh_dict[v] = graph[v]
'''Проход по вершинам в двух шагах от целевой
Поиск пересечений списков соседей'''
for i in after_one_neigh_dict:
check = len(set(after_one_neigh_dict[i]) & node_neighbours)
cnt_neis[i] = check
'''Зануление результата для исследуемой вершины и ее реальных соседей'''
cnt_neis[node] = 0
for neigh in graph[node]:
cnt_neis[neigh] = 0
return cnt_neisПолучаю топ-10 вершим с наибольшим количеством соседей:
nc = neights_count(dict_graph, person)
nc_ans = {}
for ind, el in enumerate(nc):
nc_ans[mapping_reverse[ind]] = el
nc_ans_sorted = sorted(nc_ans.items(), key=lambda x: x[1], reverse = True)[:10]
nc_ans_sorted
Лидер — Теон Грейджой, он знаком с семью из одиннадцати друзей Ходора.
Алгоритм 2 – Подсчет среднего количества шагов, которое требуется для достижения какой-либо вершины из исследуемой
Запускаю несколько случайных блужданий N из исследуемой вершины, в каждом блужданий фиксируем номер шага, на котором в первый раз была достигнута конкретная вершина. Количество шагов также ограничено, если вершина не была достигнута, то ставится максимум, указанный в ограничении.
Случайное блуждание — набор случайных переходов из одной вершины в другую (в том числе, возможен возврат в ту вершину из которой совершён переход).
Для сохранения результата будем использовать следующий метод — например, я хочу найти расстояния из вершины 1, совершив 10 случайных блужданий с шагом N=3 для следующего графа:
Создаю таблицу для фиксации результата:
В строке «Шаг достижения» увеличиваю значение в ячейке на номер шага, в который вершина была достигнута впервые.
В строке «К блужданий, когда достигнута» — если в текущем блуждании вершина была достигнута, то увеличиваем значение для этой вершины на 1.
Первое блуждание:
Вершина 1 достигнута на шаге 0, вершина 4 — на шаге 1 (увеличиваем значение в ячейке на 1: 0 + 1 = 1), вершина 6 — на шаге 2 (увеличиваем значение в ячейке на 2: 0 + 2 = 2) и вершина 7 — на шаге 3 (увеличиваем значение в ячейке на 3: 0 + 3 = 3). Для всех вершин при каждом первом вхождении увеличиваю значение на 1 в строке «К блужданий, когда достигнута».
Второе блуждание:
Вершина 1 достигнута на шаге 0, вершина 3 — на шаге 1, вершина 2 — на шаге 2 и на шаге 3 произошел возврат в вершину 3, но она уже была посещена в этом блуждании, значит значение не меняем. Для всех вершин при каждом первом вхождении увеличиваем значение на 1 в строке «К блужданий, когда достигнута».
Третье блуждание:
Вершина 1 достигнута на шаге 0, вершина 4 — на шаге 1, вершина 6 — на шаге 2 и вершина 7 — на шаге 3. Для всех вершин при каждом первом вхождении увеличиваю значение на 1 в строке «К блужданий, когда достигнута».
Повторяю еще 7 раз, смотрю результат:
Итак, вершина 1 достигнута 10 раз, что естественно, потому что я с нее начинал.
Четыре вершины достигнуты по 5 раз — 2,3,4,6
Пятая вершина — 3 раза, седьмая — 2 и восьмая ни разу.
Но для подсчета среднего количества шагов нужно указать одинаковое количество блужданий для каждой вершины. Для этого, если в блуждании вершина не была достигнута, то считаю для нее количество шагов, равное N — в моём случае, трём. Например, вершина 2 была достигнута 5 раз, значит не достигнута: 10 — 5 = 5 раз, для каждого из них количество шагов равно максимуму (3): 5 * 3 = 15, прибавляю 15 к результату: 10 + 15 = 25, в строке «К блужданий, когда достигнута» ставим 10 — это общее количество блужданий:
Делаю то же самое для остальных вершин:
Делю «Шаг достижения» на К блужданий, получаю среднее количество шагов:
Ближайшие вершины — 3 и 4, но они нас не интересуют, так как уже являются соседями.
Далее идут вершины 2 и 6, значит можно предположить наличие таких ребер:
Реализую в Python.
Код
def from_distance(graph, node, time=15, samples = 50):
'''Список для сохранения результата'''
from_dist = [0] * nodes
'''Список для подсчета количества раз достижения вершин'''
ach_times = [0] * nodes
'''Список для суммы порядковых номеров шагов при достижении'''
used = [0] * nodes
'''Совершение блужданий'''
for iter in range(samples):
u = node
'''Список вершин, посещенных в блуждании'''
visited_nodes = []
for step in range(time):
'''Выбор случайной вершины из числа соседних'''
next_node = random.choice(graph[u])
'''Проверка наличия вершины в списке посещенных'''
if next_node not in visited_nodes:
'''Если вершина не посещена'''
'''Увеличение значения суммы шагов для текщей вершины'''
used[next_node] += step + 1
'''Увеличение значения в списке для фиксации количества
блужданий, в которых была достигнута вершина'''
ach_times[next_node] += 1
'''Добавление вершины в список посещенных
вершин в текущем блуждании'''
visited_nodes.append(next_node)
u = next_node
'''Для каждой вершины считаем количество блужданий, в которые она не была посещена'''
plus_to_used = [(samples - el)*time for el in ach_times]
'''Вычисляем среднее количество шагов для каждой вершины'''
from_dist = [el/samples for el in list(map(sum, zip(used,plus_to_used)))]
'''Для исследуемой вершины и ее соседей проставляем максимальное количество шагов'''
from_dist[node] = time*samples
for neigh in graph[node]:
from_dist[neigh] = time*samples
return from_distТоп-10 вершин с наименьшим количеством шагов:
fd = from_distance(dict_graph, person)
fd_ans = {}
for ind, el in enumerate(fd):
fd_ans[mapping_reverse[ind]] = el
fd_ans_sorted = sorted(fd_ans.items(), key=lambda x: x[1], reverse = False)[:10]
fd_ans_sorted
Ближайшими вершинами снова оказались Теон Грейджой и Джон Сноу. Необходимо отметить, что поскольку блуждания случайные, результаты могут немного отличаться при каждом запуске функции, также они зависят от количества блужданий и шагов.
Алгоритм 3 – Подсчет среднего количества шагов, которое требуется для достижения исследуемой вершины из всех остальных
Для расчёта расстояний используется рекурсивная формула:
где N – номер шага,
(v) – текущая вершина,
|N(v)| - количество соседей вершины.
Для каждой вершины можно вычислить расстояние до исследуемой вершины, если знаю все расстояния до исследуемой вершины для всех вершин, которые находятся к ней ближе.
В качестве примера буду использовать тот же граф:
Для оптимизации вычислений можно использовать матрицу номер вершины x шаг от исследуемой вершины.
Для исследуемой вершины значение всегда будет равно 0.
Осуществляю вычисления для N = 1.
Вершина 1 = всегда 0.
Вершина 2 = 1 + 1/1 * 1 = 2, у вершины 1 сосед (вершина 3), N-1 для соседа равен 1.
Вершина 3 = 1 + 1/2 * (0+1) = 1,5, у вершины 2 соседа (вершины 1,2), N-1 для соседа 1 равен 0, N-1 для соседа 2 равен 1.
Вершина 4 = 1 + 1/2 * (0+1) = 1,5, у вершины 2 соседа (вершины 1,6), N-1 для соседа 1 равен 0, N-1 для соседа 6 равен 1.
Вершина 5 = 1 + 1/2 * (1+1) = 2, у вершины 2 соседа (вершины 6,7), N-1 для соседа 6 равен 1, N-1 для соседа 7 равен 1.
Вершина 6 = 1 + 1/3 * (1+1+1) = 2, у вершины 3 соседа (вершины 4,5,7), N-1 для соседа 4 равен 1, N-1 для соседа 5 равен 1, N-1 для соседа 7 равен 1.
Вершина 7 = 1 + 1/3 * (1+1+1) = 2, у вершины 3 соседа (вершины 5,6,8), N-1 для соседа 5 равен 1, N-1 для соседа 6 равен 1, N-1 для соседа 8 равен 1.
Вершина 8 = 1 + 1/1 * 1 = 2, у вершины 1 сосед (вершина 7), N-1 для соседа 7 равен 1.
По этому же принципу заполняю остальные столбцы:
Минимальные расстояния у вершин 3 и 4, но это соседи исследуемой вершины‑ их не учитываю.
Далее следуют вершины 2 и 6 — 3 и 3,67 соответственно. Опять выходит такая же картина, что и в предыдущем алгоритме:
Но так случается далеко не всегда.
Реализую в Python:
def to_distance(graph, node, time=10):
'''Формируем матрицу, наполняем нулями'''
martix = [[0 for _ in range(nodes)] for _ in range(time + 1)]
'''Цикл расчетов'''
for t in range(1, time + 1):
'''Проверка каждой вершины'''
for curr_node in range(nodes):
'''Если текущая вершина равна исследуемой, то пропускаем'''
if curr_node == node:
continue
'''Если не исследуемая'''
if graph[curr_node]:
'''Для первого шага всем ставим 1'''
'''Для остальных делаем расчет по формуле'''
if t == 1:
martix[t][curr_node] = 1
else:
prev_t_sum = 0
node_nei = graph[curr_node]
for prev_node in node_nei:
prev_t_sum += martix[t - 1][prev_node]
martix[t][curr_node] = 1 + (1/len(node_nei))
'''Для исследуемой вершины и ее соседей проставляем максимальное количество шагов'''
martix[time][node] = time
for neigh in graph[node]:
martix[time][neigh] = time
return martix[time] Топ-10 вершин с наименьшим количеством шагов:
td = to_distance(dict_graph, person)
td_ans = {}
for ind, el in enumerate(td):
td_ans[mapping_reverse[ind]] = el
td_ans_sorted = sorted(td_ans.items(), key=lambda x: x[1], reverse = False)[:10]
td_ans_sorte
А вот тут Теон даже не входит в топ-10, зато остался Джон Сноу, скорее всего, это первый кандидат на дружбу с Ходором.
Объединение результатов работы алгоритмов
def normalize_list(lst, reverse=False):
min_val = min(lst)
max_val = max(lst)
if reverse:
normalized_list = [1 - (x - min_val) / (max_val - min_val) for x in lst]
else:
normalized_list = [(x - min_val) / (max_val - min_val) for x in lst]
return normalized_list</code></pre><!--EndFragment-->
norm_nc = normalize_list(nc, True)
norm_fd = normalize_list(fd)
norm_td = normalize_list(td)Затем объединяю результаты:
def combine_ans(data1, data2, data3):
return [x + y + z for x,y,z in zip(data1,data2,data3)] ca = combine_ans(norm_nc,norm_fd,norm_td)
comb_ans = {}
for ind, el in enumerate(ca):
comb_ans[mapping_reverse[ind]] = el
comb_ans_sorted = sorted(comb_ans.items(), key=lambda x: x[1], reverse = False)[:10]
comb_ans_sorted
Итак, нашлось десять персонажей, с которыми может подружиться Ходор. Половину из них составляют члены семейства Старк — вполне логично, учитывая его заботу о Бране, также есть Тирион Ланнистер — он, похоже, дружит со всеми и Сэм Тарли — друг Джона Сноу. Позабавило наличие Рамзи Сноу, видимо, существуют какие‑то неявные связи. Остальных, к сожалению, не помню, так как смотрел сериал довольно давно.
Заключение
Представленные алгоритмы можно применять не только для поиска социальных связей, но и в любых других кейсах, связанных с анализом графов: поиск похожих фильмов, книг, в решении транспортных вопросов. Как и у любой рекомендательной системы, результат их работы не являются непреложной истиной, так как он носит, скорее, характер предположений, чем утверждений, но все равно может помочь в решении многих задач.
