Построение рекомендательной системы
В этом нотбуке мы выполним наш финальный проект — построим рекомендательную систему, основанную на методах, которые мы обсудили.

Для этого мы будем использовать данные от Амазон. Граф размещен в отдельном файле, он загружается в первом блоке.

Нам нужно будет реализовать три метода, обсуждавшиеся на этой неделе, и протестировать их. Но общий подход во всех трех методах один и тот же:

мы фиксируем вершину (в коде ниже это переменная query);
удаляем некоторые смежные с ней ребра (в коде ниже это список samp);
вычисляем специально определенное расстояние между нашей вершиной и всеми остальными (методы различаются как раз выбором расстояния);
выбираем вершины с наименьшим расстоянием до выбранной, это те вершины, в которые метод предлагает провести ребра;
сравниваем предложенные методом ребра с удаленными, чем больше совпадений, тем лучше сработал метод.
Вспомогательные шаги уже реализованы ниже. Шаг 2 реализован в функции generate_graph. Шаги 4-5 реализованы в функции check_answer. Вам нужно реализовать только шаги 3 для всех методов.

В первом методе, который нужно реализовать, расстоянием является просто число общих соседей. Во втором методе нужно будет посчитать усеченные моменты достижения из выбранной вершины. Их мы подсчитываем приближенно, запуская случайное блуждание несколько раз. Сначала нужно реализовать функцию для одного случайного блуждания, затем функцию для приближенного вычисления усеченных моментов достижения. Длину блуждания мы фиксируем равной 10. В третьем методе нужно посчитать усеченные моменты достижения в вершину. Для них у нас есть рекуррентная формула.

Мы подробно обсуждали все три метода на этой неделе. Ниже вы также можете найти поясняющие комментарии.

Внимание: в функциях пользуйтесь только теми графами (graph или adjlist), которые переданы в аргументах. Все остальные вхождения могут измениться во время тестирования.





# В этом блоке мы загружаем граф из файла и приводим его в вид, удобный для работы

import networkx as nx

amazon = nx.read_edgelist("Amazon0302.txt", create_using=nx.Graph(), nodetype=int, data=False)
amazon = nx.convert_node_labels_to_integers(amazon, ordering='decreasing degree')
nodes = amazon.number_of_nodes()


# В этом блоке собраны вспомогательные функции, которые потребуются вам для выполнения задания

# Эта функция получив на вход словарь упорядочивает его по значению меток
def index_sorted(a, reverse=False):
    return sorted(range(len(a)), key=lambda k: a[k], reverse=reverse)

# Эта функция позволяет выбрать ответ из посчитанных расстояний и сравнить его с целевым значением.
# Она выбирает нужное количество вершин с минимальным расстоянием и находит число совпадений с удаленными ребрами.
def check_answer(stat, samp, reverse=False):
    index_dist = index_sorted(stat, reverse)
    guess = index_dist[:len(samp)]
    return len(set(samp) & set(guess))

# Эта функция генерирует тестовый пример, удаляя данные ей ребра из графа.
def generate_graph(query, samp):
    graph = amazon.copy()
    for i in samp:
        graph.remove_edge(query, i)
    return graph


# В этом блоке требуется реализовать метод числа общих соседей.
# Функция в ячейке массива i должна сохранить число общих соседей query и i.
# Но есть одна тонкость: ячейку с номером query и ее соседей правильно обнулить,
# а то нам будут рекомендовать соединить query с query или ее соседями

def common_neighbours(graph, query):
    common_neigh = [0] * nodes
    # your code here
    for i in graph:
        for neigh in graph[i]:
            if neigh in list(graph[query]):
                common_neigh[i] += 1
    common_neigh[query] = 0
    for v in graph[query]:
        common_neigh[v] = 0

    return common_neigh



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

query = 422
samp = [35561, 98891, 157171, 3060, 198304, 28054, 226896, 20673, 110999, 125875, 125877, 20342, 208996, 205186, 829, 189415, 212872, 164896, 104718, 78418]
graph = generate_graph(query, samp)

ans = common_neighbours(graph, query)
assert index_sorted(ans, reverse=True)[:len(samp)] == [829, 3060, 20673, 13141, 21150, 35561, 36377, 103988, 110999, 172699, 4863, 8961, 10572, 16003, 20342, 28054, 53201, 70084, 70323, 104718]
assert check_answer(ans, samp, reverse=True) == 8

# В этом блоке требуется реализовать метод случайных блужданий.
# Допишите обработку новой вершины в блуждании и учет непосещенных вершин.
# Обратите внимание на массив used: вместо того, чтобы перед каждым блужданием его очищать,
# мы поддерживаем номер последней посещенной итерации и сравниваем его с текущим.

import random

def hit_time(adjlist, hit_dist, hit_times, used, source, time_bound, it):
    current_node = source
    for step in range(time_bound):
        current_node = random.choice(adjlist[current_node])
        if used[current_node] != it:
            # your code here
            hit_dist[current_node] += step + 1 #расстояние до вершины
            used[current_node] +=1 #счетчик


def hit_distance(adjlist, query, time=10):
    # инициализация статистик
    hit_dist = [0] * nodes  # искомые расстояния
    hit_times = [0] * nodes  # кол-во раз, когда вершина была достигнута в блуждании
    used = [0] * nodes  # последняя итерация, на которой вершина была достигнута в блуждании
    samples = nodes // time  # кол-во блужданий

    # запуск блужданий
    for i in range(1, samples + 1):
        hit_time(adjlist, hit_dist, hit_times, used, query, time, i)
    # your code here
    for i in hit_dist:
        i = (i + time * (samples - i)) / samples   #расчет расстояний
        hit_dist[query] = time

# Проверьте Ваше решение

adjlist = nx.convert.to_dict_of_lists(graph)
hd = hit_distance(adjlist, query)
assert check_answer(hd, samp) >= 8




# В этом блоке необходимо реализовать подсчет усеченных моментов достижения в вершину.
# Допишите рекуррентную функцию и постобработку (какие вершины точно не должны попасть в ответ?)
# В нашем тестовом графе нет петель, но если вы захотите потестировать свое решение на других графах,
# обратите внимание, что петля (ребро, идущее из вершины в саму себя) повышает степень вершины на 2

def truncated_hitting_time(graph, query, time=10):
    tht = [[0 for _ in range(nodes)] for _ in range(time + 1)]
    for t in range(1, time + 1):
        for vert in range(nodes):
            if vert == query:
                continue

            if graph.degree[vert] != 0:
                # your code here

            tht[t][vert] += 1

    # your code here

    return tht[time]




# Проверьте Ваше решение

tht = truncated_hitting_time(graph, query)
assert index_sorted(tht)[:len(samp)] == [164896, 254021, 110999, 212872, 20673, 172699, 3060, 104718, 205186, 194186, 35561, 36377, 829, 103988, 157171, 198304, 113283, 21150, 244935, 186662]
assert check_answer(tht, samp) == 11


# В этом блоке требуется реализовать функцию, которая принимает две разные статистики и выдает новую,
# являющуюся суммой переданных

def sum_of_stats(first, second):
    # your code here




# Проверьте Ваше решение

assert check_answer(sum_of_stats(hd, tht), samp) >= 9