（计算机应用技术专业论文）关联规则挖掘算法研究(2).pdf

西南交通大学硕士研究生学位论文第1 页 摘要 与传统的统计、查询方法相比，数据挖掘技术涉及到多个学科，汇集了人 工智能、模式识别、数据库、机器学习以及管理信息系统等学科的成果。数据 挖掘是一个新兴的边缘学科，其应用领域非常广泛，并且具有良好的应用前景。 本文对数据挖掘技术，尤其是关联规则数据挖掘技术进行了系统、深入地 学习和分析研究，主要包括以下内容： 关联规则研究与分析。在对现有关联规则文献的研究基础上，详细的介绍 了关联规则的基本概念和基本性质，并且对关联规则的典型挖掘算法及其基本 思想进行了归纳、分析和研究。 针对本文所要解决的闻题，对经典的关联规则挖摇算法一a d r i 鲥算法和 f p g r o w t h 算法进行了详细分析和研究。针对提高a p r i o r i 算法效率的各种优化 技术也在这里被详细地研究和讨论，为a p r i o r i 改进算法的提出和构造建立了理 论上的必要性前提。 n p r i o r i 改进算法的设计和分析研究。在前面几部分工作的基础上，本文提 出一个a p r i o r i 的改进算法，该算法主要考虑a p r i o r i 算法中频繁项目集生成的瓶 颈问题，采取了减少事务数据库扫描次数，压缩进一步迭代扫描的事务数等方 法对经典算法n p r i o r i 进行改进，通过一个实例，我们给出了运用a p r i o r i 改进算 法进行关联规则挖掘中发现频繁项集的过程。 a p r i o r i 改进算法的试验结果。在构造基于柏松分布函数和指数分布函数的 合成数据的基础上，对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 改进算法 西南交通大学硕士研究生学位论文第1 i 页 a b s t r a c t c o m p a r i n gw i t h t h et r a d i t i o n a ls t a t i s t i c a n d q u e r ym e t h o d s ，d a t am i n i n g c o n c e r n s m u l t i p l es u b j e c t s ，c o n g r e g a t i n g s o m er e s e a r c hr e s u l t so fa r t i f i c i a l i n t e l l i g e n c e ，p a t t e r nr e c o g n i t i o n ，d a t a b a s e ，m a c h i n e l e a r n i n g a n d m a n a g e m e n t i n f o r m a t i o ns y s t e m ，e t c d a t am i n i n gi san e w l y - e s t a b l i s h e df r o n t i e rs u b j e c t i ti s b e i n g u s e de x t e n s i v e l ya n di t sa p p l i c a t i o nf u t u r ei sb r i 曲t t h i st h e s i ss t u d i e sa n da n a l y s e st h ed a t am i n i n gt e c h n i q u es y s t e m a t i c a l l ya n d d e e p l y , e s p e c i a l l y f o ra s s o c i a t i o nr u l e s t h em a i nc o n t e n t sa r el i s t e da sf o l l o w s ： r e s e a r c ha n da n a l y s i so fa s s o c i a t i o nr u l e s b a s e do nt h er e s e a r c ho ft h ee x i s t e d d o c u m e n to fa s s o c i a t i o nr u l e s ，i nt h i sd i s s e r t a t i o n ，t h eb a s i cc o n c e p t sa n d p r o p e r t ya r e i n t r o d u c e dr o u n d l ya n di t st y p i c a lm i n i n ga l g o r i t h m sa n dt h e s ea l g o r i t h m s b a s i ci d e a s a r es u m m a r i z e d ，a n a l y s e da n ds t u d i e d f o rt h eq u e s t i o ns o l v i n gi nt h ed i s s e r t a t i o n ，t h ec l a s s i c a la l g o r i t h m s - - t h ea p r i o r i a l g o r i t h ma n df p - g r o w t ha l g o r i t h ma r ea n a l y s e da n ds t u d i e d a l lk i n d so fo p t i m i z e d t e c h n i q u e sw h i c h a r cd e s i g n e dt op r o m o t et h ea p r i o r ia l g o r i t h m se f f i c i e n c ya r ea l s o s t u d i e dh e r e a l lo ft h ea b o v er a t i o n a l l ye s t a b l i s ht h en e c e s s a r yp r e m i s ef o rt h e i m p r o v e da l g o r i t h m sp r o p o s i t i o na n d c o n s t r u c t i o n d e s i g n a n a l y s i sa n d r e s e a r c ho f t h ei m p r o v e da l g o r i t h mf o ra p r i o r i b a s e do nt h e w o r ka b o v e ，i nt h ed i s s e r t i o n ，t h ei m p r o v e da l g o r i t h mf o ra p r i o r ii sp u tf o r w a r d t h i s a l g o r i t h mm a i n l y t a k e si n t oc o n s i d e r a t i o nt h eb o t t l e n e c k p r o b l e mo ff r e q u e n ti t e m s e t s g e n e r a t i o n ，i ti m p r o v e st h ea p r i o r ia l g o r i t h mb y r e d u c eo fs c a nt i m e so ft r a n s a c t i o n d be t c s u c c e s s i v e l yt h ep r o c e s so fm i n i n ga s s o c i a t i o nr u l e su s i n gt h ei m p r o v e d a l g o r i t h mi si l l u s t r a t e dt h r o u g h a ni n s t a n c e e x p e r i m e n t a lr e s u l t so f t h ei m p r o v e da l g o r i t h m b a s e do n t h es y n t h e t i cd a t au s i n g p o s s i o nd i s t r i b u t i o nf u n t i o na n d e x p o n e n t i a l d i s t r i b u t i o nf u n c t i o n ，t h ep e r f o r m a n c eo f t h ei m p r o v e da l g o r i t h ma n dt h ec o m p a r i s o na m o n gt h ei m p r o v e d a l g o r i t h m ，a p r i o r i a l g o r i t h m a n df p g r o w t h a l g o r i t h m i s e x p e r i m e n t e d f i n a l l y t h er e s u l t so ft h e e x p e r i m e n t sa r ea n a l y s e d a l lo ft h ee x p e r i m e n t sr e v e a lg o o dp e r f o r m a n c eo ft h e i m p r o v e da l g o r i t h m 西南交通大学硕士研究生学位论文第页 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 n r u l e s m i n i n g ；c a n d i d a t e i t e m s e t st r e e i m p r o v e da l g o r i t h mf o ra p r i o r i 西南交通大学硕士研究生学位论文第1 页 1 1 数据挖掘简介 1 1 1 数据挖掘的定义 第1 章绪论 1 技术上的定义及含义 数据挖掘( d a t am i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、 随机的实际应用数据中，提取隐含在其中的、人们事先不知道的、但又是潜在 有用的信息和知识的过程【l 】。 与数据挖掘相近的同义词有数据融合、数据分析和决策支持等。这个定义 包括好几层含义：数据源必须是真实的、大量的、含噪声的；发现的是用户感 兴趣的知识：发现的知识要可接受、可理解、可运用；并不要求发现放之四海 皆准的知识，仅支持特定的发现问题。 2 商业角度的定义 数据挖掘是一种新的商业信息处理技术，其主要特点是对商业数据库中的 大量业务数据进行抽取、转换、分析和其他模型化处理，从中提取辅助商业决 策的关键性数据。 简而言之，数据挖掘其实是一类深层次的数据分析方法。因此，数据挖掘 可以描述为：按企业既定业务目标，对大量的企业数据进行探索和分析，揭示 隐藏的、未知的或验证已知的规律性，并进一步将其模型化的先进有效的方法。 3 数据挖掘与传统分析方法的区别 数据挖掘与传统的数据分析( 如查询、报表、联机应用分析) 的本质区别是 数据挖掘是在没有明确假设的前提下去挖掘信息、发现知识数据挖掘所得到的 信息应具有事先未知、有效和可实用三个特征。 先前未知的信息是指该信息是预先未曾预料到的，即数据挖掘是要发现那 些不能靠直觉发现的信息或知识，甚至是违背直觉的信息或知识，挖掘出的信息 越是出乎意料，就可能越有价值。在商业应用中最典型的例子就是一家连锁店通 过数据挖掘发现了小孩尿布和啤酒之间有着惊人的联系。 西南交通大学硕士研究生学位论文第2 页 1 1 2 数据挖掘研究内容和本质 随着d m k d ( d a t am i n i n g k n o w l e d g ed i c o v e r y ) 研究逐步走向深入，数 据挖掘和知识发现的研究已经形成了三大技术支柱：数据库、人工智能和数理 统计。因此，k d d 大会程序委员会曾经由这三个学科的权威人物同时来任主席。 目前d m k d 的主要研究内容包括基础理论、发现算法、数据仓库、可视化技术、 定性定量互换模型、知识表示方法、发现知识的维护和再利用、半结构化和非 结构化数据中的知识发现以及网上数据挖掘等。 数据挖掘所发现的知识最常见的有以下四类： 1 广义知识( g e n e r a l i z a t i o n ) 广义知识指类别特征的概括性描述知识。反映同类事物共同性质，是对数 据的概括、精炼和抽象。 广义知识的发现方法和实现技术有很多，如数据立方体、面向属性的归约 等。 2 关联知识( a s s o c i a t i o n ) 它反映一个事件和其他事件之间依赖或关联的知识。如果两项或多项属性 之间存在关联，那么其中一项的属性值就可以依据其他属性值进行预测。最为 著名的关联规则发现方法是r a g r a w a l 提出的a p r i o r i 算法。 3 分类知识( c l a s s i f i c a t i o n c l u s t e r i n g ) 它反映同类事物共同性质的特征型知识和不同事物之间的差异型特征知 识。最为典型的分类方法是基于决策树的分类方法。 数据分类还有统计、粗糙集( r o u g h s e t ) 等方法。最近也有人研究使用神 经网络方法在数据库中进行分类和规则提取。 4 预测型知识( p r e d i c t i o n ) 它根据时问序列型数据，由历史的和当前的数据去推测未来的数据，也可 以认为是以时间为关键属性的关联知识。 目前，时问序列预测方法有经典的统计方法、神经网络和机器学习等。 此外，还可以发现其他类型的知识，如偏差型知识( d e v i a t i o n ) ，它是对差 异和极端特例的描述，揭示事物偏离常规的异常现象，如标准类外的特例，数 据聚类外的离群值等。所有这些知识都可以在不同的概念层次上被发现，并随 着概念层次的提升，从微观到中观、到宏观，以满足不同用户不同层次决策的 需要。 西南交通大学硕士研究生学位论文第3 页 1 1 3 数据挖掘的应用 需要强调的是，数据挖掘技术从一开始就是面向应用的。目前，在科学研 究，商业等很多领域，数据挖掘( d a t am i n i n g ) 都是一个很时髦的词，尤其是在 如银行、电信、保险、交通、零售( 如超级市场) 等商业领域。数据挖掘所能 解决的典型商业问题包括：数据库营销( d a t a b a s em a r k e t i n g ) 、客户群体划分 ( c u s t o m e rs e g m e n t a t i o n c l a s s i f i c a t i o n ) 、背景分析( p r o f i l ea n a l y s i s ) 、 交叉销售( c r o s s s e l l i n g ) 等市场分析行为，以及客户流失性分析( c h u r n a n a l y s i s ) 、客户信用记分( c r e d i ts c o r i n g ) 、欺诈发现( f r a u dd e t e c t i o n ) 等 等。 1 1 4 数据挖掘的研究现状 从数据库中发现知识( k d d ) 一词首次出现在1 9 8 9 年举行的第十一届国际 联合人工智能学术会议上。目前为止，美国人工智能协会已经主办多次k d d 国 际研讨会。规模由原来的专题讨论会发展到国际学术大会，研究重点也逐渐从 发现方法转向系统应用，注熏多种发现策略和技术的集成，以及多种学科之间 的相互渗透。并行计算、计算机网络和信息工程等其他领域的国际学会、学刊 也把数据挖掘和知识发现列为专题和专刊讨论，甚至到了脍炙人口的程度。 与国外相比，国内对d m k d 的研究稍晚，没有形成整体力量。1 9 9 3 年国家自 然科学基金首次支持对该领域的研究项目。目前，国内的许多科研单位和高等 院校竟相开展知识发现的基础理论及其应用研究。其中，北京系统工程研究所 对模糊方法在知识发现中的应用进行了较深入的研究，北京大学也在开展对数 据立方体代数的研究，华中理工大学、复旦大学、浙江大学、中国科技大学、 中科院数学研究所、吉林大学等单位开展了对关联规则挖掘算法的优化和改造； 南京大学、四川大学和上海交通大学等单位探讨、研究了非结构化数据的知识 发现以及w e b 数据挖掘。 1 2 论文选题及工作 在数据挖掘领域，没有哪一种算法是全能的，每种算法都有其自身的优点和 缺点，在对应某一种模式的数据时可能会性能很好，但在应用到其他模式的数 据时就未必那么好用。正是由于数据挖掘中算法的这种特性，才使得国内国外 西南交通大学硕士研究生学位论文第4 页 众多的学者始终在孜孜不倦的研究并提出各种算法以针对具有不同特点的数据 进行更高效的挖掘。 数据挖掘所发现的知识比较重要的一个类别就是关联知识，关联规则挖掘在 金融，商业等领域的应用非常广泛，由于它在实际生活中的成功应用，也使得 关联规则挖掘成为数据挖掘中的一个研究热点。 基于以上的原因，本论文选择关联规则挖掘算法作为研究的重点。 本论文研究工作如下： 1 关联规则挖掘技术的分析与研究。 2 a p r i o r i 改进算法的设计，分析与研究。 3 实验数据的合成 4 a p r i o r i 改进算法的实验结果以及和现有算法的比较分析。 西南交通大学硕士研究生学位论文第5 页 第2 章关联规则 2 1 关联规则的有关概念和性质 关联规则是表示数据库中一组对象之间某种关联关系的规则，关联规则挖 掘的主要对象是交易( t r a n s a c t i o n ) 数据库。这种数据库的一个主要应用是零售业， 比如超级市场的销售管理。条码技术的发展使得数据的收集变得更容易、更完 整，从而可以存储大量的交易资料。关联规则就是辨别这些交易项目之间是否 存在某种关联关系。例如：关联规则可以表示购买了商品a 和b 的顾客中有8 0 的人又购买了商品c 和d ”。这种关联规则提供的信息可以用作商品目录设计、 商场货架的布置、生产安排、具有针对性的市场营销等。 2 1 1 项目集的定义及性质 本节将给出关联规则发现任务的一些基本定义。在定义关联规则以前首先 介绍频繁项目集( ( f r e q u e n tn e m s c t ) 的定义，频繁项目集是产生关联规则的基础。 1 项目集的定义 设i 为一个由m 个项目组成的集合i - “，i2 ，i 。 ，称为项目集( i t e m s e t ) 。 则交易t 为由i 中的项组成的i 的子集，即t c _ i 。与集合的定义一样，交易中同 样不存在重复的元素。假设本文中所涉及的交易及其它项目集合中的项目都已 经排序”1 。 设数据库d 是由n 个交易组成的集合，其中每个交易以一个交易标识号表 示其在数据库中的唯一性。 如果交易t 包含项目集x 中的所有项目，即x c _ t ，则称t 支持x 。t ( x ) 定义为所有支持x 的交易组成的集合。 项目集中所包含的项目数称为项目集的长度。每一个项目集都有一个统计 指标称为支持度( s u p p o a ) ，数据库d 中支持项目集x 的交易所占的比例称为x 在d 中的支持度，记为s u p p ( x ) 或s ( x ) 。设m i n s u p 为给定的最小支持度，如果 s u p p ( x ) 一m i n s u p ，则称项目集x 是频繁的( f r e q u e n t ) 。一个项目集的最小支持度 是该项目集被认为是有意义的。支持它的交易占数据库d 中所有交易总和的最 小比例，通常是根据经验来确定的。不具有最小支持度的项目集被认为是没有 西南交通大学硕士研究生学位论文第6 页 意义的。项目集中所包含的项目的个数称为它的长度或基数。长度为k 的项目 集称为k ( k = ix1 ) 维项目集，记为k i t e m s e t 。 2 项目集的性质 频繁项目集具有以下三个性质呤1 ，性质1 及3 是所有关联规则算法的基础。 性质1 ：子集支持 设a 和b 是两个不同的项目集，如果a c b ，则s u p p ( a ) 一s u p p ( b ) 。因为是 d 中所有支持b 的交易也一定支持a 。 性质2 ：非频繁项目集的超集也一定是非频繁的 如果a 在d 中不满足最小支持度条件，即s u p p ( a ) 一m i n c o n f , s u p p ( - r ) m i n s u p ， 则称关联规则r 关于数据库成立。规则的前项及后项必须是频繁的是一个关联 规则成立的必要条件。 个关联规则必须同时满足最小支持度和最小可信度条件，二者缺一不可。 如果一个规则的可信度为t 0 0 ，但是它描述的并不是数据库中的一个普遍模式， 由于它不满足最小支持度的约束，该规则也应该被删除。假设一个规则具有足 够大的支持度，但是可信度却很低，例如购买肥皂的顾客中2 的人也购买了水 果。这一事实虽然被数据库中的大部分数据支持。但是由于它不能表示出项目 间的较强的相关性，因此也不能作为一个关联规则存在。 规则前项及后项不相交条件并不是必须的：如果去掉这一约束条件不会产 生错误的规则，只是会产生冗余或没有意义的规则。如果x 辛y 是一个正确规 则，由于x 等x u y 与x j y 是等价的，因此规则x j x u y 就没有意义。规 则的前项x 可以是空集，每个交易都支持空项目集，因此接个数据库也支持空 项目集。前项为空集的规则的可信度等于后项目集的相对频度。同样道理规则 的后项y 必须是非空的项目集，并且前项和后项项目集不能相交。对交易t 来 说，规则r ：x 辛y 的可信度c o n f ( r ) 是一个条件概率，如果y - - o ，则c o n f ( 鼬= s u p p ( x u0 ) s u p p ( x ) = l 。这表明规则x j x 与x j 0 是等价的。 2 关联规则的性质 关联规则项目集具有以下四个性质【2 。 性质1 ：规则的非结合性 如果规则x j z 及y z 在d 中成立，规则x u y j z 不一定在d 中成立。 如果x n y = o ，并且d 中支持z 的所有交易都只支持x 或y ，则集合x u y u z 的支持度为0 ，因此x u y j z 的可信度为0 。 类似的，如果规则x j y 及x 等z 成立，规则x 等y u z 不一定成立。 性质2 ：规则的不可分解性 如果x u y j z 在d 中成立，规则x 等z 及y j z 不一定在d 中成立。例 如，当z 只出现在一个交易中时，如果x 及y 也出现在其中，即s u p p ( x u y l = s u p p ( z ) ，规则就是不可分解的。另外，如果x 与y 的支持度与x y 的支持度相比足 够大，就会使得分解后的两个规则不具有所要求的可信度，因而规则也不可分 解。 西南交通大学硕士研究生学位论文第8 页 因为s u p p ( x u y ) s u p p ( x u y u z ) 及s u p p ( x uz ) s u p p ( x u y u z ) ，所 以如果规则x j y u z 成立，则规则x j y 及x z 都成立。由此可得较小规 则的支持度与可信度与原规则相比都有所增大。 性质3 ：规则的不可传递性 由规则x j y 及y j z 成立不能推出规则x 等z 。设t ( x ) ct ( y ) c t ( z ) ， 最小可信度为m i n c o n ec o n f ( x j y ) = c o n f ( y ：，z ) = m i n c o n f 。 由t ( x ) c t ( y ) 可得c o n f ( x = y ) = s ( x u y ) s ( y ) = s ( x ) s ( y ) = m i n c o n f 由t c t ( z ) 可得c o n f ( y j z ) = s ( y u z ) s ( z ) ；s ( y ) s ( z 闩m i n c o n f 由t ( x ) c t ( z ) 可得c o n f 【x j z ) = s ( x v z ) s ( z ) = s ( x ) s ( z ) 由上面三个等式及m i n c o n f z ) = m i n c o n f 2 一s u p p ( a ) ， 再由可信度的定义可得c o n f f bj ( l - b ) ) = s u p p ( l ) s u p p 0 3 ) s u p p ( l ) s u p p ( a ) a p f i o f i 算法：该算法利用了项目集如下性质对数据库进行多趟扫描：任 意频繁项集的子集都是频繁项集；任意非频繁项集的超集都是非频繁项 集。第一趟扫描得到频繁一1 项集的集合l ，第k 趟扫描前先利用上趟 扫描的结果项目集l 。产生候选k 项集的集合c 。，然后再通过扫描数 据库确定对c 中每一候选k 项集的支持数，最后在该趟结束时求出频 繁k 项集的集合l 。，算法在c 。或l 。为空时终止。a p r i o r i 算法所产生 的候选项集比a i s 算法少的多，效率较高。事实上，它被视为关联规则 挖掘最经典的算法，其他很多算法都是它的变种或改进。 s e t m 算法：该算法实际也是a i s 算法的变形。s e t m 把候选集的产生和 累计分开，在一个线性存储结构里存储了所有候选集和相应的交易的标 识符( t i d ) 。每趟扫描结束后，不再读取数据库，而是对t i d 进行排序 并累计各个候选集的支持。其思想是扫描候选集的编码( t i d ) 来代替扫 描数据库，它实质上是把数据库中与支持有关的信息单独提取出来，构 成一个较小但充分的t i d 库。这种做法大大减少了数据库访问时间。但 西南交通大学硕士研究生学位论文第1 0 页 它的不足之处也是候选项集过大。 d h p 算法：该算法利用散列表( h a s ht a b l e ) 产生候选集，是对a p r i o r i 算法的直接改进。在遍历一次数据库得到候选k 一项目集的支持，得到 频繁k 一项目集后，d h p 算法将每一个事务的可能的( k + 1 ) 一项目集通过哈 希规则形成散列表。散列表的每一栏包括所有通过散列规则映射到该栏 中的项目集的数目。根据结果的散列表，可以生成一个位向量，当散列 表中对应的该栏中的数字大于或者等于最小支持时，对应的位置为1 ， 否则为0 。用该向量可以过滤掉下一次生成候选时所不必要的项目集： 如某候选在向量中对应位的值为0 ，则舍弃。这对候选2 一项目集的产生 尤为有效，可以在第二趟就大大减小候选集的规模。在某些场合，d h p 的效率比a p r i o r i 有明显提高。 p a r t i t i o n 算法：该算法主要针对大型数据库，可分为两个部分：( 1 ) 将目标数据库分为n 个互不相交的分数据库d 1 ，d ”，每个d ( i = l ，2 ，n ) 的大小都要能容纳在内存中。然后把每个d ，读入内存 并按一般算法发现频繁项集l 。再把所有的l 合并为数据库d 的潜在 频繁项集p l = u ；l ：( 2 ) 计算潜在频繁项集p l 在d 中的支持数，得 出频繁项集l 。 s a m p l i n g 算法：该算法的思想是，对数据库d 进行随机抽样得到抽样事 务数据库d ，先以小于指定的m i n s u p 的支持度挖掘d 中的频繁项集 l ，再在剩下的数据集d - d 中继续计算l 中各元素的支持数，最后再 以m i n s u p 求出l 。这在大部分情况下就可以求得所有的频繁项集，但 是有时会漏掉一些。这时可以对d 进行二次扫描以得出漏掉的频繁项 集。此算法多数情况下只需对d 进行一次扫描，最坏也只需扫描两次。 f p g r o w t h 算法【l 】：该算法主要是为了克服类a p r i o r i 算法的产生候选 项集的缺点，通过采用一种新的数据结构f p t r e e ，来达到目的。该算 法只扫描数据库二次，并且不用产生候选项集，提高了效率。 2 3 关联规则挖掘算法的优化技术 目前已经提出了许多a p r i o r i 算法的变形，其中采取了多种算法的优化技术 以提高算法的效率”1 。由于本文提出的算法属于有候选项集一类，所以本文仅限 西南交通大学硕士研究生学位论文第1 1 页 讨论基于a p r i o r i 的优化方法。 1 基于散列的优化方法 基于散列( h a s h - b a s s e d ) 的优化方法可以用于压缩候选k 一项集的集合c 。( k 2 ) 的大小。基本思想：当扫描事务数据库，由候选k 一项集产生频繁k 一项集 的时候，同时产生每个事务的( k + 1 ) 项子集，并把它们散列到散列表的不同桶 中，增加桶的计数，在下次产生候选k + 1 ) 一项集的时候，可以根据散列表和最小 支持度排除一些无意义的候选项集。这种技术当k = 2 时特别有效。它的关键是 构造一个有效的散列函数。 2 基于事务压缩的优化方法 基于事务压缩( t r a n s a c t i o nr e d u c t i o n ) 优化方法通过减少不必要的事务来减 小扫描的事务数据库的大小，以提高挖掘的效照。一个基本的原理就是当一个 事务不包含任何k 项集的时候，它必然不可能包含任何( 1 【+ 1 ) 项集，从而我们可 以将这些事务删除，因为在为产生( k + 1 ) 项集而扫描事务数据库的时候已经不再 需要它们了。 3 基于划分的优化方法 基于划分( p a r t i t i o n i n g ) 的优化方法采用对原数据库进行两遍扫描的技术。 在第一遍，首先将事务数据库划分成n 个非重叠的部分，每个部分的最小主持 度等于整个事务数据库的最小支持度与该部分的事务数之积。对于每一个部分， 找出该部分的频繁项集，称作局部频繁项集。局部频繁项集可能不是整个事务 数据库的频繁项集，接个事务数据库的任何一个频繁项集必须作为局部频繁项 集至少出现在一个部分中。这样，把所有局部频繁项集的集合作为事务数据库 的候选项集，称作全局候选项集。再次扫描事务数据库，根据全局候选项集和 实际最小支持度确定全局频繁项集。每部分的大小和划分的数目由是否能够把 该部分放入内存来确定。 4 基于采样的优化方法 基于采样( s a m p l i n g ) 的优化方法是在一个给定数据库的随机样本中进行挖 掘，这种方法牺牲了精确性以换取有效性，样本的大小由是否能够把它放入内 存来确定。样本中的频繁项集不一定是数据库中的频繁项集，而且，数据库中 的频繁项集不一定出现在样本的频繁项集中，因此，应该使用比事务数据库最 小支持度低的支持度值来搜索样本中的频繁项集，之后，通过数据库的其余部 分再来计算每个项集的实际频繁度。当效用是决定因素的时候，采样方法比较 合适。 西南交通大学硕士研究生学位论文第1 2 页 5 基于动态项集计数的优化方法 基于动态项集计数( d y n a m i ci t e m s e tc o u n t i n g ) 的优化方法将数据库划分为 标记开始点的块，算法可以在任何开始点添加新的候选项集。该技术动态地评 估已被计数的所有项集的支持度，如果一个项集的所有子集已被确定为频繁的， 则添加它作为新的候选项集。该方法对数据库扫描次数比a p r i o r i 算法少。 西南交通大学硕士研究生学位论文第1 3 页 第3 章a p r i o ri 算法与f p g r o w t h 算法的分析研究 在数据挖掘领域，没有哪一种算法是全能的，每种算法都有其自身的优点和 缺点，在对应某一种模式的数据时可能会性能很好。但在应用到其他模式的数 据时就未必那么好用。正是由于数据挖掘中算法的这种公共特性，才使得国内 国外众多的学者始终在孜孜不倦的研究并提出各种算法以针对具有不同特点的 数据进行更高效的挖掘。 本章中，我们对现有关联规则挖掘方法中两个重要的方法进行详细深入的 分析和研究，在此基础之上。我们在后续章节中提出了一个新的算法，并且对 这三个算法利用人工合成数据进行试验。 3 1 有候选项集产生的算法 a p r i o r i 是有候选项集产生算法的代表，具有十分重要的地位根据关联规 则和频集的定义，频繁集中应该存储了挖掘关联规则所需的全部信息，因此， 得到一个完整的、正确的频集是产生关联规贝蟾前提。a p r i o r i 算法核心思想是 任何频集的所有子集定是频集。其算法实现由发现所有频集和产生规则两部 分组成。 3 1 1 a p r i o r i 算法 f l = ( 1 a r g el - i t c m s e t s ) = f o r ( k = 2 = fi l m ：l 。h ) d ob e g i n c t = a p r i o r i - g e n ( f ) ；新的候选集 f o ra l lt r a n s a c t i o nt dd o b c g m c ，= s u b s c t ( c i ，t ) ；事务t q 3 g 含的候选集 f o ra l lc a n d i d a t ec c d o c c o u n t + + ： e n d l k2 ( c e c i c c o u n t m i n s u p ) e n d 亘童奎塑盔兰堡主塑塞圭兰垡迨銮 笙! 兰戛 - - - _ - _ _ _ _ _ l - _ _ - - _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ l _ _ _ _ _ - _ - - - _ _ - _ _ _ _ _ _ _ _ _ _ _ _ - _ _ _ _ _ 。一一一 a l l s w c r - u 这里，由于从候选项集中产生频集的过程需要遍历数据库，因此正确地产生 最少数目的候选项集是关键候选项集产生的过程a p r i o r i g e n ( f 。) 被分为两部 分：联合与剪枝。 根据a p r i o r i 算法的基本观点，对任意有k 个项的频集f 。，有k 个长度为k 一1 的子集f 。必定都是频集因此，长度为k 的频集可以用以下方法得到：对于两个 长度为k l 的频集f 。和f ：，其中f = ( i ，i2 ，i 。，i 。) ，f2 。 ( j l ，j2 ，j “，j “) ，若在f l 和f2 中，i 1 2 j 1 ，i2 = j2 ，i h 2 j ，只有 i 。- 4j 。，那么可以得到一个长度为k 的集合c ，称其为候选项集，c = ( i ，i2 ，i 。，i 。，j 。) 采用这种方式，使得所有的频集既不会遗漏又不 会重复。 剪枝的目的是减少扫描数据库时需要比较的候选项集的数量剪枝的原则： 候选项集c 的k 个长度为k i 的子集都在f 。中，则保留c ，否则c 被剪枝。 3 1 2a p r i o r i 算法的特点及局限性 h p r i o r i 算法利用候选项集和频集的相互作用，得到了全部频集，并通过对 候选项集的剪枝，大大地减少了候选项集的尺寸，获得了令人满意的结果。然 而，当面对挖掘对象具有繁多的频繁模式、长模式或者用户给定的最小支持度 的阈值较低时，a p r i o r i 算法仍然有可能因为如下两个方面的巨大开销而面临困 境。 ( 1 ) 在处理大量的候选项集方面，如果算法得到了大量的1 项频集，那么， 在产生2 项候选集时，会遇到大量2 项候选集难以处理的情况。例如：假设算 法得到的1 项频繁集的数量是1 04 ，则根据a p f i o f i 算法，会产生超过1 07 个2 项候选集，由于2 项候选集没有剪枝，所以所有这些候选项集都需要检验。此 外，在面对频繁模式的尺寸较大时，同样会产生大量的候选项集需要检验。在 内存等其它条件都为理想状态的情况下，这种由产生候选项集的方法内在属性 所决定的开销，无论采用什么实现技术都无法回避。所以，在有大量候选项集 产生的情况下，a p r i o r i 类的算法基本无法运行。 ( 2 ) a p r i o r i 算法采用的模式匹配方式，在检测大量的候选项集，特别是在 挖掘长模式时，对数据库的重复扫描非常冗长，大量的时间消耗在内存与数据 西南交通大学硕士研究生学位论文第1 5 页 库中的数据交换上。 由于上述两点原因，可以发现a p n o n 类算法的瓶颈就是候选项集的产生和 测试过程如果有一种算法能够对产生大量的候选项集进行有效的控制，那么 挖掘过程所消耗的时间将会极大地缩小。 3 2 无候选项集产生的算法 由于依赖于候选项集产生频集的理论所开发的算法具有先天的弱点，使得在 基于a p n o n 算法基础上开发的应用没有实质性突破而由h a n 等提出的一种新 的算法理论，用一种压缩的数据结构( f p - t r e e ) 口- f 存储关联规则挖掘所需的全部数 据信息，通过对源数据的两次扫描，将数据信息存到这种结构里，避开了产生 候选项集的步骤，极大地减少了数据交换和频繁匹配的开销。这就是所谓无候 选项集产生算法( f r e q u e n t p a t t c m sg r o w t h ，f p - - g r o w t h ) 。 3 2 1 f p g r o w t h 算法 f p - - g m 一d a 算法口”通过如下三方面的改进与创新，脱离了必须产生候选项 集的传统方式，开辟了关联规则挖掘的新思路。 ( 1 ) 它构造了一种新颖的、紧凑的数据结构f p t r e e 。它是一种扩展的前缀 树结构。存储了关于频繁模式数量的重要信息。树中只包含长度为l 的频繁项 作为叶节点，并且那些频度高的节点更靠近树的根节点，因此，频度高的项比 那些频度低的项有更多的机会共享同个节点。 ( 2 ) 开发了基于f p t r e e 的模式片断成长算法，它从长度为1 的频繁模式 开始，只检查它的条件模式基构建它的条件模式树，并且在这个树上递归地执 行挖掘。模式的成长通过联合条件模式树新产生的后缀模式实现。由于事务处 理中的频繁项都对应着频繁树中的路径进行编码，模式的成长确保了结果的完 整性。因此，f p t r e e 算法不象a p r i o r i 类算法那样需要产生再测试。挖掘的主 要操作是计算累加值和调整前缀树，这种花费通常要远远小于a p r i o r i 类算法 中的候选项集的产生和模式匹配操作。 ( 3 ) 挖掘过程中采用的搜索技术是基于分区的，通过分割再解决的方法，而 不是a p r i o r i 类算法的自下向上地产生频繁模式的集合。它通过将发现长频繁 模式的问题转化成寻找短模式然后再与后缀连接的方法，避免了产生长候选项 集。 1 f p t r e e 的构造方法 西南交通大学硕士研究生学位论文第1 6 页 f p t r e e 的结构包括一个标识成“n u l l ”的根、一个由频繁项组成的头表和 一组项的前缀予树组成了根的子孙。树中的每个节点包括3 个域：项名 ( i t e m n a m e ) 、计数( c o u n t ) 和节点链接( n o d e i i n k ) 。其中，项名记录了节点所 代表的项；计数记录了树中到达这个节点的路径所代表的事务处理的数目；节 点链接指向树中下一个同名节点，如果没有同名节点则指向空。头表中的每条 记录包含两个域：项名和节点链接的头。节点链接的头指向树中第一个同名的 节点。 f p t r e e 中只保存了满足最小支持度的项的集合，所以，首先需要知道哪些 项符合条件，这就是构造头表的工作。对源数据进行第一次扫描得出满足最小 支持