生活方式 数学

“猜你喜欢”是怎么猜中你心思的?

淘宝是怎么知道你想要买什么的

ccyou 发表于  2012-11-12 15:54

(文/Joseph A. Konstan & John Riedl)如今,到网上购物的人已经习惯了收到系统为他们做出的个性化推荐。Netflix 会推荐你可能会喜欢看的视频。TiVo 会自动把节目录下来,如果你感兴趣就可以看。Pandora 会通过预测我们想要听什么歌曲从而生成个性化的音乐流。

所有这些推荐结果都来自于各式各样的推荐系统。它们依靠计算机算法运行,根据顾客的浏览、搜索、下单和喜好,为顾客选择他们可能会喜欢、有可能会购买的商品,从而为消费者服务。推荐系统的设计初衷是帮助在线零售商提高销售额,现在这是一块儿规模巨大且不断增长的业务。与此同时,推荐系统的开发也已经从上世纪 90 年代中期只有几十个人研究,发展到了今天拥有数百名研究人员,分别供职于各高校、大型在线零售商和数十家专注于这类系统的其他企业。

这些年来,推荐系统有了相当的进展。开始时它们还相对较为粗糙,往往对行为做出不准确的预测;但随着更多的和不同类型的网站用户数据变得可用,推荐系统得以将创新算法应用于这些数据之上,它们迅速得到了改善。今天,推荐系统都是些极其复杂和精专的系统,常常看起来比你自己还要了解你。同时,推荐系统正在向零售网站以外的领域拓展:大学用它们来引导学生选课,移动电话公司靠它们来预测哪些用户有可能转投另一家供应商,会议主办方也测试过用它们来分配论文给审稿专家。

我们两人从推荐系统的早期开始便一直在开发和研究它们,最初是以学术研究者的身份,参与 GroupLens 计划(GroupLens Project)。1992 年起,GroupLens 通过对美国兴趣论坛网站 Usenet 讨论区里的消息进行排序,将用户指向他们可能会感兴趣、但自己尚未发现的话题线索。几年以后,我们成立了 Net Perceptions,这是一家推荐算法公司,在互联网第一次热潮期间(1997 年 - 2000 年),一直处于业界领先地位。有鉴于此,虽然这些公司极少公开谈论他们的推荐系统是如何运作的,我们的经验使我们能够深入了解亚马逊和其他在线零售商幕后的情景。(在本文中,我们的分析是在观察和推理的基础上得出的,不包含任何内部消息)。

下面就是我们所看到的。

 

推荐算法是怎么“猜你喜欢”的?

来源:recommenderapi.com

来源:recommenderapi.com

你有没有想过自己在亚马逊眼中是什么样子?答案是:你是一个很大、很大的表格里一串很长的数字。这串数字描述了你所看过的每一样东西,你点击的每一个链接以及你在亚马逊网站上买的每一件商品;表格里的其余部分则代表了其他数百万到亚马逊购物的人。你每次登陆网站,你的数字就会发生改变;在此期间,你在网站上每动一下,这个数字就会跟着改变。这个信息又会反过来影响你在访问的每个页面上会看到什么,还有你会从亚马逊公司收到什么邮件和优惠信息。

许多年来,推荐系统的开发者试过用各种各样的方法来采集和解析所有这些数据。最近这段时间,多数人都选择使用被称为个性化协同推荐(Personalized Collaborative Recommender)的算法。这也是亚马逊、Netflix、Facebook 的好友推荐,以及一家英国流行音乐网站 Last.fm 的核心算法。说它 “个性化”,是因为这种算法会追踪用户的每一个行为(如浏览过的页面、订单记录和商品评分),以此进行推荐;它们可不是瞎猫碰上死耗子——全凭运气。说它 “协同”,则是因为这种算法会根据许多其他的顾客也购买了这些商品或者对其显示出好感,而将两样物品视为彼此关联,它不是通过分析商品特征或者关键词来进行判断的。

不同类型的个性化协同推荐系统最晚从 1992 年开始便已经出现。除了 GroupLens 计划,另一项早期的推荐系统是 MIT 的 Ringo,它会根据用户的音乐播放列表从而给用户推荐其他他们有可能会喜欢的音乐。

User-User 算法:计算用户之间的相似度

GroupLens 和 Ringo 都使用了一种简单的协同算法,被称为 “用户关联”(user-user)的算法。这种类型的算法会计算一对用户之间的 “距离”,根据的是他们对同一物品打分的相似程度。举例来说,如果吉姆和简都给《电子世界争霸战》(Tron)这部电影打了 5 分,那么他们之间的距离就是 0。如果吉姆给它的续集《创:战纪》(Tron: Legacy )这部电影打了 5 分,而简只打了 3 分,那么他们之间的距离就变大了。按照这样的计算得出来品味相对 “靠近” 的用户,我们把他们称之为共有一个 “邻集”(neighborhood)。

但是,这种用户关联的策略效果并不是很好。首先,形成有意义的邻集很难:很多用户两两之间只有很少几个共同评分,有的就完全没有;而仅有的那几个都打了分的项目呢,往往是票房大片,基本上人人都喜欢的那种。再来,由于用户之间的距离可以变得很快,算法必须当场就进行大部分的计算;而这可能会比一个在网站上这儿点点那儿戳戳的人下一个动作发出之前需要更久的时间。

Item-Item 算法:计算物品之间的关联

因此,大部分的推荐系统如今都依靠一种“物-物关联”(item-item)的算法,这种算法计算的是两本书、两部电影或者两个其他什么东西之间的距离,依据的是给它们打过分的用户的相似度。喜欢 Tom Clancy 书的人很可能会给 Clive Cussler 的作品打高分,因此 Clancy 和 Cussler 的书就共处一个邻集。一对物品之间的距离可能是根据成百上千万的用户的评分计算得出,在一段时间里往往保持相对稳定,因此推荐系统可以预先计算距离,并更快的生成推荐结果。亚马逊和 Netflix 都曾公开表示过他们使用的是物-物关联算法的变种,但对细节都绝口不提。

用户关联算法和物-物关联算法都有的一个问题,是用户评分的不一致性。当给他们机会再评一次分时,用户往往会对同一件物品给出不同的得分。品味在变、心情在变,印象也在变。MIT 在上世纪 90 年代进行的一项研究表明,在最初打分一年以后,用户的评分会发生平均 1 分(满分 7 分)的变动。研究人员们也在一直在尝试不同的方法在模型中纳入这一变量;比如说,如果用户给某个商品了打一个分,但这个评分与推荐算法所了解的关于这个人和这个商品的所有其他信息不相符,有的推荐算法就会邀请用户再次对这个商品进行评价。

降维算法:把事物特征一般化

不过,用户关联算法和物-物关联算法还存在一个比一致性更大的问题:它们太死了。就是说,它们能发现都喜欢同一样东西的人,但却忽略了爱好非常相似的潜在用户组合。比如说你喜欢莫奈的睡莲。那么,在这个法国印象派大师画的 250 幅睡莲中,你最喜欢哪一幅?在一群喜欢莫奈的人当中,完全可能每个人喜欢的睡莲都不相同,而基本的算法就有可能识别不出这些人都有着共同的爱好。

大约十年前,研究者们想出了一个办法,通过一个叫降维(Dimensionality Reduction)的过程,把事物更一般化的表现出来。这种方法在计算量上比用户关联和物-物关联算法要密集得多,因此也就没有那么快的得到采用。但随着计算机变更快更便宜,降维算法也逐步取得了一些进展。

为了弄清降维算法是怎么工作的,我们来看看你爱吃的东西,以及如何把它跟其他一百万人爱吃的东西做比较。你可以把这些信息用一个巨型矩阵表示出来,每一条竖线代表一样食物,每个人爱吃什么东西就自然形成了一行。在你的这一行上面或许会显示你给了烤牛排 5 颗星、红烧小排 4 星半、烤鸡翅 2 颗星、冻豆腐卷 1 颗星、奶酪烤蘑菇 5 颗星、盐水毛豆 4 颗星,等等。

然而,使用这个矩阵的推荐算法并不关心你给哪种食物评了多少颗星。它想要了解的是你一般而言的喜好,这样它可以将这个信息应用到更丰富多样的食物上。比如说,基于你上面给出的信息,算法可能会认为你喜欢牛肉、咸的东西和烤制菜品,不喜欢鸡肉和任何油炸的东西,不喜欢也不讨厌蔬菜,依此类推。你爱吃的食物所拥有的特点或者说维度,它的数量和符合你要求的食物的数量比起来要小得多——至多可能 50 或 100。通过查对这些维度,推荐算法可以迅速决定你是否会喜欢一种新的食物(比方说盐焗排骨),方法就是把这种食物的各项维度(咸的、牛肉做的、不是鸡肉、不是炒的、不是蔬菜、不是烤的)同你的资料进行比对。这种更为一般性的呈现使得推荐算法能准确的发现有着相似但不同喜好的用户。而且,它大幅压缩了矩阵的规模,使算法变得更加高效。

这是一个很酷的解决方案。不过,你爱吃的食物的维度该上哪儿去找呢?肯定不是去问厨师。推荐系统会使用一种称为奇异值分解的数学方法来计算维度。这种方法涉及到把最初的一个巨型矩阵分解为两个 “口味矩阵”——其中一个包含了所有的用户和 100 项口味维度,另一个则包含了所有的食物和 100 项口味维度——再加上第三个矩阵,当乘以前面两个矩阵中的任意一个时,会得到最初的那个矩阵(※此处已更改)。

不像上面例子中说的那样,计算用的维度既不是描述性的,也一点儿都不直观;它们是纯抽象的值。这并没有什么,只要这些值最终生成准确的推荐结果就行了。这种方法的主要缺点是,创建矩阵所需要的时间会随着客户和产品数量的增多而飞速增长——创建一个拥有 2.5 亿名客户和 1000 万种产品的矩阵,需要花上创建一个 25 万名客户和 1 万种产品的矩阵 10 亿倍那么多的时间。而且这一过程还需要经常重复。一旦收到新的评分,矩阵就已经过时;在像亚马逊这样的公司,每一秒钟都会收到新的评论。幸运的是,就算略微过时,矩阵仍然能以一个挺不错的水平运作。研究人员们也已经在设计新的算法,为奇异值分解提供可用的近似值并显著缩短计算时间。

 

Joseph A. Konstan 和 John Riedl 都是美国明尼苏达大学的计算机科学教授。身为 IEEE 高级会员的 Konstan 和 IEEE 会士的 Riedl 参与创建了 MovieLens 推荐系统。在接下来的文章里面,两位作者将继续介绍, 推荐算法绝对不会向你推荐的是什么

 

更正说明: 文章发布之初,倒数第二自然段有关奇异值分解的内容表述有误,现已更改,特此说明。(2012-11-13)

 
 
编译自: 《IEEE科技纵览》Deconstructing Recommender Systems
文章图片: ieee. spectrum.org

显示所有评论

全部评论(77)
  • 1楼
    2012-11-12 17:00 Dr.smile

    老子杀!!几天没更新了啊???!!!!!!

    [0] 评论
  • 2楼
    2012-11-12 17:01 Dr.smile

    我愿意为很简单,实践永远比较难啊。

    [0] 评论
  • 3楼
    2012-11-12 17:04 ALIENWARE外星人 ALIENWARE官方账号

    不要这么骄傲好吗。
    请听题:我煮泡面的时候喜欢加几个蛋?来嘛,系统,试试看。

    [0] 评论
  • 4楼
    2012-11-12 17:10 StillYu

    我在淘宝搜过东西后,打开亚马逊就向我推荐
    这是怎么回事?

    [0] 评论
  • 5楼
    2012-11-12 17:14 Dr.smile
    引用@StillYu 的话:我在淘宝搜过东西后,打开亚马逊就向我推荐
    这是怎么回事?

    你的个人信息遭到泄漏。。。或者说,这俩货之间在搞基。。。。

    [0] 评论
  • 6楼
    2012-11-12 17:14 JohnCapper李润涛
    引用@StillYu 的话:我在淘宝搜过东西后,打开亚马逊就向我推荐
    这是怎么回事?

    你的信息其实并非那么隐蔽。

    我只在亚马逊买书,但亚马逊推荐的书籍,10本里面有3本是猜中 我喜好的,所以个人觉得并非那么准确。

    [0] 评论
  • 7楼
    2012-11-12 17:27 Drazen
    引用@StillYu 的话:我在淘宝搜过东西后,打开亚马逊就向我推荐
    这是怎么回事?

    你在亚马逊上之前搜索过该物品,或者是亚马逊正好推荐给你了这个物品。

    [0] 评论
  • 8楼
    2012-11-12 17:28 hinnocence

    马克之 择日再看


    ps 强烈要求收藏功能

    [0] 评论
  • 9楼
    2012-11-12 17:42 NWGbb

    IEEE Spectrum上有好多有意思的好东西。
    那个奇异值分解应该不是乘以前两个的“任意一个”,而是三个一起乘得到原矩阵吧

    [0] 评论
  • 10楼
    2012-11-12 17:51 starsnow

    有个朋友让我帮忙收藏他的商店,后来我发现老推荐一些无聊的东西,我就想着把那个商店取消收藏了,于是推荐的东西又合我口味了。

    [0] 评论
  • 11楼
    2012-11-12 17:57 行星轰炸机
    引用@JohnCapper李润涛 的话:

    你的信息其实并非那么隐蔽。

    我只在亚马逊买书,但亚马逊推荐的书籍,10本里面有3本是猜中 我喜好的,所以个人觉得并非那么准确。

    10本里面有3本是你喜好的,这个成绩已经不错了!
    如果你恰巧动心,打开其中一个链接,拍下这本书,那么亚马逊的目的就达到了!

    [0] 评论
  • 12楼
    2012-11-12 17:58 果饭

    算法不行啊,都买过的那类东西再被推荐,烦。

    [0] 评论
  • 13楼
    2012-11-12 18:01 冰煌笑雪


    引用@ALIENWARE外星人 的话:不要这么骄傲好吗。
    请听题:我煮泡面的时候喜欢加几个蛋?来嘛,系统,试试看。

      如果在数据采集上完全理想化(即不考虑获取数据的成本和法律问题),这个还真能猜个差不多。比如先统计你去超市买泡面和鸡蛋的量以及其他各种食材的量(这个数据能或得到的前提是你付费的时候用的是银行卡,现金交易的话就没办法了,),然后结合根据你平时在菜谱网站上的行为数据判断你自己下厨的频率和常做的菜,由此可以粗略估算出你一般在吃面时消耗的鸡蛋,跟你吃的面的量一平均就能大概猜出来你平均每吃一袋泡面要消耗几个鸡蛋,而误差主要取决于你买东西时使用现金多还是信用卡多,以及你在菜谱网站上的活跃程度。
      我曾经看过一个关于个人隐私的漫画说的就是这事,漫画里说当你去超市消费买东西,如果给商家留下了实名信息(比如使用实名会员卡换取折扣、使用银行卡支付),那么保险公司就可以去超市购买你的消费记录,来了解你的饮食习惯,并进而根据你的饮食习惯健康程度来调节你购买的各种医疗、人寿保险的价格。

    [0] 评论
  • 14楼
    2012-11-12 18:50 ALIENWARE外星人 ALIENWARE官方账号
    引用@冰煌笑雪 的话:


    如果在数据采集上完全理想化(即不考虑获取数据的成本和法律问题),这个还真能猜个差不多。比如先统计你去超市买泡面和鸡蛋的量以及其他各种食材的量(这个数据能或得到的前提是你付费的时候用的是银行卡,现金交易的话就没办法了,),然后结合根据你平时在菜谱网站上的行为数据判断你自己下厨的频率和常做的菜,由此可以粗略估算出你一般在吃面时消耗的鸡蛋,跟你吃的面的量一平均就能大概猜出来你平均每吃一袋泡面要消耗几个鸡蛋,而误差主要取决于你买东西时使用现金多还是信用卡多,以及你在菜谱网站上的活跃程度。
    我曾经看过一个关于个人隐私的漫画说的就是这事,漫画里说当你去超市消费买东西,如果给商家留下了实名信息(比如使用实名会员卡换取折扣、使用银行卡支付),那么保险公司就可以去超市购买你的消费记录,来了解你的饮食习惯,并进而根据你的饮食习惯健康程度来调节你购买的各种医疗、人寿保险的价格。

    妈呀!突然觉得好赤裸。泡面加几个蛋都被人看穿了!
    明天就在地下室里养鸡,自家产蛋吃。

    [0] 评论
  • 15楼
    2012-11-12 20:09 AI油泳的鹰 勘查技术与工程专业,编程爱好者

    我知道一位信息泄露的苦主,就在果壳,要不要@ 过来?

    [0] 评论
  • 16楼
    2012-11-12 20:18 啸-46

    郁闷豆瓣的猜你喜欢鲜有我喜欢的

    [0] 评论
  • 17楼
    2012-11-12 21:04 we_cry 空间信息与数字技术专业
    引用@AI游泳的鹰 的话:我知道一位信息泄露的苦主,就在果壳,要不要@ 过来?

    。。。

    [0] 评论
  • 18楼
    2012-11-12 21:11 tox
    引用@行星轰炸机 的话:

    10本里面有3本是你喜好的,这个成绩已经不错了!
    如果你恰巧动心,打开其中一个链接,拍下这本书,那么亚马逊的目的就达到了!

    在当当买书的表示我收藏了某本书它就推荐类似的一串书单。。问题是我已经买了一本一样的。。(目前没能力买各种版本的苦逼妹子真心觉得推荐什么的好打击人)

    [0] 评论
  • 19楼
    2012-11-12 21:20 猪了个去 智能科学专业

    喜欢的东西构成了稀疏矩阵。。。
    所以把啤酒放在纸尿裤旁边这样的关系计算机分析出来了真是牛逼。。。。。。

    [0] 评论
  • 20楼
    2012-11-12 21:21 zhuzhi00

    从不理会猜你喜欢,在亚马逊买书从来都是先想好要买什么再去买的

    引用@hinnocence 的话:马克之 择日再看
    ps 强烈要求收藏功能

    http://userscripts.org/scripts/show/130896

    [0] 评论
  • 21楼
    2012-11-12 21:28 iiiiiw

    M

    [0] 评论
  • 22楼
    2012-11-12 21:46 小饼干

    降维算法,解决计算量和在线更新的问题话会是很不错的推荐计算方式吧?

    [0] 评论
  • 23楼
    2012-11-12 21:48 JohnCapper李润涛
    引用@行星轰炸机 的话:

    10本里面有3本是你喜好的,这个成绩已经不错了!
    如果你恰巧动心,打开其中一个链接,拍下这本书,那么亚马逊的目的就达到了!

    的确,我也经常拍下那些介绍正确的书。只是我希望相关推荐性上能强化多一点点。

    [0] 评论
  • 24楼
    2012-11-12 22:14 素食者
    引用@冰煌笑雪 的话:


    如果在数据采集上完全理想化(即不考虑获取数据的成本和法律问题),这个还真能猜个差不多。比如先统计你去超市买泡面和鸡蛋的量以及其他各种食材的量(这个数据能或得到的前提是你付费的时候用的是银行卡,现金交易的话就没办法了,),然后结合根据你平时在菜谱网站上的行为数据判断你自己下厨的频率和常做的菜,由此可以粗略估算出你一般在吃面时消耗的鸡蛋,跟你吃的面的量一平均就能大概猜出来你平均每吃一袋泡面要消耗几个鸡蛋,而误差主要取决于你买东西时使用现金多还是信用卡多,以及你在菜谱网站上的活跃程度。
    我曾经看过一个关于个人隐私的漫画说的就是这事,漫画里说当你去超市消费买东西,如果给商家留下了实名信息(比如使用实名会员卡换取折扣、使用银行卡支付),那么保险公司就可以去超市购买你的消费记录,来了解你的饮食习惯,并进而根据你的饮食习惯健康程度来调节你购买的各种医疗、人寿保险的价格。


    最后一段保险公司的话,估计在中国还没有这么先进,印象中的保险公司是水平不高、嘈杂纷乱的一群人,很狡猾,但是不敏捷。不知道这个印象准确不。

    [0] 评论
  • 25楼
    2012-11-12 22:18 素食者
    引用@ALIENWARE外星人 的话:

    妈呀!突然觉得好赤裸。泡面加几个蛋都被人看穿了!
    明天就在地下室里养鸡,自家产蛋吃。

    鸡饲料和相关物品的购买记录也会泄露你的秘密,还有房屋信息有关地下室的部分。最后他们通知物业你私养家禽违规……

    [1] 评论
  • 26楼
    2012-11-12 23:03 zhlong

    mark

    [0] 评论
  • 27楼
    2012-11-12 23:06 etheryang

    同用。。。。

    引用@hinnocence 的话:马克之 择日再看


    ps 强烈要求收藏功能
    [0] 评论
  • 28楼
    2012-11-12 23:16 dedede

    那种定向推广的广告是谁窃取的信息啊,比如刚在淘宝看了个手表,这几天各个网站的定向广告就全是手表了,感觉隐私被窃取了

    [0] 评论
  • 29楼
    2012-11-13 07:24 今晨

    这几天刚好需要学习这方面的东西

    [0] 评论
  • 30楼
    2012-11-13 07:47 雪之女王就是喜欢猛禽

    看完果壳的文章后我去搜索帕金森和阿兹海默症,之后现在每次打开播放器,都会推荐一堆脑病医院给我,和这篇文里提到的有关系吗

    [0] 评论

显示所有评论

你的评论

登录 发表评论

ccyou
ccyou 游戏设计师,游戏达人

作者的其他文章

更多科研事,扫码早知道

关于我们 加入果壳 媒体报道 帮助中心 果壳活动 家长监控 免责声明 联系我们 移动版 移动应用

©果壳网    京ICP证100430号    京网文[2015] 0609-239号    新出发京零字东150005号     京公网安备11010502007133号

违法和不良信息举报邮箱:jubao@guokr.com    举报电话:18612934101    网上有害信息举报专区    儿童色情信息举报专区