一种基于NSGA-II的协同过滤推荐算法
摘要：为了提升几种基本的协同过滤推荐算法的精确度与召回率，引入了多目标遗传优化算法NSGA-II，并利用模型加权融合的方法实现了新的协同过滤算法。实验证明，该算法相较几种基本的协同过滤算法在精确度与召回率上均有所提升。
本文引用地址：http://www.eepw.com.cn/article/201603/287502.htm个性化推荐系统是近年来解决信息超载问题一个有效途径,它根据用户的信息需求、兴趣等历史行为，主动向用户推荐其可能感兴趣的产品或者信息。不同于用户利用搜索引擎进行主动检索，推荐系统通过收集用户的兴趣偏好，进行个性化计算，由系统发现用户的兴趣点，从而引导用户被动发现自己的信息需求。推荐系统根据用户兴趣和行为特点，向用户推荐所需的信息或商品，帮助用户在过载信息中快速发现真正所需的商品，提高用户黏性，促进信息点击和商品销售。
现阶段广泛利用推荐系统的领域包括电子商务、视频、音乐、社交网络、阅读、基于位置的服务、个性化邮件和广告等。如著名的电子商务网站亚马逊，推荐系统深入到了其各类产品中，其中最主要的应用有个性化商品推荐列表和相关商品的推荐列表。
目前常用的推荐算法有基于邻域的算法与矩阵分解算法[1]，而基于邻域的算法又被分为基于用户的协同过滤算法(UserCF)与基于物品的协同过滤算法(ItemCF)[5]。而根据常用的评测指标精确度(Precision)和召回率(Recall)来看，每种算法均不能在两个指标上获取较好的结果，所以推荐过程中单独利用某一种推荐算法都存在一定的局限性。
1 常用推荐算法介绍
1.1 基于邻域的算法
1.1.1 基于用户的协同过滤算法
基于用户的算法分为两步：首先，找到和目标用户兴趣相似的用户集合，然后找到这个集合中用户喜欢的，且目标用户没有听过的物品推荐给目标用户[2]。图1为基于用户的协同过滤推荐原理图。
基于用户的协同过滤算法推荐过程分为三步：
1.根据公式1计算用户u与用户v的相似度。
(1)
2.根据用户相似度，对每个用户获取其固定数量的相似用户。
3.根据公式2推算用户u对物品i的感兴趣程度。
(2)
1.1.2 基于物品的协同过滤算法
基于物品的算法也分为两步:首先，计算物品之间的相似度，然后根据物品的相似度和用户的历史行为给用户生成推荐列表[3]。图2为基于物品的协同过滤推荐原理图。
基于物品的协同过滤算法推荐过程分为两步：
1.根据公式3通过改进的余弦相似度公式计算物品i与物品j的相似度
(3)
2.根据公式4预测用户 对物品 的感兴趣程度
(4)
1.2 矩阵分解法
从矩阵分解角度来说，就是将评分矩阵 分解为两个低维矩阵相乘，如公式5所示：
(5)
其中P∈Rf×m和Q∈Rf×n是两个降维之后的矩阵。用户因子矩阵表示第u个用户对第k个因子的喜好程度，物品因子矩阵表示第i个物品中第k个因子的程度。在图书推荐系统中，图书因子可以理解为：图书的薄厚，距今年代是否久远，体裁是小说还是诗歌等。
如公式6所示，第u个用户对第i个物品的预测评分值为：
(6)
由于每种算法只能在一个评测指标上获取较好的结果，而不能在多个评测指标上获得突出表现，所以单独采用任何一种推荐算法都具有其局限性，所以我们引入多目标优化遗传算法对几种常用推荐算法做了一个线性加权操作。
2 NSGA-П算法简介
单目标优化研究的是单个目标函数的极值问题, 多目标优化则要同时优化多个、可能相互冲突的目标函数，而实际中的推荐系统就是一个多目标并存的系统。UserCF、ItemCF和MF是推荐系统的三个基础算法，在解决在面对多目标问题时往往不能给出相对优化的解。
NSGA-Ⅱ算法在强大的参数相互作用下，依然能得到比其他多目标遗传算法更接近于优化前沿的解。实际运算证明，该算法能够较好地解决实际过程的多目标优化问题，对此我们提出将NSGA-Ⅱ算法结合多种基础推荐算法应用在推荐系统中。
NGSA-II算法流程：
首先初始化种群，再将初始化后的种群在各等级内进行非支配排序。第一级被完全非支配在当前的种群，第二级被第一级内的个体支配，接下来也是。每个等级的个体被指定等级(适应度)或者根据个体所在的等级分配。第一等级的个体是一级适应度，在第二等级的个体是二级适应度等。
除了适应度，每个个体都要计算一个新的参数—拥挤距离[4]。拥挤距离是用来衡量个体和附近个体之间的距离值。越大的平均拥挤距离表明种群分布越多样。
根据适应度和拥挤距离，一定数量的父代种群通过二进制锦标赛法(种群中被选中的个体等级比别的个体小，或者在等级相同的情况下拥挤距离大于别的个体)从所有种群中选出。选中的个体经过交叉和变异等操作产生同数量的后代群体。
N为种群规模，目前的种群加上产生的子代将再次根据适应度和拥挤距离被非支配排序，只有最优的前N个个体会被选中，其他的将被淘汰。
然后再次迭代整个过程，直到达到最大迭代次数后退出循环，取其前最优的N个作为最终解。
3 NSGA-П算法在推荐算法中的应用
3.1 权重系数的初始化
R1'、R2'和R3'是三种不同的推荐系统算法ItemCF、UserCF和MF得出的三组推荐列表。三组列表推荐方式不同，得出多目标函数值也不同。为了得出多目标均较优的推荐结果，利用线性加权的方法可得到新的预测评分R''如公式7所示：
(7)
其中，λ1, λ2和λ3分别为各数据集所代表算法的权重系数，并且λ1+λ2+λ3=1。
根据λ1和λ2的值，得出对应的推荐列表，计算每组权重系数对应的各目标函数值。
3.2 非支配和拥挤距离排序
将当前权重系数种群进行非支配排序，每个权重系数被分配到各个等级中，得到等级变量。然后计算同一等级内，根据每组权重系数的多目标函数值，计算拥挤距离，根据结果进行排序。由此产生了整个种群的排序结果。
判断当前种群数量是否超过额定种群数量N，如是，则选取排序列表中前N个作为本代的结果。
3.3 子代权重系数的产生
在遗传算法中，两个父母代可以通过基因重组和遗传变异产生新的子代。包括以下三个基本遗传算子：选择、交叉和变异[7]。
1、选择。随机选取两组不同的权重系数作为父代和母代，λp11λp12和λp21λp22。
2、交叉。设置交叉系数为1，父代和母代在子代中所占的比例相同。故可定义产生的子代权重系数为：
(8)
(9)
3、变异。实际中，遗传变异是个小概率事件，故考虑设置变异系数。每当要产生子代前，随机产生一个0到1之间的数，若该数小于变异系数，则发生遗传变异，否则跳过此部分。遗传变异的过程产生的新权重系数为：
(10)
(11)
产生新的权重系数后，再进行排序和更新种群，筛选出M 个最优个体。如此反复进行迭代，不断产生新的权重系数和种群。
4 实验设计与实验结果
4.1 评测指标
本文中选择了精确度和召回率作为评价的主要标准。
令R(u)是根据用户在训练集上的行为给用户做出的推荐列表，而T(u)是用户在测试集上的行为列表。
那么，推荐结果的召回率定义为：
(12)
推荐结果的精确度定义为：
(13)
4.2 实验设计
(1) 实验数据
本文中利用的数据是MovieLens数据集，用户对自己看过的电影进行评分，分值为1～5，该数据是943个独立用户对1682部电影作的100000次评分的数据，其中每个用户至少对20个物品进行了评分[6]。
(2) 算法实现
全文的算法设计包括以下三个步骤：
1、基础算法的实现;
2、多目标遗传算法—NSGA-П的实现;
3、综合算法的整体实现。
1、基础算法的实现
ItemCF的实现：数据集的读入、各物品之间的相似度的计算以及最终推荐列表的获得。其中，在获取推荐列表时，选取N个与目标物品最相似的物品的过程中，N的值并不固定。取值规则为，从5-20中选取使得其精确度与召回率最高的那个值作为N。
UserCF的实现：数据集的读入、各用户之间的相似度的计算以及最终推荐列表的获得。其中，在获取推荐列表时，选取N个与目标用户最相似的用户的过程中，N的值并不固定。取值规则为，从5-20中选取使得其精确度与召回率最高的那个值作为N。
MF的实现：实现过程包括：数据集的读入、矩阵P与Q的初始化，各用户负样本的设定。对数据集进行训练迭代一定的步数，当误差达到局部最小或者迭代步数达到设置时退出训练，利用得到的矩阵P与Q获取最终的推荐列表。
2 多目标遗传算法的实现
多目标遗传算法的实现包括以下几个部分：
(1)随机产生100组权重系数λ1和λ2。
(2)读入基础算法的三组推荐表单，和
(3)编写目标函数和。
(4)NSGA-П主函数部分, 并在其中根据加权后的集合获取最终的推荐表单。
(5)输出10组最好的权重系数λ1和λ2，以及对应的目标函数值。
3 综合算法的整体实现
对以上五个数据集随机初始化100个权重系数，迭代10次，种群规模为10，交叉概率设置为1，变异概率设置为0.1。经过交叉和变异，得到五个数据集的权重系数，每个数据集有10组最优的λ1和λ2。对这五个数据集中的权重系数进行加权取平均值，得到最终的10组λ1和λ2。最后在u1.test，u2.test，u3.test，u4.test，u5.test上重新测试，每组得到10组Recall和Precision值。
4.3 实验结果
将基本算法得到的推荐表单代入计算程序，得到Recall和Precision值。表1为u1的实现结果。
分别对五组数据集，各随机初始化100组权重系数，通过NSGA-П的交叉变异迭代10次，得到最终的10组权重系数。表2为ItemCF、UserCF和MF在数据集u1上得到的权重系数表。
从表2可知，多目标最优化的ItemCF、UserCF和MF分布，MF的权重值最大，几乎占到一半，UserCF的权重值次之，ItemCF的权重值最小。
表3为u1测试集中基础算法与加权融合算法计算出的Recall和Precision值。由表3可以看出在经过多目标优化后，NSGA-П得出的推荐表单相比基础算法在Recall和Precision值上都有了明显的提升。
5 结束语
研究了推荐系统的相关算法。指出了常用推荐算法在多目标优化时的不足，然后提出了系数线性加权融的协同过滤推荐算法[8]。并利用NSGA-II算法针对其线性融合系数进行求解，仿真结果表明加权融合算法得到的结果相较几种基础的协同过滤算法在Recall和Precision指标上均有明显的提升。
参考文献：
[1]景民昌.从ACM RecSys2014国际会议看推荐系统的热点和发展[J].现代情报，2015:41-45
[2]项亮，推荐系统实践[M].北京:人民邮电出版社，2012
[3]Toby Segaran(著)，莫映，王开福(译).集体智慧编程[M].北京:电子工业出版社，2009
[4]Kalyanmoy Deb，Amrit Pratap，Saeer Agarwal，and T.Meyarivan，A Fast and Elitist Multiobjective Genetic Algorithm:NSGA-II[J].IEEE，2002:182-187
[5]王晓耘，钱璐，黄时友.基于粗糙用户聚类的协同过滤推荐模型[J].现代图书情报技术，2015:45-51
[6]宋真真.协同过滤技术在个性化推荐中的应用研究[D].合肥:合肥工业大学，2008
[7]吴兰兰.基于遗传学方法的个性化推荐技术研究[D].沈阳:沈阳航空工业学院，2010
[8]Hao Wen，Liping Fang，Ling Guan.A hybrid approach for personalized recommendation of news on the Web [J].Expert Systems with Applications，2012:5806-5814
本文来源于中国科技期刊《电子产品世界》2016年第2期第57页，欢迎您写论文时引用，并注明出处。
评论