来还前两天的债了。后面是推荐系统的业务调研。

　　粘帖之前先说点八卦话题。最早知道数据挖掘和“尿布与啤酒”，是大一在贺仲雄老师那门妙趣横生的选秀课上，至今历历在目。包括后来两个月为了写那篇软件工程的论文，每天跑去图书馆查的资料，每一份内容都记得好清楚。再往后的三年，课堂上再也找不到那种感觉了，枯燥乏味死记硬背。最好玩的是，为了应付几门不同的选修课考试，连续三个学期，三次把“关联规则分析”和“梯度下降法”等算法的步骤背得贼熟，考完又很快忘掉。

　　工作之后，进入生物信息领域，视角逐渐小众。认识xVector还是因为去贝塔沙龙听技术讲座，粗心记错时间了，幸运地碰到了Resys线下聚会。此后就成了xVector的粉丝，只要他的公开讲座，就尽量去听。最近一次就是今年在上海的第二届中国推荐系统大会。后面这份调研笔记的内容，大部分都是从他的书《推荐系统实践》里抄来的。

　　今年连续参加了很多次数据处理的讲座，讨论。这份文档也算结果之一吧。

==============我是分割线，以上为无用的八卦内容===============

一、修改历史

　　略……

二、简介

　　随着ODPS系统被深入应用，在数仓团队以外，各个公司的BI团队也逐渐成为我们的用户。ODPS面临的需求也就逐渐拓展到数据挖掘领域。而推荐系统和个性化算法正是目前BI团队最典型的业务。

　　本文对推荐系统的领域现状、典型算法、业务流程进行梳理。这份调研不是学术性的论文、算法、专利的全面列举，而是站在产品和业务的立场进行分析，对经典的工业界常用算法进行介绍，如果涉及Big Data场景会重点关注和讨论。

　　涉及信息主要源于公开的网络、杂志、书籍和技术讲座。其中涉及淘宝推荐系统的涉密内容已删除，剩下的内容都可以在公网搜索到。

　　转载，请保留原作者http://wangleheng.net链接。

三、背景和应用案例

　　产品太多的情况下，用户面临信息过载，解决这个问题的方案包括分类目录、搜索引擎和推荐系统。前两种方案中用户知道自己想要什么，而推荐系统则更加主动。

　　推荐系统通过挖掘用户的各种数据，找到其个性化的需求，将长尾商品推荐给需要它的用户，帮助用户发现那些感兴趣但很难发现的商品。目前已经投入工业实用的知名推荐系统包括：

业务领域	著名产品名称	网址	国内类似产品
电子商务	亚马逊图书推荐	www.amazon.com	豆瓣读书
电影视频	Netflix视频推荐	www.netflix.com	暴风影音、（hulu）
个性化音乐	Pandora和Last.fm	www.pandora.com www.Last.fm	豆瓣电台
社交网络偏好推荐	Facebook Instant Personalization	facebook.com/instantpersonalization	新浪微博
个性化阅读	Google Reader Digg 新闻排序	www.google.com/reader www.digg.com	百度新闻猜您喜欢
LBS	Foursquare客户端	foursquare.com/apps	大众点评客户端
个性化邮件	Gmail优先收件	gmail.com
定向广告投放	Facebook 目标投放	facebook.com-> creat a Ad

　　推荐系统的评价依赖于各种指标：用户满意度、预测准确度、覆盖率、多样性、新颖性、惊喜度。要测量这些指标，有些可以采用离线计算方式，有些则必须采用A/B对照组在线实验。真正的工业化实践中，往往是在诸多指标中寻求平衡，并记录业务效果，所以最终的衡量标准往往还得看点击率和转化率。

四、针对各种业务数据类型的经典算法方案

4.1. 利用用户浏览、购买、评价的记录数据

　　基于用户行为的应用，最典型的就是各种排行榜，例如淘宝指数。

　　早期数据挖掘领域最经典方法是基于销售数据的关联规则发现，一个被反复提起的行业故事是“尿布和啤酒”的故事。这个阶段，数据挖掘算法的主要业务客户来自于金融、电信、零售，这些行业才有条件和动力收集自己的业务数据。

　　而进入互联网时代，协同过滤等算法成为主流算法。这种方法的基础是网站记录下来的用户行为数据。和前面提到“尿布啤酒”案例中的数据相比，互联网应用除了记录下产品的销售数据以外，还拥有每个用户（账号或客户端）的独立行为数据，这样就可以进一步针对每个用户进行个性化推荐。

　　目前工业界最常用的协同过滤算法有两种：基于用户的（user based collaborative filtering）和基于物品的（item based collaborative filtering）协同过滤算法。另外隐语义模型（latent factor model）算法也比较受关注。

4.1.1基于用户的协同过滤算法

　　基于用户的协同过滤算法是整个推荐系统领域最早最经典的算法。这个算法在1992年的提出标志着推荐系统的诞生。目前最著名的使用者是Digg新闻推荐系统。

　　基于用户的协同过滤算法主要包括两个步骤：
　　1> 找到与目标用户兴趣相似的用户集合；
　　2> 找到这个集合中用户喜欢的、且目标用户尚未点击/购买/观看的物品给目标用户。

　　对于步骤1>，要计算两个用户的兴趣相似度。从日志数据里，可以得到两个用户曾经有过正面反馈的物品集合，然后把这两个集合通过Jaccard公式（交集数除以并集数）或通过余弦夹角计算出其距离。

　　有了距离公式，求对于某个用户最相似的Top N用户，就成了一个典型的KNN算法。如果用双层循环，硬算用户两两之间的距离，其时间复杂度是平方级的。

　　但现实情况下，实际上很多用户之间是没有任何交集的，我们可以首先计算交集，只有不为零的用户对才除以分母的并集部分。这就节省了很大一部分计算量。具体算法里可以空间换时间，先创建“物品到用户”的倒排索引，再建立一个稀疏矩阵C用于存储两个用户之间的交集总数。只要扫描所有物品的倒排索引，将其中包含的所有用户之间的交集数加1（利用C），最终就可以得到所有用户之间不为零的交集（也就是C的内容）。

　　得到用户之间的兴趣相似度之后，就开始步骤2>，这就相对比较简单了，只要用一个双重循环，就可以把与目标用户最接近的Top N个用户涉及到的所有物品进行排列，然后再挑选出其中目标用户没有涉及过的前K个产品。

　　对于这个算法，还可以通过各种手段进行预处理，进一步提高效果。一个最常见的问题是“哈里波特现象”，也就是大热的畅销商品导致所有用户之间都有虚假的联系，既增加了运算量，也干扰了预测结果，降低了惊喜度。因此可以对畅销热门商品施加一个权重惩罚值。

4.1.2基于物品的协同过滤算法

　　基于用户的协同过滤算法，其时间复杂度是与用户数目相关的。在大多数电子商务网站上，物品数都是大大小于用户数的。因此亚马逊最早应用了基于物品的协同过滤算法。这个算法目前成了业界应用最多的算法。反过来，Digg、新浪微博等新闻类网站仍然坚持使用基于用户的协同过滤算法，是由于这些网站上的物品（新闻帖子）的数目都是大于用户数的,而且这些物品会的很快过时（几天甚至几个小时）。

　　基于物品的协同过滤算法主要分为两步：
　　1> 计算物品之间的相似度；
　　2> 根据物品的相似度和用户的数据给用户生成推荐结果。

　　与基于用户的协同过滤算法类似，基于物品的协同过滤算法的计算也可以首先建立“用户到物品”的倒排索引，然后对每个用户，将他物品列表中物品两两在矩阵C中加 1。然后将矩阵归一化就可以得到物品之间的余弦夹角。

　　除了前面提到的“哈里波特现象”，基于物品的协同过滤算法也会被“超级买家现象”干扰。如果有用户大量购买各种商品（例如职业出版人和评论家）则会导致算法性能下降，因此需要对过于活跃的用户进行权重惩罚。

　　另外，为了增加推荐的覆盖率和多样性，应该对前面的相似度矩阵C按最大值归一化。这样就能保证被推荐的商品不仅仅来自一个类型中心附近。

4.2. 利用用户对产品的个性化标签（UGC tags）

　　UGC标签系统是很多Web 2.0网站的重要组成部分。使用标签数据进行推荐的网站包括Delicious、Last.fm和豆瓣。

　　基本的利用用户标签个性化推荐算法包括以下几步：
　　1> 统计每个用户最常用的标签；
　　2> 对于每个标签，统计被打过这个标签最多的物品；
　　3> 对于目标用户通过他的常用标签，查找这些标签对应的热门物品，删重并推荐。

　　上面方法倾向于推荐热门标签和热门物品，降低了新颖性。可以借鉴搜索引擎TF/IDF的思路，对热门标签和热门物品进行适当惩罚。

　　进一步，可以适当对标签集合做聚类，计算标签之间的相似度，对标签进行拓展，从而对标签历史比较少的新用户或新物品提供更多推荐。对于相似度的度量，可以认为当两个标签同时出现在很多物品的标记中时，它们相似度较高。因此我们可以利用常规的余弦夹角来计算标签的相似度。

　　再进一步，可以通过清理一些区分性不好的标签，以便提高算法精度，例如词频很高的停止词。也可以让编辑和运营人员进行整理。

4.3. 利用上下文和社交网络数据

　　上下文信息和社交网络数据，均可以为主力推荐算法提供补充，作为参数输入到前面提到的经典算法当中去。

　　例如，利用时间上下文，可以给物品设定一个半衰期，让较新的物品排在前面，这种做法对新闻类的Web 2.0网站很常见。

　　再如，利用位置信息上下文，对很多LBS类应用很关键。具体计算时，可以先对目标用户进行个性化推荐，再利用他所在位置得到一个用户集合，利用这个集合的信息再给出另一个推荐结果，最后把两个推荐结果进行综合。

　　还有，如果能得到一个用户的社交网络信息，就可以获得他的熟人圈子和关注对象列表。基于友好用户的兴趣来推荐或解释推荐结果，对目标用户的感受而言会更加可信。尤其是对于信息流的推荐，更加适合使用社交网络的信息。

　　此外，社交网络的一个标准模块是好友推荐。最常规的方法是推荐“好友的好友”。

五、淘宝的推荐系统的特点

5.1. 业务场景

　　淘宝的推荐系统主要涉及以下这些业务场景：
　　1>Detail 浏览了还浏览
　　2>收藏夹弹出层推荐
　　3>购物车弹出层推荐
　　4>已买到宝贝你可能感兴趣
　　5>淘宝无线应用
　　6>EDM（重复购买提醒）
　　7>各个垂直频道
　　8>个性化list排序

5.2. 算法应用

　　淘宝推荐系统主要用到了聚类算法，预测算法，分类算法等基础算法产生基础知识库；利用协同过滤算法、基于标签的推荐算法和关联规则发现算法进行推荐。应用方式说明如下：

　　预测算法，例如logistic 回归，通过以点击率为目标，以商品，卖家等因素作为指标，建立预测模型构建淘宝优质宝贝库。

　　分类算法，例如朴素朴素贝叶斯算法，用于对商品和用户进行性别判断（男性、女性、中性）。

　　聚类算法，例如k-means算法，用于对人群进行细分，例如客户流失分析；也用于Big Data条件下的降维。

　　关联规则发现算法，用于发现类目、商品和用户的相关性。

　　协同过滤算法，提供长尾新奇商品的个性化推荐，遇到的问题主要是冷启动。

　　基于标签的推荐算法，优势是实现简单，且与搜索引擎容易配合，缺点是难以区分商品品质，无法照顾惊喜度。

5.3. 特点和需求

　　淘宝推荐系统的特点是用户、商品、类目和商铺的数量都很惊人（数百万店铺信息、4.4亿激活用户、8亿在线商品、数十亿收藏标签、每分钟销售商品4.8万件）。因此前文提到的多数单机内存算法，都面临大数据下的分布式化改写的问题。除此之外，淘宝TCIF团队还希望融入更多信息，例如支付信息，用户访问的第三方网站PV等等。

　　淘宝推荐系统的评价指标包括CTR、GMV和转化率。

　　略……

六、参考文献

　　《推荐系统实践》，2012年6月，项亮，人民邮电出版社
　　《推荐系统@淘宝》，2012 年 7月，空望，百度文库
　　《淘宝网TCIF案例分析：基于海量数据下的消费者研究》，2012年4月，必达，2012数据库技术大会
　　《淘宝海量数据技术》，2011年 11月，空无，百度文库