复习基于图的推荐算法(PersonalRank)

将用户行为数据用二分图表示，例如用户数据是由一系列的二元组组成，其中每个元组(u,i)表示用户u对物品i产生过行为。

将个性化推荐放在二分图模型中，那么给用户u推荐物品任务可以转化为度量Uv和与Uv 没有边直接相连 的物品节点在图上的相关度，相关度越高的在推荐列表中越靠前。

基于随机游走的PersonalRank算法
假设给用户u进行个性化推荐，从图中用户u对应的节点Vu开始游走，游走到一个节点时，首先按照概率alpha决定是否继续游走，还是停止这次游走并从Vu节点开始重新游走。如果决定继续游走，那么就从当前节点指向的节点中按照均匀分布随机选择一个节点作为下次经过的节点，这样经过很多次的随机游走后，每个物品节点被访问到的概率就会收敛到一个数。最终推荐列表中物品的权重就是物品节点的访问概率。 
迭代公式如下：

公式中PR(i)表示物品i的访问概率(也即是物品i的权重)，out(i)表示物品节点i的出度。alpha决定继续访问的概率。

虽然PersonalRank算法可以通过随机游走进行比较好的理论解释，但该算法在时间复杂度上有明显的缺点。因为在为每个用户进行推荐时，都需要在整个用户物品二分图上进行迭代，直到整个图上的每个顶点的PR值收敛。这一过程的时间复杂度非常高，不仅无法在线提供实时推荐，甚至离线生成推荐结果也很耗时。 为了解决PersonalRank每次都需要在全图迭代并因此造成时间复杂度很高的问题，这里给出两种解决方案。第一种很容易想到，就是减少迭代次数，在收敛之前就停止。这样会影响最终的精度，但一般来说影响不会特别大。另一种方法就是从矩阵论出发，重新设计算法。 对矩阵运算比较熟悉的读者可以轻松将PersonalRank转化为矩阵的形式。令M为用户物品二分图的转移概率矩阵，即：