推荐算法——基于图模型
基于图模型(graph-based model) 将用户行为数据表示成图的形式。
如上,用户A对物品a,b,d有行为。
- 表示成二分图之后,给用户u推荐物品可以转化为度量用户顶点
vu 和与vu 没有边直连的物品节点在图上的相关性,相关性越高的物品在推荐列表中权重越高。 - 顶点的相关性主要体现在如下方面:
- 两个顶点之间的路径数
- 两个顶点之间路径的长度
- 两个顶点之间的路径经过的点
- 相关性高的一对顶点有如下特征:
- 两个顶点之间有很多路径相连
- 连接两个顶点之间的路径长度都比较短
- 连接两个顶点之间的路径不会胫骨出度较大的顶点
利用随机游走的personalRank算法来为用户推荐物品:
假定要给用户u进行个性化推荐,可以从用户u对应的节点
这样重复之后,每个物品节点被访问的概率收敛到一个数,最终的推荐列表中物品的权重就是物品节点的访问概率。
- 缺点
- 时间复杂度方面有明显的缺点,在为每个用户推荐的时候都需要在整个二分图上迭代,直到整个图上的PR(v)收敛,耗时。
- 解决
- 减少迭代次数,但是会影响精度
- 从矩阵论出发重新设计算法
讲PR转换成为矩阵的形式,令M为用户物品二分图的转移概率矩阵,即:
迭代公式变为:
只需要计算一次