论文投稿_医学论文投稿_核心期刊,职称论文投稿发表_论文部落

　　摘要：针对协同过滤（CF）推荐技术处理大数据时的计算效率问题，分析了CF算法的并行化。并行化CF算法采用Hadoop平台的MapReduce并行编程模型，改善大数据环境下CF算法在单机运行时的计算性能。在实验部分，设计不同集群环境下的加速比实验，验证该算法在大数据环境中具有的计算性能。

　　关键词：协同过滤；计算效率；加速比；Hadoop；大数据

　　引言

　　互联网时代，网络资源纷杂，信息过载，个性化推荐成为缓解用户在网络中的信息迷茫问题的重要途径[1]。在多项目、多领域的推荐中，因不依赖用户或项目内容，具有较好通用性的协同过滤算法[2]成为较成功的推荐技术，因而其改进也受到广泛关注。然而改进的算法通常是以牺牲计算效率换取计算准确度的提升。随着大数据时代的来临[3-7]，解决计算效率的问题也迫在眉睫。由于单机模式的计算能力有限，而分布式计算具有多资源、可扩展、高效计算等优势，用分布式计算实现高效的CF算法，既能提高推荐准确度，又能保证计算效率。目前主要使用云计算平台Hadoop实现算法的并行化，如文献[8-13]等是通过将算法移植至Hadoop得到高计算性能的算法。

　　本文将协同过滤推荐算法与开源分布式平台Hadoop结合，研究协同过滤推荐算法的并行化，探索其MapReduce过程设计，比较单节点计算与多节点计算在计算效率上的差别，证明并行化后的算法在计算效率上的优势，其更能适应大数据环境。我们将并行化的CF算法简称为PCF（CFinParallel）。

　　1CF算法及Hadoop平台概述

　　1.1CF算法概述

　　协同过滤技术的思想简单易懂，利用群体的观点为个人进行推荐，比如，日常生活中我们经常会参照身边朋友的意见或行为，购买一些商品或作出某种选择。在协同过滤技术中，用户之间是有联系的，他们可以是朋友、邻居，根据趣味相投原则，邻居用户的喜好是一致或相近的，所以，对于当前用户为其推荐邻居的偏好项目。CF技术通过所有用户的偏好、评分信息，经过用户相似度的度量，找到特定用户的邻居集合，根据最近邻的兴趣信息，为其作出项目推荐。

　　协同过滤推荐算法一般步骤为：构建用户-项目评分矩阵，据此计算用户或项目相似度，进而计算预测评分、取前N个预测评分高的项目产生推荐集。以user-based算法为例，具体如下[14]。

　　⑴构建评分矩阵。如表1所示。

　　⑵以用户的相似度为计算目标，寻找邻居用户。余弦相似性、修正的余弦相似性、Pearson系数相关为三种常见的相似度计算方法。

　　其中Pearson系数相关计算两用户的相似度sim（i，j），用户i与用户j共同评分的项目集合为Iij，用户i已作出评分的均值为。

　　⑴

　　⑶生成推荐。

　　①计算预测值。

　　平均加权策略：用户i对项目c的预测评分值：

　　⑵

　　②Top-N形式的推荐集。

　　计算邻居集中的用户i对各项目的加权评分平均值，Top-N推荐集取前N个且不属于Ii（用户i评分的项目集合）的项。

　　1.2存在问题

　　1.2.1矩阵稀疏问题

　　协同过滤是目前个性化推荐应用中的主流技术，然而随着大数据时代的到来，系统内的项目不断增多，用户规模日渐壮大，用户不可能对每个或大多数项目都做出评价。当用户或项目数量增大速度远远大于用户对项目的评分速度时，就导致数据量虽然增大，CF技术所依赖的评分矩阵却越来越稀疏，激化了该技术中一直存在的数据稀疏性问题，导致邻居用户或项目的计算准确性降低，对评分的预测出现偏差，影响推荐效果。针对稀疏性问题，目前主要的改进方向是矩阵填充或降维技术。

　　1.2.2冷启动问题

　　处于信息化时代，人们与互联网的接触越来越频繁，越来越多的新用户或新项目加入进来：新用户无历史行为信息，无法寻找到邻居以获得个性化服务；新项目评分信息较少甚至没有，故无法寻找到邻居以得到推荐。这是CF技术中的冷启动问题，前者是用户冷启动，后者是项目冷启动。冷启动问题也可以理解成数据稀疏性的极端情况。针对该问题，目前主要是借鉴CBF的思想，结合用户或项目本身的属性信息完成推荐，缓解冷启动[1]。

　　1.2.3可扩展问题

　　一个好的推荐系统不仅仅预测的准确度要高，同样重要的还有实时性。系统运算速度与评分矩阵的大小紧密关联，而用户规模和项目规模决定了矩阵的规模。面对急速增长的用户量和项目量，协同过滤技术中可扩展问题的重要性日渐突出。针对该问题，目前的研究一方面是利用聚类技术，通过概率计算或设定阈值，在确保能够尽量多地找到目标用户或项目的邻居前提下，将搜索空间缩至最小，以提高计算速度，缓解CF中的可扩展问题[15]；另一方面，跳出单机的局限，采用多核计算或云计算并行化方法，相对多核方式的核数有限、高实现成本，云计算的优势凸显，越来越多的研究与应用采用该方法解决推荐领域的高准确度和低计算效率的矛盾。

　　1.3Hadoop简介

　　Hadoop起源于Apache公司的Lucene和Nutch项目[16]，是谷歌云计算理论的Java语言实现。其中并行计算模型MapReduce是Hadoop中最核心的部分，它是一种可靠、高效的并行编程模型和计算框架，借助于HDFS等分布式技术，能够处理各类PB数量级的大数据[17]，其构成部分主要有一个主控服务JobTracker，若干个从服务TaskTracker，分布式文件系统HDFS，以及客户端Client[18]。MapReduce通过分解任务、合并结果的分而治之思想，实现可分解、可并行处理大数据集上的并行计算。MapReduce的任务执行过程由Map和Reduce两阶段构成，每次Map和Reduce的输入和输出均是键值对的形式，通过对相同key键值对的若干次归类整理，调用用户自定义的Map和Reduce函数，得到最终输出结果。

　　2基于MapReduce的CF算法分析