一种用于大数据的改进的ItemBased推荐算法∗

李 洋 黄树成

（江苏科技大学计算机学院 镇江 212003）

1 引言

随着信息化时代的发展，人们生活与工作中所产生、接收的信息量越来越庞大，对信息的处理和过滤就显得尤为重要。信息的过滤可以通过推荐算法来实现。好的推荐算法对整个系统的推荐准确度以及系统性能提升有很大的帮助。近年来，国内外涌现了不少高效的推荐算法，有内容关联算法、K-means聚类算法等［1］。随着大数据时代来临，推荐系统中的数据量和需要推荐的商品数量呈指数倍增长，使得大量数据的处理速度过慢，因此推荐算法领域中产生了分布式推荐算法这一研究方向。

在信息泛滥的网络世界中，只有拥有对大数据的处理能力，才能快速高效地对海量数据进行过滤、筛选，并在极短的时间内对用户的需求做出响应。在本文中，将会介绍传统协同过滤推荐算法（Collaborative filtering recommendation），并对User⁃Based算法和ItemBased算法分别加以介绍，对两种算法的优缺点进行分析，并修改原有的ItemBased算法来提升算法的性能、优化其短板［2］。

2 协同过滤算法

协同过滤推荐算法的原理是统计与目标用户有着相同兴趣的用户，或者有同样的经验的用户群体，归纳该用户群体感兴趣的信息，将这些信息推荐给目标用户［3］。个人用户能够通过反馈一定的信息（如评价）能够为其他用户的推荐提供一定的帮助。协同过滤算法能够帮助目标用户发现他们潜在的兴趣或者可能喜欢的物品，并且这种推荐算法推荐的质量都比较高。

协同过滤算法分为以用户为基础（UserBased）的协同过滤和以项目为基础（ItemBased）的协同过滤两大类。

以用户为基础的协同过滤算法，通过使用相似统计的方法，获取到具有相似兴趣的相邻用户进行推荐，因此该算法又称为基于邻居的协同过滤算法（Neighbor-based Collaborative Filtering）。

以项目为基础的协同过滤算法，通过统计用户本来喜好的、评分高的项目，再找到与之相似的项目，通过计算项目之间的相似性，达到来代替用户之间的相似性。该算法认为通过这种方法找到的项目更能够引起用户的兴趣。同时，以用户为基础的协同过滤算法在用户数量增加的时候，算法的计算时间会变得更长，而已项目为基础的协同过滤算法刚好能够解决这一问题。在本文中，也正是需要对这一算法进行改进。

该方法需要以下几个步骤。

1）收集用户信息

这里的用户信息主要指的是用户对于不同项目的兴趣信息，比如说有许多网站会让用户在使用过后进行评价，根据用户的评价好坏以及评价等级来判断用户的喜好程度［4］。除此之外，可以根据用户在网上的行为进行收集信息，系统根据用户的行为进行喜好程度评价，比如用户点赞、收藏、分享等行为，或者在次使用等行为，都能够让系统进行自动评价，不需要用户去主动地进行评价操作或者输入相关的评价数据。由于在电子商务网站有许多用户的商品购买及使用操作记录，这种算法在电子商务网站上有很大的优势［5］。

2）针对物品的最近邻搜索

将待测物品和已评价的物品的相似度作为权重，加权已评价物品的分数，就能够得到待预测物品的预测值。比如要同时对A和B两个物品进行计算，就要先找到同时对A和B进行评价过的用户，用这些用户的组合进行计算。目前较为常见的相似度算法有皮尔森相关系数公式、余弦相似度公式以及修正的余弦相似度公式等。

设现有两件物品a和b，用户u，物品a和物品b都评价过的用户集合为Uab，用户u对物品a和物品b的评价分别为rua和rub，物品a和物品b的评分期望值分别为`rˉa和`rˉb，则根据皮尔森相关系数公式可得，物品a和b之间的相似度SIM（a，b）的值如式（1）所示：

3）产生推荐结果

根据用户已评价的物品和待测物品间的相似度，计算出适合推荐的物品作为推荐结果，进而推送给对应的用户［6］。与UserBased推荐算法相比，ItemBased协同过滤推荐算法在进行推荐计算是不需要使用目标用户的历史数据，因此推荐的精准度不会受到冷启动的影响。一般情况下不同的物品之间的相似性非常稳定，受到用户数量变化的影响很小，因此许多关于推荐计算的步骤可以离线完成［9］，不会影响在线用户的体验，效率比UserBased算法要高。当然，这一算法更适用于用户数量多于数量的情况。

3 基于Hadoop平台的ItemBased推荐算法

与其他推荐算法相比，传统的协同过滤推荐算法有自己的优势，但是仍然还存在些许不足之处［10］。主要表现在以下几个方面。

1）冷启动推荐精准度不够

一般的推荐系统在进行推荐的时候需要使用大量用户的历史评价数据，尤其是传统的User⁃Based推荐算法，对数据的需求尤为明显。在本文中使用的ItemBased推荐算法对用户的历史评价记录依赖程度并不高，受到冷启动问题的影响也不大。

2）稀疏数据推荐可靠性低

在协同过滤推荐系统中，用户评价的数据越多，最终根据算法得出的推荐结果越可靠，但是当用户的评价数量很少的时候，或者两个项目之间共同评价的用户的数量很少甚至没有的时候，通过皮尔森相关系数公式计算出的推荐结果可靠性就会大幅下降。很明显，数据的稀疏性［7］对于推荐的可靠性有非常大的影响。因此在原公式修改为式（2）：

其中λ是对当前推荐结果的可靠性的度量，它的值为原始评价矩阵中项目间评分用户交集个数与项目间评分用户交集大小阈值的商，取值范围为（0，1］。当用户评价的交集越大，推荐的准确度越高，λ值也就越大。

3）可扩展性问题

随着系统的不断使用，产生的数据量会不断增多，处理数据的时间也会相应地变长。这时，算法的可扩展性就显得尤为重要［8］。近年来，越来越多的推荐系统中都遇到了这一问题，推荐算法的可扩展性也受到了越来越多人的关注［11］。为了解决这一问题，本文中使用了Hadoop集群实现对数据的分布式计算和存储。

Hadoop是一个开源的分布式计算框架，它提供了分布式文件系统HDFS（Hadoop Distributed File System）和MapReduce分布式计算的软件架构。MapReduce框架的计算过程分为Map和Re⁃duce两个阶段。在MapReduce作业中，输入的数据集被且分为若干独立的数据块，现有Map任务并行处理，对Map的输出数据排序后，再作为输入数据交由Reduce任务处理，最终输出计算结果。每个阶段的输入输出数据格式是以形式呈现的键值对。开发者只需要编写Map和Reduce阶段的映射函数即可，任务装载、调度和节点间的通信由Hadoop自动完成。该集群的工作流程如图1所示。

图1 算法工作流程图

4 实验结果分析

4.1 实验平台及数据说明

根据上述研究，利用7台计算机作为硬件，其中有1个Master节点和6个Salave节点。计算机统一搭载Ubuntu 15.04，Hadoop版本为3.1.2，JDK版本为1.8.0_181。

本文中的实验选取了MovieLens中的电影评价数据集，并分别下载了大小为100KB、1MB、10MB的数据集进行实验，数据集的详细信息如下：1）100KB：包括943个用户对1628部电影的100000条评分记录；2）1MB：包括6040个用户对3900部电影的1000209条评分记录；3）10MB：包括71567个用户对10681部电影的1000054条评分记录，评分范围为1～5，每个用户至少对20部电影进行过评价。

4.2 实验结果评估指标

本文中的实验结果评估指标主要有两项：加速比和平均绝对偏差MAE。

加速比就是指在相同的系统环境下使用同样的数据集对目标商品进行选择推荐，单机运行串行算法与集群运行并行算法所需时间之比。设程序的串行时间为T1，在N个节点上的并行时间为TN，则加速比的公式如式（3）所示。

平均绝对偏差MAE在本文中用来衡量推荐准确度。其基本思想是通过计算预测值和真实值之间的平均绝对偏差来衡量算法的最终运行结果和真实值的偏差大小。MAE的值越小，就代表推荐值和真实值之间的误差就越小，推荐结果也就越准确。设Pi为项目的预测评分值，Ri为项目的真实评分值，N为实验中的项目个数，则MAE值的公式见式（4）。

4.3 结果分析

本文选取平均绝对误差（MAE）作为算法推荐质量的衡量指标。MAE值越小，意味着推荐结果的准确度越高。从100KB数据集中，分别选取用户数量为50、200、400、800和943作为5组实验数据。实验结果见表1。

表1 数据集详细数据

在5组实验数据下将本文提出的算法分别放在非分布式环境和分布式环境下进行推荐，计算MAE值，最终结果如图2所示。

图中，纵轴为MAE值，横轴为5组实验数据的编号，根据图中的折线图可以看出，本文提出的基于Hadoop平台的ItemBased推荐算法的MAE值要低于另外两种算法，并且三种算法最终的MAE值都随着实验数据量的增大而减小，推荐精度也越高。两种ItemBased算法在第一组数据中存在着一定的数据稀疏性的问题，尤其是分布式ItemBased算法，其第一组数据中的稀疏性问题颇为严重［12］。而本文的算法在第一组数据中克服了数据稀疏性的问题，MAE值远低于另外两种算法。这说明本文提出的算法能够很好地解决数据稀疏性问题。

另外，本文使用加速比来比较Hadoop集群对于多种不同规模数据的执行效率。由上文可知加速比S=T1/Tn，T1为单个节点的运算时间，Tn为n个节点的运算时间。在实验过程中分别启动1～7台运算节点，分别根据运行时间绘制曲线图如图3。

图3 数据集处理加速比变化

该图显示三个不同大小的数据集在Hadoop集群上进行算法处理的加速比变化。这表明，针对同一数据集，增加节点数量可以提高算法效率。这种效率的提升在节点数量少的时候还不明显，当节点数量多之后，效率的提升效果就会非常明显。因此基于Hadoop集群的ItemBased推荐算法在大数据规模下拥有良好的可扩展性。

5 结语

传统的协同过滤推荐算法中存在着数据稀疏性和可扩展性两个问题［13］，本文针对这两个问题进行了深入的研究，并通过实验验证了自己的优化方案。本文将ItemBased推荐算法稍作改进，增加了推荐结果可靠性的权值，并根据Hadoop集群的分布式计算特点将算法移植到Hadoop集群进行Ma⁃pReduce化处理。通过实验证明，改算法能够显著改善推荐算法的数据稀疏性和可扩展性，从而提高大数据环境下的数据处理能力。