201 1年第2O卷第11期 http://www.c—S—a.org.cn 汁算机系统应用 基于用户行为与角色的协同过滤推荐算 李幼平 ,一,尹柱平 f桂林航天工业高等专科学校,桂林541004) (桂林电子科技大学商学院,桂林541004) 摘要:针对传统协同过滤推荐算法中以稀疏评分讨‘算用户相似性可能并不准确的问题,提出以用户行为对应 一定分值填补空缺的I.u评分矩阵,并以分角色下的权重系数K约束用户相似性计算的改进协同过滤推荐算法。 实验表明,改进算法的推荐质量更高。 关键词:协同过滤;I.u评分矩阵;相似性计算;用户行为;用户角色 Collaboratix e Filtering Recommendation Algorithm Based on Users’Behavior and Roles LI You.Ping .YIN Zhu—Ping (Guilin College ofAerospace Technology,Guilin 541004,China) (School of Business,Guilin University of Electronic Technology,Guilin 54 1 004,China) Abstract:There are sparse ratings problem in the traditional CF recommendation algorithm,and based on this sparse ratings will lead to the fact that the similarity may not be accurate.For this reason,a CF algorithm based on fixed I-U ratings matirx,which is given by a certain ratings of user behavior instead of vacancies rating,and weighted coefifcient K bases on users’role to constrain the similarity calculation is proposed.Experiments show that the improved algorithm has better recommendation quality. Key words:collaborative filtering;I-U score matrix;similarity calculation;users’behavior;users’role. 协同过滤推荐算法(collaborative filtering recom 算法的准确性。故本文提出了一种改进的协同过滤推 mendation algorithms)是目前应用和研究最为广泛的 荐算法。并通过验证实验表明本算法有更高精确度。 推荐技术之一(¨,它根据用户对项的I—u评分矩阵来计 算用户的相似度,从而产生目标用户的最邻近用户集, 1基于用户行为与角色的推荐算法 通过这一集合中用户对项的打分预测产生目标用户对 1.1问题的提出 未知项的打分,取预测打分最高的首选若干项作为结 传统协同过滤推荐算法基于以下假设:如果用户 果推荐给用户。它可忽略项目对象本身的内容问题, 对一定项的打分较相似,则他们对其他项的打分也较 能应用在可计算的文本领域和非结构化的电影、音乐 相似。它是以用户对项打分的I.u评分矩阵作为学习 和图书等复杂对象领域【 。这一推荐如同现实中的口 用户偏好并产生推荐的基础,但用户的打分常常十分 碑,不局限于用户原有的感兴趣内容,可发现用户可 稀疏。 能感兴趣的新内容。 事实上,用户对项的打分作为对资源项的偏好表 形成用户的最邻近用户集是协同过滤推荐算法中 达,但同时,用户的系统行为也是对偏好的表达。以 最为关键的_。。步【引,但传统协同过滤推荐算法存在稀 用户的浏览、点击作为一个基本偏好的筛选过程。以 疏性问题,用户对资源项的打分非常稀疏,以稀疏的 用户的“收藏”操作表明对某一信息资源的关注,并 打分产生用户间的相似性可能并不准确,从而影响了 存在针对这…资源的偏好。用户查询则是对自身偏好 ①收稿时间:2011-03.17;收到修改稿时f ̄:2011-04—11 Research and Development研究开发103 计算机系统应用 http://www.c—s—a.org.ca 2011年第2O卷第1l期 资源的明确查找。在系统中以日志方式记录用户行为, 其中,C.f,为用户i和j共同评分项的交集,C.f+C, 为用户已评分项的并集。 1.2基于用户角色和行为的改进算法过程 并以1~4的分值与上述用户行为对应,以此填补并修 正I—U评分矩阵。 在得到用户对项的直接打分和通过用户行为填补 传统协同过滤推荐算法过程有三个阶段【 】:建立 I—u评分矩阵,计算用户相似度并产生目标用户的最邻 评分数据后,协同过滤推荐算法将预测用户对未打分 的未知项的打分,以此产生推荐。其中,较典型的是 slope one算法【4l,它是以用户共同打分项的打分情况 猜测用户对目标未打分项的打分:假定存在用户x, Y和A都已对Item 1打分,且用户X,Y也对Item2 打分,如表1: 表1用户评分表 \ atm.g u \\ Item1 Item2 X 5 3 Y 4 3 A 4 口● 那么根据Slope One算法,用户A对Item2 J打 分为:4-[(5—3)+(4-3)]/2=2.5。 但在slope one算法中,默认了用户对Item2的打 分倾向是相似甚至是相同的,显然,在评分数据稀疏 时这种倾向并不存在。同时,slope one算法容易陷入 一个逻辑的死循环,计算用户的相似性并预测评分是 根据相似用户的评分来计算,即默认了用户之间是相 似的,是可允许通过其他任意用户的打分来预测评分。 但如果x、Y和A之间的打分倾向是不一样的,这个 式子就不成立了。包括加权slope one算法,仍依据这 一默认的假设。 故本文认为,在计算用户相似性时,要考虑影响 用户偏好或评分倾向的一些重要而稳定的属性。根据 这种在用户自身明确而稳定的属性对用户群进行划 分,由此产生的用户群称之为角色。因而同一角色下 用户具有较好的关联和相似的偏好特征,从而具有相 同的打分倾向。 以这一思想,定义约束权重系数K来计算用户相 似度sim。相同角色时,K为1;不同角色时,取用户 之间评分的项的交集比例来作为K的值,。在多评分 数据下,两用户即使角色不同,如果共同评分项较多, K也越接近1,同样可成为相似用户。则权重系数K 的计算式为: I1,相同用户角色 一 l /( + ),不同用户角色 (1) 1 04研究开发Research and Development 近用户集,预测评分产生推荐项集。基于传统算法, 改进算法的过程描述如下: 第一阶段:建立以用户行为填补的修正I.u评分 矩阵。 统计用户对项的评分形成了I.U评分矩阵,它是 计算用户相似性的重要数据源。在m个用户对n个项 进行打分的基础上,以用户行为对应一定分值填补部 分空缺项的打分,建立修正的I-U评分矩阵。 第二阶段:依靠用户角色,基于约束系数K的最 邻近用户集的形成。 度量用户相似性的方法主要有余弦相似性、相关 相似性、以及修正的余弦相似性三种。本文应用基于 皮尔逊相关系数(Pearson Correlation)并能度量两组 用户评分数据线性关系的相关相似性度量法【6】,具体 计算公式为: 砌蚴= 畸 屿 -2(2) 其中,I。为已打分项a,Iii为用户i和J均已打分的项 集,.Ria表示用户i对项目a的打分, 表示用户J对 项目a的评分, ,, 表示用户i和J的平均评分。 计算任意用户之间相似约束系数K的值,并以式 (2)计算用户相似性时加入约束系数K进行加权,以 代替 ,以KRjo代替 ,得到式: ∽= q( )c 一尼-)/J 畸(巩 )2× 畸( 一 )2(3) 计算得到用户相关系数后,设定一个阈值 ,把 满足sim(i,J)>0的相似度以Top-N排序,产生最邻近 用户集V。 第三阶段:生成预测评分和推荐项。 由集v中用户对当前项i的打分,采用平均加权 法来计算预测打分并产生推荐结果,则用户u对目标 项目i的预测打分 计算式为L7J: ,=Ru+[∑ ,sim(u,v)×( 一 )/∑ ( ,v)I](4) 其中, 为用户U对所有项打分的均值,sim(u,v)表 示用户u,v的相似度,R 表示最近邻用户集中的用 户v对项i的打分, 为项v的平均打分。 2011年第20卷第11期 http://www.c—S—a.org.cn 计算机系统应用 对 ,进行Top—N排序,推荐前N项给用户。 3.2推荐算法质量的度量指标 本文采用常用的统计精度度量方法中的平均绝 对误差MAE(Mean Absolute Error)作为度量指标。当 MAE值越小,推荐的质量越好。MAE是用于计算 2改进的CF算法描述 输入:m个用户对n个项的打分,用户行为产生 对项的填补打分,I.u评分矩阵;分角色用户相似度 sie,用户评分项的并集和共同评分项的交集,相似 r推荐的预测评分值和用户真实评分值之间的偏离程 度【9l,它的计算公式为: 阈值0,推荐首选项数N。 输出:用户的Top.N推荐。 算法过程: 1)根据用户行为以相应分值修正用户的I.u评分 矩阵。 2)计算任意用户之间相似约束系数K的值,根据 式(3)计算用户i和J的相似度sim(i, ),比较sim(i, )与 0大小,把满足sim(i, )>0的相似度以Top—N排序, 产生最邻近用户集v。 3)由集V中用户对当前项i的评分,根据式(4) 计算目标用户U对项i的预测评分 。 4)对 进行Top-N排序,推荐前N项给用户。 3验证实验结果 3.1测试数据集 从http://www.grouplens.org/node/73下载Movie Lens提供的公共测试数据集million.m1.data来验证算 法的有效性。该数据集由6040个用户对3900部电影 评价打分产生的约100万个评分数据,它含有三个数 据表,分别为用户信息表(users)、电影信息表(movies) 和评分信息表(ratings)。其中用户信息表包含角色划 分的职业类型属性。 为了测试本文提出的基于角色划分的协同过滤推 荐算法的有效性,实验共进行两次,分别选择用户信 息表中以职业(Occupation)代号为7的行政管理者 fexecutive/manageria1)和1 7的技术工程fJ ̄(technician/ engineer)的所有用户进行相关数据测试。虽然通过用 户的职业属性在一定程度上缩小了测试数据集,但分 析在传统算法下的推荐数据情况,满意的推荐结果较 集中在相同背景下的用户之间,因而是不影响检验算 法的有效性。另值得指出的是,划分用户集能有效降 低计算的时耗。 在进行测试实验时,要进行数据的稀疏度计算I8】J 低稀疏度的数据产生的预测评分才是可靠的。 稀疏度=所有已评分值的项数/f用户数×资源数) (5) MAE=[∑n- Pi-q I]/n 其中,P 为用户的预测评分值,q 为用户的实际评分 值,n为预测项的个数。 3.3实验结果 通过Excel表格和Access数据库对数据进行预处 理,把数据以)k--比例分为两部分,80%部分作为训 练base集,20%部分作为测试test集。预处理后数据 样本的格式如下: E 一 《 9 ̄830t368 图I预处理后数据样本的格式 通过数据预处理和统计得到两个测试数据集: 1)职业代码7下的679个用户,涉及3276部电影, 一共有104561个评分数据,数据稀疏度为4.7%。 其中用户最少已评电影2O部,最多1521部。2)职 业代码17下的502个用户,涉及3196部电影,共 72816个评分数据,数据稀疏度为4.5%。其中用户 最少已评电影20部,最多l595部。并进一步统计 各用户的已评项数n和用户的评分均值 。 对测试数据集1和2分别进行预测评分的计算并 计算MAE值,与传统CF算法下的MAE值比较,得 到结果如图2和图3。 两个实验均选取最近邻用户集为10到35个邻居, 间隔为5,从图2与图3可看出本文提出的改进协同 过滤推荐算法具有较小的MAE值,具有更高的推荐 质量。 Research and Development研究开发1 05 计算机系统应用 1.1 htcp://www.C—S—a.org.cn 2011年第2O卷第11期 荐质量。 0.9; — ~参考文献 传统cF 1王茜,杨莉云,杨德礼.面向用户偏好的属性值评分分布协同 I,U 0,S 《 : ’ 州酯一改进cF 过滤算法.系统工程学报,2010,(4):561—568. 2黄晓斌.基于协同过滤的数字图书馆推荐系统研究.大学图 0.7卜 0 6 一一一 …一一一 u--一-r 一一u- 书馆学报,2006,(1):53—57 3 Kin BM,Li Q,Park CS,et a1.A new approach for combining content—based and collaborative filters.Joumalof Intelligent Information Systems,2006,27:79—91. 10 15 2O 2S 30 35 最近邻个数 图2由测试集1得到的MAE值对比 l 1 4周敏,周继鹏,丁光华.PSL:针对大规模数据应用的并行 Slope One算法.科学技术与工程,2010,3:71 1-714. 5 Tin W Xu J,Peand YQ.CF Improvement Based on 传统cF 改进cF 1 0.9 趔 uJ 0.8 《 Probabilistic Analysis of Discrete Explicit Rating Vector. Proc.of the 2009 First IEEE Intemational Conference on Information Science and Engineering,2009,9:814—816. 0.7 0,6 一一~。。…………………~…一…一一。—’…一 6 Sarwar B,Karypis G Konsmn J,et a1.Item-Based Collabo- rative Filtering Recommendation Algorithms.Proc of the lOth Int’1 Wlof1d Wide Web Conf,2001.285—295. 7 Breese J,Heckerman D,Kadie C.Empiical Analrysis of l0 l5 2O 25 30 35 最近邻个数 图3 由测试集2得到的MAE值对比 4结论 与传统协同过滤推荐算法比较,本文提出的改进 协同过滤推荐算法最大不同的是:从评分数据稀疏问 题和产生最近邻的相似性计算出发,讨论了I.u评分 矩阵的修正问题和仅依靠用户打分是否能成为最近邻 的问题,并提出了改进的方法,以用户行为对应分值 Predictive Algorithms for Collaborative Filtering.Proc.of he t14th Conference on Uncertainty in Artiicifal Intelligent. 1998,43—52. 8 Herlocker几,Konstan JA,Terveen LG Evaluating Collabo- rative Filtering Recommendation System.ACM Trans.on Information System,2004,22(1):5—53. 替代的方式修正了I.U评分矩阵并以权重系数K约束 最近邻用户的计算,使得推荐算法能更好的产生最邻 近用户集。实验结果表明,本算法较显著地提高了推 (上接第102页) 9冯克鹏.基于协同过滤的数字图书馆推荐系统研究.软件导 刊,2010,5:16—18. pcs.http://www.microsoft.corn/whdc/winhec/pres06.mspx. 2006. 5 Microsoft.ReadyDrive and hybrid disk.http://www. microsoft.com/whdc/system/sysperf/perfacce1.mspx.2010. 3 Panablaker R.Hybrid Hard Disk&ReadyDriveTM 6 Payer H,Sanvido MAA.Combo Drive:Optimizing Cost and Performance in a Heterogeneous Storage Device.Workshop on Integrating Solid-state Memory into the Storage Hierarchy,2009. 7 http://traces.CS.amass.edu/index.php/Storage/Storage.2007. technology:Improving performance and power for Windows Vista Mobile PCs.WinHEC,2006. 4 Kim YJ,Kwon KT,Kim J.Energy—effcient fie placement techniques for heterogeneous mobile storage systems. EMSOFT Conference.2006. 106研究开发Research and Development