ResysChina翻译了IEEE Internet Computing近期发表的文章Two Decades of Recommender Systems at Amazon.com,该文讲述Amazon推荐系统近20年的发展情况,作者是著名的Item CF算法发明者。下午我寻根溯源翻看了相关论文,特以此作总结。

1.概述

        现在的主流电商网站均有其推荐系统,Netflix就曾透露其80%的用户流量来自推荐系统。一个好的推荐系统能准确识别"用户想要什么"并给出精准推荐,从而极大地减少用户检索开销,优质的推荐能显著提高商品交易率。Amazon在早期便使用了推荐系统,以下当时(2003年,目前似乎仍是)的几大主流推荐算法:

        Amazon随后推出了Item-item CF算法,其强大的效果至今仍被国内外各大网站使用,本文试图从推荐系统的基本思想开始,逐步探寻Item-item CF的亮点,同时一窥Amazon在推荐系统方面的发展历程。

2.传统推荐算法

        此处我将ItemCF之前的主流推荐算法称之为"传统算法",下文将对这些算法的思想做扼要介绍。

2.1 从基于内容的推荐开始

        基于内容的推荐应该是一种最简单推荐思想:为用户喜欢的内容分类,并向用户推荐新的同类或相近的内容。例如:虾米用户X喜欢的音乐人是张玮玮(民谣)、万能青年旅店(摇滚)和李志(摇滚/民谣),那么基于内容我们可以给他推荐草东没有派对(摇滚)。

        对每个用户,该算法的推荐只与用户本身和内容本身的特性有关,用户之间无交集。这对内容本身的分类准确性有很高的要求,例如李志被错误分类将导致许多用户的推荐效果变差。同时这种"相似推荐"单调乏味缺乏新意,在商品推荐中很容易让用户感到疲劳:试想用户购买某品牌的钢笔后,推荐列表全是其他品牌的钢笔。

2.2 传统协同过滤算法

        与基于内容算法不同的是,协同过滤(以下简称CF)算法并不事先给商品分类。它充分考虑了海量用户行为之间的相似性,其基本思想为:购买商品重合度较高的用户A和B,也有可能购买对方订单中的非重合商品,随着用户量的增长,重合度高的用户越来越多,这种预估越合理。

        在CF算法中很关键的一点是:到底以谁为基准建模。基于用户(User-Based)与基于商品(Item-Based)这两种思路分别产生了传统CF算法和大名鼎鼎的Item-item CF算法。在此先介绍前一种。

        假设现有$m$个用户,$n$件商品。传统CF的User-Based:其特点是寻找"相似用户"。对每个用户$c$,有$1*n$ 矩阵代表该用户对每件商品的喜爱程度,Amazon提供的打分准则是:购买和正面评价该商品则得分为正,负面评价则得分为负,其余都是0分。如此便得到一个$m*n$维矩阵,表征这$m$个用户对$n$个商品的评分。对两个用户$u_1$和$u_2$,我们使用余弦相似度来计算他们之间的相关性: $$u_1 = [0, 0, p_3, 0, ...p_n]$$

$$u_2 = [p_1, 0, p_3, 0, ...0]$$

$$similarity(\vec u_1, \vec u_2)=cos(\vec u_1, \vec u_2) = \frac {\vec u_1 \bullet \vec u_2}{\rVert{\vec u_1}\rVert \bullet \rVert{\vec u_2}\rVert}$$

        其中$p_i$是该用户对商品$i$的评价。

        如何给用户做推荐呢?一种常见的思路是:对每个用户$c$,找出与其相似度最高的$topN$用户,将这些用户买过的所有物品作为推荐候选集,商品的Rank以共同购买人数降序排列(当然此时热门商品占优势)。

时间复杂度

        在传统CF算法中,计算用户间的相似度是其最核心且最耗时的过程。对有$m$个用户,$n$件商品的数据集,计算某个用户$c$的相似用户时间复杂度最坏为$O(mn)$:该用户要与$m$(实际上是$m-1$)个用户比较,每个用户有$n$个维度。而事实上,矩阵的稀疏性是的其实际性能接近$O(m+n)$(对用户$i$,可以用链表将其购买过的商品连接起来,绝大部分用户购买的商品数量极少)。尽管如此,对1000万级别的用户或100万级别的商品,算法面临性能问题。

        考虑减少总用户数量$m$:例如对用户随机采样或是丢弃购买商品少的用户,然而这降低了真实用户间的相似度。另一种思路是减少商品总量$n$:常用的方式是降维,例如把2件商品"约翰克里斯朵夫(上)"和"约翰克里斯朵夫(下)"归为1件商品"约翰克里斯朵夫",这个过程一般使用聚类PCA来完成。但显而易见的是,商品维度的削减限制了精准推荐。

2.3 聚类模型

        聚类是机器学习中很重要的一部分,本文对此不做展开仅介绍其在推荐系统中的应用。我们现在的目标是找到与用户$c$最相似的一批用户,那么聚类推荐的思路是:将全体用户集合$s$分为$n$簇${s_0,s_1,s_2,...s_n}$,分别计算$c$与这n簇的相似度,将值最大的那簇作为$c$的"最相似簇",并以该簇内用户购买的商品作为推荐候选集。其离线计算过程主要用于将用户集合聚类为$n$簇,线上仅需将用户$c$分别与这$n$个矩阵的相乘,选取最大的那簇中的用户作为推荐候选集合。

        聚类模型速度快,可伸缩性(指对数据集规模的敏感性)强,但很显然其推荐质量不会太高————它给用户匹配一整簇用户,将该簇内的每个用户作为$c$的相似用户,而事实上它们并不都是$c$的相似用户。一个改进是将簇划分得更精细,但这么一来其线上计算耗时增加,其开销接近传统CF。

2.4 基于搜索的方法

        基于搜索的方法将推荐问题视作对相关商品的检索————针对用户购买和评分过的商品,该算法试图以对同一发行商、或同一导演(电影推荐)或类似keywords的检索结果作为推荐候选集。例如:用户购买了教父DVD合集,系统将考虑为他推荐犯罪主题(主题检索)、主演为Marlon Brando(主演检索)的其他电影。

        当用户购买数据极少时,基于搜索的推荐效果还算不错,但对拥有上千条商品购买记录的用户,为它们逐一检索并纳入推荐候选集是不现实的。实际应用中的所有情况,效果都很差:推荐结果要么太过宽泛(例如推荐最受欢迎的DVD),要么过于狭窄(只推荐某个作家的书籍)。推荐系统应该帮助用户发现和探索一些新的、相关且有趣的东西,以上两种均违背了该准则。

3. Item-to-Item CF算法

3.1 它是如何工作的

        与上文中传统CF计算相似用户不同,Item-to-Item CF为用户购买和评价过的每件商品寻找其相似商品,然后将这些商品放进推荐列表。

此处对"相似商品"的定义:对商品$i$,如果购买过该商品的用户有异乎寻常的可能性购买另一件商品$j$,我们称$j$是$i$的相似商品。

ItemCF的基本算法是:

        假设现有$m$个用户,$n$件商品。Item CF的**Item-Based:**其特点是寻找"相似商品"。对每件商品$i$,用$1*m$ 矩阵代表该商品被这$m$位用户的喜爱程度,用户购买和正面评价该商品则得分为正,负面评价则得分为负,其余都是0分。然后同上使用余弦相似度计算任意两件商品间的相似度。如此构建一个item-to-item(商品-商品)矩阵,矩阵每个元素是对应行列的两件商品的相似度

        考虑一个问题:并不是所有的商品都有共同买家,而两件无共同买家商品的余弦值必定是0,此时无计算相似度的必要。例如,有3件商品$i_1, i_2, i_3$, 4个用户$c_1, c_2, c_3, c_4$,按"购买过的打1分,好评0.5分,差评-0.5分,未购买过得0分"准则: $$i_1 = [0, 0, 1, -0.5]$$

$$i_2 = [0, 0.5, 1, 0]$$

$$i_3 = [0.5, 0, 0, 0]$$

        很明显商品$i_3$与前两个商品均无共同买家,此处的计算显得浪费。Item CF采用如下算法解决此问题,这是Amazon的ItemCF对传统CF计算的第二个处改进

1
2
3
4
5
6
For each item in product catalog, I1
For each customer C who purchased I1
For each item I2 purchased by customer C
Record that a customer purchased I1 and I2
For each item I2
Compute the similarity between I1 and I2

        算法改进之处在于:计算商品$i$与全部商品的相似度时,并不遍历这$n$件商品,而只计算商品$i$与购买过$i$的用户集合所购买的全部商品的相似度。此离线计算极其耗时,最坏$O(n^2*m)$,而实际中由于数据的稀疏性,接近$O(n*m)$

3.2 ItemCF vs 传统算法:可扩展性对比

        Amazon有超过2900万用户(2003年)和上百万条商品,对于大数据集,一个可伸缩推荐系统必须将其最耗时的计算放在离线环节。对比之下目前的主流算法存在如下问题;

  • 传统CF几乎不做离线计算。在大数据集下该算法不适用,除非它降维/采样。
  • 聚类算法很适合离线,但其相关性很差,增加片段能提高但这将使得线上user-segment(用户-簇)间的匹配开销增大(要比较的簇增多)。
  • 基于搜索的需要离线构建索引,但推荐结果不够有趣,对购物丰富的用户的推荐效果也很差。

        item-to-item CF可扩展性强的关键在于它开销很大的构建相似item过程是离线的。而它的线上开销呢?对用户购买或打分的商品$i$,查找其相似商品与总的商品数$n$、用户数$m$无关,而仅与购买$i$的用户所购商品条数有关,因此当数据量很大时其速度也很快。与传统CF不同,该算法在有限数据中的效果也很棒。

4. Item CF之后:Amazon推荐算法的改进及展望

        Amazon自2003年推出Item CF算法以来,其业务范围从书籍不断扩展到衣着服饰、家庭用品等方面面面,业务的复杂化促进该算法更新、改进。

4.1 算法改进

从$cosin$到共现矩阵

        Amazon对商品间的“相关性”计算方式从原来的余弦相似度改为基于共现思想的统计,下面将简要介绍该算法的思想。

        假设现有$m$个用户,$n$件商品。基于共现统计:和原来相似,对每件商品$i$,用$1*m$ 矩阵代表该商品被这$m$位用户的喜爱程度,用户购买和正面评价该商品则得分为正,负面评价则得分为负,其余都是0分。接下来构建一个$n*n$的零矩阵$I$,对行列上的商品$i$, $j$,如果其存在共同购买或打分的用户,则$I(i,j)$的值加1(差评减1)。如此遍历全部商品按共同出现的次数再对商品本身自身热度折扣便得到了这两件商品的相关程度。例如,对4件商品$i_1, i_2, i_3, i_4$,被用户购买的记为1否则记为0,它们的购买矩阵如下: $$i_1 = [1, 0, 1, 0]$$

$$i_2 = [1, 1, 1, 0]$$

$$i_3 = [1, 0, 0, 1]$$

$$i_4 = [1, 0, 1, 0]$$

        注意到以上购买矩阵中,位于第1列的用户(我们称之为$c_0$)是一个“剁手狂魔”,他买下全部4件商品,因此这4件商品两两共现次数均加1,以此类推我们得到如下$4*4$的商品矩阵: $$1 , 2 , 1 , 2$$ $$2 , 2 , 1 , 2$$ $$1 , 1 , 1 , 1$$ $$2 , 2 , 1 , 1$$

        后续计算当前商品$x$的相似商品时,取其共现次数与商品热度比值最高的$topN$商品就可以。

对共现统计的思考

        注意到这样一个事实:同时购买了商品$x$的用户里,必定存在随机购买了商品$y$的用户。我们想知道同时购买了$x$和$y$的用户中,哪些用户是买完$x$后“意愿明确地”购买了$y$,而不是出于偶然。

        一个自然的统计方法是:我们假设同时购买了$x$和$y$的用户数为$N_{xy}$,而因随机产生同时购买这两件商品的用户期望数为$E_{xy}$,则: $$真实共现次数=N_{xy}-E_{xy}$$ 其中$N_{xy}$直接从式(1)的共现矩阵中读出即可,下面看如何计算$E_{xy}$。即假设全部用户数为$M$,购买过$y$的用户数为$m_y$,购买过$x$的用户数为$m_x$,有:

$$P(y)=\frac {m_y}{M}$$

其中$P(y)$代表商品$y$被买到的概率,遂有:

$$E_{xy} = m_x * P(y)$$

        而实际情况中我们发现,对大多数任意两个商品$x$和$y$,购买过$x$的用户比平均值更有可能购买$y$。Amazon认为购买过1000个商品的用户被“选中”用于计算共现矩阵的频率是购买过20个商品用户的50倍。考虑上文中的“剁手狂魔”用户$c_0$,他的出现几乎所有商品的共现次数均增加1。

        改进的方法是:假设商品$x$和商品$y$相互独立,对购买过商品$x$的用户$c$,设其除$x$外还购买了$|c|$件其他商品,视$c$有$|c|$次独立购买商品$y$的机会,每次概率为$P(y)$,则: 用户$c$购买$y$的概率是:

$$1-(1-P(y))^{|c|}$$

此时对购买过$x$的用户集合$C_x$,其因偶然购入$y$的期望$E_{xy}$: $$E_{xy} = \sum_{c \epsilon {C_x}}[1-(1-P(y))^{|c|}]= \sum_{c \epsilon{C_x}}[1-\sum_{k=0}^{|c|}{|c| \choose k}(-P_y)^k]$$

$$=\sum_{c \epsilon {C_x}}[1-[1+\sum_{k=1}^{\lvert c \rvert}{\lvert c \rvert \choose k}(-P_y)^k]]$$

$$=\sum_{c\epsilon{C_x}}\sum_{k=1}^{|c|}(-1)^{k+1}{|c| \choose k}{P_y}^k$$ $$=\sum_{c\epsilon{C_x}}\sum_{k=1}^{\infty}(-1)^{k+1}{|c| \choose k}{P_y}^k    (当k>|c|时,{|c| \choose k})$$

$$=\sum_{k=1}^{\infty}\sum_{c\epsilon{C_x}}(-1)^{k+1}{|c| \choose k}{P_y}^k     (Fubini's theorem,多重积分变换顺序不变性)$$ $$=\sum_{k=1}^{\infty}\alpha_k(x){P_y}^k    (其中\alpha_k(x)=\sum_{c\epsilon{C_x}}(-1)^{k+1}{|c| \choose k})$$

4.2 对未来的展望

自我发现

        商品间的相关性可以通过大量用户的购买记录自我浮现出来。例如相机与存储卡的兼容性案例:购买了某型号数码相机的用户会有很高的几率会购买某特定型号的存库卡,我们事先并不知道二者是否配套,但当数据量足够大时,基本可以确认其兼容性。(结果的自我浮现) 对于低价物品,如书籍音乐,用户可能会购买多个相似物品。但对于昂贵的如电视,用户会浏览很多但最后只购买1台,此处就体现了基于内容推荐的缺陷,而相反会购买与这台电视的配套物品,如挂墙支架。

时间的重要性

        很多商品的推荐具有时效性。例如用户在购买1本书后的5个月又购买了另一本书,那么这两个物品之间的相关性很大程度上不如两本该用户同一天购买的书。再比如,用户会在买了相机之后购买存储卡,而不是反过来,因此不应该给买了存储卡的用户推荐相机。(有些物品的购买具有序列性,推荐就应该给出下一步你想要做的东西)

冷启动

  • 商品维度的冷启动:没有用户行为数据相关计算,新上架的会有一定劣势,这被称为冷启动问题。(注意:新闻和社交媒体这些易过期的物品在冷启动方面尤其具有挑战性,通常需要融合基于内容的算法、基于行为的算法(购买、浏览、打分))
  • 用户维度的冷启动:在对用户兴趣缺乏足够了解的情况下如何给出推荐?事实上,冷启动问题不仅是技术问题,也是个产品问题,可以考虑用户接受程度让其选择一些喜好等等,好的产品引导和设计可以帮助技术更好更快的解决冷启动问题

对购买的深入挖掘

  • 购买模式:用户年龄增长导致的,例如四年前购买了拨浪鼓,四年后应该推荐遥控赛车而不是奶瓶。有些商品通常只会买一次例如书籍,有些商品可预期会被重复购买例如牙膏。事实上此类问题是目前推荐领域一个让人头疼的问题,例如大家经常吐槽的某些电商网站在你买了电脑之后立即再推荐电脑,都是问题尚未完全解决的代表。其复杂度过高,目前暂无好的解决方案。
  • 购买内容挖掘:推荐的质量不仅取决于购买的时间,还取决于对用户购买中暴露出的兴趣的挖掘,我们能从一本书的购买中发现哪些?拿我举个例子,最近买了一本<夜观星空>,亚马逊就已经很明智地给我推荐天文望远镜。再比如,用户的一次订书机/袜子的订单中包含了哪些信息?通常来说推荐胶带/更多内衣或许是有用的,但长期如此会导致推荐无聊,我们需要自动识别哪些推荐是有用推荐。

多样性与意图的平衡

        有时相比一个范围很窄的推荐列表,给出一些更多样的相关物品会更好。例如,给一个重度阅读爱好者推荐更多的书可能会带动更多的销量,但是从长期来看,让用户发现他们之前从未考虑过的产品线中的新商品可能是更有用的。 意图的明确性是多样性中的一个重要因素:当用户很明显是在寻找某个具体商品时,推荐系统应该快速收窄,而用户意图不明确时,推荐应具有更多探索性和新奇感。要找的平衡点,不仅需要实验,更需要长期优化。

        以上是Amazon认为推荐系统未来有待优化的方向。

5. 参考文献

林戈 | myfancoo@gmail.com