陈 宏,王丽萍,翁杭立,祝俊毅,郭海东
1(浙江工业大学 教育科学与技术学院,杭州 310014) 2(浙江工业大学 管理学院,杭州 310014) 3(浙江工业大学 计算机科学与技术学院,杭州 310014)
推荐系统是利用统计学和知识发现等技术手段,通过挖掘和追踪用户行为和心理偏好,搜寻并定位满足需求的资源、产品和信息,减少用户在海量信息中的决策负荷,是应对信息过载的重要技术手段和工具[1].在电子商务、影视娱乐、在线学习以及医疗健康等领域已有广泛的研究和应用[2].推荐算法是推荐系统的核心,通过整合历史数据、挖掘用户喜好以提高推荐的有效性.准确性和多样性是推荐算法研究的二个重要指标[3],通过提高对用户行为预测的准确率[4]、优化排序技术[5]、构建推荐模型[6],最大程度地使推荐结果满足用户的需求.然而,基于准确性的推荐算法将导致推荐结果过于集中在某类特征上,使得多样性降低,导致用户选择的广度不足而整体效果不佳[7].因此,如何将推荐算法的准确性和多样性平衡以达到满足用户最大需求是推荐算法研究的重要关注点.为此,研究者提出在推荐算法不同阶段对不同目标进行优化[8],也有研究通过建模来获得两者平衡[9],然而这些研究均需较丰富的先验知识,故增加了推荐算法设计难度.有学者提出利用多目标优化思想来解决此类问题[10].其思想是在分析预测用户兴趣度基础上,将准确性和多样性作为推荐的二维目标,利用多目标优化算法进行推荐策略的搜索,最后得到最优推荐方案.然而,正如文献[10]所述,多目标优化得到的结果是目标间各种平衡情况的帕累托解集,解集数量多且不可控是制约多目标推荐算法实际应用的因素之一,如何选择最终满足需求的推荐方案是研究者无法规避的问题.
为了解决多目标推荐算法优化后有效方案选取问题,Wang等人[11]选择帕累托解集的极值点作为推荐方案,Chai等人[12]在得到帕累托解集后利用多属性决策法对解集进行二次排序选择获得最佳平衡解作为推荐方案.但此种方式实质上是优化过程和决策过程的分离,导致优化过程在决策者不感兴趣的区域浪费算法资源,且决策者在做决策时相对复杂.在多目标优化领域,偏好多目标优化是实现决策和优化相融合的技术[13],其通过事先给定偏好或优化过程中动态设置偏好的方式,将解集朝偏好区域收敛,最终获得具有偏好特征的帕累托前沿.然而,多数偏好多目标优化算法要求决策者事先给出偏好信息.很多情况下,如本文的推荐准确性和多样性最大化问题,决策者因缺乏足够的先验知识,无法给出明确的偏好信息,给偏好多目标优化算法在推荐领域的应用带来难题.
针对以上问题,本文利用最大预测评分模型和最大相似度差异模型构建二维目标模型,设计了获取隐式偏好的方法,提出一种基于隐式偏好的多目标推荐算法,对推荐的准确性和多样性兼顾优化.本算法首先通过基于领域算法预测兴趣度以及兴趣度排序产生推荐候选集;利用切比雪夫最小距离标定隐式偏好点,并在迭代过程中动态更新偏好点和偏好区域;采用基于HP-NSGA-II[14]的3层排序准则为进化策略,将解集收敛于偏好区域;最后以最小切比雪夫距离为决策准则,将非支配解进行推荐偏好的划分,生成具有不同目标偏好的推荐方案集.实验表明,此算法能在确保准确率的同时能提高推荐的多样性和新颖度,且能有效降多目标推荐算法的推荐方案的数量,提高算法的实际应用能力.
1.1 多目标推荐
多目标优化问题是多个目标效用最大化的问题,用数学公式(1)表示:
maxF(x)=(f1(x),f2(x),…,fn(x))
(1)
其中F(x)是具有互斥性的目标集.x=[x1,x2,…,xd]∈Ω为策略集向量,Ω为策略向量空间.当给定两个向量xA和xB,存在fi(xA)≥fi(xB),i=1,2,…,n,且F(xA)≠F(xB),称之为xA支配xB(xA≻xB),即xA更为优秀.当存在x∈Ω不被任何其他策略支配时,x称为帕累托最优解.所有帕累托最优解组成的集合称为帕累托集PS.
PS={x∈Ω|┐∃x′∈Ω,x′≻x}
(2)
帕累托集映射到目标空间形成的区域称为帕累托前沿(PF).
PF={F(x)|x∈PS}
(3)
如何有获取帕累托最优解是多目标优化算法的核心问题,也是多目标推荐最终能否提供有效推荐的关键.目前,多目标优化问题的求解有众多算法,如多目标进化算法、粒子群算法、免疫优化算法、蚁群算法等.其中,多目标进化算法(multi-objective evolutionary algorithms,MOEA)应用较为广泛,其模拟生物自然选择与进化规律执行随机搜索,能适用于解决高复杂度的非线性问题,且具有较好的通用性.根据进化机制不同,一般可以分为:基于支配关系,如NSGA-II、SPEA2等算法;基于指标,如IBEA、HypE等算法;基于分解,如MOEA/D、NSGA-III等算法[15].当引入决策者偏好信息时,则称为偏好MOEA.根据偏好信息不同可分为:基于占优关系,如g-NSGA-II;基于角度关系,如AD-NSGA-II;基于权重向量,如R-MEAD;以及基于偏好集,如iPICEA-g.
传统推荐算法多聚焦解决单个目标问题,如用户兴趣度预测误差的最小化[16],推荐结果评分最大化[17]等.近年来,有学者将多目标优化技术与推荐系统结合,获取满足多个推荐目标的最优结果,此类推荐技术称之为多目标推荐(multi-objective recommender systems,MORS).由此衍生出诸多研究.如平衡推荐的性能指标[18];缓解群组中个体和群体公平性矛盾[19];兼顾多利益相关者推荐[20]等.
推荐性能指标的平衡是MORS典型的研究领域.在推荐系统中,除了推荐的准确性外,新颖度、多样性、偶然性和流行度等指标也是衡量推荐系统质量和性能的指标.然而,指标间有可能存在互斥的情况,最大化其中一个指标有会导致其他指标性能的下降.因此,需要通过多目标优化技术来平衡相关指标产生推荐.根据MORS工作机制,相关研究可分为基于多目标优化的用户行为预测和推荐列表生成两大类.在预测评分方面,Cai等人[21]构建了一种混合模型,通过对多个推荐算法的预测值进行加权,利用MOEA学习权重值,加权后的结果为最终用户兴趣度预测值;Cao等人[22]在张量分解推荐算法中,利用MOEA进行张量学习,兼顾多个推荐性能;Xie[23]等人利用联合学习模型,为用户找到合适的多个目标间权重,在损失函数中对多个目标梯度加权,以预测用户兴趣度.在推荐列表生成方面,通过MOEA中种群的基因编码方式,可以对用户的推荐列表进行优化.Zuo等人[24]在对用户评分预测后,利用实数编码结合MOEA生成满足准确性和多样性目标的推荐列表;Wang等人[11]利用协同过滤技术筛选推荐候选集后,利用MOEA生成满足准确性和新型性目标的推荐列表;在此基础上,Cai等人[12]融合多属性决策,对MOEA产生的帕累托推荐列表集进行排序后推荐,降低了推荐方案的规模.
尽管多目标优化解决了传统推荐算法兼顾多个目标的难题,但其输出是数量众多的帕累托最优解,需依靠决策者筛选和确定最终推荐方案,而决策者偏好依赖先验知识,通常无法明确给定,这为多目标推荐算法效率和实际应用带来负担.基于此,本文算法聚焦推荐性能指标,其多目标推荐步骤如下:
1)预测用户兴趣度,构建拟推荐候选集;
2)根据推荐系统需求,建立目标问题模型;
3)利用多目标优化算法在候选集中搜寻最优策略;
4)在帕累托解集中选择最终推荐方案;
1.2 隐式偏好
多目标优化中膝点是天然的偏好点[25].而极值点则在某一目标上拥有最佳性能,且能有效获取前沿范围,帮助构建偏好[26].当决策者因缺乏足够先验知识而无法给出明确偏好信息时,可将PF的膝区域(Knee Region)和极区域(Extreme Region)作为隐式偏好区.膝区域的解在所有优化目标上具有最佳平衡性,而极区域则是某一目标上最大性能.对于推荐系统而言,当偏好信息未知时,在隐式偏好区域选择推荐方案可降低多目标推荐系统的决策难度.
当优化目标为最大化问题时,隐式偏好区域选择方法如公式(4).本文采用圆形区域,S为偏好参考点,r为区域半径.
R=[S,r]
(4)
膝区域和极区域偏好点定义如公式(5)～公式(7)所示:
(5)
(6)
(7)
极值点Sextr为任一目标值最大点.膝点定义为与隐式理想参考点z*切比雪夫距离最小点.隐式理想参考点z*为拥有所有目标最高值的点,其几何意义图1所示.
图1 隐式偏好下的极值点,膝盖点和理想点Fig.1 Extreme point,knee point and ideal point based on implicit preference
1.3 切比雪夫距离
切比雪夫距离(Chebyshev distance)是一种评价候选决策向量与偏好目标参考向量之间距离的效用函数[27].当给定目标空间中的偏好参考向量z,决策向量与其切比雪夫距离如公式(8)表示:
(8)
在一组策略集中,距离目标参考向量的切比雪夫距离最小的解可以定义为在该目标参考向量偏好下具有最佳平衡性能.
(9)
本文利用切比雪夫距离来获取膝点进而标定膝区域.
2.1 算法流程
本文基于隐式偏好的多目标推荐算法(Implicit preference multi-objective algorithm for recommender systems,IP-MRS)总体流程框架包含推荐候选集生成、基于隐式偏好的多目标优化、推荐策略选择3个阶段.具体算法流程见图2所示.
图2 算法框架和流程Fig.2 Framework and process of the method
2.2 候选集生成策略
候选集是拟推荐给用户的集合.本算法候选集生成策略包含两个步骤:
1)对用户未发生行为项目的兴趣度预测;
2)对项目根据兴趣度大小排序.
对用户兴趣度预测采用基于领域算法(KNN),根据用户行为计算项目间的相似度进而推测用户对未发生行的项目的兴趣度.本文采用余弦相似度计算方法[28].
(10)
Pu,i=∑j∈nS(i,j)ru,j
(11)
其中i和j为两个不同项目,u为用户,r为用户评分矩阵,Pu,i为预测用户u对项目i的兴趣度.进而筛选出兴趣度最高的K个项目(top-K)作为给目标用户推荐的候选集,并对候选列表的兴趣度进行归一化处理.
2.3 基于隐式偏好的多目标优化策略
2.3.1 目标函数构建
本文将采用基于预测评分最大化模型[24]和内部相似度差异最大化模型[18]作为准确性(accuracy)和多样性(diversity)目标构建二维目标模型.
(12)
(13)
maxF=(facc,fdiv)
(14)
其中u为目标用户,R为推荐列表,i,j为推荐项目.Pr(u,i)是推荐列表中用户u对项目i的兴趣度,sim(i,j)是推荐列表中项目之间的相似度.facc越大表明提供给用户的推荐列表越能满足其喜好,fdiv越大表明提供给用户的推荐列表中项目具有更好的多样性.二维目标最大化的含义是推荐方案既要满足用户的喜好又要保证足够丰富.上述2个目标间一定程度上是互斥的.
2.3.2 多目标进化策略
本算法多目标进化策略是基于HP-NSGA-Ⅱ算法思想[14].HP-NSGA-Ⅱ算法改进了种群更新机制,在Pareto非支配排序确定的临界层上以3层排序准则引导算法收敛目标区域,并且其在多个目标区域采用并行计算的方式提升算法性能.
进化策略描述如下:
Step1.公式(5)、公式(6)标定偏好点(极值点、膝点),公式(4)确定目标区域,目标偏好点数量为M,种群数量为N;
Step2.种群进化操作,确定临界层;
Step3.利用3层排序机制选择N/M个体进入下一代;
Step3.1如临界层在目标区域个体等于N/M,选入;
Step3.2如临界层在目标区域个体大于N/M,拥挤度排序后选入;
Step3.3如临界层在目标区域个体小于N/M,目标区域外个体与目标偏好点C_dis排序后补足数量;
Step4.重复Step 2,直到所有目标区域跟新完毕.
Step5.合并M个偏好区域的个体为子代种群.
2.3.3 遗传变异策略
在遗传变异操作上,采用均匀交叉机制(uniform crossover).考虑到给用户推荐的项目不应重复出现,当满足遗传条件时,两个父代中相同的项目遗传给两个子代,不同的项目以50%的概率随机交叉给两个子代.在变异操作上,当个体满足变异条件时,在候选集中随机选择未在推荐列表中的项目替换对应位置的项目,遗传变异操作如图3所示,其中数字代表推荐项目的编号.具体步骤如下:
图3 个体交叉变异操作Fig.3 Crossover and mutation operation
Step1.设置交叉概率、变异概率.
Step2.符合交叉条件进入交叉操作;
Step2.1.采用锦标赛机制选择2个父代个体;
Step2.2.保留父代相同项目给子代,提取不同项目;
Step2.3.不同项目按0.5的概率分配给两个子代,交叉过程结束;
Step3.个体中项目位置符合变异条件,进入变异;
Step3.1.从候选集中随机选择项目,且该项目不在待变异个体中.
Step3.2.新项目替换变异个体对应项目,变异过程结束.
2.4 推荐方案选择策略
多目标优化过程结束得到PF后,进一步采用选择策略将Pareto解集划分成不同偏好属性的子集,从而降低推荐系统的决策负担.本算法利用隐式偏好,将推荐方案划分成准确性占优(IP-MRS-a)、多样性占优(IP-MRS-d)和目标平衡(IP-MRS-k)3个方案集.具体划分步骤如下:
Step3.对每个个体的3个C_dis排序,最小C_dis对应的区域即为该个体所属集合;
Step4.输出3个集合.
2.5 算法复杂度
算法包含3个阶段,其复杂度从3方面分析.候选集产生阶段,假设有m个用户n个项目的评分矩阵,目标用户候选集长度为K,算法时间复杂度为O(mn2)+O(clog2K);多目标优化阶段,2个目标,3个隐式偏好,N个种群,g次迭代,算法时间复杂度为O(6N2g);推荐方案选择阶段,假设有d个PF个体,3个隐式偏好,算法时间复杂度为O(3dlog2d).算法总体时间复杂度为3个阶段的总和.
3.1 实验准备
本文算法采用Python语言编程实现.实验运行环境为macOS Big Sur,处理器CPU:Intel(R)Core(TM)i5 @2.7GHz,内存8GB.本文采用Movielens 100K和Netflix两个数据集进行实验.Movielens 100K数据集包含了943个用户对1682个电影共计10万条评分,评分区间为[1,5].Netflix数据集中随机选择10000名用户对2700个电影的80万条评分,评分区间为[1,5].两个数据集均随机选择80%的数据作为训练集,剩余20%作为测试集,并从测试集中随机选择20位目标用户进行推荐.
3.2 参数设置
本文实验参数设置见表1.
表1 实验参数设置Table 1 Parameters of experiment
3.3 评价指标
针对推荐结果的评价,本文采用准确率(Precision)、新颖度(Novelty)以及优化目标中的多样性(Diversity)3个指标[2].准确率表示推荐算法满足用户实际兴趣的程度,是评价推荐准确性常用指标.而新颖度则是评价推荐算法挖掘长尾的能力.
(15)
(16)
其中,R(u)为用户u的推荐列表;T(u)为测试集中该用户有过行为的项目;k为项目的流行度,即测试数据集中有多少用户对该项目发生了行为,U为测试数据集中用户数量.上述指标数值越大表明该项性能好.
3.4 实验结果
3.4.1 推荐性能有效性
为验证算法性能及有效性,实验结果将本算法与Item-based协同过滤推荐算法(Item-based Collaborative Filtering,ItemCF)[28]和基于NSGA-II的多目标推荐算法MOEA-RS[24]进行对比.ItemCF算法与本文IP-MRS算法采用相同的基于项目相似度预测目标用户兴趣度,以兴趣度排序给用户推荐TOP-10的项目.与其比较的目的是验证本文算法在同时优化两个推荐目标上的性能.MOEA-RS算法是无偏好的多目标推荐算法,其最终输出的PF分布在整个目标空间区域,与其比较验证IP-MRS能否有效降低推荐系统的决策负担.本文算法将推荐结果分为准确性占优(IP-MRS-a)、多样性占优(IP-MRS-d)和目标平衡(IP-MRS-k)3个结果进行呈现.
实验结果分两部分对推荐有效性进行呈现和分析.首先两个数据集各选择6位目标用户对IP-MRS前沿图和各算法推荐性能详细情况进行分析,然后对两个数据集20位目标用户总体推荐性能进行分析.
图4和图5分别展示了Movielens数据和Netflix数据集中6位目标用户IP-MRS算法最终推荐方案的PF分布情况.
图4 Movielens数据集中6位目标用户IP-MS算法帕累托前沿图Fig.4 Pareto front of six users in movielens dataset by IP-MS algorithm
图5 Netflix数据集中6位目标用户IP-MS算法帕累托前沿图Fig.5 Pareto front of six users in Netflix dataset by IP-MS algorithm
实心圆点为非支配解,虚线框为不同偏好区域.从解集的分布情况可以看出,本算法可以有效地将推荐方案收敛于极值区域和膝区域.在决策者偏好未知的情况下,作为隐式偏好的此3区域可以为最终决策提供帮助.从各目标用户推荐结果分布来看,不同区域解的分布数量不均匀,形态不规则.这是由于推荐算法是根据用户历史行为进行预测和决策,而用户历史行为信息的稀疏性和不规则性导致候选集中各项目间的相似度和预测评分差异性较大,这是最终解集分布不均匀的原因之一.同时,候选集作为多目标优化的策略搜索依据,其数量的限制,导致解的搜索空间有限,这也是造成上述问题的原因.偏好区域范围r的取值理论上可以影响解围绕偏好点的聚集性,但据上述分析,在推荐问题的实际场景中是否能达到同样性能并不确定,且本文探讨算法能否有效引导解集分布在偏好区域,故不对r的取值范围进行分析论证.
为进一步验证在隐式偏好区域内的推荐方案的有效性,表2～表7分别展示了不同算法两个数据集中6位目标用户上的推荐性能,图6、图7展示了不同算法在两个数据集20位用户上的平均性能表现.其中MOEA-RS的结果是所有PF个体性能的平均值,IP-MRS-a、IP-MRS-d、IP-MRS-k的结果是对应偏好区内PF个体性能的平均值.从图6可见,在Movielens数据集上,IP-MRS在推荐准确度上略低于ItemCF算法(平均降低18.3%,最少降低8.4%),而多样性指标得到了较大提升(平均提升38.0%,最高提升47.2%),新颖度指标表现也更好(平均提升58.6%,最高提升68.8%).从图7可见,在Netflix数据集上的表现与Movielens基本一致,IP-MRS在推荐准确度上略低于ItemCF算法(平均降低15.1%,最少降低7.1%),多样性指标提升明显(平均提升33.4%,最高提升49.1%),新颖度指标表现更为显著(平均提升125.4%,最高提升131.1%).这与ItemCF只关注准确性这单一目标,而多目标推荐算法同时兼顾准确性和多样性两个目标有关.说明本文算法在保证推荐准确性的同时提升推荐的多样性和新颖度.在多目标推荐算法中,IP-MRS在准确率、多样性和新颖度性能上均高于MOEA-RS.这是因为IP-MRS将更多的搜索资源分配给了偏好区域,而MOEA-RS则在整个目标区域进行搜索,因此在实验中IP-MRS推荐性能表现更为优异.从3个偏好区域的推荐性能对比看出,不同的偏好区域表现出了其应有的特性.如IP-MRS-a推荐准确率高,IP-MRS-d的多样性和新颖度好,而IP-MRS-k具有最佳平衡性能.
表2 Movielens数据集中6位目标用户各算法推荐准确率Table 2 Precision by different algorithms for six users in Movielens dataset
表3 Movielens数据集中6位目标用户各算法推荐多样性Table 3 Diversity by different algorithms for six users in Movielens dataset
表4 Movielens数据集中6位目标用户各算法推荐新颖度Table 4 Novelty by different algorithms for six users in Movielens dataset
表5 Netflix数据集中6位目标用户各算法推荐准确率Table 5 Precision by different algorithms for six users in Netflix dataset
表6 Netflix数据集中6位目标用户各算法推荐多样性Table 6 Diversity by different algorithms for six users in Netflix dataset
表7 Netflix数据集中6位目标用户各算法推荐新颖度Table 7 Novelty by different algorithms for six users in Netflix dataset
图6 Movielens数据集中20位目标用户各算法推荐性能Fig.6 Performance of different algorithms for 20 target users in Movielens dataset
图7 Netflix数据集中20位目标用户各算法推荐性能Fig.7 Performance of different algorithms for 20 target users in Netflix dataset
3.4.2 降低决策负担有效性
多目标推荐算法虽能同时优化准确性和多样性,但其输出的解集数量较多,在决策偏好未知的情况下,不利于推荐系统最终选择.表8、表9分别展示了两个数据集中不同MORS算法最终提供给6位目标用户的推荐方案数量,在偏好区域内的推荐方案数量较大程度低于MOEA-RS.降低推荐方案的数量对于推荐系统最终决策有一定优势.例如当给ID号328的用户进行推荐,MOEA-RS给用户提供了29个推荐列表,而IP-MRS则是给用户提供3大类具有不同偏好属性的推荐模式,每种模式各提供5～8个推荐列表.图8展示了两个数据集中不同MORS给20位用户提供推荐方案数量的平均值,3个偏好区域的IP-MRS提供的推荐方案数量显著低于MOEA-RS,由此降低了推荐系统的决策负担.
表8 Movielens数据集中6位目标用户推荐方案数量Table 8 Number of solutions from 6 users in Movielens dataset
表9 Netflix数据集中6位目标用户推荐方案数量Table 9 Number of solutions from 6 users in Netflix dataset
图8 20位用户推荐方案数量均值Fig.8 Average number of solutions from 20 users
针对传统推荐算法无法兼顾推荐结果的准确性和多样性问题.本文提出了一种基于隐式偏好的多目标推荐算法,将极值点和膝点作为偏好点,利用切比雪夫距离在迭代过程中对其动态标定,以引导个体收敛于隐式偏好区域,得到具有不同偏好的推荐方案.实验结果表明,本算法的推荐结果保证准确率的同时多样性和新颖度得到了有效提升,同时降低了多目标推荐算法的决策复杂度,有效解决了实际应用问题.
猜你喜欢 列表准确性方案 烂脸了急救方案好日子(2022年3期)2022-06-01浅谈如何提高建筑安装工程预算的准确性建材发展导向(2021年10期)2021-07-16学习运用列表法小学生学习指导(中年级)(2021年4期)2021-04-27扩列吧课堂内外(初中版)(2020年5期)2020-06-19定边：一份群众满意的“脱贫答卷” 一种提供借鉴的“扶贫方案”陕西画报(2018年6期)2018-02-25美剧翻译中的“神翻译”:准确性和趣味性的平衡疯狂英语(双语世界)(2016年3期)2016-02-27论股票价格准确性的社会效益管理现代化(2016年5期)2016-01-23列表画树状图各有所长中学生数理化·中考版(2015年10期)2015-09-10超声引导在肾组织活检中的准确性和安全性分析安徽医药(2014年4期)2014-03-20不含3-圈的1-平面图的列表边染色与列表全染色华东师范大学学报（自然科学版）(2014年3期)2014-03-11