Tag Archives: 贺仲雄

推荐系统业务调研

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

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

  工作之后,进入生物信息领域,视角逐渐小众。认识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月,空无,百度文库

贺仲雄老师走了

  摔断了胳膊,昨天去医院打石膏,回来才得到消息,贺老师1月5日告别仪式,没赶上送行,郁闷。

  gem老大说:“人生路上总有有限的几个人如明灯,如父亲。请接受学生在此的祈祷。默哀”。

  坦率地说,本科期间太贪玩,我并没有从课堂上学到多少真本事:数据结构和算法大多是高中时代参加全国信息学奥赛的基础,而工程经验都来自兼职打工,英语又是后来为了考托福才到新东方补的。要说收获,就数贺教授退休后,面向低年级本科生开的那门特立独行的选修课了。

  上课时从来都人山人海,好多外校学生来旁听。贺老师不讲具体知识,而是“授之以渔”,教你如何寻找感兴趣的课题和方法,如何去图书馆查资料,如何利用互联网收集最新科研动态。期末考试时,有个的独特要求:“可以打小抄递条子,但必须从图书馆借三本以上参考书带入考场,否则以作弊论处!”,考试的题目是,《这六个月你做了哪些创新?》,发表了论文或申请了专利的学生,可以不来考试,成绩100分。

  特别强调专注和独特,“人和人不同,所以成功的方式必然各自不同”,要求每个学生只关注自己感兴趣的独特领域,要结合创新和实用。记得一位喜欢足球的小伙,应用模糊数学方法写了一个预测比赛输赢的算法,虽然预测结果很不靠谱,还是受到大大赞扬,期末成绩是101;还有个外校旁听的学生,利用数据挖掘和决策支持技术,改进了自己父亲经营的摩托车厂的流水线,贺老师非常高兴,让他上讲台给大家讲课;著名的“数学和诗”讲座,估计很多人都知道,用数学方法来研究李白,听众都张大嘴。

  贺老师给我个人带来,远不只限于大一发表的那篇软件工程学术论文,而是创新的技巧和独立思考的勇气,一笔无价的财富。

  胳膊骨折,打字不方便,还有很多话没说出来,向贺仲雄老师致敬。