基于缺失值迭代预测填充的协同过滤推荐算法

卢　棪　刘应安

(南京林业大学信息科学技术学院　南京　210037)

基于缺失值迭代预测填充的协同过滤推荐算法

卢棪刘应安

(南京林业大学信息科学技术学院南京210037)

摘要推荐系统是目前在电子商务中用的较为广泛的一种技术。伴随着数据量的增大,评分矩阵的稀疏性成为了一大难题。对于评分数据较为稀疏的矩阵,提出了一种基于缺失值迭代预测填充的协同过滤算法。这种算法以迭代的方式对评分矩阵填充,直到缺失值个数恒定在某一数值。而在迭代的过程中,每一次用于填充计算的相似度度量又是依据均值填充后的相似度来动态计算的。说明该算法即可以降低数据稀疏性,又提高了用户相似度计算精度的问题。实验研究表明,利用该算法能够提高评分矩阵的密度,并降低了系统的推荐误差。

关键词推荐系统; 协同过滤; 迭代; 预测; 相似度计算; 缺失值填充; 数据密度

Class NumberTP311

1引言

协同过滤是在电子商务系统中使用非常广泛的一类推荐算法,其基本思想是在用户群中找到指定用户的相似(兴趣)用户,综合这些相似用户对某一信息的评价,形成系统对该指定用户对此信息的喜好程度预测。

随着电子商务系统的进一步扩大,用户数目和项目数目日益剧增,这样就会导致用户评分的极度稀疏性。在这样的情况下,系统的推荐质量就会急剧下降。通常,针对推荐系统数据稀疏的问题,有一种最简单的方法就是对未评分的用户设定一个为评分域中所有评分的均值的值,这种改进方法可以改善稀疏性并且提高提高推荐系统的推荐精度,但是用户的主观评分不可能完全相同,所以此方法在用户评分数据稀疏的情况下计算相似性还是存在着一定的弊端。目前,已有很多研究者提出了更有效的解决数据稀疏性的方法。文献[1]提出了一种通过计算项目相似度填充用户评分矩阵的方法,有效缓解了数据的稀疏性。文献[3]将奇异值分解技术应用到协同过滤中来,通过降低输入矩阵的维数来降低数据的稀疏性。文献[5]提出了基于用户相似度传递的方法来缓解稀疏性。文献[6]提出了一种解决数据稀疏性的迭代协同过滤算法,该算法根据项目评分的相似性来反复填充评分矩阵,虽然能够很大程度上改善数据的稀疏性问题,但是却没有考虑到项目评分相似性不高,项目本身相似度很高的情况。文献[7]提出了一种在稀疏数据集中使用巴氏距离计算相似度的方法来提高评分的相似性,但计算巴氏距离较为复杂,而且也没有改善数据稀疏的问题。文献[9]提出了一种基于云模型的方法来预测填充矩阵,该算法可以适用于任何数据集并且改善稀疏性,但是巨大的计算开销还是需要考虑。文献[10]提出了一种算法,该算法对相似性很高但却没有评分的用户进行评分预测,从而降低稀疏性提高推荐质量。文献[13]提出了一种基于神经网络的方法,通过构建B-P神经网络来填充评分矩阵中的缺失值,充分缓解数据稀疏性问题。但是B-P神经网络模型的学习成本较大,计算效率的提高需要进一步考虑。文献[14]提出了一种分布填充的协同过滤算法,该算法首先通过相似度和评分数量都达到一个特定值的用户作为邻居用户,其次通过这些用户来预测并填充为评分的项目,最后通过填充后的用户评分矩阵来预测用户的评分。这种方法能在降低数据稀疏性的同时提高推荐质量。

为了进一步缓解评分矩阵的稀疏性,本文提出了一种基于缺失值迭代预测填充的协同过滤算法,此算法以迭代的方式对评分矩阵填充直到缺失值个数恒定在某一数值。而在迭代的过程中,每一次用于填充计算的相似度度量又是依据均值填充后的相似度来动态计算的。即在降低数据稀疏性的同时又改善了在用户评分极端稀疏情况下用户相似性计算准确度的问题。

2协同过滤算法相关概念

2.1相似相关性

2.1.1项目类别相似性

根据文献[15]可知,通过项目间的类别距离度量项目类别相似性如式(1)所示:

(1)

其中,l(i,j)为返回项目i和j节点到达公共双亲的最长路径长度,H为项目类别树的树高。

2.1.2用户相似性

设Iuv表示用户u和用户v共同评分项目集,则用户u和v的相似性sim(u,v)如下式:

(2)

通过上述方法可以基于用户对项目的评分作相似性的判断。

2.2产生推荐

目标用户对任意项目i的评分:设目标用户的最近邻集合为Nu={vi1,…,vik},u∉N,则目标用户u对项目i的预测评分Pui如下式所示。

(3)

式中,rv和ru分别表示用户v和u对项目的平均评分值。

3基于缺失值迭代预测填充的协同过滤算法

3.1评分矩阵缺失值的预测及填充

为了有效地解决评分矩阵极端稀疏的情况下相似度可信度不高的问题,本文提出对评分矩阵的缺失值进行预测并填充的方法。

设项目中未评分的缺失值集合为Nup,对任意项目p∈Nuj,使用如下方法预测用户u对项目p的评分Pu,p。

1) 计算所有项目之间的相似性

对于项目本身而言,存在项目类别的相似性和项目评分的相似性。在计算项目类别的相似性时,考虑到若某个项目可能存在多个类别。为了解决此问题,本文对式(1)的方法进一步改进。如式(4)所示:

(4)

其中,若只存在一个公共父节点,就取最长路径长度。若存在多个公共父节点,就取距离项目i和j节点最短的公共父节点中最长路径长度。

故可用式(5)来动态加权计算项目之间的相似性,

(5)

其中,sim(i,j)*是最终加权得出的相似性结果,sim(i,j)是项目评分之间的相似性,s(i,j)是项目类别之间的相似性,simaverage(i,j)是均值填充所计算的项目的相似性,α为权重系数并与simaverage(i,j)有关,具体关联如式(6)所示

(6)

2) 缺失值的预测

通过上述方法处理后便得到项目之间的相似性,将相似性最高的若干项目作为p的邻居项目集合。即在整个项目空间中查找与项目p相似度最高的项目集合Kp={I1,I2,…,In},并且sim(p,I1)最高,sim(p,I2)次之,依次类推。

得到Kp后,采用文献中[4]提出的方法预测用户u对项目p的评分Pu,p:

(7)

其中,Ru,n表示用户u对相似度最高的项目集合中项目n的评分,simp,n表示项目p和项目n的相似性。

3) 缺失值的填充

通过上述方法处理后,对整个项目空间中的任意项目的评分Ru,j则可以表示为

图1　预测值填充流程

经过如上方法后可以对评分矩阵的缺失值进行填充。

具体填充方法如图1所示。

3.2迭代预测及填充

随着迭代的次数增加,填充的值可能会趋向某一固定的数值,这样就导致填充的值失去真实性。故需要引入一个修正值来动态控制填充值的大小。通过用户属性的相似度来预测缺失值,并以此预测值为基准来动态的调整迭代后的预测的值。用以下公式进行调整:

(8)

其中,Pcorrrect为修正后的填充值,Piterate为迭代后的填充值,Pproperty为基于用户属性的填充值。α则是用来控制修正范围大小的参数,即当Piterate与Pproperty相差较大时,则修正的范围较大。反之,当Piterate与Pproperty相差较小时,则修正的范围较小。并且当Piterate与Pproperty相同时,则说明当前迭代后的填充值为离真实值最接近的填充值。对于系数k的判定,则根据评分制度来判定,则k的大小始终与评分的最大值相同。比如,评分标准为5分制,k就为5,若为3分制,k就为3。

通过上述的方法就能动态的对填充值进行修正。

故加入修正值后的具体迭代方法如图2所示。

图2　迭代流程

通过上述方法,可以有效地降低原始评分矩阵的稀疏性,并改善在用户评分极端稀疏情况下用户相似性计算准确度的问题。

4实验结果与分析

4.1数据来源

本文采用MovieLens站点提供的数据集(http://movielens.umn.edu/)。它由美国Minnesota大学计算机科学与工程学院的GroupLens项目组创办,并且用于接收用户对电影的评分并提供相应的电影推荐列表。目前,该Web站点的用户评分的电影超过3500部,用户已经超过43000人。但实际评分数据的密度为100000/(943*1682)=6.3%,说明此数据是相当稀疏的。我们从用户评分数据库中随机选取了三组数据,每组数据包括150个用户,1682部电影,并将每组数据进一步划分为训练集和测试集。整个数据集的80%作为训练集,20%作为测试集。

4.2推荐质量的度量标准

评价推荐系统推荐质量的度量标准主要包括统计精度度量方法和决策支持精度度量方法两类。统计精度度量方法中的平均绝对偏差(Mean Absolute Error,MAE)是最常用的一种推荐质量度量方法,该方法是通过计算预测的用户评分与实际的用户评分之间的偏差度量预测的准确性。若MAE越小,则说明推荐质量越高。反之,说明推荐质量越低。

设预测的用户评分集合表示为{p1,p2,…,pn},对应的实际用户评分集合为{q1,q2,…,qn},则平均绝对偏差MAE定义为

(9)

4.3实验结果

为了检验本文提出算法的有效性,分别以传统的基于用户的协同过滤推荐算法(UBCF),均值填充的协同过滤算法(AFCF)以及本文提出的基于缺失值迭代的协同过滤算法(IFCF)来做比较,计算其MAE值,邻居个数从5增加到30,间隔为5。实验结果如图3～图5所示。

图3　不同邻居数对MAE的影响(数据1)

其中图3为第一组数据的三种算法的比较,图4为第二组数据,图5为第三组数据,可以观察出当邻居个数越大时,算法的推荐精度就越好。

5结语

本文通过分析传统协同过滤面临的数据稀疏性问题及现有的解决方法,提出了一种基于缺失值迭代预测填充的协同过滤算法。利用项目和用户的相似性来预测缺失值,并利用迭代的方式来进一步缓解评分矩阵的稀疏性。由于每一次都是基于上一次填充后的矩阵进行迭代,因此也改善了在用户评分极端稀疏情况下用户相似性计算准确度的问题。实验结果表明,基于缺失值迭代预测填充的协同过滤算法可以有效的解决用户评分数据的稀疏性问题,提高推荐的准确度。

图4　不同邻居数对MAE的影响(数据2)

图5　不同邻居数对MAE的影响(数据3)

参 考 文 献

[1] 邓爱林,朱扬勇,施伯乐.基于项目评分预测的协同过滤推荐算法[J].软件学报,2003,14(9):1621-1628.

DENG Ailing, ZHU Yangyong, SHI Bole. Collaborative filtering recommendation algorithm based on item score prediction[J]. Journal of Software,2003,14(9):1621-1628.

[2] 邓爱林,左子叶,朱扬勇.基于项目聚类的协同过滤推荐算法[J].小型微型计算机系统,2004,25(9):1665-1670.

DENG Ailing, ZUO Ziye, ZHU Yangyong. Collaborative filtering recommendation algorithm based on item clustering[J]. Journal of Chinese Computer Systems,2004,25(9):1665-1670.

[3] Sarwar BM, Karypis, Konstan JA, Riedl J. Application of dimensionality reduction in recommender system-A case study[C]//ACM WebKDD 2000 Workshop,2000:80-90.

[4] Sarwar B, Karypis, Konstan J, Riedl J. Item-Based collaborative filtering recommendation algorithms[C]//Proceedings of the 10thInternational World Wide Web Conference,2001:285-295.

[5] HUETE J F, FEMANDEZ-LUNA J M, De CAMPOS L M, et al. Using past-prediction accuracy in recommender systems[J]. Information Science: an International Journal,2012,199(9):78-92.

[6] Zhuo Zhang, Paul Cuff, Sanjeev Kulkarni. Iterative collaborative filtering for recommender systems with sparse data[C]//2012 IEEE International Workshop On Machine Learning For Signal Process,2012,SEPT:23-26.

[7] Bidyut Kr. Patra, Raimo Launonen, Ville Ollikainen, et al. A new similarity measure using Bhattacharyya coefficient for collaborative filtering in sparse data[J]. Knowledge-Based Systems,2015,82:163-177.

[8] Mohsen Ramezani, Parham Moradi, Fardin Akhlaghian. A pattern mining approach to enhance the accuracy of collaborative filtering in sparse data domains[J]. Physica A,2014,408:72-84.

[9] 张光卫,李德毅,李鹏,等.预计云模型的协同过滤算法[J].软件学报,2007,18(10):2403-2411.ZHANG Guangwei, LI Deyi, LI Peng, et al. Cloud model based collaborative filtering algorithm[J]. Journal of Software,2007,18(10):2403-2411.

[10] 张学胜.面向数据稀疏的协同过滤推荐算法研究[D].合肥:中国科技大学,2011.

ZHANG Xuesheng. Research on Collaborative Filtering Recommendation Algorithm Based on data sparse[D]. Hefei: University of Science and Technology of China,2011.

[11] 杨炎.基于项目聚类的协同过滤推荐算法的研究[D].吉林:东北师范大学,2005.

YANG Yan. Research on Collaborative Filtering Recommendation Algorithm Based on item clustering[D]. Jilin: Northeast Normal University,2005.

[12] 李涛,王建东,叶飞跃,等.一种基于用户聚类的协同过滤推荐算法[J].系统工程与电子技术,2007,29(7):1176-1182.

LI Tao, WANG Jiandong, YE Feiyue, et al. Collaborative filtering recommendation algorithm based on user clustering[J]. Systems Engineering and Electronics,2007,29(7):1176-1182.

[13] 张锋,常学友.使用BP神经网络缓解协同过滤推荐算法的稀疏性问题[J].计算机研究与发展,2006,43(4):667-672.

ZHANG Feng, CHANG Xueyou. Sparsity problem of collaborative filtering recommendation algorithm based on BP neural network[J]. Computer Research and Development,2006,43(4):667-672.

[14] 张玉芳,代金龙,熊忠阳.分步填充缓解数据稀疏性的协同过滤算法[J].计算机应用研究,2013,30(9):2603-2605.

ZHANG Yufang, DAI Jinglong, XIONG Zhongyang. Collaborative filtering algorithm for sparse data filtering by step filling[J]. Application Research of Computers,2013,30(9):2603-2605.

[15] 黄创光,印鉴,汪静,等.不确定近邻的协同过滤算法[J].计算机学报,2010,33(8):1369-1377.

HUANG Chuangguang, YIN Jian, WANG Jing. Collaborative filtering algorithm for uncertain nearest neighbor[J]. Chinese Journal of Computers,2010,33(8):1369-1377.

[16] Sarwar B, Karypis G, Konstan J, et al. Analysis of recommendation algorithm for E-commerce[C]//Proc. Of the 2ndACM Conference on Electronic Commerce. New York: ACMPress,2000:158-167.

[17] 吴一帆,王浩然.结合用户背景信息的协同过滤推荐算法[J].计算机应用,2008,28(11):2973-2975.WU Yifan, WANG Haoran. Collaborative filtering recommendation algorithm based on user background information[J]. Computer Application,2008,28(11):2973-2975.

[18] 黄霞,韦素云,业宁,等.基于用户属性和项目类别的协同过滤算法[J].计算机与数字工程,2012,40(10):5-8.

HUANG Xia, WEI Suyun, YE Ning, et al. Collaborative filtering algorithm based on user attributes and item categories[J]. Computer & Digital Engineering,2012,40(10):5-8.

[19] STOLCK A, ZHENG Jing, WANG Wen, et al. SRILM at sixteen:update and outlook[C]//Proc of IEEE Workshop on Speech Hecognition and UnderStanding,2011.

A Collaborative Filtering Algorithm Based on Predicting and Filling Missing-Data by Iterated

LU YanLIU Ying’an

(College of Information Science and Technology, Nanjing Forestry University, Nanjing210037)

AbstractRecommendation system is a widely used technology in the electronic commerce. Along with the increase of the amount of data, sparsity of rating data become a big question. To improve sparsity of rating data more effectively, a collaborative filtering algorithm based on predicting and filling miss-data by interated is proposed. This method fills the rating data by iterated until the number of missing-data stably. During the iterating, the method of similarity analysis based on the result-data at last step. So not only this method improves sparsity of rating data more effectively, but else efficiently improves the accuracy of similarity analysis under the exreme sparsity of rating data.The experimental results show that this method can improve the quality of recommendation.

Key Wordsrecommendation, collaborative filtering, iteration, prediction, similarity computing, filling missing-data, data density

收稿日期:2015年12月7日,修回日期:2016年1月30日

基金项目:国家自然科学基金(编号:11471161)资助。

作者简介:卢棪,男,硕士研究生,研究方向:数据挖掘。刘应安,男,博士,教授,研究方向:数据挖掘,统计诊断,林业统计分析。

中图分类号TP311

DOI:10.3969/j.issn.1672-9722.2016.06.002