（管理科学与工程专业论文）基于兴趣度的推荐系统研究.pdf

西安建筑科技大学硕士学位论文 基于兴趣度的推荐系统研究 专业：管理科学与工程 姓名：靳峰 指导教师：黄光球教授 摘要 发达的市场经济使客户有了更多的选择余地，客户更容易流失，如何提高客户 忠诚度及保持客户，如何实现交叉销售等成为营销成败的一个关键问题，对电子商 务这种新的商务模式而言，更是如此。这就要求企业进行主动营销，发现客户的偏 好，分析客户的购买动机，从而更好地吸引客户的注意力。满足客户的喜好，使客 户感受到完全个性化的购物体验，推荐系统成为解决这一问题最有效的工具。 本文首先介绍了数据挖掘理论，它是兴趣度提出的前提条件，也是推荐系统赖 以实现的基础。为了发现客户的喜好，以便于更有针对性的向客户推荐商品，兴趣 度的分析就成为了本文的核心部分。文中将兴趣度从主、客观二方面多因素进行阐 述，同时对于常见的一些因素提出了计算方法，在此基础上提出了m - f i m 多因素 兴趣度建模，合理权衡构成有趣模式的多个因素中的各个指标，从而发现不同客户 对商品的不同偏好，以扩展兴趣度的适用范围。协同过滤是目前在推荐系统中应用 较为成功的推荐技术。但是，当系统规模( 客户数量、产品种类) 艮大时，推荐系统 中的协同过滤技术面临着严峻的挑战。为了迎接这种挑战，提高推荐系统的推荐质 量和实时性，基于兴趣度的协同过滤推荐的研究引入了兴趣度，用来修剪挖掘过程 中所产生的大量冗余规则，在很大程度上提高了推荐的效率和推荐的准确性；最后 对于挖掘算法进行了分析，引入兴趣度后的挖掘的算法提高了挖掘效率，降低了系 统的开销。 本论文独创性的将兴趣度评估问题归结为一个多方案的多目标决策问题，从中 得出高质量相似的客户兴趣度，使得商品推荐更加个i 生化。最后，对本文研究进行 了全面总结，指出了存在的不足，展望了未来进一步研究的方向。 关键词： 数据挖掘关联规则兴趣度协同过滤 论文类型：应用研究 两安建筑科技大学硕士学位论文 s t u d yo i lr e c o m m e n d e rs y s t e mb a s e do ni n t e r e s tm e a s u r e s p e c i a l t y ：m a n a g e m e n ts c i e n c ea n de n g i n e e r i n g n a m e ：j i nf e n g i n s t r u c t o r ：p r o f h u a n gg u a n g q i u a b s t r a c t i nt h ed e v e l o p e dm a r k e te 圮o n o m y , c u s t o m e rh a sm o r ec h o i c e s s oa st ol o s i n g c u s t o m e ri su s u a lt op r o p r i e t o r h o wt op r o m o t et h ec u s t o m e r sl o y a l i s ma n dh o l d i n g t h e m ，a n dh o wt or e a l i z ec m s s - m a r k e t i n gi s ak e yi nt h em a r k e t i n g , e s p e c i a l l yi n e c o m l n e r e em o d e i ti sn e c e s s a r yf o rp r o p r i e t o rt ou s ea c t i v em a r k e t i n gs t r a t e g y , m i n e c u s t o m e r st a s t e ，a n a l y s i sc u s t o m e r sp u r c h a s i n gm o t i v a t i o n , a c c o r d i n g l ya b s t r a c t i n g c u s t o m e r sa t t e n t i o ne f f e c t i v e l y , s a r i s l y i n gc u s t o m e r sf a v o r , a n dm a k et h ec u s t o m e r t a s t e sa b s o l u t ei n d i v i d u a ls h o p p i n ge x p e r i e n c e r e c o m m e n d e rs y s t e mb e c a m et h em o s t e r i e c l i v et 0 0 1 t h ep a p e ri n t r o d u c e sd a t a - m i n i n gt h e o r y , w h i c hi st h ec o n d i t i o no fi n t e r e s tm e a s u r e b r i n gf o r w a r da n dt h eb a s i cr e c o m m e n d e rs y s t e mc a r r i e so u t t os a f i s 母w i t hc m t o m e r s ， a st h es a m et i m e ，r e c o m m e n d sp r o d u c t st oc u a o m e mp e r t i n e n t l y , t h e r e f o r e ，i n t e r e s t m e 8 s u r ei saf o c u so fa t t e n t i o n t h ep a p e re x p a t i a t e sm u l t i f a c t o ma b o u to b j e c t i v ea n d s u b j e c t i v es i d e so ft h ei n t e r e s tm e a s u r e ，a n dt h e no f f e r ss o m em e t h o d s t oe v a l u a t et h e s e f a c t o r s t h em - f i mi sb a s e do nt h e s ef h c t o r s t h em o d e lp r o p e r l ym e a s u r ee a c h e v a l u a t i n gi n d e xi nt h em u l t i f a c t o r sa b o u ti n t e r e s tm e a s u r e ，t h e nf i n dv a r i o u sp e r s o n s t a s t et op r o d u c t ，i no r d e rt h a te x p a n dt h ei n t e r e s tm e a s u r e sa d a p t a b l es c a l e c o l l a b o r a t i v e f i l t e r i n gi sas u c c e s s f u lt e c h n o l o g yt h a ti si m p l e m e n t e di nr e c o m m e n d e rs y s t e m st o d a y b u t , w h e nt h es y s t e ms c a l e ( s u c ha st h en u m b e ro f c u s t o m e r so rt h et y p e so f p r o d u c t s ) i s v e r yl a r g e ，c o l l a b o r a t i v ef i l t e r i n gf a c e sg r e a tc h a l l e n g e s i no r d e rt om a k et h ep r o b l e m s s o l v e da n di m p r o v et h eq u a l i t ya n de f f i c i e n to fr e c o m m e n d e rs y s t e m s ，ar e c o m m e n d e r s y s t e mb a s e do nc o l l a b o r a t i v ef i l t e r i n ga n di n t e r e s tm e a s l l f ew a sb r o u g h tf o r w a r di nt h i s p a p e r t h em o d e lu s ei n t e r e s tm e a s u r ep r u n i n g t h el a r g en u m b e r so f r e d u n d a n tr o l e sf r o m d a t am i m n g ，t h er e c o m m e n de f f i c i e n c ya n da c c u r a c yi si m p r o v e di nal a r g ed e g r e e ，a tt h e s a i t l et i m e ，r e d u c e st h ec o m p u t e rs y s t e m sc o s t t n s p a p e rr e s o l v e st h ei n t e r e s tm e a s u r e e v a l u a t i n gp r o b l e mb yam u l t i - c r i t e r i o n 西安建筑科技大学硕士学位论文 d e c i s i o nm a k i n gp r o b l e m s ，w h i c hc a nb r i n gam o r es i m i l a rc u s t o m e r st a s t e ，a n dt h e n r e c o m m e n dp r o d u c t si n d i v i d u a l l y f i n a l l y , w es m n m a r i z eo nt h ep a p e r ，p o i n to u td e f e c t s a n dt h ed i r e c t i o n st h a tw i l lb ef u r t h e rs t u d i e di nt h ef u t u r e k e y w o r d s ：d a t am i n i n g ，a s s o c i a t i o nm l e ，i n t e r e s tm e a s u r e ，c o l l a b o r a t i v ef i l t e r i n g t h e s i s1 冲e ：a p p l i c a t i o ns t u d y 声明 y 8 4 1 7 0 3 本人郑重声明我所呈交的论文是我个人在导师指导下进行的研究工 作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他人已经发表或撰写过的研究成果，也不包含本人或其他 人在其它单位已申请学位或为其它用途使用过的成果。与我一同工作的同 志对本研究所做的所有贡献均己在论文中作了明确的说明并表示了致谢。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 论文作者签名： 铆哮 关于论文使用授权的说明 日期：喈氖名 本人完全了解西安建筑科技大学有关保留、使用学位论文的规定，即： 学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布 论文的全部或部分内容，可以采用影印、缩印或者其它复制手段保存论文。 ( 保密的论文在论文解密后应遵守此规定) 论文作者签名：酝本 导师签名 注：请将此页附在论文首页。 日期：h 心3 t l o 西安建筑科技大学硕士学位论文 1 1 课题研究的背景 1 绪论 随着近年来市场的变化，以利润为导向的营销已渐趋微，取而代之的是以客户 为导向的营销方式，为了提供更佳的顾客价值及满意度，将已知的利润来源做最有 效的控制以提高顾客忠诚度，将目标定位于与既有顾客发展更好的关系，相对于花 高成本取得新顾客来说，是获得利润更经济有效的方式；又真正掌握市场的致胜因 素，即满足顾客需求以创造企业竞争优势。 随着网络技术以及企业数字信息化程度的不断提高，电子商务的应用越来越受 到重视，电子商务网站已不再只单纯作为企业对外的一个门户，而成为了企业进行 经营的场所。如何在电子商务网站上有效地提高产品的吸引力，使企业获得尽可能 多的效益? 如何使客户面对电子商务网站提供的上万甚至上百万种产品时，更好地 选择到自己满意的商品? 推荐系统成为解决这一问题的最有效工具之一。 1 2 国内外研究现状及发展动态 早期的推荐系统提供的推荐信息是对全体客户提供相同的信息1 1 1 ，如商品销售 排行榜等，并不是对个体客户进行推荐，这类推荐系统在个性化推荐方面存在不足。 随着电子商务的发展，为适应实际商务中客户要求得到一对一的服务的需要，应用 于电子商务网站的推荐系统逐渐向能实时地为客户提供符合其个人需要的推荐服 务的方向发展，从而提高客户对自身网站的信任度，为企业的数字化发展和企业经 济效益的增长提供更广泛的发展前景。因此加强对电子商务推荐系统的研究具有非 常重要的现实意义。 1 2 1 推荐系统的表现形式 按照推荐系统的界面表现形式主要分为以下几种： ( 1 ) 浏览( b r o w s i n g ) ：客户提出对特定商品的查询要求，推荐系统根据查询要求 返回高质量的推荐。 西安建筑科技大学硕士学位论文 ( 2 ) 相似项( s i m i l a r i t e m ) ：推荐系统根据客户购物篮中的商品或客户感兴趣的商 品推荐类似的商品，为客户提供个性化的推荐。 ( 3 ) 电子邮件( e m a i l ) ：推荐系统通过电子邮件的方式通知客户可能感兴趣的商品 信息，使网站与客户保持联系，提高客户对网站的信任度，从而使增加对该网站的 访问量。 ( 4 ) 评论信息( t e x tc o m m e n t s ) ：推荐系统向客户提供其他客户对相应产品的评论 信息，客户根据他人对产品好坏的评价，来做出自己的判断。 ( 5 ) 等级评价( a v e r a g e r a t i n g ) ：推荐系统向客户提供其他客户对相应产品的等级 评价，而不是产品的评论信息，通过对等级评价的相应统计和分析，较直观地表示 出其他客户对产品的观点或看法，使客户易于接受该种推荐。 f 6 y f o p - n ：推荐系统根据客户的喜好向客户推荐最可能吸引他的n 件产品，一 方面可以把网站的浏览者转变为客户，另一方面帮助客户决定是否购买自己最初感 到犹豫不决的产品。 ( 7 ) 兴趣度推荐( o r d e r e ds e a r c hr e s u l t ) ：推荐系统列出所有的搜索结果，并将搜 索结果按照客户的兴趣度降序排列。 1 2 2 推荐系统的输入方式 按照推荐系统的输入方式可以分为以下几种： ( 1 ) 隐式浏览输人( i m p l i c i tn a v i g a t i o n ) ：客户的浏览行为作为推荐系统的输入但 客户并不知道这一点，如客户对网站网页的点击情况等； ( 2 ) 显式浏览输人( e x p l i c i tn a v i g a t i o n ) ：客户的浏览行为是有目的向推荐系统提 供自己的喜好，如对某产品的等级评价等； ( 3 ) 关键词和项目属性输入( k e y w o r d sa n di t e ma t t r i b u t e s ) ：客户输入关键词或项 目的有关属性以得到推荐系统有价值的推荐； ( 4 1 客户购买历史( p u r c h a s eh i s t o r y ) ：客户过去的购买记录。 1 2 3 推荐系统的产生条件 按推荐系统产生条件进行的分类： ( 1 ) 非个性化推荐( 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 ) ：推荐系统的推荐主要基 于其他客户对该产品的平均评价，这种推荐系统独立于客户，所有的客户得到的推 荐都是相同的，是非个性化的推荐。这种推荐的产生是自动的，客户参与很少，而 西安建筑科技大学硕：b 学位论文 且基于客户当前单个会话，对客户不予区分，是瞬时的。 ( 2 ) 基于产品属性的推荐( 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 ) ：推荐系统的推荐主 要基于产品的属性特征。该推荐系统由于需要客户输入他所需要的产品属性特征， 因此推荐往往是手工产生。基于产品属性的推荐也可以是瞬时的或个性化的，这取 诀子电二f 商务网站是否保存有客户偏好的记录。 ( 3 ) 相关性产品推荐( i t e m t o i t e mc o r r e l a t i o n ) ：推荐系统根据客户感兴趣的产品 推荐相关的产品，由子它不需要客户购买产品的历史纪录，只需了解客户当前选择 的产品，因此是瞬时的。如果推荐系统产生的推荐是基于客户长期较少改变的购买 模式，可以认为它是自动的，如果需要客户明确输入一些感兴趣的产品后产生推荐， 可以认为它是手工。 ( 4 ) 相关性客户推荐( p e o p l e - t o p e o p l e ) ：又称协同过滤，推荐系统根据客户与其 他已经购买了商品的客户之间的相关性进行推荐，此种推荐是自动产生的，而且是 持久的。例如m y c d n o w 用该技术完全自动地产生推荐，客户的喜好、想法通过 客户在c d n o w 商务网站建立自己个人音乐站点时的行为获得，不需要客户输入 任何信息，而且不同的客户所得的推荐是根据其个人的具体情况得到的，因此个性 化程度较高。 1 2 4 推荐系统采用的技术 电子商务推荐系统中目前己使用的技术主要有：贝时斯网络( b a y e s i a n n e t w o r k ) 、关联规则( a s s o c i a t i o nr u l e s ) 、聚类( c l u s t e r i n g ) 、h o r t i n g 图( h o r t i n gg r a p h ) 、 协同过滤技术( c o l l a b o r a t i v ef i l t e r i n g ) 等。 ( 1 ) 贝叶斯网络 贝叶斯网络是基于概率分析、图论的一种不确定性知识的表达和推理模型。从 直观上讲，在贝叶斯网络中，用每一个节点表示一个变量，即一个事件，各变量之 间的弧表示事件发生的直接因果关系。贝叶斯网络的建模目的是对所包含的定性知 识和定量知识进行结构上的描述，并为下一步推理提供依据。从原始数据中构造贝 叶斯网络模型，实际上就是对原始数据进行数据挖掘：即先找出晟符合原始数据的 定性的网络图关系，然后根据网络图中的因果关系，计算节点问的条件概率。 推荐系统中应用的贝叶斯网络技术利用训练集创建相应的模型，其中模型用决 策树表示，节点和边表示客户信息。模型的建立可以离线进行，即脱离系统的网络 运行环境，时间一般需要数小时或数天，而由此得到的模型可以非常小，对模型的 使用非常快。但随着客户的不断增多以及客户兴趣爱好的变化，即数据集的变化， 西安建筑科技大学硕士学位论文 贝叶斯网络的学习过程也要重新进行，因此这种方法适合客户的兴趣爱好变化比较 慢的场合。 ( 2 ) 关联规刚 在知识发现( k d d ) 领域，在电子商务中常用的数据挖掘技术就是在顾客购买的 不同商品集之间发现关联规则，产生推荐。关联规则挖掘的典型例子是购物篮分析。 该过程通过发现顾客放入其购物篮中不同商品之间的联系，分析顾客的购买习惯。 通过了解哪些商品频繁地被顾客同时购买，这种关联的发现可以帮助零售商制定营 销策略。关联规则的发现算法很多，如：a p r i o r i ，a p n o n t i d ，d h p ，f p - t r e e 等。 基于关联规则的推荐算法就是根据关联规则发现算法以及客户当前的购买行 为向客户产生推荐。该算法常被用于产生t o p - n 推荐。在关联规则推荐技术中，关 联规则的发现是最耗时的，也是算法的瓶颈，因此可以考虑离线进行。 f 3 ) 聚类 聚类就是将数据对象分组成为多个类或簇( c l u s t e r ) ，在同一个簇中的对象具有 较高的相似度，而不同簇中的对象差别较大。通过聚类，人们能够识别数据对象密 集的和稀疏的区域，因而发现全局的对象分布模式，以及数据属性之间的相互关系。 在商务上，聚类能帮助市场分析人员从客户信息库中发现不同的客户群，并且用购 买模式来刻画不同的客户群的特征。 为了便于寻找目标客户的相似客户，聚类模型首先将现有的客户按照定的方 法分成为多个类或簇，这样具有相似爱好的客户分配到相同的簇中，根据目标客户 所在簇的对某商品的评价得到目标客户对该商品的评价，有些算法将目标客户分配 到多个簇中，根据与所在簇的关系强度进行综合考虑计算。由于对大型数据集产生 最佳的聚类是不现实的，因此在实际应用过程中使用贪婪聚类生成的方法，这些方 法首先形成各个分类，每个分类常常仅包含一个任意选择的客户，然后反复地将剩 余客户分配到不同的簇中，这期间可能产生新的簇，也可能将不同的簇进行合并等。 由于聚类模型只是将目标客户与一定数量的簇进行比较而不是整个客户集，因 此在扩展性和实现性能上比传统的协同过滤技术略显优势，而且聚类计算可以离线 进行。但是在推荐质量上并不是很高，如当某客户处于一个聚类的边缘时，则对该 客户的推荐精度比较低。为了能够更好的给目标客户进行推荐，需要将其分配到与 他具有较高相似度的客户所在簇或类中，这样对簇的要求提高了，簇的数量也会有 大的增加，因此在线进行目标客户归类的代价反而大于协同过滤技术中寻找相似客 户的代价。 f 4 ) h o r t i n g 图 电子商务推荐系统中的h o r t i n g 图技术是一种基于图的方法，节点代表客户， 4 西安建筑科技大学硕士学位论文 边代表两个客户之间的相似度。在图中寻找近邻节点，然后综合近邻节点的观点形 成最后的推荐。h o r t i n g 图技术可以跳过中间节点寻找最近邻居，考虑了节点之间 的传递相似关系。 ( 5 ) 协同过滤 协同过滤技术是推荐系统技术中应用最早和最为成功的技术之一。它一般采用 最近邻技术，利用客户的历史喜好信息计算客户之间的距离，然后利用目标客户的 最近邻居对商品评价的加权平均值来预测他对特定项( 商品) 的喜好程度，系统从而 根据这一喜好程度来对目标客户进行推荐。 它分析“客户一客户”关系，根据客户兴趣的相似性来推荐商品，把和客户相 似的其他客户的意见提供给特定客户，无需考虑商品的表示形式，把客户对商品的 评分向量作为客户兴趣的表示形式。其优点是能为客户发现新的感兴趣的商品，但 是面临两方面挑战：数据的高维稀疏性。一般情况下，信息资源的数量是巨大的， 而客户对信息对象的评价是极其少数的。数据的高维稀疏性会导致推荐质量不高。 算法可扩展性不好。随着系统内客户和商品的不断增加，推荐算法的计算量非常 大，很难满足推荐系统的实时性要求。 1 2 5 现有推荐系统分析 现在许多信息推荐服务系统以及相关技术可以帮助客户在w w w 上快速定位、 检索感兴趣的信息。目前已出现了一些相关的研究，主要有： ( 1 ) w e b w a t c h e r 系统1 2 ，3 】：采用跟踪客户浏览w e b 站点的行为或者访问路径方 法，学习客户的访问模式，将客户可能感兴趣的w e b 页在线推荐给客户。 ( 2 ) s i t e h e l p e r 系统【4 】：采用分析每一个客户已经访问的w e b 页，学习客户的兴 趣模式，从客户感兴趣的w e b 中提取关键词，然后，提供给客户，系统基于客户 相关反馈技术为客户推荐其它的相关w e b 页。 ( 3 ) f o o t p r h a t 系统【5 1 ：利用可视化技术，为客户提供w e b 站点被频繁访问的路 径。 ( 4 ) a v a n t i 系统1 6 】：利用自适应规则为每组相同的客户访问模式实现定制化。 基于数据挖掘的推荐系统是当前的一个研究热点。主要的研究有： ( 1 ) s c h e c h t e r 等人【”根据客户的访问路径模式预测客户未来可能的h r r p 请求， 让代理服务器执行预取操作，将相关w e b 页存入其c a c h e 中，以加快访问速度。 ( 2 ) c o o l e y d e 等人1 8 i 和b u c h n e r | 9 等人利用数据挖掘技术从访问的l o g 文件中提 西安建筑科技大学硕士学位论文 取客户的访问模式，用于市场决策和智能推荐服务。 ( 3 ) n a s r a o u i “叫等人采用聚类客户访问模式方法，预测客户未来的访问行为。 目前已经存在很多推荐系统，但是仍然存在一些问题，主要包括： ( 1 ) 推荐系统针对的是注册客户，较少考虑非注册客户的信息推荐。 ( 2 ) 推荐系统对新客户和访问站点较少的客户的信息推荐考虑不够，因为新客户 和浏览站点较少的客户被系统收集的客户信息较少，采用某些推荐算法并不合适。 ( 3 ) 推荐系统没有考虑客户是否有新颖信息需求的偏好。 数据挖掘技术应运而生，并得以蓬勃发展，越来越显示其强大的生命力，让人 们有能力最终认识数据的真正价值，即真正认识蕴藏在数据中的信息和知识i 】1 - m 。 k d d 是从大量数据中提取出可信的、新颖的、有效的并能被人理解的模式的 处理过程。 图1 2u f a y y a d 提出的k d d 处理过程 通过对以上技术的分析可以看出，随着信息资源的日益丰富，以上技术均面临 着一定的困境，协同过滤的出现为进一步提高信息服务质量提烘了一个新的思路， 协同过滤技术( c o l l a b o r a t i v ef i l t e r i n g ) ，它通过构造客户对商品( 项) 的偏好数据集来 实现，而且它并不依赖于对这些商品必须有文本描述，成为目前推荐系统技术中应 用最为成功的技术之一。随着协同过滤技术的不断发展以及在推荐系统中的广泛应 用，该技术逐渐向通过建立客户行为的客户偏好模式从而自动为客户进行推荐的方 向发展。 模式兴趣度的度量包括客观和主观两个方面b 】，一些学者对此进行了深人研 究。h i l d e r m a n 和h a m i l t o n 应用客观兴趣度度量方法对所发现的关联规则进行评估， 并提出了一个两步骤法对发现的关联规则( 模式) 进行排序，筛选出一个满足客观度 量的简单模式集【l ”。l u d w i g 等人专门研究兴趣度的一个重要方面一新颖性 ( n o v e l t y ) 。运用先验模型来度量规则的新颖性，并将该模型用于医学分析中【1 5 】。 西安建筑科技大学硕士学位论文 p a d m a n a b h a n 和t t t z h i l i n 基于奇异性( u n e x p e c t e d n e s s ) 来定义规则的兴趣度。模型的 奇异性是由客户定义的一组信念决定，包括软信念( s o f tb e l i e f s ) 和硬信念( h a r d b e l i e f s ) 【l “。新颖性和奇异性其实都是衡量模式对客户信念的改变程度，只是表示 不同。s i l b e r s c h a t z 和t u z h i l i n 还研究了模式的主观兴趣度度量方法，以模式的可用 性和奇异性度量模式的兴趣度，并建立了数据挖掘信念系统，为进一步研究模式的 主观兴趣度度量方法提供了一个理论框架 1 ”。h i l d e m a a n 和h a m i l t o n 对兴趣度度量 方法进行了综述，共列出了1 7 种度量模式兴趣度的准则【1 8 】。 以上这些工作为模式兴趣度评估研究提供了基础，但兴趣度的度量包括主观和 客观两个方面，目前许多研究工作都还只侧重一个方面或某一点1 啦o l 。另外，尽管 提出了许多衡量模式兴趣度的准则，但如何综合这些准则来最终确定模式的优劣， 进而实现自动发现客户感兴趣模式，也是一个急待解决的问题。 1 3 论文的主要研究内容 兴趣度的分析将是本文讨论的重点，本文将从其概念出发，逐步扩展探讨其内 在的影响因素以及如何确定不同因素所占的权重，更加全面的考虑不同因素对于兴 趣度的影响，最后将模式兴趣度应用到商品推荐领域。 本文独创性的将数据挖掘结果的兴趣度评估问题归结为一个多方案的多目标 决策问题，从中得出更加相似的客户兴趣度，从而使得商品推荐更加有针对性。 本文研究的目标是关联规则中兴趣度的提取、度量及应用领域。 ( 1 ) 针对关联规则判定标准的存在的一些不足，引入了兴趣度的概念，论述了关 联规则有趣性问题，主要从主观和客观两个方面进行评测，并给出了较为科学的兴 趣度定义。 ( 2 ) 对兴趣度的主客观度量分别加以分析，并提出了m - f i m 的数据挖掘模型， 对兴趣度进行权重的确定，并用兴趣度标准判定得出客户感兴趣的定量关联规则。 为了结合客户的个人偏好和背景知识的影响，本文引入协同过滤技术来确定主观兴 趣度对客观兴趣度的的权值更新。 ( 3 ) 将兴趣度理论与协同过滤技术应用于商品推荐系统当中，提出了基于兴趣度 的协同过滤推荐模型，在兴趣度分析基础之上引入协同过滤的推荐，极大的提高了 推荐的效率和推荐的准确性。 本文对数据挖掘中兴趣度理论及商品推荐领域进行了探索。第二章中首先就兴 趣度提出的理论前提进行了阐述，若在此基础上提出了m f i m 模型。第三章中就 m f m 模型中的客户偏好与背景知识的确定引入了协同过滤技术。第四章将基于 西安建筑科技大学硕士学位论文 兴趣度的协同过滤应用于商品推荐当中，并分析了其现实意义。第五章节简单说明 引入兴趣度对于经典挖掘算法的效率改进作用。最后对本文的工作进行总结和展 望。 西安建筑科技大学硕士学位论文 2 兴趣度模型分析与扩展 于1 9 9 3 年提出的关联规则是当前数据挖掘研究的主要模式之- - i “】，它用于确 定数据集中不同领域或属性之间的联系，找出可信的、有价值的多个属性之间的依 赖关系。关联规则的挖掘目标是从数据集中找出形如“由于某些事件发生而引起另 外一些事件的发生”的规则。例如，通过对学生成绩数据库的分析，我们可能发现 “程序设计成绩为优的同学，数据结构成绩也是优”的可能性是7 8 。因此， 可以通过强化程序设计的教学来改善数据结构的教学成果。 本章主要介绍关联规则挖掘技术的一些发展情况，包括关联规则的定义、基本 算法和研究现状等，这将为兴趣度的论证提供基础。 2 1 兴趣度模型建立的前提条件 下面从数据挖掘的角度出发，给出关联规则的形式化定义 2 2 1 。 定义2 1 关联规则( a s s o c i a t i o nr u l e s ) 设卢( i l ，f 2 ，f m ) 为项集，其中钛1 对脚) 称为项，0 f l ，t 2 ，q 为交易集，表示每笔交易的集合，其中自互i ( 1 l 曲。其中关联规则是形如式2 1 ， 其蕴含式为： x j y ( 2 1 ) 其中，x c _ l ，y g i ，并且x n y = a 。在这里，d 相当于知识发现定义中的数据 集f ，关联规则相当于模式e 。 为了对关联规则的价值进行评判，我们一般还需要使用两个参数，即支持度 ( s u p p o a ) 和置信度( c o n f i d e n c e ) 。 定义2 2 交易集口的投影： 给定项集j 和交易集d ，交易集d 在项集z ，上的投影，如式2 2 所示： d j = 啦d “x 母 ( 2 2 ) 定义2 ，3 关联规见| l 的支持度( s u p p o r t ) ： 给定交易集d 和d 和的关联规则j j y ，关联规则的支持度，如式2 3 所示： 叫硼叫删) = 斜 ( 2 3 ) 其值域为坛。这个支持度的定义是一个相对的定义。在实际的运用中，往往考虑 9 西安建筑科技大学硕士学位论文 的是支持度的绝对定义，即同时包含x 和y 的交易的数量i d 。i ，我们称其为频繁 度。 定义2 4 关联规则的置信度( c o n f i d e n c e ) ： 给定交易集d 和d 和的关联规则x j y ，关联规则的置信度，如式2 4 所示： “抽y ) _ 矧 ( 2 4 ) 其值域为 磊。显然由式2 3 和2 4 可以得到 皑y ) = 等 ( 2 5 ) s i 爿1 支持度和可信分别对应于知识发现定义中的u ( e ，乃和c ( e ，d 。从语义的角 度来看，规则的置信度表示这条规则的正确程度；支持度表示用这条规则可以推出 百分之几的目标，即这一原因对于这一结果的重要程度，可被接受理解的程度。 例2 1 ：设j = ( 咖啡，奶粉) ，在有1 0 0 条原始记录集d 中有2 5 条记录显示 购买了咖啡，而这2 5 条记录中又有2 0 条显示购买了奶粉，则关联规则“买咖啡j 买奶粉”的支持度s = 2 0 1 0 0 = 0 2 ，置信度c = 2 0 2 5 = 0 8 。 我们一般对支持度和置信度特别显著的关联规则感兴趣，要求数据挖掘系统所 生成的规则的支持度和置信度都不小于给定的闽值，这样的关联规则称为强关联规 则。 定义2 5 强关联规则，最小支持度，最小置信度： 给定交易集d 和d 上的关联规则x j y ，m i n c o n f e m c ，m i n s u p m s ，当且仅 当c i m i n c o n f a s l m i n s u p 时，称z j 】，为强关联规则，其中，m i n c o n f 为最小置信 度，m i n s u p 为最小支持度。 2 1 1 兴趣度引入的意义 在数据挖掘系统中，为了获得客户感兴趣的规则，人们以支持度和置信度作为 产生强关联规则的评价标准，但是，在实际应用中，基于这一体系评价方法，逐渐 暴露出它的局限性。如果人们把支持度的阈值设得足够低，以避免不丢失任何有意 义的规则，但是，在产生的规则中，有可能存在一些对客户不具有实际应用价值的 规则，而且，可能会带来计算效率的低下：如果阈值设得过高，就有可能丢失对客 户有价值的规则。如何评价这些规则，以剪切对于客户不具有应用价值的规则，目 前，也引起了一些学者的研究兴趣。有些学者在支持度和信任度的框架下，引入了 另一评价阈值兴趣度，用来修剪无用的规则，即避免生成“干扰住”的关联规则。 西安建筑科技大学硕士学位论文 下面先介绍关联规则的评价标准，然后介绍兴趣度的基本类型。 兴趣度是表征客户对规则的关注程度的度量，这种度量是客户对挖掘出的知识 的新颖性、可用性和可理解性的综合考虑。客户对不同挖掘任务和应用环境，所挖 掘出的规则的关注程度是不同的。如何从大量的规则中筛选出客户感兴趣的规则， 目前，是数据挖掘所研究的主要任务之一。客户对规则的兴趣度包括主观兴趣度和 客观兴趣度。 2 1 2 兴趣度相关的挖掘算法 关联规则的挖掘通常分解为两个也问题来解决： ( 1 ) 在交易集d 中找出所有项集的集合l = l = 啦i a f a a s ( t ) m i n s u p ， 这时我们称i e l 为频繁项集，其中包括的项的个数为该项集的长度或大小。 ( 2 ) v t l ，? cz ，如果s ( 1 ) s ( 1 ) m i n c o n f , 就生成强关联规则，j ( ，一，) 。 由于第二个子问题的求解比较简单，大量的研究工作集中在第一个子问题上。 因为第一个子问题的求解手段和策略的不同就产生了不同的关联规则的挖掘算法。 这二个算法的区别在于它们对结果空间的构造方式不同，一个是基于广度优先的思 想，采取自底向上的逐层构造方式的a p r i o r i 算法，另一个是以数据压缩为基础， 采取转换处理对象方式的f p g r o w t h 算法。 ( 1 ) a p t s o r i 算法幽】 a p n o n 算法是由r a g r a w a l 等人在1 9 9 4 年提出的，建立于广度优先搜索思想 上的算法。它具有很大的影响力。目前大多数算法都是以a p r i o r i 算法为基础进行 优化或扩展的。 a 州嘶算法的基本思想是通过对数据库d 的多次扫描来发现所有的频繁项集。 在第是次扫箍中只考虑具有圊一长度k 的所有项集。在第一趟扫描中，& p r i o r i 算法 计算j 中所有单个项的支持度，生成所有长度为】的频繁项集。在后续的扫描中， 首先以前一次所发现的所有频繁项集为基础，生成所有新的候选项集( c a n d i d a t e i t e m s e t s ) ，即潜在的频繁项集，然后扫描数据库d ，计算这些候选项集的支持度， 最后确定候选项集中哪一些真正成为频繁项集。重复上述过程，直到再也发现不了 新的频繁项集。算法高效的关键在于生成较小的候选项集，也就是尽可畿不生成和 计算那些不可能成为频繁项集的候选项集。 ( 2 ) f p g r o w t h 算法【2 4 】 f p _ g r o w t h 算法是一种不产生候选频繁项集的算法，它采取一种分治策略：将 提供频繁项集的数据库压缩到一棵频繁模式树( f p 一树) ，但仍保留项集关联信息： 西安建筑科技大学硕士学位论文 然后，将这种压缩后的数据库分成一组条件数据库，每个条件数据库关联一个频繁 项，并对该数据库进行挖掘。 f p 一树的第一条路径代表一个交易，节点在路径中出现的顺序按节点所代表的 项在交易集中出现的次数排序。为方便树遍历，创建个项头表，使得每个项通过 一个节点链指向它在树中的出现。 扫描所有的交易之后得到一棵f p 树，数据库频繁模式的挖掘问题就转换成挖 掘f p 树问题。 f p 一树挖掘如下进行：由长度为1 的频繁模式开始，构造它的条件模式基。然 后，构造它的条件f p 树，并递归地在该树上进行挖掘。模式增长通过后缀模式与 条件f p 一树产生的频繁模式连接实现。 2 1 3 兴趣度模型的应用领域 关联规则分析最初始的应用就是购物篮分析，但从关联规则的一般定义可知， 它可以从大量的数据中找寻数据之间的有趣关联或相关联系。因此，关联分析的思 想被逐步应用到其它各个领域，如空间关联分析、多媒体数据分析、生物医学数据 分析等。 2 2 兴趣度挖掘模型 自从关联规则技术被提出后，就不断有人指出关联规则的局限性，为了避免或 者减少生成的模式中没有意义的规则，人们引入各种新的阈值以加强对关联规则进 行完善。其中，兴趣度的提出是一个比较瞩目的观点，同时对于兴趣度的各种定义 也颇多。 2 2 - 1 兴趣度相关定义 r s r i k a n t 等首先给出感兴趣的规贝, u t 2 5 】的定义，随后他们又对此进行了改进。 s ，b r i n 等把事件依赖性的统计定义扩展到兴趣度上来，后来又把a ，b 的信任度 定义为户( 4 ) _ p ( 、b ) p ( a ，艿) ，它是蕴涵性的度量。k l e m e t t i n e n 等定义了模板 ( t e m p l a t e ) 的概念【2 ”。客户使用它来确定哪些规则是令人感兴趣的，哪些则不是：如 果一条规则匹配一个包含的模板，则是令人感兴趣的，如果一条规则匹配一个限制 模板，则被认为是缺乏兴趣的。其它的还有收集强度等。 西安建筑科技大学硕士学位论文 文2 8 忡提出了一个基于差异思想的兴趣度定义，并提出了改进的关联规则的 定义以及使用了兴趣度以后对挖掘算法的修改等。但对于引入兴趣度以后的挖掘算 法并没有考虑其效率的问题，而将反而规则局限于对规则提取还有待进一步商榷。 在对关联规则定义的基础上，可以把关联规则和兴趣度的形式定义如下： 定义2 1 关联规则： 设i = i 1 ) i z ，i 。) 为项集，i s ( 1 ，m ) 为正项，相应的i j ( 1 s j 茎m ) 为负项， d = f 1 ，t 2 ，岛) 为交易集，其中 量i ( 1 f n ) 为交易。关联规则是一个形如式 2 6 p 1a a p # p z “a a p # j 譬1 一a q ia q + l a q _ ( 2 6 ) 的蕴含式，其中p ，q ，硼这n , 1 j m ) ， b ，p 2 ，p 。) n q 1 ，9 2 ，q 。 = g 。 令x = 崩，p l ，p t 。，p 。) ，y = ( 9 1 ，q ，g 。，q 。) ，有关联规则的支持 度s = s ( 船) = i 胛1 俐和置信度为c ：l 胛l i x i = s ( 船) s ( x ) 。我们称x 为规则的 左部，y 为规则的右部。 弓i 入负项不仅仅是知识表示手段上的如强，而且是对关联规则原有定义的完 善。 定义2 2 兴趣度( i n t e r e s tm e a s u r e ) 给定交易集d ，d 上的关联规则x j y 的兴趣度。如式2 7 ： j 一= 磊c 石- s ( y 两) ( 2 7 ) 1 ”m a x 虹s ( y ) ”v 其域值为m 。 定义2 2 是由规则的支持度和置信度而产生的。分母i - 的m a x c ，j ( y ) ) 只是一个 标准化因子，使得i 。i l 时，称x ；y 为强关 联规则。其中，s ，c ，i 分别为关联规则的支持度、置信度和兴趣度。 西安建筑科技大学硕士学位论文 在完成对原有定义的改进后，对于挖掘算法面临如何充分利用兴趣度判定关联 规则的价值。一般做法是在关联规则经过