（管理科学与工程专业论文）电子商务智能推荐系统研究.pdf

摘要 随着互联网的普及和电子商务的发展，电子商务系统在为用户提供越来越多选择的 同时，其结构也变得更加复杂，用户经常会迷失在大量的商品信息空间中，无法顺利找 到自己需要的商品。电子商务中的商品推荐系统直接与用户交互，模拟商店销售人员向 用户提供商品推荐，帮助用户找到所需商品，从而顺利完成购买过程。在日趋激烈的竞 争环境下，商品推荐系统能有效留住客户、防止客户流失，提高电子商务企业的销售以 及竞争力。 商品推荐系统在电子商务系统中具有良好的发展和应用前景，逐渐成为电子商务i t 技术的一个重要研究内容，得到越了来越多研究者的关注。 目前，虽然电子商务中的商品推荐系统在理论和实践中都得到了很大发展，但是随 着电子商务系统规模的进一步扩大，商品推荐系统也面i 临一系列挑战。针对商品推荐系 统所面临的主要挑战，本文在以下三个方面对电子商务推荐系统进行了有益的探索和研 究。 第一，提出了基于选举理论的推荐算法。在过往电子商务推荐系统中，普遍使用协 同过滤推荐算法，而在大型电子商务系统中，由于用户的喜好对于供其选择的商品来说 可能是有矛盾的，协同过滤推荐算法并不能很好的解决这个问题，基于选举理论的算法 在这方面却有不错的解决方法。另外，优秀的推荐系统应该能根据用户的喜好程度对某 类商品各种选择进行排序，然后按照这种排序把推荐结果提供给用户，基于选举理论的 算法同样胜任这种要求。 第二，提出了采用基于朴素贝叶斯分类器进行文本分析，这种文本分析一方面能够 跟踪用户的行为，发现用户喜好的变化并记录在数据库中，使用户模型能够动态的改变。 另一方面减少了用户设置喜好信息的工作量，减轻了用户的负担，使推荐系统更具有人 性化。 第三，在应用上，以钟表行业供应链的电子商务为背景，分析了钟表推荐系统结构、 功能，并把基于选举理论的算法和基于朴素贝叶斯分类器的文本分析应用在系统上。 关键词：商品推荐系统，选举理论，朴素贝叶斯分类器，文本学习 三耋三些查兰篁竺兰堡圭篁兰 a b s t r a c t w i t ht h ed e v e l o p m e n to fi n t e r n e ta n de l e c t r o n i cc o m m e r c e ( e c ) ，t h es t r u c t u r eo fe c s y s t e mi sb e c o m i n gm o r ea n dm o r ec o m p l e x a n dt h eu s e r sf e e lc o n f u s e df a c i n gs om a n y i t e m st oc h o i c e ，b e c a u s ei ti sh a r df o rt h e mt of i n do u tw h a t t h e yr e a l l yn e e da n dw h e r ew h a t t h e yn e e d a r e t h ee cr e c o m m e n d a t i o ns y s t e m sc a ni n t e r a c tw i t ht h eu s e r s ，r e c o m m e n di t e m s t ot h eu s e r sa n dh e l pt h eu s e r st of i n do u tw h e r et h ei t e m st h e yr e a l l yw a n t s ou n d e rt h e r e c o m m e n d a t i o ns y s t e m sh e l p ，t h eb u y i n gp r o c e d u r ei s v e r ys m o o t h f a c i n gt h et o u g h c o m p e t i t i o n ，t h ee cr e c o m m e n d a t i o ns y s t e mc a l lh e l pe n t e r p r i s e s t oh o l dt h ec u s t o m e r s e f f i c i e n t l y ，b o o s tt h es a l ev o l u m e a n de n h a n c et h ec o m p e t i t i o n p o w e r t h er e c o m m e n d a t i o ns y s t e mh a saa m a z i n gd e v e l o p m e n tp r o s p e c t i ti sb e c o m i n gah o t i s s u ea m o n gt h ei t t e c h n o l o g y ，a n d i ta t t r a c t sm o r ea n dm o r ea t t e n t i o no fo b s e r v e r s e cr e c o m m e n d a t i o ns y s t e mh a sm a d eag r e a ta d v a n c eb o t hi nt h e o r ya n di np r a c t i c e b u t i ta l s of a c e sas e r i e so f c h a l l e n g e sw h e n i t ss c a l eb e c o m e s b i g g e r a i m a tt h e s ec h a l l e n g e s ，t h e p a p e r s t u d i e se cr e c o m m e n d a t i o ns y s t e mf r o mt h r e ea s p e c t s ： f i r s t l y , t h er e c o m m e n d a t i o ns y s t e m t h ep a p e rs t u d i e sa d a p t st h em e c h a n i s m sf r o m v o t i n g t h e o r y m o s tr e c o m m e n d a t i o ns y s t e ma d a p t ss o c i a lf i l t e r i n ga p p r o a c hm e c h a n i s m s ，b u tt h e s o c i a lf i l t e r i n ga p p r o a c hm e c h a n i s m sc a nn o tr e s o l v et h ep r o b l e mt h a tu s e r sp r e f e r e n c e sa r e o f t e nc o n f l i c t i n gw e l l i nt h eo t h e rh a n d t h em e c h a n i s m sf r o mv o t i n gt h e o r yc a n f u r t h e r m o r e ， t h ee x c e l l e n tr e c o m m e n d a t i o ns y s t e ms h o u l dr a n kt h ei t e m sa c c o r d i n gt ou s e r sp r e f e r e n c e s a n d p r o v i d et h er e s u l tt ou s e r t h em e c h a n i s m s f r o m v o t i n gt h e o r ya l s od o i tw e l l s e c o n d l yt h ep a p e ra d a p t sn a i v eb a y e sc l a s s i f i e rt oa n a l y z et h ec o n t e n t so f t h ec o n t e n t s o fi t e m s s u m m a r i e s b a s eo nt h en a i v eb a y e sc l a s s i f i e r , t h er e c o m m e n d a t i o ns y s t e mc a n t r a c kt h eu s e r sp r e f e r e n c e sc h a n g e ，t h e ni tc a nc h a n g et h eu s e rm o d e l i n ga c c o r d i n g l y t h i s c a nr e d u c et h eu s e sw o r k l o a do fs e t t i n gp r e f e r e n c e si n f o r m a t i o na n dl i g h t e nt h eb u r d e no f u s e r f i n a l l y , t h ep a p e ra n a l 3 z e s t h es t r u c t u r e ，t h ef u n c t i o na n dt h e a l g o r i t h m s o fw a t c h r e c o m m e n d a t i o n s y s t e m k e y w o r d ：r e c o m m e n d a t i o ns y s t e m ，v o t i n gt h e o r y ，n a i v eb a y e s c l a s s i f i e r l i 第一章绪论 1 1 研究背景和意义 第一章绪论帚一早三百t 匕 目前，在因特网上的信息以惊人的速度增长，在因特网上寻找信息的用户不是觉得 信息不够，而是普遍感到像被淹没在茫茫的信息大海里。虽然用户可以通过搜索引擎、 目录、人工编辑等工具，来获得一定的帮助，但是专门服务于单个企业或个人的信息搜 集、整理、对比和提醒的服务，却仍然主要依赖大量的人力工作来完成。例如，通过搜 索引擎，人们需要不停地一次一次重复查找自己所需要的信息，而且，这些信息往往很 不及时，难以满足用户的需要。 特别是，以因特网为支撑的电子商务同样面临这种困扰。从事电子商务的企业通过 因特网与用户正处在空前的密切接触之中，所有的营销策略都紧紧围绕用户的需求而展 开。第一时间掌握了丰富的用户信息，了解用户的需求，便能准确的把握市场变化的脉 动，控制竞争的最高点。因此，电子商务的个性化服务愈来愈得到重视。个性化服务需 要跟客户全方位的接触，获得完整的、连续的客户信息，对其进行全方位的连接，以实 行交叉营销、一对一营销、定制化客户服务、以及提供适时的客户关怀等，从而使客户 产生备受重视的感觉，提高客户的满意度和支持度；同时企业可以最大化客户生命周期 价值，实现企业和客户双赢的局面。 近几年，针对这个问题，关于智能化信息代理的研究得到了广泛的重视。智能化信 息代理其中一个主要目标是找出每一个用户的需求，并自动地为了适应和满足用户这种 具体的要求而寻找合适的信息。为了这个目标，就必须应用正确适合的用户建模技术。 在用户建模这个研究领域里，很多研究工作主要集中在信息检索算法的使用以及机器学 习这两方面上 ”。在过去的几年中，如何得到用户的喜好信息已经成为了研究的热门课 题。近来，运用智能代理来获取并建立用户喜好的模型也吸引了人工智能研究人员的注 意刚。 研究人员在研究智能信息代理系统的早期也开始了商品推荐系统的研究，商品推荐 系统属于智能信息代理一个特殊类别。商品推荐系统可以向特定用户推荐其可能喜欢的 厂东工业大学管理学硕上论文 物品，典型物品包括电影、书籍、c d 、网站等等。现在从事与电子商务的企业都对商 品推荐系统特别关注，因为通过商品推荐系统可以解决上面所阐述的问题，主动地向用 户推荐其喜欢的商品，不仅可以促进交易的进行，还可以提高服务的质量，提升企业的 竞争力。 1 2 研究现状和发展 1 2 1 商品推荐系统的研究现状 正是因特网的普及和电子商务的发展，商品推荐系统逐渐成为电子商务i t 技术的一 个重要研究内容，越来越多地得到研究者的关注。目前，几乎所有大型的电子商务系统， 如a m a z o n ，c d n o w ，e b a y ，当当网上书店等，都不同程度地使用了各种形式的商品推 荐系统。 构建商品推荐系统的关键是建立用户模型，建立用户模型就需要为推荐确定算法【2 。 为了产生合理的推荐，保证推荐系统的实时性和在不同领域中的应用要求，现在的研究 人员提出了各种不同的推荐算法，如协同过滤算法、b a y e s i a n 网络技术、聚类技术、关 联规则技术以及基于图的h o r t i n g 图技术等， t y p e s t r y 是最早提出来的基于协同过滤的推荐系统，目标用户需要明确指出与自己 行为比较类似的其他用户。g r o u p l e n s 是基于用户评分的自动化协同过滤推荐系统，用 于推荐电影和新闻。r i n g o 推荐系统和v i d e o 推荐系统通过电子邮件的方式分别推荐音 乐和电影。b r e e s e 等人对各种协同过滤推荐算法及其改进进行了深入分析。 协同过滤推荐通过用户的最近邻居产生最终的推荐，基于项目的协同过滤推荐首先 计算项目之间的相关性，然后通过用户对相关项目的评分预测用户对未评分项目的评 分。 b a y e s i a n 网络技术利用训练集创建相应的模型，模型用决策树表示，节点和边表示 用户信息。训练得到的模型非常小，所以对模型的应用非常快。这种方法适合于用户的 兴趣爱好变化比较慢的场合。 聚类技术将具有相似兴趣爱好的用户分配到相同的簇中，聚类产生之后，根据簇中 其他用户对商品的评价预测目标用户对该商品的评价。由于聚类过程离线进行，所以在 第一章绪论 线的推荐算法产生推荐的速度比较快。 关联规则技术在零售业得到了广泛的应用，关联规则挖掘可以发现不同商品在销售 过程中的相关性。基于关联规则的推荐算法根据生成的关联规则模型和用户当前的购买 行为向用户产生推荐。关联规则模型的生成可以离线进行，因此可以保证有效地推荐系 统的实时性要求。 而在实际中应用中，协同过滤算法应用的最多【3 】。 1 2 2 商品推荐系统的发展趋势 1 趋向c s 结构的推荐架构 目前大部分的电子商务推荐系统采用的是嵌入式构架，如a m a z o n 、c d n o w 、e b a y 、 当当等。推荐引擎作为商务系统的一部分，特点是实施简单，一般通过函数库、类库或 软件组件等形式实现。在嵌入式推荐构架中，推荐系统强烈依赖于应用系统，要求采用 和应用系统相同的运行环境，如相同的应用服务器软件平台 4 】。 而c s 结构的推荐构架有这自身的优势。推荐引擎作为提供推荐服务的服务器端， 独立于商务系统；商务系统则作为请求推荐的客户端。它们之间用某种应用接口( 例如 t c p i p ，h t r p 或者r c p 等) 交互。此构架的特点是推荐系统的运行环境不需要和应用 系统相同，对应用环境的适应性好。一个的例子是文提出的基于w e b 使用挖掘和内容 挖掘的个性化推荐服务体系结构。 2 向多算法发展 现有的推荐系统多以某个或某种推荐算法为核心，推荐功能单一，不能灵活提供多 种推荐。而未来的推荐系统会采用多种算法，算法之间进行互相协调，从而使推荐结果 更准确。 3 注重文本分析 对于推荐的产生，现阶段较少用到文本的分析。而对文本的分析却对推荐的产生起 着重大的作用。举个例子，在客户服务中一t l , ，把同客户的谈话转化为文本数据，再对这 些数据进行挖掘，进而了解客户对服务的满意程度和客户的需求以及客户之间的相互关 系等信息，从而作出准确的推荐。但是文本的分析并不是一件容易的事情，尤其是在分 析方法方面，还有很多需要研究的专题。目前市场上有一些类似的软件，但大部分方法 只是把文本移来移去，或简单地计算一下某些词汇的出现频率，并没有真正的分析功能。 三变三些盔耋重型兰堡圭篓塞 1 3 本文的主要研究内容与创新点 1 3 1 理论上的创新 电予商务在近几年蓬勃发展，为人类提供了新的购物方式和更多的选择，但是在提 供这种多选择的同时，电子商务系统结构也变得更加复杂，用户在网络上经常要面对一 大堆商品，却无法顺利找到自己的所需。电子商务中的商品推荐系统直接与用户交互， 模拟商店销售人员向用户提供商品推荐，帮助用户找到所需商品，从而顺利完成购买过 程。在日趋激烈的竞争环境下，商品推荐系统能有效留住客户、防止客户流失，提高电 子商务企业的销售以及竞争力。 目前的电子商务中的商品推荐系统在理论和实践中都得到了很大发展，但是随着电 子商务系统规模的进一步扩大，商品推荐系统也面临系列挑战。针对商品推荐系统所 面临的主要挑战，本文在理论上对两个方面对电子商务推荐系统进行了有益的探索和研 究。 第一一，提出了基于选举理论的推荐算法。在过往电子商务推荐系统中，普遍使用协 同过滤推荐算法，而在大型电子商务系统中，由于用户的喜好对于供其选择的商品来说 可能是有矛盾的，协同过滤推荐算法并不能很好的解决这个问题，基于选举理论的算法 在这方面却有不错的解决方法。另外，优秀的推荐系统应该能根据用户的喜好程度对某 类商品各种选择进行排序，然后按照这种排序把推荐结果提供给用户，基于选举理论的 算法同样胜任这种要求。 第二，提出了采用基于朴素贝叶斯分类器进行文本分析，这种文本分析一方面能够 跟踪用户的行为，发现用户喜好的变化并记录在数据库中，使用户模型能够动态的改变。 另一方面减少了用户设置喜好信息的工作量，减轻了用户的负担，使推荐系统更具有人 性化。 这两方面的研究有以下优点： 选举理论机制运用用户的对钟表各方面的喜好，产生了基于语法的评估方法， 而基于朴素贝叶斯分类其的文本分析机制则提供了基于语义的评估方法。 基于朴素贝叶斯分类器的文本分析机制可以跟踪用户喜好的变化。 本论文的目的是建立以选举理论为基础的推荐系统的可行性。虽然，把基于用户喜 4 第一章绪论 好信息的选举理论和协同过滤机制结合来开发推荐系统效果会更好，但是因为本文的目 的是根据用户的喜好信息来建立有效的推荐系统，所以本文还是着重于只用用户喜好的 选举理论来进行开发。而且这样的系统在需要的时候可以把社会过滤机制结合起来。 和其他基于协同过滤机制的推荐系统不同，本文论述的推荐系统着重于基于用户的 喜好进行推荐，这种喜好可以是用户设置的也可以是系统根据交互的过程中推断出来 了。根据了解，目前并没有把选举理论机制和基于文本的学习机制结合起来应用的个性 化推荐系统。 1 3 2 应用上的创新 本文以钟表行业供应链的电子商务为背景，把研讨的基于选举理论的算法和基于朴 素贝叶斯分类器的文本分析应用到钟表行业基于w e b 供应链信息管理系统，从而成为 了钟表推荐系统，并分析了该钟表推荐系统结构、功能。据了解在目前还没有专门针对 钟表的推荐系统的文献。本文在此基础上进行了测试。 ：至三、业銮：重墨主要士鲨兰 2 1引言 第二章商品推荐系统 最近几年，推荐系统这个课题得到了广泛的关注和兴趣，推荐系统的作用在于其能 在一个很大的选择集合中作出选择。推荐系统是以代理为基础的系统，系统利用所存储 用户的喜好来向用户推荐用户感兴趣的选项【3 ”。如果当某些选项既在某方面符合用户的 喜好，而在另一些方面又不符合( 例如，有选项a 和选项b ，选项a 的颜色符合用户 的喜好，但是其形状并不是用户最喜欢的；而选项b 的形状是用户最喜欢的，颜色却恰 恰不是) ，这种系统能够在这种矛盾的情况下作出一致的、有意义的折中的选择，那么 这个系统就是成功而有效的 3 6 1 。人工智能、代理以及数据库领域的学者对这个领域都产 生了浓厚的兴趣。 2 _ 2 商品推荐系统应用 推荐系统汇聚了信息检索和智能系统的技术【4 】。典型的推荐系统有c d 和音带推荐 系统( 例如：c d n o w c o m ) ，电影推荐系统( 例如：m o v i e c r i t i c c o r n ) ，书籍推荐系统等 等。另外还有先进的网页搜索引擎，社会网络过滤器( s h a r d a n a n da n dm a e s ，1 9 9 5 ) ，采 用了h a r n e s s 信息检索技术的半结构数据推荐系统( r e s n i c k ，i a c o v o u ，s u c h a k ，b e r g s t r o m a n d r i e d l ，1 9 9 4 ) ，还有科学软件选择器。现在，推荐系统在电子商务领域中得到了应用， 通过推荐系统，电子商务网站向拥护推荐他们感兴趣的商品( s c h a f e r , k o n s t a na n d r i e d l ，1 9 9 9 ) 。相信未来，运用商品推荐系统的应用会更加的广泛。 6 ：。，。：，：。：，。三：三直皇堂丝 2 3 目前商品推荐系统主要采用的算法 2 3 1 各类型的算法 目前有很多系统尝试对用户的喜好进行建模。例如电影推荐系统m o r s e ( f i s k ，1 9 9 5 ) ，此系统基于社会过滤机制进行个性化电影推荐。其他采用相同机制的在 线系统有f i r e f l y 电影推荐系统( f i r e f l y c o m ) ，m o v i ec r i t i c ( m o v i e c r i t i c c o r n ) 等等。其他解 决个性化推荐系统问题还有以下几个系统： 口m o v i es e l e c t ，运用了人工智能和模糊逻辑。 口w a w a 系统( e l i s a s s i r a da n ds h a v l i k ，2 0 0 2 ) 运用了神经网络技术。 口 在m 玎开发n e w t ( m a e s ，1 9 9 3 ) ，n e w t 运用了遗传算法，深化了每代之间 所发生的非遗传学习。 口a g e n t m c ，运用了多信息源和贝叶斯算法。 2 3 2 协同过滤算法 协同过滤推荐根据其他用户的观点产生对目标用户的推荐列表，它基于这样一个假 设：如果用户对一些项目的评分比较相似，则他们对其他项目的评分也比较相似 3 8 。协 同过滤推荐系统使用统计技术搜索目标用户的若干最近邻居，然后根据最近邻居对项目 的评分预测目标用户对项目的评分，产生对应的推荐列表。 为了找到目标用户的最近邻居，必须度量用户之间的相似性，然后选择相似性最高 的若干用户作为目标用户的最近邻居。目标用户的最近邻居查询是否准确，直接关系到 整个推荐系统的推荐质量。准确查询目标用户的最近邻居是整个协同过滤推荐成功的关 键m 1 。 用户评分数据可以用一个m x n 阶矩阵a ( m ，n ) 表示，m 行代表m 个用户，n 列代表n 个项目，第f 行第歹0 的元素r 代表用户i 对项目j 的评分。用户评分数据矩阵如表2 - 1 所示。 度量用户i 和用户，之间相似性的方法是，首先得到经用户i 和用户j 评分的所有项 目，然后通过不同的相似性度量方法计算用户f 和用户，之间的相似性，记为s i m ( i ，) 。 7 广东工业大学管理学碗士论文 表2 - 1 用户评分数据矩阵 t a b e 2 1t h ee v a l u a t i o nd a t am a t r i xo fh s e r i t e m li t e m ki t e m u s e r lr 1 ，1r 1 u s e r fr i 1r i 月 u s e r mr 坍tr m 传统的相似性度量方法 度量用户间相似性的方法有多种，主要包括如下3 种方法余弦相似性、相关相似性 以及修f 的余弦相似性【4 】。 余弦相似性( c o s i n e ) ；用户评分被看做是n 维项目空闻上的向量，如果用户对项目 没有进行评分，则将用户对该项目的评分设为0 ，用户问的相似性通过向量间的余弦夹 角度量。设用户f 和用户j 在n 维项目空间上的评分分别表示为向量f ，则用户f 和用户j 之间的相似性s i m ( i ，j ) 为 s i m ( i ，j ) = c o s 6 ，j ) ： ：t z ， 分子为两个用户评分向量的内积，分母为两个用户向量模的乘积。 相关相似性( c o r r e l a t i o n ) ：设经用户f 和用户j 共同评分的项目集合用i u 表示，则用 户i 和用户f 之间的相似性s i m ( i ，j ) 通过p e a r s o n 相关系数度量： _ 、咄k 厂曩k 扯一r ) 鄹州l 川2 西菰i 丽i 露丽。一r 厂咄一q 厂 r 一表示用户i 对项目c 的评分，一r i 和一r j 分别表示用户f 和用户j 对项目的平均评分 修正的余弦相似性( a d j u s t e dc o s i n e ) ：在余弦相似性度量方法中没有考虑不同用 户的评分尺度问题，修正的余弦相似性度量方法通过减去用户对项目的平均评分来改善 上述缺陷，设经用户f 和用户j 共同评分的项目集合用1 0 表示，。和，f 分别表示经用户i 和用户f 评分的项目集合，则用户f 和用户j 之间的相似性j l m ( f ，j ) 为 _ 、咄一r 胎扯一r ，j 肌圳户霭熏i 丽嘉霞丽叫一r r r 哪瑚，r 第二章商品推荐系统 尺。表示用户i 对项目c 的评分，和分别表示用户f 和用户j 对项目的平均评分。 随着电子商务系统规模的扩大，用户数目和项目数目呈指数级增长，用户评分数据 极端稀疏 4 1 。在大型电子商务系统中，用户评分的项目一般不会超过项目总数的1 ，经 两个用户共同评分的项目则更少。在用户评分数据极端稀疏的情况下，传统的相似性度 量方法存在相应的弊端【3 8 。下面我们详细分析传统的相似性度量法在用户评分数据极 端稀疏情况下存在的问题。 在余弦相似性度量方法中，用户没有评分的项目均将评分假设为0 ，设用户i 对项 目j 的评分为l ，则在构造用户评分数据矩阵a ( m ，n ) 时，对任意的项目j ，用户i 对项目 的评分尺。为 这样做的好处是可以有效地提高计算性能，但在项目数量及其巨大、用户评分数目 极端稀疏的情况下，上述假设的可信度并不高，因为用户对所有未评分项目的评分均假 设为0 。事实上，用户对未评分商品的喜好程度不可能完全相同，对这些项目的评分也 不可能完全相同( 全部为o ) ，由此可见，在用户评分数据极端稀疏的情况下，余弦相似 性并不能有效地度量用户之间的相似性，修正的余弦相似性存在同样的问题。 在相关相似性度量方法中，设经用户a 评分的项目集合用，。表示，则在计算用户f 和 用户f 之间的相似性时，首先需要计算经用户f 和用户j 评分的项目集合的交集，。： lq 2 l 。n i i 然后在项目集合，i 上通过相关相似性度量方法计算用户f 和用户j 之间的相似性。 常识告诉我们，用户只有在比较多的项目上评分比较相似，我们对用户之间的相似性的 确定才比较高。在用户评分数据极端稀疏的情况下，经两个用户共同评分的项目集合，。 更小，经常只有一两个项目，即使用户在这样小的项目集合上评分非常相似，根据常识 我们也不能肯定它们之间的相似性很高，因此在用户评分数据极端稀疏的情况下，相关 相似性度量方法也存在一定的弊端。 综上所述，传统的3 种相似性度量方法在用户评分数据极端稀疏的情况下并不能有 效地度量用户之间的相似性，从而使得计算出来的目标用户的最近邻居不准确，导致整 个推荐算法的推荐质量急剧下降。 9 广东工业大学管理学硕十论文 2 3 3 本文所研究的推荐系统的运用的算法 本文研究的购买钟表推荐系统采用了两个算法。第一种理论是选举理论算法，第二 种是基于朴素贝叶斯分类其的文本分析算法。目前并没有某个个性化商品推荐系统在运 用选举理论的同时又运用文本分析理论。 1 0 t t 。a ，：。，。，。；。；。二至三耋耋璧塑坠 3 1 选举理论概述 第三章选举理论弟二早迈罕埋化 在我们社会生活中，常常面临着各种各样的选择，最后要求我们在其中选出一个或 者若干个结果，以反映全体人员的意愿。 但是现在问题是如何通过选举去衡量人们的意愿。在实际当中，通常通过投票选举 的办法来确定选择。投票选举的方法有很多。最典型的是全体人员对自己选项投一票， 然后简单地以多数为准则，把每个选项得到的票数累积起来，票数最多就是最后选择。 事实上，这是投票一种方法，但是在很多情况下这种处理方法并不合适。 例如，在某个地区进行钟表的调查，调查该地区人们喜好钟表的情况，以引进一种 品牌表进行本地生产，调查结果如下表3 - 1 ： 表3 一l 手表品牌偏好 t a b l e 3 一ln l ew a t c h ，l i k et r e n do fc i t i z e n s 1 日本表 1 5 i 美国表 3 4 瑞士表 5 l 也就是说该地区有1 5 的人喜欢日本表，3 4 的人喜欢美国表，而5 1 喜欢瑞士表。 从表3 - 1 反映的信息可能认为瑞士表最终赢得调查，应该引进瑞士表进行生产，但 是如果调查是在几个具体的手表品牌之中进行，这就使结果变得复杂了。现在假设有五 个品牌手表参加了这次调查，这五个品牌要么属于日本，要么属于美国的，要么属于瑞 士的。情况如下表3 2 ： 表3 - 2 手表品牌偏好 r i b l e 3 2t h ew a t c h l i k et r e n do fc i t i z e n s 日本表精工 l 西铁城 1 4 总共 1 5 美国表斯伯丁 3 4 瑞士表梅花 2 6 劳力士 2 5 总共 5 1 表3 2 中最后一列是该地区人们对品牌的支持度。可以清晰的看出，虽然该地区有 5 1 的人喜爱瑞士表，但是美国表斯伯丁会赢得最后的调查，这和该地区的人的意愿有 违背的地方。我们把这种处理方案叫做多数原则( p l u r a l i t y ) 方案。 多年来，数学家和其他对选举理论感兴趣的学者都在寻求一个选举方法，以满足各 种情况的需求，所以对各种方法提出了多项的准则，希望通过这些准则使到选举方法更 公平，使更多人满意“】。以下，我们对其中几个准则以及典型的选举方法进行比较详细 的阐述。 3 2 选举理论准则 3 2 1 大多数准则( t h em a j o r i t yc r i t e r i o n ) 这个原则的意思是哪个候选选项在选举投票中获得过半数票，那么这个选项就是获 胜者。 例如，假设一共有1 0 0 个人对选项a 、b 和c 投票，选项a 在投票中得到第一的票 数是5 l ，选项曰获得第一票数是4 0 ，而选项c 获得票数是9 ， 如果最后是宣布选项b 或胜，那么这种投票就是违反了大多数原则。 3 2 2 孔多塞准则( t h ec o n d o r c e tc r i t e r i o n ) 孔多塞原则的意思是如果有一个选项在和其他选项的两两配对的选举投票选择中， 都获得了胜利，那么这个选项就是最后的胜利者【l “。 假设有4 个候选人a 、曰、c 和d 竞选某个小镇的镇长。有2 0 个投票选举人。有一 家当地的报纸对这2 0 个投票人作了一个选前的调查，调查的是后选人c 和其他的候选 人两两比较中，会选择谁。结果如下：1 1 个投票人选择c 不选择a ，1 1 个投票人选择 c 不选择b ，1 7 个投票人选择c 不选择d 。 所以，在两两的配对较量中，候选人c 都获得了胜利。如果最后投票结果公布的时 候，候选人没有获胜，那么就是投票不公平。例如当实际点票时，候选人a 得到了9 票 第一，口没有得到第一的选票，c 获得了8 票第一，而d 获得了3 票第一。如果c 没有 宣布为最后的胜利者，那么这种投票方法就是为违反了孔多塞原则。 3 2 3 单一性准则( t h em o n o t o n i c i t yc r i t e r i o n ) 这个原则的意思是，如果某个候选选项被确定为胜利者后，重新投票选择，而投票 人的选择发生了有利于这个胜利者的改变，那么重选的胜利者应该还是原来的胜利者 b 7 。 例如有三个学生：a l ，b o b 和c a r r i e 竞选班长。投票分为两轮进行。投票的方法是 这样的：第一轮投票中，获得票数最少的学生退出第二轮的投票，而在第二轮的投票中， 获得票数最多的学生就当选为班长。在第一轮的投票中，a z 获得了1 1 张投票，b o b 获 得了8 票，而c a r r i e 获得了1 0 票。那么b o b 就因为得到最少的票数而退出了第二轮的 角逐。在第二轮的投票中a f 获得了1 1 票，而c a r r e 获得了1 8 票，那么c a r r i e 就当选 为班长。 但是选举委员会的主席在结果正式公布前认为投票程序有误，需要重选。在重选的 第一轮中，有4 个投票人改变了第一次的选择，从选a f 改为了选c a r r i e ，而其余的投 票者的选择没有发生改变。结果在第一轮投票中，a l 得到了7 票，b o b 得到了8 票，c a r r i e 得到了1 4 票。这促使了a l 退出了第二轮的角逐，第二轮角逐就在b o b 和c a r r i e 中进行。 在第一轮选择a l 的投票人因为a l 的退出就在第二轮的投票中选择了b o b ，从而投票的 最终结果是，b d b 获得了1 5 票，c a r r i e 获得了1 4 票，b o b 当选为班长。我们可以看出， 广东t 业大学管理学硕士论文 虽然4 名投票人虽然发生了有利于c a r r i e 的改变( 从投票给a 1 改为投票给o ，r p ) ，但 是结果并没有使c a r r e 当选，所有这个选举投票的方法就违背了单一性原则。 3 2 4 非相关选择独立睦准d i j ( t h ei n d e p e n d e n c eo fi r r e l e v a n ta l t e r n a t i v e s c r i t e r i o n ) 这个原则的含义就是一个候选选项被确定为胜利者后，如果重选，而且有一个或多 个原来的失败选项退出了角逐，那么重选的胜利者应该还是原来的胜利者”7 1 。 例如，一间公司2 0 周年庆典，需要定做一个蛋糕，公司的成员有三种不同的意见： 定做苹果蛋糕、桃子蛋糕或者是奶油蛋糕。选举投票的方法如下：公司成员需要对三种 选择进行排序，排第一位的得3 分，第二位得2 分，第三位得1 分，最后把选项的得分 累计，以确定最后的选择。排序的情况如下( 按喜好的先后排) ： 2 7 人排序是：苹果蛋糕、奶油蛋糕、桃子蛋糕。 2 4 人排序是：桃子蛋糕、奶油蛋糕、苹果蛋糕。 2 人排序是：奶油蛋糕、桃子蛋糕、苹果蛋糕。 根据排序，算出三个选项的各自得分： 苹果蛋糕的分数是：得到2 7 个第一，每个第一得3 分，共8 1 分；得到2 6 个第三， 每个第三得1 分，共2 6 分。总共得分是1 0 7 分。 奶油蛋糕的得分是：得到2 个第一，每个第一得3 分，共6 分；得到5 1 个第二，每 个第二得2 分，共1 0 2 分。总共得分是1 0 8 分。 桃子蛋糕的得分是：得到2 4 个第一，每个第一得3 分，共7 2 分；得到2 个第二， 每个第二得2 分，共4 分；得到2 7 个第三，每个第三得1 分，共2 7 分。总共得分是1 0 3 分。 因而，奶油蛋糕得分最高，得1 0 8 分，苹果蛋糕得分次之，得1 0 7 分，桃子蛋糕最 后，得1 0 3 分。所以周年庆典应该选奶油蛋糕。 正在此时，因为没有桃子蛋糕供应，所以重新计分。又因为只有两个候选选项 苹果蛋糕和奶油蛋糕，所以排第一的得2 分，排第二的得1 分。重新计分结果如下： 苹果蛋糕的分数是：得到2 7 个第一，每个第一得2 分，共5 4 分；得到2 6 个第二， 每个第二得1 分，共2 6 分。总共得分是8 0 分。 1 4 。：。，。璧三量，塑些垒 奶油蛋糕的得分是：得到2 6 个第一，每个第一得2 分，共5 2 分；得到2 7 个第二， 每个第二得1 分，共2 7 分。总共得分是7 9 分。 因而，苹果蛋糕得分最高，得8 0 分，奶油蛋糕得分次之，得7 9 分。所以周年庆典 应该选苹果蛋糕。 注意到，第一次选择的胜利者是奶油蛋糕。而失败者桃子蛋糕退出后重选胜利者就 变成了苹果蛋糕。说明了这个选举投票方法违背了非相关选择独立性原则。 3 3 选举方案 3 3 1 配对方案 配对方案把候选项进行两两的配对进行计票比较，直到找出最后的胜利者3 8 】。 假设有a 、b 、c 、d 四个选项供投票人选择，投票的结果如下表3 - 3 ： 表3 3 配对投票 t a b l e 3 3t h e p a i r w i s ee l e c t i o n 投票顺序av bbvcbv ddvcc v a 1 5 adbc a曰d da 1 5 acdbacdca 1 5 b ) c d a 口bbcc 1 0 bdcab口口dc 2 5 c ) d b a四cdc c 2 0 d b ) c ab曰d dc 3 0 ，7 06 0 ，4 02 5 7 54 5 5 57 0 3 0 分析选举结果的程序如下： 首先，a 和b 比较。 然后，第一步胜者和c 比较。 最后，第二步的胜者和d 比较。 详细的比较如下： 广东t 业大学管理学硕士论文 _ i i i i i 电詈詈皇! 詈暑詈鼍皇曼暑昌詈詈量_ _ - _ 皇! 皇毫罩鼍= 暑詈鼍田- - - _ e 詈詈= l 墨霉景詈置墨_ - _ 皇皇皇墨鼍鼍= 量- l 詈昔= 所以，候选项d 是最后胜利者。 配对方案的最明显缺点是当配对比较的顺序不同时，最后结果也可能不同3 8 】。 3 3 2 孑l 多塞方案( t h ec o n d o r c e ts c h e m e ) 孔多塞选举方案就是完全遵循孔多塞准则的选举方案，孔多塞选举方案一般的流程 如下； 对每个选项进行两两配对，并确定每一对那个选项胜出 从这些胜出的选项中找出一个选项，此选项在所有的配对中都胜出，作为孔多 塞胜者，也就是最后的选择。 假设有a ，b 、c 、d 四个选项供投票人选择，投票的结果如下表3 - 4 ： 表3 - 4 孔多塞投票a 1 1 a b l e 3 4t h ec o n d o r c e te l e c t i o na 投票顺序 av bavcav dbvcbv dcv d 3 0 abc)daaa曰矗c 1 5 b c d a曰cd日bc 1 0 b d c abcd曰曰d 2 5 c b d a曰cdc曰c 2 0 d b c a口cd艿dd 3 0 7 03 0 ，7 03 0 7 07 5 2 58 0 2 07 0 3 0 根据配对选择，找出孔多塞胜者，如表3 5 1 6 表3 - 5 孔多塞选举投票结果a t a b l e 3 5t h ec o n d o r c e te l e c t i o nr e s u l ta v s av s bv s cv j d a3 0 、7 0曰3 0 t7 0c3 0 7 0d 曰7 0 3 0曰7 5 2 5曰8 0 2 0曰 c7 0 | 3 0c 2 5 7 5丑7 0 7 0c d7 0 3 0d2 0 8 0b3 0 7 0c 从上面两个表可以看出，选项曰在两两的配对中都胜出，所以选项b 就是孔多塞胜 者，也就是最后的选择。 但是现在的问题是，是否在任何的情况下，都可以得出孔多塞胜者呢? 下面再举一 个例子，例子跟上面一个一样，只是选项从四个变成三个，投票结果如下表3 6 ： 表3 - 6 孔多塞投票b t a b l e 3 6t h ec o n d o r c e te l e c t i o nb 投票顺序 av bavcb vc 3 3 abcaa 曰 3 3 b ) c a 曰c b 3 4 c a bac c 6 7 ，3 33 3 6 76 6 3 4 根据配对选择，找出孔多塞胜者 表3 7 孔多塞投票机结果b t 曲l e 3 7t h ec o n d o r c e te l e c t i o nr e s u l tb 【 v s a v 量bw c l a 6 7 3 3a3 3 、6 7c i 曰3 3 6 7a 6 6 | 3 4曰 l c 6 7 3 3c3 4 6 6 口 从上面两个表可以看出，在两两的配对中选项a 胜选项b ，但是有输给了选项c ；b * i tc ，但是输给了a ；c 赢了a ，但是输给了b 。这正像游戏“石头、剪子、布”，没 有一个绝对的胜利者。 所以，我们可以得出结论：并不是在任何情况下，都有孔多塞胜者m 1 。 銮三、业查耋箜塞兰竺圭篁兰 3 3 3 博尔达计分方案( b o r d ac o u n t ) 一些比较简单的选举方案，例如两两配对方案、孔多塞选举方案等都力求简单，它 们都设法把投票人对全部选项喜好排序的信息精简为选项之间的两两比较的信息( 如： a v s b ) 3 9 o 而一些比较复杂的选举方案就刚好相反，它们力求找出投票人对全部选项 的喜好排序，其中个方案就是博尔达计分方案( b o r d ac o u n t ) 方案。 假设有个候选项，博尔达计分方案的步骤如下： 投票人对他的第一选择的候选项赋值( 一j ) ，对第二选择赋值( 2 ) ，如此 类推，对第k 选择赋值( n