基于用户的优化协同过滤推荐算法*

卫 泽 周登文

(华北电力大学控制与计算机工程学院 北京 102206)

基于用户的优化协同过滤推荐算法*

卫 泽 周登文

(华北电力大学控制与计算机工程学院 北京 102206)

针对传统的协同过滤推荐算法存在的用户邻居集选择不准确问题,论文提出了一种优化的协同过滤推荐算法,选择用户的共同评分数据计算用户的相似性,同时考虑共同评分数据中用户对项目评分的一致性,构造评分一致矩阵,将用户评分一致次数与评分项目数之比作为惩罚函数引入到相似度的计算中,缓解相似度计算值与实际值出现的偏差。实验表明,提出的优化算法显著提高了预测的准确性,从而提高了推荐质量。

邻居集; 协同过滤; 一致矩阵; 相似度

1 引言

随着信息技术和互联网的发展,人们逐渐从信息匮乏的时代进入到信息过载的时代。在这个时代,无论是信息消费者还是信息生产者都遇到了极大的挑战:作为消费者,如何从大量信息中找到自己感兴趣的信息是一件非常困难的事;而作为生产者,如何让自己的信息脱颖而出,受到广大用户的关注,同样是一件困难的事。推荐系统就是为解决这一问题而提出的智能代理系统,能从大量信息中推荐符合用户兴趣偏好的资源[1]。推荐系统就是联系用户和信息,一方面帮助用户发现对自己有价值的信息,另一方面让信息展示在对其感兴趣的用户面前,从而达到消费者和生产者的双赢。电子商务是推荐系统的一大应用领域,著名的亚马逊是个性化推荐系统的积极应用者和推广者。电子商务推荐系统可以基于销售排行和用户对商品的评分等来进行推荐[2]。评分直接反映了用户对商品的喜好程度。协同过滤算法正是利用户对商品的评分数据来进行推荐。至今为止,协同过滤算法仍是电子商务推荐系统中应用最成功的推荐技术之一[1～3]。

现有的协同过滤推荐算法可以分为三个子类: 1) 基于用户的推荐(User-based Recommendation)算法[4],该算法根据所有用户对物品的偏好,发现与当前用户偏好相似的“邻居”用户群,为当前用户产生推荐,它的基本假设是:喜欢类似物品的用户可能有相同或者相似的偏好; 2) 基于项目的推荐(Item-based Recommendation)算法[5～7],使用所有用户对物品的偏好发现物品之间的相似度,然后根据用户历史偏好信息,将类似物品推荐给用户; 3) 基于模型的推荐(Model-based Recommendati-on)算法[8～9],利用样本的用户喜好信息,训练一个推荐模型,然后进行预测,计算推荐。已有研究指出,基于近邻算法能获得更好地推荐准确率,但是无法解决由数据量激增带来的可伸缩性问题[2];基于模型的算法有更好的伸缩性,但是由于模型不能表现用户兴趣多样性,因此在推荐质量方面不如基于近邻的算法[10]。

2 传统的协同过滤推荐算法

基于用户的协同过滤一般需经过:收集用户偏好、找到相似的邻居用户、计算推荐三个步骤,如何收集用户的偏好信息成为系统推荐效果最基础的决定因素[10]。用户有很多方式向系统提供自己的偏好信息,主要分为显式(如评分)或隐式(如购买),显式反馈能明确表示用户对物品喜好的程度。要对目标用户产生推荐,首先需要找到和目标用户相似的用户集合,找到这个集合中用户喜欢的,而目标用户没有听说过的物品推荐给目标用户,由此可见,算法的核心就在于如何寻找相似用户,一般通过用户之间的相似度来度量。选择合适的相似度计算方法可以明显提高推荐系统的精度。

在协同过滤推荐算法中,用户评分数据包含m个用户的集U={u1,u2,…,um}和n个项目的集合I={i1,i2,…,in},用户对项目的评分数据可表示为矩阵R(m,n),如表1所示。

表1 用户-项目评分矩阵R(m,n)

其中,Rui、Rvi分别表示用户u、v对项目i的评分,用户u和v的相似度记为sim(u,v),用户u,v在项目集合I上的共同评分集表示为Iuv={i∈I|Rui≠0∩Rvi≠0}(I为全部项目集)。Rmn表示用户m对项目n的评分。评分表示用户对项目的感兴趣程度,评分越高,表示用户越感兴趣。为了获得更高的推荐效率,更准确的推荐结果,最重要的一步是获得目标用户的相似用户集。相似用户集合的准确性直接影响对目标用户最终预测的准确性。传统的相似性计算方法分为:余弦相似度、修正的余弦相似度和Pearson相关系数[3]。目前,最常用的相似度计算方法是Pearson相关系数计算方法。

2.1 相似度的计算

1) 余弦相似性(Cosine Correlation)

用余弦相似性计算相似度,速度快,实现简单,但是没有考虑用户评分尺度的问题,导致计算出的邻居数据不够准确。

(1)

2) 修正的余弦相似性(Adjusted Cosine Correlation)

修正余弦相似性相对余弦相似性考虑了用户评分尺度问题,可表示为如下公式:

(2)

3) Pearson相关相似性(Pearson Correlation)可由如下公式计算得到:

(3)

根据上一步计算得到的相似度,找到目标用户最近邻居集合V={v1,v2,v3,…,vm}。

2.2 预测评分并产生推荐

根据目标用户的最近邻居集合对项目的评分信息来预测目标用户对其未评分项目的评分,并产生TopN推荐。用户u对未评分项目i的预测评分Pui可通过u的邻居集合Su(即V)对i的评分得到,可通过如下公式计算:

(4)

3 优化的协同过滤推荐算法

3.1 问题描述

2.1节中传统的相似用户的计算只针对用户评分的相似性计算,两两用户共同购买项目的评分能够反映用户之间的相似度,但是,两两用户对于相同项目的评分如果一致,理论上可以认为该用户对之间的相似度更高。2.2节提到的最近邻的选取,怎样选取最好的邻居,每个邻居的评分有多重要,邻居的权值选择是提高协同过滤算法精度的重要组件。本文将用户对共同项目评分一致的次数及用户对项目评分的总次数作为惩罚函数引入传统的相似度计算中,对共同评分项目极少情况下的相似度计算进行平滑,从而降低过度估计带来的影响,提高相似度的准确性。Pearson相似度计算没有考虑用户间重叠的评分项数对相似度的影响。本文提出的算法考虑到用户在共同评分项目上评分一致的次数,对于相似度的影响,进而构造出评分一致矩阵,用于修正用户相似度的计算。

3.2 用户相似性

定义二维int型数组(维度是5*5),它存储了两个用户在评分上的一致性。假定用户U与V都对10个项目进行了评分,(评分标准为1～5分)其中对6个项目的评分一致,而其余的都不同。开始这个矩阵的所有单元都被初始化为0;对于两个用户对同一条目的评分,在分值对应的行与列中加1。所以,如果三个一致性的评分是4分,另三个是5分,就可得到matrix[3][3]与matrix[4][4]都是3。只要把matrix矩阵对角线的元素加起来,就能得到两个用户评分一致的次数。

修正后的相似度计算公式如下所示:

(5)

其中,c(u,v)表示用户u和v之间在共同评分项目上评分一致的次数,N(u)与N(v)分别表示用户u与用户v对所有项目的评分次数。

3.3 相似性邻居的选取

邻居的选择是预测目标用户的评分的重要一步,如果选择的邻居用户和目标用户不相似,结果会导致目标用户的预测评分不准确。Herlocker等最早提出了用户相似性调整参数和邻居用户的选取阈值,并通过实验证明引入这些参数后提高了推荐准确度[11～12]。所以本文引入θ来限定用户相似邻居的选取,θ的取值决定了相似性邻居用户集合的个数,只有相似性邻居和目标用户的相似度大于θ,才将此邻居作为目标用户的相似性邻居。可表示如式(6)所示:

S(u)={v|Sim′(v,u)>θ,v≠u}

(6)

其中,S(u)表示目标用户u的相似性邻居集合,θ表示相似性邻居用户选取的阈值Sim′(v,u)的计算采用式(5)来计算。

4 实验结果及分析

4.1 数据集

本文数据集来源于公开可用的MovieLens项目的电影数据集,MovieLens项目是明尼苏达州立大学GroupLens研究组提供的。MovieLens提供了三种不同数量级的数据集,具体参数如表2所示。

表2 三种规模数据集

4.2 评价标准

推荐系统多采用准确度来对算法的好坏来进行评价[4]。准确度是衡量推荐算法预测用户对项目的评分与用户实际对项目的评分的相似程度,通常采用平均绝对误差(MAE)来度量推荐算法的准确度。MAE是一个简单却鲁棒的用于评估推荐精度的技术,计算的是预测评分与实际评分差的绝对值。MAE越小,则推荐精度越高。用户u的平均绝对误差MAEu计算如式(7)所示:

(7)

4.3 仿真分析

图1 本文算法与传统相似性算法推荐精度比较

为了验证本文推荐算法的准确性,对传统的User-based协同过滤算法与本文提出的基于评分一致的优化协同过滤算法进行比较分析,相似性度量方法选用Pearson相关系数,实验参数θ设置为0.5。计算推荐算法的MAE邻居个数从5增加到50,间隔为5。实验结果如图1所示。

由图1可看出,在邻居数不同的条件下,本文提出的基于评分一致的优化协同过滤算法均具有最小的MAE值。

5 结语

本文在传统的基于用户的协同过滤算法中,对邻居权重的选择使用惩罚函数来缓解对于相似度过于估计所带来的影响,从而降低相似度计算值与实际值出现的偏差,提高算法的推荐精度。

在MovieLens数据集上进行的实验,结果表明本文提出的基于评分一致优化协同过滤算法的预测准确率相对于传统的协同过滤算法,可以获得更好的推荐质量。

[1] 王国霞,刘贺平.个性化推荐系统综述[J].计算机工程与应用,2012,48(7):66-76. WANG Guoxia, LIU Heping. Survey of personalized recommendation system[J]. Computer Engineering and Application,2012,48(7):66-76.

[2] 游文,叶水生.电子商务推荐系统中的协同过滤推荐[J].计算机技术与发展,2006,16(9):70-72. YOU Wen, YE Shuisheng. A Survey of Co-llaborative Filtering Algorithm Applied in E-commerce Recommender System[J]. Computer Technology and Development,2006,16(9):70-72.

[3] 奉国和,梁晓婷.协同过滤推荐研究综述[J].图书情报工作,2011,55(16):126-130. FENG Guohe, LIANG Xiaoting. Review of Collaborative Filtering Recommender[J]. Libraryand Information Service,2011,55(16):126-130.

[4] Goldberg D, Nichols D, Oki B M, et al. Using collaborative filtering to weave an information Tapestry[J]. Communications of ACM,1992,35(12):61-70.

[5] Sarwar B, Karypis G, Konstan G, et al. Item-based collaborative filtering recommendation algorithms[C]//New York: Proc. of World Wide WebCon,2001:285-295.

[6] Linden G, Smith B York, J. Amazon.com.recommendations:Item-to-item collaborative filtering[J]. IEEE Internet Computing,2003,7(1):76-80.

[7] Y. peng, X.P. Cheng. Item-based Collaborative Filtering Algorithm Using Attribute Similarity[J]. Computer Engineering and Applications,2007,43(14):144-147.

[8] Liu H. A new user similarity modelto improve the accuracyof collaborative filtering[J]. Knowledge-based System,2014,15(2):156-166.

[9] Y.L. Zhuang. A Collaborative Filtering Recommendtion Algorithm Based on the Model of Items’ Features[J]. Computer Applications and Software,2009,5(26):244-246.

[10] ADOMAVICIUS G, TUZHILIN A. Toward the Next Generation of Recommender Systems: A Survey of the State-of-the-Artand Possible Extensions[J]. IEEE Trans. Knowl. Data Eng,2005,17(6):734-749.

[11] Herlocker L J, Konstan A J, Riedl T J. Empiricalanalysis of design choices in neighborhood-based collaborative filtering algorithms[J]. Information Retrieval,2002,5(4):287-310.

[12] Herlocker L J, Konstan A J, Terveen G L, et al. Evaluating collaborative filtering recommender system[J]. ACM Transaction on Information Systems,2004,22(1):50-53.

Collaborative Filtering Recommendation Optimization Based on User

WEI Ze ZHOU Dengwen

(Department of Computer Science and Technology, North China Electric Power University, Beijing 102206)

In order to improve accuracy of the traditional collaborative filtering algorithm select user neighbor set, this paper proposes an improved collaborative filtering recommendation algorithm. The algorithm selects the user common rating data to calculate the user’s similarity, also considers the consistency of the score data, constructes evaluation matrix, and alleviates the similarity calculation value and actual value deviation by user rating consistent times thanratingitem number as a penalty function is introduced into the similarity calculation. Experimental results show that the improved algorithm proposed in this paper significantly increases the prediction accuracy, so as to improve the quality of recommendation.

neighbor set, collaborative filtering, consistent matrix, similarity Class Number TP301.6

2016年10月10日,

2016年11月14日

国家自然科学基金项目(编号:61372184);北京市自然科学基金项目(编号:4162056)资助。

卫泽,男,硕士,研究方向:推荐算法,数据挖掘。周登文,男,硕士生导师,研究方向:计算机视觉,图像处理。

TP301.6

10.3969/j.issn.1672-9722.2017.04.003