上海教育信息化云服务研究：个性化推荐技术

2.5.1　云计算与推荐技术

目前，我们正处在数据时代，每时每刻都有海量的电子数据在产生。尤其是互联网进入Web2.0时代后，互联网从少数人创造数据，多数人获取数据的情况转变为人人都是数据的创造者和使用者。电子数码设备，如数码相机、智能手机、平板电脑等，更是让电子化数据无时无刻不在产生和分享。"数据宇宙"项目统计得出，2006年全球的数据总量为0.18ZB（1ZB＝1　024EB）。而当时预测到2011年该数据将会达到1.8ZB，也就是18亿TB。

针对如此大量的数据，如何保证这些数据被安全的存储，如何保证数据在高吞吐量下的可访问性等等问题，便可以引出如今盛行业界的云计算的概念。云计算是网格计算（Grid Computing）、分布式计算（Distributed Computing）、并行计算（Parallel Computing）、效用计算（Utility Computing）、网络存储（Network Storage Technologies）、虚拟化（Virtualization）、负载均衡（Load Balance）等传统计算机和网络技术发展融合的产物。云计算具有以下优点：将计算过程集中到云端，降低了用户终端负载，使得客户端专注于交互技术；降低了用户使用应用的学习曲线；应用的处理能力具有弹性的扩展能力，可以应对多种复杂的网络访问状态；应用具有快速部署能力，提高了应用开发的迭代频率；减少了应用的硬件资源开销，并开创了按需付费的模式。

Google公司在云计算的研究领域中发表了3篇重要的论文，分别对分布式文件存储系统GFS、分布式编程模型Map Reduce和分布式系统上结构化数据存储方案Big Table进行了阐述，对云计算提出了一套完整的解决方案。在此理论基础上，Apache基金会开发了开源软件Hadoop，对Google的云计算方案GFS、Map Reduce和Big Table分别用HDFS、MapReduce和Hbase予以实现。Hadoop现己成为流行的云计算基础架构，被各大互联网公司所应用，在互联网中承担起千万级、亿级用户在线的运行支持。推荐系统搭载在云计算平台上具有它天然的优势。首先，云中集群化的数据存储和虚拟化的存储管理为推荐系统提供了理论上没有容量限制的数据存储能力和高效的数据吞吐能力，这使得推荐系统拥有海量的能快速获取的训练数据得以提供优质的推荐结果；其次，云中集群的分布式计算能力和虚拟化的资源分配为推荐系统提供了较高的响应能力以应对大量用户的各种个性化推荐。

2.5.2　目前主流的智能推荐技术分析

主流的推荐技术按照实现算法和实现方式的不同，可以分为三种，分别是基于关联规则的推荐、基于内容过滤的推荐、基于协同过滤的推荐，也可以综合以上三种推荐方式产生新的混合型推荐算法。

1）基于关联规则的推荐

基于关联规则的推荐技术的工作原理：首先由管理员定制一系列的规则条目，然后利用制定的规则度量项目间的相互关联性，将关联密切的项目推送给用户。在进行推荐时，系统分析用户当前的兴趣爱好或访问记录，然后按照事先制定的规则向用户推荐其可能感兴趣的资源项目。例如，在上海终身学习网上（www.shlll.net）对于一个正在学习《现代生活与银行》的学习者来说，当他点播《现代生活与银行》学习资源时，系统向他推荐《金融知识入门》的课程。这是因为《金融知识入门》的课程是《现在生活与银行》的基础知识，学习者可能并未很好掌握，或者仍有兴趣深入学习，这样就形成了一个基于关联规则的推荐。

基于关联规则的个性化推荐存在两个缺点：①规则无法由系统自动生成，必须由管理员手动定制，这无法保证推荐的精确度，而且规则的制定和维护的工作量大；②规则在制定之后不能动态变化。制定后的规则只能为用户推荐与其原始兴趣相符的资源条目，无法为其推荐其它高质量的资源，更不能发现用户潜在的兴趣点。

2）基于内容过滤的推荐

内容过滤推荐技术是信息过滤中最基本的一种方法，是较早被提出的一种推荐技术。内容过滤的工作原理：采用概率统计和机器学习等技术实现过滤，首先用一个用户兴趣向量表示用户的信息需求；然后对文本集内的文本进行分词、标引、词频统计加权等，生成一个文本向量；最后计算用户向量和文本向量之间的相似度，把相似度高的资源条目发送给该用户模型的注册用户。内容过滤推荐技术适用于推荐文本类型的学习资源，不适用于推荐多媒体类型的学习资源。内容过滤推荐技术需要在分析文本资源结构的基础上，抽象出若干个代表文本特征的关键词，描述资源内容特征。对于其它形式的学习资源（动画、音频、视频等），该技术不能用几个关键词概括它们而无法做出较高精度的推荐。另外，内容过滤推荐只能根据资源向量同用户向量的匹配程度向用户推荐相关资源，无法筛选出优质的资源。

3）基于协同过滤的推荐

与前两种推荐技术不同，协同过滤推荐需要在分析资源内容、计算资源和用户的匹配度的基础上产生用户推荐，产生推荐的依据是用户对资源的评分。协同过滤推荐的工作原理：首先分析用户特性，如兴趣、职业等信息；然后利用相似性算法计算用户间的相似性，找出与目标用户相似性最高的k个用户；最后参照邻居对资源的评分预测目标用户对资源的评分，将预测评分最高的n个资源推荐给目标用户。

协同过滤推荐技术具有以下三个特点：①好的普适性。与其它个性化推荐技术不同，协同过滤推荐算法所依赖的是用户对资源的评分，和资源的内容或者形式无关。这一特点使得协同过滤推荐不仅适用于容易抽象出特征向量的文本类资源，而且对动画、视频、音频等难以准确概括出特征向量的多媒体素材具有同样的推荐效果。②良好的推荐精度。用户对资源的评分反映了用户对资源的满意程度，在绝大多数情况下代表了资源的品质，使建立在评分数据基础上的协同过滤推荐具有出色的推荐准度，其推荐结果在质量上能够得到保证。③共享好友经验。由于协同过滤推荐通过目标用户（项目）的邻居预测评分，使得相似用户间彼此共享资源使用经验。通过分享邻居的经验发现目标用户的潜在兴趣点，能拓展其学习思路和提供学习支架，使得推荐更加高效。

协同过滤概念的提出要追溯到上个世纪，在1992年由Goldberg、Oki、Nichols和Terry首次提出，首先应用在Tapestry系统中。作为协同过滤技术的第一代产品，Tapestry系统存在诸多缺陷，没有达到成熟的程度。但是随着技术的进步，协同过滤（Collaborative Filter，CF）已经成为当前研究最多、应用最广的个性化推荐技术，其核心思想是：首先，系统基于系统中的已有评分数据，计算给定用户（或项目）之间的相似性；然后根据计算得到的相似性，寻找与目标用户（或项目）的最近邻居集合；最后使用最近邻居集合中的用户（或项目）的评分情况来预测目标用户对目标项目的评分值，以此来产生对目标用户的推荐。其基本原理如图2-9所示。

图2-9　协同过滤系统推荐流程

协同过滤的两个基本算法：基于用户（User-based）的协同过滤算法和基于项目（I-tem-based）的协同过滤算法。其中，User-based协同过滤是出现最早，也是在实际生活中应用最广泛的推荐技术，它以用户-项目评分矩阵中的行（用户）为基础来计算用户之间的相似性；相反，Item-based协同过滤技术则是以用户-项目评分矩阵中的列（项目）为基础来计算项目之间的相似性。这两个算法的共同点在于二者都基于用户-项目评分矩阵来建立推荐系统模型，进而为用户提供个性化推荐服务的。

基于用户（User-based）的协同过滤理论模型：基于用户的协同过滤方法也被称为最近邻协同过滤法或KNN（K-Nearest-Neighbor，K最近邻）法，其核心思想可以分为三部分：首先，使用用户的已有评分信息来计算用户之间的相似性程度；然后，寻找与目标用户的相似性程度较高的用户加入其最近邻居集，进而利用最近邻居集中的用户评分信息来预测目标用户对未评分项目的喜好程度；最后系统根据这一预测情况来产生目标用户的推荐列表。一般来说，基于用户的协同过滤算法可以通过评分数据的表示（representation）、最近邻居集构建（neighborhood formation）、推荐生成（recommendation generation）这三个阶段来进行描述。

2.5.3　个性化推荐系统研究

1）个性化推荐技术研究现状

随着Web2.0技术的日益成熟和电子商务的发展，推荐系统逐渐成为一项重要的研究内容，得到越来越多学者的关注。ACM的数据挖掘小组SIGKDD早在1999就设立了以网页挖掘技术和推荐技术为主题的WEBKDD研讨组。同年召开的人机界面会议CHI’99也设立了特别兴趣小组，用以促进个性化推荐技术的发展。

近年来，我们国家的专家学者也越来越重视个性化推荐系统方面的研究工作，对推荐系统的发展起到了积极的促进作用。周涛等人通过将用户-项目表示成一个二部分图来建立用户-项目的关联关系，进而提出了一个基于网络结构的个性化推荐方法。

在个性化推荐系统技术研究逐渐成为学术界的一个热点的同时，也出现了许多著名的大型推荐系统实例，如Amazon.com：最大的网上书店，它记录了所有用户的商品购买和网页浏览情况，然后通过对这些记录的分析，来产生目标用户的推荐列表。(www.chuimin.cn)

图2-10为Amazon.com协同过滤推荐结果示意图。

图2-10　亚马孙网站协同过滤推荐结果示意图

EBay：当前最大的网络交易平台，它通过要求用户提供对商品的满意度评分以及对其他客户的相关评述来获得用户的反馈信息，并利用这些信息来对用户产生相应的个性化服务；MovieLens：电影推荐系统，它在为用户个性化服务之前要求用户至少提供对15部电影的评分。系统通过用户的评分情况，寻找与目标用户相似性程度较高的邻居用户，然后根据这些邻居用户的评分信息，来对目标用户产生个性化推荐；Ringo：音乐推荐系统，它可以预测目标用户对所有音乐的评分值情况，并将评分值较高的音乐推荐给用户。

2）个性化推荐系统——协同过滤系统

协同过滤系统是目前应用最为广泛的个性化推荐系统，其核心思想可以分为三部分：首先，利用用户的历史行为信息计算用户之间的相似性；然后，利用与目标用户相似性程度较高的邻居用户对其他产品的评分信息来预测目标用户对特定产品的喜好程度；最后系统根据这一喜好程度来对目标用户产生个性化推荐。图2-11为一般推荐系统的架构：

图2-11　一般推荐系统的架构

协同过滤推荐技术可以为用户找到与其原有兴趣点最为契合的资源，然而该技术产生精确推荐的前提是要有足够多的评分数据，即较高的用户——资源评分率。然而，对于大型的应用系统（电子商务网站、e-learning平台等）来说，其数据库中的资源项目的数量异常庞大。资源很多但是每个用户访问并评价的资源数目只占其中很小的一部分，这将导致用户—资源评分矩阵极为稀疏，由此产生协同过滤算法的第一个问题：数据稀疏。这种情况使得系统难以成功的产生邻居用户集，用户间的相似性计算非常耗时，产生的推荐结果也难尽人意。协同过滤推荐技术的第二个问题是“冷启动”问题。一方面，对于一个新注册的用户来说，由于系统中没有该用户的任何资源访问记录，所以系统无法为其找到邻居用户集，更无法对其进行推荐；同样的，对于一个新加入的资源，系统中也不存在对该资源的任何评分记录，因而无法被协同过滤算法所推荐。这两种“0评分”情况构成了协同过滤算法的“冷启动”问题。

在协同过滤系统中广泛存在的数据稀疏性问题，和因数据稀疏性而带来的冷启动的问题。协同过滤系统通过收集系统用户的评分（选择）信息来构建用户-项目评分矩阵R（m，n）；基于该矩阵计算各个用户之间的相似性大小，进而寻找与目标用户具有相似兴趣爱好的用户构成目标用户的最近邻居集合；然后通过该集合中的用户对目标项目的评分信息来预测目标用户对该项目的评分值；最后将评分预测值最高的前N个项目作为推荐结果返回给目标用户。由于协同过滤系统是基于用户评分数据来工作的，如果用户的评分信息不足，往往会导致推荐系统的性能下降。然而实际应用中的一些大型推荐系统，其用户和项目的数量都是非常庞大的，但是系统的用户却往往只对其中的1%～2%进行评分，这样势必造成用户-项目评分矩阵非常稀疏，从而导致了推荐系统的推荐质量难以保证。

首先，对于“数据稀疏”问题，目前流行的有两种解决方法：一种是缺省值法，也就是将用户对未评分项目的评分统一设置设为一个固定的缺省值（通过情况下取用户对项目评分的平均值，如5分制中的2.5分），这个方法虽然简单，但可以在一定程度上缓解数据稀疏问题；另一种方法是项目评分预测法，可通过计算资源条目之间的相似性，由用户对相似项目的评分来预测用户对未评分项目的评分，使得用户之间共同评分的项目比较多，从而有效地解决用户评分数据极端稀疏情况下传统相似性度量方法存在的不足。

其次，对于“冷启动”问题，我们引入内容过滤克服协同过滤推荐算法的不足。具体实现方法：对用户——资源的评分率设定一个阈值，当评分率小于阈值时即可认为处于“冷启动”状态，此时采用内容过滤推荐的方式。由于内容过滤是根据用户兴趣模型与资源向量空间模型的匹配来产生推荐，其对每个用户的操作都是独立的而不依赖其他用户对资源的评价，因此能够比较好地解决“冷启动”问题。

2.5.4　基于云计算平台的智能推荐算法研究

前面介绍了基于协同过滤算法智能推荐系统，下面讨论一种以后可能会用到的基于云计算平台的智能推荐算法，以期望对目前系统的迭代和改进提供参考的方向。智能个性化推荐系统搭载在云计算平台上具有它天然的优势。首先，云中集群化的数据存储和虚拟化的存储管理为推荐系统提供了理论上没有容量限制的数据存储能力和高效的数据吞吐能力，这使得推荐系统拥有海量的能快速获取的训练数据得以提供优质的推荐结果；其次，云中集群的分布式计算能力和虚拟化的资源分配为推荐系统提供了较高的响应能力以应对大量用户的各种个性化推荐。

1）云计算平台中Map reduce算法改进原则

在对传统的单机计算的算法进行改进之前，我们要先考虑从什么方面入手实现算法的并行化，以及如何实现算法以适应MapReduce的编程模式。设计一个并行算法需要寻找算法中的并发性元素。它包括任务的并行分解、数据的并行分解和数据流的并行分解。任务的并行分解分为两种情况：当任务间相互独立时，任务属于易并行的算法；当任务间不独立，相互依赖或通信时我们对问题递归地分治求解其子问题，寻找其可并行的部分，将不可并行的部分由一台计算机串行执行，而将其可并行的部分重新设计其并行的方法。数据的并行分解和任务的并行分解类似，分为两种情况：当问题求解的数据域离散分布时，通过并行计算每个子数据域；当问题求解的子空间需要其它子空间的数据时，将子空间的数据域再次分解交换数据。

数据流的并行分解主要是对顺序执行的数据流的并行化。顺序执行通常是一个任务的输出是下一个任务的输入，对于这种问题，我们采用流水线的思想，将顺序执行的两个任务划分成对应并行的子任务。例如任务A和任务B是顺序执行的，任务A的算法输出是任务B的算法输入。我们可以将任务A划分成n个子任务：al，a2，…，an，将任务B划分成n个子任务：bl，b2，…，bn，使得任务al的输出是任务bl的输入，以此类推。这样任务A和任务B中的n个子任务是可并行的。

在MapReduce中，我们考虑其任务分治运行机理。首先输入数据由map函数进行按键划分，将相同的键下的值交由一个reduce执行。因此一个MapReduce过程就是一个子问题划分求解合并的问题，如图2-12所示。每个map阶段就是子问题划分和求解阶段，每个reduce阶段就是子问题合并阶段。

对于MapReduce的程序设计，首先我们要考虑问题域的划分对于输入数据的划分所造成的影响。MapReduce中的子问题数据划分是通过键的重排机制来实现的，即通过map函数，相同键的值将会分配到同一个reduce来处理。因此MapReduce中对于键的良好设计能够帮助提高并行能力。通过键，我们能够将需要划分的数据分开并行处理，也可以将需要合并的数据合并求解结果。

2）云平台中Map reduce对协同过滤算法的改进

Item-Based的协同过滤算法最主要的两个步骤是根据用户-项目推荐评分矩阵计算项目的相似度和根据项目相似度计算目标用户的未评分项目的预测评分。这两个步骤是有先后顺序的串行歩骤。计算项目的相似度过程中，对于任意两个项目的相似度计算是没有耦合的可并行过程，因此我们可以使用一个MapReduce作业来实现；计算目标用户的未评分项目的预测评分过程中，对每个项目的预测评分计算也是可并行的过程。因此，我们的算法由一个MapReduce作业计算项目的相似度，得到结果后再由一个MapReduce作业计算用户未评分项目的预测评分值。这两个MapReduce作业之间是串行关系。计算项目相似度的MapReduce作业我们可以通过2个MapReduce任务来完成。第一次MapReduce按用户收集各用户对项目的评分，map函数将输入数据转换成以用户为键的键值对，reduce函数将相同用户的各项合并。第二次MapReduce将用户和各项目之间的键值对转换成项目和项目之间的键值对，从而计算项目和项目之间的相似度。map函数获得各项目两两之间同一用户的评分对比，reduce函数计算相似度。该算法和传统Item-Based的协同过滤算法相比具有相同的推荐效果，但具有在大规模集群中运行的能力，可以高效地对海量的数据集进行推荐分析。

图2-12　问题划分求解合并图