（计算机科学与技术专业论文）基于熵和市场值函数的推荐系统算法研究与评价.pdf

一 _ l 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 摘要 摘要 随着信息技术的不断发展，电子商务带来的经济效益和社会效益越来越大。 不少传统行业都采用了这种新的商业模式。推荐技术伴随着这种趋势应运而生， 并且以其在搜索以及电子商务等领域所带来的良好效果越来越为人们所熟知。 目前，推荐技术作为w e b 智能等研究领域的重要研究内容，已经成为科学研 究人员的研究热点。本文针对其中的协同过滤推荐技术和目标营销统一框架模型 进行了研究。主要工作为： 1 协同过滤以其所带来的良好效果使其成为目前应用最为广泛的推荐技 术。但是由于其本身的算法特点和现有的相似度计算方法使其面对现实世界中广 泛的稀疏数据时有一定的缺点。针对这一问题，本文借鉴条件熵、互信息等与熵 相关的多种重要度量方法来描述产品间的相关关系。基于此，构建了基于熵的协 同过滤推荐模型。实验表明本文提出的方法在稀疏数据中是有效的。 2 从目标营销统一框架模型中，可以看出面向顾客的目标营销系统、面向 产品的目标营销系统以及四个子模型为目标营销提供了多数据源中多侧面的分 析。模型的构建以及其基本算法的设计都以市场值函数为基础。面对当今电子商 务领域越来越多的多级评分形式的数据，该统一框架模型下还缺乏好的市场值函 数模型。针对这一问题，本文对目标营销统一框架模型下的市场值函数进行了改 进，将评分数据充分利用了起来，使得高评分项中的属性值对于市场值贡献更大。 总之，本文从熵和市场值函数两个角度出发研究了推荐系统算法。采用了多 种评价方法来从不同的侧面反映了基于熵的统一框架模型的推荐效果；同时为目 标营销统一框架模型提供了多种合适的评价方法，进一步完善了该模型。 关键词推荐系统；目标营销统一框架模型；熵；协同过滤 北京t 业大学t 学硕十学位论文 i i i a b s t r a c t 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 f o r m a t i o nt e c h n o l o g y , e - c o m m e r c eb r i n g sm o r ea n d m o r ee c o n o m i cb e n e f i t sa n ds o c i a lb e n e f i t s m a n yt r a d i t i o n a li n d u s t r i e sh a v ea d o p t e d t h i sn e wb u s i n e s sm o d e l r e c o m m e n d a t i o nt e c h n o l o g ye m e r g e d ，a n db e c o m ew e l l k n o w n a tp r e s e n t ， b e i n ga ni m p o r t a n tp a r to fw e bi n t e l l i g e n c e ，t h er e s e a r c h o n r e c o m m e n d e rs y s t e m sh a sb e c o m ea na c t i v et h e o r e t i c a lr e s e a r c h i n ga r e a t h i sp a p e r f o c u s e s0 1 1t h er e s e a r c ho fc o l l a b o r a t i v ef i l t e r i n ga n dt h eu n i f i e df r a m e w o r ko f t a r g e t e dm a r k e t i n g t h em a i nw o r ki n c l u d e s ： 1 c o l l a b o r a t i v ef i l t e r i n gi saw i l d l yu s e dm e t h o di nr e c o m m e n d a t i o ns y s t e m h o w e v e r , i th a sal o to fd r a w b a c k sb e c a u s e o ft h ea l g o r i t h mi t s e l fa n dt h em e t h o d sf o r s i m i l a r i t yc o m p u t e t os o l v et h i sp r o b l e m ，w ep r e s e n tp r o d u c te n t r o p ya n dm e a s u r e t h ec o r r e l a t i o nb e t w e e np r o d u c t sw i t hc o n d i t i o n a le n t r o p y 、m u t u a li n f o r m a t i o na n d s o m eo t h e rm e t h o d s a ne n t r o p yb a s e dr e c o m m e n d e rs y s t e mf r a m e w o r ko f c o l l a b o r a t i v ef i l t e r i n gi sp r o p o s e d e x p e r i m e n t so nr e a l w o d dd a t as e ta r ep e r f o r m e d t od e m o n s t r a t et h ee f f e c t i v e n e s so ft h ep r o p o s e df r a m e w o r k 2 i nt h eu n i f i e df r a m e w o r ko ft a r g e tm a r k e t i n g ，w ec a i l s e gt h e c u s t o m e r - o r i e n t e d t a r g e tm a r k e t i n gs y s t e m s ，p r o d u c t - o r i e n t e dt a r g e tm a r k e t i n g s y s t e m sa n df o u rs u br e c o m m e n d a t i o nm o d e l t h i sf r a m e w o r ka n dt h ea l g o r i t h m sa r e d e s i g n e db a s e do nt h em a r k e tv a l u ef u n c t i o n f a c i n gt o d a y sm u l t i - c l a s sr a t i n g so f e - c o m m e r c e ，i tl a c k so fag o o dm a r k e tv a l u ef u n c t i o nm o d e l w ei m p r o v e dt h em a r k e t v a l u ef u n c t i o n ，m a k ef u l lu s eo ft h ed a t a i ns h o r t ，t h i sp a p e rs t u d i e st h er e c o m m e n d e rs y s t e ma l g o r i t h mf r o mt w oa n g l e s ， e n t r o p ya n dt h em a r k e tv a l u ef u n c t i o n w i n lm u l t i p l e e v a l u a t i v em e t h o d s ，t h e e x p e r i m e n t a lr e s u l t sr e f l e c tt h ec h a r a c t e r so ft h eu n i f i e df r a m e w o r ko fe n t r o p yf r o m d i f f e r e n ta s p e c t s a tt h es a m et i m e ，i to f f e r sav a r i e t yo fa p p r o p r i a t ee v a l u a t i o n m e t h o d sf o rt h eu n i f i e df r a m e w o r ko ft a r g e tm a r k e t i n g ，i m p r o v e st h em o d e lf u r t h e r k e y w o r d sr e c o m m e n d e ds y s t e m ；u n i f i e df r a m e w o r ko ft a r g e tm a r k e t i n g ；e n t r o p y ； c 0 1 1 a b o r a t i v ef i l t e r i l l 北京t 业大学1 = 学硕1 7 学位论文 i v 目录 目录 摘要! ，i a b s t r a c t i i i 第1 章绪论1 1 1 研究背景与意义1 1 2 相关研究2 1 2 1w r e b 智能2 1 2 2 数据挖掘3 1 2 3 推荐系统4 1 3 研究内容5 1 4 本文结构5 第2 章推荐系统的技术与评价方法7 2 1 推荐系统的系统应用7 2 2 推荐系统的算法和技术8 2 2 1 协同过滤推荐系统8 2 2 2 基于内容的推荐系统1 1 2 2 3 混合推荐系统1 2 2 3 市场值函数1 2 2 4 评价方法1 3 2 4 1 评分准确性评价方法1 4 2 4 2 排序准确性评价方法1 4 2 5 本章小结：1 6 第3 章基于熵的协同过滤推荐模型1 7 3 1 ：确1 7 3 2 基于熵的推荐模型的定义1 8 3 2 1 产品熵1 8 3 2 2 产品间的相似度度量1 9 3 2 3 推荐算法2 2 3 3 实验2 3 3 3 1 实验环境2 3 3 3 2 实验数据2 3 3 3 3 评价方法2 3 3 3 4 实验结果2 4 3 4 本章小结2 5 第4 章基于市场值函数的推荐算法研究2 7 4 1 线性市场值函数2 7 4 2 目标营销统一框架模型2 8 4 2 1 用户偏好2 8 4 2 2 两种目标营销策略2 9 4 2 3 用户和产品的聚类3 0 4 2 4 模型的建立3 1 4 3 模型下的算法改进3 2 v 4 3 1 改进前的算法设计3 2 4 3 2 现有算法存在的问题3 6 4 3 3 改进后的算法描述3 7 4 4 实验3 8 4 4 1 实验环境3 8 4 4 2 实验数据3 9 4 4 3 评价方法3 9 4 4 4 实验结果3 9 4 5 本章小结4 l 结论4 3 参考文献4 5 攻读硕士学位期间发表的学术论文4 9 致 射5 1 v i 第1 章绪论 1 1 研究背景与意义 第1 章绪论 随着信息技术的飞速发展，社会的信息便捷程度是人类历史上前所未有的。 尤其是互联网络的发展，信息通过互联网被大量地复制、传播与共享。网络上的 信息量每日成几何倍数增长着。有数据显示，著名搜索引擎g o o g l e 索引的网页 数量目前已经超过一万亿。面对如此浩瀚的信息海洋，普通的网络用户不得不花 费大量的时间去搜索、浏览自己需要的信息，并且要找到正确的、用户需要的信 息也越来越困难，我们所面临的不是缺乏信息，而是信息过量，信息超载的问题。 电子商务作为近些年来新兴的商业模式，伴随着信息技术的进步而蓬勃发 展，这种新的商业模式，为商家和顾客搭建了更为便利的相互沟通、传递性息、 以及进行各种商业活动的桥梁。目前，电子商务带来的经济效益和社会效益越来 越大，不少传统行业都已经采用了这种的商业模式。随着电子商务的发展，互联 网络上的产品信息、用户信息的膨胀。电子商务的发展同样受到了信息超载问题 的困扰。如何能够更为高速、有效地为商家需找的目标顾客，使为顾客更方便地 找到他们喜欢的产品成为了亟待解决的问题。 在这样的大背景下，研究人员们不断地做着努力，相关的数据挖掘、人工智 能、机器学习、统计学等多个领域的理论和技术成果被应用到互联网络和电子商 务。随着研究的不断深入，一个新的研究领域推荐系统应运而生，受到了众多研 究者的关注，已经成为了当今的研究热点，相关的研究成果更是不断被提出，并 且以其在现实世界网络上的网页信息搜索，电子商务网站上的产品推荐，个性化 的用户推荐服务等诸多实际应用中带来的良好效果越来越为人们所熟知，为人们 所喜欢。 推荐系统为用户提供了个性化的信息推荐服务。帮助消费者决定应该购买什 么产品，模拟销售人员帮助客户完成购买过程，使用户参与程度更低，大大降低 了用户寻找信息的成本，更为重要的是目前推荐系统的成熟技术已经达到了很高 的推荐质量。推荐质量的优秀和用户使用的便捷直接带来的就是商家更好的效 益。有数据显示美国著名电子商务网站a m a z o n 的销售额有3 0 由其网站货品推 荐带来。 根据所采用的推荐技术和推荐策略的不同，目前己经出现了各种不同的推荐 系统模型，比如基于协同过滤的推荐系统、基于内容的推荐系统等。 协同过滤技术目前已经有了比较多的成功应用的例子，但是由于传统的协同 过滤及其本身的算法特点和现有的相似度计算方法使其面对现实世界中广泛的 稀疏数据时有一定的缺点。使得推荐结果的准确性和可靠性打了折扣。信息熵是 北京 = 业大学t 学硕 j 学位论文 衡量信息不确定性的量度。利用信息论中熵的概念来解决以上问题引起了研究者 的兴趣。文献 1 ，2 都对此进行了尝试。但这些研究对于熵理论的利用，尤其是 信息论中丰富相似性方法的利用不足。本文对此进行更为深入的研究，着重从相 似性的角度进行探讨。 目前，推荐系统最常用的三种基本推荐方法是分类、评分和排序： 1 ) 分类：将商品按是否会购买分为两类，对于可能购买的目标客户进行推 荐3 1 。 2 ) 评分：用多级的评分来表示用户对商品的偏好程度，然后通过预测评分 产生推犁4 1 。 3 ) 排序： 排序的方法挑选最有可能被用户购买的t o p - n 产品或挑选最有可 能购买产品的t o p - n 顾客，进行推荐。 由于用户的偏好并非非是即否，分类方法不符合人们选择事物的习惯。评分 的方法当在预测评分相同时，无法对用户的偏好进行更细致地区分，进而进行 t o p - n 推荐。相比较而言，排序是更适合于现代推荐系统的方法【5 】。 目前，已经有了基于排序的通用推荐模型一目标营销统一框架模型【6 7 】，此 模型是基于市场值函数建立的，但在此模型下还缺乏拥有合适评价方法的市场值 函数模型。由于传统的推荐系统评价方法不是基于分值预测的( 如m a e ) 就是 基于分类的( 如正确率、召回率) 【8 】，都不太适合这个模型，需要选择合适的评 价方法，并在该框架模型下改进市场值函刿9 1 ，构造较为完整的基于统一框架模 型的市场值函数模型，进而拓宽w e b 智能 1 0 - 1 4 、数据挖掘的应用领域范围。 1 2 相关研究 1 2 1w r e b 智能 随着信息技术和互联网的飞速发展。互联网上庞大数量的w e b 页面、无数 的网络站点、各种不同类型、层出不穷的数据使得我们在对这些信息的存储、管 理和检索时存在着很大的困难。要处理w e b 环境下结构化、半结构化、非结构 化且相互关联的对象组合，因此，必需要增强和发展现有的信息技术中的相关理 论、方法和技术来有效处理w e b 相关的问题。 w e b 智能【1 0 。4 】正是在这样的大背景下诞生的一个新的研究领域，最早由 z h o n g 等在2 0 0 0 年美国i e e e 国际计算机软件与应用学术会议上提出，w e b 智能 的目的就是研究新的基于网络的信息处理技术和新的应用。其英文简称为w i ， 简单来讲，可以将其看作是将人工智能技术和信息技术应用在互联网络这个新的 平台上。l i u 】认为w e b 智能的最终理性目标为实现智慧网。通过智慧网，人们 2 第1 芎绪论 不仅可以从w e b 上浏览和搜索信息，而且可以通过w e b 获取智慧，从而使得 w e b 更好的为人们的生活、学习、工作、娱乐服务，因而提出万维智慧网的概念。 y a o 1 2 , 1 3 1 认为可以从信息科学和知识管理的角度来看网络，将w e b 的发展看成是 从数据的w e b 发展到信息的w e b 和知识的w e b ，再发展到智慧的w e b 。数据、 信息、知识和智慧的层次性是信息科学和知识管理领域详细研究的概念。当前的 w e b 时代主要处理数据、信息和一定程度熵的知识。新一代的w e b 将重点放在 知识、智能和智慧上。 虽然w e b 智能的相关部分，如人工智能，认知科学，神经科学的各个领域 的研究已经分别进行了多年，并且有了很多深入的研究成果。但是还没有一个统 一的架构使智能能够被系统的研究从而发展人类级的智能w e b 。而w 曲智能就 是要将这些分散的研究统一起来，进一步探索新的理论技术。 从技术层次划分，w e b 智能包括i n t o m e t 层、接口层、知识层、应用层四个 层浏9 1 。目前w i 的具体研究内容包括【1 0 j 4 1w e b 人本媒体工程、w e b 信息管理、 w 曲信息检索、w e ba g e n t 、w e b 挖掘和w e bf a n n i n g 、w e b 信息系统的环境和 基础、以及基于w e b 的应用等7 个大的组成部分。由于推荐系统的研究意在为 顾客和提供更智能的，更个性化的电子商务消费环境。因而也成为w e b 智能研 究的重要组成部分。并且与w 曲智能的很多研究内容都有着十分密切的联系。 1 2 2 数据挖掘 在信息时代，人们生活在极为丰富且日益膨胀的数据之中，却很难得到想要 的知识，为解决这样的问题，数据挖掘应运而生。数据挖掘侧重于对观测数据集 的分析，从中寻找未被发现的关系，将数据以新的、用户可理解的、有价值的方 式提炼出来。它是一门涉及面很广的交叉学科，吸收了机器学习、信息检索、数 据库技术、人工智能、模式识别、数理统计、粗糙集、模糊数学、神经网络等多 学科成熟的相关理论与技术。数据挖掘的主要技术包括：分类，评估、预测、关 联分析、聚类等【3 1 。 目前，在学术研究领域，数据挖掘技术作为数据处理的重要研究课题，其关 键性已经被研究者所广泛认同。也有了不少相关的学术会议，如美国计算机协会 数据挖掘专业组国际会议( a c ms i g k d d ) 、i e e e 数据挖掘国际学术会议 ( i c d m ) 、工业与应用数学学会数据挖掘会议( s d m ) 、美国计算机学会数据管理 国际会议( a c ms i g m o d ) 、亚太地区数据挖掘国际会议( p a k d d ) 、欧洲数据挖 掘会议( p k d d ) 等。主要的学术刊物有：美国计算机学会的 t r a n s a c t i o n so n k n o w l e d g ed i s c o v e r yf r o md a t a 、国际电子电器学会的t r a n s a c t i o n so n k n o w l e d g ea n dd a t ae n g i n e e r i n g ) ) 等。 北京t 业大学t 学硕t 学位论文 在工业界，现今的数据挖掘更多地用在了非常专业化的领域。例如在气象预 报领域，通过地球观测卫星和地面观测站获得的气候数据在数据量上是庞大的， 数据形式上是复杂的，要从这样的数据中获得信息，数据挖掘不可或缺。在生物 信息学研究中，一个很重要的数据挖掘研究热点就是d n a 序列的分析，探求生 物基因密码，尤其是挖掘生物基因序列和疾病的关联。在银行业、通讯业、零售 业以及电子商务领域都有着大规模的商业数据，这些行业都高度依赖于数据挖掘 工具进行商业决策，分析客户偏好，评估销售业绩。 1 2 3 推荐系统 什么是推荐? 在日常生活中，人们选择产品时，如果对于目标产品没有经验， 往往会寻求购买过此产品的人的意见，比如，我们在购买图书的时候会在网上寻 找查看他人对于此书的评价。外出就餐时餐馆的选择也会以其口碑为重要依据。 简单来讲，推荐系统就是将这种用户借助他人意见选择商品的过程利用现代信息 技术加以量化，从而帮助用户选择产品。 目前被引用最多的，最被人们所认可的推荐系统的定义是由r e s n i e k 和 v a r i a n 在1 9 9 7 年提出的【15 1 ，其内容为：利用电子商务网站向客户提供商品信息 和建议，帮助消费者决定应该购买什么产品，模拟销售人员帮助客户完成购买过 程。 伴随电子商务的发展推荐系统广泛的应用逐渐被人们所认识，相关的技术也 是不断被提出。早期推荐系统研究领域的技术主要来自于信息检索、数据挖掘等 相关研究领域。这些研究领域经过无数科研工作者多年的辛勤耕耘，已经有无数 非常成熟、非常优秀的理论与技术。研究者们将这些理论与技术引入到推荐系统 这一新的研究领域，并且结合这一领域的特点进行了增强和发展，取得了很好的 效果。目前，推荐系统依照其所使用的基本推荐技术主要可以分为协同过滤推荐 系统、基于内容的推荐系统以及混合推荐系统三大类。 在学术界，目前推荐系统的主要相关学术会议有：美国计算机学会推荐系统 国际会议( a c mr e c o m m e n d e rs y s t e m s ) 、智能用户界面国际会议( i n t e r n a t i o n a l c o n f e r e n c eo fi n t e l l i g e n tu s e ri n t e r f a c e s ) 、美国计算机学会信息检索专业组国际会 议( i n t e r n a t i o n a la c m s i g i rc o n f e r e n c e ) 。 在工业界，推荐系统应用非常广泛。其最典型的应用就是a m a z o n 、t a o b a o 、 e b a y 的商品推荐，g o o g l e 和b a i d u 的网页推荐，当当网和c h i n a - p u b 的图书推荐。 推荐系统是非常贴近现实世界应用的研究领域，它来源于电子商务的发展，推荐 技术的进步也促进着电子商务的发展。世界上最大的在线影片租赁提供商n e t f l i x 的设立的n e t f l i x 大奖不仅推动着研究的进步，也带来了网站服务质量与用户体 4 第1 苹绪论 验的提高。是研究与应用相结合的具体体现，也反映了推荐系统研究中理论与实 际的紧密结合。 1 3 研究内容 本文针对传统协同过滤本身的一些缺点，考虑将熵和熵相关的度量引入到协 同过滤之中，为协同过滤提供新的方法与技术。本文对于目标营销统一框架模型 目前所存在的面对现实世界数据特点缺乏好的市场值函数模型的问题加以研究。 对算法进行改进。具体的研究内容如下： ( 1 ) 将熵与传统协同过滤相结合的研究 本文考虑现实世界营销与推荐过程的特点。将熵与产品的被评价情况相结 合，用熵来描述产品被用户的喜好情况，构建产品熵。利用信息论中非常丰富的 与熵相关的理论成果，不仅引入了衡量熵相似性、统计相关性的条件熵、互信息， 还引入了基于此两种方法在信息检索研究中构建的多种相关性衡量方法。并且根 据产品熵的特点借鉴基于产品的协同过滤设计了实用算法。最后将产品熵、多种 相似性衡量方法、实用算法在协同过滤基本思想下进行整合，构建了基于熵的协 同过滤推荐模型。 ( 2 ) 市场值函数的研究与改进 本文根据目标营销统一框架模型的优点和特点，以及当今现实世界多级评分 数据的形式。考虑到统一框架模型下现有市场值函数模型还没能对此种类型的数 据进行充分利用，而推荐系统研究中更好地利用信息很有可能带来更优的推荐效 果。基于此，本文对现有的市场值函数模型进行改进，探索适合于多级评分数据 集的市场值函数模型。将评分数据的特点充分发挥出来，提高推荐的效果，进一 步完善目标营销统一框架模型。 ( 3 ) 对于目标营销数据挖掘模型的多评价方法实验 本文对于算法的实验采用了多种评价方法。对于基于熵的统一框架模型来 讲，通过多种的评价方法可以从不同的侧面来反映推荐的效果，更全面地衡量推 荐效果。对于目标营销统一框架模型来说，传统的一些评价方法并不适用。引入 一些新的评价方法，除了验证算法的有效性、算法改进的效果之外，还为用户使 用模型算法时提供了多种选择，进一步完善目标营销统一框架模型。 1 4 本文结构 本文将按照以下结构进行组织： 第l 章本文的绪论，简要介绍了本文的研究背景、研究意义、相关的研究 5 北京t 业大学t 学硕t 学位论文 以及本文的主要研究内容。 第2 章主要介绍了本文研究所需要的相关技术和评价方法。综述了推荐系 统应用的发展，推荐系统领域主要的协同过滤等技术的原理与特点。介绍了推荐 系统领域的评价方法，对本文使用的评价方法进行了说明。 第3 章利用信息熵理论构建了产品熵，然后将熵和相关的度量如条件熵、 互信息引入到协同过滤之中，借助这些量的特点构建了基于熵的协同过滤推荐模 型，通过实验验证了模型算法的有效性。 第4 章介绍了市场值函数、目标营销统一框架模型等重要理论，为适应新 的现实世界数据改进了原有得市场值函数模型，通过实验验证了改进效果。 6 第2 章推荐系统的技术j 评价方法 第2 章推荐系统的技术与评价方法 推荐系统预测用户与产品间的兴趣关系。这种预测通常来说是基于用户的信 息、用户评价历史数据以及产品的属性的。大多数的推荐系统首先预测用户如何 评价某产品，然后基于这种预测出的信息，将具有高评价的产品进行推荐。从技 术方面来讲，目前的推荐系统领域已经形成了比较成熟的体系，具体的理论和技 术在实际的应用中也取得了很好的成绩。 对于推荐来讲，由于作为推荐目标的人的需求的个性化和多样性，如何来衡 量其推荐效果的优劣是比较困难的。很多的研究者注意到了这点，对于推荐系统 的评价进行深入研究，引入或提出了很多成果来尝试解决此问题，但是目前还没 有统一的概念来衡量推荐系统的质量，推荐系统的效果也无法用统一的标准来刻 画。所以比较推荐系统的推荐效果时就需要从现有的评价方法中选择适合于本算 法或本系统推荐目标的方法。 所以，本章除了从系统应用、算法技术的角度对推荐系统的理论进行综述外， 还将介绍推荐系统的评价方法，并着重介绍适合于本文的方法。 2 1 推荐系统的应用 最早在1 9 9 2 年，g o l d b e r g 等人创造了协同过滤算法 16 1 ，并基于此构建了一 个新型邮件过滤系统一t a p e s t r y ，这项开创性的研究成果，被学术界普遍认为是 第一个真正意义上的推荐系统【l4 1 。其后，随着电子商务的兴起，越来越多的人投 入到推荐系统的研究。1 9 9 9 年以后，a c m 等学术组织开始开展针对推荐系统的 专题研讨。 起初，推荐系统更多地是一些实验性质的系统，主要用于信息过滤，如电子 邮件的过滤、新闻组文章的过滤等，代表系统有g r o u p l e n s r 7 1 、r e f e r r a l w e b 、 p h o a k s 18 1 、s i t e s e e r 、f a b 等。 在互联网络高速发展的今天，在我们的生活中到处都可以看到推荐系统的影 子。从a m a z o n 、e b a v 、淘宝网的商品推荐，到g o o g l e 新闻资讯的推荐。m o v i e l e n s 的电影推荐，甚至到各个小的b b s 社区，也有诸如“今日十大热门话题”之类的 简单推荐系统。 在学术界，r e s n i c k 和s c h a f e r 曾分别在文献 1 5 和文献 1 9 1 中对当时最为 著名的推荐系统应用进行了多角度的比较、分析和总结。对于人们更好地认识推 荐系统的发展状况与发展前景有很大的帮助。 7 北京t 业大学工学硕十学位论文 2 2 推荐系统的算法和技术 目前，推荐系统研究领域已经形成了较为成熟的理论与技术体系，依照其所 使用的基本推荐技术主要可以分为协同过滤推荐系统、基于内容的推荐系统以及 混合推荐系统三大类。 2 2 1 协同过滤推荐系统 在现实生活中，每个人都是独立的个体，可是又会根据用户的兴趣等因素， 聚集成一个一个的类。一个根据兴趣而形成类中用户，对于更多新事物的兴趣和 观点往往也具有很高的相似性。而协同过滤就是利用这种现象，在为用户推荐时， 首先找与他兴趣相似的同类型用户，然后将这些用户感兴趣的内容推荐给此用 户，或者利用这些用户对于产品的评价来预测目标用户对于产品的评价。 协同过滤推荐系统的基本架构非常简单，传统的协同过滤系统主要包括如图 所示的三个部分。首先是如何利用评分数据，通常是将评分数据表示成评分表的 形式，对于评分的具体使用已经有很多优秀的研究成果。第二个关键的步骤是最 近邻居的计算，这就要选择用何种的相似性方法来度量用户间的兴趣关系，方法 的选择和评分数据如何表示也有密切的关系，最后就是根据最近邻居集预测评分 生成推荐序列。 随着协同过滤理论与技术的不断发展，现在，我们不仅可以根椐相似用户的 评价为用户推荐商品，还可以根据用户对不同商品的相似评价，为商品寻找潜在 顾客。从这个角度来看，目前的协同过滤技术主要可以分为基于用户的协同过滤 和基于产品的协同过滤两大类。 1 l1 2 1 3i q1 51 6i n u 1l5 u 2 5 一 p u 3 4 u 42 u 5 一 5 ；1 磁 l j l f ih ，气| u s e t s 评分表 i t e m s k 个最近邻居 图2 1 传统协同过滤的推荐流程 f i g u r e2 1t 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 推荐序列 力 第2 章推荐系统的技术与评价方法 2 2 1 1 基于用户的协同过滤 基于用户的协同过滤的主要思想就是根据与目标用户历史兴趣相似的用户 或用户集对于待预测产品的评价，推测出目标用户对于待预测商品的评价，根据 这些评价，选取目标用户可能喜好的产品向目标用户进行推荐。 基于用户的协同过滤算法主要包括以下步骤： 1 计算所有用户之间的相似性s i m ( x ，y ) 。 2 根据相似性计算目标用户x 的最近邻用户集n b s x 。 3 根据公式( 2 1 ) 预测目标用户x 对于待预测产品，的评分。 s i m ( x ，y ) x ( r y 广墨) 一 ， ， r x , i = 瓦+ 燮玎 协) y n b s x 其中，墨是用户x ，】厂对产品的平均评分。 4 根据评分产生推荐序列。 2 2 1 2 基于产品的协同过滤 基于产品的协同过滤的主要思想就是根据目标用户对于与待预测产品获得 历史评价相似的产品或产品集的评价，推测出目标用户对于待预测产品的评价， 根据这些评价，选取目标用户可能喜好的产品向目标用户进行推荐。 基于产品的协同过滤算法主要包括以下步骤： 1 根据对产品x 和】，都进行过评价的用户的评价数据计算所有产品之间的 相似性s i m ( x ，y ) 。 2 根据相似性计算待预测产品x 的最近邻用户集n b s x 3 根据公式( 2 2 ) 预测目标用户，对于待预测产品x 的评分。 s i m ( x ，y ) r ，y r i , x - - 鼍孓丽玎 q - 2 ) y n b s x 4 根据评分产生推荐序列。 2 2 1 3 协同过滤技术的相似性问题 通过分析协同过滤的两种主要推荐技术我们可以看到，计算相似性是协同过 9 北尿l 业大掌【掌坝j j 掌1 市论又 滤的最关键的步骤，目前应用最为常用的方法是余弦相似性( c o s i n e ) 和相关相 似l 生( c o r r e l a t i o n ) 方法【4 ，7 2 0 1 。 余弦相似性( 以基于用户的协同过滤为例) ： r p r 徊 砌 一卜一p a p q 。3 相关相似性( 以基于用户的协同过滤为例) ： ( 心。p - 一r c , x r 。, 厂石) 酊似c f ，劲2 万p e 霭p 弼甄雨 q 。4 其中s i m ( c i ，c j ) 是m pc f 和用户巳的相似度。r p 和r 舻分别是用户c i 和用 户勺对产品p 的评分。r 和足，是用户c f 和用户巳对产品的平均评分。 协同过滤技术最为现在应用最为广泛的推荐技术，它能够根据各项目的品 质、风格、观点来产生推荐，但其还是存在一些缺点： ( 1 ) 稀疏性问题 在现实世界推荐系统的应用过程中，用户数量的累计，产品的丰富，使得其 数量可以用庞大来形容。举例来说，在一个拥有一万件商品的购物网站上，有一 万名注册的用户，对于协同过滤推荐系统来说，可以视为有1 0 0 0 0 1 0 0 0 0 的矩阵， 总共有一亿个位置。而绝大部分用户购买过、评价过的商品数量是非常有限的， 这就使得评价矩阵的稀疏度是非常之高的。而这么高稀疏度的评价矩阵。在进行 协同过滤时，结果的可信度就会大打折扣。 ( 2 ) 冷启动问题 一位新的用户，在系统上没有任何的使用记录、评分数据。一件新的产品， 在系统上没有任何被评价过的历史。利用最相似的邻居用户或者邻居产品的传统 协同过滤方法就无法对评分进行预测，进而无法产生推荐。 ( 3 ) 扩展性问题 协同过滤的计算复杂度会随着用户和产品的增加成倍增长，因为采用计算最 近邻居的方法，计算的复杂度与用户数量或产品数量成平方的关系。随着系统的 运行，数据量的增大，对于系统硬件、系统效率都会有一定的挑战。 1 0 第2 章抟荐系统的技术与评价方法 2 2 2 基于内容的推荐系统 在生活中，人们在选择产品时，会选择和印象中接近或者相似的产品，而这 些产品通常都会都具有某些用户非常偏好的相似的特征或者属性。基于内容的推 荐系统【2 1 2 2 正是借鉴这种思想。假设能使用户感兴趣的产品应该与用户以前喜欢 或者购买过的产品在某些特征或属性上相似。如前文所述，协同过滤通常是度量 用户偏好间或产品被用户喜欢的情形之间的相似性，而基于内容的推荐系统则是 度量用户的偏好特征和产品间的相似程度，其核心是对产品内容、特征的分析。 此种方法的将基本步骤如下，简单示例如图2 2 。 1 通过历史数据建立用户兴趣模型( u s e rp r o f i l e ) 。图2 - 2 中经过对用户喜爱 的电影集合c 的分析，用户喜欢具有喜剧、科幻、惊险特征的电影。 2 对每个待推荐产品集中的产品进行特征提取。图2 中提取出电影a 属于喜 剧、科幻、惊险类的电影，电影b 属于爱情、文艺类电影。 3 当需要对某个用户进行推荐时，把该用户的用户兴趣模型同产品集中的产 品特征进行比较得到二者的相似度，图2 2 中通过将电影a 和电影b 的特征和 与用户兴趣模型进行比较，发现电影a 的特征与用户的兴趣模型较为一致 4 通过相似度生成推荐序列，进行推荐。图2 2 中的简单示例可以直接将电 影a 推荐给用户。 国当圈刊_ 喜剧，科幻，惊险 爱情，文艺片 喜剧，科幻，惊险 图2 2 基于内容推荐的流程 f i g u r e2 - 2c o n t e n t - b a s e dr e c o m m e n d a t i o n 基于内容的推荐由于其利用的是产品本身的特征进行衡量，所以很好地解决 了协同过滤的冷启动问题，即使有新的从未被评价过的商品，只要分析其属性、 特征，也能很好地进行推荐。对于推荐一些被评价数量极少或者并不流行的事物 来说，基于内容推荐也是很好的解决办法。事物通常都具有两面性，基于内容的 推荐的特点也带来了其一些缺点。因为采用的是属性、特征，所以无法推荐一些 塑 臻 盈 丑 圈酮一 可一圈 夕。 ，矿， 北京t 业人学t 学硕 j 学1 壶论文 与以往有很大不同的新颖的产品，对于科学、文化飞速发展，新事物层出不穷的 当代社会来说，这样的缺点的确是不能忽视的。另外，有很多事物的特征是很难 刻画的，比如，艺术、设计风格、用户观点等。对于这些事物推荐上的缺陷，也 体现了基于内容推荐方法一些局限性。 2 2 3 混合推荐系统 前文分析了协同过滤推荐系统和基于内容的推荐系统两大类最为主要的推 荐系统的特点，他们各自都具有一些缺点。研究者们将他们的相结合，取长补短， 优势互补，提出了很多优秀的研究成果，可以统称为混合推荐系统。文献 2 3 将 协同过滤与基于内容的过滤相结合的方法总结为以下四种。 1 分别用协同过滤和基于内容的过滤进行预测，最后进行结合。 2 将一些基于内容过滤的技术融入到协同过滤之中。 3 将一些协同过滤的技术融入到基于内容过滤之中。 4 充分结合这两种技术建设一个混合推荐系统。 第一种方法中两种技术预测出的评分可以进行线性的结合也可以使用某种 衡量方法进行选择。在协同过滤之中使用用户兴趣模型来寻找用户的最近邻居是 方法二的典型例子。第三种方法例如对基于内容的推荐技术中用户兴趣模型的降 维。方法四例如将基于内容的推荐和协同过滤的某些特性用到基于规则的分类器 之中。文献 2 4 进行了细致的分析，将现有的混合推荐系统中协同过滤技术和基 于内容的推荐技术相结合的具体技术归纳为，主要有加权，变换，混合，特征组 合，层叠，特征扩充、元级别等种类。 2 3 市场值函数 市场值函数最早来源于信息检索，并发展为一种应用于目标营销的客户选择 方法，作为本文的重要理论基础，在此进行简要介绍。 市场价值函数【7 ，2 5 ，2 6 】由y a o ，z h o n g 于2 0 0 1 年提出。这一线性模型的构建基于 假设相似的顾客将做出相似的决定。具体函数形似的构建基于假设：每一个对象 都是由一个有限的属性集合的属性值来表示，并且可以用一个线性的市场值函数 来计算对象的市场值。 此函数模型的具体形式为 r ( x ) = 铊“口( 乞( x ) ) ， ( 2 - 5 ) a e a t 其中u 为效用函数，缈为权值。材的值可以是正数、负数或者零，u 0 说明对 象x 在属性a 上相似于正例；如果u 0 ，说明对象x 在属性a 上相似于负例；如 1 2 第2 辛推荐系统的技术与评价方法 果u = 0 ，那么说明对象x 在属性a 上既不相似于正例也不相似于负例。如果属性 具有较大权值就说明该属性对于用户的偏好比较重要，属性的权值如果接近零或 为负就说明该属性对用户的偏好不太重要【7 】 2 5 】【2 6 】【2 7 1 。 在实际的应用中根据具体的情况为市场值函数找到具体的形式，通过计算对 象各属性值的效用函数的加权和，算出对象的市场值，根据市场值进行排序，形 成推荐序y o t 2 9 】 3 0 】。 目前基于市场值函数的深入探讨以及多方面的应用研究还不是很多，已有的 基于市场值函数的研究成果主要有以下这些： 文献 2 9 使用d e c i l e 、l i f t 评价方法【2 8 】对市场值函数在n e e 现实数据库的多种 不同商品上的实验和与朴素贝叶斯方法的实验