解构个性化推荐
初识推荐
每天访问亚马逊的时候它不仅会在首页根据你的名字问候你,同时也会在展示一些推荐你购买的东西。它给小明推荐了《射雕英雄传》(金庸)和《小李飞刀》(古龙),一番浏览之后,小明最终选择了《明朝那些事儿》(当年明月)。
现在这些个性化的推荐已经司空见惯了,Netflix推荐视频;TiVo会记录一些我们感兴趣的东西;Pandora构建了一个性化音乐流来预测我们接下来可能会听什么。
这些推荐都来自个性化推荐系统——一堆计算机程序。根据用户的浏览、搜索、购买等行为以及用户的年龄等属性,帮助用户找到他们喜欢或者需要购买的商品。目标是提升销量,推荐系统是一项规模巨大的成长性业务。与此同时,推荐系统领域的开发者数量也从90年代中期的几十个人到现在的数十万人。他们来自大学、大型的电商公司以及其它一些专注于推荐系统的公司。
推荐系统的历史
时光荏苒,推荐系统得到了长足的发展。最开始的推荐系统相当不给力,经常推荐不准确。随着网站上用户的数据可用性的提高和推荐算法上的创新,推荐系统快速成长。今天的推荐系统非常复杂,专业化程序非常高,甚至标榜“比你更懂你”。它们也不仅仅用于电商领域,大学借助它来指导学生的课程;手机厂商依赖它来预测哪些用户更有可能会转向竞争对手;大会的主办单位在为同行评审的时候使用它来分发论文。
我和我的小伙伴很早就开始学习并参与构建推荐系统,最初是以研究员的身份从事GroupLens Project。从1992年开始,GroupLens对Usenet论坛上的信息进行了分类处理,试图找出用户可能感兴趣但连他们自己都不知道的话题。几年之后,我们创建了Net Perceptions,它在第一次互联网浪潮中是推荐系统的领航者。藉由这些经验,我对亚马逊及其它一些电商网站背后的逻辑略知一二,甚至包括那些从来没有公开描述他们的推荐系统是如何工作的那些公司。(在这篇文章中,我们的分析来自于细致的观察推论,不基于其它任何秘密信息)。下面是一些我们已经知道的东西:
如果这几张ppt看不懂,没关系,下面有它们的解释
你有没有想过你在亚马逊那边是什么样的?事实并不浪漫:你不过是一张巨大的矩阵中的其中一行——一串长长的数字!这一串数字描述了所有你看过的东西,所有你点过的东西,所有你买过的东西。其余的行则代表亚马逊上其余数百万购物者。你的那一行数字在你每次访问网站的时候都会被修改,当你每做一个动作的时候,它会再次被修改。这些数据影响着你在网页上实际看到的商品以及电商给你发送的购物邮件。
协同过滤
多年以来,推荐系统的开发者尝试了很多种方式来收集和解析所有数据,那时,主要是个性化协同过滤推荐系统。这种类型的推荐系统是amazon、Netflix、Facebook的朋友推荐以及last.fm(英国一家受欢迎的音乐网站)的核心。
个性化:通过跟踪每个用户的行为——网页浏览、购买、评分等产生推荐,并不是事先准备好的一萝匡建议
协同:根据所有其它用户的购买或偏好来计算两个物品之间的相关度,而非通过分析物品所具有的特征或者关键字来计算
个性化协同过滤系统最早大概出现在1992年,当时除了GroupLens项目外,另一个比较早期的推荐系统是麻省理工的Ringo,它根据用户已有的音乐专辑推荐其它的一些用户可能会喜欢的音乐。
基于用户的协同过滤推荐系统
GroupLens和Ringo都使用简单的协同过滤算法——基于用户的协同过滤。这个算法根据用户对物品的评分来计算他们之间的相似度。例如:假如小明和小强都给快拿(一款移动app)打5分,那么他们之间的距离就是0(非常近);假如小明对快牙打5分,小强对快牙打3分,那么他们之间的距离就增大一些。用户的口味与他的“邻居”相近。
但是基于用户的方法实际上没那么好,其中一个问题就是,很多用户两两之间有共同评分的物品很少或者根本就没有,电影领域更是如此,在这种情况下就无法计算这两个用户之间的距离。另外,用户之间的距离变化很快,每次用户的点击或者购买都会导致重新计算,这样的计算量对于一个有数百万用户的网站来说是非常大的。
基于物品的协同过滤推荐系统
现在的一些推荐系统使用了基于物品的协同过滤推荐系统,根据两个物品得到的评分来计算它们的距离。例如:假如对快拿评价很高的人同时对快牙评分也很高,那么快拿和快牙就是“邻居”。根据数百万用户的评分计算出来的两个物品的距离通常不会随时间变化的很快,所以就可以提前计算好任意两个物品之间的距离,这样在给出推荐的时候就会非常快。amazon和Netflix都公开表示他们用的是基于物品的协同过滤系统。
协同过滤的缺陷
这两种方法都有一个共同的问题:不靠谱的评分。受情绪、环境的影响,用户对同一个物品的评分在不同时期并不总是相同的。麻省理工实验室曾在20世纪90年代末期做了一项调查发现,用户对个物品的评分与一年后的评分平均相差1分(总分7分),研究人员尝试了不同的方法把这个变化包含到他们的模型中。例如:当系统认为原有的评分已经过时的时候,会要求用户重新评分。
比评分不靠谱问题更严重的是:算法太死板了。它可以发现用户喜欢的同类的物品,但在非常相似的物品之间就不起作用了。例如:如果你喜欢莫奈的《睡莲》系列,在他画的250个睡莲中,你更喜欢哪一个呢?每个人可能都有自己特别喜欢的那一个,但是这两个基础算法却无能为力。
SVD(奇异值分解)
大约在十年前,研究人员发现了在这些非常相似的物品之间找出特征的方法,叫做降维。它需要的计算量远大于协同过滤,也因此被接受的比较慢。随着计算机变得更快更廉价,它也取得了很大的进展。
为了帮助理解降维是如何工作的,下面以对食物口味以及怎么跟其它人比较来举例说明。想象有一张很大的矩阵,每一行代表一个用户,每一列代表一种食物,你的那一行数据表明了你的偏好:烤红薯(5分)、炖排骨(4.5分)、炸鸡腿(2分)、凉拌花生米(1分)、盐水鸭(5分)等等。推荐系统所用的矩阵不会真的关心你对各种食物的评分。它只是把这种知识应用到各种各样的食物上,以便了解你的偏好。举例来说,根据上面的数据,系统可能会认为你喜欢炸的,肉类,那它可能会给你推荐鸭血粉丝汤或者酸菜鱼。食物所具有的属性(偏咸、油炸的等维度)可能高达上百种,通过把食物的属性与你的偏好(肉类、油炸的等维度)做比较,就可以预测你对于新食物的喜好。这样推荐系统就可以发现你对那些相似但实际上又是不同的物品的喜好。它大大压缩了矩阵,使系统更加高效。
这是一个相当给力的办法。但是怎么找到这些口味维度呢?找个大厨问问?这里我们运用一种叫做奇异值分解的数学技巧来计算出这些维度。把原始的大矩阵分成两个,一个包含所有的用户和100个口味维度,另一个包含所有的食物和100个口味维度。这两个矩阵乘上第三个矩阵就等同于原始矩阵
不同于上面的例子,这些维度即不可描述也不能直观的感觉到,它们只是数学上的抽象,你找不到一个类似于“偏咸的”维度。不过没关系,只要用这些值可以得到准确的推荐就行。它主要的缺点就是计算的复杂度随着用户数和物品数急剧攀升,一个具有1千万用户和1百万物品的矩阵比只有1万人和1千种物品的矩阵计算所需的时间可能要多出几亿倍。更要命的是,这个过程需要被频繁的执行。像amazon这样的公司,这样的计算每秒钟都在发生。幸运的是,即使这个矩阵稍微过时了一点,也能很好了工作。现在研究人员已经开发出了新的算法来逼近奇异值分解的结果,同时大大缩短了计算时间。
推荐系统背后的商业逻辑
到目前为止,你对电商公司怎么描述你,怎么尝试根据你的兴趣为你推荐商品已经有了基本的认识。推荐系统还有两个其它特征:
它不仅要计算谁跟你相似,还要计算你真正喜欢什么
它包含一些商业规则,推荐出来的商品不仅要让你感觉不错,同时也要对卖家有利
以亚马逊的艺术品商店为例,它拥有9百万印刷品和宣传画。它通过以下几种途径得到你的偏好:
你对感兴趣的艺术品的打分(满分5分)
你仔细看过哪些商品(鼠标放到图片上会放大图片)
浏览的次数
加入心愿单
实际购买了哪些商品
一次会话(session)中浏览过的所有商品
点击路径
像amazon这样的公司记录了海量的用户数据,几乎用户在他们网站上的一举一动都被记录了下来,以备日后使用。通过使用浏览器的cookie,未注册用户的数据也会被记录下来,等到他们在网站上注册之后,再与之前的数据关联起来。不仅电商拥有海量的数据,线下的零售商店如沃尔玛也拥有巨量的用户交易数据。但是电商不仅可以准确的记录你的交易行为,还可以记录你的浏览和评价。用户数据收集在全世界都非常普遍,除了欧洲(法律禁止)。
抛开法律不说,当用户知道他们的数据被不正当利用之后会非常生气。amazon在2000年9月收到了很多老用户的投诉,因为他们发现amazon给他们看的商品的价格比未注册用户要高一些。随后amazon宣称这只是一次随机价格测试,老用户看到的价格高纯属巧合。
推荐系统背后的商业逻辑是在保证用户体验的同时也要能提高销售额。从最基本的方面来说,推荐系统要避免“超市悖论”。比如,在各大超市中香蕉很受欢迎,很多人都购买,那么推荐系统应该给每一个用户推荐香蕉吗?答案当然是:不。因为推荐香蕉即不会对用户有任何帮助,也不会帮助商家提高香蕉的销量。所以一个好的推荐系统应该包含这条规则,不要推荐香蕉。
上面的例子听起来有些简单,但是在我们最开始做推荐系统的时候,系统几乎给每一个人都推荐了披头士的《White Album》专辑。从统计学上来看这样的推荐是合理的,因为用户没有在你的网站上买过,并且其它用户这个专辑的评价很高。但实际上这样的推荐却是白费力气,这个专辑这么流行,如果用户喜欢的话,那他肯定早就买过了。
当然,也有很多推荐规则很精细。当小明在Netflix上搜索动作大片的时候,实际上Netflix不会给他推荐《复仇者联盟》,因为Netflix还没拿到版权。系统可能会把《钢铁侠2》推荐给小明,因为Netflix已经有了这部电影。
另外一些商业逻辑会给用户推荐一些价格非常低的商品来吸引用户到他的网站,或者推荐库存积压的商品。我们在Net Perceptions工作期间,有一个客户就通过推荐库存积压的商品而获得了相当大的成功。
带解释的推荐
这些各种各样的商业规则会变得越来越棘手。一个只是简单的向用户推荐高利润的商品的推荐系统很难得到用户的认同。这就好像你去一家餐厅吃饭,服务员老是给你推荐一些特定的鱼,用户可能就会怀疑,这玩意儿真的好吃吗?抑或这些鱼其实快过期了,商家只是想尽快卖出去?
为了取得用户的信任,推荐系统应该让用户明白为什么给他们推荐这些东西,并且在用户不喜欢推荐出来的东西的时候,让用户可以修正他们的偏好数据。
例如当你购买的东西只是一个礼品的时候,你可以把这个数据从你在amazon的偏好库里删除,毕竟它们不是你自己的口味。你也可以找到系统给你推荐这些商品的原因。如果amazon给小明推荐了《三体》,小明可以点击商品下边的链接:“为什么给我推荐?”,然后小明看到,因为他的心愿单里有其它一些科幻书籍,所以系统才给他推荐《三体》。这些解释让用户清楚推荐的依据。
但是偏好调整和推荐解释通常并不能让推荐系统变得完美。最近amazon给小明发送很多关于iphone5的邮件,几乎每天都发。但是虽然邮件中的iphone是用户喜欢的商品,但是amazon却并不知道他已经用他老婆的帐号买过了。更悲剧的是这些邮件都是不可回复的,小明没法告诉amazon:“我已经对iphone无爱了”,所以他只能退订amazon的邮件。
那么推荐系统的成效如何呢?它肯定对电商的销售额的促进作用。Aaronson集团的分析师Jack Aaronson估计推荐系统带来了10%~30%的收益,并且他们还可以做得更好。
推荐系统的评测
现在对于我们学习推荐系统的人来说最大的挑战是如何衡量这些算法的好坏。这可不像cpu基准性能测试一样简单,因为不同的推荐系统的目的相差很大。
最简单的办法是看预测的评分和用户真实的评分相差有多大。假如小明给《乔布斯传》打1分,而推荐系统根据与他相似的用户的评分情况预测小明会打2分,那误差就是1分。通常卖家更关注系统对用户评分很高的误差,因为评分的商品才是用户真正想买的。小明肯定不会买《乔布斯传》,较低等级的评分无助于理解推荐系统是如何工作的。
另一个常用的度量方法是看推荐出来的商品有多被用户实际购买了。但实际上这种分析方法有误导性,它过分关注那些用户自己就能找到的商品,这种推荐实际上是没有意义的。
因为有这些缺点,研究人员又想出了另外一些指标,这些指标不同于准确度,是推荐系统的另外一些属性,比如惊喜度、多样性。
惊喜度关注于冷门的推荐,特别是那些对相似用户没有价值,但对小明来却很有价值的东西。如果系统的惊喜度很高,那么像前边说的《White Album》这样几乎所有人都喜欢的商品就会被Joan Armatrading的《Love and Affection》替代。这些冷门的推荐有可能满足用户的需求,如果用户真的喜欢的话,那他将会感到非常惊喜。
多样性关注推荐商品的种类数,如果小明非常喜欢it类的书,那么考虑到推荐列表的多样性,就不能只推荐《计算机程序设计艺术》(高德纳)或者《Java编程思想》(Jame Gosling)这样的纯技术类的书,适当的推荐一下《操作系统革命》(电影)、《三体》(科幻小说)、《NetHack》(游戏)也许是个不错的选择。
推荐系统的未来
对推荐系统的研究打破了各种领域,远超现有的推荐系统。一些前沿的研究员正在考虑推荐系统应该做到什么程度,比如要不要给在amazon上买的人推荐服装,而不是现在的与图书相关的商品。
抛开零售行业来看,推荐系统可以帮助人们接触新思想;尽管其中有一些不是很适合,但总的来说还是有效的,它甚至可以帮助减少社会的碎片化,它到底能不能在不干扰我们,不令我们感到厌烦的情况下做到呢?让我们拭目以待。
有一件事情是肯定的,那就是推荐系统只会变得越来越好,收集更多关于你的数据,出现在令你惊奇的地方。对你来说,如果你喜欢这篇文章的话,amazon可能会给你推荐所有与推荐系统相关的图书。
这篇文章翻译自IEEE:http://spectrum.ieee.org/computing/software/deconstructing-recommender-systems
转载于:https://my.oschina.net/enyo/blog/188576