田欢欢,赵文涛,吴 岩,冯婷婷,崔自恒

(河南理工大学 计算机科学与技术学院,河南 焦作 454003)

1 引 言

随着互联网的快速发展,海量信息不断增加.特别在电子商务领域,用户需要花费更多的时间和精力寻找有价值的信息,信息过载问题[1]突出.推荐系统[2]通过分析用户的历史偏好行为,快速准确地推荐高质量的信息,从而提供个性化服务.基于邻域的协同过滤推荐算法[3,4]应用较为广泛,但普遍面临冷启动[5]和稀疏性[6,7]等问题,导致所选邻居的质量以及做出准确预测的能力受到较大影响.

在相似度计算的阶段,大多数代表性的相似度算法[8-12]依赖共同评分集合,计算简单且运行效率较高,但在稀疏数据下相似度计算的准确性较低甚至不可用.为了打破共同评分集合的限制,目前基于评分概率密度提出了一些改进的相似度方法,如BCF[13](Bhattacharyya Coefficient,BCF)和KLCF[14](KL-based Similarity Measure,KLCF),将物品相似度作为权重因子加入到对应的用户相似度计算中,提高了相似度计算的准确性.然而涉及大量的笛卡尔计算,导致较高的时间成本.

在传统的评分预测方法中,若给定用户对近邻物品有评分行为则参与计算,否则过滤掉它们的贡献,这样的预测是直接有效的,但稀疏数据下评分预测的准确性较低.一些改进的评分预测方法,如递归预测算法[15](a Recursive Prediction Algorithm,RPA)和迭代预测算法[16](an Iterative Rating Prediction algorithm,IRP),通过将更多的评分数据加入到预测计算中,一定程度上提升了评分预测的准确性.但其中涉及的参数较多,计算较难实现.

针对数据稀疏导致算法所选邻居的质量以及做出准确预测的能力降低这两个问题,提出新的协同过滤算法.首先,基于模糊集与推荐系统的关联,计算用户的偏好概率,并将其拓展到Vague集,提出基于Vague集的KL散度以衡量物品间相似度.其次,为避免评分数量信息的损失,定义权重因子α并将其加入到KL散度中,进一步提高相似度计算的准确性.最后,提出改进的评分预测公式,放宽传统的评分预测方法中对近邻评分信息的限制,使更多的近邻参与评分预测的贡献,提高预测准确性.

2 相关工作

2.1 相似度方法

传统数值型相似度是一种基于评分值计算用户(物品)相似度的算法.传统结构型相似度仅考虑共同评分集合的数量信息.传统混合型相似度[17]综合考虑评分的数值和结构信息,一定程度上提升了推荐质量.但这些相似度方法都依赖共同评分集合,忽略了非共同评分的作用.在稀疏数据下,相似度计算的准确性较低甚至不可用.

目前许多研究人员分别从不同的角度设计相似度模型,以提高近邻的可靠性.Ahn等人[18]提出使用特定领域含义的相似性度量PIP(Proximity-Importance-Popularity,PIP),由3个因素(接近度、重要度和流行度)的乘积组成.为了简化和标准化PIP模型,Liu等人[11]提出新启发式相似度NHSM,并结合共同评分物品的比例和用户评分偏好,能更好地区分用户间的相似性.然而,这些算法仍然受到共同评分集合的限制,对稀疏数据的适应性较差.为了打破这一约束,从评分概率分布的角度,分别提出线性相似度BCF和混合相似度KLCF,有效提高了相似度计算的准确性,但忽略了邻居可用性的影响且运行成本较高.为实现简单高效的推荐,Bag等人[19]提出一种新的结构型相似度(Related Jaccard,RJaccard),除考虑共同评分项目之外,也强调非共同评分项目数量的重要性.此外,Wang等人[20]提出基于α散度的物品相似度,进一步加入绝对评分数量和共同评分数量.Gazdar等人[12]提出OS(Our Developed Similarity,OS)方法,综合考虑非共同评分数量占比和相对绝对评分差异,更敏感地捕捉评分差异的变化.

尽管针对基于邻域的协同过滤算法中相似度模型的设计展开了大量的研究,但相似度方法在面向数据稀疏时的准确性问题仍然是开放问题.

2.2 评分预测公式

基于加权平均的评分预测公式[21]目前较为常用,除考虑物品间的相似度关系外,进一步加入物品的平均评分来调整预测值.然而,在预测评分的计算中仅加入给定用户对近邻物品有评分行为的项,否则过滤掉它们的贡献.因此在数据稀疏的情况下,预测性能较差.

为了缓解这一问题,Zhang等人[15]提出递归预测算法RPA,递归预测中间值,并将其加入评分预测.基于RPA,进一步提出迭代预测算法IRP[16],利用直接和间接邻居的评分,迭代更新预测评级矩阵.然而,需要设置一个合适的迭代参数来实现稳定状态,导致较高的时间成本.

在基于邻域的协同过滤算法中,进一步提高稀疏数据下评分预测的准确性,仍然是值得深入研究的问题.

3 提出的方法

为缓解数据稀疏问题,首先提出基于Vague集的物品相似度,以提高稀疏数据下相似度计算的准确性.然后提出改进的评分预测方法,进一步提高稀疏数据下评分预测的能力.

3.1 基于Vague集的物品相似度

3.1.1 推荐系统上对模糊集和Vague集的定义

人们对模糊复杂的客观问题做出判断或决策时,往往是不确定的.模糊集理论[22]用于表明不确定的决策信息.同样地,在推荐系统中用户对物品的偏好行为进行决策时往往也是模糊,没有明确界限的.因此基于模糊集和推荐系统的这种关联,首先定义模糊集A,表示任意物品i下对其有评分行为的所有用户表现出的整体偏好程度.

定义1.模糊集.论域X表示对同一物品i有评分行为的所有用户构成的集合,论域X上的模糊集A={(x,μA(x)):x∈X}.

(1)

在实际推荐系统的场景中,每个用户都会受到对应周围环境的影响.即同一个物品对其有评分行为的用户之间相互影响.这种相互影响的关系,使得将会对同一物品进行评分的用户在决策时受到影响,从而表现出一定程度的犹豫.为了更准确地表达推荐系统中的模糊信息,即同时考虑用户偏好行为中的喜欢、不喜欢和犹豫.将以上定义的模糊集A拓展到Vague集[23].

3.1.2 基于Vague集的KL距离

根据模糊集A上每个用户对给定物品i的偏好行为,统计出用户整体对该物品喜欢的概率pA,l和不喜欢的概率pA,d,如式(2)所示.其中,N(X)表示论域X中的用户数量.

(2)

(3)

(4)

其中,Vague集下的用户偏好集合为{l′,d′,h,m},pre′表示集合中任意的元素.

3.1.3 评分数量因子

在上述提出的基于Vague集的KL距离中,由于从用户偏好概率的角度衡量集合间差异程度,参与计算的概率值经过了约分化简的步骤,导致一定程度的评分数量信息受到损失.特别在数据稀疏的情况下,相似度结果容易产生较大误差.为了缓解这一问题,定义评分数量因子α,并将其加入KL距离.

(5)

因此加入评分数量信息后,基于Vague集的KL距离改写为式(6)所示,一定程度上缓解了稀疏数据下评分数量信息的损失,进一步提高相似度计算的准确性.

(6)

(7)

3.2 改进的评分预测方法

在传统的基于物品的预测方法中,严格要求邻居的可用性,即给定用户必须对近邻物品评分,否则不能参与评分预测.由于数据稀疏问题普遍存在,相当数量的邻居不满足这一约束条件,即使这些邻居与目标物品非常相似,这些可能的有价值的贡献也会被过滤掉.

为了缓解这一问题,提出改进的评分预测方法.根据给定用户u是否对近邻集合中的物品评分,将近邻集合中的物品划分为两个子集(N1和N2).首先,将满足条件的近邻物品放在类别N1中.即给定用户对其中任意的物品j都有评分(任意的ruj都是存在的),可以直接参与计算.其次,将不满足条件的近邻物品放在类别N2中.这里任意的ruj都是不存在的,不能直接参与计算.针对这一情况,引入近似替代的原则.在对类别N2中的任意物品j有评分行为的用户集合中,寻找与给定用户最相似的近邻用户v,使用rvj替代未直接给出的ruj,进一步引入sim(u,v)作为权重因子调节这种近似替代所带来的误差.

最终改进的评分预测方法如式(8)所示,通过整合更多近邻的评分信息提高稀疏数据下评分预测的能力.

(8)

其中,sim(u,v)与式(7)中sim(i,j)的计算原理相同,不再赘述.

3.3 算法实现

最终面向稀疏数据的物品相似度和评分预测算法(VAGUE)的详细实现过程如算法1所示.

算法1.面向稀疏数据的物品相似度和评分预测算法

输入:用户-物品评分表(用户数为m,物品数为N.)

输出:评分预测结果值

//步骤1.基于Vague集的物品相似度计算

1. fori←1 toNdo

2. 根据式(1)和式(2)计算模糊集A(即对应物品i)下用户整体的偏好概率

4. forj←1 toNdo

5. 将式(6)代入式(7)计算物品间相似度

在单因素试验基础上，确定百香果汁添加量、胡萝卜汁添加量、白砂糖添加量的最佳值，每个因素取3个适宜的水平，进行三因素三水平正交试验，即采用L9（34）正交试验对百香果胡萝卜复合型酸奶的配方进行筛选，以确定产品的最佳工艺配方。根据产品的组织形态、口感和风味等指标进行综合评分，参照了贾娟等人[10]在胡萝卜火龙果混合酸奶的感官评分标准，从而根据胡萝卜百香果复合酸奶所呈现的状态进行感官评分。

6. end

7. end

//步骤2.改进的评分预测计算(测试集中当前用户u评分的物品数为T,当前物品i的近邻集合为S.)

8. foru←1 toMdo

9. fori←1 toTdo

10. forj←1 toSdo

11. 如果ruj存在,则根据子集N1计算

12. 否则,根据子集N2计算

14. end

15. end

16. end

4 实 验

为验证提出的VAGUE模型的有效性,选择8种代表性的协同过滤算法作为对比,依次为SPCC[8]、JMSD[10]、NHSM[11]、BCF[13]、KLCF[14]、α-CF[20]、RJMSD[19]和OS[12].

4.1 数据准备

实验选择两个公开常用的数据集,分别是ML-100K和ML-1M.表1展示了两个数据集在用户、物品、评分数量和稀疏度方面的信息.

表1 数据集属性Table 1 Datasets properties

4.2 评估指标

首先使用平均绝对误差(Mean Absolute Error,MAE)和均方根误差(Root Mean Squared Error,RMSE)衡量算法的预测准确性[24],公式如式(9)、式(10)所示.

(9)

(10)

其中rui、pui分别表示实际评分和预测评分,n为算法执行次数.

其次,使用综合评价指标(F1-value)衡量算法的推荐准确性[25],同时考虑精确率(Precision)和召回率(Recall),公式如下所示.

(11)

(12)

(13)

其中,Ipr和Iar分别是预测推荐列表和测试集中的实际推荐列表.推荐规则为推荐列表中物品的评分须大于该目标用户的平均评分.

除以上两类评价指标外,引入成功预测率(RSP)和完美预测率(RPP)衡量算法的预测能力[26].RSP强调协同过滤算法能做出评分预测的能力,RPP强调做出正确预测的能力,公式如下所示.

(14)

(15)

其中,Ns表示成功预测评分的数量,Np表示正确预测评分的数量,Nt表示数据集中实际需要预测的评分数量.

4.3 实验结果

4.3.1 预测准确性结果分析

图1展示了在ML-100K数据集下,各算法预测准确性的结果.在不同近邻数量下,VAGUE算法的MAE和RMSE值最小.特别是近邻数量小于50时,相比最接近的NHSM算法,在MAE上有平均2.6%的降低,在RMSE上有平均3.2%的降低,预测准确性的优势明显.主要原因是VAGUE算法在计算相似度时,不受共同评分集合的限制,得到的近邻更加可靠.评分预测阶段也能充分利用近邻的评分信息,进一步提高预测值的准确性.同样地,图2展示了在ML-1M数据集下,各算法预测准确性的结果.不同近邻数量下,相比其余算法,VAGUE算法具有最好的预测误差值,当近邻数量为100时,达到最优,此时MAE约为0.712,RMSE约为0.916.

图1 ML-100K数据集上的MAE和RMSEFig.1 MAE and RMSE in ML-100K dataset

图2 ML-1M数据集上的MAE和RMSEFig.2 MAE and RMSE in ML-1M dataset

4.3.2 推荐准确性结果分析

图3展示了在ML-100K和ML-1M数据集下,各算法的推荐准确性结果.随着近邻数量的增加,所有算法的F1-value都逐渐变大.但在不同近邻数量下,VAGUE算法有最好的F1-value.值得注意的是,在图3(a)中,相比其他对比算法,最近提出的BCF和KLCF算法的F1-value有明显改进,与VAGUE算法相比差距小于1%.此外,在图3(b)中,NHSM和JMSD算法的F1-value与VAGUE算法保持最接近的趋势.可能的原因是,在数据集较为稀疏的情况下,共同评分集合的数量信息对推荐结果有重要的影响.

图3 ML-100K和ML-1M数据集上的F1-valueFig.3 F1-value in ML-100K and ML-1M datasets

4.3.3 预测能力结果分析

在ML-100K数据集下,各算法的RSP和RPP结果如图4所示.由图4(a)可知,VAGUE算法的RSP值最高,稳定在0.998左右.其中,BCF和KLCF算法也有较好的RSP值,且两者基本保持一致.主要原因是,基于概率分布的相似度方法,可计算任意物品间的相似度,有利于预测出更多的评分值.由图4(b)可知,在不同近邻数量下,VAGUE算法的NPP值最高,且分布在0.41至0.44之间.其中,NHSM和KLCF算法与VAGUE算法最为接近,NPP值分布在0.37至0.42之间.图5展示了ML-1M数据集下各算法的RSP和RPP结果.由图5(a)中可知,不同近邻数量下,VAGUE算法的RSP值保持0.999左右.其中,随着近邻数量的增加,NHSM、BCF和KLCF算法的RSP值逐渐变大,且与VAGUE算法的差距逐渐缩小.由图5(b)中可知,随着近邻数量的增加,所有算法的RPP值逐渐变大,但VAGUE算法一直保持最优.

图4 ML-100K数据集上的RSP和RPPFig.4 RSP and RPP in ML-100K dataset

图5 ML-1M数据集上的RSP和RPPFig.5 RSP and RPP in ML-1M dataset

5 结 论

本文提出一个新的协同过滤算法,由改进的物品相似度和评分预测方法组成,以提高对稀疏数据的适应性.首先,从用户偏好概率的角度,使用KL散度计算Vague集之间的差异,以衡量对应物品间的相似度.为进一步提高稀疏数据中相似度计算的准确性,定义评分数量因子并将其加入物品相似度.然后,提出改进的评分预测方法,整合更多具有潜在价值的近邻信息,以实现更高的预测精度.在不同稀疏度的数据集上实验,结果验证了本文提出的算法有效提高了稀疏数据中的推荐精度.

未来的工作将进一步探索结合知识图谱的推荐算法,更好地处理数据稀疏的问题.