文档章节

最小推荐系统:基于图拓扑的相似性描述SimRank - 知乎

o
 osc_mx6cpuet
发布于 07/01 11:56
字数 860
阅读 21
收藏 0

精选30+云产品,助力企业轻松上云!>>>

推荐系统的问题/任务描述有两种方式,一是预测,也就是对于用户-条目对预测出用户的(喜好)评分值(比如上一篇提到的隐语义模型)。对于这种问题描述,通常假设训练数据是可得的,对于m 个用户和 n 个条目的数据,也就是存在一个不完整的 m\times n 矩阵,其已知部分(已有观测)用作训练,以预测未知部分(空白观测)。这样就把推荐问题转化为Matrix Completion Problem(矩阵补全问题). 第二个是排序,在实际推荐系统中,我们做推荐没有必要得到用户对所推荐条目的准确喜好值,而只是需要推荐特定用户最可能喜好的top-k条目。而且对用户的top-k条目问题比对条目的top-k用户问题更常见,虽然这两个子问题是完全等价的。

做排序的方法中,可解释性最好的通常是基于前篇提到的邻域方法。因为它们都基于一个共同的强假设:在观测到用户消费过条目A之后,我们有很高的可能性观测到用户会喜欢与A相似的条目B以及相似的用户可能喜欢同一个条目。既然是描述相似性,我们可以认为物品A与物品B的相似性等价于物品B与物品A的相似性,也就是说,由包含物品A和B等组成的节点之间的相似性,构成无向图。按照定义[1],SimRank\left( a,b \right)=\frac{C}{\left| I\left( a \right) \right|\left| I \left( b \right)\right|}\sum_{i=1}^{\left| I\left( a \right) \right|}\sum_{j=1}^{\left| I\left( b \right) \right|}SimRank\left( I_i\left( a \right) , I_j\left(b \right)  \right) , 其中 C 是介于0到1之间的常量, I\left( a \right)I\left( b \right) 分别表示 ab 的直接相连节点(in-link nodes)组成的集合, I_i\left( a \right)\in I\left( a \right) , I_j\left( b \right)\in I\left( b \right) . 当 I_i\left( a \right)= I_j\left( b \right) 时, SimRank\left( I_i\left( a \right) , I_j\left(b \right)  \right) =1 ,否则 SimRank\left( I_i\left( a \right) , I_j\left(b \right)  \right) = 0 . 这个定义是递归定义,其对应的计算过程也是递归的,而且一定收敛。其计算复杂度为 O\left( n^4 \right) . 直观上, SimRank(a,b) 可以理解为在网络中从节点 ab 出发进行随机游走直至碰到所需要的预期时间损耗。

SimRank 有一些bad case. 如果节点 ab之间的路径的边数是奇数的话,从上面的递归过程可以看出 SimRank\left( a,b \right)=0 . 比如下图中的节点A和B,它们之间的所有路径边数都是3,所以 SimRank\left( A,B \right)=0 , 而A到C之间路径边为偶数,所以 SimRank\left( A,C \right)>0 . 但从图中可见,A和B的相似性远高于A和C之间。

在条目-用户构成的二相图中,条目到用户的边数如果存在的话,总是奇数。所以条目跟用户的相似性总是0,虽然这是符合实际意义的。

由于计算复杂度高,即便是对于离线计算,一般由上千个节点组成的条目-用户二相图,其对应的 SimRank 矩阵计算耗时和内存需求也是难以接受的。因此通常使用并行、MapReduce等进行计算,甚至并不计算真实值,而是用Monte Carlo等方法进行近似计算[2][3].

参考

  1. ^Jeh, G. , & Widom, J. . (2002). SimRank: a measure of structural-context similarity. the eighth ACM SIGKDD international conference. ACM.
  2. ^Yu, W. , Lin, X. , Zhang, W. , Pei, J. , & Mccann, J. A. . (2019). Simrank*: effective and scalable pairwise similarity search based on graph topology. Vldb Journal, 28(3), 401-426.
  3. ^Weiren Yu, Wenjie Zhang, Xuemin Lin, & Qing ZhangJiajin Le. (2012). A space and time efficient algorithm for simrank computation. World Wide Web.
o
粉丝 0
博文 62
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
最小推荐系统:基于图拓扑的相似性描述SimRank - 知乎

推荐系统的问题/任务描述有两种方式,一是预测,也就是对于用户-条目对预测出用户的(喜好)评分值(比如上一篇提到的隐语义模型)。对于这种问题描述,通常假设训练数据是可得的,对于 个用户和...

Hic Rhodus hic salta
06/30
0
0
最小推荐系统: SimRank快速近似计算 - 知乎

在上一篇中提到,SimRank的计算复杂度非常高,在实际部署中是大不可能计算其真实值的,也没有必要。对于其近似值的计算来说,有很多计算方法。 在实际中,由条目-用户关系构建消费关系图 ,对...

osc_40usjisk
07/04
4
0
最小推荐系统: SimRank快速近似计算 - 知乎

在上一篇中提到,SimRank的计算复杂度非常高,在实际部署中是大不可能计算其真实值的,也没有必要。对于其近似值的计算来说,有很多计算方法。 在实际中,由条目-用户关系构建消费关系图 ,对...

Hic Rhodus hic salta
07/03
0
0
GNLP产品介绍

GNLP产品介绍 1. 平台简介 GNLP(Giant Natural LanguageProcessing)语义理解平台(以下简称GNLP)是将非结构化或半结构化的自然语言文本转化为计算机可深层处理的结构化信息、并进行分类、分...

dm_ml
2015/11/24
16
0
最小推荐系统:隐语义模型(Latent Factor Model) - 知乎

在上一篇中提到,邻域方法(Neighborhood/Similarity Based Models)基于一个强假设:在观测到用户消费过条目A之后,我们有很高的可能性观测到用户会喜欢与A相似的条目B(Item CF)以及 相似的...

osc_iy56i6w3
06/24
4
0

没有更多内容

加载失败,请刷新页面

加载更多

功率放大芯片IR2184介绍

IR2184引脚定义: IN一般为脉冲信号,即全桥电路中的pwm波信号,一般可以通过调节它的占空比来控制智能车电机的转速。 SD信号为使能信号,高电平有效,芯片工作。 Vb是高侧浮动电源输入脚,H...

osc_baeiwmv4
27分钟前
21
0
认知成长:聊聊专业性和职业性

最近在忙双十一全链路压测的事情,由于岗位职责和团队定位等原因,和很多部门以及不同角色的同事都有接触。上周和某个团队的Leader开完会,简短的聊了下工作的推动和协同的一些事项。关键词就...

老_张
2019/10/21
7
0
百万年薪程序员的7点能力

点击蓝字关注,回复“职场进阶”获取职场进阶精品资料一份 几周前,微盟爆了个大雷,数据库让内部员工删库跑路。写了篇文章,做了一些我的判断:从微盟36小时故障,谈谈数据安全这点事。 很明...

潘永斌
04/01
13
0
收住你的下巴!第一人称视角宛如外星科技的自动化伐木!

声明:图片、视频均来自网络,若有侵权请联系处理 喜欢就点赞,随手转发 END 获取更多机械电子资讯 扫码关注 微信公众号:机电狂人 搜索关注 微博:机电狂人531 本文分享自微信公众号 - 工科...

工科生日常
2018/06/10
12
0
matlab教程:Matlab入门教程

  1、适当了解一些数值计算、数值分析以及最优化的理论   用Matlab的无非是做数值计算或者最优化,这也是Matlab的强项,Matlab有足够多的工具箱解决这些问题。但是在使用这些工具箱之前,...

SXXpenguin
28分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部