召回算法

㈠ 推荐系统召回算法之——图模型（Personal Rank）

目录

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的重要程度排序?

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

算法文字描述 ：对用户A进行个性化推荐，从用户A结点开始在用户物品二分图random walk ，以alpha的概率从A的出边中等概率选择一条游走过去，到达顶点后（例如a），有alpha的概率继续从顶点a的出边中等概率选择一条继续游走到下一个结点，或者（1-alpha）的概率回到起点A，多次迭代。直到所有的顶点对于用户A的重要度收敛。（二分图有且只有一个顶点）

算法公式推导 ：

按照上面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离线计算或maprece将多节点并行计算提高计算性能。

㈡ 如何提高机器学习算法的召回率

最近在做文本分类，遇到了一些问题，想问问大家有没有好的方法。为了节省时间，我只采取了部分数据来跑算法（全部数据跑了之后的结果和这个差不多）
训练集：4837 documents
测试集：2074 documents
样本比例：正样本：负样本 = 1：3
预测结果中，有的算法在正样本中预测的精确率还行（0.95-1.00之间），但是召回率非常差，通常只有0.01和0.02左右，KNeighbors和DecisionTree的精确率和召回率都是0，只有NaiveBayes和BernoulliNB的PR和Recall比较平均，但是也没有到0.8。
问题：我查了一下那些召回率较低（0.01）的算法，475个样本中（正样本），实际上只有5个被预测正确了的，但是具体原因没有查出来。
我想请问一下：1.召回率低是因为样本极度不平衡造成的吗？（虽然我认为1：3的比例不算极度不平衡。）2.在这种样本不平衡的问题上，有没有什么好的方法可以提高召回率？我试过SMOTE方法（过采样和欠采样都有试过），但对于我的数据集并没有什么好的效果，不止到有没有有什么好的方法可以解决这个问题？谢谢！
添加评论
分享

查看全部 11 个回答

0赞同反对，不会显示你的姓名
Elvin 全是细枝末节，做一个乐于分享的人
两个问题一并回答一下，根据你的描述，我觉得问题应该不是出在正负样本比上，1比3这个比例不但不是非常不均衡，相反在我看来已经是非常均衡了。以前做比赛有处理过正负比1比10000的数据，我觉得这才叫不平衡，才需要使用类似上采样，下采样，以及SMOTE算法（都用过），而且这样的情况下recall，F1等指标的提升是显着的。我觉得正负比例在1：1至1：100间差别都不会太大，需要根据具体问题做离线交叉验证去找到最好的比例。

所以我建议你不用再纠结正负样本比的问题，可以再回头看一看你的数据集，一方面看一看代码是否有误？数据集是否太小？（总觉得你的数据集太小，而且测试集相对于训练集太大）另外训练集，测试集的划分是否正确？或者重新划分一下训练测试集做一下交叉验证看一看各项指标再具体研究。