（计算机软件与理论专业论文）基于影响关系的协作过滤推荐算法研究.pdf

基于影响关系的协作过滤推荐算法研究 计算机软件与理论 硕士生：曲泉 指导教师：印鉴教授 摘要 推荐系统是电子商务应用中最重要的技术之一。推荐系统是根据用户以往的 购买或评分记录，根据推荐算法，向用户推荐其他产品的一种实用系统。各国的 研究者们为了使得算法产生精确的推荐，保证推荐系统的实时性要求，提出了各 种不同的推荐算法，如：协作过滤技术，b a y e s i a n 网络技术，聚类技术，关联规则 技术以及基于图的h e r r i n g 图技术等。其中，协作式过滤是至今最成功的推荐技 术，而它又分为基于用户的协作推荐和基于项目的协作推荐。 本文首先介绍了基于协作过滤的推荐算法的理论基础，从两个不同的考察角 度( 基于用户和基于项目) 对协作过滤算法进行了分析。然后基于多示例学习算 法中“参考”与“引用”的概念，提出了一种改进的结合k 最近邻居和k 逆最 近邻居的协作过滤算法。 改进算法是一种基于项目的协作过滤算法，它通过计算项目的相似性得出最 近的k 个邻居，然后找出k 逆最近邻居矩阵，综合考虑k 近邻和k 逆近邻的因 素，从而解决了以往协作过滤算法扩展性差和推荐信息量不足的缺点。 实验结果表明，在高维数据集的大量实验中，证明了本文提出的改进的协作过 滤算法在推荐质量方面优于以往算法。 关键字：协作过滤推荐k 最近邻k 逆最近邻 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 sb a s e do ni n f l u e n c er e l a t i o n s h i p 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 ：q uq i l a n 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 r e c o m m e n d a t i o ns y s t e mi so n eo ft h em o s ti m p o r t a n tt e c h n i c si 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 mw i l lr e c o m m e n ds o m en e wp r o d u c tt ou s e rb a s e do nt h e i r p u r c h a s er e c o r db e f o r e r e s e a r c h e r sf r o md i f f e r e n t c o u n t r i e sh a dp r o p o s e ds e v e r a l d i f f e r e n tr e c o m m e n d a t i o na l g o r i t h m s ，s u c ha s ：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 s , b a y e s i a nn e t ，c l u s t e r i n g ，a s s o c i a t i o n - r u l e sa n dh o r t i n ga l g o r i t h m sb a s e do nm a p c o l l a b o r a t i v ef i l t e r i n g a l g o r i t h m si s t h em o s ts u c c e e dr e c o m m e n d a t i o ns y s t e m t e c h n i c s ，a n dc fa l g o r i t h m si n c l u d et w ot y p e s ：c o l l a b o r a t i v ef i l t e r i n gb a s e d o nu s e r a n dc o l l a b o r a t i v ef i l t e r i n gb a s e d - o ni t e m i nt h i s p a p e r , f i r s t i n t r o d u c e dt h e t h e o r y f o u n d a t i o no fr e c o m m e n d a t i o n a l g o r i t h m sb a s e d - o nc o l l a b o r a t i v ef i l t e r i n g ，t h e na n a l y z e d t h ec 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 m sf r o mt w oa n g l e ：b a s e d o nu s e ra n db a s e d o ni t e m t h e n ，t h i s p a p e ri m p o r tt h ec o n c e p to f “r e f e r e n c e a n d “c i t e r i nm u l t i - i n s t a n c el e a r n i n g p r o p o s e da ni m p r o v e da l g o r i t h mw h i c hc o m b i n e st h ek n n ( k - n e a r e s tn e i g h b o r ) a n d r k n n ( r e v e r s e dk - n e a r e s tn e i g h b o r ) t h i sa l g o r i t h mi sac fa l g o r i t h mb a s e d - o ni t e m ，f i r s tc o m p u t et h ec o m p a r a b i l i t y b e t w e e ni t e m s ，g o tt h ek n nm a t r i x ，t h e nf i n dt h er k n nm a t r i xf r o mk n nm a t r i x s ow es o l v e dt h e e x p a n s i b i l i t yp r o b l e m a n dt h e p r o b l e m a b o u tl a c ko f r e c o m m e n d a t i o ni n f o r m a t i o nw h i c hb o t h e r e dt h ec fa l g o r i t h m sb e f o r e a tl a s t ，w e c o m p u t et h er e c o m m e n d a t i o nu s i n ga n e wp r o p o s e df o r m u l a a c c o r d i n gt ol o t so fe x p e r i m e n t ，w ep r o v e dt h a tt h en e wa l g o r i t h mi nt h i sp a p e r h a v eb e t t e rq u a l i t yt h a nt h ec l a s s i cc fa l g o r i t h m sb e f o r e k e yw o r d s ：c o l l a b o r a t i v ef i k e r i n gr e c o m m e n d a t i o nk - n e a r e s tn e i g h b o rr e v e r s e k - n e a r e s tn e i g h b o r 第1 章绪论 1 1推荐系统的应用背景 随着互联网的普及和电子商务的发展，计算机技术越来越广泛地应用到我们 生活的每一个角落。但是同时，网络上各种数据大量膨胀，旱在2 0 0 2 年，网页数量 就已经超过全球人口数量。如何在短时间内帮用户找到最需要的产品，节省客户 购物时间，吸引客户，提高忠诚度，是近年来电子商务网站普遍面临的一个巨大挑 战。 早期w e b 是以信息共享为主，近年来，电子商务、电子图书馆、远程教育等已 成为w e b 的主要应用，促使w e b 以更快的速度发展。同时，对w e b 站点的设计 和功能提出了更高的要求。要求w e b 具有智能性，能快速、准确地找到用户所需 信息；能为不同用户提供不同的服务；能允许用户根据自己的需要定制页面；能为 用户提供产品营销策略信息等等。完全彻底地实现所有功能是困难的，它需要在 人工智能和自然语言理解等方面有突破性进展。 事实上，在互联网上搜索信息，即便在功能r 益完善的搜索引擎的帮助下，浩 如烟海的大量相关信息仍然很难满足我们迅速定位的要求。在这种市场的需求 下，出现了w e b 个性化服务、推荐系统以及自适应站点等智能技术。 1 w e b 个性化服务 个性化服务( w e bp e r s o n a l i z a t i o ns e r v i c e ) ：w e b 服务器通过与用户交互的过 程收集用户的信息，服务器根据这些信息对用户请求的页面进行裁剪，为用户返 回定制的页面，其目的就是提高用户的满意度。例如：当用户注册提供个性化服 务的网站后，用户可以从服务器提供的选项中选取感兴趣的栏目( 新闻、股票、 天气预报、电视节目预报、交通状况等) 以及喜欢的页面风格、布局、颜色等， 以后，服务器响应该用户的请求时，就根据用户的定制信息将页面修改后返回给 用户。目前，许多网站都提供个性化服务，如：m y y a h o o l ( h t t p ：m y y a h o o c o r n ) 、 m y a o l ( h t t p ：m y a 0 1 c o r n ) 、m y n e t s c a p t e ( h t t p ：m y n e t s c a p e c o m ) 等。 在文献【1 】中提出用页面框架( p a g ef l a m e ) 实现个性化服务的技术思想，页 面框架由多个不同的部分构成，例如：对一个新闻网站，页面框架可能包含国内、 国际、科技、社会、体育等栏日，w e b 服务器对应每一栏目包含众多的素材，根 据当前用户的情况，w e b 服务器为页面框架中的各部分添加用户感兴趣的内容， 对个性化服务而言，用户要通过显式地圈定f 也她所感兴趣的内容，来完成 定制页面的工作。对于一个大的门户网站：如y a h o o ! ( h t t p ：1 w w w y a h o o c o r n ) ， 可能包含上百个选项，这就加重了用户的负担，另一方面，用户只有在很好的了 解了站点，才能作出正确的选择，所以，在用户深入了解站点之前，用户可能并 不知道怎样定制站点内容，因而也就不能充分享受w e b 站点的个性化服务。 2 推荐系统 r e s n i c k & v a r i a n 在1 9 9 7 年给出了电子商务推荐系统( r e c o m m e n a e rs y s t e m s 1 正式的定义。推荐系统：直观地讲，推荐系统就是w e b 服务器根据用户的喜 好，为用户推荐可能感兴趣的内容或者可能购买的商品。近几年电子商务的快速 发展推动了推荐系统的发展，推荐系统已经逐渐成为电子商务中的主流发展方 向。例如：g r o u p l e n s ( 丛! p ；f 婴5 垡! ! 垫旦曼d 婪堡垒s 塑丝b 丝自q ! ! 匹曼韭s 臣婴蛔塑sb ! 盟! ) 曼旦9 蛆h ! ! 壁；碰 w w w e b a y c o m ) 等都是包含推荐系统的电子商务网站。 推荐系统可以为电子商务网站带来一系列的好处：能够更好地吸引新的访问 者，并将访问者转变为购买者，同时可以增加客户在网站的滞留时间和他们对网 站的忠诚度( 1 0 y a l t y ) 。另外，推荐系统可以针对不同的推荐用户可能感兴趣的 广告，从而提高广告的效率，这一切最终将增加网站的利润。据因特网研究机构 j u p i t e rc o m m u n i c a t i o n s ( h t t p ：w w w j u p c o r n ) 报道1 3 1 ，通过对2 5 个电子商务消 费网站的观察发现，这些网站在提供了推荐系统后的第一年中，平均增加了4 7 的新客户，利润同比增加了5 2 。另一个因特网研究机构n i e l s e nn e t r a t i n g ( h t t p ：w w w n e t r a t i n g s c o r n ) 报道，与一般的电子商务网站比较，提供推荐系统 的电子商务网站可以将更多的访问者变为购买者。据因特网咨询公司a p p i a n ( h t t p ：w w w a p p i a n c o r p c o r n ) 的估计，随着电子商务中智能化的发展，由此带 来的利润将大幅度增加，预计2 0 0 3 年将达到5 3 亿美元。 推荐系统的自动化程度( d e g r e e o f a u t o m a t i o n ) 指用户为了得到推荐系统的 推荐是否需要显式的输入信息，而推荐系统的持久度( d e g r e eo f p e r s i s t e n c e ) 指 推荐系统产生推荐是基于客户当前的单个会话( s e s s i o n ) 还是基于客户的多个会 话。根据推荐系统的自动化程度和持久度这两个参数，可以将推荐推荐系统进行 2 分类： 非个性化推荐系统( n o 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 n ) 这种推荐系统独立于用户，所有访问的用户得到的推荐结果都是相同的。这 种推荐系统产生的推荐结果主要基于多数用户对于该产品的平均评价。例如： a n l a z o n 网站( h t t p ：w w w a m a z o n c o i n ) 的a v e r a g ec u s t o m e rr a t i n g e b a y 网站( h t t p ：w w w e b a y c o m ) 的c u s t o m e rc o m m e n t s 基于属性的推荐系统( a t t r i b u t e d b a s e dr e c o m m e n d a t i o n ) 推荐系统的推荐主要基于产品的属性特征为用户进行推荐，与用户的兴趣以 及浏览行为无关。例如： r e e l 网站( h t t p ：w w w r e e l c o m ) 的m o v i em a p a m a z o n 网站的d e l i v e r s 基于项目之间相关性的推荐系统( i t e m t o r c mc o r r e l a t i o n r c c o m m e n d a t i o n ) 推荐系统根据客户感兴趣的产品推荐与此相关的产品。例如： a m a z o n 网站的c u s t o m e r sw h ob o u g h tt h i sb o o ka l s ob o u g h t c d n o w 网站( h i t p ：w w w c d n o w c o m ) 的a l b u ma d v i s o r m o v i ef i n d e r 网站( h t t p ：w w w m o v i e f i n d e r c o m ) 的m a t c h m a k e r 基于客户相关性的推荐系统( p e o p l e t o p c o p l c c o r r e l a t i o n r e c o m m e n d a t i o n ) 这种推荐系统又称作基于协作过滤( c o l l a b o r a t i v ef i l t e r i n g ) 的推荐系统， 推荐系统根据客户与其他已经购买了商品的客户之间的相关性进行推荐。例如： a m a z o n 网站的b o o km a t c h e r m o v i ef i n d e r 网站的w cp r e d i c t 推荐系统中通常采用的技术有： 信息过滤( i n f o r m a t i o nf i l t e r i n g ) 将相关的信息发送给需要的用户。 基于内容的过滤( c o n t e n t b a s e df i l t e r i n g ) 根据文档的内容以及属性 为用户推荐文档。 协作过滤( c o l l a b o r a t i v ef i l t e r i n g ) 根据其他用户的评价和打分为用 户推荐。 目前，许多电子商务的网站，如m o v i e f i n d e r ( h t t p ：w w w m o v i e f i n d e r c o m ) 推荐系统【4 】中采用了协作过滤技术，基于协作过滤技术的推荐系统的构造过程 为：首先收集用户对各个文档的评分，根据用户的评分，将意见相似的用户进行 聚类，依据同一聚类中其他用户的评分为当前用户进行推荐。 基于协作过滤技术的推荐系统的主要限制是：必须有一定数量的文档被用户 评价和打分，并且被服务器推荐给用户的文档至少要有一个用户已经对它进行了 打分。同时，由于用户的评分标准不一样，导致打分有所偏差。例如：两个用户 同样都喜欢旅游，由于两个人的性格以及行事风格不同，其中一个用户对于自己 喜欢的东西，他最高只给4 分( 假设打分采用5 分制) ，而另外一个对于自己喜 欢的则给5 分，这两个分数虽然数值不同，但为其打分的两个用户都同等程度地 喜欢旅游，只是由于用户的自身原因造成分数值不同，系统根据这样的打分结果 进行推荐就可能会产生偏颇。 3 自适应站点 自适应站点( a d a p t i v e w e b s i t e ) ：通过观察用户的访问模式，自动改进站点 的结构和表现形式，以反映用户的兴趣所在。建立自适应站点的主要步骤是：发 现用户聚类，然后为每个聚类的用户建立配置文件( p r o f i l e ) ，并将之保存在w e b 服务器中。当用户访问站点时，服务器判断当前用户属于哪个聚类，寻找该聚类 相应的配置文件，并将用户请求的页面的经过变形后返回给用户。自适应站点的 目的是为用户推荐页面的变化或是站点结构的变化，以更加适合用户的需求。 相对于个性化服务，自适应站点可以将用户的定制属性在一定范围内共享。 将具有相似兴趣和目的的用户进行分组，组内的用户具有相同的定制属性，如果 一些用户对站点的某一部分感兴趣，那么相应组内的其它用户的定制属性也将随 之改变。 1 2国内外研究现状 各国的研究者们为了使得算法产生精确的推荐，保证推荐系统的实时性要求， 研究者提出了各种不同的推荐算法，如：协作过滤技术，基于项目的协作过滤推 荐，b a y e s i a n 网络技术，聚类技术，关联规则技术以及基于图的h o r t i n g 图技术 等。 4 目前，推荐技术主要有两种：基于内容的推荐和协同推荐【2 1 。其中，协同式过滤 是至今最成功的推荐系统技术【5 l ，并且在网络中许多成功的推荐系统已经得到使 用。协同式过滤推荐产品给用户是基于其它用户的意见。协同式推荐系统使用历 史信息来识别用户的邻居，并且分析这些邻居来识别有可能被这个用户喜欢的信 息，我们叫这种方法为基于用户的推荐算法。 t y p e s t r y l 6 j 是最早提出来的基于协作过滤的推荐系统，目标用户需要明确指 出与自己行为比较类似的其他用户。g r o u p k 璐【4 】是基于用户评分的自动化协作 过滤推荐系统，用于推荐电影和新闻。r i n g o 推荐系统【8 1 和v i d e o 推荐系纠9 】通过 电子邮件的方式分别推荐音乐和电影。b r e e s e l 5 】等人对各种协作过滤推荐算法及 其改进进行了深入分析。 传统的协作过滤推荐通过用户的最近邻居产生最终的推荐，基于项目的协作 过滤推荐首先计算项目之间的相关性，然后通过用户对相关项目的评分预测用户 对未评分项目的评分1 1 0 l 。 b a y e s i a n 网络技术利用训练集创建相应的模型1 1 1 】，模型用决策树表示，节点 和边表示用户信息。训练得到的模型非常小，所以对模型的应用非常快。这种方 法适合于用户的兴趣爱好变化比较慢的场合。 聚类技术将具有相似兴趣爱好的用户分配到相同的簇1 1 2 , 1 3 ，聚类产生之后， 根据簇中其他用户对商品的评价预测目标用户对该商品的评价。由于聚类过程离 线进行，所以在线的推荐算法产生推荐的速度比较快。 关联规则技术在零售业得到了广泛的应用，关联规则挖掘可以发现不同商品 在销售过程中的相关性。基于关联规则的推荐算法根据生成的关联规则模型和用 户当前的购买行为向用户产生推荐f 1 4 1 。关联规则模型的生成可以离线进行，因此 可以保证有效地推荐系统的实时性要求。 h o r t i n g 图技术是一种基于图的方法【1 5 】，节点代表用户，边代表两个用户之 间的相似度。在图中搜索近邻节点，然后综合近邻节点的评分形成最后的推荐。 h o r t i n g 图技术可以跳过中间节点寻找最近邻居，考虑了节点之间的传递相似关 系。因此，推荐精度优于最近邻协作过滤技术。 除此之外，h y b r i d 系统【1 6 1 还通过将各种不同的过滤技术进行混合应用以得 到更好的推荐。 5 针对数据的极端稀疏性问题，文献1 7 】提出通过奇异值分解( s v d ) 减少项目空 间的维数，使得用户在降维后的项目空间上对每一个项目均有评分，实验结果表 明这种方法可以有效地解决同义词( s y n o n y m y ) 问题，显著地提高推荐系统的伸 缩能力。但降维会导致信息损失，降维效果与数据集密切相关，在项目空间维数很 高的情况下，降维的效果难以保证1 1 8 l 。 1 3 本文的工作 本文通过改进原有的协作过滤算法，来提高算法的推荐精度。受到多示例学习 中引入逆k 最近邻居的启发，本文在基于项目的协作过滤算法基础上，加入了k 逆 最近邻居的思想，并且使用了多种相似性度量和推荐公式。实验表明与未加入逆 最近邻的朴素算法相比，能够比较显著的提高推荐精度，并且算法和原有算法是同 复杂度。从而在不加大算法负担的情况下提高了算法的推荐精度。 本文安排如下： 第1 章中主要介绍推荐系统的产生，概念和研究意义，本文的研究内容以及主 要工作，最后是本文的章节安排。 第2 章先重点介绍推荐系统中协作过滤算法的技术现状，概述了两个主要算 法的基本情况，然后着重阐述分析了协作过滤推荐系统现存的主要问题。 第3 章详细解释了本文针对协作过滤推荐算法改进中所用到的相关知识：k 最近邻以及k 逆最近邻，并把两者结合起来应用于新算法中。 第4 章详细阐述了本文对基于项目的协作过滤推荐算法所提出的改良解决方 案以及核心算法。 第5 章先给出了一般的协作过滤推荐系统的实验结果，然后给出了本文的改 进方案的实验结果及其分析，通过比较来证明改良算法的正确性。 第6 章总结了本文的研究成果和所做的工作，分析了本文的创新点，最后对 下一步工作的开展提供了一些建议。 6 第2 章基于协作过滤的推荐算法 2 1经典协作过滤推荐技术 目前。推荐技术主要有两种：基于内容的推荐和协作推荐【2 l ，其中，协作式过滤 是至今最成功的推荐系统技术，并且在网络中许多成功的推荐系统已经得到使 用。协作式过滤推荐产品给用户是基于其它用户的意见。 协作式推荐系统使用历史信息来识别邻居，并且通过分析这些邻居来识别有 可能被这个用户喜欢的信息。现行的协作过滤推荐算法按照寻找邻居的方式，主 要分为以下两种：基于用户的过滤推荐和基于项目的过滤推荐。 2 1 1 基于用户的协作过滤推荐技术 基于用户的协作过滤推荐技术根据其他用户的观点产生对目标用户的推荐 列表，它基于这样一个假设【s 】：如果用户对一些项目的评分比较相似，则他们对其 它项目的评分也比较相似。协作过滤推荐系统使用统计技术搜索目标用户的若干 最近邻居，然后根据最近邻居对项目的评分来预测目标用户对项目的评分，产生 对应的推荐列表。 为了找到目标用户的最近邻居，必须度量用户之间的相似性，然后选择相似 性最高的若干用户作为目标用户的最近邻居。目标用户的最近邻居查询是否准确 直接关系到整个推荐系统的推荐质量，准确查询目标用户的最近邻居是整个协作 过滤推荐成功的关键。 下面详细介绍基于用户的协作过滤推荐算法。 用户评分数据可以用一个m 冗阶矩阵a ( m ，n ) 表示，i n 行代表m 个用户，n 列代表n 个项目，第i 行第j 列的元素足，代表用户i 对项目j 的评分。用户 评分数据矩阵如图2 1 所示。 图2 一l 用户评分数据矩阵 度量用户i 和用户j 之间相似性的方法是，首先得到经用户i 和用户j 评 分的所有项目，然后通过不同的相似性度量方法计算用户i 和用户j 之间的相 似性，记为s i m ( i ，j ) 。 而衡量相似度的算法有很多，普遍用于过滤算法中的相似性度量公式有以下 三种： 余弦相似性( c o s i n e ) 两个用户被看做是n 维项目空问上的向量，如果用户对项目没有进行评分， 则将用户对该项目的评分设为0 ，项目问的相似性通过向量间的余弦夹角度量。 设用户i 和用户j 在n 维项目空间上的评分分别表示为向量i 和j ，则它们之间 的相似性s i m ( i ，j ) 为： 酊叫u ) _ c o s ( 不7 ) 2 赫 分子为两个用户评分向量的内积，分母为两个用户向量模的乘积。 相关相似性( c o r r e l a t i o n ) ： 设由用户i 和j 都评过分的项目集合用u 表示，则用户i 和用户j 之间的相 似性s i m ( i ，j ) ，通过p e a r s o n 相关系数度量： i 、。，。印限，。一元) ( 马，一豆) c i n , ”i d q j 。忑鬟盖- - 蔬2 蓊r r 。表示用户i 对项目u 的评分，和瓦为项耳u 的平均评分。 8 修正的余弦相似性( a d j u s t e dc o s i n e ) ： 在余弦相似性度量方法中没有考虑不同用户的评分尺度问题，修正的余弦相 似性度量方法通过减去相应用户对项目的平均评分来改善上述缺陷，设由用户i 和j 都评过分的项目集合用u 表示，则用户i 和用户j 之间的相似性s i m ( i ，j ) ： 咖刚，2 衰筹鼎 r 。表示用户i 对项目u 的评分，和藏为用户i 对所有项目的平均评分。 推荐公式 在得到了相似用户之后，之后就是整个算法中最重要的步骤：产生推荐。 有两种推荐公式现在被广泛采用，分别是： 1 设用户的最近邻居集合用表示，则用户埘项目j 的预测评分 户也珂以通过最近邻居集合j m 中用户对项目的评分得到，计算方法如下 【5 】： p “= r + 盖咖“咖删 。美( 胁i ) g 。1 s f r o ( i , 力表示用户j 与用户j 之间的相似性，r u , 秭示用户u 对项目珀q 评 分，瓦表示用户i 对所有项目的平均评分。 2 第二种推荐公式不考虑项目的平均评分，仅考虑项目之间的相似性 和评分【1 0 】 9 分。 一，：奎竺竺竺 弘 。磊。( m ) i ) q 心 s i r e ( i , 力表示用户与用户j 之间的相似性，r u , j 表示用户u 对项目珀g 评 2 1 2 基于项目的协作过滤推荐技术 由于用户评分数据的极端稀疏性，传统的相似性度量方法不能有效地计算目 标用户的最近邻居，协作过滤推荐系统的推荐质量难以保证。为了解决用户评分 数据的极端稀疏往，最简单的办法就是将用户对未评分项目的评分设为一个固定 的缺省值( 一般设为评分域的中间值，如在5 分制评分中设为3 ) ，或者设为用户 的平均评分，实验表明，这种改进方法可以有效地提高协作过滤推荐系统的推荐 精度p j 。 显然，用户对未评分项目的评分不可能完全相同，因此上述改进方法并不能 从根本上解决用户评分数据极端稀疏情况下传统相似性度量方法存在的问题。 因此，另外一种更具有广泛性的算法应运而生，这种算法通过计算项目问的 相似性，由用户对相似项目的评分预测用户对未评分项目的评分，使得用户之间 共同评分的条目比较多，从而可以有效地解决用户评分数据极端稀疏情况下传统 相似性度量方法存在的不足，使得计算得到的最近邻居比较准确。 基于项目评分预测的协作过滤推荐算法与基于用户得协作过滤推荐基本步 骤相同，不同的在于相似性度量公式，下面分别详细说明。 余弦相似性( c o s i n 田 在此类算法中，项目是考察的基本对象。 两个项目被看做是m 维项目空间上的向量，如果用户对项目没有进行评分， 则将用户对该项目的评分设为0 ，项目问的相似性通过向量间的余弦夹角度量， 设项目i 和项目j 在m 维用户空间上的评分分别表示为向量i 和j ，则它们之间 的相似性s i m ( i ，j ) 为： 豇邮一酊国2 晌 分子为两个项目评分向量的内积，分母为两个项目向量模的乘积。 相关相似性( c o r r e l a t i o n ) ： 对于基于项目的协作过滤算法，相关相似性计算的是项目与项目之间的相似 度。这种相似度是通过计算两个项目之间共同评分项的距离来实现的( 如图 2 2 ) 。 ( 垦塑) - ll r 熊 匹二盈 剿隧 啤r r l | _ 设对项目i 和j 都评过分的用户集合用u 表示，则项目i 和项目j 之间的相 似性s i m ( i ，j ) ，通过p e a r s o n 相关系数度量是： n ，一。曰( r i - 蘑) 慨厂秀) e i m ( i 、r ，d 吖畔2 忑鬟焉_ - - 透2 券r 咒。表示用户u 对项目i 的评分，和豆为所有用户对项目i 的平均评分。 1 1 n ；0j，j v ，p，l； 32 修正的余弦相似性( a d j u s t e dc o s i n e ) ： 与相关相似性类似，对于基于项目的协作过滤算法，修正的余弦相似性计算 的是项目与项目之间的相似度。这种相似度也是通过计算两个项目之间共f 司评分 项的距离来实现的 设对项目i 和j 都评过分的用户集合用u 表示，则用户i 和用户j 之间的相 似性s i m ( i ，j ) ： s i m ( i ，) = 瓦表示用户u 对项目的平均评分。 推荐公式 与基于用户的协作过滤推荐算法有所不同，这里的推荐公式所有的考察项均 落在项目上。 1 设项目i 的最近邻居集合用船v m 表示，则用户尉项目j 的预测评分见， 可以通过用户尉最近邻居集合阳眦中项目的评分得到，计算方法如下： 见i = 冠+五咖( f d 啦, - r ) 盖( 愀i ) 偿3 s 砌( t 力表示项目j 与项目j 之间的相似性，m 濠示用户u 对项目珀q 评 分，瓦表示所有用户对项目i 的平均评分。 2 第二种推荐公式不考虑项目的平均评分，仅考虑项目之间的相似性和评 分【1 0 】 s i m ( i ，小阮，) 既；2 篙 ， 五( 愀栅 u 叫 2 2 协作过滤推荐算法现存问题分析 协作过滤是目前最成功的推荐系统技术，并且在网络中的许多成功的推荐系 统中已经得到应用。协作过滤推荐产品给用户是基于其他用户的意见，这类系统 使用历史信息来识别用户的邻居，并且分析这些邻居来识别有可能被这个用户喜 欢的信息。这种传统的协作过滤推荐技术被称为基于用户的推荐算法。 但是，传统的协作过滤推荐系统遇到几个主要的限制。 第一个限制就是缺乏扩展性。基于内存的k 最近邻居算法要求推荐算法的邻 居构造过程必须在线进行，且随着用户数和产品数的增加，算法所需要的计算时 间也相应增加。对于非常大的数据集来说，用户可能无法忍受产生推荐所需要的 等待时间，尤其当协作过滤算法的输入数据为w e b 使用数据，扩展性更差，因为 在这种情况下，用户的浏览模式被用于间接得到用户对内容喜好的程度，计算用 户间相似性降低了系统的性能。 第二个重要的限制是数据集极端稀疏【1 0 】。在实践中，许多商业推荐系统的 产品集合非常大，如a m a z o n c o m 和c d n o w t o m ，它们分别销售和推荐书籍和音 乐专辑。在这些系统中，即使是非常活跃的用户，也只是购买过低于1 的产品 ( 2 0 0 百万本书的1 为2 万本) 。因此，一个基于最近邻居算法的推荐系统可能 无法将任何产品推荐给某一特定用户，而且这样所产生的推荐精度不高。随着数 据库中项目数的增加，每位用户评过分的项目百分数相对减少，结果用户间共同 评过分的项目数的百分比也降低了，导致相关度计算结果可靠性低，难以产生可 靠的预测。另外，在许多推荐系统中，用户和项目的历史信息的数量经常是有限 的，使协作过滤推荐系统不能准确地计算出邻居和识别推荐项目，导致了贫穷的 推荐。 第三个是同义问题。在现实生活中，不同的商品名字可以代表相同或相似的 对象。基于相关度的推荐系统不能找到这类潜在关联，因此将这些相似的商品看 成完全不同类别的商品。举个例子，有这样两个客户，一个购买1 0 本信纸，另 一个购买1 0 本备忘录，基于相关度计算的推荐系统会认为这两个购买的商品集 合没有任何交集或关系，导致无法发现它们之问的潜在关联，因为这两类产品同 属于办公室用品。 最后，这类系统的一个明显的限制就是，无法为新的或最近增加的项目产生 预测或推荐。也就是说一个用户对一个新增项目的评分无法与其他用户对该项目 的评分比较，进一步讲系统绝对无法为还没被访问过或评过分的新增项目产生评 分预测。这个问题通常被成为“新项目问题”。 本文所提出的改进算法，主要针对第二个问题，即数据稀疏性造成的训练信 息不足的问题进行了改良。 1 4 第3 章集成r k n n 的协作过滤推荐算法 3 1k n n 和r k n n 问题综述 目前，k 最近邻居问题，简称i ( n n ( k - n e a r e s tn e i g h b o r ) 问题，在国内外 已经得到了深入的研究和广泛的应用，尤其是在空间数据的查询方面，如地理信 息系统、信息检索等领域。k n n 算法是数据挖掘中的一个重要的算法，一般用于 分类( c l a s s i f i c a t i o n ) 、聚类( c l u s t e r i n g ) 和预测( p r e d i c t i o n ) 。文本分类 是k n n 算法在分类方面的一个重要应用。随着文本信息的快速增长，尤其是 i n t e r n e t 资源信息的迅猛发展，文本分类已经是现代信息处理研究的一大热点。 一般文本分类分两步进行，首先依据某种原则进行文本的特征提取，然后对特征 进行处理以得到文本分类结果。k n n 算法就是一种基于文本特征向量空间模型表 示的文本分类方法，有较好的应用结果。另外，网站经营者也可以用k 最近邻居 算法对访问网站的用户资料进行分类，对各类用户采用不同的个性化界面和不同 的宣传策略。在预测方面，k n n 算法也有一定的应用。由于距离相近的对象通常 他们的预测值也相似，因此只要知道一个对象的预测值，就可以用它来预测它的 k 最近邻居的值。 近来，在该领域内，有一类问题的出现吸引了许多理论研究者和应用系统设 计者的重视和兴趣。例如在无线通信系统中，数据库保存了各个信息基站的地理 位置信息，假设每个移动用户的移动设备( 例如移动电话、p d a 等) 只能接受距 离它最近的3 个基站发送的信息，那么，如何确认每个信息发送控制中心管辖的 范围? 换句话说，哪些移动用户会受到指定基站的影响? 该类问题统称为“影响 集”( i n f l u e n c es e t s ) 问题 1 9 1 ，它是k 一最近邻居的逆问题，可以通过算法的逆 算法算法来解决。k 最近邻居问题的逆问题逆k 最近邻居( r e v e r s ek n e a r e s t n e i g h b o r s ) 问题的出现于是吸引了许多理论研究者和应用系统设计者的重视和 兴趣。r k n n 查询主要用于市场决策、电子商务和无线通信等领域。下面的例子 很好的阐述了r k n n 查询的作用。 例一：顾客进行网上购物有多种影响因素，商品种类、价格、送货速度、付 款方式等等。购物网站经营者经常希望了解哪类顾客最有可能在他们的网站购买 商品，且哪些客户对哪几类商品最感兴趣，也就是目标客户群的查找问题，以便 有针对性地发送商品信息给顾客。假如某购物网站现对某商品进行促销，而经营 者想将促销信息发送给对这种商品最感兴趣的网站顾客，那么他所需要做的就是 把这种商品作为查询点q ，而所有顾客以往的购物历史作为数据集s ，那么r k n n ( q ) 返回的就是对这类商品最感兴趣的顾客群。当获取到这些顾客的资料后， 就可以有目的地针对这些顾客的购物偏好进行资料的发送、邮寄和宣传。 例二：随着移动电话的普及，各种手机游戏应运而生。早期的手机游戏只是 单机的，随着移动通信技术的发展，g p r s 的诞生，手机联网游戏也开始出现。 假如有一种枪战游戏，游戏的规则就是射击离自己最近的参加该游戏的手机用 户。那么你不仅需要查找自己的最近邻居，同时还要查找自己的逆最近邻居，也 就是把自己当成射击目标的游戏参加者，以移动到另一地点避免被对方击中。在 游戏过程中，每个用户都是随时在移动的，这时的r n n 查找虽然动态数据集的查 找，但归根到底还是r n n 问题的应用。 以上两个例子就是r k n n 在具体领域的应用。例一主要介绍了r k n n 查询在电 子商务方面的应用而例- - n 是动态r k n n 查询在无线电通信技术方面的应用。 总的来说，k n n 查询算法是找寻给定集合中与指定点距离最近的k 个点的过 程：而r k n n 查询算法则是在给定集合中查询将指定点视为k 最近邻居的点的集 合。 3 1 1k 最近邻居问题基本定义 k n n ( k - n e a r e s tn e i g h b o r ) 问题是在最近邻居问题基础上扩展出来的。什 么是k 最近邻居? 给定一个数据集s 和一查询点q ，求q 的k 最近邻居也就是求 s 中离q 点距离最近的k 个点的集合。这里的距离，以两点间的欧几里德距离 ( e u c l i d e a nd i s t a n c e ) 定义。另外，k 的定义有两种，一种仅重视邻居的个数， 即使这k 个邻居与查询点的距离都相同：另一种则表示距离的个数，即返回与查 询点距离最小的k 个距离，这就要求这k 个距离不能重复，本文采用第一种定义。 给定数据集s 和查询点q ，k n n 的形式化定义如下： 定义l ：i n n 查询似n e a r e s tn e i g h b o rq u e r y ) 是指在数据集s 中查找k 个与q 距离最近的点的集合。 1 6 妇v n ( q ) - s c _ s i v p e s ，v r e s 一乳o ( q ，p ) d ( ) ，- k 参数k 是根据需要而改变的，一般是经验值。 3 1 2k 逆最近邻居的基本定义 k e r n 和s m u t h u k r i s h n a n 1 9 】首次提出了逆最近邻居( r n n ) 的概念，给出了 其基本的定义、定理及相关证明，详细介绍了如何在静态和动态数据集中进行 r n n 查询的做法，并给出r n n 的扩展定义r k n n 及其朴素的查询算法思想。 在这里，我们在k o r n 的定义基础上，根据本文需要定义一种r k n n ( r e v e r s e k n e a r e s tn e i g h b o r s ) ，叫k 逆最近邻居问题，是指在给定的集合中查询将指定 点视为其最近邻居的k 个点的集合。当我们查找r k n n ( q ) 时，返回的是把q 视 为k n n 的那一类点。假设给定一个数据集s 和一个查询点q ，k 是事先定好的一 个经验参数，那么r k n n 的形式化定义如下： 定义2 ：k 逆最近邻居查询( r e v e r s ekn e a r e s tn e i g h b o ro u e r y ) 是指在 数据集s 中查找将g 视为最近邻居的k 个点的集合。 r k n n ( q ) - 侈s i y p s ，p e i n n ( p ) ，l i s l | - k r k n n 查询与k n n 查询虽然有着密切联系，却并不完全对称。最主要的原因在 于k 最近邻居的关系是不对称的，q k n n o ) 一，p e k n n ( q ) 。反之亦然，例如： 图3 - 1k n n 与r k n n 关系示意图 据定义，1 n n ( q ) - i s ) ，r i n n ( s ) - u ) 。 3 1 3k n n 与r k n n 在推荐系统中的应用 近些年来，在推荐系统中，k n n 与其逆问题r k n n 在推荐系统中得到了广泛的 应用，并且取得了很好的成果，在电子商务网站个性化推荐，商务智能，决策支持 等领域均有了很好的应用实例。下面分别介绍单独的k n n 应用和集成了r k n n 问 1 7 题的应用。 单纯使用k n n 的推荐系统 k 一最近邻居查询方面，相关的理论和实现都已经发展得比较成熟，国内外学 者也就此提出了大量相关的数据结构、求解算法及其评价和具体应用等。r i v e s t ， c l e a r y