论文部分内容阅读
摘 要：针对高效的协同过滤推荐技术处理大数据时的计算效率问题，提出了并行计算的ASUCF算法。该算法采用Hadoop平台的MapReduce并行编程模型，改善大数据环境下高效的CF算法在单机运行时的计算性能问题。最后在实验部分，结合Mahout，实现ASUCF算法的并行化，设计不同数据集上的加速比实验，验证算法并行化后在大数据环境中具有较好的计算性能。
关键词：协同过滤；计算效率；加速比；Hadoop；Mahout
中图分类号：TP391 文献标识码：A
文章编号：2096-1472（2016）-06-17-04
Abstract：Aiming to solve the CF’s （Collaborative Filtering） computing efficiency problem in big data processing，the paper proposes parallel ASUCF（Average Similarity of User-Item Collaborative Filtering） algorithm.It applies the MapReduce parallel-programming model in Hadoop platform，which improves the CF’s computational efficiency in big data processing on a single PC.Combined with Mahout，the parallelization of ASUCF is achieved.The paper designs speedup experiments on different data sets.The experiment results prove that the parallel algorithm brings out better computing performance in big data processing.
Keywords：collaborative filtering；computing efficiency；speedup；Hadoop；Mahout
1 引言（Introduction）
互联网时代，网络资源纷杂，信息过载，个性化推荐成为缓解用户在网络中的信息迷茫问题的重要途径[1]。在多项目、多领域的推荐中，因不依赖用户或项目内容，具有较好通用性的协同过滤算法[2]成为较为成功的推荐技术，其改进因而也受到广泛关注。然而，改进的算法通常是以牺牲计算效率换取计算准确度的提升。随着大数据时代的来临，解决计算效率的问题也迫在眉睫。由于单机模式的计算能力有限，而分布式计算具有多资源、可扩展、高效计算等优势，所以用分布式计算实现高效的CF算法，既能提高推荐准确度，又能保证计算效率。目前主要使用云计算平台Hadoop实现算法的并行化，如文献[3—8]等是通过将算法移植至Hadoop，以得到高计算性能的算法。
本文将基于平均相似度的协同过滤推荐算法（Average Similarity of User-Item Collaborative Filtering，简称ASUCF）与开源分布式平台Hadoop结合，改写Mahout中Item-based CF分布式实现，研究ASUCF算法的并行化，探索其MapReduce过程设计，并通过在不同规模的数据集上实验，比较单节点计算与多节点计算在计算效率上的差别，证明并行化后的ASUCF算法在计算效率上的优势，更能适应大数据环境。
2 Hadoop平台及ASUCF算法并行化分析（Hadoop and analysis of ASUCF in parallel）
2.1 ASUCF算法概述
文献[9]详细描述了ASUCF算法，并通过实验证明推荐准确度的提高，在此对其简单描述，为后续的并行化分析作铺垫。ASUCF为避免矩阵预处理带来的偏差，改进的算法回归到最原始的评分矩阵，从用户行为分析、项目行为分析，引入平均相似度，将计算预测评分分解成用户角度的预测和项目角度的预测两部分，综合两部分后得到最终的用户对项目的预测评分。
用户的项目平均相似度和项目的用户平均相似度计算分别如式（1）和式（2），和分别表示用户已评分项目的集合，对项目已评分的用户集合：
综合用户、项目两方面，引入UAS、IAS，则目标用户对目标项目的预测评分如式（3）所示。
2.2 Hadoop简介
Hadoop起源于Apache公司的Lucene和Nutch项目[10]，是谷歌云计算理论的Java语言实现。2006年，实现分布式文件系统和MapReduce的部分从Lucene和Nutch中分离出来，成为新项目Hadoop[11]。对应GFS实现的HDFS、并行计算模型MapReduce是Hadoop中最核心的部分。HDFS是Hadoop中的文件管理系统，采用主从结构，一个集群中包括一个主控服务器，即目录节点NameNode，用于索引DataNode、负责系统内文件命名空间操作、数据块和DataNode之间的映射关系等；以及多个块服务器，即数据节点DataNode，用于数据物理存储，文件通常被划分成若干个数据块，储存在不同的DataNode中[12]。MapReduce是一种可靠、高效的并行编程模型和计算框架，借助于HDFS等分布式技术，能够处理各类PB数量级的大数据[13]，其构成部分主要有一个主控服务JobTracker，若干个从服务TaskTracker，分布式文件系统HDFS，以及客户端Client[14]，它们的主要功能分别是：
（1）JobTracker：将作业划分成若干个任务，分发给多个TaskTracker，管理任务的执行以及输出反馈。 （2）TaskTracker：完成若干个Map、Reduce任务，并向JobTracker实时反馈执行情况。
（3）HDFS：数据、相关信息的保存及管理。
（4）客户端Client：Map和Reduce程序的编写，作业的提交。
MapReduce通过分解任务、合并结果的分而治之思想实现可分解、可并行处理大数据集上的并行计算。MapReduce的任务执行过程由Map和Reduce两阶段构成，每次Map和Reduce的输入和输出均是键值对的形式，通过对相同key键值对的若干次归类整理，调用用户自定义的Map和Reduce函数，得到最终输出结果。
2.3 ASUCF算法分析
要实现算法的并行性，首先需要分析出算法中的可并行计算部分，以及并行计算部分与串行计算之间的关系。为方便表述，设：
通过对改进算法ASUCF的分析，将每次推荐的计算分解为：UAS、IAS、、，其中又可分解为两两用户的相似度计算和目标预测评分的计算；又可分解为目标区域内两两项目的相似度计算和目标预测评分的计算。UAS、IAS之间不存在计算依赖关系，两者之间是可并行的；相似度的计算和目标预测评分计算之间存在先后顺序，即目标预测评分须依赖于相似度的计算，两者之间必须是串行关系；UAS、IAS与、存在顺序性，两两之间分别是串行计算；而和之间无依赖关系，可并行计算；预测评分计算之间也是可并行的。上述计算过程关系如图1所示。需要说明的是：UAS和IAS虽然实质上也是相似度的计算，但是由于计算空间不同，所以不与和中的相似度计算部分混合，而是作为单独的过程进行计算。
3 ASUCF算法并行化计算的过程及实现（Process and implementation of parallel ASUCF）
3.1 UAS和IAS的计算
UAS的计算实际是通过对当前用户已评分项目相似度的综合衡量，得到当前用户的兴趣跨度。变换评分矩阵输入成键值对形式，过程如图2所示，共包含三个MapReduce过程，每个过程都可并行运行。后续章节中的offset代表每条记录在评分表中的偏移量。
输入：评分矩阵，当前用户id。
输出：当前用户的UAS值。
IAS的计算实际是通过对已给出当前项目评分的用户相似度的综合衡量，得到当前项目的适用用户分布度。变换评分矩阵输入成键值对形式，过程如图3所示，共包含三个MapReduce过程，每个过程都可并行运行。
输入：评分矩阵，当前项目id。
输出：当前项目的IAS值。
用户相似度的并行计算过程参照文献[15]，同理得出项目相似度的并行计算过程，在此不再赘述。
3.2 预测评分及推荐的计算
综合3.1内容及用户相似度、项目相似度并行化过程设计，分析如下：
步骤一：将输入经过MapReduce输出为<用户，（项目，评分）>，生成用户向量矩阵user-vector matrix；将用户向量矩阵转置为<项目，（用户，评分）>，生成项目向量矩阵item-vector matrix。
步骤二：用<（用户，用户），相似度>构成用户相似度矩阵user-similarity matrix；用<（项目，项目），相似度>构成项目相似度矩阵item-similarity matrix。
步骤一和步骤二在文献[15]中已具体表述。
步骤三：矩阵相乘，公式计算。
（1）项目向量矩阵×用户相似度矩阵，根据式（4）计算，如图4所示。
（2）用户向量矩阵×项目相似度矩阵，根据式（5）计算，如图5所示。
关键4：根据（用户，项目）进行聚合，、推荐结果计算如图6所示。
当目标用户需要推荐时，在Map阶段输入用户对项目的预测评分，在Reduce阶段根据预测分值排序，返回TOP-N推荐集。至此，推荐完成。
在所有阶段的MapReduce过程设计没有改变算法的数学计算关系，所以对算法的计算结果没有影响，在Hadoop平台上运行与非并行模式下运行的推荐结果是一样的，但是，并行模式Hadoop下的算法，有高效的大数据集计算能力，可扩展性较高。
3.3 基于Mahout的ASUCF并行化实现
Mahout中的RecommenderJob实现了item-based CF全推荐过程的MapReduce编程，本文在此基础，改写RecommenderJob，实现ASUCF的并行化。结合上一章的分析，算法主要步骤如下[16]：
（1）改写PreparePreferenceMatrixJob，将USER_VECTORS重命名为USER_RATING_MATRIX，原Item向量RATING_MATRIX重命名为Item_RATING_MATRIX。
（2）以RowSimilarityJob的工作过程为模板，增加UserSimilarityJob，将输入改成USER_RATING_MATRIX，计算出用户的相似度。
（3）以AggregateAndRecommend的工作过程为模板，增加asucfaggregateAndRecommend，改写AggregateAndRecommend中预测评分计算：
PU（i，c）=sum（all n from N：（usersimilarity（i，n）-uas（i）*（Item_RATING_MATRIX（i，n）-Average（i））/sum（all n from N：abs（usersimilarity（i，n）-uas（i））
关键词：协同过滤；计算效率；加速比；Hadoop；Mahout
中图分类号：TP391 文献标识码：A
文章编号：2096-1472（2016）-06-17-04
Abstract：Aiming to solve the CF’s （Collaborative Filtering） computing efficiency problem in big data processing，the paper proposes parallel ASUCF（Average Similarity of User-Item Collaborative Filtering） algorithm.It applies the MapReduce parallel-programming model in Hadoop platform，which improves the CF’s computational efficiency in big data processing on a single PC.Combined with Mahout，the parallelization of ASUCF is achieved.The paper designs speedup experiments on different data sets.The experiment results prove that the parallel algorithm brings out better computing performance in big data processing.
Keywords：collaborative filtering；computing efficiency；speedup；Hadoop；Mahout
1 引言（Introduction）
互联网时代，网络资源纷杂，信息过载，个性化推荐成为缓解用户在网络中的信息迷茫问题的重要途径[1]。在多项目、多领域的推荐中，因不依赖用户或项目内容，具有较好通用性的协同过滤算法[2]成为较为成功的推荐技术，其改进因而也受到广泛关注。然而，改进的算法通常是以牺牲计算效率换取计算准确度的提升。随着大数据时代的来临，解决计算效率的问题也迫在眉睫。由于单机模式的计算能力有限，而分布式计算具有多资源、可扩展、高效计算等优势，所以用分布式计算实现高效的CF算法，既能提高推荐准确度，又能保证计算效率。目前主要使用云计算平台Hadoop实现算法的并行化，如文献[3—8]等是通过将算法移植至Hadoop，以得到高计算性能的算法。
本文将基于平均相似度的协同过滤推荐算法（Average Similarity of User-Item Collaborative Filtering，简称ASUCF）与开源分布式平台Hadoop结合，改写Mahout中Item-based CF分布式实现，研究ASUCF算法的并行化，探索其MapReduce过程设计，并通过在不同规模的数据集上实验，比较单节点计算与多节点计算在计算效率上的差别，证明并行化后的ASUCF算法在计算效率上的优势，更能适应大数据环境。
2 Hadoop平台及ASUCF算法并行化分析（Hadoop and analysis of ASUCF in parallel）
2.1 ASUCF算法概述
文献[9]详细描述了ASUCF算法，并通过实验证明推荐准确度的提高，在此对其简单描述，为后续的并行化分析作铺垫。ASUCF为避免矩阵预处理带来的偏差，改进的算法回归到最原始的评分矩阵，从用户行为分析、项目行为分析，引入平均相似度，将计算预测评分分解成用户角度的预测和项目角度的预测两部分，综合两部分后得到最终的用户对项目的预测评分。
用户的项目平均相似度和项目的用户平均相似度计算分别如式（1）和式（2），和分别表示用户已评分项目的集合，对项目已评分的用户集合：
综合用户、项目两方面，引入UAS、IAS，则目标用户对目标项目的预测评分如式（3）所示。
2.2 Hadoop简介
Hadoop起源于Apache公司的Lucene和Nutch项目[10]，是谷歌云计算理论的Java语言实现。2006年，实现分布式文件系统和MapReduce的部分从Lucene和Nutch中分离出来，成为新项目Hadoop[11]。对应GFS实现的HDFS、并行计算模型MapReduce是Hadoop中最核心的部分。HDFS是Hadoop中的文件管理系统，采用主从结构，一个集群中包括一个主控服务器，即目录节点NameNode，用于索引DataNode、负责系统内文件命名空间操作、数据块和DataNode之间的映射关系等；以及多个块服务器，即数据节点DataNode，用于数据物理存储，文件通常被划分成若干个数据块，储存在不同的DataNode中[12]。MapReduce是一种可靠、高效的并行编程模型和计算框架，借助于HDFS等分布式技术，能够处理各类PB数量级的大数据[13]，其构成部分主要有一个主控服务JobTracker，若干个从服务TaskTracker，分布式文件系统HDFS，以及客户端Client[14]，它们的主要功能分别是：
（1）JobTracker：将作业划分成若干个任务，分发给多个TaskTracker，管理任务的执行以及输出反馈。 （2）TaskTracker：完成若干个Map、Reduce任务，并向JobTracker实时反馈执行情况。
（3）HDFS：数据、相关信息的保存及管理。
（4）客户端Client：Map和Reduce程序的编写，作业的提交。
MapReduce通过分解任务、合并结果的分而治之思想实现可分解、可并行处理大数据集上的并行计算。MapReduce的任务执行过程由Map和Reduce两阶段构成，每次Map和Reduce的输入和输出均是键值对
2.3 ASUCF算法分析
要实现算法的并行性，首先需要分析出算法中的可并行计算部分，以及并行计算部分与串行计算之间的关系。为方便表述，设：
通过对改进算法ASUCF的分析，将每次推荐的计算分解为：UAS、IAS、、，其中又可分解为两两用户的相似度计算和目标预测评分的计算；又可分解为目标区域内两两项目的相似度计算和目标预测评分的计算。UAS、IAS之间不存在计算依赖关系，两者之间是可并行的；相似度的计算和目标预测评分计算之间存在先后顺序，即目标预测评分须依赖于相似度的计算，两者之间必须是串行关系；UAS、IAS与、存在顺序性，两两之间分别是串行计算；而和之间无依赖关系，可并行计算；预测评分计算之间也是可并行的。上述计算过程关系如图1所示。需要说明的是：UAS和IAS虽然实质上也是相似度的计算，但是由于计算空间不同，所以不与和中的相似度计算部分混合，而是作为单独的过程进行计算。
3 ASUCF算法并行化计算的过程及实现（Process and implementation of parallel ASUCF）
3.1 UAS和IAS的计算
UAS的计算实际是通过对当前用户已评分项目相似度的综合衡量，得到当前用户的兴趣跨度。变换评分矩阵输入成键值对形式，过程如图2所示，共包含三个MapReduce过程，每个过程都可并行运行。后续章节中的offset代表每条记录在评分表中的偏移量。
输入：评分矩阵，当前用户id。
输出：当前用户的UAS值。
IAS的计算实际是通过对已给出当前项目评分的用户相似度的综合衡量，得到当前项目的适用用户分布度。变换评分矩阵输入成键值对形式，过程如图3所示，共包含三个MapReduce过程，每个过程都可并行运行。
输入：评分矩阵，当前项目id。
输出：当前项目的IAS值。
用户相似度的并行计算过程参照文献[15]，同理得出项目相似度的并行计算过程，在此不再赘述。
3.2 预测评分及推荐的计算
综合3.1内容及用户相似度、项目相似度并行化过程设计，分析如下：
步骤一：将输入
步骤二：用<（用户，用户），相似度>构成用户相似度矩阵user-similarity matrix；用<（项目，项目），相似度>构成项目相似度矩阵item-similarity matrix。
步骤一和步骤二在文献[15]中已具体表述。
步骤三：矩阵相乘，公式计算。
（1）项目向量矩阵×用户相似度矩阵，根据式（4）计算，如图4所示。
（2）用户向量矩阵×项目相似度矩阵，根据式（5）计算，如图5所示。
关键4：根据（用户，项目）进行聚合，、推荐结果计算如图6所示。
当目标用户需要推荐时，在Map阶段输入用户对项目的预测评分，在Reduce阶段根据预测分值排序，返回TOP-N推荐集。至此，推荐完成。
在所有阶段的MapReduce过程设计没有改变算法的数学计算关系，所以对算法的计算结果没有影响，在Hadoop平台上运行与非并行模式下运行的推荐结果是一样的，但是，并行模式Hadoop下的算法，有高效的大数据集计算能力，可扩展性较高。
3.3 基于Mahout的ASUCF并行化实现
Mahout中的RecommenderJob实现了item-based CF全推荐过程的MapReduce编程，本文在此基础，改写RecommenderJob，实现ASUCF的并行化。结合上一章的分析，算法主要步骤如下[16]：
（1）改写PreparePreferenceMatrixJob，将USER_VECTORS重命名为USER_RATING_MATRIX，原Item向量RATING_MATRIX重命名为Item_RATING_MATRIX。
（2）以RowSimilarityJob的工作过程为模板，增加UserSimilarityJob，将输入改成USER_RATING_MATRIX，计算出用户的相似度。
（3）以AggregateAndRecommend的工作过程为模板，增加asucfaggregateAndRecommend，改写AggregateAndRecommend中预测评分计算：
PU（i，c）=sum（all n from N：（usersimilarity（i，n）-uas（i）*（Item_RATING_MATRIX（i，n）-Average（i））/sum（all n from N：abs（usersimilarity（i，n）-uas（i））