（管理科学与工程专业论文）基于P2P结构的分布式协同过滤系统研究.pdf

摘要 摘要 个性化电子商务推荐系统在过去几年得到迅速发展。许多大型的商 业网站已经使用推荐系统为其客户推荐产品。例如a m a zo n 、e b a y 、淘宝 等。这些推荐技术是网站个性化的一部分，它使网站自身适应每个用户 的需求。推荐算法是推荐系统的核心。协同过滤算法是最常用的推荐算 法。协同过滤推荐系统找出与用户兴趣相似的其他用户，通过其他用户 的评分来预测用户的感兴趣的商品。但是，由于协同过滤算法存在扩展 性等问题。算法的复杂度随着用户和项的数量的增加而急剧上升。因此， 需要应用分布式协同过滤来解决这样的问题。 基于以上的问题，本文在一般协同过滤系统的研究基础上，利用分 布式计算和j x t a 实现了分布式协同过滤，其中有以下内容：( a ) 分布式 计算。将中心化的数据库的数据分别分配到p 2 p 网络中的对等体进行相 似性运算，每个对等体负责计算一部分数据，然后每个对等体将计算的 结果返回给分配任务的对等体。这个对等体将其他对等体返回的部分数 据进行汇总。利用分布式计算可以有效减少计算项相似度的运算量，并 且充分利用p 2 p 网络中闲置的资源。( b ) 利用s ur l 公司提出的p 2 p 规范 协议j x t a 开发出一套p 2 p 协同过滤系统。系统主要功能包括：( 1 ) 该系 统充分利用j x t a 的几个关键属性来实现数据传输与数据查询。如利用通 告来建立接收信息的限制。利用j x t a s e r v e rs o c k e t 用来监听信息，凡是 不满足通告内容的数据都不会被系统接收等。( 2 ) 该系统属于完全分布 式系统，每个对等点之间共同充当客户器与服务器的角色。数据库储存 的数据是一些相似度很高的用户的评分数据，系统就是通过这些数据来 对用户进行协同过滤推荐。( 3 ) 对等点储存部分的数据，这些数据是动 态的，随时变动的。系统会将数据库里面相似度最低的用户数据作为阈 值，进入对等体的数据相似值大于阈值，将会存入邻集数据库中。 关键词协同过滤；个性化推荐：j x t a 架构；分布式；p 2 p 结构 广东工业大学硕七学位论文 a b s t r a c t r e c o m m e n d e rs y s t e m sa r ec h a n g i n gr a p i d l yi nr e c e n ty e a r s m a n yo f t h el a r g e s tc o m m e r c ew e bs i t e sa r ea l r e a d yu s i n gr e c o m m e n d e rs y s t e m st o h e l pt h e i rc u s t o m e r sf i n dp r o d u c tt op u r c h a s e ( e g ：a m a z o n ；e b a y ；t a o b a o ) t h e s et e c h n i q u e sa r ep a r to fp e r s o n a l i z a t i o no nas i t e ，t h e yh e l pt h es i t e a d a p ti t s e l ft oe a c hc u s t o m e r r e c o m m e n d e ra l g o r i t h m sa r et h ec o r eo f r e c o m m e n d e rs y s t e m s c o l l a b o r a t i v e f i l t e r i n g i si nc o m m o nu s ea m o n g t h e m c o l l a b o r a t i v er e c o m m e n d e rs y s t e m st r yt op r e d i c tt h eu t i l i t yo fi t e m s f o rap a r t i c u l a ru s e rb a s e do nt h ei t e m sp r e v i o u s l yr a t e db yo t h e ru s e r s h o w e v e r ，s i n c et r a d i t i o n a lc o l l a b o r a t i v ef i l t e r i n gl a c k so fs c a l a b i l i t y ，i t s c o m p l e x i t yi n c r e a s e da st h en u m b e r so fu s e r sa n di t e m si n c r e a s e d t og e t a r o u n dt h i s p r o b l e m ，w e c a ni m p l e m e n tc o l l a b o r a t i v e f i l t e r i n g i na d e c e n t r a l i z e dw a y b a s e do nt h ep r o b l e m sa b o v e ，t h i sp a p e r ，o nt h eb a s i so fr e s e a r c h e s a b o u tc o l l a b o r a t i v e f i l t e r i n g ，p r e s e n t s ap 2 pd i s t r i b u t e dc 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 mb a s e do nd i s t r i b u t e dc o m p u t i n ga n dj x t am a i nc o n t e n t s i n c l u d e ：( a ) d i s t r i b u t e dc o m p u t i n g a s s i g n i n gc e n t r a l i z e dd a t at op e e r st o c o m p l e t es i m i l a r i t yc o m p u t a t i o ni nt h ep 2 pn e t w o r k e a c hp e e rt a k e sc h a r g e o fc o m p u t i n gs e g m e n t s ，a n dt h e yr e t u r nt h er e s u l t st ot h a tp e e rw h i c h a s s i g n s t a s k s t h i sp e e rc o l l e c t sa l lt h ed a t at h a to t h e rp e e r sr e t u r n ( b ) i m p l e m e n t i n gp 2 pc o l l a b o r a t i v ef i l t e r i n gb a s e do nj x t aw h i c hi sap 2 p p r o t o c o ls p e c i f i c a t i o nd e v e l o p e db y s u n c o r p o r a t i o n m a i n f u n c t i o n s i n c l u d e ：( 1 ) t h es y s t e mi m p l e m e n t sd a t at r a n s m i s s i o na n dd a t aq u e r yu s i n g s o m ek e ya t t r i b u t e so fj x t a f o re x a m p l e ，t h es y s t e mu s e sa d v e r t i s e m e n t s t oe s t a b l i s hs o m ec o n s t r a i n so nr e c e i v i n gd a t a ，a n du s e sj x t a s e r v e r s o c k e t t ol i s t e ni n ( 2 ) t h ss y s t e mb e l o n g st od e c e n t r a l i z e du n s t r u c t u r e dt o p o l o g y e a c hp e e ri nt h es y s t e mi sb o t hs e r v e ra n dc l i e n t ，t h ed a t ai nt h ed a t a b a s e s t o r er a t e da n d h i g h s i m i l a r p o i n t s t h es y s t e m u s e sd a t at om a k e r e c o m m e n d a t i o nf o ru s e r s ( 3 ) e a c hp e e rs t o r e sp a r t so fd a t a t h ed a t aa r e i i 摘要 d y n a m i ca n dc a nb eu p d a t e da ta n yt i m e t h ed a t ao fm i n i m u ms i m i l a r i t yi s f e t c h e da sat h r e s h o l d d a t aw i l lb ei n s e r t e di n t on e i g h b o rs e ti fd a t a sv a l u e i sm o r et h a nt h et h r e s h o l d k e y w o rdsc o l l a b o r a t i v e f i l t e r i n g ； p e r s o n a l i z e d r e c o m m e n d a t i o n ； j x t a f r a m e w o r k ；d i s t r i b u t e d ；p 2 ps t r u c t u r e i l l 独创性声明 独创性声明 秉承学校严谨的学风与优良的科学道德，本人声明所呈交的论文是我个人在 导师的指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以 标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，不包 含本人或其他用途使用过的成果。与我一同工作的同志对本研究所做的任何贡献 均已在论文中作了明确的说明，并表示了谢意。 本学位论文成果是本人在广东工业大学读书期间在导师的指导下取得的，论 文成果归广东工业大学所有。 申请学位论文与资料若有不实之处，本人承担一切相关责任，特此声明。 敝作者擗厶豫f 悟 、 指导刻噬字啊芝嘭 沙1 7 年铲月z d 日 7 1 第一章绪论 1 1 背景与意义 第一章绪论 随着互联网的普及和电子商务的发展，电子商务系统在为用户提 供越来越多选择的同时，其结构也变得更加复杂，用户经常会迷失在 大量的商品信息空间中，无法顺利找到自己需要的商品。个性化电子 商务推荐系统直接与用户交互，模拟商店销售人员向用户提供商品推 荐，帮助用户找到所需商品，从而顺利完成购买过程。在日趋激烈的 竞争环境下，个性化电子商务推荐系统能有效保留用户、防止用户流失， 提高电子商务系统的销售。 电子商务推荐系统逐渐应用在电子商务网站上，其用途是帮助用户 搜寻到自身需要的商品。它可以帮助用户从数以百万中的商品中找到合 适自身需要的商品，它可以为用户推荐多种商品选择，因此，推荐系统 在当前得到广泛应用。 推荐算法是个性化推荐系统的核心，贯穿于用户输入推荐请求到推 荐结果输出的全过程。目前，主要的个性化推荐算法有协同过滤推荐、 基于规则的推荐、基于人口的推荐、基于内容的推荐、基于效用的推荐、 基于知识的推荐等，其中基于内容的推荐和协同过滤的应用较广。 1 1 1 内容过滤推荐技术 内容过滤主要采用自然语言处理、人工智能、概率统计和机器学习 等技术进行过滤。通过相关特征的属性来定义项目或对象系统基于用户 评价对象的特征学习用户的兴趣，依据用户资料与待预测项目的匹配程 度进行推荐，努力向客户推荐与其以喜欢的产品或者相似的产品。如新 闻组过滤系统n e w sw e e d e r 。基于内容过滤的系统其优点是简单、有效。 其缺点是特征提取的能力有限并且过份细化。纯基于内容的推荐系统不 能为客户发现新的感兴趣的资源，只能发现和客户已有兴趣相似的资源。 这种方法通常被限制在容易分析内容的商品的推荐而对于那些较难提取 广东t 业大学硕七学位论文 出内容的商品，如音乐cd 、电影等就不能产生满意的推荐效果。 1 1 2 协同过滤技术 协同过滤是在信息过滤和信息系统中正迅速成为一项很受欢迎的技 术。与传统的基于内容过滤直接分析内容进行推荐不同。协同过滤技术 基本思想是基于评分相似的最近邻居的评分数据向目标用户产生推荐， 推荐算法处理的基础数据是不同用户对项目的评价。评价可以是布尔型 的也可以是实数，数值的大小代表喜欢的程度，也称为评分。协同过滤分 析用户兴趣，在用户群中找到指定用户的相似( 兴趣) 用户，综合这些 相似用户对某一信息的评价，形成系统对该指定用户对此信息的喜好程 度预测。协同过滤有利于判断符合用户兴趣的商品。 与传统文本过滤相比，协同过滤有下列优点： 1 ) 能够过滤难以进行机器自动内容分析的信息，如艺术品、音乐等。 共享其他人的经验，避免了内容分析的不完全和不精确，并且能够基于 一些复杂的，难以表述的概念( 如信息质量、个人品味) 进行过滤。 2 ) 有推荐新信息的能力。可以发现内容上完全不相似的信息，用户 对推荐信息的内容事先是预料不到的。这也是协同过滤和基于内容的过 滤一个较大的差别，基于内容的过滤推荐很多都是用户本来就熟悉的内 容，而协同过滤可以发现用户潜在的但自己尚未发现的兴趣偏好。 3 ) 能够有效的使用其他相似用户的反馈信息，较少用户的反馈量， 加快个性学习的速度。 协同过滤作为一种典型的推荐技术有其相当的应用，但协同过滤仍 有许多的问题需要解决。最典型的问题有稀疏问题( s p a r s i t y ) 和可扩展 问题( s e a l a b i l i t y ) 。 在协同过滤推荐算法中，全局数值算法能及时利用最新的信息为用 户产生相对准确的用户兴趣度预测或进行推荐，但是面对日益增多的用 户，数据量的急剧增加，算法的扩展性问题( 即适应系统规模不断扩大的 问题) 成为制约推荐系统实施的重要因素。虽然与基于模型的算法相比， 全局数值算法节约了为建立模型而花费的训练时间，但是用于识别“最近 邻居”算法的计算量随着用户和项的增加而大大增加，对于上百万的数 2 第一章绪论 目，通常的算法会遇到严重的扩展性瓶颈问题。该问题解决不好，直接 影响着基于协同过滤技术的推荐系统实时向用户提供推荐问题的解决， 而推荐系统的实时性越好，精确度越高，该系统才会被用户所接受。因 此，分布式协同过滤为了解决这个问题而提出的。采用分布式的方法来 实现最近邻协同过滤推荐算法是克服传统电子商务推荐系统计算复杂度 及其可扩展性问题的一个有效方法。p 2 p 网络由于其在可扩展性方面的 优势变的越来越流行，构造一种基于p 2 p 网络的协同过滤推荐方法将可 以极大的增加协同过滤推荐系统的可扩展性，并且可以利用分布在网络 上的资源来有效地解决时空计算复杂度的问题。 因此，研究分布式协同过滤系统有其重要的意义。 1 2 文献综述 1 2 1 概述 协同过滤算法( c o l l a b o r a t i v ef i l t e r i n g ，简称：c f ) 是当前推荐系统 中最有效的技术之一。现在大多数推荐系统采用集中式协同过滤算法， 传统协同过滤基于存储在本地数据库用户的评分来产生推荐。随着站 点结构、内容复杂度和用户人数的不断增加，在时间和空间上的计算 的复杂度会快速增加，所以传统c f 算法面临着可扩展性问题。而分 布式协同过滤算法( d i s t r i b u t e dc o l l a b o r a t i v ef i l t e r i n g 简称：d c f ) 可 以有效解决可扩展性的问题。 1 2 2 传统协同过滤算法与分布式协同过滤算法区别 自g o l d b e r g 等人在l9 9 2 年提出c f 算法【2 1 】开始，c f 算法理论以 极快的速度发展，已得到了广泛的应用。文献【2 】中提到了大量的研究 型推荐系统实例。例如：x e r o o xp a r c 研究中心的t y p e s t r y 、 c a r n e g i e m e l l o n 大学的a c f 系统、m i t 开发的g r o u p l e n s 、r i n g o 系 统等等。这些系统都是基于c f 算法技术来进行信息过滤。 根据文献 3 】，常用c f 算法可以分为1 ) 基于记忆的过滤算法。例 如基于用户( u s e r b a e s d ) c f 算法，基于项( i t e m b a s e d ) 【4 】c f 算法等。 广东t 业大学硕十学位论文 2 ) 基于模型的过滤算法。例如贝叶斯网、聚类分析、决策树等。以上 的方法共同特征是需要一个集中的数据库来管理用户数据，以及运算 过程非常复杂。 目前大多数d c f 系统都是通过p 2 p 网络实现。在文献 5 中详细 介绍了p 2 p 。p 2 p 的优点有很多，其中1 ) 在网络中存在成千上万台计 算机，计算机之间可以相互传递资源。2 ) 对等点之间可以不通过连接 服务器来进行资源信息交换，可以在很短时间内完成任务。3 ) 对等体 ( p e e r ) 可以很容易进出网络，而且对整个网络的影响不大，这样的 系统比其他系统更健壮，容错能力更好。 p 2 p 应用可分为：并行应用、内容与文件管理应用、协同应用。 d c f 系统属于协同应用。与传统c f 系统相比，d c f 系统要求每个对 等体存储一部分用户数据，当为某个用户进行推荐时，需要从其他对 等体检索到其数据到目标用户数据库进行计算。 因此，d c f 需要解决两个问题1 ) ) 如何将用户数据划分到各个节 点，当需要时能够有效的检索到。2 ) 当需要为特定用户预测时，如何 识别所需的记录并且可以有效的检索到。 1 2 3 国内外研究现状 ( 1 ) 国外研究现状 2 0 01 年a t v e i t 在p e e r t o p e e rb a s e dr e c o m m e n d a t i o n sf o rm o b i l e c o m m e r c e 中首次提出分布式协同过滤算法m 】，移动用户可以透过软件代 理在p 2 p 平台上获得推荐。不足之处是，代理之间的通讯基于一种网络 泛洪机制，这种机制增加了网络的开销。之后，在文献【6 】中提出了一种 改进的方法，但这种方法降低了邻居集的形成阶段的效率。b m s a r w a r 等人在文献 7 中，提出了分布式协同过滤系统的分类，以及提出了在电 子商务不同领域中的框架结构。这些研究大多数还没有通过现实的试验 测试，而且没有分析到影响推荐质量的因素。p o c k e t l e n s 比较了5 种分 布式架构的优劣，通过实验得到的结论是没有一种架构是完美的，但其 中的d h t 架构在推荐质量上与集中式最接近。s h l o m o 、b e r k o v s k y 等人 在文献 8 】提出了基于l o u d v o i c e 的协同过滤系统。l o u d v o i c e 是多代理 4 第一章绪论 通讯平台，它基于信道组播原理。本地数据仓库封装在信道里面，信道 之间通过随机代理调解器来进行链接通讯。j u n w a n g 等在文献 1 8 ，1 9 】 提出了自组织s o d c f ，其特点是利用b u d d yt a b l e 来记录i t e m 之间关联 度。j a ek y e o n gk i m 等人在文献 2 0 】中提出了p e o r 推荐系统，该系统 用来向用户推荐图像，其特点是通过用户对图像下载等行为获取其隐性 评分。d i a z a v i l e s 等人在文献 3 7 提出了基于代理的分布式协同过滤框 架。 ( 2 ) 国内研究现状 在国内分布式协同过滤还处在起步阶段，有代表性的是上海交通大 学 9 ，1 0 】的p i p e c f 以及改进的d c f l a 。孙雨等人在文献 1 1 】中提到了 利用多生成树路由算法来搜索邻居方法的p 2 p 分布式协同过滤系统。郭 锋、林颖等人砸文献 16 中提出了基于p 2 p 网路的自组织推荐系统。 1 3 本文研究的内容和目标 研究目标：研究和设计一个基于j x t a 平台的分布式协同过滤系统。 运行该系统的用户( 对等点) 能够进行互相通信。每个用户都能从对等 组内的相似性用户组的评分中，利用协同过滤算法产生推荐。每个对等 点各自保留自己的评分的数据以及t o p n 个用户的评分数据，这些数据 以x m l 形式储存。 下面是研究的具体研究的内容： 第二章研究个性化推荐系统及其种类。研究集中式协同过滤技术的 原理及分类，分析u s e r b a s e d 和i t e m b a s e d 协同过滤技术的优势和不足。 第三章介绍p 2 p 的相关概念，介绍p 2 p 平台的分类、优势和p 2 p 智 能数据分析的内容。 第四章研究分布式协同过滤技术的现状，分析分布式协同过滤的优 势，尤其是p 2 p 平台自身的优势。展示几种经典的分布式协同过滤系统。 第五章是利用当前流行的开源p 2 p 平台j x t a ，设计一个分布式协 同过滤系统。使得协同过滤技术在充分利用p 2 p 优势的情况下突破自身 的瓶颈。其中包括以下几点： ( 1 ) 研究协同过滤算法中基于用户的协同过滤算法。算法先使用统 5 广东t 业人学硕l ：学位论文 计技术寻找与目标用户有相同喜好的邻居，然后根据目标用户的邻居的 偏好产生向目标用户的推荐。研究基于用户的协同过滤算法在分布式情 况下的实现问题。改进基于用户算法来提高搜索邻居效率。 ( 2 ) 研究j x t a 的核心技术。在j x t a 网络中建立推荐用户组，让 网络中的用户加入该组进行相互推荐。研究如何有效的通过对等体发现 协议( p d p ) 自动寻找j x t a 资源，通过j x t a 的管道服务来对使得对等 体( 用户) 之间进行有效通讯。 ( 3 ) 研究如何用x m l 存储用户评分数据。通过文件格式定义功能 ( d t d ) 规范数据的格式，规范标签名名称，研究如何通过x m ld o m 是 用于获取、更改、添加或删除x m l 元素。 6 第二章个性化推荐系统，0 协同过滤算法 第二章个性化推荐系统与协同过滤算法 2 1 个性化推荐系统 2 1 1 个性化推荐系统简介 推荐系统的推荐形式包括：为用户推荐商品，提供商品信息，汇总 用户意见，为用户提供其他用户的评论。总的来说，这些推荐技术是网 站个性化的一部分，因为它使用网络自身适应每个用户的需求。推荐系 统跟其他销售系统、供应链决策支持系统很类似，但却又不同。推荐系 统直接与用户打交道，协助他们找到自身所需要的产品。 推荐系统用以下四种方式来加强了电子商务网站的产品销售【 】： ( 1 ) 将浏览器演变为卖家。以前，网站来访者访问网站时，总是 随意浏览一下网站信息，基本上不会购买产品。现在，推荐系统充当卖 家角色，帮助并推荐用户找到其合适的产品。 ( 2 ) 增强了交叉销售的方式：交叉销售( c r o s ss e l l i n g ) 是一种发 现顾客多种需求，并满足其多种需求的营销方式，从横向角度开发产品 市场，是营销人员在完成本职工作以后，主动积极的向现有客户、市场 等销售其他的、额外的产品或服务。交叉销售是在同一个客户身上挖掘、 开拓更多的顾客需求，而不是只满足于客户某次的购买需求，横向的开 拓市场。 ( 3 ) 建立起忠诚度：获得用户忠诚度是商业战略的其中一个重要 部分。推荐系统通过数值来建立用户与该网站的相关度。为了了解他们 的客户，网络中推荐系统可以帮助公司了解客户的需要。客户使用推荐 系统越多，他们对网站的忠诚度就越高。 ( 4 )数据挖掘与推荐系统：销售者利用自己所获得的用户交易数 据来分析客户的消费行为。数据挖掘就是用来分析数据的一门技术，其 中一种比较有名的应用在电子商务方面的数据挖掘技术是关联规则，它 可以发掘商品与商品之间的关联度。 7 广东i 业大掌碗士学位论文 2 1 2 个性化推荐系统案例 许多大型网站已经应用推荐系统去帮助他们的顾客找到合适的商 品。推荐系统从顾客中了解到其购买的兴趣，并为其推荐其他商品。 j o e p r i c e 认为，企业仅仅生产某种类产品已经远远不够，企业应最 低限度生产多种类型的产品满足不同顾客的多种需求。电子商务的出现， 使企业能够为顾客提供更多的选择，在种情况下，企业必须增加各种各 样的产品信息，这样顾客才能透过这些信息去购买满足自己需求的产品。 其中，推荐系统就是为解决这样的问题而出现的。推荐系统利用电子商 务网站，为顾客推荐产品。推荐的产品可以在网站上显示出来，它们基 于顾客的特性或者客户以前的购买的记录来预测客户未来的购买行为。 下面是推荐系统的几个经典例子： ( 1 ) a m a z o n 和许多电子商务网站一样，a m a z o n 的产品网页包括：商品的基本 信息、商品的购买信息。当用户购买完意见商品后，客户还可以找到系 统推荐的一些推荐信息。例如网站会推荐一些其他商品，这些商品是其 他人所购买的商品。当有新的商品加入时，a m a z o n 的e y e s 功能通过电 子邮件通知客户，客户可以键入相关的信息。例如书的作者、题目、内 容、i s b n 号码或者出版日期等信息来查找书籍。另外，用户可以使用简 单或者复杂的查询来查找合适的商品。客户还可以利用b o o k m a t e h e r 这 个功能来反馈对该商品的满意程度，用户还可以对购买的商品进行评分， 评分的范围是1 - 5 ，分别表示厌恶到喜欢的程度。c u s t o m e r e o m m e n t s 是 用户评论的功能，它允许用户对评分的商品进行评论。 c u s t o sw h ob o u g h tt h i si t e ma l s ob o u g h t ( 2 ) c d n o w 1h 图2 e f e 。1 ea m a z o n m 推荐a z o f i g u r e2t h e f u n c t i o no f a m a z o 翌n 巽c c o m m e n d a t i 。nlsr c c o m m e n d a t i o n 第一二章个性化推荐系统与协同过滤算法 该网站的系统分为两个模式，在单一的模式下，用户提交某一个歌 曲专辑的名字，系统会返回10 个其他专辑的推荐。在多人模式下，用户 键入3 个歌手的名称，系统会协助用户找到10 个这些歌手的专辑的推荐。 其中客户可以利用m y c d n o w 这个功能根据自身喜爱的歌手和专辑名 称来建立自己的个人唱片商店，通过这个商店，客户表达了他们对那些 歌手、那些唱片感兴趣。当客户购买了某张唱片时，其个人商店也会将 该唱片自动加入到列表中。当用户请求系统推荐时，系统会根据用户过 去的购买记录来为用户进行推荐。在系统推荐的产品列表中，每个产品 有一个选择，用户可以通过该选择将信息反馈给系统。例如，用户对该 推荐的产品不满意，那么用户可以通过选择按钮将产品信息反馈给系统， 系统会根据用户的反馈信息调整推荐策略。 ( 3 ) e b a y e b a y 的反馈机制允许买家或者卖家将信息反馈给与他们做买卖的 其他客户。这个反馈信息包括满意度评分、对该客户的评论等。反馈机 制为购买者提供一个类似推荐系统的功能，购买者可以查看卖家的资料。 这个资料中有一个表，表里面包含了过去7 天、过去一个月、过去半年 每个评分值的数量，并且购买者可以查看其他客户对该卖家的评分和评 论。 ( 4 ) l e v i s l e v i s 的s t y l e f i n d e r 功能使得用户可以从其网站上获取衣服的推荐信 息。客户进入网站后，首先输入自己的性别，然后系统会提供三种类型 的衣服，每种类型的衣服数量大约3 - 4 件。客户对每件衣服进行评分( 1 7 分) ，当客户评分的数据足够多的时候，客户可以选择推荐的功能获取系 统的推荐。客户获取推荐后，可以反馈信息，系统会根据客户的反馈信 息调整推荐策略。 ( 5 ) m o v i e f i n d e r 客户指定一个电影的名字，m o v i e f i n d e r z 的m a t c h m a k e r 功能可以通 过该电影帮助用户查找与该电影的名字、类型、演员相类似的电影。另 外，系统还可以根据用户对某些电影的评分值，( a f ) 来为客户推荐。 随着客户对电影的评分数量的增加，系统也相应调整相应的电影。 9 广东丁业大学硕十学位论文 ( 6 ) r e e l c o r n r e e l e o m 的推荐系统和a m a z o n 类似。都是在一个页面上推荐相似 性的其他商品。 由以上6 个例子可以看出，推荐系统应具备以下的功能： 浏览：过去，一位顾客走进一间影音店购买电影，并且叫职员推荐 5 0 年代的喜剧片，这位职员推荐几部符合他要求的片子。但是，这种推 荐的范围是职员自身所知道的片子。现在，像r e e l t o m 为电影导航实现 了浏览的功能。用户可以获得良好的推荐，并且该推荐局限性降低了。 相似项：像r e e l c o r n 这样的网站都会根据用户之间的购买记录来为 用户推荐与用户兴趣相类似的商品。 电子邮件：推荐系统还可以通过电子邮件进行为用户进行推荐，例 如a m a z o n 的e y e s 通过发电子邮件告诉客户当前增加了那些新的商品。 这样做可以比其他网站更快让用户了解到新的产品。这样网站将客户的 流失量减少到最低。 评论：越来越多的网站开始加入客户点评功能。a m a z o n 等网站允 许买家对卖家的产品以及对卖家进行评分。当某个买家浏览到某个商品， 并且该商品获得大部分人认可时，该商品就会获得买家的信任。 评分：除了允许用户对商品进行评论外，对商品的评分值也是一个 反映用户对商品满意度的一个指标。它也间接反映了商品的质量和购买 者对其的偏好。 t o p n ：a m a z o n 等网站为用户推荐t o p n 个商品。网站根据用户 的购买偏好，为用户推荐t o p n 个用户还没有评分的其他商品。这样做 好两个好处，第一，浏览器充当卖家的角色，为用户推荐商品，并且为 用户推荐的n 个商品都是用户比较感兴趣的。第二，它可以为用户提供 决策。用户可以从这n 个商品中选择，而不必为选择成千上万的商品感 到苦恼。 l o 第二章个性化推荐系统与协同过滤算法 2 2 集中式协同过滤算法 2 2 1 协同过滤发展 第一个使用协同过滤的系统是i n f o r m a t i o nt a p e s t r y 的x e r o xp a r c 。 系统其中一个功能是文档的搜索查找。使用该系统的用户可以通过之前 使用过的用户对文档的评论来搜索文档。系统不足在于不能有过多用户 同步使用。u s e n e t 改进了x e r o xp a r c 的缺点，他能够容纳数量巨大的 用户群，用户根据文章受欢迎的程度对其进行评分，然后系统会根据这 些评分为用户推荐文章。 篪 篪 3e ， 麓一! 叠l = | 乏l 一缀 、 同焘 篪l l 麓 纛 图2 - 2u s e n e t 的结构图 f i g u r e2 2t h es t r u c t u r eo fu s e n e t 如图2 2 所示，其中服务器的原点表示每个服务器所管理的群组， 服务器之间的箭头表示每个服务器所管理的群组之间对文章的共享，客 户端与服务器之间箭头表示客户与该服务器进行通信，客户端在该服务 器上上传下载文章，服务器端为客户推荐文章。 在推荐音乐方面，最早利用协同过滤算法在互联网上为用户推荐音 乐的是f i r e f l y ，它是是m i tm e d i al a b 早期研究的项目。最后f i r e f l y 被 微软公司收购。 除了以上提到的应用协同过滤算法的系统外，还有m i t 研究的 g r o u p l e n s ，r i n g o ，a m a z o n 、d i g g c o r n 、i t u n e 、l i b r a r yt h i n g s 等等。 由此看到，协同过滤的应用非常广泛。 2 2 2 常用的协同过滤算法 常用c f 算法可以分为1 ) 基于记忆的过滤算法。例如基于用户 至些奎兰塑圭茎堡耋圣 ( u s e r b a e s d ) c f 算法，基于项( i t e m b a s e d ) c f 算法等。2 ) 基于模型 的过滤算法。例如贝叶斯网、聚类分析、决策树等。 表2 - 1 协同过滤算法分类 基于记忆的协同过滤算法 基于模型的协同过滤算法 最近邻居 贝叶斯网络 聚类聚类 圈论人t 神经网络 线性回归 概率模型 2 2 2 1 协同过滤的原理 图2 - 3 协同过滤算法原理图 f i g u r e2 - 3t h ep r i n c i p l e so fc 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 图2 3 是协同过滤算法的原理图，推荐系统利用记录了用户对商品 的评分数据，根据各种协同过滤算法来预测某个用户对他没有评分的商 品的预测值，然后再将t o p n 个商品推荐给该用户。 协同过滤算法的总体公式如下表示： 0 ，= a g g r 21 ) 其中，表示用户c 对j 的评分值，；表示和用户c 相似的_ v 个用户的 集合，该集合中个用户对项j 进行了评分。 a g g r 函数可以有几种具体方式，分别为 第二章个性化推荐系统与协同过滤算法 b ) ，。= k s i m ( c ，c ) x c e 仑 c ) ，= i + 足s 砌( 叩) ( 名，一劢 c e 仑 其中k 为归一化因素 j i = 1 协( 叩) f d e 会 ( 2 2 ) ( 2 3 ) ( 2 4 ) ( 2 5 ) 用公式( 2 5 ) 表示，用户c 与用户c 之间的相似性用s i m ( c ，c ) 表示。 s i m ( c ，c ) 作为以上推荐公式的权重，用户c 的邻居越多，权重就越多，那 么推荐质量越精确。以上三个公式中，公式( 2 4 ) 比前两个科学。公式 ( 2 2 ) 没有计算权重，公式( 2 3 ) 虽然引入了权重，但没有考虑到不同 用户对评分数值范围的一统。公式( 2 4 ) 解决了上面两个问题。 由此看出，要计算名，的关键是计算出s i m ( c ，c ) ，两用户之间的相似 度。计算用户相似度的方法有很多种，通常主要用到余弦相似性和相关 性。下面介绍这两种方法： 1 ) 余弦相关计算 s f 研( 石，y ) = c 。s ( ；，歹) 2 赫2 ( 2 6 ) 其中两个不同用户分别用x 和y 表示，表示用户x 和y 同时都有评 分的商品列表( 项列表) ，用公式表示如下：岛= j si ，& o ， 在余弦相似方法中，用户x 和y 看作是两个m 维向量并且朋= l l 。之后 两个用户向量的余弦相似性就用公式( 2 6 ) 表示。 2 ) p e a r s o n s 相关计算 ( 厂i ) ( o 厂i ) “州屯2 蠢羔i 霞丽 q 7 vs e 6 x yj e j 秽 公式( 2 7 ) 与( 2 6 ) 的不同之处是它减去了x 和) ，对以前评分的项 r c 叠 一 1 1 名 幻 广东工业大学硕十学位论文 的平均评分值和0 。 2 2 2 2u s e r - b a s e d 基于用户协同过滤算法 u s e r b a s e d 协同过滤算法基于这样一个假设：如果用户对一些项的评 分比较相似，则他们对其它项的评分也比较相似。协同过滤推荐系统使 用统计技术搜索目标用户的若干最近邻居，然后根据最近邻居对项目的 评分预测目标用户对项目的评分，产生对应的推荐列表基于用户的协同 过滤算法可以分为三个步骤：发现邻居、邻居中用户数据比较、产生推 荐数据集合。 图2 4 邻居相似性图 f i g u r e2 - 4n e i g h b o rs i m i l a r i t y 图2 4 中，中间表示目标用户，用户之间的直线表示其他用户与目 标用户之间距离。直线的长度表示用户之间的相似度。直线长度越短， 表示目标用户与该用户之间的相似度越高。在邻居形成阶段，最关键是 如何选择用户的子集来表示邻居。图中的圆圈表示邻居集，圈内的用户 就是目标用户的邻居。通过这些邻居来预测目标用户对某个未评分项的 评分值。协同过滤的目标是帮助目标用户预测他还没有评分的项的值， 如2 2 表所示： 1 4 第二章个性化推荐系统与协同过滤算法 表2 - 2 用户评分表 湫 i t e m1i t e m2i t e m3i t e m4 i t e m u s e r134 1 u s e r2 4 5 9 2 u s e r3 9 531 例如，要预测u s e r 一1 对i t e m 一4 的评分值，发现u s e r 一2 的评分与 u s e r 一1 的评分很相似，于是u s e r 一2 就可以作为u s e r _ 1 的邻居。邻居发 现的算法有很多种，在这里主要用到p e a r s o n 相关。通过p e a r s o n 相关获 得邻居集合后，就可以通过公式( 2 7 ) 来计算预测值。 2 2 2 3 it e m - b a s e d 基于项协同过滤算法 i t e m b a s e d 协同过滤推荐根据用户对相似项的评分预测该用户对目 标项的评分，它基于这样一个假设：如果大部分用户对一些项的评分比 较相似，则当前用户对这些项的评分也比较相似。i t e m - b a s e d 协同过滤算法 是计算项之间的相似值，如图2 5 所示。 123i j n ln 、 r 。 r 。 、 r 、- 石 - i ， r ， r i t e m b a s e d 算法是计 算项与项之问的相 似性。例如计算i 与j 的相似性，所用到 的评分值的用户是 同时对i 与j 都评分的 用户 图2 - 5i t e m b a s e d 算法原理图 f i g u r e2 - 5t h ep r i n c i p l e so fi t e m b a s e da l g o r i t h m 例如要计算f 和j 的相似值，首先从矩阵中得到用户1 、2 和m - 1 对i 和评分，之后再利用余弦算法、或者p e a r s o n s 公式来计算相似值s ，。 使用i t e m b a s e d 算法最典型的例子是a m a z o n t 2 ，i 。 1 5 广东工业大学硕士学位论文 i t e m - b a s e d 算法其中一个扩展的例子是s l o p eo n e 算法f 2 2 】，s l o p eo n e 算法也是利用项之间的相似性来预测目标用户未评分的项的值。但s l o p e o n e 并没有用相似性公式计算项之间的相似性，而是通过项之间的差来 计算项的相似性。 s l o p eo n e 算法的优点是： 1 易于实现和维护：普通工程师可以轻松解释所有的聚合数据，并 且算法易于实现和测试。 2 运行时可更新的：新增一个评分项，应该对预测结果即时产生影 响。 3 高效率的查询响应：快速的执行查询，可能需要付出更多的空间 占用作为代价。 4 对初次访问者要求少：对于一个评分项目很少的用户，也应该可 以获得有效的推荐，解决冷启动问题。 5 合理的准确性：与最准确的方法相比，此方法应该是有竞争力的， 准确性方面的微小增长不能以简单性和扩展性的大量牺牲为代价。 i j i4 u ) ，、 。r 1 k ll1 5u ，e r a ； 目 i i l 2 ； ?u ，盯b ： i t e m ii 怔m j ，一上 图2 - 6s l o p eo n e 简单例子 f i g u r e2 - 6a ne x a m p l eo fs l o p eo n e s l o p eo n e 的基本原理可以用图2 - 6 一个例子介绍。 假设用户彳对给项目l 的评分为1 ，用户b 给l 的评分为2 ，4 为项 厶的打分为1 5 ，在a 的评分中，厶比厶的分数高1 5 1 = 0 5 分，那么可 以从中预测到用户口将会对厶的评分为2 + 0 5 = 2 5 2 2 3 协同过滤引擎介绍 1 6 第二章个性化推荐系统与协同过滤算法 t a s t e t 2 ，】是利用j a v a 开发的协同过滤引擎，它具有灵活、运算快等特 点。它取得用户对项的偏好值( 评分) ，之后估计目标用户对其他项的偏 好值。例如，购物网站可以利用过去用户的购买记录的数据来估计出用 户对哪一些新的商品感兴趣。 t a s t e 提供了各种各样的功能，可以从庞大的类库中选择多种算法来 为推荐服务。它为j 2 e e 应用程序提供标准