融合标签相似度的k近邻Slope One算法

张　鹏，葛小青

(1. 中国科学院 遥感与数字地球研究所，北京 100094；2. 中国科学院大学，北京 100049)



融合标签相似度的k近邻Slope One算法

张鹏1，2，葛小青1

(1. 中国科学院 遥感与数字地球研究所，北京 100094；2. 中国科学院大学，北京 100049)

摘要：Slope One协同过滤算法被广泛应用于个性化推荐系统中。标签是一种描述项目特性的重要形式，针对Slope One算法推荐精度不足的问题，将标签信息融合到Slope One算法当中。同时参考k近邻算法思想，选取阈值过滤后的k近邻项目参与平均评分偏差计算，提高计算效率的同时增加预测精度。使用评分相似度和标签相似度作为权重修正线性回归模型。通过线性加权融合预测结果，进一步提升推荐质量。将算法应用于MovieLens数据集，与传统加权Slope One算法相比，平均绝对偏差下降4.8%，召回率和准确率分别提高32.1%和26.3%。

关键词：协同过滤；推荐系统；标签相似度；k近邻；Slope One算法

0引言

随着信息资源的超载式增长，用户对个性化服务需求逐步提高，推荐系统在电子商务、社交网络和新闻推荐等领域已成为不可或缺的技术[1]。个性化推荐系统中，协同过滤(collaborative filtering，CF)是应用最成功、最广泛的技术之一[2]，主要包括基于内存(memory-based)的协同过滤推荐和基于模型(model-based)的协同过滤推荐[3]。而基于内存的协同过滤又包括基于用户的协同过滤算法[4]和基于项目的协同过滤算法[5]。为了提高效率及实时性，LEMIRE等[6]提出了基于简单线性回归模型的Slope One算法。因其参数更新查询速度快、维护扩展性好、抗冷启动和数据稀疏能力强等特点，在推荐系统领域得到了广泛应用。

Slope One算法本质是基于项目的协同过滤推荐，然而它并未深入挖掘项目之间的内在联系，在部分项目的预测上会产生较大误差。杜茂康[7]等以项目间相似度作为权重计算项目评分偏差。WANG[8]等对Slope One算法填充后的评分矩阵使用基于用户的协同过滤算法进行评分预测。林德军等[9]使用奇异值分解(singular value decomposition，SVD)对项目-评分矩阵进行填充后，使用动态近邻项目进行Slope One评分预测。

标签是一种描述项目特性的重要形式，为信息检索和个性化推荐提供了重要数据来源，丰富了推荐方法的多样性。TSO-SUTTER等[10]将标签数据与项目评分矩阵相结合，扩展了传统协同过滤算法。GUAN等[11]利用标签信息提出了一种基于图的推荐学习算法。SEN等[12]根据用户标签喜好建立了贝叶斯模型预测用户项目喜好。

上述论文或单从评分角度[7-9]或单从标签角度[10-12]考虑推荐问题，忽略了项目的综合特异性，很难取得较高准确度。对推荐模型进行算法融合是当今推荐系统领域的一种研究趋势[13]，本文通过预先设置的相似度阈值对项目进行筛选，将k近邻协同过滤算法(k-nearest neighbor algorithm，KNN)和Slope One算法进行融合，分别使用评分相似度和标签相似度作为权重修正预测评分，最后通过线性加权融合2种预测结果，进一步提高推荐精度。

1相关研究

1.1Slope One算法模型

Slope One算法是一种经典评分预测算法，是对一元线性模型f(v)=v+b的线性回归预测[6]，v为用户u对项目i的评分，b为项目j相对于项目i的平均评分偏差。Slope One算法原理如图1所示，用户c对项目j的预测评分为rc,j=rc,i+(ra,j-ra,i)=2+(1.5-1)=2.5。

定义同时对项目j和项目i完成评分的集合为Sj,i(χ)，card(x)表示集合x中的元素个数。则目标项目j相对于项目i的平均评分偏差devj,i为

(1)

对所有预测结果取平均值，得到用户u对项目j的预测评分为

(2)

(2)式中，Rj表示与目标项目j同时被评分的项目集合。

图1　Slope One算法原理Fig.1　Basis of Slope One algorithm

Weighted Slope One算法是Slope One算法应用最广泛的实现方式。由于不同用户数量平均得到的devj,i置信度不同，故将用户数量作为项目评分偏差的权重，定义同时评价过项目j和项目i的用户数量为cj,i，得到最终预测评分[6]为

(3)

1.2Tag Genome模型

基因标签组(TagGenome)模型是VIG等[14]提出的一种与传统布尔型标签不同的数据结构。TagGenome模型使用监督学习方法，建立了广义线性分层回归模型，计算得到一个0-1之间的连续型数值，用以表示标签和项目的关联强度。整个训练过程如图2所示[14]。

图2　计算标签基因组的过程Fig.2　Process of calculating Tag Genome

TagGenome模型从项目内容、项目属性、用户标签使用情况及用户评分、评论中提取特征作为后续学习模型的输入，主要特征[14]见表1。

表1　Tag Genome模型主要特征

采用(4)式的sigmoidal函数对特征值的加权结果进行变换，使得最终结果为0-1间的连续型数，达到归一化效果。

(4)

最终标签和项目的相关性表示为

(5)

一旦通过模型拟合计算出相关参数，上述模型就可以用来预测任意项目的标签基因组组成。

1.3相似度计算

相似度计算是协同过滤中的关键步骤，k近邻算法中近邻项目集合的选择通常依赖于相似性的度量。常用的相似性计算方法有：

1)修正的余弦相似性[4]：

(6)

2)相关相似性(Pearson相关性系数)[5]：

(7)

3)标签相似性[14]：

tsim(i,j)=

(8)(8)式中，wt=log(popularity(t))/doc-freq(t)，popularity(t)表示所有使用过标签t的用户数量，代表标签t的流行度，doc-freq(t)表示所有与标签t相关性系数大于0.5的项目的个数，反应了标签t的特异性。

2本文算法

传统SlopeOne算法推荐精度较低。k近邻协同过滤算法抗稀疏能力差且无法给出推荐理由。基于标签的推荐可信度更高，但目前在推荐系统中应用较少。为克服上述弊端，本文提出了融合标签相似度的k近邻SlopeOne算法，通过权值修正、阈值过滤、近邻选择、算法融合等方法提高算法准确性，取得更好的推荐效果。

2.1融合标签相似度的k近邻Slope One算法

1)阈值过滤：

SlopeOne算法忽略了项目间的差异性，有时会选取与目标项目完全无关的项目参与计算，降低了预测精度。为了避免将无关项目纳入计算，我们设置了评分相似度阈值λr和标签相似度阈值λt，只有相似度大于阈值的项目才并入计算，从而过滤掉不相关项目，在减少计算量的同时提高计算精度。

2)近邻选择：

除了使用阈值对无关项目进行过滤外，同时参考k近邻协同过滤算法思想，通过相似度近邻选择的方法进一步筛选相关项目。定义rsim(i,j)为使用(6)式计算的评分相似度，则评分相似度大于阈值λr且最大的k近邻项目形成的集合可定义为

定义tsim(i,j)为使用(8)式计算的标签相似度，则标签相似度大于阈值λt且最大的k近邻项目形成的集合可定义为

3)权重修正：

利用项目-评分矩阵和项目-标签基因组矩阵计算相似度，分别使用评分相似度和标签相似度修正预测评分结果。

使用评分相似度计算的修正结果为

Prwso(u)j=

(9)

我们将评分数量cj,i融合到评分相似度权重中，是由于这种融合方法计算结果更加精确[13]。

使用标签相似度计算的修正结果为

(10)

4)算法加权融合:

将2种预测方法进行加权融合，进一步提高推荐质量。最终所使用的预测评分公式为

(11)

(11)式中，参数α起到了加权调和的目的，当α为0时，公式(11)退化为基于评分相似度的k近邻SlopeOne算法[7]，当α为1时，公式(11)退化为基于标签相似度的k近邻SlopeOne算法。α需通过仿真实验确定最终取值大小。

2.2融合标签相似度的k近邻Slope One算法步骤

在本文算法当中，首先分别计算评分相似度和标签相似度，然后利用2种相似度作为测度，分别选取与目标项目相似度最大的k个已评分项目，求得项目平均评分偏差，以相似度作为权重进行SlopeOne算法评分预测，最后对2种算法所得结果进行加权融合得到最终预测评分，进行TOP-N推荐。具体的推荐过程如下。

输入：用户-项目评分矩阵Rm×n，标签-项目基因组矩阵Th×n，当前活跃用户u，目标项目j，评分相似度阈值λr，标签相似度阈值λt，最近邻项目数k，推荐列表长度N,融合权重α。

输出：长度为N的推荐列表。

步骤1对于项目-评分矩阵Rm×n，使用(6)式计算项目间的评分相似性矩阵RSn×n；

步骤2对于项目-基因组矩阵Th×n，h为标签个数，使用(8)式计算项目间的相似性矩阵TSn×n；

步骤3从用户已评分项目中，选择评分相似度大于λr且最大的k个项目作为St(uj)，选择标签相似度大于λt且最大的k个项目作为Sr(uj)；

步骤4利用(1)式计算St(uj)与Sr(uj)中的项目与目标项目j的评分偏差devj,i；

步骤5利用(11)式计算对项目j的预测评分，若St(uj)为空则取α为1，若Sr(uj)为空则取α为0，若St(uj)与Sr(uj)都为空，则以用户u对其他项目的评分均值作为预测评分；若用户u未对任何项目进行过评分，则以项目j的平均评分作为预测评分；

步骤6从预测评分中选择最大的N个，形成推荐列表，推荐给用户u。

2.3算法复杂度分析

算法复杂度是评定算法优劣的基本标准，直接影响算法实际应用时的效率和性能。本文所描述的融合标签相似度的k近邻SlopeOne算法的计算时间由离线处理和线上推荐两部分组成。

线下离线计算主要包括计算项目-标签基因组矩阵，计算项目间的评分相似度矩阵和计算项目间的标签基因组相似度矩阵3部分。①计算项目-标签基因组矩阵虽然需要进行深度学习的复杂迭代计算，但是项目的性质一般比较稳定，仅需定期离线计算即可，并不会影响推荐速度[15]。②假设整个推荐系统中，用户数量为m，项目数量为n。计算项目间的评分相似度矩阵时间复杂度为O(n2m)。③项目间的标签基因组相似度矩阵时间复杂度为O(n2m)。

线上实时更新仅需针对当前用户，使用候选近邻进行评分预测即可，时间复杂度为O(kmn)。

综上所述，算法的时间复杂度为O(n2m+ n2m+kmn)=O(n2m)。

在空间复杂度上，算法主要存储项目-标签基因组矩阵的复杂度为O(nh)，项目-评分矩阵的复杂度为O(nm)，项目标签基因组相似度矩阵的复杂度为O(n2)和项目评分相似度矩阵的复杂度为O(n2)，故算法的总的空间复杂度为O(nh+nm+n2+ n2)。在用户数量m远大于项目数量n的系统中，近似等于O(nm)，在项目数量n远大于用户数量m的系统中，近似等于O(n2)。

3实验结果与分析

3.1实验数据集

实验部分采用GroupLens研究小组(http:∥www.grouplens.org)提供的电影评分数据集作为算法测试数据集。MovieLens100k数据集[16]，提供了来自943位用户对1 682部电影的10万评分记录。评分等级采用5分制策略，代表偏爱程度由低到高。数据稀疏度(未知评分在数据集中所占比例)为1-100000/(943×1682)=0.937 0。

同时，从MovieTuner提供的MovieLensTagGenome数据集[17]中，抽取MovieLens100k数据集对应的1 682部电影的标签基因组信息(共1 128个标签)形成项目-标签基因组矩阵。

3.2推荐质量评价指标

评价推荐系统常用度量标准有统计准确度和决策支持度两类[5]。其中统计准确度中最常用的方法为预测准确度和分类准确度。

为评估算法预测评分的准确性，本文采用预测评分和实际评分的平均绝对偏差[5](meanabsoluteerror，MAE)作为预测准确度评价标准。MAE值和推荐精准程度之间呈反比关系，MAE值越小，推荐越准确。定义pi为对项目i的预测评分，qi为对项目i的实际评分，Nt为测试数据集的大小，则MAE可表示为

(12)

TOP-N推荐中最常用的分类准确度方法有召回率和准确率2种[18]。

召回率反映了待推荐项目被推荐的比率为

(13)

(13)式中：R(u)为被推荐项目集合；T(u)为用户在测试集上的行为列表。

准确率表示算法推荐成功的比率为

(14)

3.3实验结果

将MovieLens100k数据集按照80%和20%的比例划分为训练数据集和测试数据集两部分。为降低随机性对预测结果的干扰，将数据平均分为5份，使用5折线交叉验证(5-foldcrossvalidation)的方法[18]进行评分预测，取5次结果均值作为测试结果。

3.3.1融合参数α对算法的影响

为验证加权参数α对实验结果的影响，我们固定近邻项数量为k=10，k=20，k=40，k=80，使融合权重系数α从0增加至1.0，间隔为0.1，实验结果如图3所示。从图3中不难分析出，对于同一近邻数，平均绝对偏差MAE随着α先下降后上升，在0.3-0.6达到最小值。同时也证明了融合算法比单一使用项目相似度评分相似度的k近邻SlopeOne算法(α=1.0)或基于标签相似度的k近邻SlopeOne算法(α=0.0)的推荐质量都要高。

3.3.2近邻数量k对算法的影响

为验证近邻项目数量对实验结果的影响，我们固定融合参数为α=0.3，α=0.4，α=0.5，α=0.6，使最近邻数k从10增加至100，间隔为10，实验结果如图4所示。从图4中我们不难分析出，在最近邻数从5增加至20时，MAE值不断减小，推荐精度不断提高，在k=20时取得最小值，此后随着k增大，引入计算的项目和目标项目的相关性逐渐减小，噪声增加，MAE值曲线平缓增加。4条曲线当中，α=0.4，k=20取得最小MAE值，因此后续采用此参数进行对比试验。

图3　本文算法在不同α下MAE的对比Fig.3　Effect of α on MAE

图4　本文算法在不同近邻数k下MAE的对比Fig.4　Effect of k on MAE

在实际推荐系统中应根据系统中项目数量，按照上述方法选取融合参数α和近邻数k，确保将实际相似项目纳入计算，达到最佳推荐效果。

3.3.3预测准确度分析

为进一步验证算法预测准确度，我们采用对比试验的方法，结果如图5所示。其中Item-CF代表基于项目的协同过滤算法[5]，WSO代表WeightedSlopeOne算法[6]，KNNSO代表基于近邻项目的SlopeOne算法[7]，SVDSO代表SVDSlopeOne算法[9]，HSO代表本文的HybridSlopeOne算法。

图5　不同推荐算法MAE比较Fig.5　Comparisons of MAE between different algorithms

分析图5可知，任意最近邻数目下，HSO算法都取得了最小MAE值，与传统WSO算法相比下降4.8%，与其他算法相比下降2.33%—5.33%。并且k=20时就达到最小MAE值，比其他算法取得最小MAE所需的最近邻数量减少20—60个。

3.3.4分类准确度分析

不同算法召回率的比较结果如图6所示，传统WSO算法召回率最低，HSO算法召回率比其他4种算法的召回率有21.1%—41.7%的提高，平均情况下召回率比传统WSO算法有32.1%的提高。并且召回率随推荐列表长度的增加，提升速度更加明显。

图6　不同算法的召回率比较Fig.6　Comparison of the recall of different algorithms

不同算法准确率比较结果如图7所示，HSO算法准确率比其他4种算法准确率提高6.7%—26.9%，平均情况下准确率比传统WSO算法有26.3%的提高。并且准确率与其他算法相比，受推荐列表长度的影响更小。

图7　不同算法的准确度比较Fig.7　Comparison of the precision of different algorithms

上述结果表明，融合标签相似度的k近邻SlopeOne算法较传统加权SlopeOne算法有效提高了分类准确度，同时适应性也得到大幅度增强。

3.3.5算法运行时间分析

为分析算法运行时间是否符合预期，验证前文对算法复杂度的分析结果，采用java语言实现该算法，并在处理器为酷睿I5、主频3.1GHz、内存4GByte的电脑上求解算例。将5种算法在不同近邻数k下的运行时间进行对比(10次运行取平均值)，对比结果见表2，时间单位为秒。

表2　不同算法运行时间比较

分析表2可知，传统WSO算法与近邻数无关，时间恒定。SVDSO算法由于需要进行SVD矩阵分解因此运行时间最长。Item-CF，KNNSO和HSO3种算法运行时间随近邻数k增加逐步增长。本文提出的算法运行时间与KNNSO算法运行时间相近，与理论时间复杂度分析的结果一致。算法实际运行效率较高，可运用于实际推荐系统中。

4结束语

本文提出的融合标签相似度的k近邻SlopeOne算法同时使用了评分相似度和标签相似度作为权重，考虑了项目之间的内在联系，解决了算法对项目本身针对性不强的问题，增强了算法合理性，针对评分预测问题给出了一种有效的求解思路和方法。最终实验表明，与传统加权SlopeOne算法相比，平均绝对误差MAE值下降4.8%，召回率提高32.1%，准确率提高26.3%，算法运行时间也在合理范围内。加权融合的方法以及对参数调优的讨论，对于推荐系统的实际应用有一定的指导意义。

参考文献：

[1]KARDA A, EBRAHIMI M. A novel approach to hybrid recommendation systems based on association rules mining for content recommendation in asynchronous discussion groups[J].Information Sciences,2013,219:93-110.

[2]RICCI F,ROKACH L,SHAPIRA B,et al.Recommender systems handbook[M].New York:Springer,2011:145-186.[3]许海玲,吴潇,李晓东，等. 互联网推荐系统比较研究[J]. 软件学报, 2009, 20(2): 350-362.

XU Hailing, WU Xiao, LI Xiaodong, et al. Comparison study of internet recommendation system[J].Journal of Software,2009,20(2):350-362.

[4]BREESE J S, HECKERMAN D, KADIE C. Empirical analysis of predictive algorithms for collaborative filtering[C]∥Proceedings of the fourteenth conference on Uncertainty in Artificial Intelligence. Morgan New York: Kaufmann Publishers Inc,1998:43-52.

[5]SARWAR B, KARYPIS G, KONSTAN J, et al. Item-based collaborative filtering recommendation algorithms[C]∥Proceedings of the 10th international conference on World Wide Web (WWW’10). New York: ACM, 2001:285-295.

[6]LEMIRE D, MACLACHLAN A. Slope One predictors for online Rating-based Collaborative Filtering[C]∥SIAM. Proceedings of the SIAM data mining conference. California: SIAM,2005:21-23.

[7]杜茂康,刘苗,李韶华,等．基于邻近项目的Slope One协同过滤算法[J]. 重庆邮电大学学报:自然科学版,2014,26(3):421-426.

DU Maokang, LIU Miao, LI Shaohua, et al. Slope One Collaborative Filtering recommendation algorithm based on neighbor[J]. Journal of Chongqing University of Posts and Telecommunications: Natural Science Edition, 2014, 26(3):421-426.

[8]WANG Pu, YE Hongwu. A personalized recommendation algorithm combining Slope One Scheme and User Based Collaborative Filtering[C]∥IEEE. 2009 International conference on Industrial and Information Systems．Haikou: IEEE Press, 2009:152-154．

[9]林德军,孟祥武. 基于奇异值分解的Slope One算法[J]．新型工业化, 2012, 2(11):12-17.

LIN Dejun, MNEG Xiangwu. Slope One algorithm based on Single Value Decomposition[J] Journal of New Industrialization, 2014, 2(11):12-17.

[10] TSO-SUTTER K H L, MARINHO L B, SCHMIDT-THIEME L. Tag-aware recommender systems by fusion of Collaborative Filtering algorithms[C]∥ACM. Proceedings of ACM symposium on applied computing(SAC’08). New York: ACM Press, 2008: 1995-1999.

[11] GUAN Ziyu,WANG Can,BU Jiajun,et al.Document recommendation in social tagging services[C]∥ACM. Proceedings of the 19th international conference on World Wide Web(WWW’10).New York:ACM,2010:391-400.

[12] SEN S, VIG J, RIEDL J. Tagommenders: connecting users to items through tags[C]∥ACM. Proceedings of the 18th international conference on Word Wide Web (WWW’09). New York: ACM,2009:671-680.

[13] 项亮.推荐系统实践[M].北京:人民邮电出版社,2012

XIANG Liang. Recommendation system practice[M]. Beijing: Posts and Telecom Press, 2012.

[14] VIG J, SEN S, RIEDL J. The Tag Genome: encoding community knowledge to support novel interaction[J]. ACM Transactions on Interactive Intelligent Systems, 2012, 2(3):1-44.

[15] 冷亚军,陆青,张俊岭. 结合类别偏好信息的item-based协同过滤算法[J]. 计算机应用研究, 2016,33(3):669-672.

LENG Yajun, LU Qing, ZHANG Junling. Improved item-based collaborative filtering algorithm combined with class preference information[J].Application Research of Computers, 2016,33(3):669-672.

[16] GroupLens Research Lab. MovieLens datasets[EB/OL].(1998-04) [2016-01-14]. http:∥grouplens.org/datasets/movielens/100k/.

[17] GroupLens Research Lab. MovieLens Tag Genome Dataset[EB/OL].(2012-03) [2016-01-14]. http:∥grouplens.org/datasets/movielens/tag-genome/.

[18] SYMEONIDIS P, NANOPOULOS A, PAPADOPOULOS A N, et al. Collaborative recommender systems: Combining effectiveness and efficiency[J]. Expert Systems with Applications, 2008,34(4):2995-3013.

DOI：10.3979/j.issn.1673-825X.2016.04.012

收稿日期：2016-01-22

修订日期：2016-04-05通讯作者：葛小青gexq@radi.ac.cn

中图分类号：TP391

文献标志码：A

文章编号：1673-825X(2016)04-0518-07

作者简介：

张鹏(1990-)，男，河北邢台人，硕士研究生。研究方向为个性化推荐算法，信号与信息处理，地面站任务规划。E-mail: zhangpengtzy@163.com。

葛小青(1965-)，男，浙江东阳人，高级工程师。研究方向为信号与信息处理，遥感数据处理与系统。E-mail: gexq@radi.ac.cn。

(编辑：魏琴芳)

K-nearest neighbor hybrid Slope One algorithm combined with tag similarity

ZHANG Peng1,2， GE Xiaoqing1

(1. Institute of Remote Sensing and Digital Earth, Chinese Academy of Sciences, Beijing 100094，P. R. China;2. University of Chinese Academy of Sciences, Beijing 100049，P. R. China)

Abstract:Slope One Collaborative Filtering algorithm is widely used in personalized recommendation system. Label is an important form to describe the characteristics of the items. To overcome its deficiency in rating prediction accuracy, this paper proposes a new hybrid algorithm combined with tag information. With reference to the k-nearest neighbor Collaborative Filtering algorithm, we select neighbors of the target item to participate in the calculation of the average rating deviation, which ensures computational efficiency and improves the prediction accuracy. The algorithm defines rating similarities and tag similarities as weight to revise the linear regression model. To achieve further improvement of the recommendation quality, the algorithm adopts a linear weighted fusion method to combine the results. Experimental results on the Movielens data sets indicated that, compared with the traditional weighted Slope One algorithm, mean average absolute error declined 4.8%, while recall rate and precision rate respectively increased 32.1% and 26.3%.

Keywords：collaborative filtering; recommendation system; tag similarity; k-nearest neighbor; Slope One