一种基于NSGA-II的协同过滤推荐算法

摘要：为了提升几种基本的协同过滤推荐算法的精确度与召回率，引入了多目标遗传优化算法NSGA-II，并利用模型加权融合的方法实现了新的协同过滤算法。实验证明，该算法相较几种基本的协同过滤算法在精确度与召回率上均有所提升。

个性化推荐系统是近年来解决信息超载问题一个有效途径,它根据用户的信息需求、兴趣等历史行为，主动向用户推荐其可能感兴趣的产品或者信息。不同于用户利用搜索引擎进行主动检索，推荐系统通过收集用户的兴趣偏好，进行个性化计算，由系统发现用户的兴趣点，从而引导用户被动发现自己的信息需求。推荐系统根据用户兴趣和行为特点，向用户推荐所需的信息或商品，帮助用户在过载信息中快速发现真正所需的商品，提高用户黏性，促进信息点击和商品销售。

现阶段广泛利用推荐系统的领域包括电子商务、视频、音乐、社交网络、阅读、基于位置的服务、个性化邮件和广告等。如著名的电子商务网站亚马逊，推荐系统深入到了其各类产品中，其中最主要的应用有个性化商品推荐列表和相关商品的推荐列表。

目前常用的推荐算法有基于邻域的算法与矩阵分解算法^[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∈R^f×m和Q∈R^f×n是两个降维之后的矩阵。用户因子矩阵表示第u个用户对第k个因子的喜好程度，物品因子矩阵表示第i个物品中第k个因子的程度。在图书推荐系统中，图书因子可以理解为：图书的薄厚，距今年代是否久远，体裁是小说还是诗歌等。

如公式6所示，第u个用户对第i个物品的预测评分值为：

(6)

由于每种算法只能在一个评测指标上获取较好的结果，而不能在多个评测指标上获得突出表现，所以单独采用任何一种推荐算法都具有其局限性，所以我们引入多目标优化遗传算法对几种常用推荐算法做了一个线性加权操作。

2 NSGA-П算法简介

单目标优化研究的是单个目标函数的极值问题, 多目标优化则要同时优化多个、可能相互冲突的目标函数，而实际中的推荐系统就是一个多目标并存的系统。UserCF、ItemCF和MF是推荐系统的三个基础算法，在解决在面对多目标问题时往往不能给出相对优化的解。

NSGA-Ⅱ算法在强大的参数相互作用下，依然能得到比其他多目标遗传算法更接近于优化前沿的解。实际运算证明，该算法能够较好地解决实际过程的多目标优化问题，对此我们提出将NSGA-Ⅱ算法结合多种基础推荐算法应用在推荐系统中。

NGSA-II算法流程：

首先初始化种群，再将初始化后的种群在各等级内进行非支配排序。第一级被完全非支配在当前的种群，第二级被第一级内的个体支配，接下来也是。每个等级的个体被指定等级(适应度)或者根据个体所在的等级分配。第一等级的个体是一级适应度，在第二等级的个体是二级适应度等。

除了适应度，每个个体都要计算一个新的参数—拥挤距离[4]。拥挤距离是用来衡量个体和附近个体之间的距离值。越大的平均拥挤距离表明种群分布越多样。

根据适应度和拥挤距离，一定数量的父代种群通过二进制锦标赛法(种群中被选中的个体等级比别的个体小，或者在等级相同的情况下拥挤距离大于别的个体)从所有种群中选出。选中的个体经过交叉和变异等操作产生同数量的后代群体。

N为种群规模，目前的种群加上产生的子代将再次根据适应度和拥挤距离被非