（计算机应用技术专业论文）协同过滤推荐算法的若干问题研究.pdf

摘要 摘要 推荐系统通过预测用户对项目的喜好程度来为用户进行信息过滤，应用知 识发现技术来生成个性化推荐。协同过滤是一种常用的减少信息过载的技术， 己经成为了个性化推荐系统的一种主要工具，被广泛应用于电子商务网站的推 荐系统。但随着系统结构、内容的复杂度和用户人数的不断增加，协同过滤技 术的一些缺点逐渐暴露出来，主要有精确性、数据稀疏性、冷启动、可扩展性 和安全性问题。 协同过滤算法主要分为基于内存的协同过滤和基于模型的协同过滤两类， 这两类算法的典型代表分别为最近邻协同过滤算法和基于奇异值分解的算法， 前者因其简单适用而被广泛应用于电子商务推荐系统，却通常因数据的极度稀 疏性和相似度度量方法的弊端导致算法的精度下降。后者则通过矩阵奇异值分 解的降维技术一定程度解决了数据稀疏性问题，然而目前国内对该算法的安全 性研究较少。本文将分别以上述两种算法为载体，研究算法的数据稀疏性问题 和安全性问题。 为解决协同过滤算法中数据稀疏性问题和传统相似度度量方法的弊端，本 文研究了最近邻协同过滤算法在不同的稀疏性问题解决方案下各相似度方法的 优化对算法性能的影响。通过实验对现有的各种常用相似度进行了基于用户评 分项目并集和基于相关加权因子的优化，分别确定了基于稀疏评分矩阵、缺省 评分矩阵和奇异值分解( s v d ) 预测评分矩阵的最近邻算法中的最优相似度方 法，有效地提高了各情况下算法的推荐精度。 为解决协同过滤推荐系统遭受的欺诈攻击带来的安全性问题，本文研究了 典型的基于奇异值分解的协同过滤算法的抵御攻击的能力，通过设计不同规模 和攻击意图的攻击测试，以平均绝对偏差、平均预测偏移及平均命中率偏差这 三种评估参数分析了不同填充规模和攻击规模的攻击用户概貌对攻击效果的影 响，同时研究了不同攻击类型的攻击效果差异。 关键词：推荐系统电子商务协同过滤稀疏性安全性相似度优化欺诈攻击 a b s t r a c t a b s t r a c t r e c o m m e n d a t i o ns y s t e m sp r o v i d eu s e r s 、衍mi n f o r m a t i o nf i l t e r i n gs e r v i c eb y p r e d i c t i n gu s e r s r a t i n g sa b o u ti t e m s ，a n dg e n e r a t ep e r s o n a l i z e dr e c o m m e n d a t i o n u s i n gk n o w l e d g ed i s c o v e r yt e c h n i q u e s c o l l a b o r a t i v ef i l t e r i n gi sac o m m o n l yu s e d t e c h n o l o g yt or e d u c et h ei n f o r m a t i o no v e r l o a dp r o b l e m ，w h i c hi sb e c o m i n gam a j o r t o o lo ft 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 sa n dw i d e l yu s e di ne - c o m m e n c e h o w e v e r ，a st h es y s t e ms t r u c t u r e ，t h ec o n t e n t so ft h ec o m p l e x i t ya n dt h ei n c r e a s i n g n u m b e ro fu s e r s ，c o l l a b o r a t i v e f i l t e r i n gt e c h n o l o g yg r a d u a l l ye x p o s e ds o m e s h o r t c o m i n g s ，s u c ha sa c c u r a c y ，s p a r s i t y ，c o l ds t a r t ，s c a l a b i l i t ya n ds e c u r i t y c o l l a b o r a t i v ef i l t e r i n ga l g o r i t h m sa r ed i v i d e di n t ot w ot y p e s ：m e m o r y - b a s e d a n dm o d e l b a s e d t h en e a r e s tn e i g h b o rc o l l a b o r a t i v e f i l t e r i n ga l g o r i t h mi s a r e p r e s e n t a t i v eo fm e m o r y b a s e da l g o r i t h m s ，i th a sb e e nw i d e l yu s e di ne - c o m m e r c e r e c o m m e n d a t i o ns y s t e m ，b u ti t sa c c u r a c yi su s u a l l yd e c r e a s e do w n i n gt oe x t r e m e l y s p a r s ed a t aa n ds i m i l a r i t ym e a s u r e m e n t t h es i n g u l a rv a l u ed e c o m p o s i t i o n ( s v d ) a l g o r i t h mi sat y p i c a lo n eo ft h em o d e l - b a s e da l g o r i t h m s ，i tr e s o l v e st h es p a r s i t y p r o b l e mac e r t a i ne x t e n tb yt h em a t r i xr e d u c e d d i m e n s i o nt e c h n o l o g y ，b u tt h e r ea r e f e wr e p o r t sa b o u tt h es t u d yo fi t ss e c u r i t yp r o b l e m i nt h i sp a p e r ，w ew i l ls t u d yt h e s p a r s i t yp r o b l e mo f t h en e a r e s tn e i g h b o ra n dt h es e c u r i t yp r o b l e mo ft h es v d b a s e d a l g o r i t h m t os o l v et h ep r o b l e m sc a u s e db yt h es p a r eu s e rd a t aa n dt r a d i t i o n a lm e t h o d so f s i m i l a r i t ym e a s u r e ，w ea n a l y z et h ep e r f o r m a n c eo ft h en e a r e s tn e i g h b o ra l g o r i t h m a f f e c t e db yt h eo p t i m i z a t i o no fs i m i l a r i t ym e a s u r e si nt h r e ed i f f e r e n ts p a r s ep r o b l e m s o l u t i o n s ，a n dm o d i f yt h et r a d i t i o n a ls i m i l a r i t yc a l c u l a t i o n sb a s e do nt h ei n t e r s e c t i o n o fu s e rr a t i n g sa n dc o r r e l a t i o n s h i pw e i g h t i n gf a c t o r ，a n dg e tt h e o p t i m i n n g s i m i l a r i t ym e a s u r er e s p e c t i v e l yf o rt h en e a r e s tn e i g h b o ra l g o r i t h mb a s e do nt h e s p a r s er a t i n gm a t r i x ，t h ed e f a u l tr a t i n gm a t r i xa n dt h es v d b a s e dr a t i n gm a t r i x ，t h e e x p e r i m e n tr e s u l t ss h o wt h a tt h e s eo p e r a t i o n si m p r o v et h ea c c u r a c yo fa l g o r i t h m s o b s e r v a b l y t os o l v et h es e c u r i t yp r o b l e mo w n i n gt os h i l l i n ga t t a c k si nc o l l a b o r a t i v e f i l t e r i n gs y s t e m s ，w es t u d yt h ea b i l i t yt or e s i s ta t t a c k so ft h es v d b a s e da l g o r i t h m b yd e s i g n i n ga t t a c kt e s t so fd i f f e r e n ti n t e n t sa n ds c a l e s ，a n da n a l y z et h ea t t a c k e f f e e t i v e n e s so fa t t a c km o d e l si nd i f f e r e n tf i l ls i z ea n da t t a c ks i z eb yu s i n gt h r e e a b s t r a c t e v a l u a t i o np a r a m e t e r ss u c ha sm e a na b s o l u t ee r r o r ( m a e ) ，a v e r a g ep r e d i c t i o n s b j f t ( h p s ) a n da v e r a g eh i tr a d i od i f f e r e n c e ( a h r d ) ，a tl a s t ，w er e s e a r c ht h e a t t a c kd i f f e r e n c eo ft h ef o u rt y p e so fa t t a c km o d e l s k e yw o r d s ：r e c o m m e n d e rs y s t e m s ，e - c o m m e n c e ，c o l l a b o r a t i v ef i l t e r i n g ，s p a r s i t y ， s e c u r i t y ，s i m i l a r i t yo p t i m i z a t i o n ，s h i l l i n ga t t a c k s i i i 中国科学技术大学学位论文原创性声明 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除已特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 作者签名： 毪匆 签字日期： 丝2 ：笸：芝 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 d 公开口保密( 年) 作者签名：雌 签字日期一銎翌址! 至一 导师签名：二要赴 签字日期： 巧! 曼：三一 第1 章绪论 1 1引言 第1 章绪论 1 1 1信息过载 随着信息高速公路的发展和普及，人们己经被包围在信息的汪洋大海之中。 i n t e m e t 是海量信息源，而且其信息的组织是异构的、多元的和分布的，由于信 息不断地更新和增加，信息量以指数规律迅猛地增长和扩展，因而形成了“信息 爆炸”。对于普通的用户来说，信息过载己经成为日益严重的问题。信息过载是 由于i n t e r n e t 提供的信息的复杂性和广泛性，并且限于浏览者的知识水平与认识 能力，造成浏览者无法正确理解和使用信息。 解决这些问题关键在于将i n t e m e t 从被动接受浏览者的请求转化为主动感知 浏览者的信息需求，实现i n t e r a c t 系统对浏览者的主动信息服务。新一代的信息 服务将是个性化主动信息服务，如何从海量的数据和信息中高效地获取有用知识， 如何从迅速爆炸的信息中及时地获取最新信息，如何提高信息检索与推送的智能 水平，以及如何满足各种用户不同的个性化需求等，都是新的信息服务系统面临 的挑战性课题。 目前解决信息过载问题的方法主要有两种：信息检索和信息过滤( g o o de ta 1 1 9 9 9 ；s a r w a re ta i 1 9 9 8 ) 。 信息检索是指将信息按一定方式组织和存储起来，并针对信息用户的特点需 求查找出所需信息内容的过程。如我们常用的搜索引擎g o o g l e 、百度等都属于 信息检索系统。信息检索技术运用广泛，但是它无法主动为用户做出推荐，除了 用户自己输入的查询，它无法进一步发掘出用户更多的兴趣。 1 1 2 信息过滤 信息过滤则是指计算机根据用户提供的一个兴趣描述文件，从动态变化的信 息流中，自动检索出满足用户个性化需求的信息。比如在描述文件中记录用户喜 爱的演员的名字，当有这些演员演出的新片时就可推荐给用户。信息过滤的应用 领域很广泛，如基于用户过滤规则模板的邮件过滤系统，针对某一集体或个人的 新闻过滤系统，针对儿童的不良信息过滤系统，针对网络信息检索结果的过滤不 相关信息的应用等等。 信息过滤又可分为基于内容的过滤和协同过滤。 第l 章绪论 基于内容的过滤又称为认知过滤( 徐小琳等，2 0 0 3 ) 。基于内容的过滤根 据信息的内容和用户模板之间的相关性向用户推荐信息，它们利用资源与用户兴 趣的相似性来过滤信息。基于内容的过滤可以应用于过滤广告，过滤垃圾邮件， 过滤反动、色情网页等等。 基于内容的过滤主要有下面的局限： ( 1 ) 要求信息流要么是机器可以分析的形式( 如文本) ，要么是手工标注了 属性( 如声音、图像、视频可能不能自动分析出相关的属性信息，然而由于信息 量巨大的关系，采用手工标注属性是不实际的或不可能的) 。 ( 2 ) 不容易发现新的信息，系统经常把用户以前看过的信息又推荐给用户。 ( 3 ) 不能根据质量、风格或观点等进行过滤。如两篇文章碰巧使用了同样的 关键字，系统将不能区分哪篇是优质的文章，哪篇是劣质的文章。 协同过滤( c o l l a b o r a t i v ef f l t c f i n g ) ，又称社会过滤，是至今为止最为成功 的个性化推荐技术，它被应用到很多领域中。协同过滤技术为当前用户在用户群 体中寻找和他兴趣相似的用户，然后综合这些用户对某一信息的评价，预测当前 用户对该信息的喜好程度。协同过滤基于这样的认识：如果若干用户对某些项目 的评分相似( 表明他们的兴趣相投) ，则他们对其它项目的评分也应相似。 协同过滤做出推荐的出发点是其他用户对于项目的评价与项目的本身内容 无关。这与认知过滤建立在项目内容基础上的推荐方法恰恰相反。它是补充认知 过滤系统的一种技术，正成为一种减小信息负载的常用方法。协同过滤己经在电 子商务推荐上取得了很大的发展，是到目前为止最为成功的一种推荐方法，己被 用于许多站点。 本文的研究工作主要围绕协同过滤推荐系统存在的稀疏性问题和安全性问 题展开，对协同过滤技术的两类典型算法分别进行了针对性的实验研究，并取得 一定的成果。 本章1 2 节对电子商务推荐系统进行了概述；1 3 节对协同过滤技术进行了 简要介绍；1 4 节阐述了本文的研究内容；1 5 节介绍了本文的章节组织。 1 2 电子商务推荐系统概述 1 2 1 电子商务推荐系统的引入 电子商务网站的建立改变了传统的贸易行为，它对传统的商业形态、交易形 式、流通方式以及营销方式等都产生了巨大的影响，企业和用户也都因此而面临 很多新的问题。对用户而言，电子商务网站为用户提供了前所未有的巨大的产品 2 第1 章绪论 选择空间，给人们的生活带来了极大的便利。伴随电子商务网站中产品极大丰富 的同时，用户的个性化产品需求也日益显现。为找到自己需要的商品，用户必须 花费大量的时间浏览很多无关的信息，从而出现了信息过载的现象。 虽然电子商务网站为用户提供的产品选择范围扩大了，用户的选择机会也增 多了，但是用户的信息处理负担却越来越重。电子商务网站中包含了大量的信息， 用户不得不花费越来越多的时间搜寻他们所需要的产品，因为电子商务网站中的 很多信息与用户的兴趣是不相关的。此外，网络的虚拟性使得用户不可能像现实 中的商场购物那样直接触摸产品以检查它的外观和质量。因此，用户追切地希望 电子商务网站能够提供一种类似购物助手的功能，可以根据用户的兴趣爱好推荐 他们满意的产品。 通过构建电子商务推荐系统可以解决上述问题。电子商务推荐系统根据用户 的兴趣爱好向他们推荐感兴趣的产品或服务，有利于促进交易的进行，有利于提 高服务的质量。推荐系统帮助用户节省了寻找信息的时间，企业也可以利用推荐 系统收集和反馈的信息改进企业的营销策略，吸引更多的忠实客户。 电子商务推荐系统向客户提供商品信息和建议，帮助客户决定购买何种商品， 模拟销售人员向客户推荐商品，完成购买的过程。它是数据挖掘系统的一类，但 它又是一种较为特殊的数据挖掘系统：这主要是体现在推荐系统的实时性和交互 性上。推荐系统不但根据用户以往的历史记录，更需要结合当前一段时间的行为 动作做出实时的反应，并根据与用户交互的反馈结果修正和优化其推荐结果。 电子商务推荐的作用表现在五个方面( s c h a f e re ta 1 2 0 0 1 ；s c h a f e r e t a l 1 9 9 9 ) ： ( 1 ) 帮助用户检索信息：对于购物目标明确的用户，利用电子商务网站提供 的检索功能可以迅速地找出他所需要的产品，免除用户在产品目录中依次查找的 劳苦。但是对于没有明确购物目标的用户，检索系统就无法发挥它的作用了。 ( 2 ) 变浏览者为购买者：网站的浏览者通常只是浏览信息而没有购买意向。 如果推荐系统能够有针对性地向浏览者提供高质量的推荐信息，就可能激发浏览 者的购买兴趣，从而将他由浏览者转变为购买者。 ( 3 ) 增加交叉销售能力：例如推荐系统可以根据顾客当前购物车中的商品， 向顾客推荐他没有想到但可能会购买的与之相关的一些商品向顾客推荐额外有 价值的商品，将提高网站的交叉销售能力。 ( 4 ) 提供个性化的服务：一个成功的电子商务推荐系统要能够为用户提供个 性化的商品和服务，能够根据每位用户的兴趣特点，为他构建一个个性化的商品 库，实现“一对一 销售。 ( 5 ) 构建用户的忠诚度：在电子商务环境下，建立用户的忠诚度是电子商务 网站成功的关键点之一，因为用户更换交易商家极其便捷，只需要几次鼠标点击 3 第1 章绪论 操作便可。如果每次购买商品的时候，推荐系统都可以进行高效的商品推荐，无 疑会吸引顾客再次在该网站上选购商品。此外，推荐系统还可以学习顾客之间的 购买行为，帮助兴趣相似的用户建立联系，于是便有更多的用户受益于推荐系统 的个性化服务，从而有助于提高用户对该网站的忠诚度。 研究表明，在基于电子商务的销售行业使用个性化推荐系统后，销售额能提 高2 8 ，尤其在书籍、电影、c d 音像、日用百货等产品相对较为低廉并且产 品种类繁多的行业，以及用户使用推荐系统程度较高的行业，电子商务个性化推 荐系统能够大大提高企业的销售额。可以预见到，我国电子商务个性化推荐系统 将有一个相当广阔的发展前景。 1 2 2 电子商务推荐系统的构成 电子商务推荐系统主要由以下三个模块组成：输入模块、推荐方法模块、输 出模块( 王莉红，2 0 0 5 ) 。 ( 1 ) 输入模块 输入模块主要负责对用户信息的收集和更新。输入来源按时间来划分可以分 为用户当前的行为输入和用户访问过程中的历史行为输入，也可以分为个人输入 和群体输入两部分。用户个人输入主要指推荐系统的目标用户为了得到系统准确 的推荐结果而对一些项目进行评价，这些评价表达了用户自己的偏好。群体输入 主要指以群体形式出现的评价数据。 用户个人输入往往包括了用户注册信息输入、隐式浏览输入、显式浏览输入、 关键词项目属性输入和用户购买历史输入等。群体输入主要包括项目属性输入、 用户购买历史输入、文本评价输入、用户评分输入等。 ( 2 ) 推荐方法模块 推荐方法模块是整个电子商务个性化推荐系统的核心部分，它直接决定着推 荐系统的性能优劣。 目前电子商务推荐系统中常用的推荐方法有( 余力等，2 0 0 4 ) ： a ) 分类浏览。分类浏览是基于主题分类查找的方法，特点是符合用户的 习惯，易于被用户接受。这种方法缺点是：很多内容难以决定其所属 子类且分类查找方法所花的时间比较多，用户必须根据查找目标的内 容和分类标准一步步地缩小查找范围，缺乏自动化和智能化。很多 时候用户对自己的需求也是不清楚的，系统不能强求用户一次性用户 把自己的需求全部表达出来。所以尽管分类查找的方法广泛使用，但 实际上存在很严重的问题，必须通过其它的方法来弥补其缺陷。 4 第1 章绪论 坊基于内容的检索。基于内容的检索是一种传统的查找技术，也是使用 相当普遍和成熟的一种技术。其主要思想是根据查找目标所包含的主 要内容，在被查找范围内，寻找与目标匹配的内容。该方法优点是： 技术比较成熟，用户易于接受查找结果；缺点是：查找结果非常依赖 于内容的确定，不易发现用户新的和潜在的兴趣点，很多项目的内容 信息无法得到或者很难得到。 c ) 统计分析。电子商务网站将产品的购买或评分信息统计后呈现给顾客， 作为顾客购买商品的参考信息，如给用户推荐卖得最好的n 种商品等。 这种方法的优点是客观以及计算方便，但是没有考虑每个顾客的不同 需求，推荐缺乏个性化。由于这种方法实现简单且推荐原因易于理解， 所以很多网站都采用了这种方法，如最热门列表。 d ) 关联规则。推荐系统以诸如“购买本商品的人可能还会对以下商品感 兴趣”的形式向顾客提供经常同时购买的商品的信息。系统还可能根 据顾客购物篮中的商品向顾客推荐。 曲协同过滤。用户对一些有代表性的商品评分，系统根据和该用户评分 相近的顾客群体的兴趣偏好进行推荐。协同过滤最具个性化和针对性， 真正做到了一对一推荐，应用前景最为看好。该过程是由计算机自动 处理完成的，我们称之为自动推荐系统。这种方法的主要思想是推荐 出最符合用户兴趣的n 个项目，推荐结果的个性化程度最高，这也是 本文研究的重点。 ( 3 ) 输出模块 输出模块负责将推荐结果输出给用户。电子商务推荐系统的输出形式 主要包括：相关产品输出、个体文本评价输出、个体评分输出、平均数值 评分输出、电子邮件输出、编辑推荐输出等。 1 2 3 电子商务推荐系统的研究现状 a c m 从1 9 9 9 年开始每年召开一次关于电子商务的研讨会，每年的会议论文 中都有很多关于电子商务推荐系统的研究报告。a c m 下属的数据挖掘特别兴趣 研究组s i g k d d 于1 9 9 9 年设立w e b k d d 研讨组，主题集中在电子商务中的 w e b 挖掘技术。a c m 下属的信息检索特别兴趣研究组s i g i r 在其召开的第2 4 届研究和发展会议上，专门把推荐系统作为一个研究主题。其它一些与数据挖掘 和w e b 系统相关的会议也都将电子商务推荐系统列入研究主题。 电子推荐系统的研究内容很多，主要包括以下六个方面： 5 第1 章绪论 ( 1 ) 推荐方法的研究：目前主要的推荐方法有基于内容的过滤和协同过滤两 种，其中协同过滤是当前研究的主流。协同过滤的一个优点是不需要分 析对象的属性，它对推荐对象没有特殊的要求，能够处理非结构化的复 杂对象，例如音乐和电影等，这是基于内容的过滤难以做到的。 ( 2 ) 实时性研究：由于大型电子商务网站的规模越来越庞大，推荐系统的可 伸缩性和实时性要求越来越难以保证，如何满足推荐系统的实时性要求 便成为研究的重点。 ( 3 ) 推荐质量的研究：在大型电子商务网站中，用户评分的数据是相当稀疏 的，导致无法产生有效的推荐，推荐系统的质量难以保证。因此，提高 推荐系统质量的研究显得格外重要。 ( 4 ) 信息集成的研究：当前的电子商务推荐系统只利用了部分的可用信息来 进行推荐，为了提高推荐的质量，电子商务推荐系统应该收集多种类型 的数据有效集成多种推荐技术，充分挖掘和利用各种有用的信息。 ( 5 ) 数据挖掘技术在推荐系统中的应用研究：推荐系统主要利用数据挖掘等 技术发现用户的兴趣模式，然后产生个性化的信息推荐。数据挖掘技术 在推荐系统中的应用非常广泛，进行数据挖掘技术在推荐系统中的应用 研究十分必要。 ( 6 ) 系统性能评价的研究：要让推荐系统为广大用户所接受，必须对推荐系 统做出客观的评价，需要从准确性、个性化、安全性和用户满意度等多 方面进行评价。但是目前推荐系统的评价指标仅仅是准确率和召回率， 没有对整个推荐系统进行综合评价的标准。 目前电子商务推荐系统的研究热点主要是高质量、高效率的推荐算法的研究。 推荐算法是推荐系统的核心部分，它直接影响推荐系统的质量和性能。目前最为 成功的推荐算法是协同过滤，它能够利用与当前用户兴趣相似的顾客群体的观点 进行推荐。传统的协同过滤技术存在的稀疏性、可扩展性等问题严重影响了推荐 系统的性能，协同过滤技术的研究在学术领域占有重要的地位。 近几年电子商务的快速发展推动了推荐系统的发展，其商业应用不断的扩大， 诸如互联网上最大的书店a m a z o n c o r n ，w e b 上最大的c d 商店c d n o w c o r n ， 全球最大的c 2 c 网站淘宝网等等。由微软研究院开发的协同过滤工具己被 集成在微软的c o m m e r c es e r v e r 产品中，并被许多站点使用。协同过滤技术作为 在线购物网站的一部分越来越流行。 1 3 协同过滤技术概述 6 第1 章绪论 协同过滤( c o l l a b o r a t i v ef i l t e r i n g ) 技术是应用最为广泛的个性化推荐技术，是 推荐系统的一个重要组成部分。协同过滤通过参考与活动用户具有相似兴趣和需 求的其他用户的选择来决定如何为该用户进行信息过滤。协同过滤技术是知识获 取的一种方式之一，是从可利用的知识源中抽取形式化知识的过程( 孙小华，2 0 0 5 ) ”。用通俗的话来说，协同过滤就是“如果和我兴趣爱好相同的人喜欢这样东西， 那我也会喜欢这样东西的。这个概念是由g o l d b e r g 等人提出来，g o l d b e r g 运 用协同过滤技术建立了t a p e s t r y 系统( g o l d b e r g ，1 9 9 2 ) ，它是最早提出来的基于 协同过滤的推荐系统。o r o u p l e n s ( k o n s t a ne ta 1 1 9 9 7 ) 是基于用户评分的自动化 协同过滤推荐系统，用于推荐影片和新闻。 1 3 1 协同过滤技术的优缺点 迄今为止在个性化推荐系统中，协同过滤技术是应用最成功的技术。协同过 滤的最大优点是不需要分析对象的特征属性，对推荐对象没有特殊要求，能处理 非结构化的复杂对象。协同过滤有三个主要优点( 孙小华，2 0 0 5 ) 3 1 是基于内容 的过滤方法所没有的： ( 1 ) 在协同过滤中，人们在信息流中决定对一个项的兴趣、质量。因此可以 在计算机上过滤一些用计算机难以分析的项，如电影、c d 、思想、感觉、评论 等等。 ( 2 ) 协同过滤系统可以通过测试某一项目满足用户需要的程度来增强信息过 滤系统的性能，人们可以分析某一项目的质量或者其它内在品质，但计算机却难 以做到。一个基于内容的检索过程可以检索出所有张艺谋导演的电影，但如果将 基于内容的过滤系统与协同过滤系统相结合，则系统可以只返回张艺谋导演的那 些拍得确实好的电影。 ( 3 ) 协同过滤系统有时可以产生一些令人意想不到的推荐结果，而不仅仅是 用户原来就已经想到的推荐项目。协同过滤是根据用户的相似性来推荐资源，它 与基于内容的过滤技术不同，它比较的是用户描述文件，而不是资源与用户描述 文件。由于它是根据相似用户来推荐资源的，所以有可能为用户推荐出新的感兴 趣的内容。 尽管协同过滤技术在个性化推荐系统中获得了极大的成功，但随着站点结构、 内容的复杂度和用户人数的不断增加，协同过滤技术的一些缺点逐渐暴露出来， 主要有( h e d o c k e re ta 1 1 9 9 9 ) ： ( 1 ) 精确性( a c c u r a c y ) 问题：即提高对用户的推荐质量的挑战，用户需要一 个可以让他们感到信任的推荐系统来给他们提供项目的推荐。 7 第1 章绪论 ( 2 ) 稀疏性( s p a r s i t y ) 问题：在许多推荐系统中，每个用户涉及的信息量相 当有限，在一些大的系统如w w w a i i l a z o i l c o r n 网站中，用户最多不过就评估了 上百万本书的1 - 2 ，造成评估矩阵数据相当稀疏，难以找到相似用户集，导 致推荐效果大大降低。 ( 3 ) 冷启动( c o l ds t a r t ) 问题：分为新项目( n e wi t e m ) 问题和新用户( n e wu s e r ) 问题。如果一个新项目没有人去评价它，则这个项目肯定得不到推荐，推荐系统 就失去了作用，这在运用协同推荐技术的系统中最为突出。同样，如果一个新用 户从未对系统中的项目进行评价，则系统无法获知他的兴趣点也就无法对他进行 推荐。 ( 4 ) 扩展性( s c a l a b i l i t y ) 问题：现有大部分协同过滤算法的计算量随着用户 和项目的增加而大大增加，对于上百万之巨的数目，通常的算法将遭遇到严重的 扩展性问题，但由于大多数算法可以离线进行运算，随着计算机计算能力的不断 提高，可扩展性问题相对于前面几个问题来说不是特别严重。 ( 5 ) 安全性( s e c u r i t y ) 问题( 张富国等，2 0 0 8 ) ：在电子商务推荐系统中， 一些不法用户为维护自身利益，向推荐系统中输入大量伪造评分数据进行欺诈攻 击，人为干预算法的预测结果，导致推荐的精确度下降，严重危害了电子商务推 荐系统的公正性和安全性。因此协同过滤算法的抗攻击能力也日益成为衡量系统 稳定性和健壮性的一个重要指标，也成为各国研究者重视的研究领域，目前国内 对这方面的研究还处于起步阶段。 1 3 2 协同过滤技术的研究现状 b r e e z ee ta 1 ( 1 9 9 8 ) 根据协同过滤采用的算法将其分为两类，基于内存的 ( m e m o r y b a s e d ) 与基于模型的( m o d e l - b a s e d ) 。 基于内存的协同过滤先用统计的方法得到具有相似兴趣爱好的邻居用户，再 基于邻居进行计算，所以该方法也称为基于邻居的协同过滤。在进行推荐时，须 计算分析使用者历史记录，以找出与使用者偏好相似的邻近族群，其中最常使用 的方法为g r o u p l e n s 中使用的最近邻算法( k o n s t a n e ta 1 1 9 9 7 ) 。 基于内存的协同过滤利用整个用户项数据库来完成预测。这些系统使用统 计技术来找到活动用户的近邻集合，他们有与活动用户一致的历史纪录( 他们与 活动用户对于不同项的评价相似) 。一旦活动用户的最近邻被找到，这些系统会 使用不同的算法来综合这些最近邻的评价并由此为活动用户提供预测或者对n 个最高评价项进行推荐。这种算法具有计算方法简单的特点，精确度也往往比较 高，目前实际使用的协同过滤算法多属这种类型。但是任何一次预测都要基于数 8 第1 章绪论 据库的所有记录，无疑大大增加了计算量。在当今用户规模动辄达到数以百万计 的情况下，这个问题尤为严重。 基于模型的协同过滤( m bc f ) 主要是将使用者历史记录，通过统计方法或机 器学习方法来建构出使用者偏好模型，进而利用此偏好模型来产生推荐，目前所 使用的方法有关联规则法( a s s o c i a t i o nr u l e ) 、贝叶斯网络( b a y e s i a nn e t w o r k ) 、回归 分析( r e g r e s s i o na n a l y s i s ) ，奇异特征值分解( s i n g u l a rv a l u ed e c o m p o s i t i o n ，简称 s v d ) 等等。 m bc f 在模型建立的阶段计算量往往很大，但模型建立以后，当新的用户 或项出现时，可以很快将之分类。在实时推荐中它的运算速度比基于存储的方法 具有优势，因为复杂的预计算可以在非上线的时段完成。同时，模型本身也可能 含有某些有用的信息或规律。不足之处在于与基于全体存储纪录的方法相比，有 的算法可能会牺牲一定的精确度。 s a r w a re ta l ( 2 0 0 d 贝a 依据协同过滤技术所使用的事物之间的关联性，将基于 内存的协同过滤算法分为基于用户的算法u bc f ) 和基于项目的算法( i b。 c f ) ( 1 ) 基于用户的协同过滤：其核心概念是假设人与人之间的行为具有某种程 度的相似性，即购买行为类似的顾客，会购买相类似的产品。g r o u p l e n s 即属于 此类型的系统。 ( 2 ) 基于项目的协同过滤：其主要假设是项目与项目间具有某种程度的关联， 即顾客在购买时，其所购买的产品通常具有关联性，如顾客在购买电子游戏机时， 通常会购买电池及游戏卡匣。i bc f 首先计算项目之间的相关性，然后通过用户 对相关项目的评分预测用户对未评分项目的评分。 目前应用较多的是基于邻居用户的协同推荐算法，即最近邻算法。 l i bc f 运行的瓶颈是要在一个很大的用户群中找出合适的邻居，i bc f 可 以通过寻求项目之间的相似关系，而不是用户之间的相似关系来避免这个瓶颈问 题。i bc f 首先根据用户项目矩阵来求出不同项目之间的关系，然后利用这些 关系来推出给用户的推荐结果，给用户的推荐结果是通过发现与用户喜欢的项目 相似的项目来完成的。因为在典型的电子商务环境中，项目之间的关系相对来说 比较稳定，所以利用项目之间的相似性，i bc f 可以花费较少的在线计算时间来 得到与u bc f 准确性相近的预测结果，这种方法在某种程度上解决了l i bc f 存在的可扩展性问题。 近几年来，国内外学者针对协同过滤算法存在的多种问题展开了研究，并取 得了一定的成果。 为解决用户评分数据的稀疏性问题，s a r w a re ta l ( 2 0 0 0 ) 提出通过奇异值分解 减少项目空间维数的方法，但降维会导致信息损失，使得该方法在项目空间维数 9 第1 章绪论 较高的情况下难以保证推荐效果。邓爱林等( 2 0 0 3 ) 提出一种基于项目评分预 测的协同过滤推荐技术，通过估计用户评分的办法补充用户项矩阵，减小数据 稀疏性对计算结果的负面影响。周军锋等( 2 0 0 4 ) 在此基础上引入了项目分类 信息，采用修正的条件概率计算项目之间的相似性，并用于对用户没有评价过的 项目进行评分估计，填充用户项矩阵，进而根据填充了的用户项矩阵计算用户 相似性，取得了不错的效果。 协同过滤的安全性问题主要围绕以下两点展开研究：一、现有协同过滤推荐 算法对各种欺诈攻击类型的抵御能力研究；二、欺诈攻击的检测模型研究。 国外学者对各类协同过滤算法的抵御攻击的能力进行了系统的研究，并取得 一定的成果。l a me ta 1 ( 2 0 0 2 ) 对u bc f 和i bc f 分别做了各种攻击测试分析， 认为i b c f 比u b c f 有更好的抵御攻击的能力，以及推荐结果的呈现方式对攻 击效果也有一定影响、并对新项目的攻击问题提出一些建议。m o b a s h ee ta 1 ( 2 0 0 6 ) 则对基于模型的算法( k - m e a n s 聚类和p l s a ) 和l i bc f 进行了攻击效果对比 分析，认为p l s a 和k m e a n s 聚类方法在系统稳定性和健壮性方面比l i bc f 更 胜一筹。 目前研究的攻击检测模型主要有基础检测模型、c h i r i t a 检测模型以及分块检 测模型等。基础检测模型( o m a h o n y e ta 1 2 0 0 4 a ) 是通过比较每个用户的预测变 化值、用户评价值背离程度、与其他用户相适度、邻居用户相似程度和背离平均 度等指标来实现的。它的优点是综合了多个指标检测，形象直观；缺点是检测过 程较复杂。 c h i r i t a 检测模型是c h i f i t ae ta 1 ( 2 0 0 5 ) 在基础检测模型基础上提出了一种新的 检测模型及应用方案。它通过分析每个用户概貌的攻击可能度( p r o b a b i l i t yo f a t t a c k ) ，对最近邻算法中的相似度进行修正，从而提高了推荐系统的推荐质量。 然而该模型对低填充规模的攻击检测效果不好，且对分块攻击的检测效果也不好。 研究表明，现有的攻击检测模型对部分攻击类型的检测效果较好，但算法的复杂 度都偏高，需要对系统中的每一个用户的数据进行计算，影响了检测算法的可行 性。 1 4 本文的研究内容 由上节内容可知，协同过滤算法主要分为基于内存的协同过滤和基于模型的 协同过滤两类，这两类算法的典型代表分别为最近邻协同过滤算法和基于奇异值 分解的协同过滤算法，前者因其简单易用而被广泛应用于电子商务推荐系统，却 通常因数据的极度稀疏性和相似度度量方法的弊端导致算法的精度下降。后者则 1 0 第l 章绪论 通过矩阵奇异值分解的降维技术一定程度解决了数据稀疏性问题，然而目前国内 对该算法的健壮性和安全性研究较少。本文将分别以上述两种算法为载体，研究 算法的数据稀疏性问题和安全性问题，论文的主要工作如下： ( 1 ) 为解决协同过滤算法中数据稀疏性问题和传统相似度度量方法的弊端， 本文研究了最近邻协同过滤算法在不同的稀疏性问题解决方案下各相似度方法 的优化对算法性能的影响。通过实验对现有的各种常用相似度进行了基于用户评 分项目并集和基于相关加权因子的优化，分别确定了基于稀疏评分矩阵、缺省评 分矩阵和奇异值分解( s v d ) 预测评分矩阵的最近邻算法中的最优相似度方法， 有效地提高了各情况下算法的推荐精度。 ( 2 ) 针对协同过滤推荐系统遭受的欺诈攻击带来的安全性问题，本文研究了 典型的基于奇异值分解的协同过滤算法的抵御攻击的能力，通过设计不同规模和 攻击意图的攻击测试，以平均绝对偏差、平均预测偏移及平均命中率偏差这三种 评估参数分析了不同填充规模和攻击规模的攻击用户概貌对攻击效果的影响，同 时研究了不同攻击类型的攻击效果差异。 1 5 本文的组织 本文共分五章，文章结构和各章的内容安排如下： 第一章绪论。首先介绍了电子商务推荐系统和协同过滤技术的研究现状， 然后介绍了本文的研究工作，最后给出了本文的章节安排。 第二章协同过滤算法综述。介绍了主要的协同过滤算法的研究现状，详细 阐述了本文研究的最近邻协同过滤算法和基于奇异值分解的协同过滤算法，以及 协同过滤算法的评估指标。 第三章最近邻协同过滤算法的相似度优化研究。通过实验分析了多种稀疏 性问题的解决方案下，现有相似度度量方法的优化对最近邻算法性能的提升效果， 从而为各种情况下选取最合适的相似度优化方案，实现稀疏性的解决方案和相似 度优化方案的有效结合。 第四章基于奇异值分解的协同过滤算法的安全性研究。实验分析基于s v d 的协同过滤算法在不同攻击模型下的性能表现，并以三种评估参数分析不同填充 规模和攻击规模的攻击模型对攻击效率的影响。 第五章结束语。总结全文，指出了本文的研究成果和后续工作。 第2 章协同过滤算法综述 第2 章协同过滤算法综述 协同过滤算法主要被分为两类：一类是基于内存的协同过滤，另一类是基于 模型的协同过滤，两类算法均有各自的适用领域和缺陷，本章将简要介绍这两类 算法的典型代表算法的流程。本章的内容组织如下：第一节简单描述了协同过滤 推荐系统的实现过程，第二节详细介绍了本文研究的两类典型算法的步骤：最近 邻算法和基于s v d 的算法，第三节介绍了协同过滤推荐系统的评估标准和本文 的实验数据集。 2 1协同过滤系统简单描述 协同过滤也称为面向用户行为的技术，它通过分析用户的历史数据生成与当 前用户行为兴趣最相近的用户集，然后利用他们对项目的评分来预测当前用户对 项目的评分产生推荐列表即t o pn 推荐。 协同过滤系统根据其他客户的意见向目标客户推荐产品。系统采用统计技术 去发现一个称为“邻居”的用户集合，与