来还前两天的债了。后面是推荐系统的业务调研。
粘帖之前先说点八卦话题。最早知道数据挖掘和“尿布与啤酒”,是大一在贺仲雄老师那门妙趣横生的选秀课上,至今历历在目。包括后来两个月为了写那篇软件工程的论文,每天跑去图书馆查的资料,每一份内容都记得好清楚。再往后的三年,课堂上再也找不到那种感觉了,枯燥乏味死记硬背。最好玩的是,为了应付几门不同的选修课考试,连续三个学期,三次把“关联规则分析”和“梯度下降法”等算法的步骤背得贼熟,考完又很快忘掉。
工作之后,进入生物信息领域,视角逐渐小众。认识xVector还是因为去贝塔沙龙听技术讲座,粗心记错时间了,幸运地碰到了Resys线下聚会。此后就成了xVector的粉丝,只要他的公开讲座,就尽量去听。最近一次就是今年在上海的第二届中国推荐系统大会。后面这份调研笔记的内容,大部分都是从他的书《推荐系统实践》里抄来的。
今年连续参加了很多次数据处理的讲座,讨论。这份文档也算结果之一吧。
==============我是分割线,以上为无用的八卦内容===============
推荐系统业务调研
一、修改历史
略……
二、简介
随着ODPS系统被深入应用,在数仓团队以外,各个公司的BI团队也逐渐成为我们的用户。ODPS面临的需求也就逐渐拓展到数据挖掘领域。而推荐系统和个性化算法正是目前BI团队最典型的业务。
本文对推荐系统的领域现状、典型算法、业务流程进行梳理。这份调研不是学术性的论文、算法、专利的全面列举,而是站在产品和业务的立场进行分析,对经典的工业界常用算法进行介绍,如果涉及Big Data场景会重点关注和讨论。
涉及信息主要源于公开的网络、杂志、书籍和技术讲座。其中涉及淘宝推荐系统的涉密内容已删除,剩下的内容都可以在公网搜索到。
转载,请保留原作者http://wangleheng.net链接。
三、背景和应用案例
产品太多的情况下,用户面临信息过载,解决这个问题的方案包括分类目录、搜索引擎和推荐系统。前两种方案中用户知道自己想要什么,而推荐系统则更加主动。
推荐系统通过挖掘用户的各种数据,找到其个性化的需求,将长尾商品推荐给需要它的用户,帮助用户发现那些感兴趣但很难发现的商品。目前已经投入工业实用的知名推荐系统包括:
推荐系统的评价依赖于各种指标:用户满意度、预测准确度、覆盖率、多样性、新颖性、惊喜度。要测量这些指标,有些可以采用离线计算方式,有些则必须采用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月,空无,百度文库