（计算机应用技术专业论文）基于fptree的关联规则挖掘算法的研究.pdf

广西夫掣凋等掌力申请硕士掌位论文i i 于f p t r e e 的关联鲠j g 挖掘爿坤基的研究 基于f p t r e e 的关联规则挖掘算法的研究 摘要 数据挖掘也称为数据库中的知识发现，受到当今国际人工智能与数据库界的广泛重 视，它是从大量数据中发现潜在的、有趣的知识的过程。关联规则挖掘是数据挖掘领域 中的一个非常重要的研究内容，其主要目标就是发现数据库中一组对象之间某种有趣关 联或相关联系，在许多领域得到了广泛的应用。 关联规则的挖掘主要是基于频繁集的方法，相关的算法主要有a p r i o r i 算法和 f p g r o w t h 算法。f p g r o w t h 算法采用不同于以前a p r i o r i 系列算法的候选产生测试方法， 采取模式增长的方法挖掘关联规则，它克服了a p d o d 系列算法的缺陷，取得了很好的 效果。但是，f p g r o w t h 算法仍然存在着一些不足，如算法的性能严重依赖于数据库的 大小，挖掘关联规则时需要递归地生成和释放成千上万的条件模式树，等等。 针对a p r i o r i 算法和f p g r o w t h 算法存在的问题，本文主要开展并完成了以下研究工 作： ( 1 ) 深入了解关联规则挖掘的研究现状，重点研究基于f p - t r e e 的关联规则挖掘算法 f p g r o w t h 算法，分析和讨论该算法存在的主要问题。 ( 2 ) 提出了一种基于投影的频繁模式树后插式构造方法并设计了相应的算法。该方 法充分利用大型数据库的投影运算能力，按层来构造频繁模式树( f p t r e e ) ，有效地解决 了传统的f p t r e e 构造中存在的问题。 ( 3 ) 具体研究了f p t r e e 和p r i f p - t r e e 的实现，并通过实验对两种构造方法进行对比， 分析两种构造算法的性能。实验结果表明基于投影的频繁模式树后插式构造方法与传统 的频繁模式树的构造方法相比较，具有更好的可伸缩性，特别是在事务数很大的情况下， 效果尤其显著。 本文的研究工作是对关联规则的挖掘算法的切实可行的改进，对研究基于s q l 的 关联规则挖掘算法具有一定的参考价值。 关键词：数据挖掘关联规则频繁模式树投影技术投影后插式频繁模式树 广西大掌同等掌力申请硕士掌位论文l 于f p t r e e 的美联规则挖掘算法的研究 s t u d yo na s s o c i a t i o nr u l e sm i n i n ga l g o r i t h mb a s e d o nf p t r e e a b s t r a c t d a t am i n i n g ，w h i c hi sc a l l e dk n o w l e d g ed i s c o v e r yi nd a t a b a s e ，h a sb e e na t t a c h e d i m p o r t a n c eb yt h ef i e l do fi n t e r n a t i o n a la r t i f i c i a li n t e l l i g e n c ea n dd a t a b a s e i ti sap r o c e s so f d i s c o v e r i n gl a t e n ta n di n t e r e s t i n gk n o w l e d g ef r o mp l e n t i f u ld a t a a so n eo ft h ei m p o r t a n t c o n t e n t si nd a t am i n i n g ，a s s o c i a t i o nr u l em i n i n ga i m st od i s c o v e rt h ei n t e r e s t i n gc o n n e c t i o no r t h ec o r r e l a t i o nm i d s tas e to fo b j e c t si nad a t a b a s e i ti sa p p l i e dw i d e l yi nm a n yf i e l d s a p r i o r ia l g o r i t h ma n df p - g r o w t ha l g o r i t h m a r et w om a i na l g o r i t h m si n m i n i n g a s s o c i a t i o nr u l e sw h i c ha r eb a s e do nf r e q u e n ti t r e m s e t s d i f f e r e n tf r o mt h ef o r m e rc a n d i d a t e s e tg e n e r a t i o n a n d - t e s tp a t t e r n so ft h ea p r i o r i l i k ea l g o r i t h m ，f p - g r o w t ha l g o r i t h mt a k e st h e w a yo fp a t t e r nf r a g m e n tg r o w t ht om i n ea s s o c i a t i o nr u l e i tc o m p l e t e st h ea p r i o r ia l g o r i t h m a n dh a sg o o de f f e c t b u tt h ef p - g r o w t ha l g o r i t h mi sn o tp e r f e c t f i r s t 。i t sp e r f o r m a n c e s e r i o u s l yr e l i e so nt h es c a l eo ft h ed a t a b a s e n e x t ，i tm a yg e n e r a t ea n dr e l e a s em i l l i o n so f c o n d i t i o n a lp a t t e r nt r e e si nt h ep r o c e s so f m i n i n g ，a n ds oo n t h i sp a p e rh a sc o m p l e t e dt h ef o l l o w i n gr e s e a r c hw o r kt os o l v et h ep r o b l e m so ft h e a p r i o r ia l g o r i t h ma n dt h ef p - g r o w t ha l g o r i t h m ( 1 ) a f t e rk n o w i n gt h ea c t u a l i t yo f t h ea s s o c i a t i o nr u l em i n i n g ，t h i sp a p e rm a i n l ys t u d i e s t h ef p - g r o w t ha l g o r i t h mw h i c hi sb a s e do nt h ef p - t r e e i ta l s oa n a l y z e sa n dd i s c u s s e st h e m a i ne x i s t e n c ep r o b l e m s ( 2 ) t h i sp a p e rp r o p o s e sar e a r - i n s e r t i n gc o n s t r u c t i o no ff r e q u e n tp a t t e r nt r e eb a s e do n p r o j e c t i o nt e c h n o l o g y i tc o n s t r u c t st h ef p t r e el e v e lb yl e v e lb a s e do np r o j e c t i o nt e c h n o l o g y a n dm a k e st h eb e s to ft h ep r o j e c t i o no p e r a t i o na b i l i t yo ft h el a r g e s c a l ed a t a b a s e i ts o l v e st h e p r o b l e me f f e c t i v e l yw h i c he x i s ti nt h et r a d i t i o n a lf p - t r e ec o n s t r u c t i o n ( 3 ) t h i sp a p e rh a ss t u d i e dt h ei m p l e m e n t a t i o no ft h ec o n s t r u c t i o no ft h ef p t r e ea n d p r i f p t r e e i tc o m p a r e st h e s et w oc o n s t r u c t i o nm e t h o d sa n da n a l y z e st h ep e r f o r m a n c eo f t h e mt h r o u g he x p e r i m e n t t h er e s u l ts h o w st h a tt h ep r j f p t r e ec o n s t r u c t i o ni sm o r ee f f i c i e n t a n ds e a l a b l et h a nt r a d i t i o n a lf p - t r e ec o n s t r u c t i o n ，e s p e c i a l l yw h e nt h et r a n s a c t i o n sa l eh u g e o u rr e s e a r c hw o r ki sap r a c t i c a li m p r o v e m e n tt ot h ea s s o c i a t i o nr u l em i n i n ga l g o r i t h m i t h a sv a l u a b l er e f e r e n c et ot h er e s e a r c ho f a s s o c i a t i o nr u l em i n i n ga l g o r i t h mb a s eo ns q l k e yw o r d s ：d a t am i n i n g ，a s s o c i a t i o nr u l e ，f r e q u e n tp a t t e r nt r e e ( f p - t r e e ) ，p r o j e c t i o n t e c h n o l o g y , p r o j e c t i o nr e a r - i n s e r t i n gf r e q u e n tp a t t e r nt r e e ( p r i f p - t r e e ) l i 广西大掌同等学力申请硕士掌位论文| l 于f p t r e e 的 黾联规曩9 挖掘j ”羞的研，巴 第一章绪论 1 1 课题研究的背景和意义 在这被称之为信息爆炸的时代，如何才能不被信息的汪洋大海所淹没，从中及时发 现有用的知识，提高信息利用率是人们面临的一个重要的挑战。随着数据库技术的成熟 和数据库管理系统的广泛应用，特别是国际互联网的快速发展，人类积累的数据量正在 以指数速度增长。这些海量数据中隐藏着许多事先不知道、但又是潜在有用的信息和知 识，人们迫切需要能从海量数据中发现这些信息和知识的工具，数据挖掘( d a t am i n i n g ) 和知识发现技术应运而生，并得以蓬勃发展，越来越显示出其强大的生命力。目前，数 据挖掘技术已经在大型商业、金融业、保险业、民航业、电信业等行业得到广泛的应用， 已经显示出巨大的应用价值和广阔的应用前景。 数据挖掘指的是从大型数据库或数据仓库中提取人们感兴趣的知识，这些知识是隐 含的、事先未知的、潜在的有用信息。数据挖掘的任务是从数据中发现模式，模式有很 多种，在实际应用中细分为6 种：分类模式、回归模式、时间序列模式、聚类模式、关 联模式和序列模式，其中关联模式的挖掘是目前数据挖掘领域中最为广泛的研究课题之 一。 数据项之间的关联规则称为关联模式。我们所讨论的问题集中在数据挖掘中的关联 规则上。关联规则用于从大量数据中发现项集之间的有趣关联或相关联系i l l 。关联规则 挖掘的一个典型例子是购物篮分析。关联规则研究有助于发现交易数据库中不同商品 ( 项) 之间的联系，找出顾客购买行为模式，如购买了某一商品对购买其它商品的影响。 分析结果可以应用于商品货架布局、货存安排以及根据购买模式对用户进行分类。关联 规则有着广泛的应用：在商业领域，关联规则能够协助企业决策者完成市场分析和进行 客户关系管理1 2 1 ；在基因生物学中，关联规则可用来分析基因表达谱数据i 引，揭示不同 基因间或环境与基因表达之间的相关联系；在网络安全领域，关联规则能够揭示不同攻 击行为之间的关系1 4 l 。此外，关联规则还能应用于分类、相关分析等数据挖掘领域。 关联规则的挖掘主要是基于频繁集的方法，最近也有独立于频繁集的算法研究。基 于频繁集的算法主要是a p r i o r i 算法和f p g r o w t h 算法。a p r i o r i 算法存在一些固有的、 无法克服的缺陷，主要有：( 1 ) 需要重复地扫描数据库，这导致了巨大的i o 开销；( 2 ) 需 要产生大量的候选集，并通过模式匹配来检查候选项集的频繁性，这会产生巨大的计算 广西大掌同等掌力申请硕士掌位论文| i 于f p t r e e 的号射供籼口挖掘算法的研究 量。f p g r o w m 算法是一个本质上不同于a p r i o r i 算法的挖掘频繁模式的有效方法，它 不生成候选频繁项集且只需要两次扫描数据库，有效地克服了a p r i o r i 算法的缺点。性 能分析表明：对于挖掘长的和短的频繁模式，f p g r o w t h 算法都是有效的，并且其挖掘 速度大约比a p r i o r i 算法快一个数量级。但是f p g r o w t h 算法本身也还存在着一些缺点， 主要有：( 1 ) 在挖掘频繁模式时，它需要递归地生成条件f p t r e e ，并且每产生一个频繁 模式就要生成一个条件f p t r e e 。在支持度阈值较小时，即使对于很小的数据库，也将产 生数以十万计的频繁模式。动态的生成和释放数以十万计的条件f p - t r e e ，将耗费大量时 间和空间。( 2 ) f p - t r e e 和条件f p t r e e 需要自顶向下生成，而频繁模式的挖掘需要自底向 上处理。如果f p t r e e 和条件f p - t r e e 采用双向指针，结点中就需要更多的指针，从而需 要更大的内存空间来维护f p t r e e 和条件f p t r e e 。 针对f p g r o w t h 算法中存在的问题，本文提出了基于投影的频繁模式树后插式构造 方法，对传统的f p - t r e e 进行重构，采用自底而上的指针结构，取消头表，充分利用了 大型数据库投影运算的能力，按层来构造f p t r e e ，实现了f p t r e e 的单向指针结构，节 约了内存空间，而且算法在结点数比较大的情况下更加有效。因此本文的研究具有较高 的实用价值和理论意义。 1 2 国内外研究的现状 1 9 9 3 年r a b e s ha g r a w a l 等人首先提出了关联规则的问题1 5 i ，并于1 9 9 4 年提出了挖 掘关联规则的经典算法a p n o n 算法1 6 i 。a p r i o r i 算法需要多次重复扫描数据库，而且可 能产生大量的侯选项集。为了提高算法挖掘规则的效率，不少学者进行了大量的研究， 并对原有的a p r i o r i 算法进行了优化，如引入了散列方法n i 、事务压缩嘲1 9 1 、划分的思想 1 0 l 、随机采样i i 和动态集计数1 1 2 1 等。 针对a p r i o r i 算法的固有缺陷，j i a w e ih a n 等提出了不产生候选挖掘频繁项集的方 法一f p g r o w t h 算法l i “，实验表明，f p g r o w t h 算法对不同长度的规则都有很好的适应 性，同时在效率上较之a p r i o r i 算法有巨大的提高。但是f p g r o w t h 算法并不是完美无 缺，如果由原数据库得到的f p t r e e 的分支很多且分支长度很长时，该算法将需要构造 出数量巨大的条件f p t r e e ，不仅费时而且要占用大量的空间，挖掘效率不高，而且递 归算法本身效率也较低。为了进一步提高算法的效率，不少研究者进行了大量的研究， 提出了许多改进的算法。文献【1 4 i 提出了基于共同事务频繁项目树的c o f l 一t r e em i n i n g 算法，通过有效的剪枝节约大量的内存空间；文献i ”1 通过引入f 一矩阵，来减少条件模 2 广西大掌同等掌力申司 硕士掌位论文| i 于f p t r e e 的关联规则挖掘算法的研究 式树的数目：为了避免了挖掘过程中不断产生和释放条件模式树的缺点，文献i “i 弓i a t 被约束子树，而文献i 1 中的c f p t r e e 是对f p t r e e 的进一步压缩存储，并对交易数据 库进行投影分割，然后分别进行关联规则的挖掘；除此之外，为了解决当频繁模式树结 点数目巨大时，可能会造成内存溢出和算法性能的激剧下降问题，许多研究引入了并行 算法和分布式算法【1 8 i i ”1 。而针对解决频繁模式树自顶而下的构造和频繁模式自底而上挖 掘的问题，相关研究比较少，许多算法简单地以空间换取时间，采用双向指针的结构 1 1 4 1 1 加i 。 a p r i o r i 算法和f p g r o w t h 算法都是基于频集理论的关联规则挖掘算法。由于最大频 繁项目集中已经隐含了所有频繁项目集，所以可把发现频繁项目集的问题转化为发现最 大频繁项目集的问题。先前提出的可用于发现最大频繁项目集的算法主要基于a p r i o r i 候选项目集生成一检验方法，主要有m a f i a l 2 1 i 、p i n c e r - s e a r c h l 2 2 i 、d m f i l 2 3 l 和 m a x m i n e r i n i 等。而目前挖掘最大频繁项目集的算法主要基于f p t r e e 的算法，主要的算 法有d m f i a i 筋1 、m f p g r o w t h l 2 6 1 等。 挖掘频繁闭包项目集是降低候选项目集数量的另一种手段，由于频繁闭包项目集能 导出所有的频繁项目集及其支持度，从而也就导出了所有的关联规则，既没有丢失信息， 又大大减少了工作量，提高了效率。先前提出的基于a p r i o r i 候选项目及生成一检验方 法的算法主要有文献1 2 7 1 1 2 8 1 1 2 9 1 中的算法。而基于f p t r e e 的频繁闭包项目集挖掘算法主要 是j i a n p e i 等提出的c l o s e t 算法咖1 和c l o s e t + 算法i n l ，之后的闭包项目集挖掘算法主要都 是基于此基础上进行改进的，例如文献1 3 2 i i 蚓中的算法。 作为数据挖掘的一项重要研究内容，关联规则挖掘算法的研究一直受到数据挖掘界 的重视。在f p g r o w t h 算法提出之前，主要研究a p r i o r i 算法的优化和改进，以提高算法 的效率。之后的研究主要集中在f p g r o w t h 算法的优化和改进方面，而对于f p - t r e e 的构 造算法的研究比较少。本文提出的基于投影的后插式频繁模式树的构造方法是这方面研 究的一个补充，对基于f p t r e e 的关联关则挖掘算法的进一步研究工作具有一定的参考 价值。 1 3 论文的研究内容与组织结构 本文主要开展并完成以下方面的工作： ( 1 ) 深入了解挖掘关联规则相关算法，重点研究基于f p t r e e 的关联规则挖掘算法一 f p g r o w t h 算法，分析和讨论该算法存在的主要问题。 广西犬掌周等学力申爿h 页吐唾粤位诧文| l 于f p t r e e 的袅美规则挖掘算法- 的嗣h 恕 ( 2 ) 对传统的f p - t r e e 进行重新构造，使之占用更小的存储空间，同时更好地解决存 在的问题。 ( 3 ) 研究并提出基于投影的频繁模式树后插式构造方法，并给出构造算法。 ( 4 ) 为了验证新的构造方法的有效性，利用d e l p h i 语言实现构造的算法，利用实际的 数据进行实验，并与传统的f p - t r e e 构造方法进行比较。 本文其余章节安排如下： 第二章为数据挖掘和关联规则挖掘方面的内容。首先介绍了数据挖掘的产生背景、 定义、功能和应用领域；接着给出关联规则的定义，描述挖掘关联规则的两种经典算法 并分析其优缺点。 第三章阐述本文所提出的基于投影的频繁模式树后插式构造方法的相关内容。首先 描述传统的频繁模式树的构造过程，然后阐述基于投影的频繁模式树后插式构造方法的 基本思想、构造方法和算法，并详细描述其构造过程。 第四章是实验评价与性能分析，主要对新的频繁模式树构造方法的正确性和有效性 进行验证，通过与传统的频繁模式树构造方法进行比较，证明新算法在时间和空间上的 可伸缩性。 第五章是本文研究工作的总结和展望。 4 广西夫掌同等掌力申请司e 士掌位论文 墓于f p t r e e 的岩港期哺蚰它掘算法的研究 第二章数据挖掘与关联规则挖掘 2 1 数据挖掘的基本概念 在过去的数十年中，我们产生和收集数据的能力已经迅速提高，许多商务、科学和 行政事务的数字化，特别是国际互联网的流行，已经将我们淹没在数据和信息的汪洋大 海中，存贮数据的爆炸性增长已激发对新技术和自动工具的需求，以便帮助我们将海量 数据转换成信息和知识。目前的数据库系统可以高效地实现数据的录入、查询、统计等 功能，却无法识别隐藏在数据中的、能对决策提供支持的信息。大量的数据未能充分利 用的现象常常被描述为“数据爆炸，但知识贫乏”。为了解决这个问题，人们迫切需要 能从海量数据中发现潜在有用的信息和知识的工具，数据挖掘技术正是为满足这一需求 而产生的。数据挖掘就是按既定的业务目标，对大量的数据进行探索和分析，揭示隐藏 的未知的或验证已知的商业规律，且进一步将其模式化的数据处理方法，它的最大特点 是能够建立预测模型，预测未来的情况。 2 1 1 数据挖掘的定义 从技术的角度来定义，数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声 的、模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是 潜在有用的信息和知识的过程。简单的说，数据挖掘是从大量的数据中提取或挖掘“知 识”。提取的知识表示为概念、规则、规律、模式等形式。 从商业的角度来定义，数据挖掘是一种新的商业信息处理技术，其主要特点是对商 业数据库中的大量业务数据进行抽取、转换、分析和其它模型化处理，从中提取辅助商 业决策的关键性数据。简而言之，数据挖掘其实是深层次的数据分析方法。 数据挖掘与传统的数据分析( 如查询、报表、联机应用分析) 的本质区别是：数据挖 掘是在没有明确假设的前提下去挖掘信息、发现知识，数据挖掘所得到的信息应具有先 前未知、有效和可实用三个特征。 先前未知的信息是指该信息是预先未曾预料到的，即数据挖掘就是要发现那些不能 靠直觉发现的信息或知识，甚至是违背直觉的信息或知识，挖掘出的信息越是出乎意料， 就可能越有价值。数据挖掘在商业应用中最典型的例子就是一家连锁店通过数据挖掘发 现了小孩尿布和啤酒之间有着惊人的联系。 广西大掌同鼍掌力申请硕士掌位论文童于f p t r e e 的岩啾期测挖掘算法的研究 2 1 2 数据挖掘的功能与任务 数据挖掘的任务主要是关联分析、聚类分析、分类、预测、时序模式和偏差分析等。 ( 1 ) 关联分析( a s s o c i a t i o na n a l y s i s ) 关联分析的目的是找出数据库中隐藏的关联网。般用支持度和可信度两个阈值来 度量关联规则的相关性，还需要不断引入兴趣度、相关性等参数，使得所挖掘的规则更 符合需求。 ( 2 ) 聚类分析( c l u s t e r i n g ) 聚类是把数据按照相似性归纳成若干类别，同一类中的数据彼此相似，不同类中的 数据相异。聚类分析可以建立宏观的概念，发现数据的分布模式，以及可能的数据属性 之间的相互关系。 ( 3 ) 分类( c l a s s i f i c a t i o n ) 分类就是找出一个类别的概念描述，它代表了这类数据的整体信息，即该类的内涵 描述，并用这种描述来构造模型，一般用规则或决策树模式表示。分类是利用训练数据 集通过一定的算法而求得分类规则。分类可被用于规则描述和预测。 ( 4 ) 预澳1 ( p r e d i c a t i o n ) 预测是利用历史数据找出变化规律，建立模型，并由此模型对未来数据的种类及特 征进行预测。预测关心的是精度和不确定性，通常用预测方差来度量。 ( 5 ) 时序模式( t i m e s e r i e sp a t t e m ) 时序模式是指通过时间序列搜索出的重复发生概率较高的模式。与回归一样，它也 是用己知的数据预测未来的值，但这些数据的区别是变量所处时间的不同。 ( 6 ) 偏差分析( d e v i a t i o n ) 在偏差中包括很多有用的知识，数据库中的数据存在很多异常情况，发现数据库中 数据存在的异常情况是非常重要的。偏差检验的基本方法就是寻找观察结果与参照之间 的差别。 2 1 3 数据挖掘的应用 目前，数据挖掘的应用领域包括以下八个方面，而每个领域又都有自己的应用领域 和应用背景1 3 4 i d 5 i 。 ( 1 ) 金融。金融事务需要收集和处理大量的数据，通过对这些数据进行分析，发现 其数据模式及特征，然后可能发现某个客户、消费群体或组织的金融和商业兴趣，也可 6 广西大掣惆等掌力申请硕士掣啦论文墓于f p t r e e 的j 溅规则挖掘喜【法的研究 观察金融市场的变化趋势。数据挖掘在金融领域的应用广泛，包括数据清理、金融市场 分析预测、用户分类、信用评估等。 ( 2 ) 医疗保健。医疗保健业有大量的数据需要处理，但这个行业的数据由不同的信 息管理系统管理，数据以不同的格式保存，从总体看，数据是无组织的。在这个行业中， 数据挖掘的关键任务是进行数据清理、预测医疗保健的费用。例如g t e 实验室开发的 k e f i r ，它能进行多维分析，用于分析g t e 的医疗保健数据，对比数据和预测数据， 在定量范围内解释偏差，生成超文本报表。 ( 3 ) 市场业。市场业应用数据挖掘技术进行市场定位、消费者分析、辅助制定市场 营销策略等。 ( 4 ) 零售业。零售业是最早运用数据挖掘技术的行业。目前，主要运用于销售预测、 库存需求、零售点的选择、价格分析等。 ( 5 ) 制造业。制造业应用数据挖掘技术进行零部件故障诊断、资源优化、生产过程 分析等。 ( 6 ) 司法。数据挖掘也可应用于案件调查、诈骗检测、犯罪行为分析等方面，这些 都可以给司法工作带来巨大的利益。 ( 7 ) 工程和科学。在信息量极为庞大的天文、气象、生物技术等领域中，所获得的 大量实验和观察数据巨大，仅靠传统的数据分析工具难以应付，因此对功能强大的智能 化自动分析工具要求迫切，这种需求推动了数据挖掘技术在科学研究领域的应用发展。 目前该领域的数据挖掘已取得了一些重要的研究成果，例如：j e t p r o p u l s i o n 实验室利用 决策树方法对上百万个天体数据进行分析，帮助天文学家发现了1 6 颗星体，效果要比 人工更快、更准确。 ( 8 ) 保险业。对受险人员的分类将有助于确定适当的保险金额度。通过数据挖掘可 以得到对不同行业、不同年龄段、不同社会层次的人的保险情况、他们的险金应该如何 确定等信息。另外，还可进行险种关联分析，分析购买了某种保险的人是否又同时购买 另一种保险，以便预测出什么样的顾客将会购买新险种。 2 2 关联规则简介 关联规则挖掘作为数据挖掘中的一个重要领域，目前已在商业、教育、科研等领域 有了许多成功应用，这使它成为数据挖掘中最成熟、最重要、最活跃的一个分支。关联 规则挖掘首先由r a b e s h a g r a w a l 等人1 5 i 于1 9 9 3 年提出，用于发现大量数据中项集之间 - 西大掌同等掌力申请硕士掌位论文| i 于f p t r e e 的 联期u q 挖掘奢特的研究 有趣的关联或相关联系，例如关联规则研究有助于发现交易数据库中不同商品( 项) 之 间的联系。关联规则挖掘的一个典型例子是购物篮分析，市场分析员要从大量的数据中 发现顾客放入其购物篮中的不同商品之间的关系。如果顾客买牛奶，他也购买面包的可 能性有多大? 顾客多半会在一次购物时同时购买什么样的商品组或集合? 例如，买牛奶 的顾客中有8 0 也同时买面包，这就是从购物篮数据中提取的关联规则。这种关联的发 现可以帮助零售商制定营销策略，以及应用于商品货架布局、货存安排，根据购买模式 对用户进行分类等。 2 2 1基本概念 设i = ( i 1 ，i 2 ，i 。) 是项( i t e m ) 的集合，任务相关的数据d 是数据库事务的集合，其 中每个事务t 是项的集合，有t - - i 。每一个事务有一个标识符，称作t i d 。 定义2 1设x 是i 中项的集合，称作项集( i t e m s e t ) ，事务t 包含x 当且仅当x 量t 。 定义2 2 包含k 个项的项集称为k 项集。例如 牛奶，面包 是一个2 项集。 定义2 3 如果项目集x 在事务数据库d 中的支持度不小于用户给定的最小支持度 阈值，那么称x 为频繁项目集；反之称之为非频繁项目集。 定义2 4 关联规则是形如x _ y 的蕴涵式，其中x 互i ，y i ，并且x n y = 中。 描述关联规则属性常用的参数有： ( 1 ) 支持度( s u p p o r t ) 。支持度s 是d 中包含a u b 的事务百分比，它是概率p ( a u b ) ， 即s u p p o r t ( a - b ) = p ( a u b ) ，它描述了a 和b 这两个物品集的并集在所有的事务中出 现的概率。 ( 2 ) 可信度( c o n f i d e n c e ) 。可信度c 为d 中包含a 的事务中同时也包含b 的百分比， 它是概率p ( b a ) ，即c o n f i d e n c e ( a = b ) = p ( b a ) 。 ( 3 ) 相关支持度( c o r r e l a t i o ns u p p o r t ) 。在事务数据库d 中和d 中的关联规则x - y ， 该关联规则的相关支持度为： c o r r e l a t i o n _ s u p p o r t = s u p p o r t uy ) ( s u p p o r t ( x ) xs u p p o r t ( y ) ) = c o n f i d e n c e ( x = y ) s u p p o r t ( y ) 从某种意义上说，相关支持度更能反映关联规则中x 和y 的关系，由它可以了解x 和y 之问的关系究竟如何密切；而可信度则反映了在这种情况下的关系方向，即是从x 到y ，还是从y 到x ；支持度则反映了这种情况在事务中是否是普遍的规律。 广西大学同等掌力审爿卜瞩士学位论文基于f p t r e e 的关联规更q 挖掘爿讳去的研究 项集的出现频率是包含项集的事务数，简称为项集的频率、支持度计数或计数。在 基于支持度一可信度框架中，同时满足用户定义的最小支持度阈值( m i n 度阈值( r a i nc o n o 的关联规则称为强关联规则。关联规则的挖掘问题就是在事务数据库 d 中找出满足用户给定的最小支持度和最小可信度的强关联规则。频繁k 项目集的集合 通常记作l k 。 2 2 2 关联规则的分类 传统的关联规则挖掘形式是购物篮分析，但关联规则绝不仅这一种，根据不同的标 准，关联规则可以分为不同的类型i m i 。 2 2 2 1 按规则中处理的变量的类别来划分 按规则中处理的变量的类别来划分，关联规则可以分为布尔型和数值型。布尔型关 联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系；而数值型关联 规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理，将其进行动态 的分割，或者直接对原始的数据进行处理，当然数值型关联规则中也可以包含种类变量。 例如，性别女，_ 职业秘书”，是布尔型关联规则；性别女_ a v g ( 收入) = 1 3 0 0 ， 涉及的收入是数值类型，所以它是一个数值型关联规则。 2 2 2 2 按规则中数据的抽象层次来划分 按规则中数据的抽象层次来划分，可以分为单层关联规则和多层关联规则。在单层 的关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的；而在多 层的关联规则中，对数据的多层性已经进行了充分的考虑。 例如：i b m 台式机= s o n y 打印机，是一个细节数据上的单层关联规则；台式机 = s o n y 打印机，是一个较高层次和细节层次之间的多层关联规则。 2 2 2 3 按规则中涉及到的数据的维数来划分 按规则中涉及到的数据的维数来划分，关联规则可以分为单维的和多维的。在单维 的关联规则中我们只涉及到数据的一个维，如用户购买的物品；而在多维的关联规则中， 要处理的数据将会涉及多个维，换句话说单维关联规则是处理单个属性中的一些关系； 多维关联规则是处理各个属性之间的某些关系。 例如，啤酒= 尿布这条规则只涉及到用户的购买的物品，性别= “女”= 职业= “秘 书”这条规则就涉及到两个字段的信息，是在两个维上的一条关联规则。 9 广西夫掌同等掌力申请司仕掌位论文基于f p t r e e 的毒蹶规则挖掘算法的研究 2 2 3 关联规则的应用领域 如前所述，关联规则挖掘的一个典型应用是购物篮分析( b a s k e ta n a l y s i s ) 。在超市购 物蓝分析中可以认为每个事务表示一个顾客的购买行为，而事务包含的项目表示顾客一 次性购买的商品。该过程通过发现顾客放入其购物篮中不同商品之间的联系，从而分析 顾客的购买习惯。例如“8 0 的顾客在购买笔记本电脑的同时也会购买数码相机”，这 种关联发现可以帮助零售商制定营销策略。譬如，超市经理可以将笔记本电脑和数码相 机放在一起，以便在销售笔记本电脑的同时刺激数码相机的销售。 关联规则在其它领域也有着广泛的应用。在商业领域，关联规则能够协助企业决策 者完成市场分析，进行客户关系管理【2 i ；在基因生物学中，关联规则可用来分析基因表 达谱数据舢，揭示不同基因间或环境间与基因表达之间的相关联系；在网络安全领域， 关联规则能够揭示不同攻击行为之间的关系1 4 i ；在网络信息领域，关联规则能为用户提 供个性化的服务i i 。此外，关联规则还能应用于分类、相关分析等数据挖掘领域： 2 3 关联规则挖掘的经典算法及分析 关联规则的挖掘主要是基于频繁集的方法，最近也有独立于频繁集的算法研究。基 于频繁集的算法主要是a p r i o r i 算法，但是a p r i o r i 算法存在一些固有的缺陷无法克服， 而基于频繁集的另外一种算法是f p - g r o w t h 算法，能较好地解决a p r i o r i 算法存在的一些 问题。 挖掘关联规则的问题是在基于支持度一可信度框架中，找出所有满足用户给定的最 小支持度和最小可信度的关联规则，即挖掘出所有的强规则。该问题可分解为两个子问 题i l i ，即： ( 1 ) 找出所有的频繁项目集，即出现频率至少和预定义的最小支持度一样的项目集； ( 2 ) 由频繁项目集产生关联规则。 2 3 1 层次迭代算法 2 3 1 1 a p r i o r i 算法 a p r i o r i 算法1 6 l 是1 9 9 4 年r a b e s ha g r a w a l 等人提出的。该算法使用一种称之为逐层 迭代的候选产生测试的方法，k - 项目集用于探索( k + 1 ) 一项目集。首先，找出频繁1 项目集 的集合，该集合记作l l ，然后由l l 找出l 2 ，由l 2 找出l 3 ，如此下去，直到不能找到 频繁k 项目集为止。每找一层l k 均需要一次数据库扫描。 为了提高频繁项目集逐层产生的效率，一种称作a 州o r i 的重要性质可用于压缩搜 1 0 广西大掌罔等掌力申爿 硕士掌位论文| i 于f p t r e e 的崔毙规则挖期l 算法的研竞， 索空间。 性质2 1 ( a p r i o r i 性质) ：频繁项目集的所有非空子集都必须是频繁的。 a p r i o r i 性质应用在算法的以l k _ l 找k 过程中，该过程由连接和剪枝两个步骤组成： ( 1 ) 连接步：为找出l k ，通过l k 1 与自己连接产生候选k - 项目集的集合。该候选项目 集的集合记作c k 。c k = l k 1 口司l k 1 ，l k 1 中的两个元素是可连接的当且仅当这两个元素的 前k - 2 个元素相同。设l k - i = l l ，1 2 ，l 。 ，l i 和l j 0 i n ，1 j n ，i ：j ) 是其中的两 个元素，1 i = l i 1 ，l i 2 ，l i 【k 一1 】) ，l i 【m 】( 1 m k 1 ) 是项集l i 中的第m 个项， 若满足：( 1 i 1 】- b 【1 】) ( 1 i 【2 】= b 2 1 ) a ( 1 i 【k - 2 】；b k - 2 1 ) a ( 1 i k - 1 1 = l j k - 1 1 ) ，则有： l i 闻b = l i 1 ，l i 2 ，l i k - 1 ，l j k - 1 】) ，l i l l l j c k 。 ( 2 ) 剪枝步：由a p r i o r i 性质可知，任何非频繁的( k - 1 ) 项集不可能是频繁k 项集的子 集。设c k c k ，即c k 是一个侯选k 项集，c k 1 是c k 的一个o 卜1 ) 项子集，若满足：c k 1 垂l k 1 ， 则有：c k 幸l k ，即是说，侯选k - 项集c k 应该从侯选k 项集的集合c k 中删除。 例2 1 设有事务数据库d ，有9 个事务( 见表2 1 ) ，假设事务项按字典顺序存放。 t l d 项i d 的列表 t 1i l ，1 2 ，1 5 t 21 2 ，1 4 ”1 2 ，1 3 t 41 1 。1 2 1 4 t 5i l ，b t 6 1 2 ，1 3 t 71 1 ，1 3 t 81 1 ，1 2 ，1 3 ，1 5 t 9i l ，1 2 ，1 3 设最小支持度阈值为2 ，按算法的步骤依次求频繁项集，过程如图2 - 1 所示。 ( 1 ) 在算法的第一次迭代，每个项都是候选1 项集的集合c l 成员。算法简单地扫描 所有事务，对每个项的出现次数计数。 ( 2 ) 根据最小支持度阈值，确定频繁1 一项集的集合l l 。它由具有最小支持度的候选 1 项集组成。 ( 3 ) 为发现频繁2 一项集的集合l 2 ，算法使用l l 闻l l 产生候选2 项集的集合c 2 ，c 2 由c ；个2 项集组成。 ( 4 ) 扫描d 中事务，计算c 2 中每个候选项集的支持计数，如图2 1 中的第二行的中 广西大掌周等掌力申请硕士学位论文| l 于f p t r e e 的j 噍冉噱g 挖期b 算法的研摹巴 间表所示。 ( 5 ) 确定频繁2 项集的集合l 2 ，它由具有最小支持度的c 2 中的候选2 项集组成。 ( 6 ) 产生候选3 一项集的集合c 3 。首先，令c 3 = l 2 d 司l 2 = 1 1 ，1 2 ，1 5 ) ， i l ，1 3 ，1 5 ) ， 1 2 ，1 3 ，1 4 ) ， 1 2 ，1 3 ，1 5 ， 1 2 ，1 4 ，1 5 。根据a p r i o r i 性质，频繁项集的所有子集 必须是频繁的，我们可以确定后4 个候选不可能是频繁的。因此，我们把它们从c 3 中 删除，这样，在此后扫描d 确定l 3 时就不必在求它们的计数值。 ( 7 ) 扫描d 中事务，以确定l 3 ，它由具有最小支持度的c 3 中的候选3 项集组成( 如 图2 1 第三行所示) 。 ( 8 ) 算法使用l 3 闻l 3 产生候选4 - 项集的集合c 4 。尽管连接产生结果 1 1 ，1 2 ，1 3 ， 1 5 ) ) ，这个项集被剪去，因为它的子集 1 2 ，1 3 ，1 5 ) 不是频繁的。这样，c 4 = 中，因此算 法终止，找出了所有的频繁项集。 c lt ， 扫描d ，对每 个候选计数 由l l 产生候选c