Рекомендация по графику Принцип алгоритма _Personalrank и простая реализация

алгоритм

Дипломный проект автора - реализация рекомендательной системы на основе графового алгоритма.Буду вести блог в виде бумажной заметки.Пожалуйста, поправьте меня, если есть недочеты.

Почему графические алгоритмы?

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

На этом этапе большая часть данных, собираемых бизнесом, находится между пользователем и продуктом.Например, данные о поведении Лао Вана купили сигареты, Сяо Вана купили цветы и т. д. Это может быть представлено серией бинарных предков, который просто использует графовые алгоритмы, чтобы помочь разработчикам разработать лучшие алгоритмы рекомендаций.

Идеи алгоритма

Здесь мы заимствуем случай из книги «Практика рекомендательной системы» для иллюстрации: например, теперь есть пользователи: A, B, C, D и элементы: a, b, c, d, e, образующие замкнутую экологию. , мы будем использовать это покупательское поведение, представленное двудольным графом (как показано ниже):在这里插入图片描述Использование поведенческих данных для рекомендаций, по сути, заключается в том, чтобы найти элемент, который пользователь, скорее всего, выберет (элемент, который больше всего похож на пользователя).Исследователи считают, что факторы в двудольном графе, которые, скорее всего, будут приняты пользователем. пользователя следующие:

  • Количество путей между двумя вершинами;

Чем больше количество путей между точками, тем больше людей, которым нравится то же самое a, что и пользователю, также нравится b, а это означает, что сходство между a и b велико.

  • длина пути между двумя вершинами;
  • Точка, через которую проходит путь между двумя вершинами

При расчете корреляции элементы с более высокой корреляцией в реальности часто имеют следующие общие точки:

  • Есть несколько путей, соединяющих вершины;
  • Длина пути, соединяющего две вершины, относительно мала;
  • Путь, соединяющий две вершины, не имеет точки с относительно большой исходящей степенью.

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

Принцип алгоритма PersonalRank

На основе вышеизложенных идей сгенерирован алгоритм Personalrank, и принцип его алгоритма следующий:PR⁡(v)={α∑v'еin(v)PR(v')∣out⁡(v')∣(v≠vu)(1− alpha )+α∑v'еin(v)PR⁡(v')∣out⁡(v')∣(v=vu)\operatorname{PR}(v)=\left\{\begin{array}{l}\alpha \sum_{v^{\prime} \in \mathrm{in}(v)} \frac{\mathrm{PR}\left(v^{\prime}\right)}{\left|\operatorname{out}\left(v^{\prime}\right)\right|}\left(v \neq v_{u}\right) \\ (1-\text { alpha })+\alpha \sum_{v^{\prime} \in \mathrm{in}(v)} \frac{\operatorname{PR}\left(v^{\prime}\right)}{\left|\operatorname{out}\left(v^{\prime}\right)\right|} \quad\left(v=v_{u}\right)\end{array}\right.Среди них: v — множество вершин, pr(i) — вероятность того, что пользователь выберет i, где pr(i)=1 (исходное) pr(i)=0 (неисходное i), out(i) в начальный случай ) — степень исхода вершины, а можно рассматривать как возможность выбора пользователем следующего элемента в следующий раз. После запуска из узла i начните случайное блуждание (итерация приведенной выше формулы), после многих блужданий (итерация) вероятность посещения каждого узла будет стремиться к сходимости, и это значение сходимости считается элементом, выбранным пользователь Вероятность.

Реализация алгоритма

На основе python код алгоритма, реализованный Personalrank, выглядит следующим образом:

#personalrank算法的简单算例实现

import time

#设计personalrank算法函数
def Personalrank(Graph,alpha,root,max_depth):
    #推荐排序
    rank=dict()
    rank={x:0 for x in Graph.keys()}
    rank[root]=1
    #迭代
    begin=time.time()
    for k in range(max_depth):
        tmp={x:0 for x in Graph.keys()}
        #取出节点i和他的出边节点集合
        for i,ri in Graph.items():
            for j,wij in ri.items():

                tmp[j]+= alpha * rank[i] / (1.0 * len(ri))
        tmp[root] += (1 - alpha)
        rank = tmp
    end=time.time()
    print('使用时间：',end-begin)
    #lst=sorted(rank.items(),key=lambda  x:x[1],reverse=True)
    #for ele in lst：
        #print('%s:%.3f , \n'%(ele[0],ele[1]))
    return rank

if __name__=='__main__':
    alpha=0.8
    Graph={
        'A':{'a':1,'b':1,'d':1},
        'B':{'a':1,'c':1},
        'C':{'b':1,'e':1},
        'D': {'c': 1, 'e': 1},
        'a':{'A':1,'B':1},
        'b':{'A':1,'C':1},
        'c':{'D':1,'B':1},
        'd':{'A':1,'D':1},
        'e':{'C':1,'D':1},
           }
    print(Personalrank(Graph,alpha,'b',50))

Взяв за пример узел b, сходство с узлом можно получить с помощью алгоритма Personalrank:

'A': 0.16577257339161164, 'B': 0.043444835869696115, 'C': 0.16109189469317547, 'D': 0.07412879716688255, 'a': 0.06158614968457111, 'b': 0.308644973214133, 'c': 0.04703252728649955, 'd': 0.04420689787736918, 'e': 0.09409135081606143

считать

  • Текущий алгоритм имеет большой объем вычислений в сценарии применения крупномасштабных данных о поведении, и его можно преобразовать в матричный расчет для дальнейшего улучшения алгоритма;
  • Если результат рекомендации получен от узла-человека, каковы сходства и различия между ним и алгоритмом совместной фильтрации на основе пользователей? Точно так же, если начать с узла элемента, каковы сходства и различия между ним и алгоритмом совместной фильтрации на основе элементов?
Категории