基于关联规则的推荐系统研究.pdf

《基于关联规则的推荐系统研究.pdf》由会员分享，可在线阅读，更多相关《基于关联规则的推荐系统研究.pdf（66页珍藏版）》请在三一文库上搜索。

1、西安电子科技大学 硕士学位论文 基于关联规则的推荐系统研究 姓名：陈静 申请学位级别：硕士 专业：情报学 指导教师：丁振国 20030101 摘要 摘要 本文针对如何实现个性化的“相关产品推荐”这需求展开研究，引入了数 据挖掘中的关联规则技术为基本的实现手段，并在此基础上设计并实现了一套完 整的电子购物中的相关产品推荐系统A R e c o m ( A s s o c i a t i o nR u l e s R e c o m m e n d a t i o nS y s t e m ) 。 关联规则的算法研究部分，分为频繁项集生成和规则提取两步。针对直接决 定整体效率的频繁项集生成：本文研

2、究了3 种典型算法，并分别编程实现，比较 分析了它们在不同规模数据集上的性能特点，同时针对性能较好的F P 一增长算法 在内存上的瓶颈，本文提出了一种改进的思路F p r o j e c t 。关于规则提取：本文 研究了多种方法，并分析了其中负相关产生虚假规则这一弊端，针对这一问题， 提出了支持度一置信度一兴趣度相结合的框架。 在上述算法模型的基础上，设计并实现了一套相关产品推荐系统A R e c o m ， 包括系统中W e b 服务器、数据库服务器、和推荐服务器的功能说明及核心技术， 最后通过个实例证明了h R e c o m 具有较高的效率，较准确的推荐能力。 本论文得到总装备部“交互式

3、在线信息服务技术研究”的支持。 关键字：关联规则相关推荐频繁项集规则提取 A b s t r a c t A b s t r a c t H o wt or e a l i z et h ec h a r a c t e r i s t i cc o r r e l a t e d p r o d u c tr e c o m m e n d a t i o ni sr e g a r d e d a st h em a i nr e s e a r c h t a r g e t i nt h i s p a p e r Ac o m p l e t es y s t e m - - - -

4、 A R e c o m o f c o r r e l a t e d - p r o d u c t r e c o m m e n d a t i o ni nt h ef i e l do fE c o n l r r l e r c ei sd e s i g n e da n d r e a l i z e db a s e do nt h ea s s o c i a t i o nr u l e st e c h n o l o g yi nd a t a m i n i n g I nt h i sp a p e rt h ea l g o r i t h mo fa s s

5、 o c i a t i o nr u l e si n c l u d e st h ec r e a t i o no f f r e q u e n t i t e m s e ta n dt h er u l e se x t r a c t i o n A st ot h ec r e a t i o no ff r e q u e n ti t e m s e t ，t h i sp a p e r r e s e a r c h e st h r e es p e c i a la l g o r i t h m sa n dr e a l i z e sb yp r o g r

6、 a m m i n g A tt h es a r l l et i m e t h i sp a p e ra l s oa n a l y z e st h ed i f f e r e n t i aa m o n gt h e mi nd i f f e r e n td a t as i z ea n db r i n g s f o r w a r dak i n do fa d v a n c e d i d e a - - F p m j e c t a st ot h em e m o r yb o t t l e n e c ko f F P g r o w t h a

7、l g o r i t h m A st ot h er u l e se x t r a c t i o n ，d i f f e r e n tk i n d so fa l g o r i t h m sa r eb r o u g h t f o r t h B ya n a l y z i n gt h ed e f e c to fp r o d u c i n gm i s d i r e c t - r u l eb yn e g a t i v ec o r r e l a t i o n ，t h i s p a p e rb r i n g sf o r w a r dt

8、 h ef r a m et h a ti n t e g r a t e ss u p p o r td e g r e e ，c o n f i d e n c ed e g r e ea n d i n t e r e s td e g r e e a l t o g e t h e r B a s e do nt h ea b o v e - m e n t i o n e da l g o r i t h mm o d e l ，t h i sp a p e r d e s i g n sa n dr e a l i z e s o n e c o m p l e t es y s

9、t e m o f c o r r e l a t e d - p r o d u c tr e c o m m e n d a t i o n - - A R e c o m ，w h i c h i n c l u d e st h ef u n c t i o na n dc o r et e c h n o l o g yo fW 幽S e r v e r , D a t a - b a s eS e v e ra n d R e c o m m e n d a t i o nS e r v e r I nt h el a s tp a r t ，t h ep a p e rp r o

10、 v e st h a tt h eA R e c o m s y s t e m h a se f f i c i e n ta n da c c u r a t er e c o m m e n d a t i o n a b i f i t y T h ep a p e ri s s u p p o s e db yo n e o ft h et e c h n i c a lb a s i s p r o j e c t s o fG e n e r a l E q u i p m e n tD 印a r t m e n to f L A Mw i t ht h en a m e T

11、e c h n i c a lR e a s e a r c ho nI n t e r a c t i v e O n l i n eI n f o r m a t i o nS e r v i c e ” K e y w o r d ：A s s o c i a t i o nr u l e s c o r r e l a t e d p r o d u c tr e c o m m e n d a t i o nf r e q u e n t i t e m s e tr u l e se x t r a c t i o n 声明 创新性声明 本人声明所呈交的论文是我个人在导师的指导下进

12、行的研究工作及所取得的研 究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已发表或撰写的研究成果；也不包含为获得西安电子科技大学或其他教 育机构的学位或证书而使用过的材料。与我一同工作的同志所做的任何贡献均已在 论文中做了说明并表示了谢意。 本人签名：，啦 日期：邀! 盎 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：学校有 权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全部或部分 内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文在解密后 遵守此规定) 本人签名：毽蛰 导师 日期：丝堕

13、! ：篁 日期：垄堕。! - 第一章绪论 第一章绪论 1 1 引言 互联网对传统企业带来的最突出机会在于营销方式的变革。今天，稍有网络 意识的传统企业都利用企业网站和客户建立关系，即电子商务。电子商务本身就 是经营方式创新的结果。随着电子商务的发展，其本身也有个创新的问题。那种 千篇一律的电子商务模式和忽视客户需求差异眭的服务显然已经不能适应信息时 代的需求。电子商务个性化是集中体现差异化竞争优势的最好方式，是企业创造 竞争优势的重要手段。 本文论述的电子商务推荐系统即是商务个性化服务 1 4 , 1 5 的一个重要组成部 分。它是根据顾客已有的购买情况，推测将要进行的消费行为，进而为每位顾客

14、 提供个性化的商品推荐，模拟销售人员帮助客户完成购买过程。 电子商务推荐系统 啦l 的表现形式有多种：热销商品推荐、新品推荐、相关推 荐、同用户群同兴趣推荐等。本文在研究多种推荐技术的基础上，根据系统需求， 选择了技术难度较高的“相关产品推荐”作为重点研究对象。相关产品推荐要求 系统从大量的历史销售数据中进行学习，找出若干商品项之间的相关程度，提炼 出规则，为后来的产品推荐提供依据。比如：系统通过大量的学习发现买面包的 顾客通常也会买黄油，那么当下一个顾客购买面包时，就可以推荐黄油，为顾客 提供个性化服务。在这里需要指出的是系统的自动学习过程，并把学习的结果以 规则的形式表现出来，这就需要用到

15、数据挖掘的技术。本文引入了数据挖掘中的 关联规则技术，关联规则能够很好的解决相关产品推荐的问题，为客户的个性化 需求提供了技术上的解决方案。 1 2 目前研究现状 以电子商务为基础，以数据挖掘为手段，以个性化服务为特色的网络经济，在 国内外已渐成潮流鸭成为推动电子商务发展的加速器。如今，一些开展了电子 商务的企业纷纷打出了个性化服务这张王牌。 在国外，利用个性化推荐推动企业电子商务开展的事例不胜枚举。如A m a z o n ， C D N O W ，D r u g s t o r e t o m ，e B a y ，M o v i e F i n d e r c o m ，R e e l c

16、 o m 等都有各具特色的 个性化推荐服务。以大牌电子商务网站A m a z o n e o m 为例，分析它的各种个性化推 荐服务。 和许多电子商务网站一样，A m a z o n c o m 对于每一本书都有一个展示其详细信 基于关联规则的推荐系统研究 息的页面。在这个页面中含有两种类型的推荐列表：第一，买这本书的顾客经常 还会购买的其它书：第二。买作者A 的作品的顾客还经常会买作者B 的作品。具 体的服务形式如下： ( 1 ) 你的推荐：A m a z o n 鼓励读者对所购买的书做盔接反馈。读者对这本书从 “喜欢”到“讨厌”五个等级打分，通过对样本书的打分，推荐系统可以给顾客 提供他们

17、可能感兴趣的图书。 ( 2 ) 眼睛：A m a z o n 的这个特征可以用自动e m a i l 的方式通知读者A i i l a z o n 最 额入库的书目信息。读者可以用作者、标题、主题内容、I S B N 、出版社为关键字， 迸行布尔运算检索。 ( 3 ) 书店礼物：在这个系统中，读者只要选择一个他们想获得推荐建议的类 别，A f l l a z o n 的编辑将展示给读者一个合适的推荐列表。 ( 4 ) 顾客评价：顾客可以看到其他读者对这本书的文本评价。顾客可以根据 这些评价决定他们是否购买。而且，顾客可以对这些评价打分，并最终显示所有 顾客打分的综合结果。 在国内，个性化推荐也

18、在电子商务领域初见倪端。很多企韭已经十分注重逶过 这种方式来提高电子商务的竞争力。国内的新浪商城、网易商城、和S o h u 在线购 物，也都有适合自身弼鼓特色的推荐系统。 由上可见，个性化的推荐服务在改善顾客关系、培养顾客忠诚度以及增加网上 镑售方嚣具有明显鼹效果。毽是妞霹为顾客提供更加赃近生活的在线服务，如秘 为每个顾客提供独特的商品信息，如何使数据挖掘算法更高效的应用到这个领域 中，这些问题将不断避推动电予商务个性讫服务技术和数据挖掘技术的发展，创 造出更多的社会价值和经济价值。 1 3 论文研究的意义和所傲的工作 随着互联网络的发展，个性化的电子商务将成为网络经济的又一热点。本文在 关

19、联规则的理论基础上研究的电子商务推荐系统，正是针对商务个性化提出的。 在课题研究的过程中，我主要做了以下几项工作： f i n a n c i a lm a n a g e m e n t s o f t w a r e s u p p o r t = 2 ，c o n f i d e n c e = 6 0 规则的支持度和置信度是这个规则的度量尺度，它们分别反映发现规则的有 用性和确定性。关联规则的支持度2 意味着全部交易的2 同时购买计算机和财务 管理软件。置信度6 0 意味着购买计算机的顾客中，6 0 的顾客也购买财务管理软 件。如果一条规则同时满足最小支持度阀值和最小置信度阀值，则认为

20、这条规则 是有效的。支持度和置信度的阀值可以由用户或领域专家设定。 3 1 2 基本概念 1 事务数据库 一般地说，事务数据库【1 7 】由一个文件组成，文件中的每条纪录代表一个事务。 通常，一个事务包含一个唯的事务标识号( t r a n s I D ) ，和一个组成事务项的列 表( 如在商店购买的商品) 。事务数据库可能有一些与之相关的附加表，包含关于 销售的其它信息，如事务的日期、顾客的I D 号、销售者的I D 号、销售分店等等。 2 关联规则 设I = ，i ， 是项的集合。设任务相关的数据D 是数据库事务的集合， 其中每个事务T 是不同项的集台，使得T I 。每一个事物有一个标识符

21、，称作 T I D 。设A 是一个项集，事务T 包含A ，当且仅当爿r 。关联规则是形如A j B 的蕴含式，其中A c ，B c l ，并且A n B = o 。规则A j B 在事务集D 中成立， 具有支持度S ，其中S 是D 中事务包含A n B ( 即A 和B 二者) 的百分比，它是概 率P ( n B ) 。规则A j B 在事务集D 中具有置信度c ，如果D 中包含A 的事务同 时也包含B 的百分比是c ，即条件概率P ( B I A ) 。 s u p p o r t ( 一j 占) = P ( 4 n 占) c o n f i d e n c e ( A B ) = P ( B

22、 I ) 同时满足最小支持度阀值( m i n s u p ) 和最小置信度阀值( m i nc o n f ) 的规则 称作强规则。为方便计算，用o 和1 0 0 之间的值，而不是用0 到1 之间的值表示 支持度和置信度。 项的集合称为项集( i t e m s e t ) 。包含k 个项的项集称为k 项集。集合 c o m p u t e r ，f i n a n c i a l _ m a n a g e m e n t s o f t w a r e ) 是一个2 一项集。项集的出现频率是 包含项集的事务数，简称为项集的频率、支持计数或计数。如果项集的出现频率 大于或等于r a i n

23、 _ s u p 与D 中事务总数的乘积，项集则满足最小支持度m i n _ s u p 。 第三章基于关联规则的推荐模型的研究与改进 1 3 如果项集满足最小支持度，则称它为频繁项集( f r e q u e n ti t e m s e t ) 。频繁项集 k 一项集的集合通常记作t 。 3 1 3 预各定理 定理l ：当事务T 中不包含任何k 一高频项集时，则该事务不会包含任何n ( 太 于k ) 一高频项集。 证明：反证法，假设T 中包含n ( 大于k ) 一高频项集，假设为X ，则 s u p p o r t ( X ) = m i n s u p 。取 x的任意k维子集Y ，则 s

24、 u p p o r t ( Y ) = s u p p o r t ( x ) = m i n - s u p ，即Y 为k 一高频项集，与事物T 中不包含任 何k 一高频项集矛盾。所以命题得证。 定理2 ：规模为l 的事物T 与所挖掘规则的支持度没有关系。结论比较明显， 不再证明。 定理3 ：当求k 一高频项集时，规模小于k 的事务T 肯定与此无关。定理2 可 以作为此定理的一个特例。 定理4 ：如果一个项集x 不是高频项集，它的任何超集都不会是高频项集。 证明类似于定理1 ，这里不再重复。 定理5 ：如果一个k 一项集T 为高频项集，它的任何k l 维子集都是高频项集。 它的逆不成立。

25、证明：反证法，假设存在一个k l 维子集不是高频集，那么根据定理4 ，T 也 不是高频项集，与前提矛盾。命题得证。 定理6 ：一个候选k 一高频项集T ，如果( k 1 ) 一高频项集组成的集合中包含 该项集的k - 1 维子集的个数少于k ，那么它不是高频项集。 证明：反正法，假设T 是高频项集，根据定理5 ，k 一高频项集的所有k l 维子 集都是高频项集，而它的k - 1 维子集有k 个，如果高频k - 1 项集组成的集合中包 含该项集的k 一1 维子集的个数小于k ，也就是说存在最少个k l 维子集不是高 频项集，与定理5 矛盾。所以不是高频项集。 定理7 ：把待挖掘的数据集D 分成互

26、不相交的部分d 1 ，d 2 ，d 珥，如果x 为高 频项集，肯定存在一个子集d 。，X 在其中的支持度不小于m i n s u p 。 证明：反证法，假设不存在这样一个子集，则设x 在d 。中的支持度为S 。，S ， 小于m i n s u p ， S 。l = h i ，jD | = n = n l + n 2 + + t i m ， s u p p o r t ( X ) = ( n l * s l + n 2 * s 2 + + r l l f l * s i n ) n = m i n s u p p o r t ； ( 1 0 ) ( 1 1 ) r e t u r nL - 哪k

27、 L k 求L k 的和 p r o c e d u r ea p r i o r i _ g e n 皿k - J ：f r e q u e n t ( k 1 ) 一i t e m s e t s ；m i n s u p p o r t ：m i n i m u m s u p p o r tt h r e s h o l d ) ( 1 ) f o r e a c hi t e m s e tI i L k - 1 ( 2 ) f o re a c hi t e m s e t1 2 EL k - 1 ( 3 )i f 【1 1 【l 】= 1 2 【l 】) ( 1 t 【2 = 1

28、 2 【2 】) ( 1 1 【k - 2 = 1 2 【k - 2 】) 0 1 k - 1 = 1 2 【k - 1 】) t h e n ( 4 )c = l t u l z ； ( 5 )i f h a s _ i n f r e q u e n t _ s u b s e t ( c ，Lk - Ot h e n ( 6 ) d e l v e c ； ( 7 ) e l s e a d dc t o C k ； ( 8 ) ( 9 ) r e t u r nC k ； p r o c e d u r eh a s _ i n f r e q u e n ts u b s e t (

29、 c ： c a n d i d a t e k - i t e m s e t ； L k I ：f r e q u e n t ( k - 1 ) - i t e m s e t s ) ； ( 1 ) f o re a c h ( k - 1 ) 一s u b s e tSo f c ( 2 )i f s 芒L k - tt h e n ( 3 ) r e t u r n t r u e ； ( 4 ) I m t u H lf a l s e ； 图3 3A p r i o r i 算法的伪代码 3 2 2D I C 模型 动态项集计数法【2 8 j 9 ( D y n a m i c

30、I t e m s e tC o u n t i n g ) 是A p r i o r i 算法的变形， 旨在提高原算法的效率。D I C 技术将数据库划分为标记开始点的块，并可以在任 何开始点添加新的候选项集。该技术动态地评估已被计数的所有项集的支持度， 基于关联规则的推荐系统研究 如果一个项集的所有子集已被确定为频繁的，则添加它作为新的候选。这种方法， 能有效地减少对任意大项集进行计数的过程中扫描数据库的次数，解决了上文所 述的A p r i o r i 模型中的一大瓶颈。 1 模型描述 D I C 方法可以简单地理解为火车在各个车站中行驶：把所有的交易数据分割成 M ( M 是在试验中随

31、意设定的参数，一般为1 0 0 1 0 0 0 0 ) 次交易，每一次交易就 是火车行驶中的一个车站，当火车到达交易数据文件最后时，即已经把所有的数 据遍历一遍火车从文件头准备下次遍历。火车上的乘客就是项集，只要一个 项集在火车上，就统计它在交易中出现的次数。 如果把A p r i o r i 算法放到这个比喻中，所有的项集( 乘客) 必须在始发站上 车，终点站下车。l 一项集在第一次遍历中获得，2 一项集在第二次遍历中获得， 以此类推( 见图3 4 ) 。 图3 4A p r i o r i 的遍历过程 使用D I C 算法有很好的灵活性：它允许项集在任意站上车，但是必须在火车 经过一轮遍历

32、后同一站下车。这样项集“看到”了文件中所有的交易。这就意味 着，只要有必要对一个项集进行计数，就可以开始计数，而不必等到上一次遍历 结束再开始计数。( 见图3 5 ) = = ：皇= = = 兰 i = = = i = = = = = ：纛一 ：羔 ： + 一3 顼照= = = = = = = = = = = = = = = ：= = = ：点一+ 。 图3 5D I C 的遍历过程 第三章基于关联规则的推荐模型的研究与改进 1 9 举例来说，如果要挖掘4 0 0 0 0 个交易，M = 1 0 0 0 0 。首先要对将要读到的所有 1 0 0 0 0 个交易进行1 一项集计数；然后在第一个1

33、 0 0 0 0 个交易过后，开始对所有的 2 一项集计数；在2 0 0 0 0 个交易过后，开始对所有的3 一项集计数。假设这里不考 虑有4 一项集的情况。第一次到达文件末尾，停止对l 一项集计数，又回到文件头， 对2 一项集和3 一顼集计数。这样，第一个t 0 0 0 0 个交易过后，停止对2 一项集计 数；2 0 0 0 0 个交易过后，停止对3 项集计数。所以，在这个例子中，运用D I C 算 法只需要对数据进行1 5 次遍历，而A p r i o r i 算法需要3 次遍历过程。 2 算法分析 图3 6 网格状项集 所有的项集形成了一个网格状的结构，它的最底层是空集，所有项的组合在

34、最顶层( 见图3 6 ) 。在这里，大项集用矩形表示，其余的是小项集，所以图3 6 中的空集：A ，B ，C ，D ，A B ，A C ，B C ，B D ，C D ，A B C 都是大项集。 可以通过计数的方法来表明这些项集都是大项集。事实上，以后的计算中也 需要这些计数。然而，计算所有的小项集是不切实际的，不过幸运的是，根据定 理l ，只需要计算最小项集就足够了。最小项集用椭圆表示，在图3 7 中A D 和B C O 都是最小项集，它们形成了大项集和小项集之间的上边界。 计算大项集，必须对所有的大项集和最小项集计数( 也就是所有用矩形和椭 圆表示的项集) 。在进行动态项集计数的过程中，对项

35、集有四种表示方法： ( 1 ) 实线矩形( 确定的大项集) ：已经完成计数且超过支持度阀值的项集。 ( 2 ) 实线椭圆( 确定的小项集) ：已经完成计数且小于支持度阀值的项集。 ( 3 ) 虚线矩形( 待验大项集) ：正在进行计数且超过支持度阀值的项集。 ( 4 ) 虚线椭圆( 待验小项集) ：正在进行计数且小于支持度阀值的项集。 基于关联规则的推荐系统研究 根据上文的定义和分析，结合下面四张图，可以对D I C 的算法流程简单描述 如下： 穴 A BA CB CA DB Dc D 图3 7 开始D I C 算法 A B C D 六、 圈3 8M 个交易后 图3 92 M 个交易后图3 1

36、0 一次遍历结束后 ( 1 ) 空集用实线矩形表示。所有的l 硕集用虚线椭圆表示；其它项集未标 识。( 见图3 7 ) 第三章基于关联规则的推荐模型的研究与改进 2 1 ( 2 ) 读取M 个交易，试验中M 的范围为1 0 0 到i 0 0 0 0 ，在每一个交易中，要 对所有用虚线标识的项集进行单独计数。 ( 3 ) 如果一个虚线椭圆的计数超过指定的支持度阀值，把它变成虚线矩形。 如果某个项集的任意一个超集的所有子集都是虚线矩形或实线矩形，则 给他的计数加l ，并把它变成虚线椭圆。 ( 4 ) 如果一个虚线项集对所有的交易完成计数，把它变为对应的实线项集， 并停止对它计数。 ( 5 ) 到达

37、文件末尾后，从文件头开始循环。 ( 6 ) 如果有任何虚线项集存在，重新回到步骤( 2 ) 。 下图3 1 1 给出了D I C 实现的伪代码。D I C 算法从对l 一项集计数开始，然后 很快分别对2 ，3 ，4 k 项集开始计数。这样对交易数据经过几轮的遍历后( 对 于较小的M ，通常小于2 轮) ，就完成了对所有项集的计数。理想的情况下，可以 把M 设得足够小，这样就能在第三步中提前对项集计数，但是，第( 3 ) 步和第( 4 ) 步在运算过程中需要付出相当大的代价，所以实际应用中M 的值不小于1 0 0 。 3 D I C 模型的特点 D I C 算法实现了一种能对项集随时计数的新思路

38、。但是在性能上，如何对给定 的交易增加计数却存在一些问题。 ( 1 ) D I C 的优点 D I C 算法有很多好处，最主要的是它在性能方面的优势。如果交易数据是同类 的，而且跨度 足够小，这种算法只需要遍历两次交易文件，丽h p r i o r i 算法的 遍历次数决定于候选项集的最大容量。 除了性能方面，D I C 算法是一种非常灵活的方式，它能在遍历过程中增加或删 除正在计数的项集，使它的功能很容易得到更好地扩展。 ( 2 ) D I C 引发的问题 D I C 算法实现了一种对项集能随时计数的新思路。但是在性能上，针对如何对 给定的交易增加计数却存在一些问题。对于一个给定的项集，它的

39、数据结构的形 成很大程度上依赖于项的排列顺序。 实验证明 Z S l ，由于项的排列顺序不同，算法所付出的总代价是 ，f I n d e x ( L a s t ( I ) ，s ) 。其中I 是交易T 中所有的非叶节点项集， n I n d e x ( L a s t ( I ) ，S ) 表示在交易S 中I 后面的项的个数。因此，如果出现很多次 的项在项集排序中比较靠后，或者出现次数少的项排序靠前，都会使系统性能大 大提高。 基于关联规则的推荐系统研究 图3 1 1D I C 实现的伪代码 3 2 3F P - 增长模型 由上两节的内容可知，无论是A p r i o r i 模型还是经过改

40、进的D I C 模型，都是 建立在候选项集的基础上的。虽然频繁项集的产生大幅度压缩了候选项集的大小， 但是这些算法在产生候选集和重复扫描数据库两方面的开销都是非常巨大的【3 “。 频繁模式增长( f r e q u e n t p a t t e r n 增长) ，简称F P 一增长，它采取如下分治策略： 将提供频繁项集的数据库压缩到一棵频繁模式树( 或F P 一树) ，但仍保留项集的相 关信息：然后，将这种压缩后的数据库分成一组条件数据库( 一种特殊类型的投 影数据库) ，每个关联一个频繁项，并分别挖掘每个数据库。 1 模型描述 设项集I = a 。，a 2 一，o ，交易数据库D B =

41、。如果某一项集A 的计 第三章基于关联规则的推荐模型的研究与改进 数不小于预先定义的最小支持度阀值，则称A 为频繁模式。 定义1 ( F P 一增长) ：f 越 对于给定的交易数据库D B 和最小支持度阀值t ，寻找 所有的频繁模式项的过程，就叫做F P - 增长模型。 利用F P - 增长模型挖掘频繁模式项田H , 3 5 1 ( 即频繁大项集) ，通常要分为两个 步骤：第一，构建F P - t r e e ( F P 一增长模型的数据结构) ；第二，利用F P _ t r e e 找出 频繁模式项。 第一步：构建F P - t r e e 定义2 ( F P - t r e e ) ：F

42、P - t r e e 是一种树形的数据结构，它具有以下特点： ( 1 ) F P - t r e e 有一个标记为“n u l l ”的根节点，它的子节点为一个项前缀子树 ( i t e mp r e f i xs u b t r e e ) 的集合，还有一个频繁项( f r e q u e n ti t e m ) 组成的头表 ( h e a d e rt a b l e ) 。 ( 2 ) 每个项前缀子树的节点有三个域：i t e m n s n e ，c o u n t 和n o d el i n k ， i t e m n S f f l 8 记录了该节点所代表的项的名字；c o u

43、 n t 记录了所在路径代表的交易 ( t r a n s a c t i o n ) 中达到此节点的交易个数；n o d e l i n k 指向下一个具有同样的 i t e m n a m e 域的节点，要是没有这样一个节点，就为n u l l 。 ( 3 ) 频繁项头表( f r e q u e n ti t e mh e a d e rt a b l e ) 的每个表项( e n t r y ) 由两个域 组成：i t e m - n a m e 和n o d e l i n k 。n o d e _ l i n k 指向F P t r e e 中具有与该表项相同 i t e m -

44、n a m e 域的第一个节点。 通过一个例子，可以清楚的看到一棵F 卜增长模型的建立过程 设有如下交易数据库： T I D 购买项( 有序的) 频繁项 l O O F ，a ，e ，d ，g ，i ，m ，Pf ，C ，a ，m ，P 2 0 0 A ，b ，c ，f ，1 ，m ，of ，c ，a ，b ，m 3 0 0 B ，f ，h ，j ，0f ，b 4 0 0 B ，C ，k ，S ，P c ，b ，P 5 0 0 A ，f ，c ，e ，l ，P ，【I l ，nf ，c ，a ，m ，P 表3 1 排序频繁项 首先扫描一遍这个数据库，计算每个项的计数并保存在频繁项的集合F 中，

45、F = “a ：3 ) ，( b ：3 ) ，( c ：4 ) ，( d ：1 ) ，( e ：1 ) ，( f ：4 ) ，( g ：1 ) ，( h ：1 ) ，( i ：1 ) ，( j ：1 ) ，( k ：1 ) ，( 1 ：2 ) ，( m ：3 ) ，( n ：1 ) ，( o ：2 ) ，( p ：3 ) ) 。集合中每个元素的第二个分量代表第一个 分量所代表项的支持度。假定最小支持度为3 ，选出F 中支持度大于3 的项，并 按支持度降序排列，将结果放入列表 L 中，此 基于关联规则的推荐系统研究 时，L _ f ( f ：4 ) ，( c ：4 ) ，( a ：3 ) ，(

46、b ：3 ) ，( m ：3 ) ，( P ：3 ) ) 。 接着，创建一个标记为“n u l l ”的根节点，开始对数据库第二遍扫描。对第一 个交易的扫描将建立这棵树的第一个分支： 。 注意，在这个交易中的频繁项已经按照L 中的顺序进行排序了；对于第二个交易， 它已经排序好的频繁项列表 同已经存在的路径 有共同的 前缀 ，所以把这个前缀中的所有节点的c o u n t 增加1 ，然后新节点( b ：1 ) 被 创建并且被作为节点( a ：2 ) 的子节点，随后新节点( m ：I ) 被创建并作为节点( b ：1 ) 的 子节点；对第三个交易，因为它的频繁项列表只同以f 为前缀的子树有一个共同

47、节 点( f ，所以把这个节点的c o u n t 增加1 ，并且创建新节点( b ：1 ) ，把它作为( f ：3 ) 的 子节点。以此类推，扫描完整个数据库。 为了方便对树的遍历，需要建立一个频繁项头表( f r e q u e n ti t e mh e a d e r t a b l e ) ，项头表的n o d e l i n k 指向树里面具有相同i t e m _ n s , m e 的节点，具有相同 i t e r nn a m e 的节点通过n o d e _ l i n k 被连结在起。 1 t h e a do fn o d e l i n k 4 一一一 f C 一 a

48、 b m 、 p 图3 1 2 频繁模式树F 卜t r e e 第二步：寻找频繁模式项 构建了压缩的频繁模式树，可以确保后续的挖掘工作在一个压缩的数据结构中 进行。但是这种结构也不能自动就使挖掘的效率非常高，还需要严密丽合理的F P 一 增长算法，才能使该模型高效、准确、完备的找出所有的频繁模式项。 把图3 1 2 中已经得到的F 卜t r e e 和相应的头表作为这一部分的输入。按照从 表尾到表头的顺序考察表中的每一个表项。 第三章基于关联规则的推荐模型的研究与改进 从表项P 出发，可以先得到一个频繁集( p ：3 ) ，然后，得到包含p 的所有模式， 顺着p 表项的n o d e l i

49、n k 域，找到所有包含p 的路径 和 。对第一条路径，虽然f 出现了3 次，c 和a 各出现了两次，但它们 同p 在一起只出现了2 次，所_ 以把它们的计数改为2 ，得到 ( f ：2 ，c ：2 ，a ：2 ，i l l ：2 ，P ：2 。第二条路径中各项的计数都已相同，不用修改。把这两 条路径中的p 项去掉，就得到了p 的条件模式库，( ( f ：2 ，c ：2 ，a ：2 ，m ：2 ) ，( c ：1 ，b ：1 ) ) ， 这是下一步递归的依据。最后把这个条件模式库看作一个数据库，运用步骤一产生 一个新的F P - t r e e ，这就是步骤二中的条件树，这个新树只有一个节点( c ：3 ) ，这 时又得到个新的频繁集( c p ：3