基于改进NSGA-II的推荐算法

张海潮，杨连贺

(天津工业大学 计算机科学与技术学院，天津 300387)

0 引 言

推荐算法是根据用户偏好需求模型来进行项目推荐,与用户偏好需求越匹配的项目则越倾向于推荐给用户[1]。传统的推荐算法大多只将准确率作为评价指标[2]。这类基于准确率的推荐算法虽然能够保证一定的准确率，但会导致一些无用的推荐。因此，许多研究人员致力于推荐长尾项目或流行度低的项目[3]，而这类推荐会导致准确率降低。在推荐算法中，提高准确率和增加多样性是两个相互矛盾的性能指标，为了使这两个指标都尽可能地达到最优化，需要在其中进行协调和折衷处理。因此许多研究人员将多目标优化引入了推荐系统[4]。文献[5]提出了一个多目标推荐框架，该框架在推荐长尾项目的同时尽可能地降低精度的损失。文献[6]提出了一种多目标模拟退火方法，有效地缓解了长尾问题。文献[7]提出了一种推荐系统的多目标进化算法，该算法相较于传统算法具有良好的推荐多样性。文献[8]提出了一种基于SVD和多目标免疫优化的推荐算法，改善了推荐系统的准确性-多样性的困境。

遗传算法是一种全局随机搜索和优化方法[9]。其中NSGA-II算法由于其自身的简单有效性，已成功地应用于大量多目标优化问题[10]。

本文首先通过概率矩阵模型对目标用户产生推荐候选集，将推荐结果的准确率和多样性作为目标函数，把推荐问题转化为多目标优化问题，并根据改进的NSGA-II算法对目标用户产生一组推荐，实验结果表明了所提算法的有效性。

1 相关技术

1.1 概率矩阵分解模型

概率矩阵分解(probabilistic matrix factorization)是从概率的角度来预测用户对物品的评分，是隐语义模型的概率化形式[11]。该模型假设用户U和项目V的特征矩阵均服从高斯分布，通过评分矩阵中的已知值得到U和V的特征矩阵，并用特征矩阵去预测评分矩阵中的未知值。

本文利用概率矩阵分解模型预测评分矩阵中的未知值，并根据预测评分对目标用户产生推荐项目的候选集。

1.2 多目标优化

多目标优化问题是指使多个目标在给定区域尽可能同时达到最优，然而这些目标通常是相互冲突和影响的。多目标优化问题描述如下

(1)

式中：x=(x1,x2,…,xn)T是决策向量，Ω是x的向量空间，m是目标个数。Pareto支配、Pareto最优解、Pareto最优解集、Pareto前沿定义请参见文献[12]。

1.3 NSGA-II算法

算法首先随机产生大小为N的父代种群P0，种群根据非支配性进行排序，每个个体都被分配一个适应度，使用锦标赛选择、交叉和变异操作产生了大小为N的子代种群Q0。由于引入了精英策略，自初代后的过程有所不同。图1 描述的是第t代的过程，首先将第t代的父代种群Pt和通过交叉变异产生的子代种群Qt合并为Rt，Rt通过快速非支配排序得到一系列非支配Pareto解集，分别为F1,F2,F3…,它们的等级依次降低，首先选择F1进入种群Pt+1，如果F1小于N，则继续选择F2进入Pt+1，直到F1+F2+…+Fi刚好大于或等于N，这里称Fi为临界层，再对临界层计算拥挤距离，优先选择拥挤度小的个体先进入Pt+1，直至达到最大迭代次数。

图1 NSGA-II算法过程

2 存在的问题

2.1 拥挤距离计算

NSGA-II算法的排挤机制是建立在个体的拥挤距离之上的。拥挤距离用于估计总体中某一特定个体周围的解的密度，第i个个体的拥挤距离是它所在层级的两个相邻个体在每个目标上的距离之和。在同一层级上的个体，拥挤距离大的个体被优先选择。这一策略保留了拥挤度较小的个体。但是该策略存在一定的局限性：由于拥挤距离只计算了一次，如果拥挤距离较小的多个个体集中在了一个区域，那么这些个体将同时被删除。

2.2 交叉变异算子

遗传算法在进化代数接近终止代数时，种群接近于一个齐次种群。这是由于在选择交叉个体时采取精英策略，适应度好的个体更容易进入交配池，所以在交配池中会出现重复的个体，因此，迭代次数越多，个体的重复率越大。一般会通过变异操作改善这种情况，但是传统的变异算子会设定一个固定值，且变异概率较小，即使进行了变异操作，也会出现种群过早收敛的现象。

3 改进的NSGA-II算法

3.1 改进的拥挤距离计算

为了改善上述关于拥挤距离计算中存在的问题，本文提出了一种动态调整拥挤距离的方法。计算过程如下：

(1)计算相邻两个个体之间的欧式距离。假设有n个个体，第k(k∈(2,n-1)) 个个体和第k+1个个体之间的拥挤距离为

(2)

式中：m为目标的数目，fi(k) 为第k个个体在第i个目标上的值，fimin为第i个目标的最小值，fimax为第i个目标的最大值。

(2)找到最小拥挤距离I[k,k+1]， 比较I[k-1,k] 与I[k+1,k+2] 的拥挤距离，若I[k-1,k] 小，则淘汰个体k，否则，淘汰个体k+1。

(3)更新拥挤距离。

(4)判断是否满足需要个体的数目。若不满足，则返回(2)，否则，终止。

例如，在图2中，I[D,E] 的拥挤距离最小，则比较I[C,D] 与I[E,F] 的拥挤距离，因I[E,F] 的拥挤距离更小，故淘汰个体E，删除I[D,E] 与I[E,F] 的拥挤距离，并重新计算I[D,F] 的拥挤距离。

图2 改进的拥挤距离计算

3.2 改进的交叉变异算法

针对遗传算法中种群过早收敛的问题，本文设计了一种基于近亲系数的交叉变异算法。该算法同时考虑了进化代数对交叉变异的影响。为方便描述，本文有如下定义：

定义1 近亲系数

(3)

式中：F(Xi,Xj) 表示两个个体的近亲系数，l是个体基因的长度，xik表示个体Xi的第k个基因，μk表示第k个等位基因的权重，μk在本文中取1/l。

定义2 近亲个体：若两个个体的近亲系数大于设定阈值，则认为这两个个体为近亲个体。

交叉变异算法描述如下：

(1)随机选择两个父代个体Xi和Xj(个体长度为l)，找到两个个体相同的等位基因集Ns和不同的等位基因集Nd。

(2)计算近亲系数，判断两个父代个体是否属于近亲个体，若是，则返回步骤(1)，否则执行步骤(3)。

(3)将Ns中的基因传入子代个体，并在基因集Nd中随机选择l-|Ns| 个基因传入子代个体。

(4)根据相同等位基因的个数计算需要变异基因的个数，计算公式如下

(4)

式中：Nv表示需要变异的个数。

(5)根据相同等位基因的个数以及当前迭代次数ei计算变异概率，计算公式如下：

(5)

式中：α为一个0～1的系数，eva为总的迭代次数。

(6)根据变异个数和变异概率进行变异。

例如，A和B是两个父代个体，首先找到它们相同的等位基因集并传入子代C中(相同基因为5,18,9,2)，再从不同的等位基因集中随机选择6个基因传入子代中(例如：7,35,24,6,16,8)，根据式(4)和式(5)计算变异基因个数和变异概率，分别为2和p′v， 如图3所示，在位置2和位置6进行了变异。

图3 改进的交叉变异算法

4 多目标推荐算法

4.1 目标函数

推荐系统主要关注的是推荐的准确率，这里用f1表示推荐的准确率，公式如下

(6)

式中：R表示对用户i的推荐列表，Rij表示用户i对项目j的预测评分。

除了推荐的准确率，我们也希望能够增加推荐的多样性，这里用f2表示推荐的多样性。公式如下

(7)

式中：s(j,k) 表示项目j和项目k的相似度。

为提高推荐的准确率，应该使f1尽可能大。为了提高推荐的多样性，应该使f2尽可能小。但是准确度和多样性是两个互相冲突的目标，因此推荐问题转换成了多目标优化问题

min{-f1,f2}

(8)

4.2 算法流程

Input：Rm×n，User_ID，eva，L，N//输入评分矩阵，目标用户ID，最大迭代次数，推荐列表长度，种群规模。

Output：set[]为目标用户的推荐解集。

步骤1 使用PMF算法产生候选集S；

步骤2 从S中产生N组初始种群P0，并计算初始种群中个体的f1和f2的值；

步骤3 将Pt(初代为P0)进行快速非支配排序，使用锦标赛选择机制产生规模为N的种群Peli；

步骤4 根据3.2节介绍算法对Peli进行交叉变异操作，得到子代种群Qt(初代为Q0)，大小为N；

步骤5 将Pt和Qt合并为Rt，大小为2N，对Rt进行快速非支配排序，得到的层级为F1,F2,F3…。先将F1中的个体加入到下一次迭代种群Pt+1，若 |F1|

步骤6 根据3.1节中介绍的算法对Fm进行拥挤距离计算，每次删除一个拥挤度最大的个体并更新拥挤距离，直至Fm中剩余N-(|F1|+|F2|+…+|Fm-1|) 个个体为止；

步骤7 判断是否达到迭代次数，若没有，则返回步骤3，否则，终止。

4.3 算法复杂度分析

假设目标函数数目为M，种群大小为N，则改进的NSGA-II算法的时间复杂度计算如下：

非支配排序的时间复杂度为O(M×(2N)2)； 拥挤距离计算的时间复杂度为O(M(2N)log(2N))； 同一层级选择的时间复杂度为O(2Nlog(2N))； 交叉变异的时间复杂度为O(N)， 所以算法总体的时间复杂度为O(M×(2N)2)。

5 实验结果及分析

5.1 数据集

为了验证提出的算法的有效性，本文分别在Movielens数据集和Jester数据集上进行实验。Movielens数据集包含了943名用户对1682部电影的10万条评分数据，所有的评分值落在[0,5]区间内，每位用户至少对20部电影评分。Jester数据集包含63 978名用户对150条笑话的超过170万条评论，所有评分值落在[-10,10]区间内，本文将评分值映射到[0,5]区间上。在本实验中，将数据集随机划分80%的数据作为训练集，20%的数据作为测试集。

5.2 参数设置

本文参数设置见表1。

表1 实验参数

5.3 评价指标

本文采用推荐系统中常用的度量指标，准确率、多样性和新颖度作为推荐结果的评价指标

(9)

(10)

pop=log(1+N(i))

(11)

其中，R表示所有用户的集合，R(u) 表示在训练集上通过训练推荐给用户的列表，T(u) 表示在测试集上用户的评价过的项目列表。s(i,j) 表示项目i和项目j的相似度。N(i) 表示评论项目i的用户数目。

5.4 实验结果

算法对目标用户产生一组推荐列表，图4给出了用户1的帕累托前沿。

图4 用户1的帕累托前沿

图4中每一个点都代表对目标用户的一组推荐列表，由于算法是在准确率和多样性之间进行权衡，所以f1越大，f2就越小。同理，f1越小，f2就越大。

为了验证所提算法的有效性，下面将本文算法与PMF算法和未改进的基于NSGA-II的推荐算法进行比较。本文算法和基于NSGA-II的推荐算法随机从测试集中取50个用户，并求出对每个用户产生的20组解在评测指标上的平均值，实验结果如图5所示。

图5 3种算法评测指标比较

图5(a)展示的是3种算法推荐结果的准确率。可以看出，在两个数据集上PMF算法的准确率最高，基于 NSGA-II 的推荐算法和本文算法的准确率较低，这是由于PMF算法会推荐预测评分最高的10个项目，而另外两种算法要在准确率和多样性之间进行权衡，必然会导致准确率的降低。但是本文算法的准确率在两个数据集上的准确率要高于基于NSGA-II的推荐算法。

图5(b)展示的是3种算法推荐结果的多样性。由于本文采用推荐项目之间的相似度衡量推荐结果的多样性，所以推荐结果的值越小，多样性就越高。由图中可以看出，在多样性方面，无论是在Movielens数据集还是在Jester数据集上，本文算法都优于另外两种算法。基于NSGA-II的推荐算法在两个数据集上相较于PMF算法在多样性方面也有所提高。

图5(c)展示的是3种算法推荐结果的新颖度。由实验结果可以看出，在Movielens数据集上PMF算法新颖度略好于其它两种算法，但是在Jester数据集上PMF算法明显比另外两种算法差。本文算法比基于NSGA-II的推荐算法在新颖度方面略好。

实验结果表明，本文算法虽然在准确率上相较于PMF算法略低，但是在准确率和多样性上都比基于NSGA-II的推荐算法表现好。因此对于大多数用户来说，本文算法能够在不降低准确率甚至有所提高的同时，有效地提高推荐的多样性，从而验证了改进算法的有效性。

6 结束语

针对传统的推荐算法中单一追求推荐结果的准确率而忽略多样性的情况，本文提出了一种基于改进NSGA-II的算法的推荐算法，通过一次推荐可以对目标用户产生一组推荐列表。实验结果表明，在不降低准确率的同时，本文算法能有效提高推荐结果的多样性。

本文实现的是推荐结果准确率和多样性两个性能之间的权衡，在实际的推荐过程中往往要考虑到3个甚至更多的性能需求。在未来，我们的研究将扩展到解决推荐问题的更多目标上。