推荐引擎概述(2015/4/21)
1 分类
1.1 不同的用户推荐是否相同
1.1.1 根据大众行为的推荐引擎
对每个用户都给出同样的推荐，这些推荐可以是静态的由系统管理员人工设定的，或者基于系统所有用户的反馈统计计算出的当下比较流行的物品，比如TOPN推荐。
1.1.2 个性化推荐引擎
对不同的用户，根据他们的口味和喜好给出更加精确的推荐，这时，系统需要了解需推荐内容和用户的特质，或者基于社会化网络，通过找到与当前用户相同喜好的用户，实现推荐。
1.2 根据数据源
1.2.1 基于内容的推荐
根据推荐物品或内容的元数据，发现物品或者内容的相关性。
特点：
（1）需要对物品进行分析和建模，推荐的质量依赖于对物品模型的完整和全面程度。
（2）没有冷启动的问题。
（3）适用于类新闻推荐的应用。这类应用的特点是物品的数量远远大于用户的数量，计算量小。
1.2.2 基于协同过滤的推荐
根据用户的行为，包括其它用户的行为(这就是协同的意思)，发现用户或物品之间的相关性。
1.3 根据推荐模型的建立方式
1.3.1 基于物品或用户
基于物品和用户本身的，这种推荐引擎将每个用户和每个物品都当作独立的实体，预测每个用户对于每个物品的喜好程度，这些信息往往是用一个二维矩阵描述的。
1.3.2 基于关联规则
基于关联规则的推荐（Rule-basedRecommendation）：挖掘一些数据的依赖关系，典型的场景就是“购物篮问题”，通过关联规则的挖掘，我们可以找到哪些物品经常被同时购买，或者用户购买了一些物品后通常会购买哪些其他的物品，当我们挖掘出这些关联规则之后，我们可以基于这些规则给用户进行推荐。
1.3.3 基于模型
基于模型的推荐（Model-basedRecommendation）：这是一个典型的机器学习的问题，可以将已有的用户喜好信息作为训练样本，训练出一个预测用户喜好的模型，这样以后用户在进入系统，可以基于此模型计算推荐。这种方法的问题在于如何将用户实时或者近期的喜好信息反馈给训练好的模型，从而提高推荐的准确度。
1.4 混合的推荐机制
在现行的 Web 站点上的推荐往往都不是单纯只采用了某一种推荐的机制和策略，他们往往是将多个方法混合在一起，从而达到更好的推荐效果。关于如何组合各个推荐机制，这里讲几种比较流行的组合方法。
加权的混合（Weighted Hybridization）: 用线性公式（linear formula）将几种不同的推荐按照一定权重组合起来，具体权重的值需要在测试数据集上反复实验，从而达到最好的推荐效果。
切换的混合（Switching Hybridization）：前面也讲到，其实对于不同的情况（数据量，系统运行状况，用户和物品的数目等），推荐策略可能有很大的不同，那么切换的混合方式，就是允许在不同的情况下，选择最为合适的推荐机制计算推荐。
分区的混合（Mixed Hybridization）：采用多种推荐机制，并将不同的推荐结果分不同的区显示给用户。其实，Amazon，当当网等很多电子商务网站都是采用这样的方式，用户可以得到很全面的推荐，也更容易找到他们想要的东西。
分层的混合（Meta-Level Hybridization）: 采用多种推荐机制，并将一个推荐机制的结果作为另一个的输入，从而综合各个推荐机制的优缺点，得到更加准确的推荐。
2 应用
2.1 亚马逊
Amazon作为推荐引擎的鼻祖。对应于上面介绍的各种推荐机制，Amazon 采用的是分区的混合的机制，并将不同的推荐结果分不同的区显示给用户。
Amazon利用可以记录的所有用户在站点上的行为，根据不同数据的特点对它们进行处理，并分成不同区为用户推送推荐：
· 今日推荐 (Today's Recommendation For You): 通常是根据用户的近期的历史购买或者查看记录，并结合时下流行的物品给出一个折中的推荐。
· 新产品的推荐 (New For You): 采用了基于内容的推荐机制 (Content-based Recommendation)，将一些新到物品推荐给用户。在方法选择上由于新物品没有大量的用户喜好信息，所以基于内容的推荐能很好的解决这个“冷启动”的问题。
· 捆绑销售 (Frequently Bought Together): 采用数据挖掘技术对用户的购买行为进行分析，找到经常被一起或同一个人购买的物品集，进行捆绑销售，这是一种典型的基于项目的协同过滤推荐机制。
· 别人购买 / 浏览的商品 (CustomersWho Bought/See This Item Also Bought/See): 这也是一个典型的基于项目的协同过滤推荐的应用，通过社会化机制用户能更快更方便的找到自己感兴趣的物品。
值得一提的是，Amazon 在做推荐时，设计和用户体验也做得特别独到：
Amazon利用有它大量历史数据的优势，量化推荐原因。
· 基于社会化的推荐，Amazon 会给你事实的数据，让用户信服，例如：购买此物品的用户百分之多少也购买了那个物品；
· 基于物品本身的推荐，Amazon 也会列出推荐的理由，例如：因为你的购物框中有 ***，或者因为你购买过 ***，所以给你推荐类似的 ***。
另外，Amazon 很多推荐是基于用户的profile 计算出来的，用户的 profile 中记录了用户在 Amazon 上的行为，包括看了那些物品，买了那些物品，收藏夹和 wish list 里的物品等等，当然 Amazon 里还集成了评分等其他的用户反馈的方式，它们都是 profile 的一部分，同时，Amazon 提供了让用户自主管理自己profile 的功能，通过这种方式用户可以更明确的告诉推荐引擎他的品味和意图是什么。
2.2 豆瓣
豆瓣是国内做的比较成功的社交网站，它以图书，电影，音乐和同城活动为中心，形成一个多元化的社交网络平台，自然推荐的功能是必不可少的，下面我们看看豆瓣是如何推荐的。
当你在豆瓣电影中将一些你看过的或是感兴趣的电影加入你看过和想看的列表里，并为它们做相应的评分，这时豆瓣的推荐引擎已经拿到你的一些偏好信息，那么它将给你展示如图 8 的电影推荐。
豆瓣的推荐是通过“豆瓣猜”，为了让用户清楚这些推荐是如何来的，豆瓣还给出了“豆瓣猜”的一个简要的介绍。
“你的个人推荐是根据你的收藏和评价自动得出的，每个人的推荐清单都不同。你的收藏和评价越多，豆瓣给你的推荐会越准确和丰富。每天推荐的内容可能会有变化。随着豆瓣的长大，给你推荐的内容也会越来越准。”
这一点让我们可以清晰明了的知道，豆瓣必然是基于社会化的协同过滤的推荐，这样用户越多，用户的反馈越多，那么推荐的效果会越来越准确。
相对于 Amazon 的用户行为模型，豆瓣电影的模型更加简单，就是“看过”和“想看”，这也让他们的推荐更加专注于用户的品味，毕竟买东西和看电影的动机还是有很大不同的。
另外，豆瓣也有基于物品本身的推荐，当你查看一些电影的详细信息的时候，他会给你推荐出“喜欢这个电影的人也喜欢的电影”。
3 算法
3.1 基于用户 VS 基于物品
前面介绍了 User CF 和 Item CF 的基本原理，下面我们分几个不同的角度深入看看它们各自的优缺点和适用场景：
· 计算复杂度
Item CF 和 User CF 是基于协同过滤推荐的两个最基本的算法，User CF 是很早以前就提出来了，Item CF 是从 Amazon 的论文和专利发表之后（2001 年左右）开始流行，大家都觉得 Item CF 从性能和复杂度上比 User CF 更优，其中的一个主要原因就是对于一个在线网站，用户的数量往往大大超过物品的数量，同时物品的数据相对稳定，因此计算物品的相似度不但计算量较小，同时也不必频繁更新。但我们往往忽略了这种情况只适应于提供商品的电子商务网站，对于新闻，博客或者微内容的推荐系统，情况往往是相反的，物品的数量是海量的，同时也是更新频繁的，所以单从复杂度的角度，这两个算法在不同的系统中各有优势，推荐引擎的设计者需要根据自己应用的特点选择更加合适的算法。
· 适用场景
在非社交网络的网站中，内容内在的联系是很重要的推荐原则，它比基于相似用户的推荐原则更加有效。比如在购书网站上，当你看一本书的时候，推荐引擎会给你推荐相关的书籍，这个推荐的重要性远远超过了网站首页对该用户的综合推荐。可以看到，在这种情况下，Item CF 的推荐成为了引导用户浏览的重要手段。同时 Item CF 便于为推荐做出解释，在一个非社交网络的网站中，给某个用户推荐一本书，同时给出的解释是某某和你有相似兴趣的人也看了这本书，这很难让用户信服，因为用户可能根本不认识那个人；但如果解释说是因为这本书和你以前看的某本书相似，用户可能就觉得合理而采纳了此推荐。
研究推荐引擎的学者们在相同的数据集合上分别用 User CF 和 Item CF 计算推荐结果，发现推荐列表中，只有 50% 是一样的，还有 50% 完全不同。但是这两个算法确有相似的精度，所以可以说，这两个算法是很互补的。
关于推荐的多样性，有两种度量方法：
第一种度量方法是从单个用户的角度度量，就是说给定一个用户，查看系统给出的推荐列表是否多样，也就是要比较推荐列表中的物品之间两两的相似度，不难想到，对这种度量方法，Item CF 的多样性显然不如 User CF 的好，因为 Item CF 的推荐就是和以前看的东西最相似的。
第二种度量方法是考虑系统的多样性，也被称为覆盖率 (Coverage)，它是指一个推荐系统是否能够提供给所有用户丰富的选择。在这种指标下，Item CF 的多样性要远远好于 User CF, 因为 User CF 总是倾向于推荐热门的，从另一个侧面看，也就是说，Item CF 的推荐有很好的新颖性，很擅长推荐长尾里的物品。所以，尽管大多数情况，Item CF 的精度略小于 User CF，但如果考虑多样性，Item CF 却比 User CF 好很多。
如果你对推荐的多样性还心存疑惑，那么下面我们再举个实例看看 User CF 和 Item CF 的多样性到底有什么差别。首先，假设每个用户兴趣爱好都是广泛的，喜欢好几个领域的东西，不过每个用户肯定也有一个主要的领域，对这个领域会比其他领域更加关心。给定一个用户，假设他喜欢 3 个领域 A,B,C，A 是他喜欢的主要领域，这个时候我们来看 User CF 和 Item CF 倾向于做出什么推荐：如果用 User CF, 它会将 A,B,C 三个领域中比较热门的东西推荐给用户；而如果用 ItemCF，它会基本上只推荐 A 领域的东西给用户。所以我们看到因为 User CF 只推荐热门的，所以它在推荐长尾里项目方面的能力不足；而 Item CF 只推荐 A 领域给用户，这样他有限的推荐列表中就可能包含了一定数量的不热门的长尾物品，同时 Item CF 的推荐对这个用户而言，显然多样性不足。但是对整个系统而言，因为不同的用户的主要兴趣点不同，所以系统的覆盖率会比较好。
从上面的分析，可以很清晰的看到，这两种推荐都有其合理性，但都不是最好的选择，因此他们的精度也会有损失。其实对这类系统的最好选择是，如果系统给这个用户推荐 30 个物品，既不是每个领域挑选 10 个最热门的给他，也不是推荐 30 个 A 领域的给他，而是比如推荐 15 个 A 领域的给他，剩下的 15 个从 B,C 中选择。所以结合 User CF 和 Item CF 是最优的选择，结合的基本原则就是当采用 Item CF 导致系统对个人推荐的多样性不足时，我们通过加入 User CF 增加个人推荐的多样性，从而提高精度，而当因为采用 User CF 而使系统的整体多样性不足时，我们可以通过加入 Item CF 增加整体的多样性，同样同样可以提高推荐的精度。
3.2 Apache Mahout
Apache Mahout 是 Apache Software Foundation (ASF) 旗下的一个开源项目，提供一些可扩展的机器学习领域经典算法的实现，旨在帮助开发人员更加方便快捷地创建智能应用程序，并且，在 Mahout 的最近版本中还加入了对 Apache Hadoop 的支持，使这些算法可以更高效的运行在云计算环境中。
支持基于用户、基于物品、slope one算法。
3.2.1 slope One算法
3.2.1.1基本slope one算法
slope one的基本算法很简单。 例, 用户X, Y和A都对Item1打了分。 同时用户X,Y还对Item2打了分, 用户A对Item2可能会打多少分呢?
|
User |
Rating to Item 1 |
Rating to Item 2 |
|
X |
5 |
3 |
|
Y |
4 |
3 |
|
A |
4 |
? |
图1
根据slope one算法, 应该是:4 +((3-5) + (3-4)) / 2 = 2.5。
解释一下。用户X对Item1的rating是5, 对Item2的rating是3, 那么他可能认为Item2应该比Item1少2分。 同时用户Y认为Item2应该比Item1少1分。 据此我们知道所有对Item1和Item2都打了分的用户认为Item2会比Item1平均少(2+1)/2=1.5分。 所以我们有理由推荐用户A可能会对Item2打(4+(-1.5))=2.5分。
很简单是不是? 找到对Item1和Item2都打过分的用户, 算出rating差的平均值, 这样我们就能推测出对Item1打过分的用户A对Item2的可能rating, 并据此向A用户推荐新项目。这里我们能看出slope one算法的一个很大的优点, 在只有很少的数据时候也能得到一个相对准确的推荐, 这一点可以解决冷启动(Cold Start)问题。
3.2.1.2加权slope one算法(weighted slope one)
如果有100个用户对Item1和Item2都打过分, 有1000个用户对Item3和Item2也打过分， 显然这两个rating差的权重是不一样的。 因此我们的计算方法是
3.2.1.3双极slope one算法(bi-polar slope one)
|
user |
item1 |
item2 |
item3 |
item4 |
平均值 |
|
A |
5 |
7 |
9 |
8 |
7.25 |
|
B |
6 |
2 |
10 |
2 |
5 |
|
C |
1 |
3 |
4 |
10 |
4.5 |
|
D |
10 |
1 |
6 |
? |
4.25 |
图 2
双极slope one算法是在加权slope one算法上进行了优化。
以userA为例，userA的评分的平均值为(5+7+9+8)/4=7.25，据此我把item分为两类，like item和dislike items。其中like item是评分小于平均值7.25的item，包括item1(5)；dislikeitem是评分小于均分7.25的item，包括item2(7)、item3(9)、item4(10)。
同理userB，likeitem包括item1、item3；dislike item包括item2、item4。
userC，like item包括item4；dislikeitem包括item1，item2，item3。
userD，like item包括item1、item3；dislike item包括item2。
计算rating差的两个item要么均是like item，要么均是dislike item，否则过滤掉。例如计算 rating 3 to 4。在userC的评分中，item3是dislike item 而item4是like item；userB评分中，item3是like item而item4是dislikeitem；userA评分中，item3和item4均是like item。所以计算rating 3 to 4 时，只需关注userA。rating 3 to 4 = 6 + (8 - 9)
同理，计算item 2 to 4，需关注userB。所以item 2 to 4 =1 + (2 - 2)
计算item 1 to 4时，没有符合条件的user。最终我们估计userD对item4的评分是
(1* rating 3 to4 + 1* item 2 to 4 + 0* item 1 to 4) / (1+1+0)。
3.2.1.4 总结
这就是 Slope One 推荐的基本原理，它将用户的评分之间的关系看作简单的线性关系：Y = mX + b; 当 m = 1 时就是Slope One，也就是我们刚刚展示的基本slope one算法例子。
该算法的简洁特性使它们的实现简单而高效，而且其精确度与其它复杂费时的算法相比也不相上下。该系列算法也被用来改进其它算法。
3.3 相似度的计算
加入有两个用户，user1和user2，这两个用户对物品评分如下表。
|
|
Item 1 |
Item 2 |
Item 3 |
|
User1 |
5 |
4 |
1 |
|
User2 |
3 |
5 |
1 |
3.3.1 欧几里德距离（Euclidean Distance）
最初用于计算欧几里德空间中两个点的距离，假设 x，y 是 n 维空间的两个点，它们之间的欧几里德距离是：
可以看出，当 n=2 时，欧几里德距离就是平面上两个点的距离。
当用欧几里德距离表示相似度，一般采用以下公式进行转换：距离越小，相似度越大。
3.3.2 cosine相似度
3.3.3 皮尔逊相关系数（Pearson CorrelationCoefficient）
我们需要考虑用户间的评分习惯的差异，d用户可能喜欢打高分，e用户喜欢打低分，f用户喜欢乱打分。
pearson其实做的事情就是先把两个向量都减去他们的平均值，然后再计算cosine值。
3.3.4 Tanimoto 系数（Tanimoto Coefficient）
Tanimoto 系数也称为 Jaccard 系数，是 Cosine 相似度的扩展，也多用于计算文档数据的相似度：