信息推荐系统算法概述

推荐算法是信息推荐系统设计的核心模块，其性能直接影响着信息推荐的效率与服务质量，研究人员根据信息推荐系统在不同领域应用的特点，提出了各种不同的信息推荐算法，其中有很多方法结合了数据挖掘技术的研究成果。目前，主流的推荐算法包括如下几种:基于关联规则的推荐算法(Association Rule-based Recommendation，ARBR)、基于内容的推荐算法(Content-based Recommendation，CBR)、协同过滤推荐算法(Collaborative Filtering　Recommendation，CFR)，以及混合推荐算法(Hybrid Recommendation)。其中研究和应用最广泛的是协同过滤推荐算法及其改进技术。

(1)基于关联规则的推荐算法

关联规则是目前一些电子商务网站采用的主要推荐技术之一[9][10]，用于实现交叉销售。关联规则作为数据挖掘领域中的重要技术，已在零售领域应用多年，先根据用户交易数据产生关联规则，再结合用户当前购买行为作出推荐。最典型的关联规则应用是购物车分析，即通过研究用户购物车中商品之间的关系，发现同时被频繁购买的商品，从而帮助电子商务网站在用户下订单和付款时向其推荐相关商品。基于关联规则的电子商务推荐系统如图2-2所示。

图2-2　基于关联规则的电子商务推荐系统模型

关联规则挖掘的数据集存放在用户交易数据库中，数据库中的每条记录代表一个事务。关联规则挖掘形式化定义如下:设I＝{i1，i2，…，im}是项的集合。设与任务相关的数据D是数据库事务的集合，其中每个事务T是项的集合，使得T⊆I。每一个事务有一个标适符，称作TID。设A是一个项集，事务T包含A当且仅当A⊆T。关联规则是形如A⇒B的蕴含式，其中，A⊂I，B⊂I，并且A∩B＝Φ。规则A⇒B在事务集D中成立，具有支持度s，其中s是D中事务包含A∪B的百分比，即概率P(A∪B)。规则在事务集合D中具有置信度c，如果D中包含A的事务同时也包含B的百分比是c。这是条件概率P(B｜A)。即是:

同时满足最小支持度阈值(min＿sup)和最小置信度阈值(in＿conf)的规则称为强规则。项的集合称为项集(itemset)，包含k个项的项集称为k－项集。项集的出现频率是包含项集的事务数，简称为项集的频率、支持计数或计数。项集满足最小支持度min＿sup，如果项集的出现频率大于或等于min＿sup与D中事务总数的乘积。如果项集满足最小支持度min＿sup，则称它为频繁项集(frequent itemset)。频繁k－项集的集合通常记作Lk。关联规则的挖掘是一个两步过程:

①找出所有频繁项集:根据定义，这些项集出现的频繁性至少和预定义的最小支持计数一样。这一步需要反复扫描交易数据库，是整个算法性能的瓶颈。

②由频繁项集产生强关联规则:根据定义，这些规则必须满足最小支持度和最小置信度。

基于关联规则的推荐算法可以分为离线的关联规则推荐模型建立阶段和在线的关联规则推荐模型应用阶段。离线阶段使用各种关联规则挖掘算法建立关联规则推荐模型，这一步比较费时，但可以离线周期进行；在线阶段根据建立的关联规则推荐模型和用户的购买行为向用户提供实时的推荐服务。典型的关联规则算法有Apriori、DHP、FP-tree、Tree Projection等。目前，基于关联规则的信息推荐系统有e-VZpro等。

(2)基于内容的推荐算法

基于内容的推荐系统的产生根源于信息检索与信息过滤，该类推荐系统综合采用了很多信息检索、信息过滤技术。基于内容的推荐系统具体是根据资源项目(items)之间的相似性来进行推荐的，先用机器学习等技术分析用户已经评分的项的内容，建立用户档案模型，然后从items中选择与用户档案相似的item(s)，再从中根据评分选择一定的项目推荐给用户，最后根据用户的反馈信息修正推荐。用户u对项i的评分R(u，i)是根据用户u对与项目i相似的项目i′的评分R(u，i′)来估计的，其中i′∈items。基于内容的推荐模型如图2.3所示。

图2-3　基于内容的推荐模型

通过抽取项i的特征计算出它的属性集合Content(i)，通常该集合用来决定一个项与被推荐项的适合程度。用户档案ContentBasedProfile(u)常常根据重要关键词的权重来定义，其实ContentBasedProfile(u)就是一个权重向量Wu＝{wu1，wu2，…，wuk}，wui表示关键词ki对用户u的重要程度。在基于内容的推荐系统中评分函数R(u，i)被定义为:

R(u，i)＝score[ContentBasedProfile(u)，Content(i)](2-3)

但是，基于内容的推荐技术具有一定的局限性[11]:①其所能分析的项目内容仅限于能够用一系列的特征集合来表示的信息，而无法有效处理声音、图片、艺术品和影像等多媒体信息。②用户仅仅能够接收与过去喜好类似的推荐项目，而无法找出与过去体验有所不同、同时又具有潜在意义的新颖性推荐。③无法处理品质、风格或观点。以文章为例，若两篇文章的主题相同，但其内容品质有所差别的时候，基于内容的信息推荐无法有效分辨。

(3)协同过滤推荐算法

协同过滤推荐(Collaborative Filtering Recommendation)由Goldberg等研究人员于1992年首先提出[12]，是目前信息推荐系统中最为成功的技术。协同过滤的基本思想是根据具有类似观点用户的行为对目标用户进行推荐或预测，它基于这样的假设:如果用户对一些项目的评分比较相似，则他们对其他项目的评分也会比较相似。因而，这种方法首先找出一群具有相同兴趣的用户，形成用户群，也就是某些行为或偏好上有类似特性的成员集合，通过分析成员的共同兴趣或爱好，对目标用户产生相关的推荐。

可以看出，在协同过滤推荐算法中，预测项目c对用户u的效用f(u，c)，就是根据与用户u“相似的”其他用户uj∈U对项目c的效用评分f(uj，c)获得的。例如，在推荐电影的应用中，为了向用户u推荐电影，协同过滤推荐算法将搜索用户u的“近邻”，也就是那些与用户u具有相同电影喜好的成员(如对相同的电影评分相似)。进而，只有那些近邻用户喜好程度比较高的电影推荐给用户u。目前，协同过滤推荐分为三类，即基于用户的协同过滤、基于项目的协同过滤和基于模型的协同过滤。

①基于用户的协同过滤推荐。

基于用户的协同过滤方法是最直观、便于理解而且是应用最为广泛成功的一种协同过滤技术。基于相似邻居的协同过滤推荐的基础性假设如下[13][14]:针对特定信息资源(项目)，根据用户的评价日志，如果不同用户对于不同的项目(items)具有相同或者相似的喜好度，则这些用户在其他项目上也将具有较相似的兴趣偏好。所以，基于用户的协同过滤技术需要首先从用户集中根据用户的项目评价日志进行用户之间的相似度计算，根据相似度得分的高低从用户集中选择同目标用户最相似的若干个邻居用户，然后基于这些邻居用户的兴趣喜好来为目标用户进行资源推荐。(https://www.xing528.com)

②基于项目的协同过滤推荐。

基于项目的协同过滤方法是基于不同项目之间的相似度来进行项目的推荐预测[15]。该方法首先测量目标用户的已评价项目和待评价项目之间的相似度，具体是根据其他用户的资源评价来完成目标用户的已知、未知项目间的相似度的计算，然后根据目标用户的已有项目评价和前面得到的项目之间的相似度给出对待评项目的评价预测。基于项目的协同过滤方法中比较关键的仍然是相似度计算部分，只不过这里的相似度计算不是用户之间的相似度，而是项目之间的相似度了。同基于用户的协同过滤方法比较起来，很多试验评测表明，基于项目的协同过滤的精度指标与采用的试验数据的相关性比较大，多数情况下还是基于用户的协同过滤方法的精度指标高[16]。基于用户的协同过滤方法和基于项目的协同过滤方法都属于启发式(Heuristic)的协同过滤推荐策略。

③基于项目的协同过滤推荐。

基于模型的协同过滤方法通过对用户的历史项目评价信息进行学习以构建用户模型[17]，以用户模型为基础进行项目的评价预测。基于模型的协同过滤方法广泛使用机器学习技术、概率模型，贝叶斯网络，人工神经网络等技术，训练历史数据得到一个模型，然后根据模型产生信息推荐[18][19][20]。模型相对于原始数据而言具有滞后效应，为了保证模型的有效性，必须周期性地对模型进行更新。

协同过滤推荐的优点在于该算法并不关注项目内容本身，所以对于待处理的项目的结构等没有特殊要求，项目是否具备统一的处理格式都没有关系，系统只需要获得足够的项目评价就可以可靠地进行项目评价了。另外，协同过滤主要是根据用户的相似性来推荐资源，这与基于内容的推荐算法有所不同。协同过滤比较的是用户描述文件，而不是资源与用户的描述文件。由于是根据相似用户进行信息推荐，所以有可能为用户推荐出新的感兴趣的内容，或是潜在的兴趣点。

但是，协同过滤算法的缺点也非常明显，即冷启动问题和数据稀疏问题比较突出[21][22]。冷启动主要是针对新用户和新项目而言的，新用户和新项目的评价信息都是比较少的，推荐系统无法确定新用户或新项目的“最近邻居”，基于协同过滤算法就无法对其进行推荐，协同推荐此时就具有冷启动问题。另外，在很多实际的信息推荐系统中，由于用户和项目的数量都非常巨大，相对于进行推荐预测的所需要评分，已经获得的评分数量非常有限。例如，在Amazon.com这样的大型商务系统中，用户最多不过就评分了上百万本图书中的1%～2%。这就造成“用户—项目”评分数据矩阵非常稀疏，难以找到相似用户集，进而导致推荐效果大大降低。因此，在实际应用环境下，协同过滤又会产生数据稀疏性问题。

(4)其他推荐算法

为了更好地解决信息过载所引发的一系列问题，除了传统的推荐算法外，研究者们还提出了如下几种常见推荐算法。表2-1显示它们的基本内容，U表示用户的集合；I表示所有资源项目的集合；u表示当前要预测的用户(即目标用户)；i表示当前要预测的项(即目标项目)。表2-2则对各种推荐算法的优缺点进行比较。

表2-1　各种信息推荐算法

表2-2　各种推荐算法的优缺点对比

续表

①基于人口统计的推荐(Demographic-based Recommendation)。

基于人口统计的推荐是根据个人特征对用户分类，并基于人口统计信息作出推荐。早期的Grundy是通过交互式的对话来收集个人信息，用户的反应与一个人工创建的模式库相匹配[23]。另外，还有一些系统是采用机器学习来得到一个基于人口统计信息的分类器。基于人口统计的信息推荐系统与协同过滤推荐表明上相似，但实际所使用的数据则完全不同，其优点在于不需要用户评价历史数据，但用户对私人信息的敏感性是获取人口统计信息的障碍。

②基于效用的推荐(Utility-based Recommendation)。

基于效用的推荐算法在对用户需求和候选资源集之间匹配的评估基础上，通过计算候选资源对用户的效用来作出推荐。该算法首先为用户设计使用项目的效用函数，并考虑非产品特征，如提供商的可靠性和产品的可用性等；在此基础上，该算法通过计算项目对用户所产生的效用值来产生推荐结果，因此算法实现的核心问题是为相应的目标用户创建合适的效用函数。但是，系统通过交互方式让用户指定效用评估属性及其权重值对大部分用户来说是比较繁琐的事情，因而限制了该算法的应用。

③基于知识的推荐(Knowledge-based Recommendation)。

基于知识的推荐算法在某种程度上可以看作一种推理(Inference)技术，各种方法因所用的知识不同而有明显的区别。这种推荐技术建立了目标项目满足目标用户所需要的某类知识，并能通过指定的规则来进行推理。其中用户需求的描述方法可以引入案例(Case)，形成基于规则和案例推理技术(Case-based Reasoning)的信息推荐系统。知识的获取和表达是基于知识的推荐系统所面临的重点和难点，该方法的优点则是不存在协同过滤推荐技术中的冷启动问题。

为了使各种推荐技术能够取长补短，一些推荐系统采用了混合推荐(Hybrid Recommendation)方式，将传统的协同过滤技术与其他推荐技术整合起来，以获得较好的推荐效果。最常使用的是基于内容的推荐和协同过滤推荐的组合，混合式推荐算法可以分别使用两种推荐技术产生各自的推荐结果，然后选择一种组合的思路为用户生成最后的推荐列表。选用混合式推荐的一个重要原则是通过组合各种推荐算法能够避免各自单一推荐技术的弱点，互补长短。例如系统建立的初期，可以将协同过滤技术与基于知识或效用的推荐技术相结合，能有效解决系统的冷启动问题，提高推荐系统的性能。