工程科学与技术   2020, Vol. 52 Issue (1): 198-202
基于数据稀疏性的协同过滤推荐算法改进研究
岳希1,2, 唐聃1,2, 舒红平1,2, 安义文1     
1. 成都信息工程大学 软件工程学院,四川 成都 610225;
2. 软件自动生成与智能服务四川省重点实验室,四川 成都 610225
基金项目: 四川省科技厅人工智能重大专项(2019YFG0398)
摘要: 针对根据用户的活动行为向其推荐感兴趣项目的协同过滤推荐算法,随着用户数量和项目数量增多,用户在单一项目上的活动行为减少,导致推荐质量不佳的问题,本文提出了在数据稀疏的情况下提高推荐质量的优化算法。将基于项目和基于用户的推荐方法相结合,根据用户之间的相似度初步预测用户对项目的评分,再基于项目之间的相似度产生推荐;在填补未评分的空缺值时,将平均值与预测值相结合;在计算相似度时,考虑用户之间共同评分的项目数权重和项目之间被用户共同评分的用户数权重。实验首先对比了几种基本推荐算法的推荐效果以选取较佳的基本算法进行研究,接着将本文提出的优化算法与其他算法进行了对比,最后不同程度地增加数据稀疏性进一步进行对比。结果表明:在优化算法的实验中,本文提出的优化算法一直具有较好的推荐效果;在数据稀疏性改变的实验中,随着数据稀疏度的增大,本文提出的优化算法推荐效果更具有明显优势。
关键词: 稀疏性    推荐算法    相似度    优化    
Research on Improvement of Collaborative Filtering Recommendation Algorithm Based on Data Sparseness
YUE Xi1,2, TANG Dan1,2, SHU Hongping1,2, AN Yiwen1     
1. College of Software Eng.,Chengdu Univ. of Info. Technol., Chengdu 610225, China;
2. Automatic Software Generation and Intelligence Service Key Lab. of Sichuan Province, Chengdu 610225, China
Abstract: According to the users’ activity-behaviors, the collaborative filtering recommendation algorithms recommend the interest items to users. However, as the number of users and items increase, the activity of users on a single item decreases, resulting in poor recommendation quality. To solve this problem, an optimization algorithm to improve the recommendation quality in the case of sparse data was proposed in this paper, which combines the item-based and user-based recommendation algorithm. Firstly, the score of the items was predicted according to the similarity between users preliminary; secondly, the recommendations are got based on similarities between items. The average value was combined with the predicted value when filling unrated vacancy values. The weight of the items that commonly scored by users and the weight of users that commonly scored the same items were considered. In experiment, the recommended effects of several basic recommendations algorithms were firstly compared to select a better basic for deep research. Secondly, the proposed algorithm was compared with other algorithms. Finally, for further comparison the data sparsity to several extents was increased. The experiment results showed that the optimization algorithm proposed in this paper had better recommendation. The experiment of data sparsity changes showed that as the data sparsity increases, the optimization algorithm proposed in this paper has obvious advantages.
Key words: sparsity    recommendation algorithm    similarity    optimization    

大数据时代如何更好地挖掘爆炸性增长的数据,分析这些信息的价值,是目前普遍关注的问题。推荐系统[1-2]通过挖掘大量已知数据分析人们的行为习惯和偏好,提供用户感兴趣的信息并定制业务。

目前国内外研究人员已提出了各种推荐算法,以获得更准确的推荐结果,最常用的算法有基于内容的推荐、基于关联规则的推荐和基于协同过滤的推荐。基于内容的推荐[3]是基于用户的浏览记录,通过对文本内容、属性、标签等信息的分析,向用户推荐新项目,该方法和物品属性息息相关,由于在很多情况下得不到物品特征而存在局限性。基于关联规则的推荐[4-5]是在销售过程中挖掘不同商品之间的关联,向用户推荐新商品,但关联规则的发现非常耗时,随着规则数目的增多,系统会变得复杂和低效。基于协同过滤的推荐[6-8]是通过评分数据描述用户对于商品的爱好,进而对未评分项进行预测评分,该方法因为不用考虑被推荐项目的内容、具有推荐新信息的能力、技术易于实现、能够有效使用其他相似用户的反馈信息等优点而广泛被使用,是推荐系统中最主流的方法。

数据稀疏性是协同过滤推荐算法面临的主要挑战[9-10],为解决稀疏性问题,各学者提出了各种方法。最简单的方法就是采用空缺值填补的方式,将未评分的空缺值设为0、平均值或预估值,但设为0的方式过于粗糙,设为平均值的方法没有考虑用户、项目本身的个性差别,采用预估值进行预估,存在如何给出合理数据的问题,如李小浩[11]将未评分项设定为一个缺省值,但未评分项的值不可能完全相同,因此该方法的可信度不高。也有一些学者提出采用数据挖掘的方法,如李大学等[12]提出采用改进加权朴素贝叶斯方法预测未评分数据,张磊等[13]提出一种基于两层神经网络的推荐算法将稀疏矩阵填充问题转化为特征值向量分类问题,然而这些方法存在局部振荡、学习速度慢、运行成本高等问题。邓爱林等[14]提出先基于项目的方法填补用户评分项并集中评分空值,再在填补后的并集上通过基于用户的方法计算用户间的相似度,该方法解决了传统相似性度量方法存在的弊端,但没有考虑用户共同评分项目数的权重,如两个用户只有1、2个共同评分项,偶然评分相同不能说明具有相似性。罗辛[15]、王威[16]等在相似度计算中引入用户共同评分数目权重,在计算最近邻居时考虑用户间共同评分项目数的影响,但对未评分数据的处理没有做进一步研究。

本文在研究当前各推荐算法的基础上,分析传统协同过滤推荐算法的特点,提出一种新的改进算法。在邓爱林等[14]提出算法的基础上先基于用户的相似度计算填补用户没有活动的空缺项,再基于项目的相似度计算产生推荐,同时在计算相似度时加入罗辛[15]、王威[16]等提出的相似度权重计算方法,以用户共同评分的项目数作为相似性评估的因素,在填补空缺值时将平均值与计算值相结合,以使数据稀疏时空缺值的填补更合理。在MovieLens数据集上,在各种参数情况下对相关算法进行对比实验,尤其是在稀疏度改变时进一步分析和验证。

1 预备知识 1.1 协同过滤推荐算法分类

协同过滤推荐算法分为基于用户的协同过滤推荐和基于项目的协同过滤推荐,前者根据用户和用户之间的相似度产生推荐,后者根据项目和项目之间的相似度产生推荐。在计算相似度时具有代表性的方法有Pearson相关相似性和修正余弦相似性,因此,常用的算法有基于用户的Pearson推荐算法、基于项目的Pearson推荐算法、基于用户的修正余弦推荐算法和基于项目的修正余弦推荐算法,在后续实验中可以看出,Pearson相关相似性优于修正余弦相似性,这里只列出Pearson推荐算法公式用于讨论。

1.2 基本算法

1)基于用户的Pearson推荐算法

供应商uv之间的相似度为:

${{sum}}(u,v) = \frac{{\displaystyle\sum\limits_{i \in {I_{uv}}} {({R_{u,i}} - {{\overline R }_u})({R_{v,i}} - {{\overline R }_v})} }}{{\sqrt {\displaystyle\sum\limits_{i \in {I_{uv}}} {{{({R_{u,i}} - {{\overline R }_u})}^2}} } \sqrt {\displaystyle\sum\limits_{i \in {I_{uv}}} {{{({R_{v,i}} - {{\overline R }_v})}^2}} } }}$ (1)

根据相似度最大的前k个用户产生推荐:

${P_{u,i}} = {\overline R _u} + \frac{{\displaystyle\sum\limits_{n \in {N_k}} {sim(u,n)({R_{n,i}} - {{\overline R }_n})} }}{{\displaystyle\sum\limits_{n \in {N_k}} {sim(u,n)} }}$ (2)

式(1)、(2)中, ${R_{u,i}}$ 为用户u对项目i的评分, ${R_{v,i}}$ 为用户v对项目i的评分, ${\overline R _u}$ 为用户u在所有项目上的平均得分, ${\overline R _v}$ 为用户v在所有项目上的平均得分, ${I_{uv}}$ 为经用户uv共同评分的项目集, ${P_{u,i}}$ 为用户u对项目i的评分, ${N_k}$ 为与用户u最相似的前k个用户。

2)基于项目的Pearson推荐算法

项目ij之间的相似度为:

$sim(i,j) = \frac{{\displaystyle\sum\limits_{u \in {U_{ij}}} {({R_{u,i}} - {{\overline R }_i})({R_{u,j}} - {{\overline R }_j})} }}{{\sqrt {\displaystyle\sum\limits_{u \in {U_{ij}}} {{{({R_{u,i}} - {{\overline R }_i})}^2}} } \sqrt {\displaystyle\sum\limits_{u \in {U_{ij}}} {{{({R_{u,j}} - {{\overline R }_j})}^2}} } }}$ (3)

根据相似度最大的前k个项目产生推荐:

${P_{u,i}} = {\overline R _i} + \frac{{\displaystyle\sum\limits_{m \in {M_k}} {sim(i,m)({R_{u,m}} - {{\overline R }_m})} }}{{\displaystyle\sum\limits_{m \in {M_k}} {(|sim(i,m)|)} }}$ (4)

式(3)~(4)中, ${\overline R _i}$ i项上所有用户的平均得分, ${\overline R _j}$ j项上所有用户的平均得分, ${U_{ij}}$ 为项目i和项目j共同评分的用户集合, $M_k$ 为与项目i最相似的前k个项目。

2 协同过滤推荐算法改进 2.1 算法改进策略

基于协同过滤的推荐算法需要根据用户之间对项目的共同评分推断用户之间的相似度,或根据项目之间用户共享的数据推断项目之间的相似度。由于实际应用中用户和项目的数量不断增加,用户一般只会对一小部分项目评分,一个项目一般只有少部分用户参与评分,也就是说用户之间共同评分的项目非常少甚至两个用户之间没有共同评分项,项目之间同样如此。这样导致用于计算用户相似度的数据和用于计算项目相似度的数据非常有限,推荐质量急剧下降,对协同过滤推荐算法产生负面影响。

从式(3)中可以看出 ${U_{ij}} = {U_i} \cup {U_j}$ ${U_i}$ ${U_j}$ 分别为项目i和项目j共同评过分的用户集合, ${U_{ij}}$ 为它们的并集。当数据稀疏时, ${U_{ij}}$ 空间数据很少甚至没有数据,存在两个用户没有对同一个项目进行评分的情况,致使式(3)无法正常计算。为此改进如下:先采用基于用户的Pearson推荐算法进行第1次计算,将预测的值作为中间结果填补评分空白,再基于项目的Pearson推荐算法进行第2次计算,同时在计算相似度时考虑用户共同评分项数。

1)根据基于用户的Pearson推荐算法式(1)、(2),对任意用户计算 ${U_{ij}}$ 空间中用户对项目的评分,填充空值,扩大 ${U_{ij}}$ 空间:

①在用户空间 ${U_{ij}}$ 中,用户之间的相似度按式(1)计算;

②式(1)需要通过 ${I_{uv}}$ 计算, ${I_{uv}} = {I_u} \cup {I_v}$ ${I_u}$ 为用户u的项目集, ${I_v}$ 为用户v的项目集。同样,由于数据稀疏导致经用户uv共同评分的项目集合空间 ${I_{uv}}$ 的数据很少甚至没有,这时考虑通过评分平均值进行补全填补空白,使得 ${I_u} \cup {I_u} = {I_u} \cap {I_u}$

③根据式(2),将与用户n相似度最高的前k个用户作为集合 $N_k{\rm{ = \{ }}{U_1},{U_2}{\rm{,}} \cdots {\rm{,}}{U_k}{\rm{\} }}$ ,用户 ${U_1}$ 与用户n的相似度最高,用户 ${U_2}$ 与用户n的相似度次之,依次类推。

2)相似度高的用户之间如果共同评分的项目数量比较少,如只有1个或没有,这时相似度的可信度不高,为此引入相似度支持度权重 $S{\!W_{uv}}$ ,即:

$S\!{W_{uv}} = \frac{{S\!{S_{uv}} - S\!{S_{\min }}}}{{S\!{S_{\max }} - S\!{S_{\min }}}}$ (5)

式中:相似度支持度 $S\!S$ 为共同评分样本数量; $S\!{S_{uv}}$ 为用户uv之间相似度支持度,其值为用户uv共同评分的项目数; $S\!{S_{\min }}$ $S\!{S_{\max }}$ 分别为在用户空间中相似度支持度的最小值和最大值。

将用户uv之间的相似度 ${{sim(}}u{\rm{,}}v{\rm{)}}$ 乘以相似度支持度权重 $S\!{W_{uv}}$ 作为新的相似度:

$sim'(u,v) = sim(u,v) \times S\!{W_{uv}}$ (6)

3)根据式(3)计算相似度,此时评分空缺值采用第1次计算后的预测数据与其他原始评分数据相加求平均,以扩大 ${U_{ij}}$ 空间,最后根据式(4)产生最终推荐。

2.2 算法实验策略

协同过滤推荐算法较多,具体使用哪个算法进行优化以达到更好的推荐效果需要通过实验验证,因此首先要对各基本算法在不同优化条件下的推荐效果对比分析。

无论是基于用户还是基于项目推荐,都需要根据相似度高的前k个用户或项目产生推荐,而k的取值关系到推荐效果。k取值过大会导致计算量过大,影响推荐的实时性能,k 值过小会导致推荐精度下降,因此需要对k的取值进行实验研究。

当稀疏度改变时,优化方法是否有更好的推荐效果,也需要通过实验加以验证。

3 实验结果及分析 3.1 数据集和评分标准

本文采用MovieLens数据,包含943个用户和1 682部电影(项目),将数据集中的ua.data作为计算数据,ua.test作为测试数据。

通过预测评分与实际评分之间的MAE偏差度量预测的准确性:

${\rm MAE} = \frac{{\displaystyle\sum\limits_{i = 1}^n {|{p_i} - {q_i}|} }}{n}$ (7)

式中, ${p_i}$ 为预测评分数据集合 ${\rm{\{ }}{p_1},{p_2}{\rm{,}} \cdots {\rm{,}}{p_n}{\rm{\} }}$ 的一个元素, ${q_i}$ 为实际评分数据集合 ${\rm{\{ }}{q_1},{q_2}{\rm{,}} \cdots {\rm{,}}{q_n}{\rm{\} }}$ 的一个元素,MAE越小推荐质量越高。

3.2 优化算法实验及分析

首先,确定在相似度计算中是采用Pearson相关相似性还是修正余弦相关性进行分析。支持度权重[15-16]优化算法是在式(1)~(4)基础上,根据参考文献[15-16]对相似度考虑支持度权重进行优化;邓爱林等[14]优化算法是在式(1)~(4)的基础上,根据参考文献[14]先基于用户预测数据填补未评分值再基于项目进行优化。k取值范围为5~60,步长为5,为使对比明显,Pearson采用实线和长划线、修正余弦采用点和短划线,实验结果如图1所示。

图1 Pearson相关相似性与修正余弦相关性比较 Fig. 1 Comparisons of Pearson and adjusted cosine

图1可以看出,在支持度权重[15-16]优化算法和邓爱林等[14]优化算法中,Pearson相关优于修正余弦相关,故在相似度计算时本文采用Pearson相关相似性度量。

接着,对未优化算法、支持度权重[15-16]优化算法、邓爱林等[14]优化算法和本文提出的推荐算法在采用Pearson相关相似性度量的情况下进行比较,k值范围为15~60,计算结果如图2所示。

图2 不同k值下各推荐算法比较 Fig. 2 Comparison of recommendation algorithms under different k values

图2中看出,虽然随着k值的增加,各算法推荐精度差别减小,但本文提出的方法一直具有优势。

3.3 稀疏度实验及分析

为进一步确定优化效果,将稀疏度改变。稀疏度定义为用户评分数据中未评分项所占比例,即为:1–评分项/(用户数×电影数)。在本文采用的数据集中,用户有943人,电影有1 682部,原始数据记录有90 570条,即稀疏度d为:d=1–90 570/(943×1 682)=0.943。再随机抽取45 542、36 481、27 245、18 097条记录作为测试数据,相应稀疏度为0.971、0.977、0.983、0.989。从图1看出:在支持度权重[15-16]优化算法中k取值范围在15~30之间具有更好的优化效果;在邓爱林等[14]优化算法中,k取值范围在10~25之间具有更好的优化效果。基于计算量考虑,本文采用k=15进行实验。支持度权重[15-16]优化算法、邓爱林等[14]优化算法和本文优化算法的MAE在稀疏度增大情况下的比较结果如表1所示。

表1 不同稀疏度下各推荐算法比较 Tab. 1 Comparisons of recommendation algorithms under different sparsity

表1中可以看出:以原始数据90 570条记录作为基础,随着评分项的减少,数据稀疏度增大。在稀疏度增加到0.943、0.971、0.977、0.983、0.989的情况下,支持度权重[15-16]优化算法的MAE值分别增加12.73%、15.78%、21.75%和29.97%;邓爱林等[14]优化算法和本文优化算法的MAE值分别增加5.70%、9.01%、15.23%和25.96%;而本文的优化算法的MAE值分别增加3.34%、4.68%、6.55%和7.62%,增加量明显下降。显然,随着稀疏度的增加,本文提出的方法具有更好的优化效果。

4 结 论

提出了数据稀疏时基于协同过滤的推荐改进算法,该算法主要从如何填补评分空缺、考虑共同评分项数量等方面对基本算法进行优化,并将该优化方法与其他方法进行实验对比分析。通过实验分析可知,本文优化算法比原始模型算法推荐质量显著提高,较其他方法也有一定优化效果,尤其在数据稀疏度增大的情况下,优化效果非常显著。

基于评分数据产生推荐的方式易于模型建立,但评分数据包含的信息量有限,后续将研究通过文本挖掘获取更多的用户对项目的评论信息,通过用户感兴趣的特征词建立用户编好模型,降低数据稀疏度,将基于协同过滤的推荐算法与文本挖掘相结合产生更好的推荐。

参考文献
[1]
Zenebe A,Norcio A F. Representation,similarity measures and aggregation methods using fuzzy sets for content-based recommender systems[J]. Fuzzy Sets and Systems, 2009, 160(1): 76-94. DOI:10.1016/j.fss.2008.03.017
[2]
Yang Bo,Zhao Pengfei. Review of the art of recommendation algorithms[J]. Journal of Shanxi University(Natural Science Edition), 2011, 34(3): 337-350. [杨博,赵鹏飞. 推荐算法综述[J]. 山西大学学报(自然科学版), 2011, 34(3): 337-350. DOI:10.13451/j.cnki.shanxi.univ(nat.sci.).2011.03.001]
[3]
Huang Jinchao,Zhang Jiawei,Chen Ning,et al. Preference degree based personalized recommendation algorithm[J]. Journal of Shanghai Jiao Tong University, 2018, 52(7): 770-776. [黄金超,张佳伟,陈宁,等. 基于偏好度特征构造的个性化推荐算法[J]. 上海交通大学学报, 2018, 52(7): 770-776. DOI:10.16183/j.cnki.jsjtu.2018.07.003]
[4]
Zhang Jiale,Liang Jiye,Pang Jifang,et al. Behavior and score similarity based algorithm for association rule group recommendation[J]. Computer Science, 2014, 41(3): 36-40. [张佳乐,梁吉业,庞继芳,等. 基于行为和评分相似性的关联规则群推荐算法[J]. 计算机科学, 2014, 41(3): 36-40. DOI:10.3969/j.issn.1002-137X.2014.03.007]
[5]
Hu Wenjiang,Hu Dawei,Gao Yongbing,et al. Friend recommendation algorithm based on association rules and tags[J]. Computer Engineering & Science, 2013, 35(2): 109-113. [胡文江,胡大伟,高永兵,等. 基于关联规则与标签的好友推荐算法[J]. 计算机工程与科学, 2013, 35(2): 109-113. DOI:10.3969/j.issn.1007-130X.2013.02.019]
[6]
Huang Xianying,Xiong Liyuan,Li Qindong. Personalized news recommendation technology based on improved collaborative filtering algorithm[J]. Journal of Sichuan University(Natural Science Edition), 2018, 55(1): 49-55. [黄贤英,熊李媛,李沁东. 基于改进协同过滤算法的个性化新闻推荐技术[J]. 四川大学学报(自然科学版), 2018, 55(1): 49-55. DOI:10.3969/j.issn.0490-6756.2018.01.009]
[7]
Yu Hong,Li Junhua. Algorithm to solve the cold-start problem in new item recommendations[J]. Journal of Software, 2015, 26(6): 1395-1408. [于洪,李俊华. 一种解决新项目冷启动问题的推荐算法[J]. 软件学报, 2015, 26(6): 1395-1408. DOI:10.13328/j.cnki.jos.004587]
[8]
Wang Peng,Wang Jingjing,Yu Nenghai. A kernel and user-based collaborative filtering recommendation algorithm[J]. Journal of Computer Research and Development, 2013, 50(7): 1444-1451. [王鹏,王晶晶,俞能海. 基于核方法的User-Based协同过滤推荐算法[J]. 计算机研究与发展, 2013, 50(7): 1444-1451. DOI:10.7544/issn1000-1239.2013.20111660]
[9]
Wang Z Q,Liang J Y,Li R,et al. An approach to cold-start link prediction:Establishing connections between non-topological and topological information[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(11): 2857-2870. DOI:10.1109/tkde.2016.2597823
[10]
Li Xin,Liu Guiquan,Li Lin,et al. Circle-based and social connection embedded recommendation in LBSN[J]. Journal of Computer Research and Development, 2017, 54(2): 394-404. [李鑫,刘贵全,李琳,等. LBSN上基于兴趣圈中社会关系挖掘的推荐算法[J]. 计算机研究与发展, 2017, 54(2): 394-404. DOI:10.7544/issn1000-1239.2017.20150788]
[11]
Li Xiaohao.Research of sparsity and scalability problem in collaborative filtering[D].Chongqing:Chongqing University,2015.
李小浩.协同过滤推荐算法稀疏性与可扩展性问题研究[D].重庆:重庆大学,2015.
[12]
Li Daxue,Xie Mingliang,Zhao Xuebin. Collaborative filtering recommendation algorithm based on naive Bayesian method[J]. Journal of Computer Applications, 2010, 30(6): 1523-1526. [李大学,谢名亮,赵学斌. 基于朴素贝叶斯方法的协同过滤推荐算法[J]. 计算机应用, 2010, 30(6): 1523-1526.]
[13]
Zhang Lei,Chen Junliang,Meng Xiangwu,et al. BP neural networks-based collaborative filtering recommendation algorithm[J]. Journal of Beijing University of Posts and Telecommunications, 2009, 32(6): 42-46. [张磊,陈俊亮,孟祥武,等. 基于BP神经网络的协作过滤推荐算法[J]. 北京邮电大学学报, 2009, 32(6): 42-46. DOI:10.3969/j.issn.1007-5321.2009.06.010]
[14]
Deng Ailin,Zhu Yangyong,Shi Baile. A collaborative filtering recommendation algorithm based on item rating prediction[J]. Journal of Software, 2003, 14(9): 1621-1628. [邓爱林,朱扬勇,施伯乐. 基于项目评分预测的协同过滤推荐算法[J]. 软件学报, 2003, 14(9): 1621-1628. DOI:10.13328/j.cnki.jos.2003.09.017]
[15]
Luo Xin,Ouyang Yuanxin,Xiong Zhang,et al. The effect of similarity support in K-nearest-neighborhood based collaborative filtering[J]. Chinese Journal of Computers, 2010, 33(8): 1437-1445. [罗辛,欧阳元新,熊璋,等. 通过相似度支持度优化基于K近邻的协同过滤算法[J]. 计算机学报, 2010, 33(8): 1437-1445.]
[16]
Wang Wei,Zheng Jun. Improved collaborative filtering algorithm based on user-similarity[J]. Journal of East China Normal University(Natural Science), 2016(3): 60-66. [王威,郑骏. 基于用户相似度的协同过滤算法改进[J]. 华东师范大学学报(自然科学版), 2016(3): 60-66. DOI:10.3969/j.issn.1000-5641.2016.03.007]