SimRank for 协同过滤

概览

  • 使用场景
  • 直观解释
  • 计算 & 拓展
  • 举个栗子(python)
  • 算法复杂度

最后真推荐歌了~

使用场景

想象一个做协同过滤的推荐场景,想象不出来看下图~

user-item graph

先试试传统的基于物品的协同过滤(cf)方法,用户1喜欢摇滚和轻音乐,简单认为摇滚和轻音乐是相似的。同理用户2喜欢轻音乐和民谣,简单认为轻音乐和民谣相似。

最后计算item间相似度的时候,和摇滚相似的是轻音乐,和民谣相似的是轻音乐,传统的基于item的cf是发现不了摇滚和民谣的相似性的。

这里就不考虑基于用户的cf了,确实基于用户的cf是可以发现摇滚和民谣的关系滴~

这里带入SimRank的思想

Two objects are similar if they are related to similar objects.

这里物品的关系由消费物品的用户来表达。

image.png

从用户1和用户2的历史记录里面得到的 摇滚 - 轻音乐 - 民谣 的关系,可以得到摇滚和民谣的相似度

说明 SimRank 的思想可以发现 ItemCF 发现不了的 item 相似关系

直观解释

定义与公式

item-item关系图

item-item关系图

节点a关联到节点b的关系

节点a关联到节点b的关系

节点a的邻居节点集合,即所有指向a的节点集合

节点a的邻居节点集合

节点间相似度s(a,b),C是衰减因子,经验取值为0.8

节点间相似度s(a,b)

复现计算过程

6个用户收听5首歌的情景,通过log生成左边的二部图,再通过用户作为联系生成右边的item关系图

image.png

按照相似度公式依次计算每个节点,发现I2和I4有共同的入度节点I1,就是从(I1,I1)发现了(I2,I4)

image.png

依次进行n轮计算,图中标明了每轮计算新发现的关系,每次新发现的关系又可以反补给以前发现的关系,作为增强

image.png

可以发现第一轮发现的关系类似于推荐理由“喜欢x的用户也喜欢y”,这种第一轮计算发现的关系可以看作item之间的一次跳跃,暂时称作一跳关系,第二轮迭代发现的(I3,I5)可以看做是2条关系,第n轮拓展的为n跳关系

基于MR模型的计算方法

map阶段

去寻找每个节点的相邻节点,即寻找I(a)里,I(b)里所有点的相似度,从而计算s(a,b)

reduce阶段

根据计算结果更新全局的相似度

image.png

拓展的simrank

打开方法:自行google

  1. delta-simrank
  2. simrank++

计算方式的拓展

  1. 深度优先搜索
  1. 基于矩阵乘法的计算

python的local Example


G = nx.read_graphml("/Users/Matter/paper_code/simrank/widom.graphml")
r=0.8
max_iter=10
eps=1e-4
nodes = G.nodes()   #['1', '0', '3', '2', '4']

pred_func = G.predecessors if isinstance(G, nx.DiGraph) else G.neighbors
#  nodes_i      {'0': 1, '1': 0, '2': 3, '3': 2, '4': 4}
nodes_i = {nodes[i]: i for i in range(0, len(nodes))}

sim_prev = numpy.zeros(len(nodes))  # array([ 0.,  0.,  0.,  0.,  0.])
sim = numpy.identity(len(nodes))
# ###  单位矩阵
# array([[ 1.,  0.,  0.,  0.,  0.],
#        [ 0.,  1.,  0.,  0.,  0.],
#        [ 0.,  0.,  1.,  0.,  0.],
#        [ 0.,  0.,  0.,  1.,  0.],
#        [ 0.,  0.,  0.,  0.,  1.]])
# ###

# round 1
sim_prev = numpy.copy(sim)

for u, v in itertools.product(nodes, nodes):
    if u==v:continue
    u_ps, v_ps = pred_func(u), pred_func(v)
    s_uv = 0
    for u_n, v_n in itertools.product(u_ps, v_ps):
        s_uv += sim_prev[nodes_i[u_n]][nodes_i[v_n]]
    sim[nodes_i[u]][nodes_i[v]] = (r * s_uv) / (len(u_ps) * len(v_ps) + DIV_EPS)

对应图的结构

<?xml version="1.0" encoding="utf-8"?><graphml xmlns="[http://graphml.graphdrawing.org/xmlns](http://graphml.graphdrawing.org/xmlns)" xmlns:xsi="[http://www.w3.org/2001/XMLSchema-instance](http://www.w3.org/2001/XMLSchema-instance)" xsi:schemaLocation="[http://graphml.graphdrawing.org/xmlns](http://graphml.graphdrawing.org/xmlns) [http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd](http://graphml.graphdrawing.org/xmlns/1.0/graphml.xsd)">
  <graph edgedefault="directed">
    <node id="0" />
    <node id="1" />
    <node id="2" />
    <node id="3" />
    <node id="4" />
    <edge source="0" target="1" />
    <edge source="2" target="0" />
    <edge source="1" target="2" />
    <edge source="0" target="3" />
    <edge source="3" target="4" />
    <edge source="4" target="3" />
  </graph>
</graphml>

算法复杂度

n_i:item的数量
n:item对的数量,大概是n_i * n_i
neighbor:每个item的平均邻居数量
d:每一对vid对里的结点邻居平均数量乘积,大概 neighbor * neighbor
一轮迭代的空间复杂度:O(n*n)
一轮迭代的空间复杂度:O(n*n*d)

对应到item数量就是O(n_i * n_i * n_i * n_i)的复杂度
简而言之就是item做笛卡尔得到item pair,再对item pair做笛卡尔

后记

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,013评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,205评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,370评论 0 342
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,168评论 1 278
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,153评论 5 371
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,954评论 1 283
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,271评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,916评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,382评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,877评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,989评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,624评论 4 322
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,209评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,199评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,418评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,401评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,700评论 2 345

推荐阅读更多精彩内容