（计算机应用技术专业论文）协同过滤算法中稀疏问题的研究.pdf

究成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得重麽由电盔堂或其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡 献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名：滞立叁l 签字日期： 伽叩年卵叫日 学位论文版权使用授权书 本学位论文作者完全了解 重迭由电太堂有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查 阅和借阅。本人授权重麽由e 电盔堂可以将学位论文的全部或部分内容编入 有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者虢降、是 聊躲 寸汐 签字日期。 叫年箩月叫日 签字日期。 1 年箩月叫日 摘要 摘要 随着i n t e r n e t 的普及和应用，电子商务以其成本低廉、便捷、快速、 不受时空限制等优点风靡全球。电子商务为用户提供越来越多选择的同 时，其结构也变得更加复杂和庞大。一方面，用户面对大量的商品，要 找到自己需要的商品变得越来越困难；另一方面，商家也在大量的电子 数据中失去了与消费者的联系。个性化的电子商务推荐系统根据用户行 为特征为用户提供一对一的服务，帮助用户找到所需商品，从而顺利完 成购买过程。商家通过推荐系统能够提高电子商务系统销售，保持与客 户的联系，提高用户忠诚度和满意度。 协同过滤是目前最成功的个性化推荐技术之一，它的基本思想是利 用用户访问行为的相似性来互相推荐用户可能感兴趣的资源。然而，目 前的大多数协同过滤系统面临着数据稀疏性、冷启动和可扩展性三个问 题的困扰。其中数据稀疏性问题严重影响了推荐系统的推荐质量。论文 针对此问题进行了深入研究，提出了基于粗集的补值算法( i f r s ： i m p r o v e df i l lm i s sv a l u e sa l g o r i t h mb a s e do nr o u g hs e t ) 和基于相同评 分矩阵的补值算法( c m f m ：f i l lm i s sv a l u e sa l g o r i t h mb a s e do n c o r a t i n gm a t r i x ) 用于解决稀疏性问题。 i f r s 算法是一种基于粗集的补值算法，论文根据协同过滤数据的特 点设置了阈值用于刷选相似度更高的用户作为补值参考，同时根据实 验中的表现情况选择了使用出现频率最高值填补剩余空缺评分。实验结 果显示改进后的算法性能明显提升。 c m f m 算法是论文提出的一个新方法。该方法中提出了一种新的相 似性度量方法，并提出相同评分矩阵的概念来支持该相似性方法。算法 通过动态维护的相同评分矩阵，在循环多次的补值过程中始终选择当前 相同评分数最多的对象作为补值参考对象，这种做法有效避免了稀疏性 问题对补值算法本身的影响。为提高算法效率，论文提出了一个快速动 态维护相同评分矩阵的方法，确保了算法的可行性。实验结果证明， c m f m 算法不但具有较快的补值速度，而且推荐精度较高。 关键字：电子商务，个性化推荐，协同过滤，稀疏性，补值 重鏖堂皇奎堂堡主笙塞垒! 竺竺 a b s t r a c t e - c o m m e r c ei sd e v e l o p i n ga n db e i n gp o p u l a rg l o b a l l y ，b e c a u s ei ti s c h e a p ，f a s t ，a n dn o tl i m i t e dt os p a c ea n dt i m e e c o m m e r c ep r o v i d e sm o r e a n dm o r ec h o i c et oc u s t o m e r ，b u ti t ss t r u c t u r ei s g e t t i n gm o r ea n dm o r e c o m p l e xa tt h es a m et i m e o nt h eo n eh a n d ，i ti sm o r ed i f n c u l tf o ra c u s t o m e rt of i n dw h a th ew a n t e dw h e nt h e r ea r es om a n yw e bp a g e s o nt h e o t h e r h a n d ， i t i sm o r ed i f n c u l tf 6 raw e b s i t ec o m p a n yt ok n o ww h a t c u s t o m e r sw a n tt h o u g ht h e y g i v e s om a n yp a g e st oc u s t o m e r s sot h e p e r s o n a l i z e ds e r v i c ei sc o m i n g t h ep e r s o n a l i z e dr e c o m m e n d a t i o ns y s t e m n o to n l yh e l p st h ec u s t o m e r st of i n dw h a tt h e yw a n t ，b u ta l s o h e l p st h e s e r v e r st og i v eh i g hq u a l i t ys e r v i c e c o l l a b o r a t i v ef i l t e r i n gi so n e0 ft h em o s ts u c c e s s f h lt e c h n o l o g i e si n p e r s o n a l i z e dr e c o m m e n d a t i o ns y s t e m i t sb a s i ci d e ai st ou s et h es i m 订a r u s e s a c c e s sb e h a v i o rt o p r e d i c te a c ho t h e rt h ei t e mm a yb ei n t e r e s t h o w e v e r ，t h em a jo r i t yo fc u r r e n tc o l l a b o r a t i v ef i l t e r i n gs y s t e m sa r ef a c e d w i t hd a t as p a r s e ，c o l d - s t a r ta n ds c a l a b i l i t yp r o b l e m s d a t es p a r s ep r o b l e m h a ss e r i o u s l ya f f 色c t e dt h eq u a l i t yo fr e c o m m e n d a t i o ns y s t e m i nt h i sp a p e r ， w e p u t f o r w a r dt w on l lm i s sv a l u e s a l g o r i t h m s w h i c hn a m e d i f r s ( i m p r o v e df i l l m i s sv a l u e sa l g o r i t h mb a s e do nr o u g hs e t ) a n d c m f m ( f i l lm i s s 、h l u e sa l g o r i t h mb a s e do nc o - r a t i n gm a t r i x ) t of i g h tt h e d a t as p a r s ep r o b l e m i f r si saf i l lm i s sv a l u e sa l g o r i t h mb a s e do nr o u g hs e ta l g o r i t h m a c c o r d i n gt ot h ec h a r a c t e r i s t i c so fc o l l a b o r a t i v ef i l t e r i n g ，at h r e s h o l d i s s e ta sar e f e r e n c ev a l u et og e th i g h e rs i m i l a r i t yu s e r s a n da tt h es a m et i m e ， t h eh i g h e s t f r e q u e n c y s c o r eo ft h eu s e r si su s e dt of i l lt h er e m a i n i n g v a c a n c i e s t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h en e wa l g o r i t h mh a sm o r e h i g hp e r f b r m a n c e c m f mi san e wm e t h o dp r o p o s e db yt h i s p a p e r an e wm e t h o do f s i m i l a r i t ym e a s u r ei sp r o p o s e db a s e do nt h en e wc o n c e p to fc o - r a t i n g m a t r i x o b je c t sa r es e l e c t e dt of i l la c c o r d i n gt ot h es i m i l a r i 谚r e l a t i o n ， w h i c hi sc o m ef r o mt h ed y n a m i cm a i n t e n a n c eo ft h ec o - r a t i n gm a t r i x s o i i a b s t r a c t t h ed a t as p a r s ep r o b l e mi ss o l v e di ns o m et h i n g si nt h ef i l lm i s sv a l u e s a l g o r i t h m b e s i d e s ， at h e o r e mi sf o u n dt o c o m p u t et h ed y n a m i c a l l y c o r a t i n gm a t r i xi nt h i sp a p e r t h ee f f i c i e n c yo ft h ea l g o r i t h mi si m p r o v e d a c c o r d i n gt ot h el a w t h er e s u l t so fc o m p a r a t i v ee x p e r i m e n ts h o wt h a tt h e c m f ma l g o r i t h mh a s t h eb e s tr e c o m m e n d e d a c c u r a c y ， a n dh a s h i 曲 e f f i c i e n c y k e yw o r d s ：e - c o m m e r c e ，p e r s o n a l i z e dr e c o m m e n d a t i o n ， c o n a b o r a t i v e f i l t e r i n g ，d a t as p a r s e ，f i l lm i s sv a l u e s i i i 重庆邮电大学硕士论文 目录 目录 摘要i a b s t r a c t i i 第一章绪论1 1 1 引言1 1 2 推荐系统研究现状2 1 3 论文主要工作4 1 4 论文组织结构5 第二章协同过滤：6 2 1 协同过滤系统的简单描述：6 2 2 协同过滤算法的分类7 2 3 基于内存的协同过滤算法8 2 3 1 评分表示8 2 3 2 形成邻居9 2 3 3 产生推荐1o 2 4 协同过滤算法面临的困难1 0 2 5 现有的稀疏性问题解决方法分析l2 2 5 1 基于降维的方法1 2 2 5 2 基于聚类的方法13 2 5 3 基于补值的方法1 3 2 6 协同过滤的评价指标1 4 2 7 小结：15 第三章改进的基于粗集的协同过滤补值算法16 3 1 相关定义16 3 2i f r s 算法1 7 3 2 1 阈值1 7 3 2 2 固定值填补1 9 3 2 3 算法描述及分析2 0 3 3 实验测试2 2 3 3 1 数据集2 2 3 3 2 协同过滤仿真系统实现2 2 i v 重庆邮电大学硕士论文目录 3 4 第四章 4 1 4 2 4 3 3 3 3 推荐精度测试2 6 小结2 8 基于相同评分矩阵的协同过滤补值算法3 0 相同评分矩阵3 0 4 1 1 相关定义31 4 1 2 相同评分矩阵的定义3l 4 1 3 相同评分矩阵中表达的相似性关系一3 2 4 1 4 相同评分矩阵的动态维护3 3 基于相同评分矩阵的补值算法3 4 4 2 1 相似性度量分析3 4 4 2 2 两种相似性关系3 5 4 2 3 两种补值间的切换3 6 4 2 4 补值算法描述3 6 实验测试3 8 4 3 1 补值测试3 8 4 3 2 推荐精度测试一3 9 4 4 小结4 0 第五章总结及未来的工作4 1 5 1 总结4 1 5 2 未来的工作4 2 致谢i 4 3 攻硕期间从事的科研工作及取得的研究成果4 4 参考文献4 5 v 重庆邮电大学硕士论文第一章绪论 1 1 引言 第一章绪论 随着互联网的普及和w e b 技术的发展，电子商务在本世纪也得到了 迅速的发展，人们可以简单方便地在电脑上几次点击完成购物，这种令 传统购物方式可望不可及的方便性为电子商务带来了巨大的商业市场， 为商品供应商带来了一个新的商业契机，从而成为了电子商务发展的一 大推动力。但是，电子商务规模的剧烈膨胀也随之带来了“信息过载 j 的问题，即客户凭借目前的知识水平和认知能力，无法完全了解和利 用网站上提供的庞大信息，寻找需要的商品有如大海捞针。于是，个性 化推荐系统应运而生。 电子商务个性化推荐系统( p e r s o n a l i z e dr e c o m m e n ds y s t e m sf o r e c o m m e r e e ) 的正式定义由r e s n i c k & v a r i a n 在19 9 7 年给出：电子商务个 性化推荐系统是利用电子商务网站向用户提供产品信息和相关建议，帮 助用户决定购买什么产品，通过模拟销售人员帮助用户完成购物过程的 系统【2 儿3 1 。个性化推荐系统可以向用户主动、及时、准确地提供所需信 息，并能根据用户对推荐内容的反馈进一步改进推荐结果。其不仅要对 用户提出的要求提供最贴切的信息服务，还要能依据用户个性特征，主 动收集其可能感兴趣的信息，最后以个性化方式显示给用户。个性化推 荐系统是电子商务推荐系统的发展趋势，对于商务企业而言，利用个性 化推荐系统将消费者的个人偏好、需求同企业提供的产品和服务结合起 来。 协同过滤是个性化推荐系统中使用得最成功的技术之一，其基本思 想是基于兴趣最相似的一批用户的评分数据向目标用户产生推荐【4 巧】。由 于兴趣最相似的用户或者称之为最近邻居对项目的评分与目标用户非常 相似，因此，目标用户对未评分项目的评分可以通过该最近邻居对该项 目评分的加权平均值逼近。但是，随着商品规模的不断扩大，客户参与 过的商品往往非常有限，引起客户评分数据极端稀疏，在这种情况下， 协同过滤算法中的相似性度量方法变得力不从心，使得计算得到的目标 用户的最近邻居不够准确，致使推荐质量大大下降f 1 4 25 1 。所以，如何解 决数据的稀疏性问题成为研究的重点。 第一章绪论 1 2 推荐系统研究现状 目前，推荐系统的研究主要是针对个性化推荐算法的研究。实现个 性化的推荐技术包括基于内容的过滤和协同过滤两种【4 】【5 】。基于内容过 滤的推荐系统需要分析资源内容信息，根据用户兴趣建立用户档案，然 后根据资源内容与用户档案之间的相似性向用户提供推荐服务。这种推 荐技术具有一定的局限性。主要表现在必须分析资源的内容信息，因此 对音乐、图像、视频等信息无能为力，无法分析信息，无法提供推荐。 协同过滤技术的出现解决了以上问题【6 】。协同过滤，又称社会过滤【7 】 ( s o c i a lf i l t e r i n g ) ，其基本思想十分直观：在日常生活中，人们往往会 根据亲朋好友的推荐来作出一些选择( 购物、书籍、音乐等) 。协同过 滤就是将这一思想运用到网络信息服务( 信息推荐) 中，基于其他用户 对某一信息的评价来向对象用户进行推荐。 在协同过滤技术方面，美国m i n n e s o t a 大学计算机科学与工程系的 g r o u p l e n s 研究小组较早开始工作【8 】，以该小组为技术支撑的n e t p e r c e p t i o n 公司于19 9 6 年成立并于19 9 9 年在n a s d a q 上市。该公司的主 要产品是n e tp e r c e r p t i o n s ，它采用了一个叫“实时建议”的技术，主要 功能是根据用户以往的浏览行为及购买记录，在其他用户中匹配相似行 为的用户，根据这些用户的行为预测并为该用户推荐可能感兴趣的商品， 从而为用户提供个性化的浏览建议。采用协同过滤技术的n e t p e r c e r p t i o n s 预测具有很高的准确性，随着用户量的增加，它会变的越来 越“聪明 。 除此以外，国外一些研究机构和研究者实现了许多研究型的推荐系 统，比较著名的有a c f 【9 1 、m o v i e l e n s 【10 1 、r i n g o 】等。 a c f a c f ( a c t i v ec o l l a b o r a t i v ef i l t e r i n g ) 系统是c a r n e g i em e l l o n 大学开 发的主动协同过滤系统，用于电子文档的推荐。它通过链接实现协同过 滤推荐服务，指针包含指向电子文档的超链接、电子文档的上下文信息 和用户对电子文档的评价。在a c f 系统中，用户可以通过主动的方式将 创建的连接推荐给其他兴趣相同的用户，也可以将创建的链接保存在系 统中供其他用户查看。 m 0 v i e l e n s m o v i e l e n s 是m i n n e s o t a 大学开发的自动协同过滤推荐系统，用于电 影信息的推荐。m o v i e l e n s 系统是一个基于w e b 的推荐系统，通过在线 2 重庆邮电大学硕士论文第一章绪论 的方式收集用户的评分数据并提供推荐结果，i n t e r n e t 上的所有用户都可 以体验该推荐服务。用户在线注册时，需对至少l5 部以上电影进行评分， 评分从最差到最好分1 5 分5 个等级，系统会根据用户提交的电影评分 信息，为用户推荐一个可能感兴趣的电影列表。 r i n g o r i n g o 是m i t 设计的一个音乐推荐系统。这个系统会首先要求使用 者对音乐家做评比，再依照评比结果计算用户间的相似度进行分群，最 后由同一类兴趣的用户为使用者推荐音乐。 电子商务推荐系统在我国的研究起步较晚，目前还是几乎处于初级 阶段i l 引。目前国内电子商务网站的推荐存在以下问题：1 ) 大部分网站 缺乏个性化的推荐，不能根据不同用户的兴趣爱好给出不同的产品推荐。 2 ) 推荐的自动化程度低，用户需要的信息往往是通过反复的检索来获取 的。3 ) 推荐的持久性程度低，国内大多数电子商务网站给出的推荐都是 基于用户一次性登陆得到的。事实上，随着我国电子商务的蓬勃发展， 对个性化推荐技术需求不断急剧增加，谁先使用个性化推荐技术，谁就 可以把握更大的商机。 协同过滤在电子商务推荐系统应用中获得了巨大成功，但随着网站 结构、内容复杂度和用户人数的不断增加，基于协同过滤的推荐系统的 发展面临着两个主要挑战【1 3 】：其一是推荐质量的挑战，也是推荐系统首 要解决的问题。用户需要得到值得信任的推荐来帮助他找到喜欢的产品， 假如用户相信推荐购买了商品，而后发现并不喜欢，用户对推荐系统推 荐结果的信任度降低，同时将不愿再次使用该推荐系统；其二是推荐响 应时间的挑战，对于电子商务网站，往往需要给成百上千万的用户提供 推荐，这就不得不考虑提高响应速度，而不是让用户等着推荐。 应对以上挑战，协同过滤系统需要解决的主要问题有三个【1 3 16 1 ，分 别是：数据稀疏性问题、冷开始问题和算法可扩展性问题。解决前两者 旨在提高推荐系统的推荐质量，而解决后者旨在提高系统响应时间。 目前大多数协同过滤推荐系统中，用户涉及的信息量相当有限，一 般只有1 2 ，严重影响了推荐算法的推荐质量，所以数据稀疏性问题 是当前一个极为突出的问题。为了解决该问题，文献 17 】 18 】提出利用项 目间存在的相似关系对缺失评分进行预测，再进行用户间的相似性计算 时可以避免稀疏性问题的影响。这种方法的缺点是在利用项目之间相似 性预测用户评分时，同样受到稀疏性问题的影响，一方面导致结果的准 确性不高，另一方面很多评分无法被预测到，影响了该方法的效果。文 3 文 第一章绪论 献【1 9 2 l 】应用奇异值分解方法将评分矩阵进行降维，得到一个低维高密 度的评分矩阵，然后在这个降维后的评分矩阵上进行最近邻计算。但降 维引起了信息缺失的问题，虽然相似性计算避免了数据稀疏性问题，实 际上却很难保证能够真正提高推荐精度。文献【2 2 】 2 3 】使用b p 神经网络 技术预测目标用户和候选邻居用户评分并集中的缺失评分，缓解了数据 稀疏度以后再进行相似性度量，但这种方法使最近邻居的计算更为复杂， 严重影响了系统的反应时间，只能在非实时的推荐系统中考虑使用。文 献 2 4 2 7 提出了信任度传播的方法，让用户给其他用户进行评价，最后 根据得到的用户信任网络来得到用户之间的相似性，这种方法的缺点是 需要用户配合，所以在实际应用中受到了限制。文献【2 8 】 3 5 通过聚类技 术将具有相似兴趣爱好的用户分配到相同的聚类中，根据聚类中其他用 户对商品的评价预测目标用户对该商品的评价，这样避免了稀疏性对用 户间相似性度量带来的影响。这种方法的最大缺陷在于如果目标用户处 于聚类的边缘，则该用户的推荐精度会比较差。文献 3 9 】 4 0 】将粗集的补 值算法应用于协同过滤中，使用经过补值后的数据集进行协同过滤计算， 但本论文在研究中发现这种方法对协同过滤数据的适用性不强，提高推 荐精度有限。 1 3 论文主要工作 电子商务协同过滤推荐系统的实施受到了推荐质量和推荐响应时间 的挑战，而影响推荐质量的主要问题是数据稀疏性问题，本文是一篇针 对解决该问题来提高推荐质量的论文。 针对协同过滤面临的数据稀疏性问题，论文首先提出了改进的粗集 补值算法i f r s ( i m p r o v e df i l lm i s sv a l u e sa l g o r i t h mb a s e do nr o u g h s e t ) ，然后在研究i f r s 的基础上提出了基于相同评分矩阵的协同过滤算 法c m f m ( f i l lm i s sv r a l u e sa l g o r i t h mb a s e do nc o r a t i n gm a t r i x ) 。在 这两个算法中，补值部分和协同过滤计算是分离的，补值相当于对协同 过滤使用的数据集做了一个预处理，可以离线进行，因而不会影响协同 过滤系统的反应时间，同时补值算法本身也具有较快的运行速度，可行 性较好。 粗集理论是由波兰华沙理工大学p a w l a k 教授于2 0 世纪8 0 年代提出 的一种研究不完整、不确定知识和数据的理论方法【4 1 1 ，目前在智能信息 处理领域已经有了许多成功的应用。文献 3 9 】 4 0 】将粗集中的r o u s t i d a 4 学硕士论文第一章绪论 数据补值算法应用于解决协同过滤稀疏性问题，实验证明了该方法是有 效的。i f r s 算法是在以上文献研究的基础上提出的一个改进算法，主要 针对粗集补值算法在协同过滤数据上的适用性进行的改进，首先提出了 阈值用于提高补值参考用户的可靠性，规定补值参考用户与目标用户 须达到阈值数量的共同评分数才可以参与补值运算。然后对几种常见的 固定值补值方式进行了仿真分析，选用了其中效果较好的方法，即填补 用户出现频率最高评分值的方法加入i f r s 算法中。实验证明，改进的算 法比原算法效果更好。 i f r s 虽然能够解决稀疏性问题，但应用于极度稀疏的协同过滤数据 时，有较大一部分缺失评分必须依靠固定值填补方式填补，一定程度上 影响了填补数据的质量。所以论文进一步提出了一个补值效果更好的新 算法c m f m ( f i l lm i s sv a l u e sa l g o r i t h mb a s e do nc o r a t i n gm a t r i x ) 。该 算法中，论文提出了一种新的相似性度量方法，认为相同评分数最多的 用户( 或者项目) 最相似，同时提出了相同评分矩阵的概念来支持该相 似性方法，通过动态维护的相同评分矩阵中反映的相似性关系，避免了 稀疏性问题对补值算法的影响。并且c m f m 算法协调利用了用户间的相 似性和项目间的相似性进行补值，能填补较多的空缺数据。为提高算法 的效率，论文另外提出了一个快速动态维护相同评分矩阵的方法，确保 了算法的可行性。实验结果证明，c m f m 算法不但具有较快的补值速度， 而且在其补值后的数据集上进行协同过滤计算推荐精度较高。 1 4 论文组织结构 论文组织结构如下： 第一章介绍了协同过滤技术的研究背景和研究状况，以及本文的主 要工作。 第二章首先介绍了协同过滤算法的基础理论、分类方式以及面临的 主要困难，分析了解决数据稀疏性问题的各种主要方法。 第三章中提出了改进的粗集补值算法i f r s ，并对其在协同过滤中的 表现进行了实验测试。论文实现的仿真系统在本章实验部分进行了介绍。 第四章提出了相同评分矩阵的概念，并进一步提出了基于相同评分 矩阵的协同过滤补值算法c m f m ，深入分析了该算法的原理及特点，并 做了实验测试。 第五章对本文进行了总结，提出下一步的研究计划。 5 第二章协同过滤 第二章协同过滤 协同过滤是利用用户访问行为的相似性( 或者对对象评价的相似性) 来互相推荐用户可能感兴趣的资源【2 9 】【30 1 。日常生活中，兴趣相投的好 朋友之间经常会互相推荐自己喜欢的电影、餐厅、网站等等，而一般此 类的推荐都会得到比较满意的评价，这是因为被推荐的对象是一个得到 兴趣相似者好评的对象。协同过滤就是这样的一种推荐方式，通过寻找 历史用户中与目标用户兴趣最相似的n 个用户作为最近邻居，然后根据 最近邻居的喜好表现来为目标用户推荐。 协同过滤的最大优点是不需要分析对象的属性特征，对推荐对象的 内容格式没有特殊要求，能够处理非结构化的复杂对象。例如，电影网 站向用户推荐电影时，不需要对电影的内容进行分析，只要给出一些用 户对电影的评价信息和评分等级，完全根据用户的喜好表现来推荐。 2 1 协同过滤系统的简单描述 典型的协同过滤系统结构如图2 1 。客户端的用户将请求发给w e b 服务器端以后，服务器端调用用户数据库和项目数据库，并把用户评价 信息发给协同过滤推荐引擎，推荐引擎调用评价数据库并根据协同过滤 算法将推荐通过w e b 服务器反馈给客户端的用户。 图2 1 典型的协同过滤推荐系统结构 实现如图2 1 的协同过滤系统一般需要两个步骤【15 1 ，第一步是获得 6 第二章协同过滤 用户评价信息，即图2 1 中评分数据库数据的获取；第二步是分析用户 之间的相似度，预测特定用户对某一信息的喜好，即协同过滤推荐引擎 的协同过滤算法。 用户信息的获取主要通过用户对给定信息的评价。评价分为显式评 价和隐式评价两种。显式评价需要用户有意识地表达自己对某一信息的 认可程度，一般用整数值来表示喜欢的不同程度，如g r o u p l e n s 、r i n g o 等，协同过滤系统向新用户提供一个信息列表，要求用户对其中全部或 部分信息进行评价，系统获得用户的这些初始信息后，就能将用户加入 到用户库中，随着用户不断使用协同过滤系统，用户的信息不断积累。 隐式评价希望从用户的行为中获得用户信息，目前已做的研究有通过分 析用户网上购物记录、阅读文章的时间、u r l 的连接次数等数据记录获 取。就目前而言，隐式评价对数据分析难度较大，准确性、有效性有待 于进一步提高，所以协同过滤领域的研究主要以显式评价为主。 第二步通过综合第一步搜集的所有评分值，根据。目标用户的兴趣偏 向，利用协同过滤算法过滤掉用户不需要的信息，最终得到一个t o pn 的有序序列，即最近邻居集，然后根据最近邻居的兴趣表现，提供给目 标用户一个具有n 项可能感兴趣的项目的列表，典型的协同过滤算法过 程如图2 2 。 活 活动用形成最产生推 j 用户 户评分近邻居荐 信息集 图2 2 典型的协同过滤算法过程 2 2 协同过滤算法的分类 0 表 协同过滤算法一般有两种分类方法。一些学者根据协同过滤所采用 的算法，将其分为基于内存的( m e m o r y - b a s e d ) 与基于模型的 ( m o d e l - b a s e d ) 两种3 1 1 。另外一些学者依据协同过滤技术所使用的事物 之间的关联性，将其分为基于用户的与基于项目的协同过滤算法【3 2 1 。 基于内存的协同过滤 7 重庆邮电大学硕士论文 第二章协同过滤 首先用统计的方法在原始数据集中得到具有相似兴趣爱好的邻居用 户，再基于邻居进行计算，所以该方法也称基于邻居的协同过滤。在进 行推荐时，须计算分析使用者的历史记录，以找出与使用者偏好相似的 邻居族群，作为推荐依据。 基于模型的协同过滤 其主要是将使用者历史记录，通过统计方法或机器学习方法来构建 出使用者偏好模型，进而利用此偏好模型来产生推荐，目前使用的方法 包括关联规则法、贝叶斯网络、聚类等。 基于用户的协同过滤 通过计算目标用户的最近邻居集进行推荐。其核心概念是假设人与 人之间的行为具有某种程度的相似性，比如购买行为类似的顾客，会购 买类似的产品。 一 基于项目的协同过滤 认为项目之间也存在着相似性，通过计算项目之间的相似性，选择 出目标项目的最近邻居集合，通过当前用户对最近邻居项目的评分预测 其对目标项目的评分。 在这些所有分类中，应用较多的有基于内存的协同过滤算法【2 j 。 2 3 基于内存的协同过滤算法 综合2 2 节中协同过滤算法的分类，还可以有基于用户的或者基于 项目的内存协同过滤算法等。但是，在表达上基于用户的和基于项目的 非常相似，只是计算对象一个是用户，一个是项目，计算方法完全相同。 所以，接下来，本节的基于内存的协同过滤算法将以基于用户的为例。 2 3 1 评分表示 在协同过滤算法中，处理的评分数据对象表示为一个用户项目评 分矩阵，以m o v i e l e n s 提供的数据为例，形式如图2 3 所示，其中列代 表用户，行代表项目，评分值可以是1 5 的整数，对应的，每一个项目 用户可能会有一个评分代表该用户已评价的项目，或者，- 代表没有评价的 空缺值，实际情况是评价过的项目只占百分之几或更少。 8 重庆邮电大学硕士论文第二章协同过滤 r 项目口l项目口2 项目 用户毛 幸 l 3 用户x 2 22 霉 用户 2 露 2 3 2 形成邻居 图2 3 用户项目评分矩阵 基于内存的协同过滤核心步骤就是为一个需要推荐服务的活动用户 寻找其最相似的最近邻居集。即对一个活动用户，要产生一个通常依相 似度大小排列的“邻居 集合= j ，儿，m ，此集合将被作为计算推 荐的依据。获取该用户最近邻居集的方法是通过相似性度量算法度量该 用户与其他用户之间的相似性，最后取相似性最大的刀个用户为最近邻 居集。常用的相似性度量算法有三种，分别是：皮尔森系数，余弦相似 性和修正的余弦相似性。 皮尔森系数( p e a r s o n sc o r r e l a t i o n ) 又称相关相似性。其用户i 和用户j 的相似度j 砌( f ，) 用皮尔森系数 来衡量： 砌 加高高一 ” 其中如表示用户f 和用户共同评分的项目，如表示f 用户对项目c 的评分，足表示f 用户所有评分的平均分。 余弦相似性( c o s i n e ) 这种方法将两项目作为多维用户空间中的两个矢量，他们之间的相似 度用这两个矢量之间的夹角余弦来表示。 砌 加一 亿2 ， 其中厶代表用户f 所有的评分项目。 修正的余弦相似性( a d j u s t e dc o s i n e ) 9 同过滤 相比余弦相似性，修正的余弦相似性进一步考虑了不同用户评分尺 度可能会不同的问题，其做法是将评分减去相应用户的平均评分值来进 行修正。 咖瓴加高焉一 亿3 ， 符号含义同上。 2 3 3 产生推荐 通过相似性计算，得到了用户“的最近邻居集，我们表示为们& ， 这是一个最相似用户的集合，根据们& ，计算用户甜对指定项目f 的预 测评分如下： 氧+ 鼍一 4 ， 其中，表示用户u 对项目i 的预测评分，尺“表示用户“所有评分的 平均值，j f 垅似，砂表示用户材和邻居用户甩的相似度，r 。表示用户刀对 项目f 的评分。 2 4 协同过滤算法面临的困难 在1 2 节中，论文简单介绍了制约协同过滤推荐系统性能的三个问 题，本节我们将对这三个问题进行深入分析。 稀疏性问题 在2 3 1 节中我们提到协同过滤处理的数据对象是一个用户项目 评分矩阵，尽管这在理论上很简单，但实际上，许多电子商务推荐系统 要对大量的数据信息进行处理，而在这些系统中一般用户购买商品的总 量占网站总商品量的1 左右，因此造成了用户项目评分矩阵非常稀 疏。在矩阵如此稀疏度条件下，用论文2 3 2 小节中的相似性算法度量用 户间相似度会出现两方面的问题。 一方面，过度稀疏会造成相似性度量的不准确。在公式2 2 和2 3 余弦相似性和修正的余弦相似性计算中，对于用户没有评分的项目，我 们只能假设为0 ，显然这个0 不能代表用户的爱好表现，是不可靠的。 l o 同过滤 如果两用户间没有共同的评分项目，则相似性无法衡量，如果两用户间 共同评分的项目很少，即使有结果也是不可靠的。在公式2 1 相关相似 性计算中，我们的相似性度量排除了所有未评分的项目，显然，如果共 同评分的项目过少，在少量的几个项目上的表现来推断两用户间的相似 性，表现出了和公式2 2 及2 3 同样的不可靠性。 另一方面，由于数据非常稀疏，在形成目标用户的最近邻居用户集 时，往住会造成邻居用户关系传递性的丢失，导致推荐效果的降低。例 如，用户a 与用户b 相关程度很高，用户b 与用户c 相关程度也很高， 但由于用户a 与用户c 很少对共同的产品进行评价，。而认为两者关联程 度较低，由于数据的稀疏性，丢失了用户a 与用户c 之间潜在的关联。 冷开始问题 又称第一评价问题( n r s t r a t e r ) ，或新项目问题( n e w i t e m ) ，从一 定角度可以看成是稀疏问题的极端情况。因为协同过滤推荐是基于邻居 用户资料得到目标用户的推荐，在一个新的项目首次出现的时候，因为 没有用户对它作过评价，因此单纯的协同过滤无法对其进行预测评分和 推荐。而且，由于新项目出现早期，用户评价较少，推荐的准确性也比 较差。相似的，推荐系统对于新用户的推荐效果也很差。冷开始问题的 极端的案例是：当一个协同过滤推荐系统刚开始运行的时候，每个用户 在每个项目上都面临冷开始问题。 可扩展性问题 基于内存的协同过滤算法能及时利用最新的信息为用户产生相对准 确的用户兴趣预测或进行推荐，但是面对日益增多的用户，数据量的急 剧增加，算法的扩展性问题( 即适应系统规模不断扩大的问题) 也成为制 约推荐系统实施的重要因素。 以上分析了目前协同过滤算法面临的主要问题，其中可扩展性问题 影响的是系统的实时反应能力，针对实时性要求突出的系统，这一问题 可以通过建立推荐模型的方法来解决，也就是我们在本章2 2 协同过滤 算法的分类中指出的基于模型的算法，但系统的响应速度和推荐准确性 之间往往是顾此薄彼，同时建立起的模型的质量往往也受着稀疏性问题 的制约。对于冷开始问题，通常可以结合一些其他的推荐方式来解决不 能够被推荐的问题，比如对新用户，可以暂时先对其推荐一个关注度最 高的t o p lo 列表，待有了一定的用户数据后再由协同过滤算法进行推荐。 在这三个问题中，最突出问题是稀疏性问题，稀疏性问题影响的是推荐 系统的推荐质量，一个没有推荐质量的个性化推荐系统是不会受到客户 同过滤 青睐的。目前对该问题虽然有较多的解决方法，但大部分都处于研究阶 段，真正能够有效提高推荐精度并具可实施性的较少，论文下一节中将 讨论这些方法。 2 5 现有的稀疏性问题解决方法分析 论文对目前学者们提出的解决稀疏性问题的方法大致分成三大类 别，分别是基于降维的方法、基于聚类的方法和基于补值的方法。 2 5 1 基于降维的方法 典型的矩阵降维方法是奇异值分解法s v d 【1 9 圳1 ( s i n g u l a rv a l u e d e c o m p o s i t i o n ) 。s v d 可以将一个朋刀阶矩