基于Hadoop个性化推荐算法设计与实现

刘　斌， 李　帆， 姚　斌

(陕西科技大学 电气与信息工程学院， 陕西 西安　710021)

0　引言

随着“互联网”的发展和电子商务网站的兴起，在给人们带来便利和丰富信息的同时，信息过载的问题[1]也日益凸显，在这样的环境下个性化推荐[2]技术应运而生.传统推荐系统扩展性差且计算耗费大量时间，面对海量数据表现差强人意.大数据分析平台[3]的出现，为个性化系统的改进提供了新的方向，其中Hadoop[4]平台的分布式文件系统HDFS提供了海量数据的存储能力，MapReduce并行计算框架通过对数据并行化处理，有效提高算法性能和系统执行效率，提升了系统海量数据下的计算能力.目前也有针对特定推荐算法的Hadoop并行化研究，如李改等[5]提出了基于ALS的协同过滤算法的并行方法，王毅[6]提出了基于Hadoop的Slpoe One及其改进算法实现，但都没有避免全局扫描带来的高额开销.

推荐系统的响应速度是影响用户体验的关键指标，而传统个性化推荐系统在存在数据处理规模限制和推荐实时性低下的问题，扩展性不强，将其直接部署在分布式平台上且不能发挥大数据平台的优势，同时大量数据的分散存储造成计算时占用过多集群宝贵的带宽资源，影响推荐实时性.针对以上问题，选择基于聚类和MapReduce并行化算法提高数据分析能力和可扩展性，并在其中引入奇异值分解降低数据稀疏性对算法效果的影响.

1　分布式个性化推荐算法设计

个性化推荐算法是推荐系统的核心，其算法多种多样，选择不同的算法对推荐的质量和实时性有不同的影响.根据用户评分数据的形式，选择基于用户协同过滤[7]个性化推荐算法进行了Hadoop分布式算法的设计.

(1)收集用户物品评分矩阵.设共有m个用户和n个物品，用户对物品的评分可以表示为矩阵形式H∈m+n.

(1)

式(1)中：rij表示第i个用户对第j个物品的评分.

(2)选择进行相似度计算的用户.为了提升推荐算法的扩展性，采取将用户进行聚类[8]并类簇内进行推荐，同时将不同类簇的用户存储到同一机架方便本地计算，减少带宽消耗.但随着物品和用户数量的增多，用户物品评分矩阵存在很强的稀疏性，对用户进行聚类的效果往往较差[9].为了改善聚类效果，采取奇异值分解[10](Singular Value Decomposition,SVD)对用户物品评分矩阵降维.

(3)目标用户与所其属类簇内用户的相似度计算[11]，选择最近邻居.本文以余弦相似度为基础设计相似度计算.余弦相似度计算如下：

(2)

余弦相似度将用户评分视为空间中的矢量，通过计算两矢量之间的夹角进行度量，夹角越大，说明两用户兴趣方向越相近，相似性越高.

考虑到相似度计算时不同物品对结果的贡献度不同，例如潮流商品，购买的人很多，且一般都是追赶流行度，很少表达自己的兴趣，同时在冷门的物品方面用户购买时往往有很强的目的性，其推荐效果一般，这类物品对相似度计算造成影响，使推荐的长尾挖掘能力降低，因此基于余弦相似度引入物品贡献权重进行相似度计算.记所有物品购买次数集合为c={c1,c2,…,cn}，设计物品i的贡献度权重：

(3)

式(3)中：n为物品总数，meanc，stdc为集合C的均值和标准差.

从式(3)上看减弱了物品购买人次两端的权重，突出了均值附近物品的影响.设计相似度计算方法为：

(4)

式(4)中：i，j为用户，Ti,j为两用户共同购买的物品集合，xi,u为用户i对物品u的评分.选择与目标用户相似度最高的前M个用户作为其近邻.

(4)推荐物品.得出目标用户近邻后，计算目标用户对近邻观看但自己没有观看的物品的评分，评分预测公式为：

(5)

式(5)中：i为目标用户，p为待评分物品，K为最近邻集合，ri,rj分别为目标用户i和近邻j的平均打分.最终选择评分最高的前N个物品对目标用户进行推荐.

对比现有协同过滤算法，对本文算法在以下两点进行提升：

(1)推荐实时性.现有协同过滤算法对目标用户或者物品寻找相似用户或物品，计算相似度时需要遍历整个用户物品矩阵，在大数据的背景下，计算开销巨大；同时用户物品矩阵分布式存储于HDFS当中，完全遍历同样会造成过多I/O开销，降低推荐的实时性.

本文算法首先通过对用户进行聚类打上类别标签，对目标用户在所属类内进行推荐，避免了全局遍历计算，减少了计算的时间和空间消耗；在HDFS存储时进行了类别的分离存储，将同一类别用户信息存储于同一服务器或机架上，有效减少了节点间通信造成的I/O消耗.

(2)推荐准确性.由于数据的稀疏性，相似度计算不够准确，如两个用户有过行为的物品较少，但重叠的物品数目占比高，即使两用户评分有差距，根据相似度计算公式，也会造成两者相似度计算结果较高.本文算法通过SVD进行了特征的筛选，在此基础上对用户聚类，类别内用户关联性更强，通过在类簇内推荐，精度更高，并添加物品贡献权重，增强了推荐的长尾挖掘的能力，提升推荐的覆盖率.

2　基于Hadoop个性化推荐算法实现

2.1　平台配置及工作流程

选择4台服务器搭建Hadoop平台，包括一个Master节点和3个Slave节点.节点配置为：8 G内存，500 G硬盘，操作系统为Ubuntu14.04，JDK版本1.7.0，Hadoop版本为2.6.5.集群工作流程如图1所示.

图1　基于Hadoop平台推荐算法流程

2.2　数据降维

Deerwester等[12]提出了奇异值分解用于发现文档中的潜在因子，该方法被Koren等[13]用于Netfix推荐比赛中.

SVD可以通过矩阵分解来逼近矩阵并从中提取重要特征，保留80%～90%的能量可以得到重要特征并去掉噪声，同时得到低维度的数据，因此将其用于用户物品矩阵，可以实现降维以增强用户聚类效果.

通过SVD分解可以提取用户喜好特征，评分矩阵分解为以下形式：

(6)

式(6)中：Hm*n为户物品评分矩阵，m代表用户个数，n代表商品个数，∑为m*n的对角奇异值矩阵.奇异值大小表示其重要程度，奇异值越大则影响度越大.U是一个m*m正交矩阵，每行表示一用户对于奇异值的权重向量.通过对角线奇异值从大到小排列，通过设置占总奇异值能量的阈值，选取前K个奇异值实现对原矩阵进行降维：

(7)

(8)

式(8)中：σi为奇异值，k为选择奇异值个数，percentage为保留的特征值能量比例.

SVD不适于分解用于分布式进行计算，需要传输所有数据到一个节点中进行计算，但聚类中心是定期更新，因此SVD进行的定期离线计算.

2.3　通过并行化K-means对用户聚类

K-mean聚类算法时间复杂度随数据量呈线性关系，因此适于针对海量数据的聚类分析，基于降维后的用户特征矩阵设计了对于用户的基于MapReduce的K-means聚类[14]方法，流程如图2所示.

图2　聚类算法MapReduce并行化流程图

首先随机选择k个用户生成全局的k个类中心的列表，备份到各个计算节点用于MapReduce任务计算.

在Mapper阶段：输入降维后用户物品评分矩阵，输出以类中心为Key，属于此类的用户为Value的键值对.依次计算用户与类中心的距离，选择距离最近的类中心对用户进行归类：

ci=arg minj‖xi-uj‖2

(9)

式(9)中：xi为用户特征向量，uj为聚类中心，ci即为xi所属类别.

在Reducer阶段：输入<类中心，用户>键值对，输出以类中心为Key，所属此类的用户列表为Value的聚类结果.将输入的<类中心，用户>键值对整合为<类中心，用户列表>，重新计算类簇中心：

(10)

式(10)中：m为用户个数，j为聚类类别，xi为用户特征向量，uj为类簇中心，即计算该类中所有用户平均值作为新的类簇中心.

设置算法收敛条件目标函数为最小化用户到所属类簇中心距离的平方和：

(11)

式(11)中：k为选择聚类的个数，x为用户特征向量，ui为类簇中心，dist(ui,x)为欧氏距离，如果算法收敛或达到最大迭代次数，输出聚类结果，否则返回Map阶段进行迭代.

每次聚类时间复杂度为O(m/n)，m为用户数量，n为节点个数，时间复杂度与计算节点数量呈反比例关系.

2.4　计算用户相似度并进行物品推荐

基于用户的协同过滤算法分为两步：首先计算目标用户与所属类簇内用户的相似度，选出相似度最高的M个邻居；对于邻居购买但目标用户没有购买的物品预测评分，选择评分最高的N个物品进行推荐.其具体的MapReduce实现流程如图3所示.

(1)输入：用户评分信息；输出：用户物品评分矩阵.

在Map阶段读入数据，取出用户(U)、物品(M)、评分(R)，输出键值对.在Reduce阶段，完成用户信息的收集，输出，获得用户物品评分矩阵.

(2)输入：用户物品评分矩阵；输出：物品用户评分矩阵.

在Map阶段读取用户物品矩阵，将数据拆分，输出键值对.在Reduce阶段，将输入数据进行组合，输出，获得物品用户评分矩阵.

(3)输入：物品用户评分矩阵，用户聚类信息；输出：用户最近邻居.

在Map阶段读取物品用户评分矩阵和用户聚类信息，设用户集合为Us，用户类别集合为c=(c0,c1,…ck)，其中k为用户类别总数，对于U1,U2∈Us，如果U1∈ci&U2∈ci，即U1，U2为同一类，则输出<(U1:U2),(U1_R:U2_R)>的键值对，其中Value为用户对物品评分.在Reduce阶段，对用户对U1，U2根据式(4)进行相似度计算，得出相似度simU1,U2，根据相似度对每个用户选取相似度最高的K个邻居List(N)，其中N为邻居，输出键值对.

(4)输入：用户最近邻集合，用户物品评分矩阵；输出：用户推荐物品集合.

在Map阶段读取最近邻集合和用户物品评分矩阵，对最邻近集合进行拆分，输出的键值对，对于用户物品评分矩阵，将其直接输入到Reduce阶段.在Reduce阶段，根据式(5)预测用户对近邻购买但自己没有购买的物品，最终选择评分最高的前P个物品对目标用户进行推荐.输出，存储到HDFS当中.

3　实验测试与分析

3.1　实验数据说明

本文以对电影进行推荐为例，选取用户对电影的评分数据作为原始数据进行推荐，其中评价信息包括：用户标识，电影标识，用户对电影的评分.实验数据采用从MovieLens下载的大小分别为100 KB、1 MB、10 MB的数据集进行实验.各数据集详细信息如下：(1)100 KB：包括943个用户对1 628部电影的100 000条评分记录.(2)1 MB：包括6 040个用户对3 900部电影的1 000 209条评分记录.(3)10 MB：包括71 567个用户对10 681部电影的10 000 054条评分记录.评分范围为1～5，每个用户至少对20部电影进行过评价.

3.2　评价指标

采用准确率、召回率和覆盖率[15]作为实验的评价方式，比较本文设计算法与原有算法的推荐效果.准确率表示用户对系统推荐商品感兴趣的概率，召回率表示用户喜欢商品被推荐概率，覆盖率表示向用户推荐商品能覆盖全部商品的比例，表达推荐的新颖度.准确率、召回率和覆盖率度量如下：

(12)

(13)

(14)

式(12)、(13)中：R(u)是通过训练集生成的推荐列表，T(u)是测试集上的行为列表.

式(14)中：Ip表示推荐的物品集，I为所有物品集.

对于单机与Hadoop分布式计算效率的对比评价，引入加速比S=T1/Tn来验证集群在不同数量的节点下对于大小数据集的推荐实时性的提升.其中T1表示算法在单机下的运行时间，Tn表示在集群下的进行推荐所用的时间，S越大，表明集群推荐实时性提升越明显.

3.3实验结果与分析

3.3.1推荐结果分析

以100 KB数据集作为实验数据，采用交叉检验的方式，随机选取80%数据作为训练数据，20%作为测试数据.分别在推荐邻居个数为5、10、20、40、60、80的情况下对基于用户的协同过滤方法和本文设计分布式协同过滤算法进行对比.

首先对用户电影矩阵依据算法设计流程进行降维，为保证保留足够能量不失真并达到降维的目的，在使用SVD降维时一般保留90%奇异值能量就可以得到重要特征并去掉噪声，在此基础上对用户进行聚类，聚类集群个数为8.最终对目标用户在所属类内进行相似度计算，并引入物品贡献度权重，生成推荐结果，与现有协同过滤算法具体比较结果如图4所示.

图4　评价指标对比图

在图4中，CF为现有基于用户的协同过滤方法，D-CF为本文设计协同过滤方法.从图4可以看出，随着近邻用户个数的增加，准确率和召回率上升，到近邻个数为40的时候开始趋于平缓，此时D-CF准确率和召回率相比CF有所提高.覆盖率上，两算法都随着近邻用户个数的增加递减，但D-CF较CF数值上有较大的提升，实验表明D-CF在提升召回率和准确率的同时，通过引入物品贡献度权重较好的提高了推荐的覆盖率，增强了推荐效果和个性化推荐的长尾挖掘能力，提高了推荐的新颖度.

3.3.2推荐性能分析

选取数据量大小分别为100 K、1 MB、10 MB的数据分别在不同数量节点的Hadoop集群下运行.通过比较S得出不同规模的集群对算法执行效率的影响.实验结果如图5所示.

图5　加速比对比图

从图5可以看出，在实验数据集为100 K时，在单机环境下执行效率更高，这是因为MapReduce过程的中间结果都会存储到HDFS之后再进行读取，期间系统的I/O操作占用了部分时间，说明Hadoop集群在处理小型数据集的时候表现并不好，并且不适于数据的实时处理.在另外两个较大数据集上，随着节点的增加，推荐算法的执行效率呈上升趋势，反映了基于Hadoop的个性化推荐算法提高了推荐的实时性和横向扩展性.

4　结论

为了提升个性化推荐系统的大数据处理能力，以电影评分为对象，选择了基于用户聚类的协同过滤算法，并在此基础上进行基于Hadoop个性化推荐的算法设计与实现.对用户电影矩阵降维，改善对用户聚类的效果；引入电影贡献权重，用于增强算法推荐的新颖度；通过对用户聚类缩小推荐范围并对数据分类存储，节省Hadoop集群的资源计算时间；最终对算法进行了基于MapReduce的并行化实现.实验结果表明，本文分布式协同过滤算法提升了个性化推荐新颖度，同时增加了推荐算法的可扩展性和推荐系统的推荐实时性.

[1] Listed N.Information overload[J].Nature,2009,460(7 255):139-143.

[2] Kantor P.B,Ricci F,Rokach L,et al.Recommender systems handbook[M].USA:Springer,2010:1-35.

[3] 王强,李俊杰,陈小军,等.大数据分析平台的建设与应用综述[J].集成技术,2016,5(2):2-18.

[4] White T.Hadoop:The definitive guide[M].3rd.USA:O Reilly Media,2012.

[5] 李改，潘嵘，李章凤，等.基于大数据集的协同过滤算法的并行化研究[J].计算机工程与设计，2012,33(6):2 437-2 441.

[6] 王毅.基于Hadoop的Slope One及其改进算法实现[D].成都：西南交通大学，2011.

[7] 黄震华,张佳雯,田春岐,等.基于排序学习的推荐算法研究综述[J].软件学报,2016，27(3):691-713.

[8] Truong K,Ishikawa F,Honiden S.Improving accuracy of recommender system by item clustering[J].Ieice Transactions on Information and Systems,2007(9):1 363-1 373..

[9] G.Linden,B.Smith,J.York.Amazon.com recommendation:Item-to-item collaborative filtering[J].IEEE Inter Computing,2003，7(1)：76-80.

[10] Manolis G,Vozalis,Angelos M,et al.Collaborative filtering through SVD-based and hierarchical nonlinear PCA[J].Artificial Neural Networks ICANN,2010,6 352:395-400.

[11] 马小军,赵伟.改进相似度的分布式个性化推荐[J].计算机工程与应用,2014,50(4):126-131.

[12] Deerwester Scott C,Dumais Susan T,Landauer Thomas K,et al.Indexing by latent semantic analysis[J].Jasis,1990,41(6):391-407.

[13] Koren Y,Bell R,Volinsky C.Matrix factorization techniques for recommender system[J].Computer,2009,42(8):30-37.

[14] Rashid A M,Lam S K,Karyp Is G,et al.Clust KNN:A highly scalable hybrid model & memory-based CF algorithm[C]//The Workshop on in Proc. of Webkdd. Philadelphia,Pennsylvania.USA:ACM,2006:1-59 593-444-8.

[15] 朱郁筱,吕琳媛.推荐系统评价指标综述[J].电子科技大学学报,2012,41(2):163-175.