（计算机软件与理论专业论文）基于形式概念分析的协同推荐技术研究.pdf

西华大学硕士学位论文 基于形式概念分析的协同推荐技术研究 计算机软件与理论 研究生李凯指导教师杜亚军 摘要 随着互联网的普及和电子商务的发展，电子商务系统在为用户提供越 来越多便利的同时，其结构也变得更加复杂，用户经常会迷失在大量的商 品信息空间中，无法顺利找到自己需要的商品。推荐系统能够直接与用户 交互，模拟商店销售人员向用户提供商品推荐，帮助用户找到所需商品， 从而顺利完成购买过程。在日趋激烈的竞争环境下，推荐系统能有效保留 用户、防止用户流失，提高电子商务系统的销售。推荐系统在电子商务系 统中具有良好的发展和应用前景，逐渐成为电子商务技术的一个重要研究 内容，受到越来越多研究者的关注。 近年来，推荐系统在理论和实践中都得到了很大发展。但是随着系统 规模的扩大，推荐系统也面临一系列挑战。针对推荐系统面临的主要问题， 本文把形式概念分析( f o r m a lc o n c e p ta n a l y s i s ) 这一强有力的工具应用到 推荐系统中以提高推荐效率，但形式概念分析中的构建概念格( c o n c e p t l a t t i c e ) 是一个相当费时的工作。针对这一问题，本文进行了有益的探索和 研究，研究的主要内容为如下两方面： 1 ) 为了概念格能在协同推荐系统中得到更好的应用，本文提出了一种 时间复杂度低、实现简单的建格方法基于矩阵运算的建格方法。在矩 阵运算的基础上，本文提出了建格的算法b c l m o 。与一些传统的建格方 法相比，b c l m o 明显提高了抽取形式概念的速度，大大降低了其时间复 杂度和空间复杂度。 2 ) 针对协同推荐系统，本文提出了两个新的概念核心概念和核心 第1 页 西华大学硕士学位论文 概念格，并把核心概念格应用到了协同推荐中。基于核心概念格的协同推 荐算法不仅避免了构建概念格的复杂性，而且事先过滤掉了那些根本不可 能成为目标用户“最近邻居”的用户，这样既减少了计算量，又降低了时 间以及空间复杂度，而且在一定程度上起到了去噪功能。后经实验证明这 种方法既可以提高推荐效率，也可以提高推荐质量。 关键词：协同推荐，形式概念分析，核心概念，核心概念格，矩阵运算 第1 i 页 西华大学硕士学位论文 r e s e a r c ho fc o l l a b o r a t i v er e c o m m e n d a t i o n b a s e do nf o r m a lc o n c e p ta n a l y s i s c o m p u t e rs o f t w a r e & t h e o r y m a s t e rd e g r e ec a n d i d a t e ：k a il i s u p e r v i s o r ：u nd u a b s t r a c t w i t ht h er a p i ds p r e a do ft h ei n t e r n e ta n dt h ed e v e l o p m e n to fe c o m m e r c e ， e - c o m m e r c es y s t e m sh a v em a d em o r ec o n v e n i e n tf o ru s e r s a tt h es a m et i m e ， i t ss t r u c t u r eb e c o m e sm o r ea n dm o r ec o m p l e x i ti sd i f f i c u l tf o ru s e r st of i n d t h ep r o d u c t sa n ds e r v i c e sw a n t e d r e c o m m e n d a t i o ns y s t e mc a nd i r e c t l y i n t e r a c tw i t hu s e r s ；i tc a nr e c o m m e n df o ru s e r st os i m u l a t es a l e s m a na n dh e l p u s e r s g e t t h e g o o d s w a n t e d i nt h ei n c r e a s i n g l yf i e r c e c o m p e t i t i o n ， r e c o m m e n d a t i o ns y s t e mc a ne f f e c t i v e l yk e e pu s e r sa n di m p r o v et h es a l e s w i t hag o o dp r o s p e c to fd e v e l o p m e n ta n du t i l i z a t i o n ，r e c o m m e n d a t i o ns y s t e m h a sb e c o m ea ni m p o r t a n tr e s e a r c hf i e l d r e c e n t l y , r e c o m m e n d a t i o ns y s t e mh a sb e e nv e r ys u c c e s s f u li nb o t ht h e o r y a n dp r a c t i c e h o w e v e r , w i t ht h ei n c r e a s eo ft h es y s t e m ，i ta l s of a c e sc h a l l e n g e s a i m e da tt h em a i np r o b l e m so fr e c o m m e n d a t i o ns y s t e m s ，t h i sp a p e ra p p l i e s f o r m a lc o n c e p ta n a l y s i st oi m p r o v et h ee f f i c i e n c yo fr e c o m m e n d a t i o n h o w e v e r , e x t r a c tf o r m a lc o n c e p tf r o mf o r m a lc o n t e x ta n de s t a b l i s hc o n c e p t l a t t i c ea r et i m e c o n s u m i n g t h e r e f o r e ，s t i c kt ot h ep o i n t ，t h i sp a p e rc a r r i e s t h r o u g hau s e f u le x p l o r ea n dr e s e a r c h ，t h et w om a i np o i n t so ft h er e s e a r c ha s f o l l o w s ： 1 ) i no r d e rt ob e t t e ra p p l yc o n c e p tl a t t i c et or e c o m m e n d a t i o ns y s t e m ，t h i s p a p e rp r o p o s e sa l o w e rt i m ec o m p l e x i t ya n ds i m p l em e t h o df o rc o n s t r u c t i n g f o r m a lc o n e 印tl a t t i c e ，w h i c hb a s e do nm a t r i xo p e r a t i o n o nt h eb a s i so f m a t r i xo p e r a t i o n ，an e wa l g o r i t h mb c l m oi sp r o p o s e df o rc o n s t r u c t i n g 第1 i i 页 f o r m a lc o n c e p tl a t t i c e c o m p a r i n gw i t hs o m et r a d i t i o n a lm e t h o d ，b c l m o c o u l dd i s t i n c t l yi m p r o v et h es p e e do fe x t r a c t i n gf o r m a lc o n c e p t 。a n dd e c r e a s e t h et i m ea n ds p a c ec o m p l e x i t y 2 ) a i m i n ga tr e c o m m e n d a t i o ns y s t e m t h i sp a p e r p r o p o s e st w on e w n o t i o n s c o r e - c o n c e p ta n dc o r e c o n c e p tl a t t i c e ，a n da p p l i e s c o r e c o n c e p t l a t t i c et or e c o m m e n d a t i o n s y s t e m b a s e do nt h e c o r e c o n c e p t ，t h e c o l l a b o r a t i v er e c o m m e n d a t i o na l g o r i t h mn o to n l ya v o i d st h e c o m p l e x i t yo f c o n s t r u c t i n gf o r m a lc o n c e p tl a t t i c e ，b u ta l s of i l t e r st h eu s e r sw h oc a n tb e “t h e l a t e s tn e i g h b o r s ”i td e c r e a s e st h ec o m p u t a t i o n a ls c a l e ，r e d u c e st h et i m ea n d s p a c ec o m p l e x i t y ，a n dg e t sr i do ft h en o i s et oac e r t a i nd e g r e e a f t e r w a r d e x p e n m e n t sp r o v et h i sm e t h o dc a l li m p r o v et h er e c o m m e n d a t i o ne f f i c i e n c y a n dq u a l i t y k e y w o r d s ：c o l l a b o r a t i v er e c o m m e n d a t i o n ，f o r m a lc o n c e p ta n a l y s i s ，c o r e c o n c e p t ，c o r ec o n c e p tl a t t i c e ，m a t r i xo p e r a t i o n 第页 西华大学硕十学位论文 声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的 研究成果。除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得西华大学或其他教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论 文中作了明确的说明并表示谢意。 本学位论文成果是本人在西华大学读书期间在导师指导下取得的，论文成 果归西华大学所有，特此声明。 作者签名： 聊签名：批纷 第“页 嗍岔年厂月可日 文。影年广月前日 西华大学硕士学位论文 第1 章引言 随着互联网技术的快速发展，i n t e m e t 已成为人们获取信息的一个重要途 径，然而由于i n t e m e t 上信息的爆炸式增长，人们不得不花费大量的时间来搜索、 浏览自己需要的内容。虽然信息检索技术在一定程度上能够满足人们的查找需 求，但是它无法针对不同用户提供个性化的服务。为减轻用户的查找负担，满 足不同用户的不同需求，推荐系统的研究越来越为人们所重视并被广泛应用于 电子商务，数字图书馆等领域。本章主要介绍个性化推荐系统的背景和国内外 的研究现状，讨论研究的意义，并说明本文的工作和结构安排。 1 1 研究背景以及当前现状 推荐系统能够主动地在海量的信息中寻找用户感兴趣的内容并向用户进行 推荐，它所体现的“个性化”服务已越来越多的被成功应用到了电子商务网站、 电子图书馆等众多领域 1 】。 1 1 1 推荐系统的研究背景 i n t e r n e t 的迅速发展将人类带入了信息社会和网络经济时代，对个人生活和 企业发展都产生了深远的影响。一方面，i n t e m e t 的发展正在极大的改变着我们 每个人的生活，人们不出家门就可以随心所欲的得到自己需要的各种信息：另 一方面，基于i n t e m e t 的虚拟企业也不再需要像传统企业那样的实体投资，企 业与顾客、供应商等通过网络建立起更直接的联系。 但是，随着w 曲信息的日益增长，“信息超载 ( i n f o r m a t i o no v e r l o a d ) f 司题 随之产生。人们不得不花费大量的时间去从网络上搜索浏览自己需要的信息。 为了减轻用户的检索负担，搜索引擎( s e a r c he n g i n e ) 技术得到了广泛的应用，如 传统的搜索引擎a l t a v i s t a ，y a h o o 和新一代的搜索引擎g o o g l e ，b a i d u 等。信 第1 页 西华大学硕士学位论文 息检索技术满足了人们一定的需要，但由于其通用的性质，仍不能满足不同背 景、不同目的和不同时期的查询请求。基于这一背景，推荐系统被提出并快速 地得到了广泛的应用。 推荐系统是指能够主动为人们推荐相关信息的系统。到目前为止，推荐系 统并没有一个统一而精确的定义。下面这段话是关于推荐系统的经典描述 2 】。 人们经常必须在对所要选择的事物没有充分了解的情况下做出选择：在日常生 活中，人们依靠众口之词、推荐信、报纸上的影评或书评和调查报告等的推荐 来完成这一过程；推荐系统就是用于模拟或模仿这些物品的系统。个性化推荐 系统是信息技术发展的产物，也是社会发展的需要。对个性化推荐系统的研究 尤其具有重要的意义。 与推荐系统类似，信息过滤技术是通过对用户兴趣和行为的学习来选取相 关信息的技术。推荐系统与信息过滤一个是择取所需，一个是摒弃无关，看似 是两个相反的过程，但两者的目标和方法是一样的，因此，下文中我们不再区 分推荐系统与信息过滤两个概念。 信息过滤技术能较好的解决“信息过载”和“资源迷向”的问题，让人们 能够更充分地使用i n t e m e t 上的信息资源。信息过滤( i n f o r m a t i o nf i l t e r i n g ) 是实 现信息的个性信息推荐的基础。在信息领域，每个用户都有自己特定的、长期 的信息需求，用这些信息需求组成过滤条件，从动态的信息资源流中过滤出服 务需求的内容，屏蔽掉无用的信息并进行服务，这种做法就叫做信息过滤。 基于信息过滤技术的推荐系统具有良好的发展和应用前景。目前，几乎所 有大型的商务系统，如a m a z o n ，c d n o w ，e b a y 等，都不同程度的使用了各种 形式的推荐系统。各种提供个性化服务的w e b 站点也需要推荐系统的大力支持。 在日趋激烈的竞争环境下，推荐系统能有效保留用户，提高电子商务系统的销 售。推荐系统将会产生巨大的经济效益。 由于推荐系统的诸多优点，它得到了越来越多的关注，并且在理论和实践 方面都得到了很大发展。 第2 页 西华大学硕士学位论文 1 1 2 推荐系统的发展及研究现状 推荐系统( r e c o m m e n d e rs y s t e m s ) 在1 9 9 7 年之前一直被称作协同过滤系统 ( 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 的概念是在1 9 9 2 年由b o bg o l d b e r g 等人 构造邮件系统t a p e s t r y 时提出的 3 】。而这一方法的主要缺点是一个用户的兴趣 很少能整齐的映射到系统提供的邮件列表中。一种改进方案是由用户指定一个 过滤器，然后邮件系统根据每个用户指定的过滤器来搜索整个邮件列表，提供 用户感兴趣的邮件。这一方法得到了很多邮件系统的支持。但是这些系统提供 的过滤器都是基于内容的( c o n t e n t b a s e d ) ，没有考虑人的因素，如用户不能指定 “我的邻居b o b 读过的并且认为比较好的邮件”这样的过滤器。于是b o b g o l d b e r g 等人定义了用户这种目的的过滤器。当用户指定了多个这样的过滤器 时，整个过滤过程就相当于多个邻居相互协作为当前用户过滤信息，因而称之 为协同过滤。总的来说，c f 的主要思想是：把“邻居( 和当前用户兴趣相近 的人) 们都认为好的物品推荐给当前用户。 推荐系统有很多应用领域。1 9 9 7 年以前，推荐系统主要用于信息过滤，如 电子邮件的过滤、新闻组文章的过滤等，代表系统有t a p e s t r y ，g r o u p l e n s ， p h o a k s ，f a b ，r e f e r r a lw 曲，s i t e s e e r 3 8 等。1 9 9 7 年以后，推荐系统被引入 一个新的应用领域电子商务。在引入推荐系统以后，电子商务系统可以预 测用户的喜好，顾客可以很容易的找到自己感兴趣的商品，这样不仅极大的方 便了顾客，而且潜在的增加了电子商务的交易量，为商家带来了可观的收益。 因此，电子商务商家纷纷开始把推荐系统嵌入到他们的电子商务系统中，引发 了推荐系统研究和应用的热潮。到目前为止，很多商业公司开展了推荐系统的 研究，例如i b ma l m a d e nr e a r c hc e n t e r ，c o m p a qr e s e a r c hc e n t e r 等；美国几乎 所有知名的大学都有专门从事推荐系统的研究组，如u cb e r k e l e y 的b e r k e l e y w o r k s h o po nc o l l a b o r a t i v ef i l t e r i n g 。 1 1 3 推荐系统面- 临的主要挑战 在文献 9 中总结了推荐系统所面临的一系列挑战，其主要包括： 第3 页 西华大学硕士学位论文 2 ) 3 ) 实时性与推荐质量之间的平衡：推荐系统的推荐精度和实时性是一对 矛盾。大部分推荐技术在保证实时性要求的同时，是以牺牲推荐系统 的推荐质量为前提的。在提供实时推荐服务的同时，如何有效提高推 荐系统的推荐质量，需要做进一步深入的研究。 新型推荐系统的系统结构研究：当前大部分的推荐系统都只是一个单 一的工具，只能提供一种推荐模型。但由于电子商务，数字图书馆等 系统本身的复杂性，不同场合需要不同类型的推荐。因此，需要研究 新型推荐系统体系结构，收集多种类型的数据，提供多种推荐模型， 满足不同类型的推荐需求。 推荐结果解释研究：推荐系统为了说服用户，需要向用户解释推荐产 生的原因。需要进一步研究更加有效的方法向用户解释产生推荐的原 因，从而增加用户对推荐系统的信任度，说服用户听从推荐系统的推 荐。 1 2 本文的主要研究内容 针对于以上提出的不足，本文对电子商务推荐系统中推荐算法、推荐质量 等方面进行了有益的探索和研究。本文主要研究基于形式概念分析的协同推荐 系统，其主要研究成果如下： 1 ) 为了概念格能在协同推荐系统中得到更好的应用，本文提出了一种时间 复杂度低、实现简单的建格方法基于矩阵运算的建格方法。在矩阵运算的 基础上，本文提出了建格的算法b c l m o 。与一些传统的建格方法相比，b c l m o 明显提高了抽取形式概念的速度，大大降低了时间复杂度。 2 ) 针对协同推荐系统，本文提出了两个新的概念核心概念和核心概念 格，并把核心概念格应用到了协同推荐中。基于核心概念格的协同推荐算法不 仅避免了构建概念格的复杂性，而且事先过滤掉了那些根本不可能成为目标用 户“最近邻居 的用户，这样既减少了计算量，又降低了时间以及空间复杂度， 而且在一定程度上起到了去噪功能。后经实验证明这种方法既可以提高推荐效 第4 页 西华大学硕士学位论文 率，也可以提高推荐质量。 1 3 本文的内容安排 本文剩下的章节将组织如下： 第2 章：介绍了推荐系统中的各种经典推荐算法，并指出其各自的优缺点。 第3 章：详细介绍了形式概念分析在协同推荐系统中的应用。为了概念格 在协同推荐系统中能得到更好的应用，提出了一种新的基于矩阵运算的建格方 法b c l m o ，并将其时间复杂度与一些经典的建格算法进行对比，并用实验对 算法进行了模拟。 第4 章：提出了核心概念以及核心概念格的定义，并在此基础上提出了基 于核心概念格的协同推荐算法。 第5 章：对本文的工作进行了总结和展望。 第5 页 西华大学硕士学位论文 第2 章推荐系统 推荐系统的关键技术主要包括信息检索( i r ，i n f o r m a t i o nr e t r i e v a l ) 技术和信 息过滤( i f , i n f o r m a t i o nf i l t e r i n g ) 技术。与信息检索不同，信息过滤对动态信息进 行筛选，着重排除不希望得到的信息，带有即时性。虽然实现技术及其相似， 但信息检索和信息过滤所完成的任务完全不同 1 0 。推荐系统是针对不同的用 户提供个性化的产品和服务的应用系统。目前，常用的推荐技术有两类：基于 内容的推荐和基于协同过滤的推荐。本章将对推荐系统的研究内容以及个性化 技术进行介绍，并对两类推荐技术优缺点进行分析。 2 1 推荐系统的研究内容 推荐系统的研究内容和研究方向主要包括 9 】： 1 )推荐技术研究：设计准确、高效率的个性化推荐算法是个性化推荐系 统的核心问题。目前的推荐技术主要有协同过滤推荐、基于内容的推 荐。协同过滤推荐是个性化推荐中研究和应用最多的方法，被广泛的 应用于电子商务、数字图书馆、网页搜索、新闻过滤等。 2 )实时性研究：在大型推荐系统中，推荐系统的可扩展性能力和实时性 要求越来越难以保证。如何有效满足推荐系统的实时性要求得到了越 来越多的关注。 3 )推荐质量研究：在大型电子商务系统中，用户评分数据极端稀疏。用 户评分数据的极端稀疏性使得推荐系统无法产生有效的推荐，推荐系 统的推荐质量难以保证。 4 )多种数据多种技术的集成：当前大部分的推荐系统都只利用了一部分 可用的信息来产生推荐。随着研究的深入，新型推荐系统应该利用尽 可能多的信息，收集多种类型的数据，有效集成多种推荐技术，从而 提供更加有效的推荐服务。 5 )数据挖掘技术在推荐系统中的应用：推荐系统的基础是用户兴趣资料 第6 页 西华大学硕士学位论文 信息，如何尽可能获得更多的用户相关信息，并以合适的形式表示， 是进行个性化推荐的前提。随着研究的深入，各种数据挖掘技术( 主要 包括关联规则挖掘、序列模式挖掘、聚类分析、b a y e s i a n 分类等) 在推 荐系统中得到了广泛的应用。基于w e b 挖掘的推荐系统得到了越来越 多研究者的关注。 6 )用户隐私保护研究：由于推荐系统需要分析用户的购买习惯和兴趣爱 好，涉及到用户隐私问题，如何在提供推荐服务的同时有效保护用户 隐私值得作进一步研究。 7 )推荐系统可视化研究：推荐系统的目的是为用户提供服务，因此必须 为用户提供友好的可视化服务界面。这方面的研究主要包括推荐结果 可视化研究和推荐结果解释研究等方面的内容。 其中，过滤技术的研究是推荐技术研究的核心内容，过滤技术主要包括基 于内容的过滤和协同过滤两种。基于内容的过滤是信息检索领域的重要研究内 容 1 1 1 。基于内容过滤的推荐系统需要分析资源内容信息 1 2 1 ，根据用户兴趣建 立用户档案，然后根据资源内容与用户档案之间的相似性向用户提供推荐服务。 文 1 3 1 提出使用智能代理技术，利用智能代理获取用户兴趣信息，分析用户的 特定需求，提供推荐服务。贝叶斯概率模型、遗传算法以及其它机器学习技术 也被广泛应用于用户档案的建立和更新。 然而基于内容过滤的推荐技术也具有一定的局限n i l l 4 。主要表现在必须分 析资源的内容信息，因此对音乐、图像、视频等信息无能为力，无法分析信息 的质量，无法提供新颖的推荐。 针对上述问题，研究者提出了协同过滤推荐技术 6 。协同过滤，又称社会 过滤( s o c i a lf i l t e r i n g ) ，其基本思想十分直观：在日常生活中人们往往会根据 亲朋好友的推荐来做出一些选择( 购物、阅读、音乐) 。协同过滤系统就是 将这一思想运用到网络信息服务( 信息推荐) 中，基于其他用户对某一信息的评 价来向某一用户进行推荐。在早期的协同过滤推荐系统中，用户之间需要相互 了解对方的兴趣爱好。随着研究的深入，研究者提出了自动化协同过滤推荐技 术 1 5 1 。 推荐系统的推荐质量是推荐系统成功与否的关键。经典协同过滤推荐技术 第7 页 西华大学硕士学位论文 根据用户之间的相似性产生推荐结果。k a r y p i s 等人 1 6 】提出根据项之间的相似 性提供推荐服务，从而有效提高推荐质量。文 1 7 1 提出通过图搜索计算用户 最近邻居的优化算法。文 1 8 】对各种用户间相似性度量方法进行了分析，提出 了各种改进方法。用户评分数据的稀疏性是导致推荐系统推荐质量下降的主要 原因 1 9 】。文 2 0 中提出使用奇异值分解技术减少项空间的维数，从而有效改善 用户评分数据的稀疏性。文 2 0 中提出通过对稀疏数据的关联分析可以有效提 高推荐质量。 传统的协同过滤推荐技术根据用户显式评分产生推荐结果，用户使用不方 便，许多研究者提出可以通过w 曲挖掘技术获取用户隐式评分。文 2 1 提出通 过w 曲日志挖掘提供推荐服务。文 2 2 】提出通过u r l 聚类产生推荐的方法。各 种数据挖掘方法如关联规则挖掘技术，聚类挖掘技术被广泛的应用于w e b 日志 分析中以提高推荐精度。 2 2 基于内容的推荐系统 2 2 1 基于内容的推荐算法 基于内容的过滤源于信息检索，采用了与信息检索相似的技术。它是利用 信息内容( 如文本文档) 和用户兴趣的相似性来过滤信息。其推荐的基本思想是： 对每个用户都用一个称作用户兴趣文件( u s e rp r o f i l e ) 的数据结构来描述其爱好： 对每个项目的内容进行特征抽取( f e a t u r ee x t r a c t i o n ) ，形成特征向量( f e a t u r e v e c t o r ) ；当需要对某个用户进行推荐时，把该用户的用户兴趣文件同所有项目 的特征矩阵进行比较，得到二者的相似度，系统通过相似度推荐文档。有些系 统还收集用户的反馈信息以利于维护用户兴趣文件。 基于内容过滤的系统的关键在于待过滤文档的特征提取( 文档的表示) 、用 户兴趣文件的表示和相似度的计算。 第8 页 西华大学硕士学位论文 2 2 1 1 文档的表示 文档的表示通常采用向量空间模型。首先，我们假设文档中的字或词在确 定文档类别的作用是相互独立，则可用文档中出现的字或词的集合来代替文档， 这些字或词就是特征项。这样做虽然会丢失很多语义信息，但是它可使文档的 表示和处理形式化，在信息过滤过程中取得较好的效果。任意的特征项i ，因其 对文档表示的重要性不同而具有不同的权重m 。空间向量模型的基本思想是以 向量( ，w 2 ，k ) 来表示文档。权值w 有多种计算方法，常用的方法是倒置文 档频率( t f i d f ) 公式 2 3 】： i v ( td)：坠丝丝丝坠墼丝坠, 、面【( 1 + l 0 9 2 ( t f ( t ，d ) ) l 0 9 2 ( n n ，) 】2 其中，i v ( t ，d ) 为特征项t 在文档d 中的权重，t f ( t ，d ) 为特征项t 在文档d 中 出现的频率，n 为文档的总数，珂为在文档集中出现特征项t 的文档数。 2 2 1 2 用户模型 用户模型即是对用户建立的个性化模型，可以理解为用户的信息需要，用 户的兴趣领域或者主题，用户的访问方式，用户的思维方式等等，或者是他们 的结合，也可以是一些用户需要的特殊信息的相关背景，如被请求的知识的类 型或者用户背景知识等。 用户模型主要有这样几种类别：主题表示法，b o o k m a r k 表示法，关键词向 量，基于t f i d f 表示法，基于本体的加权向量法，语义网络法以及n g r a m s 法 等。 2 2 ：1 3 相似度的计算 对于向量空间模型来说，相似度计算的传统做法是计算两向量间的余弦相 似度( c o s i n es i m i l a r i t y ) ，具体的来说就是将用户u 的兴趣文件以及文档d 先转化 第9 页 西华大学硕士学位论文 成向量空间的形式 2 4 ，然后兴趣文档向量和文档d 向量的相似性可由如下的 余弦公式 2 5 1 计算得到： 跏印2 斋 其中厅表示用户u 的兴趣文件的向量，d 为表示文档d 的向量，i 历i 、l 孑i 为 两个向量的模，表示点积。系统把与用户兴趣文件相似度高的文档推荐给用 户。 2 2 2 基于内容的推荐算法的优缺点 一个纯粹的基于内容过滤的系统是忽略用户行为的，它只考虑信息和信息 之间的相似关系，因此它可以解决在协同过滤中出现的评分数据稀疏等问题。 其最大的优点在于建模和商品间的相似度可以脱机运行，因此它具有很快的推 荐响应时间。 但是其也存在一些缺陷 2 6 】。首先，基于内容的技术在碰到相同主题的文 档时，很难区分质量的高低。其次主要表现在必须分析资源的内容信息，因此 对音乐、图像、视频等信息无能为力。 2 3 协同过滤推荐系统 协同过滤推荐技术是应用最早并且最为成功的推荐技术之一。它一般采用 最邻近原则，根据用户的历史喜好信息计算用户之间的距离，然后利用用户的 最近邻居对商品评价的加权平均值来预测该用户对特定商品的喜好程度，最后 推荐系统根据这一喜好程度来向用户进行推荐。 近十年来，研究者提出了各种不同的推荐算法，如图2 1 所示 2 6 】 2 7 】，协 同过滤算法基本上可以分为m e m o r y b a s e d 协同过滤推荐算法和m o d e l b a s e d 协 同过滤推荐算法两类： 第1 0 页 西华大学硕士学位论文 协同过滤算 协划j 立滤纬注协川过瑟算法 麓擎懒器峰n o r t i 驯n g 矧麓擎恢燕排冽陶是 协；4 垃泷撼i l 协m 继治推ij | 协l 4 过连推il b a y e s i 嘲ii 岔麓嚣雾if 冀翟1 2 镎椎注| ii ! ；= 箨泣 l 推栉掉洼l i 荐铭洼| l 络推荐搏注 ”馅f i 门人”o 畅 f i g 2 1s o r to fc o l l a b o r a t i v ef i l t e ra l g o r i t h m 图2 1 协同过滤算法分类 基于内存的推荐算法：推荐算法利用整个用户项目数据库来产生推荐， 系统利用统计技术搜寻一组用户，称为邻居，他们与目标用户有一致的 历史( 例如：他们对不同的商品的评分相似，那么他们趋于买相似的商 品) 。一旦用户的邻居产生，系统可利用不同的算法去合并邻居的喜好产 生预测或为目标用户产生t o p - n 推荐，也就是与目标用户最有可能买的 前n 个商品。而在大型的电子商务系统中，用户数据库非常庞大，在整 个用户数据库产生推荐将非常耗时，从而使得整个推荐系统的实时性难 以保证，这也是基于内存的推荐算法面临的主要挑战。 基于模型的推荐算法：首先根据用户数据建立模型，推荐算法运行期间 将建立的模型调入内存。建立模型可利用不同的机器学习算法，如 b a y e s i a n 网络技术、聚类技术、基于规则方法等。在基于模型的推荐算 法中，建立的模型相对于原始数据集而言小很多，因而能有效缓解推荐 算法的实时性问题。模型相对于原始用户数据而言具有滞后效应，为了 保证模型的有效性，必须周期性的对模型进行更新。 2 3 1 基于用户的协同过滤推荐算法( u s e r - b a s e d ) 基于用户的协同过滤推荐算法是目前应用广泛且效率较高的一种个性化推 荐算法。该算法是协同过滤方法中最早提出的一种算法，所以一般情况下如果 第1 1 页 西华大学硕士学位论文 单独提协同过滤推荐，指的就是基于用户的协同过滤。 协同过滤推荐根据其他用户的观点产生对目标用户的推荐列表，它基于这 样一个假设：如果用户对一些项目的评分比较相似，则他们对其他项目的评分 也比较相似。它是使用统计技术搜索目标用户的若干最近邻居，然后根据最近 邻居对项目的评分预测目标用户对项目的评分，产生对应的推荐列表。 基于用户的协同过滤算法描述：算法采用一个研n 阶用户项目评分矩阵r 来表示用户输入的评分数据，使用统计技术寻找与目标用户有相同喜好的邻居， 然后根据目标用户的邻居的喜好产生向目标用户的推荐。 2 3 1 1 表示( r e p r e s e n t a ti o n ) 用户评分数据可以用一个m n 阶矩阵r ( 如表2 1 所示) 表示，m 行代表m 个用户，n 列表示n 个项目，第i 行第j 列的元素心表示用户i 对项目j 的评分 数值。评分可以是二进制的0 和1 来表示用户喜好( 喜欢不喜欢) 或购买状态( 已 购买未购买) ，也可以是用分等级表示用户对项目的喜好值( 例如：m o v i e l e n s 中用户对电影的评分值为从0 到5 之间的整数来表示用户的喜好程度) 。 2 3 1 2 最近邻居查询 表2 1 用户项目评分矩阵 t a b l e2 1u s e r s i t e m sr a t i n gm a t r i x 基于用户的协同过滤推荐系统的核心是为一个需要推荐服务的当前用户 寻找其最相似的“最近邻居”集( n e a r e s t n e i g h b o r ) ，即：对一个用户u ，要产生 第1 2 页 西华人学硕士学位论文 一个依相似度大小排序的“邻居”集合- m ，n 2 ，一u d ，u 不属于n ，从n l 到 n t 是按s i m ( u ，n k ) 从大到小排列。图2 2 演示了协同过滤中邻居的一种形成过程： 当前用户是中心点o ，它和其它用户之间的相似度被计算，如计算欧几里得距 离。图2 2 中与点o 为中心的k = 5 个最近用户被选择为邻居。 f i g 2 2t h ep r o c e s so f n e i g h b o r sf o r m a t i o n 图2 2 邻居的形成过程 最近邻居查询指整个基于用户的协同过滤推荐算法的核心部分，其效果和 效率很大程度上决定了该算法的效果和效率。最近邻居查询阶段实质上就是基 于用户的协同过滤推荐算法的模型建立阶段。 2 3 1 3 相似度计算 度量用户f 和用户之间相似性的方法如下：首先得到用户i 和用户，评分 过的所有项，然后通过不同的相似性度量方法计算用户i s t l 用户，之间的相似性。 度量用户间相似性的方法有多种，主要包括如下3 种方法 2 7 ：余弦相似性、 相关相似性以及修正的余弦相似性。 1 ) 余弦相似性( c o s i n e ) 用户评分看作为n 维项目空间上的向量，如果用户对项目没有进行评分， 则将用户对该项的评分设为0 ，用户间的相似性通过向量间的余弦夹角度量。 设用户i 和用户在，z 维项目空间上的评分分别表示为向量f ，则用户f 和 用户之间的相似性s i m ( i , 为： 第1 3 页 西华大学硕士学位论文 5 i m ( i ，) ：c 。s ( 7 ，了) ：兴 俐木 分子为两个用户评分向量的内积，分母为两个用户向量模的乘积。 2 ) 相关相似一 生( c o r r e l a t i o n ) 设用户i 和用户_ ，共同评分过的项集合用乃表示，则用户f 和用户之间的 相似性s i m ( i ，通过p e a r s o n 相关系数度量： ，、( r ，。一r ) ( 弓，。一尽，) 嘞( r ，。一r ) 2 。乃( 吩矗一吩) 2 凡。表示用户i 对项c 的评分，尺，和r ，分别表示用户i 和用户的平均评 分。 3 ) 修正的余弦相似性( a d j u s t e dc o s i n e ) 在余弦相似性度量方法中没有考虑不同用户的评分尺度问题，修正的余弦相 似性度量方法通过减去用户对项的平均评分改善上述缺陷，设用户f 和用户， 共同评分过的项集合用易表示，五和l j 分别表示用户i 和用户评分过的项集合， 则用户i 和用户之间的相似性s i m ( i , j , ) 为： 一、 。乇( 艮一r e ) ( 一r j ) c e ，fr l 。- - r ) 2 c , ；l i ( 尺加一只 风。表示用户i 对项c 的评分，r ，和尺，分别表示用户f 和用户的平均评分。 2 3 1 4 推荐产生 通过上面提出的相似性度量方法得到目标用户的最近邻居，下一步需要产 生相应的推荐。设用户u 的最近邻居集合用帆表示，则用户u 对项f 的预测 评分r ，可以通过用户“对最近邻居集合n n i 中项的评分得到，计算方法如下 2 0 】： 第1 4 页 西华大学硕士学位论文 气西鼍一 s i m ( u ，砂表示用户u 与用户n 之间的相似性，心r 表示用户n 对项i 的评分。 r 和尺。分别表示用户u 和用户n 对项的平均评分。 u s e r - b a s e d 协同过滤推荐算法的推荐过程如图2 3 所示。 援溯评分 揍捧 p i j o i ij l 砖瑷 j 缎援溯弹幼 赠i t 貅j | | p 赡荐： t 咿n 簇弼爱鹰z 矗；砌 尊派 辘i n 绶； f i g 2 3t h ep r o c e s so f u s e r - b a s e dc o l l a b o r a t i v ef i l t e ra l g o r i t h r a 图2 3u s e r - b a s e d 协同过滤算法过程 2 3 2 基于项目的协同过滤推荐算法( i t e m b a s e d ) 为了解决基于用户的协同过滤算法的数据稀疏性问题，s a r w a r 教授于2 0 0 1 年最早提出基于项目的协同过滤推荐算法 2 7 ，其算法的基本思想是：根据目 标用户已经评价过的项目与目标项目i 的相似性，选择k 个最相似的项目 f ，i 2 , 二埘，同时得到对应的相似度 s i l , s 口，- 二s 政) ，然后将目标用户对这k 个最 相似的项目的评分及这k 个最相似的项目与目标项目的相似度加权平均值作为 对目标项目的评分。 基于项目的协同过滤推荐算法主要有以下两部分组成： 第1 5 页 西华大学硕士学位论文 2 3 2 1 项目相似性计算 基于项目的协同过滤推荐算法的关键是计算项目间的相似度并选择最相似 的项目。计算项目i ，j 的相似性的基本思想是首先分离出共同评过分的项目的 用户，如图2 4 所示，并且应用一种相似性计算技术去决定相似度品。这种项 目相似性的计算方法在大体上与用户相似性的计算方法较为相似，详见文献 【2 7 】： 乒s ” _ jl r 潞我j 乞皤狰分孵j 颈弹纷域 绸隧 眺豹簿 瓤j 受。敞掰孙谬 叼 生糍鬻二：i 鬻鬈燃 到隧 _ 一一 一一川篡霆娄2 ：? 。够5 ”一 巫 矗)r r ri | _ f i g 2 4s e p a r a t i n gc o - r a t i n gi t e m sa n dc o m p u t i n gs i m i l a r i t y 图2 4 分离出被共同评分的项目和相似性计算 2 3 2 2 产生推荐 设目标项t i 的最近邻居集合用n n r l n n i ，n n 2 , ，n n k 表示，则用户u 对 项t i 的预测评分r 可以通过用户u 对最近邻居集合n n r l 中项的评分得到， 计算方法如下 2 0 ： 再鼍舞篙铲 s # n ( t i , 砂表示目标项刀与最近邻居刀之间的相似性，r 表示用户“对项 n 的评分。r 玎和r 。分别表示对项口和项拧的平均评分。通过上述方法预测 用户对所有未评分项的评分，然后选择预测评分最高的前若干个项作为推荐结 第1 6 页 西华大学硕士学位论文 果反馈给当前用户。 i t e m b a s e d 协同过滤推荐算法的推荐过程如图2 5 。 l2a 1 - lli + l r 1n f i g 2 5t h ep r o c e s so f p r e d i c t i n gf o rf i v en e i g h b o r s 图2 55 个邻居的预测产生过程 2 3 3 协同过滤推荐算法的优缺点 本小节主要从基于用户的协同推荐和基于项目的协同推荐这两个方面来分 析其各自的优缺点。 2 3 3 1 基于用户的协同推荐算法的优缺点 基于用户的协同过滤技术的推荐系统并不分析不同项目间的相似性，而是 学习顾客购买行为之间的相似性。由于它不依赖于项目的特征，因此它可以推 荐从表面上看上去不同