目录
1、Personal Rank 算法背景
2、二分图的概念
3、文件解析原理及其物理意义
4、PR公式推导
5、python实现
6、总结
Personal Rank算法背景：
用户行为很容易表示为图
图推荐在个性化推荐领域效果显著，UI矩阵就是典型的二分图。
二分图：又称为二部图，是图论中的一种特殊模型。设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集（A,B），并且图中的每条边（i,j）所关联的两个顶点i和j分别属于这两个不同的顶点集（i in A，i in B），则称图G为一个二分图。
下面举例并从物理意义角度解析，二分图算法是如何将UI矩阵表示为二分图，计算出Item集合对固定user的重要程度排序?
UI矩阵的二分图表示法
1、两个顶点之间连通的路径数？
A到c：A->a->B->c；A->d->D->c两条连通路径；
A到e：A->b->C->e一条连通路径
故，A对物品c的偏好程度大于对物品e的偏好。
2、两个顶点之间的连通路径长度？
A->c两条路径4个顶点，连通路径长度都是3；A->e也为3
3、两个顶点之间连通路径经过顶点的初度？
A到c：A->a->B->c：3+2+2+2；A->d->D->c：3+2+2+2
A到e：A->b->C->e：3+2+2+1
可见，PR算法是将UI矩阵表示为二分图存储后，通过统计两顶点连通路径长度、连通路径数以及顶点初度信息来计算Item集合每个Item对固定user的重要程度的一种算法。
算法文字描述：对用户A进行个性化推荐，从用户A结点开始在用户物品二分图random walk ，以alpha的概率从A的出边中等概率选择一条游走过去，到达顶点后（例如a），有alpha的概率继续从顶点a的出边中等概率选择一条继续游走到下一个结点，或者（1-alpha）的概率回到起点A，多次迭代。直到所有的顶点对于用户A的重要度收敛。（二分图有且只有一个顶点）
算法公式推导：
PR公式（1）
按照上面UI矩阵的二分图表示法结合算法文字描述，以节点A和a来举例解释公式。
：表示不同节点重要度。
以a为例，公式上部分表示节点a与之相连的节点A和B，分别从各自出边等概率贡献了1/3和1/2的重要度加和后乘以，
取经值为0-1之间（经验值0.6）。
以A为例，公式下部分表示与A相连的节点a,b,d，分别从各自的出边等概率贡献了1/2的重要度，同时它们又是直接与A相连的节点，从PR算法文字描述可知，都可以以1-的概率回到A节点。
公式（1）的矩阵表达方式为： (2)
其中是n维向量，每一个元素代表一个节点的PR重要度；
也是n维向量，第i个位置为1，其余位置为0，我们就是要为第i个节点进行推荐。其中
是n阶转移矩阵：
由（2）进行恒等变形可得
(3)
(4) ，其中
就是所有节点的推荐结果，乘以
就是取出矩阵的第i列。
Python实现：https://github.com/SolodanceMagicq/RecommendSys/tree/master/PersonalRank
总结：
1、personalrank二分图算法，是一种无向图，有且只有一个root顶点。
2、算法核心思想是将UI矩阵以二分图存储，通过顶点按等概率随机游走，迭代计算关联节点pr值的过程。首次迭代只计算推荐用户（root顶点）与其直接关联的节点pr值，然后每次基于上次节点进一步迭代计算关联节点，直至收敛。
3、PersonalRank算法迭代的时间复杂度过高，须进一步优化，工业界一般会借助spark离线计算或mapreduce将多节点并行计算提高计算性能。
网友评论