Ⅰ 推荐系统召回算法之——图模型（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将多节点并行计算提高计算性能。
Ⅱ C++课程设计 矩形覆盖小正方形
实际上,你可以利用图论的概念来解决.
相邻的实际上等于是有关系,那可以在图中描述为邻接点.不断的添加相邻的元素就能够组成一张无向图.如果考虑求一个最小覆盖的问题,推荐的算法(根据你的需求猜测)
1. 二部图匹配(最大流最小流)
2.最小生成树
Ⅲ ACM题目求解题思路
有N个石子,每个石子重量Qi；按顺序将它们装进K个筐中；求一种方案，使得最重的筐最轻。 分析：本题乍一看很容易想到动态规划。事实上的确可以用动态规划解决，稍加分析我们很快得到一个简单的算法。用状态f(i,k)表示将前i个石子装入k个筐最优方案，g(i,j)表示i-j中最重的石子，则可以写出状态转移方程：g(i,j)=max {g(i,j-1),Qj}f(i,j)=min max {f(k , j-1), g(k+1 , i)} | 1<=j<=k边界条件：g(i,i)=Qi,f(1,1)=g(1,1)很明显，这个算法的时间复杂度为O(N3),空间复杂度为O(N2)，并不十分理想。经过一些优化可以将复杂度降为O(N2)，不过这样思维复杂度骤然加大，且算法本身仍不够高效。现在已经很难在原动态规划模型上做文章了，我们必须换一个思路。按一般的想法，顺序将石子装入筐，即先把石子放入第一筐，放到一定时候再改放第二个筐，第三个筐……但由于筐的重量没有上限，我们无法知道放到什么时候可以停止，转而将石子放入下一个筐。此时，问题的难点已经显露出来，是不是有方法可以化解呢？我们不妨针对上面的难点，加入一个参数P，改求一个判定可行解问题：每个筐石子重量和不能超过P，是否可以用K个筐装下所有石子。首先经过分析不难发现，如果当前筐的石子总重量为T1，即将处理的石子重量为T2，若T1+T2 ≤P，则我们仍将该石子放入当前框，这是显而易见的。由此可以得出贪心算法，按顺序把石子放进筐，若将石子放入当前筐后，筐的总重量不超过P，则继续处理下一个石子；若重量和超过P，则将该石子放入下一个筐，若此时筐的数目超过K，则问题无解，否则处理完所有石子后就找到了一个可行解。以上算法时间复杂度O(N),空间复杂度O(N)，这都是理论的下界。现在我们已经解决了可行解问题，再回到原问题。是不是可以利用刚才的简化过的问题呢？答案是肯定的。一个最简单的想法是从小到大枚举P，不断尝试找最优解为P的方案（这就是刚才的可行解问题），直到找到此方案。这就是题目的最优解。估算一下上面算法的时间复杂度。令T=∑Qi，则最坏情况下需要枚举T次才能找到解，而每次判断的时间复杂度为O(N)，因此总的时间复杂度为O(TN)，故需要做进一步优化。下面考虑答案所在的区间。很明显，若我们可以找到一个总重量不超过P’的解，则我们一定能找到一个总重量不超过P’+1的解，也就是说，可行答案必定可以位于区间[q,+∞]（其中q为本题最优解）。因此，我们自然而然的联想到了二分，具体方法为：在区间[1,T]内取中值m，若可以找到不超过m的方案，则尝试区间[1,m-1];若不能，尝试区间[m+1,T]。不断重复以上步骤即可找到问题的最优解。分析一下采用二分法后算法总的时间复杂度：由于每次除去一半的区间，则一共只需判断log2N次，而每次判断的时间复杂度为O(N)，因此这个算法总的时间复杂度为O(NlgT)。一般而言，这个复杂度可以令人满意的，并且实际使用中效果非常好。但该复杂度同权值有关，不完全属于多项式算法，我们可以继续求得一个多项式算法（该算法与本文核心内容无关，只作简单探讨）。首先，此问题的答案必定为某一段连续石子的和，而段数不超过n2，因此，我们最多只要判断log2N2=2log2N次即可。现在新的问题是如何找到第m大的段。首先，以每个石子开头的所有段，例如：3 2 1 2，以2开头的所有段：2；2 1； 2 1 2， 由于每个石子的重量都大于0，因此总和一定是递增的。现在有n个递增段，如何快速的找到第k大的数呢？设各段长度为L1,L2,…,LN,中点分别为M1,M2,…,MN，我们每次询问各段中点的大小，若L1/2+L2/2+..+LN/2>k，则找到权值最大的中点，删去其后的数（下图中红色部分），否则找到权值最小的中点，删去其前面的部分（下图中黑色部分），可以证明删去的一定不是所求的数。 注：上图中每个各格子代表一个数。 由以上可知每次可以去掉某一段的1/2，因为有n段，故总共需要去O(Nlog2N)次，每次找最小最大值可以用堆实现，复杂度仅为O(lgN)，因此总的时间复杂度为O(lg2N)，而由上文我们知道找中值的操作总共有log2N次，故这个算法的时间复杂度为O(Nlg3N)。 至此我们终于得到了一个多项式级别的算法，当然这个算法实现起来比较麻烦，实际效果也不甚理想，不过具有一定的理论价值，在此不做过多讨论。 回顾本题解题过程，首先我们得到了一个动态规划算法，由于很难再提高其效率，因此我们另辟蹊径，寻求新的算法。在分析过程中我们发现由于筐的重量没有上限，因此很难确定将多少石子放入同一个筐内。为了解决此难点，我们加入了参数P，改求可行解问题。参数的加入实际上就是强行给筐定了一个上界。正是由于这无形之中多出的条件，使得问题立刻简单化，于是我们很自然的得到了贪心算法。而最终使用二分法降低了算法的时间复杂度，成功地解决了问题。 由上面的例子我们得到了此类解法的一般步骤，通常分为两步：Ⅰ.首先引入参数P，解决子问题：能否找到一个不优于P的方案Ⅱ.从小到大枚举P，判断是否有优于P的方案，直到找出原问题的最优解 一般地，参数搜索可以通过二分法或迭代降低时间复杂度，由于迭代法证明比较复杂，所以本文更多的讨论二分法。 这个方法的应用比较广泛，通常情况下和上例一样求最大（小）值尽量小（大）的题目都可以采用此方法，比如下面的例子。神秘的山：有n个队员攀登n个山峰，每个队员需要选择一个山峰，队员们攀登的山峰各不相同，要求最后一个登顶的队员用的时间尽量短。 分析：本问题分为两个部分解决：1．求出每个队员攀登到各个山峰所需的时间；2．找一个最优分配方案。 第一部分属于几何问题，我们可以枚举每个队员攀登山峰的位置再做简单的判断（题目规定攀登点必须为整点，这就为枚举提供了条件），这样就可求得队员们攀登上各个山峰所需的时间。下面重点讨论第二部分。首先将我们的数据构图，很明显，我们得到的是一个二部图，假设有3个队员3个山峰，每个队员攀登的时间如下 山峰1山峰2山峰3队员1132队员2222队员3133 则我们可以构图，每条边附上相应的权值： 现在的任务就是在图中找一个匹配，匹配中权值最大的边尽量小。这个问题是否可以直接套用一些常见的模型呢？比如最大匹配或是最佳匹配？经过分析不难发现在这个问题中它们都是不足以胜任的，因此我们不得不做新的尝试。 上文提到过要求极大（小）值尽量小（大）的题目往往先定出上界比较容易下手，那么这题也采用类似的思路。引入一个参数T，先求一个判定可行解的子问题：找一个方案，要求最后登山的队员所用时间不超过T。 改变后的题目有什么不同之处呢？如果队员i攀登上山峰j所需的时间超过T，则可以认为他在规定时间内不能攀登上山峰j，我们就可以把这条边从图中删去。例如在上例中找一个不超过2的方案，经过一次“筛选”，保留的图如下。 经过这次过滤保留下来的边都是“合法边”，我们只需要在这个新的二部图中找一个完备匹配即可，一个完备匹配唯一对应着一个可行方案。而找完备匹配可以借用最大匹配的算法，因为如果一个二部图的最大匹配数等于N，则找到了一个完备匹配，否则该图中将不存在完备匹配。（上图中的红色表示一个完备匹配），那么这一步的时间复杂度为O(NM)，而在本题中M=N2，因此我们可以在O(N3)的时间内判断出是否存在一个方案满足最后等上山顶的队员时间不超过T。 最后，再用二分法枚举参数T，找到最优解。由于答案必定为某个队员攀登上其中一个山峰的时间，因此我们开始的时候可以将所有数据排序，这样最终的时间复杂度为O(N3lgN)。引入参数后求可行解的子问题与原问题最大的区别在于定下上界以后，我们很自然的排除了一些不可取条件，从而留下了“合法”条件，使得问题变的简单明了。. 上面的例子在增加了上界之后，排除了一些无效条件，其实它的作用绝不仅局限于此，有些时候，它能将不确定条件变为确定条件，比如下面的例子，最大比率问题：有N道题目,每道题目有不同的分值和难度,分别为Ai,Bi；要求从某一题开始, 至少连续选K道题目,满足分值和与难度和的比最大。 分析：最朴素的想法是枚举下标i’,j’，得到每一个长度不小于K的连续段，通过累加Ai’->Aj’，Bi’->Bj’求出比值，并找出比最大的一段。这样做的时间复杂度很高，由于总共有N2段，每次计算比值的时间是O(N)，则总的时间复杂度到达O(N3)，不过计算比值时，可以采用部分和优化，这样能把复杂度降至O(N2)，但仍然不够理想。我们需要追求更出色的算法，先考虑一个简单的问题——不考虑难度（Bi），仅仅要求分值和最大（当然此时分值有正有负）。这个简化后的问题可以直接扫描，开始时为一个长度为K的段，设为Q1,Q2,…Qk， 每次添加一个新数，若Q1+Q2+..+QL-K小于0，则把它们从数列中删去，不断更新最优解即可。这样我们就能在O(N)的时间内找到长度不小于k且和最大的连续段。 之所以能成功解决简化后的问题，是由于该问题中每个量对最终结果的影响是确定的，若其小于0，则对结果产生不好的影响，反之则是有益的影响。那么原问题每个参数对最终结果的影响是不是确定的呢？很遗憾，并不是这样，因为每个题目有两个不同的参数，他们之间存在着某些的联系，而这些联系又具有不确定性，故我们很难知道它们对最终结果是否有帮助。想解决原问题，必须设法消除这个不确定因素！那么有没有办法将这些不确定的因素转化成确定的因素呢？此时，引入参数势在必行！那么我们引入参数P，求一个新的问题：找一个比值不小于P的方案。这个问题实际就是求两个下标i’,j’，满足下面两个不等式j’-i’+1≥k ①(Ai’+Ai’+1....+Aj’)/(Bi’+Bi’+1…+Bj’) ≥ p ②由不等式②=>Ai’+Ai’+1....+Aj’ ≥p(Bi’+Bi’+1…+Bj’)整理得(Ai’-pBi’)+(Ai’+1-pBi’+1)…+(Aj’-pBj’) ≥0可以令Ci=Ai-pBi，则根据上面不等式可知问题实际求一个长度不小于k且和大于０的连续段。由之前的分析可以知道我们能在O(N)的时间内求出长度不小于k且和最大的连续段，那么如果该段的和大于等于０，则我们找到了一个可行解，如果和小于０，则问题无解。也就是说，我们已经能在O(N)的时间内判断出是否存在比值不小于P的方案，那么接下来的步骤也就顺理成章了。我们需要通过二分法调整参数P，不断逼近最优解。计算一下以上算法的时间复杂度，设答案为T，则该算法的时间复杂度为O(NlgT)，虽然这并不是多项式级别的算法，但在实际使用中的效果非常好。引入参数后，由于增加了一个条件，我们就可以将不确定的量变为确定的量，从而解决了问题。三． 总结 本文主要通过几个例子说明了参数搜索法在信息学中的应用，从上文的例子可以看出加入参数一方面能大大降低思维复杂度，另一方面也能得到效率相当高的算法，这使得我们解最解问题又多了一中有力的武器。当然，任何事物都是具有两面性的。参数搜索在具有多种优点的同时也有着消极的一面。由于需要不断调整参数逼近最优解，其时间复杂度往往略高于最优算法，且通常依赖于某个权值的大小，使得我们得到的有时不是严格意义上的多项式算法。文章中还总结了使用此方法解题的一般步骤，在实际应用中，我们不能拘泥于形式化的东西，必须灵活应用，大胆创新，这样才能游刃有余的解决问题。
Ⅳ h 1269 tarjan WA 了 求解释
ACM 推荐题目：不过不一定是北大的。
一.动态规划
参考资料：
刘汝佳《算法艺术与信息学竞赛》
《算法导论》
推荐题目：
简单
中等，经典TSP问题
中等，状态压缩DP
中等
中等，树形DP。
可参考《算法艺术与信息学竞赛》动态规划一节的树状模型
中等，《算法艺术与信息学竞赛》中的习题
中等，《算法艺术与信息学竞赛》中的习题
中等，《算法艺术与信息学竞赛》中的习题
中等，递推
中等，需要减少冗余计算
中等，四边形不等式的简单应用
较难，状态压缩DP，《算法艺术与信息学竞赛》中有解答
较难，《算法艺术与信息学竞赛》中有解答
较难，需要配合数据结构优化（我的题目^_^）
较难，写起来比较麻烦
较难
难，树形DP
难，状态压缩DP，题目很有意思
难
非常难
二.搜索
参考资料：
刘汝佳《算法艺术与信息学竞赛》
推荐题目：
简单，深搜入门题
中等，广搜
中等，广搜
较难，广搜
难，IDA*，迭代加深搜索，需要较好的启发函数
难，可重复K最短路，A*。
可参考解题报告:
难，深搜剪枝，《算法艺术与信息学竞赛》中有解答
难，《算法艺术与信息学竞赛》习题
难，深搜
较难，《算法艺术与信息学竞赛》中有解答
很难
三. 常用数据结构
参考资料：
刘汝佳《算法艺术与信息学竞赛》
《算法导论》
线段树资料：
树状数组资料
关于线段树和树状数组更多相关内容可在网上搜到
后缀数组资料
推荐题目
较难，线段树应用，《算法艺术与信息学竞赛》中有解答
简单，线段树应用矩形面积并，《算法艺术与信息学竞赛》中有解答
较难，线段树应用，可参考解题报告
难，二维树状数组。
中等，线段树应用。
难，堆的应用，《算法艺术与信息学竞赛》中有解答
中等，左偏树，二项式堆或其他可合并堆的应用。
左偏树参考
二项式堆参见《算法导论》相关章节
中等，并查集
中等，字典树
较难，多串匹配树
参考：
难，后缀数组
较难，最长公共子串，经典问题，后缀数组
很难，后缀数组
可参考解题报告
很难，数据结构综合运用
四.图论基础
参考资料：
刘汝佳《算法艺术与信息学竞赛》
《算法导论》
《网络算法与复杂性理论》谢政
推荐题目:
简单，欧拉路
中等，无向图割边
较难，无向图双连通分支
中等，最小度限制生成树，《算法艺术与信息学竞赛》中有解答
中等，最小比率生成树，《算法艺术与信息学竞赛》中有解答
简单，最短路问题
中等，差分约束系统，Bellman-Ford求解，《算法艺术与信息学竞赛》中有解答
简单，Bellman-Ford
中等，网络流
较难，网络流
中等，二部图最大匹配
较难，二部图最大匹配
中等，二部图最大权匹配
KM算法参考《网络算法与复杂性理论》
较难，二部图最大权匹配
中等，LCA（最近公共祖先）问题
参考Tarjan's LCA algorithm 《算法导论》第21章习题
较难，2-SAT问题
参考：
较难，2-SAT问题
较难，最小树形图
参考《网络算法与复杂性理论》中朱-刘算法
Ⅳ C++ 实现输入一个二部图的临接矩阵，找出二部图中的最大匹配，输出为
#include <iostream>
#include <fstream>
#include<string>
#define MAXN 10000
using namespace std;
int mk[MAXN]; //mk[i]=0表示未访问过，为1表示访问过
int nx=MAXN, ny=MAXN; //X，Y集合中顶点的个数
int g[MAXN][MAXN]; //邻接矩阵，g[i][j]为1，表示Xi,Yj有边相连
int cx[MAXN],cy[MAXN]; //cx[i]最终求得的最大匹配中与Xi匹配的Y顶点，cy[i]同理
int pred[MAXN]; //用来记录交错轨的，同时也用来记录Y集合中的顶点是否被遍历过
int queue[MAXN]; //实现BFS搜索时，用到的队列（用数组模拟）
int read() //读取数据，数组存储
{
ifstream cin("ER_data.txt",ios::in);
/厅则/ifstream cin("test.txt",ios::in);
for(int i=0;i<MAXN;i++)
for(int j=0;j<MAXN;j++)
g[i][j]=0;
int x,y;
while(cin>>x>>y)
g[x][y]=1;
cin.close();
return 0;
}
int path (int u)
{
for (int v=0; v <ny; v++ ) //考虑所有Yi顶点v
{
if (g[u][v]&&!mk[v]) //v与u邻接，且没有访问过
{
mk[v]=1; //访问v
//如果v没有匹配；或者扮乱棚v已经匹配了，但从cy[v]出发可以找到一条增广路
//注意，前一个条件成立，则不会递归调用
if (cy[v]==-1||path ( cy[v]) )
{
cx[u]=v;
cy[v]=u;
return 1;
}
}
}
return 0; //如果不存在从u出发的增广路
}
int DMaxMatch() //DFS算法
{
int res=0; //所求得的最大匹配
memset (cx,0xff,sizeof(cx)); //从0匹配开始增广，将cx和cy各元素初始化为-1
memset (cy,0xff,sizeof(cy));
for (int i=0;i<=nx;i++)
{
if (cx[i]==-1) //从每个未盖点出发进行寻找增广路径
{
memset( mk,0,sizeof(mk));
res+=path(i); //每找到一条增广路，匹配数加1
}
}
return res;
}
int BMaxMatch() //BFS算法
{
int i,j,y;
int cur,tail; //表示队列头和尾位置的下标
int res = 0; //所求得的最大匹配
memset (cx,0xff,sizeof(cx)); //初始化所有点为未匹配的状态
memset (cy,0xff,sizeof(cy));
for ( i=0;i<陪判 nx;i++ )
{
if ( cx[i]!= -1) //对X集合中的每个未盖点i进行BFS找交错轨
continue;
for (j=0;j< ny;j++)
pred[j]=-2; //-2表示初始值
cur=tail=0; //初始化队列
for ( j=0;j<ny;j++ ) //把i的邻接顶点都入队列
{
if ( g[i][j] )
{
pred [j]=-1; queue[tail++]=j; //-1表示遍历到，是邻接顶点
}
}
while ( cur <tail ) //BFS
{
y=queue[cur];
if (cy[y]==-1) break; //找到一个未匹配的顶点，则找到了一条增广轨
cur++; //y已经被匹配给cy[y]了，从cy[y]出发，将它的邻接顶点入队列
for ( j = 0; j<ny; j++)
{
if (pred [j]==-2&&g[cy[y]][j])
{
pred [j] =y;
queue [tail++]=j;
}
}
}
if ( cur==tail ) continue; //没有找到交错轨
while (pred[y]>-1) //更改交错轨上的匹配状态
{
cx[ cy[pred[y]]]=y;
cy[y]=cy[pred[y]];
y=pred[y];
}
cy[y]=i; cx[i]=y;
res++; //匹配数加1
}
return res;
}
int main(){
read(); //读数据
int max1,max2;
max1 = DMaxMatch(); //DFS找的最大匹配
max2 = BMaxMatch(); //BFS找的最大匹配
cout<<max1<<endl<<max2<<endl;
cin.get();
return 0;
}
-----------------------------------------------------------------------
3）Hopcroft-Karp算法
/*Hopcroft-Karp算法代码*/
#include <iostream>
#include <fstream>
#include <cstdio>
#include <memory.h>
#include <queue>
using namespace std;
const int MAXN = 100 ;
const int INF = 1 << 28;
bool flag;
int p=MAXN,n=MAXN;
int Mx[MAXN], My[MAXN], Nx=MAXN, Ny=MAXN;
int dx[MAXN], dy[MAXN], dis;
bool vst[MAXN];
int g[MAXN][MAXN];
int read()
{
ifstream cin("ER_data-1.txt",ios::in);
//ifstream cin("ER_data.txt",ios::in);
//ifstream cin("test.txt",ios::in);
for(int i=0;i<MAXN;i++)
for(int j=0;j<MAXN;j++)
g[i][j]=0;
int x,y;
while(cin>>x>>y)
g[x][y]=1;
cin.close();
return 0;
}
bool BFS(void) //BFS
{
queue <int> Q;
dis = INF;
memset(dx, -1, sizeof(dx));
memset(dy, -1, sizeof(dy));
for (int i = 0; i < Nx; i++)
if (Mx[i] == -1)
{
Q.push(i); dx[i] = 0;
}
while (!Q.empty())
{
int u = Q.front(); Q.pop();
if (dx[u] > dis) break; //该增广路径长度大于dis还没有结束，等待下一次BFS再扩充
for (int v = 0; v < Ny; v++)
if (g[u][v] && dy[v] == -1) //v是未匹配点
{
dy[v] = dx[u]+1;
if (My[v] == -1) dis = dy[v]; //得到本次BFS的最大遍历长度
else
{
dx[My[v]] = dy[v]+1; //v是匹配点，继续延伸
Q.push(My[v]);
}
}
}
return dis != INF;
}
bool DFS(int u) //DFS
{
for (int v = 0; v < Ny; v++)
if (!vst[v] && g[u][v] && dy[v] == dx[u]+1)
{
vst[v] = 1;
if (My[v] != -1 && dy[v] == dis) continue; //增广路径的长度大于本次查找的dis，是BFS被break的情况，也就是还不确定是否是增广路径，只有等再次调用BFS再判断
if (My[v] == -1 || DFS(My[v])) //是增广路径，更新匹配集
{
My[v] = u; Mx[u] = v;
return 1;
}
}
return 0;
}
int MaxMatch()
{
int res = 0;
memset(Mx, -1, sizeof(Mx));
memset(My, -1, sizeof(My));
while (BFS())
{
memset(vst, 0, sizeof(vst));
for (int i = 0; i < Nx; i++)
if (Mx[i] == -1 && DFS(i))
res++; //查找到一个增广路径，匹配数增加
}
return res;
}
int main()
{
read();
int max = MaxMatch();
cout<<max<<endl;
cin.get();
return 0;
}
Ⅵ 推荐系统中用到的热传导算法和物质扩散是怎么用的
常常用二部图来表示用户和物品之间的关系：
把用户（Users）看成一类，把物品（Objects）看作另一类。当某个用户购买过某个商品时，他们之间会存在一条连边。
而同一类点之间不存在连边，即用户与用户之间，商品与商品之间不存在连边，类似于这样组成的网络就称为二部图。电子商务中的商品推荐，可以看做是二部图上的链路挖掘问题，而扩散过程可以用来寻找网络中两个节点之间的关联强度。
Ⅶ 推荐算法简介
写在最前面：本文内容主要来自于书籍《推荐系统实践》和《推荐系统与深度学习》。
推荐系统是目前互联网世界最常见的智能产品形式。从电子商务、音乐视频网站，到作为互联网经济支柱的在线广告和新颖的在线应用推荐，到处都有推荐系统的身影。推荐算法是推荐系统的核心，其本质是通过一定的方式将用户和物品联系起来，而不同的推荐系统利用了不同的方式。
推荐系统的主要功能是以个性化的方式帮助用户从极大的搜索空间中快速找到感兴趣的对象。因此，目前所用的推荐系统多为个性化推荐系统。个性化推荐的成功应用需要两个条件：
在推荐系统的众多算法中，基于协同的推荐和基于内容的推荐在实践中得到了最广泛的应用。本文也将从这两种算法开始，结合时间、地点上下文环境以及社交环境，对常见的推荐算法做一个简单的介绍。
基于内容的算法的本质是对物品内容进行分析，从中提取特征，然后基于用户对何种特征感兴趣来推荐含有用户感兴趣特征的物品。因此，基于内容的推荐算法有两个最基本的要求：
下面我们以一个简单的电影推荐来介绍基于内容的推荐算法。
现在有两个用户A、B和他们看过的电影以及打分情况如下：
其中问好（?）表示用户未看过。用户A对《银河护卫队 》《变形金刚》《星际迷航》三部科幻电影都有评分，平均分为 4 .7 分 （ (5+4+5 ) / 3=4.7 ）；对《三生三世》《美人鱼》《北京遇上西雅图》三部爱情电影评分平均分为 2.3 分 （ ( 3十2+2 ) /3=2.3 ）。现在需要给A推荐电影，很明显A更倾向于科幻电影，因此推荐系统会给A推荐独立日。而对于用户B，通过简单的计算我们可以知道更喜欢爱情电影，因此给其推荐《三生三世》。当然，在实际推荐系统中，预测打分比这更加复杂些，但是其原理是一样的。
现在，我们可以将基于内容的推荐归纳为以下四个步骤：
通过上面四步就能快速构建一个简单的推荐系统。基于内容的推荐系统通常简单有效，可解释性好，没有物品冷启动问题。但他也有两个明显的缺点：
最后，顺便提一下特征提取方法：对于某些特征较为明确的物品，一般可以直接对其打标签，如电影类别。而对于文本类别的特征，则主要是其主题情感等，则些可以通过tf-idf或LDA等方法得到。
基于协同的算法在很多地方也叫基于邻域的算法，主要可分为两种：基于用户的协同算法和基于物品的协同算法。
啤酒和尿布的故事在数据挖掘领域十分有名，该故事讲述了美国沃尔玛超市统计发现啤酒和尿布一起被购买的次数非常多，因此将啤酒和尿布摆在了一起，最后啤酒和尿布的销量双双增加了。这便是一个典型的物品协同过滤的例子。
基于物品的协同过滤指基于物品的行为相似度（如啤酒尿布被同时购买）来进行物品推荐。该算法认为，物品A和物品B具有很大相似度是因为喜欢物品A的用户大都也喜欢物品B。
基于物品的协同过滤算法主要分为两步：
基于物品的协同过滤算法中计算物品相似度的方法有以下几种：
（1）基于共同喜欢物品的用户列表计算。
此外，John S. Breese再其论文中还提及了IUF（Inverse User Frequence，逆用户活跃度）的参数，其认为活跃用户对物品相似度的贡献应该小于不活跃的用户，应该增加IUF参数来修正物品相似度的公式：
上面的公式只是对活跃用户做了一种软性的惩罚， 但对于很多过于活跃的用户， 比如某位买了当当网80%图书的用户， 为了避免相似度矩阵过于稠密， 我们在实际计算中一般直接忽略他的兴趣列表， 而不将其纳入到相似度计算的数据集中。
（2）基于余弦相似度计算。
（3）热门物品的惩罚。
从上面（1）的相似度计算公式中，我们可以发现当物品 i 被更多人购买时，分子中的 N(i) ∩ N(j) 和分母中的 N(i) 都会增长。对于热门物品，分子 N(i) ∩ N(j) 的增长速度往往高于 N(i)，这就会使得物品 i 和很多其他的物品相似度都偏高，这就是 ItemCF 中的物品热门问题。推荐结果过于热门，会使得个性化感知下降。以歌曲相似度为例，大部分用户都会收藏《小苹果》这些热门歌曲，从而导致《小苹果》出现在很多的相似歌曲中。为了解决这个问题，我们对于物品 i 进行惩罚，例如下式， 当α∈(0, 0.5) 时，N(i) 越小，惩罚得越厉害，从而使热门物品相关性分数下降（ 博主注：这部分未充分理解 ）：
此外，Kary pis在研究中发现如果将ItemCF的相似度矩阵按最大值归一化， 可以提高推荐的准确率。 其研究表明， 如果已经得到了物品相似度矩阵w， 那么可以用如下公式得到归一化之后的相似度矩阵w'：
归一化的好处不仅仅在于增加推荐的准确度，它还可以提高推荐的覆盖率和多样性。一般来说，物品总是属于很多不同的类，每一类中的物品联系比较紧密。假设物品分为两类——A和B， A类物品之间的相似度为0.5， B类物品之间的相似度为0.6， 而A类物品和B类物品之间的相似度是0.2。 在这种情况下， 如果一个用户喜欢了5个A类物品和5个B类物品， 用ItemCF给他进行推荐， 推荐的就都是B类物品， 因为B类物品之间的相似度大。 但如果归一化之后， A类物品之间的相似度变成了1， B类物品之间的相似度也是1， 那么这种情况下， 用户如果喜欢5个A类物品和5个B类物品， 那么他的推荐列表中A类物品和B类物品的数目也应该是大致相等的。 从这个例子可以看出， 相似度的归一化可以提高推荐的多样性。
那么，对于两个不同的类，什么样的类其类内物品之间的相似度高，什么样的类其类内物品相似度低呢？一般来说，热门的类其类内物品相似度一般比较大。如果不进行归一化，就会推荐比较热门的类里面的物品，而这些物品也是比较热门的。因此，推荐的覆盖率就比较低。相反，如果进行相似度的归一化，则可以提高推荐系统的覆盖率。
最后，利用物品相似度矩阵和用户打过分的物品记录就可以对一个用户进行推荐评分：
基于用户的协同算法与基于物品的协同算法原理类似，只不过基于物品的协同是用户U购买了A物品，会计算经常有哪些物品与A一起购买（也即相似度），然后推荐给用户U这些与A相似的物品。而基于用户的协同则是先计算用户的相似性（通过计算这些用户购买过的相同的物品），然后将这些相似用户购买过的物品推荐给用户U。
基于用户的协同过滤算法主要包括两个步骤：
步骤（1）的关键是计算用户的兴趣相似度，主要是利用用户的行为相似度计算用户相似度。给定用户 u 和 v，N(u) 表示用户u曾经有过正反馈（譬如购买）的物品集合，N(v) 表示用户 v 曾经有过正反馈的物品集合。那么我们可以通过如下的 Jaccard 公式简单的计算 u 和 v 的相似度：
或通过余弦相似度：
得到用户之间的相似度之后，UserCF算法会给用户推荐和他兴趣最相似的K个用户喜欢的物品。如下的公式度量了UserCF算法中用户 u 对物品 i 的感兴趣程度：
首先回顾一下UserCF算法和ItemCF算法的推荐原理：UserCF给用户推荐那些和他有共同兴趣爱好的用户喜欢的物品， 而ItemCF给用户推荐那些和他之前喜欢的物品具有类似行为的物品。
（1）从推荐场景考虑
首先从场景来看，如果用户数量远远超过物品数量，如购物网站淘宝，那么可以考虑ItemCF，因为维护一个非常大的用户关系网是不容易的。其次，物品数据一般较为稳定，因此物品相似度矩阵不必频繁更新，维护代价较小。
UserCF的推荐结果着重于反应和用户兴趣相似的小群体的热点，而ItemCF的推荐结果着重于维系用户的历史兴趣。换句话说，UserCF的推荐更社会化，反应了用户所在小型兴趣群体中物品的热门程度，而ItemCF的推荐更加个性化，反应了用户自己的个性传承。因此UserCF更适合新闻、微博或微内容的推荐，而且新闻内容更新频率非常高，想要维护这样一个非常大而且更新频繁的表无疑是非常难的。
在新闻类网站中，用户的兴趣爱好往往比较粗粒度，很少会有用户说只看某个话题的新闻，而且往往某个话题也不是每天都会有新闻。 个性化新闻推荐更强调新闻热点，热门程度和时效性是个性化新闻推荐的重点，个性化是补充，所以 UserCF 给用户推荐和他有相同兴趣爱好的人关注的新闻，这样在保证了热点和时效性的同时，兼顾了个性化。
（2）从系统多样性（也称覆盖率，指一个推荐系统能否给用户提供多种选择）方面来看，ItemCF的多样性要远远好于UserCF，因为UserCF更倾向于推荐热门物品。而ItemCF具有较好的新颖性，能够发现长尾物品。所以大多数情况下，ItemCF在精度上较小于UserCF，但其在覆盖率和新颖性上面却比UserCF要好很多。
在介绍本节基于矩阵分解的隐语义模型之前，让我们先来回顾一下传统的矩阵分解方法SVD在推荐系统的应用吧。
基于SVD矩阵分解在推荐中的应用可分为如下几步：
SVD在计算前会先把评分矩阵 A 缺失值补全，补全之后稀疏矩阵 A 表示成稠密矩阵，然后将分解成 A' = U∑V T 。但是这种方法有两个缺点：（1）补成稠密矩阵后需要耗费巨大的储存空间，对这样巨大的稠密矩阵进行储存是不现实的；（2）SVD的计算复杂度很高，对这样大的稠密矩阵中进行计算式不现实的。因此，隐语义模型就被发明了出来。
更详细的SVD在推荐系统的应用可参考 奇异值分解SVD简介及其在推荐系统中的简单应用 。
隐语义模型（Latent Factor Model）最早在文本挖掘领域被提出，用于找到文本的隐含语义。相关的算法有LSI，pLSA，LDA和Topic Model。本节将对隐语义模型在Top-N推荐中的应用进行详细介绍，并通过实际的数据评测该模型。
隐语义模型的核心思想是通过隐含特征联系用户兴趣和物品。让我们通过一个例子来理解一下这个模型。
现有两个用户，用户A的兴趣涉及侦探小说、科普图书以及一些计算机技术书，而用户B的兴趣比较集中在数学和机器学习方面。那么如何给A和B推荐图书呢？
我们可以对书和物品的兴趣进行分类。对于某个用户，首先得到他的兴趣分类，然后从分类中挑选他可能喜欢的物品。简言之，这个基于兴趣分类的方法大概需要解决3个问题：
对于第一个问题的简单解决方案是找相关专业人员给物品分类。以图书为例，每本书出版时，编辑都会给出一个分类。但是，即使有很系统的分类体系，编辑给出的分类仍然具有以下缺点：（1）编辑的意见不能代表各种用户的意见；（2）编辑很难控制分类的细粒度；（3）编辑很难给一个物品多个分类；（4）编辑很难给一个物品多个分类；（5）编辑很难给出多个维度的分类；（6）编辑很难决定一个物品在某一个类别中的权重。
为了解决上述问题，研究员提出可以从数据出发，自动找到那些分类，然后进行个性化推荐。隐语义模型由于采用基于用户行为统计的自动聚类，较好地解决了上面提出的5个问题。
LFM将矩阵分解成2个而不是3个：
推荐系统中用户和物品的交互数据分为显性反馈和隐性反馈数据。隐式模型中多了一个置信参数，具体涉及到ALS（交替最小二乘法，Alternating Least Squares）中对于隐式反馈模型的处理方式——有的文章称为“加权的正则化矩阵分解”：
一个小细节：在隐性反馈数据集中，只有正样本（正反馈）没有负反馈（负样本），因此如何给用户生成负样本来进行训练是一个重要的问题。Rong Pan在其文章中对此进行了探讨，对比了如下几种方法：
用户行为很容易用二分图表示，因此很多图算法都可以应用到推荐系统中。基于图的模型（graph-based model）是推荐系统中的重要内容。很多研究人员把基于领域的模型也称为基于图的模型，因为可以把基于领域的模型看作基于图的模型的简单形式。
在研究基于图的模型之前，需要将用户行为数据表示成图的形式。本节的数据是由一系列用户物品二元组 (u, i) 组成的，其中 u 表示用户对物品 i 产生过行为。
令 G(V, E) 表示用户物品二分图，其中 V=V U UV I 由用户顶点 V U 和物品节点 V I 组成。对于数据集中每一个二元组 (u, i) ，图中都有一套对应的边 e(v u , v i )，其中 v u ∈V U 是用户对应的顶点，v i ∈V I 是物品i对应的顶点。如下图是一个简单的物品二分图，其中圆形节点代表用户，方形节点代表物品，用户物品的直接连线代表用户对物品产生过行为。比如下图中的用户A对物品a、b、d产生过行为。
度量图中两个顶点之间相关性的方法很多，但一般来说图中顶点的相关性主要取决于下面3个因素：
而相关性高的一对顶点一般具有如下特征：
举个例子，如下图，用户A和物品c、e没有边直连，但A可通过一条长度为3的路径到达c，而Ae之间有两条长度为3的路径。那么A和e的相关性要高于顶点A和c，因而物品e在用户A的推荐列表中应该排在物品c之前，因为Ae之间有两条路径。其中，（A,b,C,e）路径经过的顶点的出度为（3，2，2，2），而 (A,d,D,e) 路径经过了一个出度比较大的顶点D，所以 (A,d,D,e) 对顶点A与e之间相关性的贡献要小于（A,b,C,e）。
基于上面3个主要因素，研究人员设计了很多计算图中顶点相关性的方法，本节将介绍一种基于随机游走的PersonalRank算法。
假设要给用户u进行个性化推荐，可以从用户u对应的节点 v u 开始在用户物品二分图上进行随机游走。游走到任一节点时，首先按照概率α决定是继续游走还是停止这次游走并从 v u 节点重新开始游走。若决定继续游走，则从当前节点指向的节点中按照均匀分布随机选择一个节点作为游走下次经过的节点。这样，经过很多次随机游走后，每个物品被访问到的概率会收敛到一个数。最终的推荐列表中物品的权重就是物品节点的访问概率。
上述算法可以表示成下面的公式：
虽然通过随机游走可以很好地在理论上解释PersonalRank算法，但是该算法在时间复杂度上有明显的缺点。因为在为每个用户进行推荐时，都需要在整个用户物品二分图上进行迭代，知道所有顶点的PR值都收敛。这一过程的时间复杂度非常高，不仅无法在线进行实时推荐，离线计算也是非常耗时的。
有两种方法可以解决上面PersonalRank时间复杂度高的问题：
（1）减少迭代次数，在收敛之前停止迭代。但是这样会影响最终的精度。
（2）从矩阵论出发，重新涉及算法。另M为用户物品二分图的转移概率矩阵，即：
网络社交是当今社会非常重要甚至可以说是必不可少的社交方式，用户在互联网上的时间有相当大的一部分都用在了社交网络上。
当前国外最着名的社交网站是Facebook和Twitter，国内的代表则是微信/QQ和微博。这些社交网站可以分为两类：
需要指出的是，任何一个社交网站都不是单纯的社交图谱或兴趣图谱。如QQ上有些兴趣爱好群可以认识不同的陌生人，而微博中的好友也可以是现实中认识的。
社交网络定义了用户之间的联系，因此可以用图定义社交网络。我们用图 G(V,E,w) 定义一个社交网络，其中V是顶点集合，每个顶点代表一个用户，E是边集合，如果用户va和vb有社交网络关系，那么就有一条边 e(v a , v b ) 连接这两个用户，而 w(v a , v b )定义了边的权重。一般来说，有三种不同的社交网络数据：
和一般购物网站中的用户活跃度分布和物品流行度分布类似，社交网络中用户的入度（in degree，表示有多少人关注）和出度（out degree，表示关注多少人）的分布也是满足长尾分布的。即大部分人关注的人都很少，被关注很多的人也很少。
给定一个社交网络和一份用户行为数据集。其中社交网络定义了用户之间的好友关系，而用户行为数据集定义了不同用户的历史行为和兴趣数据。那么最简单的算法就是给用户推荐好友喜欢的物品集合。即用户u对物品i的兴趣 p ui 可以通过如下公式计算。
用户u和用户v的熟悉程度描述了用户u和用户在现实社会中的熟悉程度。一般来说，用户更加相信自己熟悉的好友的推荐，因此我们需要考虑用户之间的熟悉度。下面介绍3中衡量用户熟悉程度的方法。
（1）对于用户u和用户v，可以使用共同好友比例来计算他们的相似度：
上式中 out(u) 可以理解为用户u关注的用户合集，因此 out(u) ∩ out(v) 定义了用户u、v共同关注的用户集合。
（2）使用被关注的用户数量来计算用户之间的相似度，只要将公式中的 out(u) 修改为 in(u)：
in(u) 是指关注用户u的集合。在无向社交网络中，in(u)和out(u)是相同的，而在微博这种有向社交网络中，这两个集合的含义就不痛了。一般来说，本方法适合用来计算微博大V之间的相似度，因为大v往往被关注的人数比较多；而方法（1）适用于计算普通用户之间的相似度，因为普通用户往往关注行为比较丰富。
（3）除此之外，还可以定义第三种有向的相似度：这个相似度的含义是用户u关注的用户中，有多大比例也关注了用户v：
这个相似度有一个缺点，就是在该相似度下所有人都和大v有很大的相似度，这是因为公式中的分母并没有考虑 in(v) 的大小，所以可以把 in(v) 加入到上面公式的分母，来降低大v与其他用户的相似度：
上面介绍了3种计算用户之间相似度（或称熟悉度）的计算方法。除了熟悉程度，还需要考虑用户之间的兴趣相似度。我们和父母很熟悉，但很多时候我们和父母的兴趣确不相似，因此也不会喜欢他们喜欢的物品。因此，在度量用户相似度时，还需要考虑兴趣相似度，而兴趣相似度可以通过和UserCF类似的方法度量，即如果两个用户喜欢的物品集合重合度很高，两个用户的兴趣相似度很高。
最后，我们可以通过加权的形式将两种权重合并起来，便得到了各个好有用户的权重了。
有了权重，我们便可以针对用户u挑选k个最相似的用户，把他们购买过的物品中，u未购买过的物品推荐给用户u即可。打分公式如下：
其中 w' 是合并后的权重，score是用户v对物品的打分。
node2vec的整体思路分为两个步骤：第一个步骤是随机游走（random walk），即通过一定规则随机抽取一些点的序列；第二个步骤是将点的序列输入至word2vec模型从而得到每个点的embedding向量。
随机游走在前面基于图的模型中已经介绍过，其主要分为两步：（1）选择起始节点；（2）选择下一节点。起始节点选择有两种方法：按一定规则抽取一定量的节点或者以图中所有节点作为起始节点。一般来说会选择后一种方法以保证所有节点都会被选取到。
在选择下一节点方法上，最简单的是按边的权重来选择，但在实际应用中需要通过广度优先还是深度优先的方法来控制游走范围。一般来说，深度优先发现能力更强，广度优先更能使社区内（较相似）的节点出现在一个路径里。
斯坦福大学Jure Leskovec教授给出了一种可以控制广度优先或者深度优先的方法。
以上图为例，假设第一步是从t随机游走到v，这时候我们要确定下一步的邻接节点。本例中，作者定义了p和q两个参数变量来调节游走，首先计算其邻居节点与上一节点t的距离d，根据下面的公式得到α：
一般从每个节点开始游走5~10次，步长则根据点的数量N游走根号N步。如此便可通过random walk生成点的序列样本。
得到序列之后，便可以通过word2vec的方式训练得到各个用户的特征向量，通过余弦相似度便可以计算各个用户的相似度了。有了相似度，便可以使用基于用户的推荐算法了。
推荐系统需要根据用户的历史行为和兴趣预测用户未来的行为和兴趣，因此大量的用户行为数据就成为推荐系统的重要组成部分和先决条件。如何在没有大量用户数据的情况下设计个性化推荐系统并且让用户对推荐结果满意从而愿意使用推荐系统，就是冷启动问题。
冷启动问题主要分为三类：
针对用户冷启动，下面给出一些简要的方案：
（1）有效利用账户信息。利用用户注册时提供的年龄、性别等数据做粗粒度的个性化；
（2）利用用户的社交网络账号登录（需要用户授权），导入用户在社交网站上的好友信息，然后给用户推荐其好友喜欢的物品；
（3）要求用户在登录时对一些物品进行反馈，手机用户对这些物品的兴趣信息，然后给用推荐那些和这些物品相似的物品；
（4）提供非个性化推荐。非个性化推荐的最简单例子就是热门排行榜，我们可以给用户推荐热门排行榜，然后等到用户数据收集到一定的时候，在切换为个性化推荐。
对于物品冷启动，可以利用新加入物品的内容信息，将它们推荐给喜欢过和他们相似的物品的用户。
对于系统冷启动，可以引入专家知识，通过一定高效的方式快速建立起物品的相关度表。
在上面介绍了一些推荐系统的基础算法知识，这些算法大都是比较经典且现在还在使用的。但是需要注意的是，在实践中，任何一种推荐算法都不是单独使用的，而是将多种推荐算法结合起来，也就是混合推荐系统，但是在这里并不准备介绍，感兴趣的可以查阅《推荐系统》或《推荐系统与深度学习》等书籍。此外，在推荐中非常重要的点击率模型以及基于矩阵的一些排序算法在这里并没有提及，感兴趣的也可自行学习。
虽然现在用的很多算法都是基于深度学习的，但是这些经典算法能够让我们对推荐系统的发展有一个比较好的理解，同时，更重要的一点——“推陈出新”，只有掌握了这些经典的算法，才能提出或理解现在的一些更好地算法。
Ⅷ 推荐算法简介
在这个时代，无论是信息消费者还是信息生产者都遇到了很大的挑战:作为信息消费者，如何从大量信息中找到自己感兴趣的信息是一件非常困难的事情;作为信息生产者， 如何让自己生产的信息脱颖而出，受到广大用户的关注，也是一件非常困难的事情。推荐系统就是解决这一矛盾的重要工具。推荐系统的任务就是联系用户和信息，一方面帮助用户发现对自己有价值的信息，另一方面让信息能够展现在对它感兴趣的用户面前，从而实现信息消费者和信息 生产者的双赢。和搜索引擎不同的是，推荐系统不需要用户提供明确的需求，而是通过分析用户的历史行为给用 户的兴趣建模，从而主动给用户推荐能够满足他们兴趣和需求的信息 个性化推荐的成功需要两个条件。第一是存在 信息过载 ，因为如果用户可以很容易地从所有物品中找到喜欢的物品，就不需要个性化推荐。第二用 户大部分时候没有特别明确的需求 ，因为用户没有明确的需求，可以直接通过搜索引擎找到感兴趣的物品。
一个完整的推荐系统一般存在3个参与方：用户、物品提供者和提供推荐系统的网站。以图书推荐为例， 首先，推荐系统需要满足用户的需求，给用户推荐那些令他们感兴趣的图书。其次，推荐系统要让各出版社的书都能够被推荐给对其感兴趣的用户，而不是只推荐几个大型出版社的书。最后， 好的推荐系统设计，能够让推荐系统本身收集到高质量的用户反馈，不断完善推荐的质量，增加 用户和网站的交互，提高网站的收入。因此在评测一个推荐算法时，需要同时考虑三方的利益， 一个好的推荐系统是能够令三方共赢的系统。
推荐系统中，主要有3种评测推荐效果的实验方法，即离线实验(offline experiment)、用户调查(user study)和在线实验(online experiment)。
2.1 离线实验
离线实验的方法一般由如下几个步骤构成: (1) 通过日志系统获得用户行为数据，并按照一定格式生成一个标准的数据集; (2) 将数据集按照一定的规则分成训练集和测试集; (3) 在训练集上训练用户兴趣模型，在测试集上进行预测; (4) 通过事先定义的离线指标评测算法在测试集上的预测结果。
从上面的步骤可以看到，推荐系统的离线实验都是在数据集上完成的，也就是说它不需要一个实际的系统来供它实验，而只要有一个从实际系统日志中提取的数据集即可。这种实验方法的 好处是不需要真实用户参与，可以直接快速地计算出来，从而方便、快速地测试大量不同的算法。它的主要缺点是无法获得很多商业上关注的指标，如点击率、转化率等，而找到和商业指标非常相关的离线指标也是很困难的事情
2.2 用户调查
3.3 在线实验
在完成离线实验和必要的用户调查后，可以将推荐系统上线做 AB测试 ，将它和旧的算法进行比较。 AB测试 是一种很常用的在线评测算法的实验方法。它通过一定的规则将用户随机分成几组，并对不同组用户采取不同的算法，然后通过统计不同组用户的各种不同的评测指标比较不同算法的好坏。 AB测试的优点是可以公平获得不同算法实际在线时的性能指标，包括商业上关注的指标。 AB测试的缺点主要是周期比较长，必须进行长期的实验才能得到可靠的结果。因此一般不会用 AB测试测试所有的算法，而只是用它测试那些在离线实验和用户调查中表现很好的算法。其次， 一个大型网站的AB测试系统的设计也是一项复杂的工程。
一般来说，一个新的推荐算法最终上线，需要完成上面所说的3个实验。 1）首先，需要通过离线实验证明它在很多离线指标上优于现有的算法。 2）然后，需要通过用户调查确定它的用户满意度不低于现有的算法。 3）最后，通过在线的AB测试确定它在我们关心的指标上。
本节将介绍各种推荐系统的评测指标。这些评测指标可用于评价推荐系统各方面的性能。这 些指标有些可以定量计算，有些只能定性描述，有些可以通过离线实验计算，有些需要通过用户 调查获得，还有些只能在线评测。
(1) 用户满意度
用户作为推荐系统的重要参与者，其满意度是评测推荐系统的最重要指标。但是，用户满意度没有办法离线计算，只能通过用户调查或者在线实验获得。
在在线系统中，用户满意度主要通过一些 对用户行为的统计得到 。比如在电子商务网站中，用户如果购买了推荐的商品，就表示他们在一定程度上满意。因此，我们可以 利用购买率度量用 户的满意度 。此外，有些网站会通过设计一些用户 反馈界面收集用户满意度 。比如在视频网站中，都有对推荐结果满意或者不满意的 反馈按钮 ，通过统计两种按钮的单击情况就可以度量系统的用户满意度。更一般的情况下，我们可以用 点击率、用户停留时间和转化率等指标度量 用户的满意度。
(2) 预测准确度
预测准确度度量一个推荐系统或者推荐算法预测用户行为的能力。这个指标是最重要的推荐系统离线评测指标
在计算该指标时需要有一个离线的数据集，该数据集包含用户的历史行为记录。然后，将该数据集通过时间分成训练集和测试集。最后，通过在训练集上建立用户的行为和兴趣模型预测用户在测试集上的行为，并计算预测行为和测试集上实际行为的重合度作为预测准确度。 预测准确度指标有分为以下几种：
评分预测：
预测用户对物品评分的行为成为评分预测，在评分预测中，预测准确度一般通过均方根误差RMSE和平均绝对误差MAE计算，对于测试集中的一个用户u和物品i,令[图片上传失败...(image-62a797-1560412790460)] 是用户u对物品i的实际评分，而[图片上传失败...(image-28cfbc-1560412790460)] 是推荐算法给出的预测评分，那么RMSE定义为：
其中T为样本个数
MAE采用绝对值计算预测误差，它的定义为:
TopN推荐
网站在提供推荐服务时，一般是给用户一个个性化的推荐列表，这种推荐叫做TopN推荐。TopN推荐的预测准确率一般通过准确率(precision)/召回率(recall)度量。 令R(u)是根据用户在训练集上的行为给用户作出的推荐列表，而T(u)是用户在测试集上的行为列表。那么，推荐结果的召回率定义为:
推荐结果准确率定义：
(3) 覆盖率
覆盖率（coverage）描述一个推荐系统对物品长尾的发掘能力。覆盖率有不同的定义方法，最简单的定义为推荐系统能够推荐出来的物品占总物品集合的比例。假设系统的用户集合U，推荐系统给每个用户推荐一个长度为N的物品集合R（u）。那么推荐系统的覆盖率可以通过下面的公式计算：
I为总物品数
此外，从上面的定义也可以看到，热门排行榜的推荐覆盖率是很低的，它只会 推荐那些热门的物品，这些物品在总物品中占的比例很小。一个好的推荐系统不仅需要有比较高的用户满意度，也要有较高的覆盖率。
但是上面的定义过于粗略。覆盖率为100%的系统可以有无数的物品流行度分布。为了更细致地描述推荐系统发掘长尾的能力，需要统计推荐列表中不同物品出现次数的分布。如果所有的 物品都出现在推荐列表中，且出现的次数差不多，那么推荐系统发掘长尾的能力就很好。因此， 可以通过研究物品在推荐列表中出现次数的分布描述推荐系统挖掘长尾的能力。如果这个分布比 较平，那么说明推荐系统的覆盖率较高，而如果这个分布较陡峭，说明推荐系统的覆盖率较低。 在信息论和经济学中有两个着名的指标可以用来定义覆盖率。第一个是信息熵:
其中：n代表推荐列表中物品类别个数，p(i)代表每个类别的所占的比率
第二个指标是基尼系数：
(4) 多样性
为了满足用户广泛的兴趣，推荐列表需要能够覆盖用户不同的兴趣领域，即推荐结果需要具有多样性。多样性推荐列表的好处用一句俗话表示就是（不在一棵树上吊死）。尽管用户的兴趣在较长的时间跨度中是一样的。但具体到用户访问推荐系统的某一时刻，其兴趣往往是单一的，那么如果推荐列表只能覆盖用户的一个兴趣点，而这个兴趣点不是用户这个时刻的兴趣点，推荐结果就不会让用户满意。反之如果推荐列表表较多样，覆盖用户绝大多数的兴趣点，那么久会增加用户找到感兴趣物品的概率。因此给用户的推荐列表也需要满足用户广泛的兴趣，即具有多样性。
多样性描述了推荐列表中物品两两之间的不相似性，因此，多样性和相似性是对应的。假设s(i, j) ∈Î[0,1] 定义了物品i和j之间的相似度，那么用户u的推荐列表R(u)的多样性定义如下：
而推荐系统的整体多样性可以定义为所有用户推荐列表多样性的平均值：
(5) 新颖性
新颖的推荐是指给用户推荐那些他们以前没有听说过的物品。在一个网站中 实现新颖性 的最简单办法是，把那些用户之前在网站中对其有过行为的物品从推荐列表中过滤掉。比如在一个视 频网站中，新颖的推荐不应该给用户推荐那些他们已经看过、打过分或者浏览过的视频。 评测新颖度的最简单方法是利用推荐结果的平均流行度，因为越不热门的物品越 可能让用户觉得新颖。因此，如果推荐结果中物品的平均热门程度较低，那么推荐结果就可能有比较高的新颖性。
(6) 惊喜度
惊喜度(serendipity)是最近这几年推荐系统领域最热门的话题。如果推荐结果和用户的历史兴趣不相似，但却让用户觉得满意，那么就可以说推荐结果的惊喜度很高，而推荐的新颖性仅仅取决于用户是否听说过这个推荐结果。提高推荐惊喜度需要提高推荐结果的用户满意度，同时降低推荐结果和用户历史兴趣的相似度。
(7) 信任度
度量推荐系统的信任度只能通过问卷调查的方式，询问用户是否信任推荐系统的推荐结果。 提高推荐系统的信任度主要有两种方法。首先需要增加推荐系统的透明度(transparency)， 而增加推荐系统透明度的主要办法是提供推荐解释。只有让用户了解推荐系统的运行机制，让用 户认同推荐系统的运行机制，才会提高用户对推荐系统的信任度。其次是考虑用户的社交网络 信息，利用用户的好友信息给用户做推荐，并且用好友进行推荐解释。这是因为用户对他们的 好友一般都比较信任，因此如果推荐的商品是好友购买过的，那么他们对推荐结果就会相对比较信任
(8) 实时性
在很多网站中，因为物品(新闻、微博等)具有很强的时效性，所以需要在物品还具有时效 性时就将它们推荐给用户。 推荐系统的实时性包括两个方面。首先，推荐系统需要实时地更新推荐列表来满足用户新的 行为变化。实时性的第二个方面是推荐系统需要能够将新加入系统的物品推荐给用户。这主要考验了推 荐系统处理物品冷启动的能力。
(9) 健壮性
健壮性(即robust,鲁棒 性)指标衡量了一个推荐系统抗击作弊的能力。算法健壮性的评测主要利用模拟攻击。首先，给定一个数据集和一个算法，可以用这个算法 给这个数据集中的用户生成推荐列表。然后，用常用的攻击方法向数据集中注入噪声数据，然后 利用算法在注入噪声后的数据集上再次给用户生成推荐列表。最后，通过比较攻击前后推荐列表 的相似度评测算法的健壮性。如果攻击后的推荐列表相对于攻击前没有发生大的变化，就说明算 法比较健壮
(10) 商业目标
很多时候，网站评测推荐系统更加注重网站的商业目标是否达成，而商业目标和网站的盈利模式是息息相关的
(11) 总结
上一节介绍了很多评测指标，但是在评测系统中还需要考虑评测维度，比如一个推荐算法， 虽然整体性能不好，但可能在某种情况下性能比较好，而增加评测维度的目的就是知道一个算法 在什么情况下性能最好。这样可以为融合不同推荐算法取得最好的整体性能带来参考。
一般来说，评测维度分为如下3种。 1） 用户维度 ：主要包括用户的人口统计学信息、活跃度以及是不是新用户等。 2） 物品维度 ：包括物品的属性信息、流行度、平均分以及是不是新加入的物品等。 3） 时间维度 ：包括季节，是工作日还是周末，是白天还是晚上等。 如果能够在推荐系统评测报告中包含不同维度下的系统评测指标，就能帮我们全面地了解推 荐系统性能，找到一个看上去比较弱的算法的优势，发现一个看上去比较强的算法的缺点。