基于稀疏数据预处理的协同过滤推荐算法

陈宗言，颜 俊

(1.南京邮电大学 通信与信息工程学院，江苏 南京 210003；2.宽带无线通信与传感网技术教育部重点实验室，江苏 南京 210003)

基于稀疏数据预处理的协同过滤推荐算法

陈宗言1,2，颜 俊1,2

(1.南京邮电大学 通信与信息工程学院，江苏 南京 210003；2.宽带无线通信与传感网技术教育部重点实验室，江苏 南京 210003)

随着推荐系统规模的不断扩大,用户-项目评分矩阵呈现出极端稀疏性,导致基于传统相似性度量方法的协同过滤推荐系统推荐质量的下降。针对该问题,文中提出了一种基于项目特征属性的稀疏数据集预处理方法来提高算法的推荐质量。首先,通过引入项目的特征属性信息,根据项目间特征属性相似度,初步预测用户对未评分项目的评分,可以使得用户-项目评分矩阵完全饱和。接着再对稀疏数据集的未评分项目进行混合填充预处理,避免了传统均值填充法中的用户对项目的评分不可能完全相同的问题以及众数填充法中的“多众数”和“无众数”问题。实验结果表明,文中提出的方法更能有效地提高推荐系统的推荐质量和推荐覆盖率。

推荐系统；协同过滤；特征属性；稀疏数据集；混合填充

1 概 述

随着信息技术和互联网的发展，人们逐渐从信息匮乏的时代步入了信息过剩的时代。在这个时代里，无论是信息的生产者或信息的消费者都面临着巨大挑战：作为信息生产者，如何让自己的信息脱颖而出，受到广大用户的关注，是一件非常困难的事情；作为信息消费者，如何从海量的信息中找到自己感兴趣的信息也是一件非常复杂的事情。因此，推荐系统成为互联网技术研究的一个热点。

推荐系统的任务就是联系用户和信息，一方面帮助用户发现对自己有价值的信息，另一方面让信息能够展现在对它感兴趣的用户面前[1]。

为使推荐系统产生精确的推荐，保证推荐系统的实时性和有效性，研究人员提出了各式各样的推荐算法。文献[2-4]提出了通过对用户(项目)进行聚类分析来进行个性化推荐的方法，该方法可以有效提高推荐系统的响应速度，但其推荐精度并没有显著改善；文献[5]通过对用户购买的商品进行关联分析，发掘商品间关联度并产生推荐，但在关联过程中会产生较多的候选项目集，输入输出负载较大；文献[6]提出了分类算法，通过对用户(项目)进行分类，进而产生分类推荐，可以有效提高推荐的准确率；文献[7-8]提出了协同过滤推荐算法，通过对用户的历史兴趣进行分析，根据得到的预测结果为用户提供推荐，显著提高了推荐的精确性，并且其算法模型简单、数据采集方便。

鉴于协同过滤算法在推荐系统方面体现出的巨大优势，文中重点讨论基于项目(Item-Based)的协同过滤推荐算法[9]。

协同过滤推荐主要有两大类：基于模型的方法[10]和基于记忆的方法[11]。基于模型的方法通过系统已有的用户-商品信息学习并产生一个模型，从而根据得到的模型进行预测推荐；基于记忆的方法主要通过计算用户(项目)间的相关性，根据算法所设定的邻居个数，寻找目标用户(项目)的最近邻，这些最近邻居可由目标项目与其他项目相似值从高到低排列所得，并通过最近邻为用户(项目)进行推荐。

迄今为止，协同过滤技术在电子商务发展中得到了广泛应用。以亚马逊为代表的电子商务公司通过对目标用户的历史购买记录进行分析，进而产生个性化推荐。据VentureBeat统计，亚马逊公司每年至少有35%的销售来自于推荐算法。著名视频网站Netflix通过对用户的历史观看记录的分析，得到用户的个人观影喜好，进而为用户推荐相似的电影。

但是，随着推荐系统规模的不断扩大，用户评分数据呈现出极端的稀疏性，比如：在大型商务系统中，用户评分的项目一般不会超过项目总和的1%[12]。研究发现，协同过滤技术在对由用户历史信息得到的用户-项目评分矩阵进行用户(项目)相似度计算时，得到的结果不能让人满意。比如：一个用户由于是新用户或者其做出评分的项目过少，可能会导致该用户和其他用户之间的相似度无法计算，从而不能做出有效推荐，导致推荐算法精确度的下降。

针对上述问题，文献[13-14]提出了相似性度量方法的优化算法，但由于其在计算项目(用户)相似性时仍然是基于稀疏数据集，所以性能仍然提高不大。因此，在大型商务系统中，基于稀疏数据集的协同过滤推荐算法的相似度计算已经成为制约推荐系统性能的一个关键因素，如何在计算相似度之前对稀疏的数据集进行合适的处理则成为提高推荐效率的一个关键。

为此，文中提出了一种基于项目特征属性的数据预处理技术。主要贡献有以下两点：

(1)通过引入项目的特征属性信息，根据项目间特征属性相似度，初步预测用户对未评分项目的评分，再对稀疏数据集的未评分项目进行混合填充预处理，可以使得用户-项目评分矩阵完全饱和。

(2)有效避免了文献[15]所提出的均值填充法中的用户对不同项目评分不可能完全一致以及众数填充法中“多众数”和“无众数”的问题。

实验结果表明，相对于对稀疏数据集的缺失项不进行填充和使用“众数填充”的方法，文中所提方法更能有效地提高推荐系统的推荐质量和推荐的覆盖率。

2 相关工作

目前，学术界对推荐算法的相似性度量和稀疏数据集的预处理已经开展了很多研究工作。

相似性的度量方法主要有三种：Pearson相关相似性、余弦相似性以及修正的余弦相似性。鉴于修正的余弦相似性原理与余弦相似性相同，只是公式上的略微变化，这里不做详细介绍。前两种方法的计算公式如下：

(1)

余弦相似性：项目所得评分被看做是n维用户空间上的向量，如果用户对项目没有进行评分，则将该用户对项目的评分设为0，项目间的相似性通过向量间的余弦夹角度量：

(2)

这两种相似性方法可以有效计算用户(项目)间的相似度，但如前文所述，如果一个用户由于是新用户或者其做出评分的项目过少，使得该用户和其他用户之间没有共同的项，导致该用户和其他用户之间的相似度无法计算。因此，针对这种由用户-项目评分矩阵极度稀疏引起的问题，研究人员又提出了各式各样对稀疏数据集进行预处理的方法。

文献[16-18]提出通过奇异值分解(SVD)算法估计未评分项目的评分来填充用户-项目矩阵，奇异值分解在用户-项目矩阵较为稠密的情况下会取得较高的准确度，在数据极度稀疏情况下，预测效果并不是很理想。文献[19]提出对用户未评分项目进行均值填充(meanfilling)及众数填充(modefilling)等方法,但是这种赋予固定值的方法并不是很可信。比如采用众数法时，利用一组数据中出现频率最高的数来填充缺失值，会出现“多众数”和“无众数”的问题。采用均值法时，对用户未评分的项目赋予项目或用户的评分均值，同样也存在用户对项目的评分不可能完全相同的问题。更为重要的是，采用现有的相似度计算方法对此填充矩阵进行项目(用户)相似度计算时，所得结果的可信度不高。

用户-项目矩阵如表1所示。

表1 用户-项目矩阵

如果对缺失项不进行填充或者采用平均值填充的方法，在使用相关相似度计算公式计算项目间相关性时(如式(1)所示)，会发现item2和其他项目的相关性无法计算(分子分母同时为0)。

在使用余弦相似性计算方法时(如式(2)所示)，将用户未评分的项目假设为0，会发现item3与item4相似度恒为1,然而item3与item4的实际所得评分差距还是很大的。

所以，基于以上两种的填充方法都不能得到令人满意的效果。

3 文中方法

3.1 方法思路

针对现有的预处理方法在处理稀疏数据集时往往只是利用已有的用户评分数据进行简单的填充，却没有利用数据自身特征属性的问题，文中所提方法充分利用特征属性隐含的潜在价值，从相似度计算和填充方法这两个角度出发，提出了基于项目特征属性的稀疏数据预处理的混合填充预处理方法，具体包括项目特征属性相似度计算和数据混合填充两个步骤。

在任何商务领域，任意项目往往可以用若干个特征属性来表示：电影可以通过战争、喜剧、文艺等属性进行分类；商品则可以通过电器、食物、书籍等属性进行分类。这些属性信息可以从项目所属的网页或者推荐系统中用来记录项目信息的数据集里抽取得到。

对此，为充分利用项目的特征属性以及避免均值填充法和众数填充法所带来的问题，文中提出了一种新的数据填充方法，即结合项目自身的特征属性，利用从这些属性计算中所获得的未评分项目的预测值结合项目均值对稀疏矩阵中未评分项进行混合填充(hybrid filling)。实验结果表明，该混合填充方法无论是在预测精度或者推荐项目的覆盖率方面，相对上述两种方法，都有明显的改善。

3.2 方法描述及流程

方法步骤如下所示：

(1)根据提取到的项目特征属性信息，建立如表2的项目-特征属性矩阵I-F。

(2)对不同的特征属性赋予不同的权值，利用式(2)计算项目间特征属性相似度，得到项目属性相似度矩阵simf。

假设项目特征属性矩阵如表2所示。其中，0表示项目不具有某项属性，1表示项目具有某项属性。

表2 项目特征属性矩阵

(3)选取一定的阈值。得到满足阈值的目标项目i的相似项目，进而得到用户u在用户-项目评分矩阵中已评分的数据集合R以及对应的特征属性相似度值集合W。

由于每个项目是多标签的，几乎项目间都具有较强的相关性，所以阈值的选定对于稀疏数据集的填充很关键。文中阈值选取0.9，只有相似度值大于0.9的项目才能作为目标项目i的相似项目。

(4)计算未评分项目的预测评分。

由第三步可以得到所有未评分项目在用户-项目矩阵中的评分数据集，通过式(3)计算出每个未评分项目的预测评分。其中，ru,j∈R，wi,j∈W。

(3)

(5)结合项目平均值，对稀疏数据集中的未评分项目进行混合填充。

由于用户-项目数据集的极度稀疏性，可能获取的目标项目i的相似项目的已评分值集合R是空集。对此，采用评分均值来填充，得到用户u对项目i的评分，如式(4)所示：

(4)

最终，可以得到一个完整的用户-项目评分矩阵U-I，再对矩阵U-I使用式(1)计算项目间的相关性，得到项目评分相似度矩阵simr，再将simr与simf组合后的相似性作为项目i，j的最终相似性。组合如公式(5)所示：

(5)

(6)

最终，可以得到对用户u的所有项目的预测评分，并对预测评分进行排序，选择分值较高且用户实际未评分的项目向用户进行推荐。

4 实 验

4.1 数据集及实验环境

文中实验数据采用的是Minnesota大学(美国)提供的Movielens数据集[20]，其中包含了943名用户对1 682部电影的100 000条评分数据，其数据稀疏度为0.94。该数据集已经在推荐系统中得到了广泛的使用和测评。

Movielens数据集一共有三个数据集合：电影的属性描述集合、评分用户的个人信息集合以及用户对电影的评分集合。文中用到了第一和第三个集合。电影的属性描述集合记录了电影的名称、发行日期、电影所属类别(喜剧、战争等)。文中所用到的特征属性可以从这个集合中提取。用户对电影的评分集合记录了用户对电影的评分和时间戳。评分分值是从1到5的整数并且每个用户都评价了至少20部电影，每部电影至少都有一次以上的评价。整个数据集按8∶2的比例分成训练集和测试集，训练集数据作为算法输入，而测试集用于测试改进后的算法性能。

算法的实验环境：R语言编程软件Rgui。

4.2 衡量指标

文中主要采用推荐的质量即精度(MAE)和推荐的范围即覆盖率(coverage)作为主要衡量指标，并分析了在邻居个数固定情况下推荐数目对覆盖率的影响。

(7)

(8)

式中，I代表电影的总数。

4.3 实验结果及分析

为了检验文中算法的有效性，将混合填充方法和传统的对未评分项不进行填充(non filling)以及对未评分项进行众数填充(mode filling)的方法作比较。由于式(5)中的w为设定的用于调节项目相似性的平衡参数，所以w的取值对系统的推荐精度有影响。先计算在相同邻居个数下不同w值对两种算法的MAE值的影响，这里，设定邻居个数k为10。实验中w的取值从0.1到1，每次增加0.1，观察w的变化对推荐系统效率的影响。实验结果如图1所示。

图1 参数w对MAE的影响

从图中可以看到，当w的取值从0.1到1时，文中提出的hybridfilling所获得的MAE值远低于nonfiling以及modefilling。当w取0.9时，三种方法的MAE都取得了最小值。再分析当w取0.9，推荐个数取10时，邻居个数对推荐系统质量的影响。图2为邻居个数k从3增加到18，间隔为3时，三种方法的MAE值。

图2 邻居个数k对MAE的影响

由图2可知，当推荐个数和w取值固定时,邻居个数k从3增加到18的过程中，文中提出的hybridfilling相比于nonfilling和modefilling均具有最小的MAE值。再分析当w取值固定(0.9)和推荐个数为10时，三种方法的推荐覆盖率(coverage)，如图3所示。

由图3可知，文中方法的推荐覆盖率相比于其他两种方法有了明显的提高。

传统的对稀疏数据集缺失项不进行填充以及赋予固定缺省值的方法，在数据矩阵极度稀疏的情况下，会使得大部分项目的相似项目无法计算或者都是相同的，故而会影响推荐的覆盖率，而混合填充方法则主要利用由项目的特征属性得到的预测值来填充，这会使得为同类型项目推荐更多相似的同类型项目，故而提高了推荐的覆盖率。

图3 邻居个数k对推荐覆盖率的影响

再分析w、k的取值固定时，推荐个数对推荐覆盖率的影响(w取0.9，k取10)，结果如表3所示。

表3 推荐个数对推荐覆盖率的影响 %

从表3可以看出，推荐个数越多，推荐的范围就越广，推荐的覆盖率就越高。故而三种方法的推荐覆盖率随着推荐个数的增加而增大。

由上可知，文中所提出的混合填充方法，相比于对缺失项不作填充以及采用“众数填充”的方法，有效提高了推荐系统的推荐质量和推荐的覆盖率。

5 结束语

针对协同过滤算法的稀疏性问题，文中给出了一种新的填充方法，即充分利用由项目自身的特征属性得到的预测值并结合项目均值对稀疏数据集进行混合填充处理，使用户-项目评分矩阵得以饱和。通过实验验证了该方法相比于传统的对缺失值不作处理以及对缺失值赋予固定缺省值的方法，无论是在推荐精度亦或是推荐的覆盖率方面都有明显的改善。下一步的工作将侧重于对协同过滤算法进行改进，以提高推荐算法的质量、效率。

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

[2]ConnerM,HerlockerJ.Clusteringitemsforcollaborativefiltering[C]//ProceedingoftheACMSIGIRworkshoponrecommendersystems.[s.l.]:ACM,2001.

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

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

[5]SarwarB,KarypisG,KonstanJ,etal.AnalysisofrecommendationalgorithmsforE-commerce[C]//ProcofthesecondACMconferenceonelectroniccommerce.NewYork:ACMPress,2000:158-167.

[6]LeeJS,JunCH,LeeJ,etal.Classification-basedcollaborativefilteringusingmarketbasketdata[J].ExpertSystemwithApplications,2005,29(3):700-704.

[7]ResnickP,IacovouN,SuchakM,etal.Grouplens:anopenarchitectureforcollaborativefilteringofnetnews[C]//Proceedingofthe1994ACMConferenceoncomputersupportedcooperativework.NewYork,USA:ChapelHillPress,1994:175-186.

[8]BresseJ,HechermanD,KadieC.Empiricalanalysisofpredictivealgorithmsforcollaborativefiltering[C]//Proceedingofthe14thconferenceonuncertaintyinartificialintelligence.[s.l.]:[s.n.],1998:43-52.

[9]LindenG,SmithB,YorkJ.Amazon.comrecommendationsitem-to-itemcollaborativefiltering[J].IEEEInternetComputing,2003,7(1):76-80.

[10]MarlinB.Modelinguserratingprofilesforcollaborativefiltering[C]//Advancesinneuralinformationprocessingsystems.Toronto,Canada:MITPress,2003.

[11]DelgadoJ,IshiiN.Memory-basedweighted-majoritypredictionforrecommendersystems[C]//ProceedingofACMSIGIR’99workshoponrecommendersystems.UC,USA:BerkeleyPress,1999:251-257.

[12]SarwarB,KarypisG,KonstanJ,etal.Item-basedcollaborativefilteringrecommendationalgorithms[C]//Procofthetenthinternationalconferenceonworldwideweb.NewYork:ACMPress,2001:285-295.

[13] 张忠平,郭献丽.一种优化的基于项目评分预测的协同过滤推荐算法[J].计算机应用研究,2008,25(9):2658-2660.

[14] 徐 翔,王煦法.协同过滤算法中的相似度优化方法[J].计算机工程,2010,36(6):52-54.

[15]DasuT,JohnsonT.Exploratorydatamininganddatacleaning[M].[s.l.]:WileyPress,2003.

[16] 余 刚,王知衍,邵 璐,等.基于奇异值分解的个性化评论推荐[J].电子科技大学学报,2015,44(4):605-610.

[17] 霍淑华,杜永萍,黄 亮,等.融入用户与物品特征信息的动态RSVD算法[J].山西大学学报:自然科学版,2015,38(1):24-30.

[18] 孙小华,陈 洪,孔繁胜.在协同过滤中结合奇异值分解与最近邻方法[J].计算机应用研究,2006,23(9):206-208.

[19] 夏建勋,吴 非,谢长生.应用数据填充缓解稀疏问题实现个性化推荐[J].计算机工程与科学,2013,35(5):15-19.

[20]LeeH,KwonJ.SimilarUserclusteringbasedonMovieLensdataset[J].AdvancedScienceandTechnologyLetters,2014,51(8):32-35.

Collaborative Filtering Recommendation Algorithm Based on Sparse Data Pre-processing

CHEN Zong-yan1,2，YAN Jun1,2

(1.College of Communication & Information Engineering，Nanjing University of Posts& Telecommunications，Nanjing 210003，China；2.Key Lab of Broadband Wireless Communication and Sensor Network Technology of Ministry of Education,Nanjing 210003,China)

With the continuous expansion of recommender systems,the sparsity of the user-item matrix can deteriorate the performance of the traditional similarity calculation based collaborative filtering recommendation approaches.In order to overcome this drawback,a new sparse data pre-processing algorithm based on item feature is proposed to mitigate this effect.First,considering the item characteristics information,the ratings of the unrated items are predicted through the similarities between each item.It can lead to saturated matrix and overcome the drawback of the sparsity matrix.Next,the hybrid filling method is utilized to process the unrated items in the sparse data sets,which can avoid the problem of full no consistency of different items for traditional mean-filling method and the multiple mode and no mode for the mode-filling approaches.The simulation demonstrates that the proposed algorithm can improve the recommended quality and coverage dramatically.

recommender system；collaborative filtering；item characteristics；sparse data set；hybrid filling

2015-10-24

2016-01-27

时间：2016-06-22

国家自然科学基金资助项目(61372122)

陈宗言(1991-),男,硕士研究生,研究方向为大数据挖掘；颜 俊,副教授,博士,研究方向为数据挖掘、压缩感知技术及其应用。

http://www.cnki.net/kcms/detail/61.1450.TP.20160622.0844.026.html

TP311

A

1673-629X(2016)07-0059-06

10.3969/j.issn.1673-629X.2016.07.013