原创文章,转载请指明出处并保留原文url地址
一、推荐引擎简介
在一家超市中,人们发现了一个特别有趣的现象:尿布与啤酒这两种风马牛不相及的商品居然摆在一起。但这一奇怪的举措居然使尿布和啤酒的稍量大幅增加了。
这可不是一个笑话,而是一直被商家所津津乐道的发生在美国沃尔玛连锁超市的真实案例。原来,美国的妇女通常在家照顾孩子,所以她们经常会嘱咐丈夫在下班回家的路上为孩子买尿布,而丈夫在买尿布的同时又会顺手购买自己爱喝的啤酒。这个发现为商家带来了大量的利润,但是如何从浩如烟海却又杂乱无章的数据中,发现啤酒和尿布销售之间的联系呢?这又给了我们什么样的启示呢?
上面的例子是推荐引擎的一个应用场景,推荐引擎及个性化推荐情况又如何?
个性化推荐是根据用户的兴趣特点和购买行为,向用户推荐用户感兴趣的信息和商品。随着商品个数和种类快速增长,顾客需要花费大量的时间才能找到自己想买的商品。这种浏览大量无关的信息和产品过程无疑会使淹没在信息过载问题中的消费者不断流失。为了解决这些问题,个性化推荐系统应运而生。
个性化推荐系统是建立在海量数据挖掘基础上的一种高级商务智能平台,以帮助电子商务网站为其顾客购物提供完全个性化的决策支持和信息服务。
如上图, 图中最上面是候选对象(推荐需要的历史事实或者数据),中间是推荐引擎(推荐行为的实现者), 下面推荐对象(推荐结果)推荐引擎根据候选对象。
一个典型的推荐过程是:推荐引擎根据候选对象(包括历史数据)通过一定的计算方法推导出推荐对象。
个性化推荐就是结合具体的对象,可能是推荐的使用对象, 或者被推荐的对象等,产生相关推荐, 一般这些推荐都需要一定的历史数据, 特别是个性化的历史数据。
二、推荐算法简单分类
在推荐系统简介中,我们给出了推荐系统的一般框架。很明显,推荐方法是整个推荐系统中最核心、最关键的部分,很大程度上决定了推荐系统性能的优劣。目前,主要的推荐方法包括:基于内容推荐、协同过滤推荐、基于关联规则推荐、基于效用推荐、基于知识推荐和组合推荐等。我们分别简要进行介绍。
(一)基于内容推荐
基于内容的推荐(Content-based Recommendation)是信息过滤技术的延续与发展,它是建立在项目的内容信息上作出推荐的,核心是项目自身的信息,而不需要依据用户对项目的评价意见。更多地需要用机器学习的方法从关于内容的特征描述的事例中得到用户的兴趣资料。在基于内容的推荐系统中,项目或对象是通过相关的特征的属性来定义,系统基于用户评价对象的特征,学习用户的兴趣,考察用户资料与待预测项目的相匹配程度。用户的资料模型取决于所用学习方法,常用的有决策树、神经网络和基于向量的表示方法等。 基于内容的用户资料是需要有用户的历史数据,用户资料模型可能随着用户的偏好改变而发生变化。
上图是基于内容的一个示意图,图中主要包括三个事物, 每个事物包括了若干自身的属性, 分别包括:几何特性, 物理特性, 化学特性,以及价值等性质。
基于内容的推荐就是让推荐引擎根据上述的相关特征(事物自身)进行学习,或者我们设定一些算法, 然后根据这些算法来产生推荐的过程。
基于内容推荐方法的优点是:l
1)不需要其它用户的数据,没有冷开始问题和稀疏问题。l
2)能为具有特殊兴趣爱好的用户进行推荐。l
3)能推荐新的或不是很流行的项目,没有新项目问题。l
4)通过列出推荐项目的内容特征,可以解释为什么推荐那些项目。l
5)已有比较好的技术,如关于分类学习方面的技术已相当成熟。
缺点是:
要求内容能容易抽取成有意义的特征,
要求特征内容有良好的结构性,
并且用户的口味必须能够用内容特征形式来表达,不能显式地得到其它用户的判断情况。
其实基于内容的推荐可以概括为:以事物自身特征为核心,采用某些算法或者模型计算不同事物之间的相似程度,或者可比较程度, 然后以特定方式呈现给用户。
例如,我们去超市购买东西, 假设我们去买水果, 你会发现水果都是集中存放,让用户进行挑选,为什么集中存放呢?因为各种水果等在某些特性等方面或者符合某些模型或者算法,因此他们集中存放后会给我们顾客带来方便。
引申理解:但用户未产生实际购买行为前, 他正在挑选相关东西,这个时候很多东西为确定,因此这个时候将相似东西放到一起会减少用户挑选东西的时间,方便了顾客进而提高相关效率。
缺点,若是我们仅仅只有这么一种推荐方法, 但用户买了很多橘子后,还会买橘子吗?也会买苹果吗?这些就不一定了, 因此这个时候就需要其他方法来确定下一步行为了。
(二)协同过滤推荐
协同过滤推荐(Collaborative Filtering Recommendation)技术是推荐系统中应用最早和最为成功的技术之一。它一般采用最近邻技术,利用用户的历史喜好信息计算用户之间的距离,然后 利用目标用户的最近邻居用户对商品评价的加权评价值来预测目标用户对特定商品的喜好程度,系统从而根据这一喜好程度来对目标用户进行推荐。协同过滤最大优 点是对推荐对象没有特殊的要求,能处理非结构化的复杂对象,如音乐、电影。
协同过滤是基于这样的假设:为一用户找到他真正感兴趣的内容的好方法是首先找到与此用户有相似兴趣的其他用户,然后将他们感兴趣的内容推荐给此用户。其基本思想非常易于理解,在日常生活中,我们往往会利用好朋友的推荐来进行一些选择。协同过滤正是把这一思想运用到电子商务推荐系统中来,基于其他用 户对某一内容的评价来向目标用户进行推荐。
基于协同过滤的推荐系统可以说是从用户的角度来进行相应推荐的,而且是自动的,即用户获得的推荐是系统从购买模式或浏览行为等隐式获得的,不需要用户努力地找到适合自己兴趣的推荐信息,如填写一些调查表格等。
同基于内容的过滤方法相比,协同过滤具有如下的优点:l
1) 能够过滤难以进行机器自动内容分析的信息,如艺术品,音乐等。l
2) 共享其他人的经验,避免了内容分析的不完全和不精确,并且能够基于一些复杂的,难以表述的概念(如信息质量、个人品味)进行过滤。l
3) 有推荐新信息的能力。可以发现内容上完全不相似的信息,用户对推荐信息的内容事先是预料不到的。这也是协同过滤和基于内容的过滤一个较大的差别,基于内容的过滤推荐很多都是用户本来就熟悉的内容,而协同过滤可以发现用户潜在的但自己尚未发现的兴趣偏好。l
4) 能够有效的使用其他相似用户的反馈信息,较少用户的反馈量,加快个性化学习的速度。
虽然协同过滤作为一种典型的推荐技术有其相当的应用,但协同过滤仍有许多的问题需要解决。
最典型的问题有稀疏问题(Sparsity)和
可扩展问题(Scalability)。
(三)基于关联规则推荐
基于关联规则的推荐(Association Rule-based Recommendation)是以关联规则为基础,把已购商品作为规则头,规则体为推荐对象。关联规则挖掘可以发现不同商品在销售过程中的相关性,在零售业中已经得到了成功的应用。管理规则就是在一个交易数据库中统计购买了商品集X的交易中有多大比例的交易同时购买了商品集Y,其直观的意义就是用户在购 买某些商品的时候有多大倾向去购买另外一些商品。比如购买牛奶的同时很多人会同时购买面包。
算法的第一步关联规则的发现最为关键且最耗时,是算法的瓶颈,但可以离线进行。其次,商品名称的同义性问题也是关联规则的一个难点。
关联规则推荐的核心是购买项目集(或者相关相集), 系统通过分析相集来产生推测,这里面仅仅关心相集,并没有关注项目产生的人或者事物, 更没有关注产生这些相集的人以及人之间的相似程度。
而协同过滤主要关注人及相关项目之间的联系, 同时考虑人的相似程度,最后根据这些相似程度进行加权处理。
(四)基于效用推荐
效用(Utility)是经济学中最常用的概念之一。一般而言,效用是指对于消费者通过消费或者享受闲暇等使自己的需求、欲望等得到的满足的一个度量。
基于效用的推荐(Utility-based Recommendation)是建立在对用户使用项目的效用情况上计算的,其核心问题是怎么样为每一个用户去创建一个效用函数,因此,用户资料模型很大 程度上是由系统所采用的效用函数决定的。基于效用推荐的好处是它能把非产品的属性,如提供商的可靠性(Vendor Reliability)和产品的可得性(Product Availability)等考虑到效用计算中。
(五)基于知识推荐
基于知识的推荐(Knowledge-based Recommendation)在某种程度是可以看成是一种推理(Inference)技术,它不是建立在用户需要和偏好基础上推荐的。基于知识的方法因 它们所用的功能知识不同而有明显区别。效用知识(Functional Knowledge)是一种关于一个项目如何满足某一特定用户的知识,因此能解释需要和推荐的关系,所以用户资料可以是任何能支持推理的知识结构,它可以 是用户已经规范化的查询,也可以是一个更详细的用户需要的表示。
(六)组合推荐
由于各种推荐方法都有优缺点,所以在实际中,组合推荐(Hybrid Recommendation)经常被采用。研究和应用最多的是内容推荐和协同过滤推荐的组合。最简单的做法就是分别用基于内容的方法和协同过滤推荐方法去产生一个推荐预测结果,然后用某方法组合其结果。尽管从理论上有很多种推荐组合方法,但在某一具体问题中并不见得都有效,组合推荐一个最重要原则就是通过组合后要能避免或弥补各自推荐技术的弱点。
在组合方式上,有研究人员提出了七种组合思路:l
1)加权(Weight):加权多种推荐技术结果。l
2)变换(Switch):根据问题背景和实际情况或要求决定变换采用不同的推荐技术。 3)混合(Mixed):同时采用多种推荐技术给出多种推荐结果为用户提供参考。l 4)特征组合(Feature combination):组合来自不同推荐数据源的特征被另一种推荐算法所采用。l
5)层叠(Cascade):先用一种推荐技术产生一种粗糙的推荐结果,第二种推荐技术在此推荐结果的基础上进一步作出更精确的推荐。l
6)特征扩充(Feature augmentation):一种技术产生附加的特征信息嵌入到另一种推荐技术的特征输入中。l
7)元级别(Meta-level):用一种推荐方法产生的模型作为另一种推荐方法的输入。
三、推荐评价
推荐系统搭建完毕之后,你最想了解的可能就是这个系统的效果如何?对于电商系统来说,推荐系统能够带来多大的转化率?对于提供音乐、电影、资讯服务的网站来说,推荐系统推荐给用户的东西有多少是用户真正喜欢的,并且使用了的?
如果一个智能系统的智能程度很弱的话,对于工业界来说,完全可以不用智能系统。假象你推荐给用户的东西效果很差的话,还不如推荐给用户一些比较hot的东西。
那么,如何来评价一个推荐系统的效果?大概有如下一些评价方法:用户满意度、覆盖率、多样性、新颖性、实时性、健壮性、商业目标等。
(一)用户满意度
用户作为推荐系统的重要参与者,其满意度是评测推荐系统的最重要指标。但是,用户满意度没有办法离线计算,只能通过用户调查或者在线实验获得。
用户调查获得用户满意度主要是通过调查问卷的形式。用户对推荐系统的满意度分为不同的层次。GroupLens曾经做过一个论文推荐系统的调查问卷,该问卷的调查问题是请问下面哪 句话最能描述你看到推荐结果后的感受?
调查问卷不是简单地询问用户对结果是否满意,而是从不同的侧面询问用户对结果的不同感受。比如,如果仅仅问用户是否满意,用户可能心里认为大体满意,但是对某个方面还有点不满,因而可能很难回答这个问题。因此在设计问卷时需要考虑到用户各方面的感受,这样用户才能针对问题给出自己准确的回答。
在线系统中,用户满意度主要通过一些对用户行为的统计得到。比如在电子商务网站中,用户如果购买了推荐的商品,就表示他们在一定程度上满意。因此,我们可以利用购买率度量用户的满意度。此外,有些网站会通过设计一些用户反馈界面收集用户满意度。比如在视频网站Hulu的推荐页面(如图1-24所示)和豆瓣网络电台(如图1-25所示)中,都有对推荐结果满意或者不满意的反馈按钮,通过统计两种按钮的单击情况就可以度量系统的用户满意度。更一般的情况下,我们可以用点击率、用户停留时间和转化率等指标度量用户的满意度。
(二)准确性
准确性是一个可以量化的指标,在学术界,评价一个推荐系统最重要的指标就是看看你预测的分数和真实的分数之间的误差有多大。一般的做法是将你拿到的 数据集分为两组,training set和 testing set,两者的比例一般是4:1(或者随便自己定,但训练集明显要多于测试集),如下图是准确性的评估的示意图
然后你可以用平均误差MAE或者误差的平方RMSE来计算推荐系统的准确性。
通过计算准确性,可以不断调试推荐系统的各种参数,比如PureSVD方法中的要保留的矩阵维数k,比如Latent Factor Model中gradient desent 算法中的下降因子等等诸多参数。
(三)覆盖率
覆盖率(coverage)描述一个推荐系统对物品长尾的发掘能力。覆盖率有不同的定义方法,最简单的定义为推荐系统能够推荐出来的物品占总物品集合的比例。假设系统的用户集合为U,推荐系统给每个用户推荐一个长度为N的物品列表R( u)。那么推荐系统的覆盖率可以通过下面的公式计算:
从上面的定义可以看到,覆盖率是一个内容提供商会关心的指标。以图书推荐为例,出版社可能会很关心他们的书有没有被推荐给用户。覆盖率为100%的推荐系统可以将每个物品都推荐给至少一个用户。此外,从上面的定义也可以看到,热门排行榜的推荐覆盖率是很低的,它只会推荐那些热门的物品,这些物品在总物品中占的比例很小。一个好的推荐系统不仅需要有比较高的用户满意度,也要有较高的覆盖率。
但是上面的定义过于粗略。覆盖率为100%的系统可以有无数的物品流行度分布。。。。。
(四)多样性
用户的兴趣是广泛的,在一个视频网站中,用户可能既喜欢看《猫和老鼠》一类的动画片,也喜欢看成龙的动作片。那么,为了满足用户广泛的兴趣,推荐列表需要能够覆盖用户不同的兴趣领域,即推荐结果需要具有多样性。多样性推荐列表的好处用一句俗话表述就是“不在一棵树上吊死”。尽管用户的兴趣在较长的时间跨度中是一样的,但具体到用户访问推荐系统的某一刻,其兴趣往往是单一的,那么如果推荐列表只能覆盖用户的一个兴趣点,而这个兴趣点不是用户这个时刻的兴趣点,推荐列表就不会让用户满意。反之,如果推荐列表比较多样,覆盖了用户绝大多数的兴趣点,那么就会增加用户找到感兴趣物品的概率。因此给用户的推荐列表也需要满足用户广泛的兴趣,即具有多样性。
多样性描述了推荐列表中物品两两之间的不相似性。因此,多样性和相似性是对应的。假设 定义了物品i和 j之间的相似度,那么用户u的推荐列表R( u)的多样性定义如下:
而推荐系统的整体多样性可以定义为所有用户推荐列表多样性的平均值:
从上面的定义可以看到,不同的物品相似度度量函数s(i,j)可以定义不同的多样性。如果用内容相似度描述物品间的相似度,我们就可以得到内容多样性函数,如果用协同过滤的相似度函数描述物品间的相似度,就可以得到协同过滤的多样性函数。
关于推荐系统多样性最好达到什么程度,可以通过一个简单的例子说明。假设用户喜欢动作片和动画片,且用户80%的时间在看动作片,20%的时间在看动画片。那么,可以提供4种不同的推荐列表:A列表中有10部动作片,没有动画片;B列表中有10部动画片,没有动作片;C列表中有8部动作片和2部动画片;D列表有5部动作片和5部动画片。在这个例子中,一般认为C列表是最好的,因为它具有一定的多样性,但又考虑到了用户的主要兴趣。A满足了用户的主要兴趣,但缺少多样性,D列表过于多样,没有考虑到用户的主要兴趣。B列表即没有考虑用户的主要兴趣,也没有多样性,因此是最差的。
(五)新颖性
新颖的推荐是指给用户推荐那些他们以前没有听说过的物品。在一个网站中实现新颖性的最简单办法是,把那些用户之前在网站中对其有过行为的物品从推荐列表中过滤掉。比如在一个视频网站中,新颖的推荐不应该给用户推荐那些他们已经看过、打过分或者浏览过的视频。但是,有些视频可能是用户在别的网站看过,或者是在电视上看过,因此仅仅过滤掉本网站中用户有过行为的物品还不能完全实现新颖性。
评测新颖度的最简单方法是利用推荐结果的平均流行度,因为越不热门的物品越可能让用户觉得新颖。因此,如果推荐结果中物品的平均热门程度较低,那么推荐结果就可能有比较高的新颖性。
但是,用推荐结果的平均流行度度量新颖性比较粗略,因为不同用户不知道的东西是不同的。因此,要准确地统计新颖性需要做用户调查。
(六)实时性
在很多网站中,因为物品(新闻、微博等)具有很强的时效性,所以需要在物品还具有时效性时就将它们推荐给用户。比如,给用户推荐昨天的新闻显然不如给用户推荐今天的新闻。因此,在这些网站中,推荐系统的实时性就显得至关重要。
推荐系统的实时性包括两个方面。首先,推荐系统需要实时地更新推荐列表来满足用户新的行为变化。比如,当一个用户购买了iPhone,如果推荐系统能够立即给他推荐相关配件,那么肯定比第二天再给用户推荐相关配件更有价值。很多推荐系统都会在离线状态每天计算一次用户推荐列表,然后于在线期间将推荐列表展示给用户。这种设计显然是无法满足实时性的。与用户行为相应的实时性,可以通过推荐列表的变化速率来评测。如果推荐列表在用户有行为后变化不大,或者没有变化,说明推荐系统的实时性不高。
实时性的第二个方面是推荐系统需要能够将新加入系统的物品推荐给用户。这主要考验了推荐系统处理物品冷启动的能力。关于如何将新加入系统的物品推荐给用户,本书将在后面的章节进行讨论,而对于新物品推荐能力,我们可以利用用户推荐列表中有多大比例的物品是当天新加的来评测。
(七)健壮性
任何一个能带来利益的算法系统都会被人攻击,这方面最典型的例子就是搜索引擎。搜索引擎的作弊和反作弊斗争异常激烈,这是因为如果能让自己的商品成为热门搜索词的第一个搜索果,会带来极大的商业利益。推荐系统目前也遇到了同样的作弊问题,而健壮性(即robust,鲁棒性)指标衡量了一个推荐系统抗击作弊的能力。
2011年的推荐系统大会专门有一个关于推荐系统健壮性的教程⑫。作者总结了很多作弊方法,其中最著名的就是行为注入攻击(profile injection attack)。众所周知,绝大部分推荐系统都是通过分析用户的行为实现推荐算法的。比如,亚马逊有一种推荐叫做“购买商品A的用户也经常购买的其他商品”。它的主要计算方法是统计购买商品A的用户购买其他商品的次数。那么,我们可以很简单地攻击这个算法,让自己的商品在这个推荐列表中获得比较高的排名,比如可以注册很多账号,用这些账号同时购买A和自己的商品。还有一种攻击主要针对评分系统,比如豆瓣的电影评分。这种攻击很简单,就是雇用一批人给自己的商品非常高的评分,而评分行为是推荐系统依赖的重要用户行为。
算法健壮性的评测主要利用模拟攻击。首先,给定一个数据集和一个算法,可以用这个算法给这个数据集中的用户生成推荐列表。然后,用常用的攻击方法向数据集中注入噪声数据,然后利用算法在注入噪声后的数据集上再次给用户生成推荐列表。最后,通过比较攻击前后推荐列表的相似度评测算法的健壮性。如果攻击后的推荐列表相对于攻击前没有发生大的变化,就说明算法比较健壮。
在实际系统中,提高系统的健壮性,除了选择健壮性高的算法,还有以下方法。
设计推荐系统时尽量使用代价比较高的用户行为。比如,如果有用户购买行为和用户浏览行为,那么主要应该使用用户购买行为,因为购买需要付费,所以攻击购买行为的代价远远大于攻击浏览行为。
在使用数据前,进行攻击检测,从而对数据进行清理。
(八)商业目标
很多时候,网站评测推荐系统更加注重网站的商业目标是否达成,而商业目标和网站的盈利模式是息息相关的。一般来说,最本质的商业目标就是平均一个用户给公司带来的盈利。不过这种指标不是很难计算,只是计算一次需要比较大的代价。因此,很多公司会根据自己的盈利模式设计不同的商业目标。
不同的网站具有不同的商业目标。比如电子商务网站的目标可能是销售额,基于展示广告盈利的网站其商业目标可能是广告展示总数,基于点击广告盈利的网站其商业目标可能是广告点击总数。因此,设计推荐系统时需要考虑最终的商业目标,而网站使用推荐系统的目的除了满足用户发现内容的需求,也需要利用推荐系统加快实现商业上的指标。
相关评价指标参考文档如下:
http://www.ituring.com.cn/article/13892