（计算机软件与理论专业论文）协同过滤推荐算法的研究.pdf

中山大学硕士学位论文中文摘要 协同过滤推荐算法的研究 计算机软件与理论 硕士生：陈玲 指导教师：印鉴教授 摘要 近年来，电子商务推荐系统在理论和实践中都得到了很大发展。但是随着电 子商务系统规模的进一步扩大，电子商务推荐系统也面临一系列挑战。在大型电 子商务系统中，用户数目和项数目急剧增加，导致用户评分数据的极端稀疏性， 在这种情况下传统协同过滤算法均存在各自的不足，导致计算得到的目标用户的 最近邻居不准确，推荐系统的推荐质量急剧下降。 针对“新项目”问题，本文提出了在传统协同过滤推荐算法基础上加入 d e m o g r a p h i c 数据进行综合预测的i d e m n n 算法。实验结果表明，i d e m n n 推 荐算法可以解决“新项目”问题，且在用户评分数据极端稀疏情况下如果参数选 取合适可以在一定范围内解决传统算法信息不足导致的问题，提高推荐系统的推 荐精度。此外，本文还针对数据集极端稀疏性问题提出另外一种集成r k n n 信息 的改进算法i r k n n 2 ，实验结果同样表明，该算法比经典协同过滤推荐算法具有 更高的推荐精度，同时比之前提出的i r k n n l 推荐算法的推荐精度也有一定程 度的提高。 关键字：协同过滤推荐算法d e m o g r a p h i c 数据逆k 最近邻居 中山大学硕士学位论文 a b s t r a c t r e s e a r c ho nc o l l a b o r a t i v ef i l t e r i n gr e c o m m e n d a t i o n a l g o r i t h m s c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：c h e nl i n g s u p e r v i s o r ：y i nj i a np r o f e s s o r a b s t r a c t a l t h o u g hr e c o m m e n d a t i o ns y s t e m si ne c o m m e r c eh a v e b e e nv e r ys u c c e s s f u li n b o t hr e s e a r c ha n dp r a c t i c e ，c h a l l e n g i n gr e s e a r c hp r o b l e m sr e m a i n w i t ht h ee x p a n s i o n o fe - c o m m e r c es y s t e m s ，t h em a g n i t u d e so fu s e r sa n dc o m m o d i t i e sg r o wr a p i d l y , r e s u l t i n gi nt h ee x t r e m es p a r s i t yo fu s e rr a t i n gd a t a t h i ss i t u a t i o nm a k e st h eq u a l i t y o fr e c o m m e n d a t i o ns y s t e m sd e c r e a s e sd r a m a t i c a l l y t oa d d r e s st h ei s s u eo fn e wi t e m ，t h i sp a p e rp r o p o s e dac o l l a b o r a t i v ef i l t e r i n g r e c o m m e n d a t i o na l g o r i t h mb a s e do ni t e m r a t i n ga n dd e m o g r a p h i cd a t a ，n a m e l y i d e m n nc fa l g o r i t h m t h ee x p e r i m e n tr e s u l t ss u g g e s t e dt h a tt h i sm e t h o dc o u l d o v e r c o m et h en e wi t e mp r o b l e ma n dt h ee x t r e m es p a r s i t yo fu s e rr a t i n gd a t at oa c e r t a i ne x t e n t ，p r o v i d eb e t t e rr e c o m m e n d a t i o nr e s u l t st h a nt r a d i t i o n a lc fa l g o r i t h m s f u r t h e r m o r e ，t h i sp a p e rs t i l lp r o p o s e dac o l l a b o r a t i v ef i l t e r i n gr e c o m m e n d a t i o n a l g o r i t h mc o m b i n e dw i t ht h ef a c t o ro fr k n n ，c a l l e di r k n n 2c fa l g o r i t h m t h e e x p e r i m e n tr e s u l t sa l s os u g g e s t e dt h a tt h i sm e t h o dc o u l de f f i c i e n t l yo v e r c o m et h e e x t r e m es p a r s i t yo fu s e rr a t i n gd a t aa n dp r o v i d eb e t t e rr e c o m m e n d a t i o nr e s u l t st h a n t r a d i t i o n a lc fa l g o r i t h m sa n di r k n n 1a l g o r i t h m k e yw o r d s ：c o l l a b o r a t i v ef i l t e r i n gr e c o m m e n d a t i o na l g o r i t h m ，d e m o g r a p h i cd a t a ， r e v e r s ek - n e a r e s tn e i g h b o r i i 中山大学硕士学位论文协同过滤推荐算法的研究 1 1背景 第1 章绪论 过去的将近十年中，在信息和通信技术领域发生了一次巨大的发展高潮。全 世界的人能够空前地获得信息、商品，以及互相交流而这一切仅仅在这一代 人之前还是不可想象的。我们现在认为能够上网冲浪、查看电子邮件，以及为在 数百公里以外的家人购买礼物，检查我们银行帐户的收支平衡和最新股市动态都 是非常正常的事，无论是在家里还是在学校或办公室或是在其它的地区出差也可 以同样方便地做这些事情。这其中的每一样活动都留下了电子商务的影子。 1 1 1电子商务 从事电子商务的公司在网络上将货物卖给客户，而客户则直接付钱给他们。 有许多这样的公司，如生产i n t e m e t 设备的思科系统公司( c i s c os y s t e m s ) 是这 一行业中最早成功的企业之一。在2 0 世纪9 0 年代的数年中，思科系统公司革命 性地将其所有的商品搬上了网络进行销售。与此同时，i b m 也改变了自己的个 人计算机市场销售策略，将重点放在了面对客户的直销，而这些销售许多来自于 互联网。亚马逊( a m a z o n ) 创造了世界上最受关注的品牌之一，而这完全是通 过网络实现的。这些公司都意识到通过网络服务于具有技术头脑的客户，能够减 少费用支出并且增加灵活性。 网络所带来的最大变化之一就是速度，客户可以在白天或晚上的任何时间下 订单。更好地理解客户的需要意味着较少的存货，更快的周转意味着更高的利润， 价格可以改变。就每一项本身而言并不是网络所独有的，然而如果三者同时满足 就是一个强有力的组合。尽管在交货方面电子商务显得很慢，但对于大多数用户 来说，他们愿意等待。 因此，网络商务并没有从根本上区别于其它类型的商务。商家仍旧需要管理 存货、制定价格；客户依然是要求优质的服务和低廉的价格；仍然有打折和捆绑 销售，特殊定购和广告以及有目标的通知。 第1 章绪论 1 1 2 电子商务推荐系统 随着互联网的普及和电子商务的发展，电子商务系统在为用户提供越来越多 选择的同时，其结构也变得更加复杂，用户经常会迷失在大量的商品信息空间中， 无法顺利找到自己需要的商品。于是，一些公司开始应用数据挖掘技术来充分利 用日常交易中积累的数据。例如，利用这些数据，他们可以做到以下事情： 1 ) 根据客户己声明的偏好或是观察到的行为，在客户再次光顾该网站时改 变网站的外观； 2 ) 回应客户的订单并在付帐的过程中推荐新的商品；或是从过去的访问记 录中记住客户的爱好，并把这些用于客户当前的访问中； 3 ) 根据客户的偏好和实时的存货控制来关注需求。 试想一下，在每位客户选购或者甚至只是对某些商品表现出兴趣时，就有一 位专业的售货员陪同并提出建议，或者想象一下一个零售商店能够为每位客户重 新布置商品柜台，将客户最可能购买的商品放在客户容易看到的地方，而这些商 品可能刚刚还被放在客户需要一些说服才会购买的商品的后面。因而，再也不会 有为了去拿牛奶而不得不通过肉食品柜台的素食者了。这些革命性的想法使得客 户和零售商同时受益。网络作为一个零售通道，使得这些想法成为可能。 在这种背景下，电子商务推荐系统应运而生。电子商务推荐系统直接与用户 交互，模拟商店销售人员向用户提供商品推荐，帮助用户找到所需商品，从而顺 利完成购买过程。因此在日趋激烈的竞争环境下，电子商务推荐系统可以有效保 留用户，提高电子商务系统的销售；商家也可以通过推荐系统保持与客户的联系， 重建客户关系。 推荐系统主要通过如下三种途径提高电子商务系统的销售能力： 1 ) 将电子商务系统的浏览者转变为购买者：电子商务系统的访问者在浏览 过程中经常并没有购买欲望，电子商务推荐系统能够向访问者推荐他们感兴趣的 商品，从而完成购买过程。 2 ) 提高电子商务系统的交叉销售：电子商务推荐系统在用户购买过程中向 用户提供其它有价值的商品推荐，用户能够从提供的推荐列表中购买自己确实需 要但在购买过程中没有想到的商品，从而有效提高电子商务系统的交叉销售。 3 ) 保留用户：与传统的商务模式相比，电子商务系统使得用户拥有越来越 2 中山大学硕士学位论文协同过滤推荐算法的研究 多的选择，用户更换商家极其方便，只需要一两次鼠标的点击就可以在不同电子 商务系统之间跳转。电子商务推荐系统分析用户的购买习惯，根据用户需求向用 户提供有价值的商品推荐。如果电子商务推荐系统的推荐质量很高，那么用户会 对该电子商务推荐系统产生信赖。因此电子商务推荐系统不仅能要为用户提供个 性化的推荐服务，而且能与用户建立长期稳定的关系，从而能有效保留用户，防 止用户流失。 电子商务推荐系统具有良好的发展和应用前景。目前，几乎所有大型的电子 商务系统，如a m a z o n ，c d n o w ， e b a y ，当当网等，都不同程度的使用 了各种形式的推荐系统。各种提供个性化服务的w e b 站点也需要推荐系统的大 力支持。在日趋激烈的竞争环境下，电子商务推荐系统能有效保留用户，提高电 子商务系统的销售。成功的电子商务推荐系统将会产生巨大的经济效益。 1 1 3 个性化服务 所谓个性化服务，就是在用户浏览w e b 站点时，尽可能地迎合每个用户的 浏览兴趣并且不断调整自己来适应用户浏览兴趣的变化，使得每个用户都有是该 w e b 站点唯一用户的感觉1 】【2 】。电子商务推荐系统使得电子商务系统主动适应每 一个用户的特定需求，为每一个用户创建一个适应该用户的电子商店，从而为每 一个用户提供完全不同的个性化购物体验，因此属于w e b 站点个性化服务的范 畴。 不同电子商务推荐系统的个性化程度各不相同，根据电子商务推荐系统的个 性化程度，可以将电子商务推荐系统分为如下三类【3 】： 1 ) 非个性化推荐系统：电子商务推荐系统对每个用户产生的推荐都是相同 的。这种推荐系统可以基于w e b 站点工作人员的手工推荐，可以基于统计分析 技术等。电子商务系统的销售排行、编辑推荐、平均数值评分、个体文本评价、 个体数值评分等推荐形式对所有的用户而言都是一样的，都属于非个性化电子商 务推荐系统。 2 ) 半个性化推荐系统：电子商务推荐系统根据用户当前的行为产生相应的 推荐。这种推荐系统根据用户当前的浏览行为或用户当前的购物篮信息产生推荐 结果，不同用户得到的推荐结果各不相同。半个性化推荐系统的个性化程度比非 第1 章绪论 个性化推荐系统要高。 3 ) 完全个性化推荐系统：推荐系统保存用户的各种历史信息。如历史浏览 信息、历史数值评分信息、用户注册信息等。然后根据用户的历史信息，结合用 户当前的行为为用户产生完全个性化的推荐服务。这种推荐系统一般只能对注册 用户提供服务，个性化程度最高。 1 2 推荐系统的研究内容和国内外研究现状 1 2 1 推荐系统的研究内容 电子商务推荐系统的研究内容和研究方向主要包括【3 】【4 】： 1 推荐技术研究：目前主要的推荐技术主要包括基于内容的过滤和协同过 滤两种。由于基于内容的过滤自身的局限性【5 1 ，协同过滤推荐技术是当前研究的 主流。 2 实时性研究：在大型电子商务推荐系统中，推荐系统的伸缩能力和实时 性要求越来越难以保证。如何有效满足推荐系统的实时性要求得到了越来越多研 究者的关注。 3 推荐质量研究：在大型电子商务系统中，用户评分数据极端稀疏。用户 评分数据的极端稀疏性使得推荐系统无法产生有效的推荐，推荐系统的推荐质量 难以保证。 4 多种数据多种技术的集成：当前大部分的电子商务推荐系统都只利用了 一部分可用信息来产生推荐。随着研究的深入，新型电子商务推荐系统应该利用 尽可能多的信息，收集多种类型的数据，有效集成多种推荐技术，从而提供更加 有效的推荐服务。 5 数据挖掘技术在推荐系统中的应用：目前，各种数据挖掘技术( 主要包括 关联规则挖掘、序列模式挖掘、聚类分析、b a y e s i a n 分类等) 在推荐系统中得到 了广泛的应用。基于w e b 挖掘的推荐系统得到了越来越多研究者的关注。 6 用户隐私保护研究：由于推荐系统需要分析用户的购买习惯和兴趣爱好， 涉及到用户隐私问题，如何在提供推荐服务的同时有效保护用户隐私值得作进一 步深入的研究。 4 中山大学硕士学位论文协同过滤推荐算法的研究 7 推荐系统可视化研究：推荐系统的目的是为用户提供服务，因此必须为 用户提供友好的可视化服务界面。主要包括推荐结果可视化研究和推荐结果解释 研究等方面的内容。 1 2 2 国内外研究现状 推荐系统中的推荐技术主要包括基于内容的过滤和协同过滤两种。基于内容 的过滤是信息检索领域的重要研究内容【6 】。基于内容过滤的推荐系统需要分析资 源内容信息，根据用户兴趣建立用户档案，然后根据资源内容与用户档案之间的 相似性向用户提供推荐服务。a b b a t t i s t a 等人【7 j 提出使用智能代理技术分析用户 的特定需求，提供推荐服务。 基于内容过滤的推荐技术具有一定的局限性【5 1 。主要表现在必须分析资源的 内容信息，因此对音乐、图像、视频等信息无能为力，无法分析信息的质量，无 法提供新颖的推荐。针对上述问题，研究者提出了协同过滤推荐技术1 8 1 1 9 1 。在早 期的协同过滤推荐系统中，用户之间需要相互了解对方的兴趣爱好【l o 】。随着研究 的深入，研究者提出了自动化协同过滤推荐技术【9 】。 推荐系统的推荐质量是推荐系统成功的关键。协同过滤是至今最成功的推荐 系统技术，并且在网络中许多成功的推荐系统已经得到使用。经典协同过滤推荐 技术根据用户之间的相似性产生推荐结果。k a r y p i s 等人【1 2 】【1 3 1 提出根据项之间 的相似性提供推荐服务，从而有效提高推荐质量。文【1 4 1 提出对用户最近邻居和项 均采用不同权重的方法改进推荐质量。协同过滤推荐技术也存在自身的不足【3 】【4 】。 用户评分数据的稀疏性是导致推荐系统推荐质量下降的主要原因 1 5 】。因此基于多 种数据多种技术的有效集成得到研究者的重视 3 】【4 】。s a r w a r 等人提出使用奇异 值分解技术减少项空间的维数，使得用户在降维后的项目空间上对每一个项目均 有评分，实验结果表明，这种方法可以有效地解决同义词( s y n o n y m y ) 问题，显著地 提高推荐系统的伸缩能力。但降维会导致信息损失，降维效果与数据集密切相关， 在项目空间维数很高的情况下，降维的效果难以保证。d e m i r i z 等人【l6 】提出通过 对稀疏数据的关联分析可以有效提高推荐质量。b a l a b a n o v i c 等人【8 】提出通过基于 内容的过滤和协同过滤的复合型推荐系统提高推荐质量。m o b a s h e r 等人【l 】中提 出基于w e b 使用挖掘和w e b 内容挖掘的推荐系统。文【l7 】中提出在推荐系统中增 第1 章绪论 加产品语义信息，从而提高推荐系统的推荐质量。 邓爱林等人【1 8 】【1 9 】针对用户评分数据极端稀疏情况下传统相似性度量方法的 不足，提出了一种基于项目评分预测的协同过滤推荐算法，根据项目之间的相似性 初步预测用户对未评分项目的评分，在此基础上，采用一种新颖的相似性度量方 法计算目标用户的最近邻居。实验结果表明，该算法可以在一定程度上解决用户 评分数据极端稀疏情况下传统相似性度量方法存在的问题，提高推荐系统的推荐 质量。 b e n j a m i nm a r l i n 在他的硕士论文1 2 0 详细研究了各种协同过滤算法，在他 的实验中，采用k 中心点聚类算法的协同过滤算法取得了较好的结果，而且时 间和空间复杂度都较低。不过，他的论文只研究了纯的、无序的基于评分的协同 过滤推荐算法，没有考虑附加的用户或项目的d e m o g r a p h i c 数据。近年来，m v o z a l i s 和k c tm a r g a r i t i s 2 1 】【2 2 1 已经尝试将d e m o g r a p h i c 信息加入到基于用户和基 于项目的协同过滤推荐算法中，产生足够可信度的改善质量的预测。 1 3 推荐系统面临的挑战 推荐系统在研究领域获得了广泛关注，在实际的电子商务系统中也得到了广 泛应用。但是，随着电子商务系统规模越来越大，推荐系统也面临着一系列挑战， 主要包括3 1 1 4 ： 1 实时性与推荐质量之间的平衡：推荐系统的推荐精度和实时性是一对矛 盾。大部分推荐技术在保证实时性要求的同时，是以牺牲推荐系统的推荐质量为 前提的【1 1 】。在提供实时推荐服务的同时，如何有效提高推荐系统的推荐质量，需 要做进一步深入的研究。 2 新型电子商务推荐系统体系结构研究：当前大部分的电子商务推荐系统 都只是一个单一的工具，只能提供一种推荐模型【1 1 。但由于电子商务系统本身的 复杂性，不同场合需要不同类型的推荐。需要研究新型电子商务推荐系统体系结 构，收集多种类型的数据，提供多种推荐模型，满足不同类型的推荐需求。 3 推荐结果解释研究：电子商务推荐系统为了说服用户，需要向用户解释 推荐产生的原因。目前的电子商务推荐系统只能通过简单的销售排行、向用户提 供其他用户对商品的评价评分信息等方式来达到上述目鲥3 1 1 4 1 。需要进一步研究 中山大学硕士学位论文协同过滤推荐算法的研究 更加有效的方法向用户解释产生推荐的原因，从而增加用户对推荐系统的信任程 度，说服用户听从推荐系统的推荐。 1 4 本文的工作 在大型电子商务系统中，用户数目和项数目急剧增加，导致用户评分数据的 极端稀疏性，在用户评分数据极端稀疏的情况下传统的协同过滤推荐算法均存在 各自的不足，导致计算得到的目标用户的最近邻居不准确，以致推荐系统的推荐 质量急剧下降。针对协同过滤推荐算法存在的新项目问题，本文提出了在传统协 同过滤推荐算法基础上加入d e m o g r a p h i c 数据进行综合预测的i d e m n n 算法。 i d e m n n 推荐算法通过分别计算项之间评分相似性和d e m o g r a p h i c 相似性，找到 目标项目的两个最近邻居群，并由这两个群体分别给出一个预测评分，综合考虑 这两个预测分得出对目标项的最终评分，并在此基础上决定推荐与否。实验结果 表明，i d e m n n 推荐算法可以解决新项目问题，且在用户评分数据极端稀疏情况 下选取合适的参数可以解决传统算法推荐质量低的问题，提高了推荐系统的推荐 质量。此外，针对数据集极端稀疏的问题本文还提出另外一种集成r k n n 信息 的改进算法i r k n n 2 ，这种算法根据评分相似性分别找出目标项目的k 近邻和 逆k 近邻，然后找出这两个邻居集合的交集，并根据用户对交集中项目的评分 预测该用户对目标项目的评分。实验结果表明，i r k n n 2 算法比经典协同过滤推 荐算法具有更高的推荐精度，同时比之前提出的i r k n n l 推荐算法的推荐精度 也有一定程度的提高。 本文共分四章，文章结构及各章内容简介如下： 第一章探讨了电子商务推荐系统提出的背景及其研究意义，介绍了推荐系统 的研究现状，分析了电子商务推荐系统面临的主要挑战，介绍了本论文主要的研 究工作及取得的主要研究成果。最后，给出了本文的整体组织结构。 第二章介绍了目前最成功的推荐技术协同过滤推荐技术及其算法。并详 细介绍了u s e r - b a s e d 协同过滤算法和i t e m b a s e d 协同过滤算法，最后指出传统协 同过滤推荐算法的不足。 第三章提出了集成d e m o g r a p h i c 数据的协同过滤推荐算法i d e m n n ，详细介 绍了该算法的提出背景、算法的详细步骤以及实验环境、实验过程及结果分析。 第l 章绪论 _ _ 一 第四章先介绍了集成r k n n 的协同过滤推荐算法i 砌 p k n n ( q ) 。图4 1 给出 了若干个二维空间数据点的位置。当七= 1 时，删= 倒，删= ，所以 r n n ( p ) = 西。 图4 1k n n 与r k n n 关系示意图 ( 说明：从i 指向j 的箭头表示j 是i 的最近邻居) 4 2 r k n n 在推荐系统中的初步应用i r k n n l 多示例学 - 3 的概念是d i e t t e r i c h 2 7 1 等人于1 9 9 7 年在对麝香分子活性的研究过 3 2 中山大学硕士学位论文协同过滤推荐算法的研究 程中提出的。在多示例学习中，数据集由包( b a g ) 组成，每个包由多个示例 ( i n s t a n c e ) 组成。一个包被标记为正包当且仅当其中至少有一个示例为正例； 一个包被标记为反包当且仅当其中所有的示例均为反例。数据集中只有包被标 记，包中的示例并没有被标记。因此，多示例学习被认为是并列于监督学习，非 监督学习和强化学习的一种新的学习框架。 王军等人最先提出将基于最小h a u s d o r f f 距离度量的k n n 算法应用于多 示例学习的推荐系统中。在此系统中，k n n 主要用来反映不同的包之间的邻居 关系。 之后，王军等人又提出了鲁棒性更好的c i t a t i o n k n n 算法 2 8 1 。该方法基于这 样的思想，在使用多数投票对一个未知包x 进行分类时，不仅考虑k 个离它最近 的包的概念标记，同时还考虑了把x 作为，近邻的所有包的概念标记，然后进 行投票并统计投票结果。 受以上思想的启发，我们猜想在协同过滤推荐算法中，目标项目的得分不仅 与其邻居项目的得分相似，也与其逆邻居项目的得分相似。基于这样的假设，我 们于2 0 0 5 年进行了初步的尝试，就是在原有的协同过滤推荐算法中加入r k n n 信息，产生推荐的过程由目标项目的近邻和逆近邻结合产生推荐，该算法称之为 i r k n n l 协同过滤推荐算法。 假设数据集中只有6 个项目，用 f j ，f 2 ，i 3 ，i 4 ，i 5 ，i 6 表示，先计算项目 间的相似性，产生一邻居表格，如表4 1 所示。 表4 - 1 项目集合( f j f ，f 2 ，乃，搿，巧，泐的邻居表格 ( k 表示最近邻居的排名) k = l k = 2k = 3k = 4k = 5 f j ，乃忍形搿i 5 f 2圉群i 5乃f 6 f 3巧 豳黼 i 2撕搿 群硒 i 2f jb 5 5 霸暖鬻嚣翻麓暖 乃f 6搿 霸鼹缀黼 f 2 珩搿门f 2f f 5 根据这个最近邻居矩阵，我们可以构造出逆最邻居矩阵如下： 表4 - 2 项目集合“j ，f 2 ，乃，搿，巧，f 研的逆邻居表格 ( k 表示编号) 第4 章集成r k n n 的协同过滤推荐算法 k = lk = 2k = 3k = 4k = 5 f j篱拦蘸搿珩 i 2 ii 4f 5订珩 订f j f 6西i 2 搿 i 4i 6i 2i ii 3i 5 i 5f 3i 2f j弭拓 坩群f jf 3西i 2 例如，现在找f j 的k 近邻和逆七近邻，设k = k = 2 ，则f j 7 的k 近邻集合为 p 3 ，洌，逆后近邻集合为2 ，巧，f 彰。当找完f j 的邻居项目和逆邻居项目后， 就可以通过这些项目的信息来对f j 进行评分预测。 与经典的协同过滤算法相似，i r k n n l 协同过滤算法同样分为三个阶段，不 同之处在于第二阶段和第三阶段。 1 数据表示 根据用户评分矩阵，将评分太少的用户( 少于2 0 个评分项目) 和被太少用户 评分的项目( 少于2 0 个用户参与评分) 过滤掉。 2 最近邻查询和逆最近邻查询 在得到评分矩阵之后，针对所有过滤后的有效项目，采用第二章讨论过的相 似性度量公式，计算得到相似度矩阵。再从相似度矩阵中查找用户或项目的最近 邻居和逆最近邻。 3 推荐产生 根据推荐公式，综合考虑某待推荐项目的最近邻和逆最近邻，按照选定的参 数，进行评分预测。 设项目i 的最近邻居集合用砌眦表示，项目i 的逆最近邻居集合用尺删表 示。根据表4 1 和表4 2 展示的某个i t e m 的最近邻以及由此产生的逆最近邻居表， 在公式2 - 9 的基础上加入逆最近邻的因素。则用户u 对项目f 的预测评分屯，r 可以 通过用户材对最近邻居集合k n n i 中项目的评分和用户”对逆最近邻居集合 r 础中项目的评分得到。预测评分的产生如公式4 1 所示： 。女。删，s i m ( i ，k ) xr 蚶+ 如删r f s i m ( i ，k ) e u , 女， 气f2 专= 万丽砑忑= i 而矿 。 3 4 中山大学硕士学位论文协同过滤推荐算法的研究 其中，s i m ( i ，尼) 表示项目i 与项目尼之间的相似性，r 础表示用户“对项目k 的评分。 当最近邻居个数k 取0 的时候，算法变化成单纯使用r k n n 作为训练信息， 推荐公式变化如下： 匕= 毫嚣筹 2 ， 实验结果表明，这种算法由于同时考虑了目标项目的k n n 和r k n n 因素， 当某个项目的最近邻居很少或者无法进行衡量的时候，它的逆最近邻居同样可以 提供预测信息，这样就比经典的算法增加了很多和目标项目相似的邻居项目参与 到预测中，因此较为有效的解决了数据稀疏性造成的训练信息不足的问题。 4 3i r k n n 2 协同过滤推荐算法 4 3 1i r k n n 2 算法基本思想 我们在4 2 节提出的i r k n n l 算法实际上是找到目标项目的k n n 和r k n n 的合集，把这个合集中的所有项目当作目标项目的相似项目，然后通过计算目标 用户对这些相似项目的评分综合得到对目标项目的预测评分。邻居项目的增多， 一方面可以解决数据稀疏性带来的信息不足问题，但另一方面可能会把与目标项 目相差较多的项目当成是相似项目看待，从而导致预测结果的偏差。因此，我们 提出进一步的设想，就是在分别查找出目标项目的k n n 和r k n n 集合后，对这 两个集合进行集合的交操作，找出它们的交集，再由交集中的项目评分对目标项 目进行预测。 还是以上节的例子来说明这种设想。假设目标项目为f j ，从表4 1 和4 2 可 以得出，当k = k = 2 时，f j 的k 近邻集合为椰，f 2 ，逆尼近邻集合为艘，西，f 3 凡 如果按照之前的做法，那么就要综合考虑项目集 i 3 ，i 2 , i 5 ，如果只是找交集的话， 那么只需要考虑3 ，f 刀这个集合。基于这样的设想，我们对i r k n n l 算法进行改 进，提出一种新的算法，该算法同样以传统的i t e m b a s e d 协同过滤算法作为基础 算法，称之为i r k n n 2 协同过滤算法。 第4 章集成r k n n 的协同过滤推荐算法 4 3 2i r l ( n n 2 算法的步骤 与4 2 节中的i r k n n i 协同过滤算法相似，i r k n n 2 协同过滤算法同样分为 三个阶段，不同之处在于第二阶段。 i 数据表示 为参与到推荐过程的垅个用户和刀个项目构造用户评分矩阵，如前面所述。 2 邻居构成 ( 1 ) 根据用户评分矩阵计算得到评分相似度矩阵，评分相似度的计算可以 采用2 2 节介绍过的几种评分相似度度量方法。然后根据评分相似度查找与目标 项目f 最相似的尼个最近邻居和尼个逆最近邻，这两个集合分别以k n n j 和r k n n ， 表示。 ( 2 ) 求k n n ，与r k n n ，的交集，以k n n ，nr k n n j 表示。 3 推荐产生 根据用户甜对k n n ，nr k n n ，集合中的项目的评分，计算得到用户“对目标 项目f 的预测评分只- i ，产生预测评分的公式如下所示： 乇= 一 件3 ， 其中，s 砌( f ，歹) 表示项目f 与项目j 之间的相似性， r u , j 表示用户“对项目 ，的评分。 4 4 实验过程及结果分析 这一章所做的实验其软硬件环境与第三章的实验环境相同，数据集同样采用 m o v i e l e n s 站点提供的开放数据集畸1 ，评价标准也同样采用绝对平均偏差m a e n ， 其计算如公式3 8 所示，这里就不再详细介绍。 这里实验的主要目的是验证i r k n n 2 算法的可行性，同时也对这种算法与传 统的i t e m - b a s e d 协同过滤算法以及i r k n n l 协同过滤算法的推荐质量进行比较。 3 6 中山大学硕士学位论文协同过滤推荐算法的研究 4 4 1 相似性度量方法的比较 该实验采用传统的i t e m - b a s e d 算法，推荐公式采用2 9 ，最近邻居个数女 从1 0 变化到4 0 0 。相似性度量分别采用标准的余弦相似性、修正的余弦相似性 和相关相似性，实验目的是比较不同相似性度量对结果的影响。图4 2 给出了分 别采用三种度量方法进行实验得到的平均m a e 值。 u 了0 豳黧嘲曩 鐾鬻 黼黉曩爨 o 9 0 蟹一 霞 删舞霪 0 8 5 圈 一爨麓懑阚黼麟 豳豳霸 l 渊戮愁黼粼黪i黼 宴 鞠 o 8 0 鞫 鞠黼豳 麟 g蘸 l 黧 0 7 5霹目器囊 矧滋 i i u iu c o s i n ec o r r e l a t i o n a d j u s t e dc o s i n e 相似度度量方法 第4 章集成r k n n 的协同过滤推荐算法 数k 等于逆最近邻个数k ，即k = k ，都是从1 0 变化到4 0 0 。 图4 - 3 相同邻居个数下四种算法的推荐效果比较 图4 3 给出了这三种算法四种公式的推荐效果比较图示。从图中可以看出， 四种公式的m a e 值都是随着最近邻个数变化而变化的，当最近邻个数从很少慢 慢增加时，推荐效果越来越好，各自在某一个k 或七值时达到最优m a e 值后又 开始反弹，之后都随着最近邻个数的增加而慢慢变差。从取得最优值看，i r k n n 2 算法表现最好，当k = k = 1 0 0 时，算法取得最优的m a e 值0 7 3 7 3 ，比i t e m b a s e d 推荐算法的最优值0 7 5 6 8 有很大的提高，而且比i r k n n l 的最优值o 7 4 7 1 也要 好。 而从总体表现来说，后面三种方法的推荐质量都要比第一种方法，也就是传 统的i t e m b a s e d 协同过滤推荐算法的推荐质量好，说明加入r k n n 信息比单纯 使用k n n 信息进行推荐效果更好。图4 4 给出这四种算法的平均m a e 值的比 较。 从图中可以看出，这四种方法的平均推荐质量最好的为i r k n n 2 算法，平 均m a e 值为0 7 5 5 8 ；平均推荐质量次好的为i r k n n l 协同过滤推荐算法及其极 端情况，分别为o 7 6 6 6 和0 7 6 5 0 ；平均推荐质量最差的是传统的i t e m b a s e d 推 荐算法，平均m a e 值为o 7 7 5 4 。 中山大学硕士学位论文协同过滤推荐算法的研究 u ，石u 霾震隰阕 0 7 7 5 慰4 闺 凳赋 0 7 7 0 鼎斟灞 l 黼 圈 霾； 0 7 6 5 鞣戳群躐端麟麓* 黼”“一 一 瓣熏燃 蠢i 疆黼嘲 蛊o 7 6 0 g 0 7 5 5 爨 懿蕊黝溺麟燃戮 震淤震 燃 黼 愿 羞 蒯 縻霞 一一 霉 溺黼震 i霾 i滋霾童 0 7 5 0 瞄瓣 霍l溺黼露 0 7 4 5 8 8 “2 一”“。“ i t e m _ b a s e d k n n u r k n np u r er k n nk n n n r k n n 中山大学硕士学位论文 结束语 结束语 本文深入研究了近年来在电子商务推荐系统中应用最为广泛的各种协同过 滤推荐算法，并在此基础上提出了改进算法，取得了一定的成果。尤其是i r k n n 2 算法，对比经典协同过滤推荐算法的推荐精度有很大程度的改善。 回顾本文的工作，可以发现还有一些不足之处和值得改进的地方。 首先，在算法的实际应用方面做的还不充分，希望以后可以应用在网站的实 时推荐中。 其次，在时间复杂度方面。由于i o e m n n 算法中加入了d e m o g r a p h i c 信息， 而在i r k n n 2 算法中需要寻找k n n 和r k n n 的合集，计算量在客观上会有一定程度 的增大，因此在计算时间方面会有一定的延长。 今后的研究工作不仅会集中在如何处理矩阵稀疏性的问题，如采用多种技术 有效集成，以取得更高的推荐精度；我们还希望能够在提高算法推荐质量的同时 减少计算时间和所需要的空间，这方面可以考虑现在研究很多的各种高维空间索 引结构实现的k n n 和r k n n 算法，以进一步提高算法效率，满足该领域研究中更 广泛的要求。 中山大学硕士学位论文 参考文献 参考文献 1 】m o b a s h e r , b ，d a i ，h ，l u o ，t ，s u n ，y ，a n dz h o u ，j i n t e g r a t i n gu s a g ea n dc o m e mm i n i n g f o rm o r ee f f e c t i v ep e r s o n a l i z a t i o n i n p r o c e e d i n g so ft h ei n t e r n a t i o n a lc o n f e r e n c eo n e - c o m m e r c ea n dw e bt e c h n o l o g i e s ( e c w e 6 2 0 0 0 ) ，2 0 0 0 ，1 5 6 - 1 7 6 【2 】m o b a s h e r , b ，d a i ，h ，l u o ，t ，a n dn a k a g a w a , m i m p r o v i n gt h ee f f e c t i v e n e s so f c o l l a b o r a t i v ef i l t e r i n go na n o n y m o u su s a g ed a t a i nw o r k s h o pi n t e l l i g e n tt e c h n i q u e sf o rw e b p e r s o n a l i z a t i o n ，i j c a i - 2 0 01 ，s e a t t l ew a s h i n g t o n ，2 0 01 5 3 - 6 0 3 】s c h a f e r , j b ，k o n s t a n ，j a ，a n dr i e d l ，j r e c o m m e n d e rs y s t e m si ne c o m m e r c e i na c m c o n f e r e n c eo ne l e c t r o n i cc o m m e r c e ( e c 9 9 ) d e n v e r , c o l o r a d o ，u n i t e ds t a t e s ：a c mp r e s s ，19 9 9 1 5 8 1 6 6 4 】s c h a f e r , j b ，k o n s t a n ，j a ，a n dr i e d l ，j e c o m m e r c er e c o m m e n d a t i o na p p l i c a t i o n s d a t a m i n i n ga n dk n o w l e d g ed i s c o v e r y , 2 0 0 1 ，5 ( 1 - 2 ) ：11 5 - 1 5 3 5 】j h e r l o c k e r , j k o n s t a n ，a b o r c h e r s ，a n dj r i e d l a na l g o r i t h m i cf r a m e w o r kf o rp e r f o r m i n g c o l l a b o r a t i v ef i l t e r i n g i n ：p r o c e e d i n g so ft h e2 2 n da n n u a li n t e m a t i o n a la c ms i g i rc o n f e r e n c e o nr e s e a r c ha n dd e v e l o p m e n ti ni n f o r m a t i o nr e t r i e v a l n e wy o r k ，n y 9u s a ：a c mp r e s s 1 9 9 9 2 3 0 2 3 7 6 】h u l l ，d a ，a n dg r e f e n s t e t t e ，gq u e r y i n ga c r o s sl a n g u a g e s ：ad i c t i o n a r yb a s e da p p r o a c ht o m u l t i l i n g u a li n f o r m a t i o nr e t r i e v a l r e a d i n g si ni n f o r m a t i o nr e t r i e v a l ，m o r g a nk a u f m a n n ，19 9 6 4 8 4 - 4 9 2 7 】a b b a t t i s t a , e ，d e g e m m i s ，m ，l i c c h e l l i ，o ，l o p s ，p ，s e m e r a r o ，c t ，a n dz a m b e t t a , f i m p r o v i n gt h eu s a b i l i t yo fa ne - c o m m e r c ew e bs i t et h r o u g hp e r s o n a l i z a t i o n i np r o c e e d i n g so f t h ew o r k s h o po nr e c o m m e n d a t i o na n dp e r s o n a l i z a t i o ni ne c o m m e r c e2 0 0 2 【8 】m b a l a b a n o v i ca n dy s h o h a m f a b ：c o n t e n t b a s e d ，c o l l a b o r a t i v er e c o m m e n d a t i o n c o m m u n i c a t i o n so ft h ea c m ，1 9 9 7 ，4 0 ( 3 ) ：6 6 - - 7 2 9 】j k o n s t a n ，b m i l l e r , d m a l t z ，j h e r l o c k e r , l g o r d o n ，a n dj r i e d l g r o u p l e