Tag Archives: 推荐系统

赞一下豆瓣bubbler

  赞一下豆瓣新推出的bubbler,这才是好产品。据说是实习生做的,牛。这么多年过去,我依然是无可救药的重度豆瓣粉。

  最近特忙,没怎么听豆瓣FM。今晚一听效果特好:它推荐给我的都喜欢,同时这些曲目大都是最近新发行的专辑,我都没听过。豆瓣的数据挖掘算法和推荐系统越来越成熟精致。

  记得刚开始用豆瓣FM的时候,一跳出梁静茹和孙燕姿的歌,我就知道是因为某两个家伙在我好友名单里,所以算法推荐了这些歌。

  前一阵还有个帖子被大量转发:一个单身女孩29岁生日那天,在微博上哭诉:“豆瓣的算法凭什么推荐一本《30岁前别结婚》给我!”

推荐系统业务调研

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

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

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

数据挖掘和哈姆雷特

  关于推荐系统和数据挖掘想到点好玩的:电子书里的小说情节可以个性化。例如根据读者特点和所处位置修改男主角失恋后去的酒吧。再例如故事结局到底是黑色幽默或者苍凉离去呢,要根据读者是宅男还是文艺女青年来定制。真正实现一千个人眼里有一千个哈姆雷特。

  好吧我承认,上面这个段子本来是另外一篇更长的文字里的点缀。最近因为工作需要,我在写一份与推荐系统有关的文档,技术和业务都会蜻蜓点水说说皮毛。其中的非涉密内容打算整理成独立一篇BLOG。忍不住先把这个小段子发布出来,也算给自己挖个坑,防止偷懒赖帐。

KDD 2012第二、三天

  继续参加KDD2012,这两天不断在会场上碰到以前计算所的老同事、阿里各子公司BI团队的同学、在阿里云认识的客户和合作伙伴。Big Data圈子好热闹。

  今天感觉最有意思的内容,包括一早上Michael I. Jordan教授的报告Divide-and-Conquer and Statistical Inference for Big Data(大数据的分治和统计推断)。以及关于推荐系统和个性化的Session A3。不过很遗憾下午要回公司开一个比较重要的会。

  我们明天再见,我还是最关心Session A3

KDD2012将在北京举行

  第18届知识发现与数据挖掘ACM学术会议,也就是KDD 2012,8月12日将在北京举办。这次大会的主题是Mining the Big Data。由于阿里云是赞助商之一,所以我弄到了参会名额。

  这次的KDD cup 2012,题目使用了腾讯微博和搜索引擎的数据。负责主持的是Kaggle,数据挖掘领域著名的竞技平台,里面举行的比赛奖金颇丰。

  2004的KDD cup,题目是生物信息领域的,pFind团队的yfu大牛取得全球并列第一。

  而让KDD cup名声大震的,当数2006年的Netflix Prize,悬赏100万美元。现在国内推荐系统领域领军人物xVector,就是凭借这次大赛成为大众偶像。这是戏剧性的一次大赛,纽约时报全程报导,xVector的团队在最后20分钟痛失第一。

  我们会上见。

参加Beta技术沙龙,主题是推荐系统

  周日去奇遇花园参加Beta技术沙龙,这次主题是“推荐系统在大型网站中的应用”,是和Resys合办的(说起来俺也起了点儿牵线搭桥的作用,哈)。推荐系统果然很热门,参与的人比以前都多。

  第一个主讲人是dangdang网的技术总监王洪涛。从产品经理的角度介绍了dangdang的推荐系统。从业务需求的视点去看,实现什么算法反而不那么重要了,关键在于整体把握。网站做到什么程度需要引入哪一类的推荐系统?如何评价系统的效果?另外对用户体验的拿捏也是个重要问题,必须既给用户惊喜,又不讨人烦。

  接着讲座的是付超群,以前在新浪音乐开发推荐系统。他从技术上介绍了推荐算法和工程实现。主要涉及了关联分析、slope one和SVD三种算法,内容很足,言简意赅没废话,我个人很喜欢这个报告。

  国内评价和推荐做得最好的应该是豆瓣。有人问dangdang是否考虑在书评挖掘方面深入做些事。我想,豆瓣的领先地位,除了源于技术,更重要的是来自 “第三方”的超然位置所带来的高质量评价内容,以及这些评价数据背后的深度参与人群。王洪涛回答时也说,dangdang上的书评,很多是抱怨送货和售后服务的,而豆瓣就没有这个包袱了。其实单个企业很难全面覆盖产业链条,合作共赢才是正理。

  顺便提一下,企业的技术形象很重要。dangdang站内搜索的口碑不好。结果每次圈子里交流,他们的工程师总是有点尴尬,心虚郁闷的样子,忍受周围的朋友拿各种雷人的搜索结果开涮。物质待遇以外,工程师还很需要专业上的自豪感和认同感。