动态k近邻辅助多权值Slope One算法

马 浩，黄 俊，孔 麟，郑小楠，郭小焕

(重庆邮电大学 通信与信息工程学院，重庆 400065)

0 引 言

随着互联网和信息技术的快速发展，信息过载[1]问题也愈来愈突出。如何在信息海洋中快速发掘用户的兴趣，并向其推荐感兴趣的信息，已成为当前的研究热点。

Daniel Lemire提出了Slope One算法(SO)。该算法简单、高效，在协同过滤算法中得到广泛的应用和发展。但随着数据量的增加，其数据稀疏性、准确性等问题[2]也凸现出来。Slope One算法在进行平均评分偏差计算时，考虑所有共同评分用户的历史评分数据，其中包含大量与目标用户相似度极低的用户群体，难免会引入干扰数据，导致评分预测结果不够精确[3]。因此，部分学者[4]采用k近邻的方法给目标用户选择近邻用户集合。但k值不具有特殊性，无法适应不同的预测场景、人群及物品，使得推荐误差很大。所以，有学者[5,6]提出使用不确定邻居来优化Slope One算法。在传统的Slope One算法当中运用最为广泛的是Daniel Lenmire提出的Weighted Slope One算法(WSO)[7]，考虑到共同评分用户数量的影响，将其作为权重，使得推荐的准确性在一定程度上得到改善。在此基础上，部分学者[8,9]将用户相似度和项目相似度添加为原始公式的权重因子进行改进，一定程度上提高了推荐精度。倪建成等[10]通过引入时间权重，来改善传统Slope One算法数据的稀疏性和实时性差等问题。以上改进大多是针对单一方面进行考虑，往往取得的效果不是很理想。针对以上问题，本文综合多方面考虑，提出一种动态k近邻辅助多权值Slope One算法(dynamick-nearest neighbor-assisted multi-weight Slope One，KTWSO)。

1 相关研究

1.1 传统Slope One算法

传统Slope One算法是一种基于项目的协同过滤算法，其核心思想是利用一元线性模型f(x)=x+b对评分进行线性回归预测。详细定义请参见文献[11]。

Slope One算法基本原理如图1所示。要对用户B的项目J进行评分预测，首先找出用户B的其它评分项目，如项目I。然后找出对项目I和项目J都做出评分的用户集合，如用户A，并计算项目I与项目J之间的平均评分偏差。最后，将用户B对项目I的评分与项目I和项目J之间的平均评分偏差进行计算，得出预测评分。

图1 Slope One算法基本原理

综上，Slope One算法评分预测推荐分为3步：

(1)利用式(1)计算项目之间的评分差的均值，记为平均评分偏差devij

(1)

其中，rui为用户u对项目i的评分，ruj为用户u对项目j的评分，Uij为对项目i与j都产生了评分的用户集合，|Uij| 为集合Uij中用户个数。

(2)利用式(2)，根据目标用户的历史评分和项目间的平均评分偏差，产生目标用户未评分项目的预测评分

(2)

其中，用preui为用户u对项目i的预测评分，I(u)为用户u产生过项目评分，且满足 (i≠j,|Uij|>0) 的项目集合，|I(u)| 为集合I(u) 中的项目个数。

(3)将预测评分进行Top-N排序，对目标用户产生推荐。

1.2 Weighted Slope One算法

传统Slope One算法简单、高效且可扩展。但是在计算项目i与项目j间的平均评分偏差时，没有将不同用户和项目区别对待，导致推荐结果不够理想。如果对项目i和项目j都产生评分的用户数为200，对项目i和项目k都产生评分的用户数为20，显然，产生共同评分的用户数差异会影响平均评分偏差的可靠性。本例中得到的平均评分偏差devij要比devik更精确，所以在进行评分预测时应该赋予devij更高的权重。因此，文献[2]提出了将用户数量作为项目间平均评分偏差的权重的Weighted Slope One算法，如式(3)所示

(3)

1.3 相似度计算方法

相似度计算作为协同过滤算法中关键步骤，在近邻用户的选择中显得尤为重要。常用的几种(用户)相似度计算方法如下所示：

(1)余弦相似度

(4)

其中，rui和rvi分别表示用户u和v对项目i的评分，Iuv为u和用户v共同评分的项目集。

(2)修正余弦相似度

(5)

(3)Pearson相关系数

(6)

2 本文算法

针对传统Slope One算法和Weighted Slope One算法在计算项目平均评分偏差时，忽略了用户之间的内在关系，无差别地使用所有用户的数据可能会引入大量不相关的评分数据，从而导致得到的平均评分偏差误差大并影响推荐质量，以及采用单一加权方式来提高推荐精度上存在的不足等问题，本文先采用一种改进的k近邻方法，去除部分不相关的干扰用户，以过滤掉干扰的评分数据。然后在评分预测时，从用户相似度、用户综合信任度和项目相似度三方面综合考虑，提出一种动态k近邻辅助多权值Slope One算法，以提高推荐的准确率。

2.1 改进的动态k近邻方法

2.1.1 改进的相似度计算

k近邻的选择取决于相似度计算，本文选择Pearson相关系数，如式(6)所示，其定义请参见文献[9]。

假设用户共同评分项目集合很小，且它们的评分也很接近，就会得到较高的相似度。但这是不可靠的，因为集合基数太小，不具普遍性。因此，可以考虑将用户间共同评分的项目数作为一个平衡因子Nuv，来改善用户评分数据稀疏的问题，如式(7)所示

(7)

其中，|Iuv| 为用户u和v共同评价的项目数，|Iu| 为用户u评分项目数，|Iv| 为用户v评分的项目数。

传统的Pearson相关系数无差别对待所有项目，忽略了热门项目对相似度带来的影响。热门项目往往反映的是大众的喜好，并不能完全代表个人的偏好，反之，若两个用户都对某个冷门项目产生评分，则更能反映用户间的相似性。因此本文引入热门项目惩罚因子wi，如式(8)所示

(8)

其中，Ni为所有用户中喜欢用户u和用户v共同评价的项目i的用户数。

而在实际生活中，用户的兴趣不会保持一成不变，用户近期的评分记录相对于比较久远的评分记录对预测应该有着更重的权值。因此，本文采用非线性指数遗忘函数来刻画用户兴趣随时间的变化，其值保持在(0,1]之间。并定义兴趣稳定期概念为用户兴趣保持不变的时间周期，用于解决用户兴趣在较小的时间窗内保持不变的问题，使得用户兴趣的衰减呈现梯度指数衰减，更加符合实际情况，如式(9)所示

(9)

其中，t=tnow-tui，tnow为当前时间，tui为用户u对项目i的产生评分时间，Ts为兴趣稳定期。

综上，结合平衡因子、热门项目惩罚因子和时间权重，改进的Pearson相关系数如式(10)所示

(10)

2.1.2 阈值过滤

传统的k近邻算法固定k值不具有特殊性，无法适应不同的预测场景、人群等。为了提高预测精度，本文在采用改进的Pearson相关系数度量用户相似度的情况下，设置一个评分相似度阈值λ，针对不同的目标用户筛选出动态k近邻用户集。即在与目标用户产生共同评分项目的用户集中，只有大于相似度阈值λ的用户，才会被选入目标用户的动态k近邻用户集合参与评分预测，并将该集合定义为rknn(u)，如式(11)所示

rknn(u)={v|simr(u,v)≥λ}

(11)

2.2 加权因子

2.2.1 改进的用户相似度

采用上章节改进的Pearson相关系数，如式(10)所示，将它作为权重加权到Slope One算法中，以考虑用户间相似性的影响。

2.2.2 用户综合信任度

用户信任度可以作为评分预测的一个重要依据。在生活中，一个值得信任的人提供的信息就具有更高的可靠性，同理，在Slope One算法中，也可以运用这种思维。具有高信任度的用户对某些项目产生的历史评分将具有更高的可信性和参考价值，反之亦然。因此，本文提出一种用户综合信任度，包含用户活跃度和评分公正度两方面。事实上，并非所有的用户都积极参与项目的评分，这就会出现部分用户的评分数量较多，而另外一部分用户评分数量较少的情况，显然我们更愿意去信任那些评分比较积极的用户。因此，我们可以采用用户的项目评分数去衡量用户活跃度。当用户的项目评价数越多，其活跃度越高，反之越低。但是仅通过用户活跃度去衡量某个用户的信任度是不够的，因为某些用户可能存在随意或者恶意评分的情况。因此，需要考虑用户对项目的评分客观公正程度。本文采用用户对项目的评分与其平均评分差值作为衡量用户评分公正度的标准，当这差值越大，其评分公正度越小，反之越大。

用户的活跃度Au如式(12)所示，其值保持在(0,1]之间

(12)

用户的公正度Fu如式(13)所示，其值保持在(0,1]之间

(13)

结合上述两个因子，用户综合信任度T(u) 如式(14)所示

T(u)=Au*Fu

(14)

对于某个用户来说，他的评分数量越多而且评分具有越高可靠性，就越具有参考价值，赋予越高的权重。

2.2.3 改进项目相似度

Weighted Slope One算法在衡量项目间内在联系的时候，考虑了两个项目共同产生评分的用户数量的影响。因此，在评分数据稀疏情况下，针对Pearson相关系数准确度不高的问题，可以结合Weighted Slope One算法的思想，加权项目间共同评分的用户数来进行改进，如式(15)所示

(15)

其中，Uij表示对项目i和项目j共同评分的用户集合，|Uij| 表示该集合中用户的个数，|Ui| 表示对项目i评分的用户数，|Uj| 表示对项目j评分的用户数。

综合多个方面进行考虑，可以有效解决单因素加权改进的不足。

2.3 动态k近邻辅助多权值Slope One算法描述

(16)

(17)

最后，将生成的预测评分，进行Top-N推荐。具体过程如下：

输入：用户-项目评分矩阵Rm×n，目标用户u，目标项目j，用户相似度阈值λ，兴趣稳定期Ts，推荐长度N。

输出：N个推荐项目。

步骤1 根据评分矩阵Rm×n，使用改进的相似度计算式(10)计算用户间相似度矩阵Sm×m。

步骤2 将其他用户与目标用户u进行相似度比较，筛选出相似度值大于λ的用户作为u的动态k近邻用户集合rknn(u)。

步骤3 在集合rknn(u) 中，采用式(16)计算目标项目j与其它项目间的平均评分偏差。

步骤4 通过式(17)为目标项目j生成预测评分。若用户u的rknn(u) 集合为空，则以u对其它项目的评分均值作为预测评分，若u未产生过任何评分，则以项目j的评分均值作为预测评分。

步骤5 将产生的预测评分进行排序，并取评分较高的N个项目生成推荐列表。

3 实验结果与分析

3.1 实验数据集

本文实验采用Grouplens提供的MovieLens数据集[12]。MovieLens数据集包含大量用户的电影的评分数据，以及电影元数据信息和用户属性信息等。其中，数据集MovieLens 100k记录了943个用户在1682部电影上产生的 100 000 条评分记录，评分范围由1到5，评分的高低反映了对电影的喜爱程度。本实验随机选取100 k总数据集的80%作为训练集，余下的20%用作测试集。

3.2 度量标准

本文采用实际评分和预测评分的平均绝对误差(mean absolute error，MAE)来衡量算法预测评分的准确性。MAE的值越高，预测评分的准确性越低，反之亦然。MAE如式(18)所示

(18)

其中，pi和qi分别表示项目i的预测评分和实际评分，N为测试集中预测项目的数量。

3.3 实验结果与分析

本文实验分为两个部分：一是参数的选择，包括用户相似度阈值λ，兴趣稳定期Ts；二是进行算法对比性实验，验证改进的有效性。

3.3.1 参数分析实验结果

(1)首先进行兴趣稳定期Ts的选择实验。由于改进的k近邻方法中涉及到用户相似度阈值λ和兴趣稳定期Ts那个参数的选择，我们先去掉相似度阈值这一参数，然后采用传统的k近邻算法中选择式(10)来进行用户相似度的计算，最后将产生的k近邻用户集拿去进行平均评分偏差的计算，定义为改进k近邻Slope One算法(improved k-nearest neighbor Slope One，KSO)。

分别取近邻k值为10、20、30与不同取值的兴趣稳定期来进行实验。由图2可知，在用户兴趣稳定期Ts为30的情况下，MAE总能取到最优值，因此我们选择Ts=30作为最佳的兴趣稳定期。

图2 兴趣稳定期对MAE的影响

(2)进行用户相似度阈值的选择实验。如果将相似度阈值设置得太低，就会引入过多的干扰数据参与到评分预测当中，势必会影响推荐的准确性，同理，如果将相似度阈值设置的太高，得到的用户近邻集合就会太小，推荐的精度也不会太理想。因此，从这两方面考虑，选取0.1到0.8作为用户相似度阈值分别进行实验。由图3可知，在相似度阈值为0.3时，可以取得最优的MAE值。

图3 λ对MAE的影响

综上，分别取λ=0.3和Ts=30作为本实验的用户相似度阈值和兴趣稳定期。

3.3.2 算法对比实验结果

(1)首先，比较本文第二章中的两个改进部分，以验证改进的有效性。

将数据集MovieLens 100k通过5折线交叉法，随机分成5等份，轮流取其中4份作为训练集，取剩下的1份作为测试集。然后将2.1节改进的动态k近邻方法与Slope One算法结合，定义为动态k近邻Slope One算法(dynamic k-nearest neighbor Slope One，KTSO)，并与结合2.1节和2.2节提出的动态k近邻辅助多权值Slope One算法进行对比，采用上面分好的数据集，分别执行5次。

实验结果如图4所示，在采用动态k近邻的情况下，结合多权值改进的KTWSO算法的MAE值明显低于仅采用动态k近邻改进的KTSO算法，从而验证了2.2节算法改进的合理性。

图4 KTSO和KTWSO的MAE比较

(2)然后将本文提出的KTWSO算法与SO算法、WSO算法以及文献[5]提出的The K-nearest neighbor Slope One algorithm based on weighted user similarity and user tag算法(KHSO)进行比较，分别进行5组实验，实验结果见表1。

表1 不同算法下的MAE

分别取表中各算法MAE均值作比较，由图5中可知，本文提出的KTWSO算法的MAE值相对于前3种算法分别降低了3%、2%和1%。相对于KHSO算法来说，本文提出的KTWSO算法采用动态k近邻，过滤掉了部分干扰数据，并一定程度上改进了传统K近邻算法无法适应不同的预测场景、人群的问题，同时从用户相似度、用户综合信任度以及项目相似度多方面考虑，进一步提高了评分预测的准确性，达到了更好的推荐效果。

图5 SO、WSO、KHSO和KTWSO的MAE比较

4 结束语

针对传统Slope One算法无差别地使用所有用户评分数据导致评分预测不准确的问题，本文引入动态k近邻的思想来筛选用户的近邻用户集，并从用户兴趣偏移和热门项目方面对相似度计算方法进行改进，一定程度上提高了近邻用户的质量。然后将近邻用户集运用到计算项目平均评分偏差中，从而剔除了干扰用户数据并提高了推荐精度。同时，本文优化的算法将用户相似度、用户综合信任度和项目相似度作为权重因子加权到Slope One算法的评分预测当中，使得推荐的精度进一步提高。未来，我们可以从用户和项目的标签信息考虑，将更多信息纳入算法，以获得更多的改进。