（计算机系统结构专业论文）基于元素增长搜索策略的频繁闭模式挖掘算法的研究与实现.pdf

、 “ at h e s i sf o rt h ed e g r e eo fm a s t e ri nc o m p u t e ra r c h i t e c t u r e 4 r e s e a r c ha n di m p l e m e n t a t i o no nf r e q u e n t c l o s e dp a t t e r nm i n i n g a l g o r i t h mb a s e d o n e l e m e n t i n c r e a s i n gs e a r c h i n gs t r a t e g y b ym ox i a o j i n g s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rs i i il a n n or l ：h e a s t e r nu n i v e r s i t y d e c e m b e r2 0 0 7 独创性声明 本人声明，所呈交的学位论文是在导师的指导下完成的。论文中取得 的研究成果除加以标注和致谢的地方外，不包含其他人己经发表或撰写过 的研究成果，也不包括本人为获得其他学位而使用过的材料。与我一同工 作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 ：屯 思o 学位论文作者龋毵勃桕 日期：彻嘭，形j 学位论文版权使用授权书 本学位论文作者和指导教师完全了解东北大学有关保留、使用学位论 文的规定：即学校有权保留并向国家有关部门或机构送交论文的复印件和 磁盘，允许论文被查阅和借阅。本人同意东北大学可以将学位论文的全部 或部分内容编入有关数据库进行检索、交流。 ( 如作者和导师不同意网上交流，请在下方签名；否则视为同意。) 学位论文作者签名： 签字日期： 导师签名： 签字日期： 专 一 、 东北大学硕士学位论文摘要 基于元素增长搜索策略的频繁闭模式挖掘算法的研究与实现 摘要 随着数据库技术的飞速发展以及人们获取数据手段的多样化，人类所拥有的数据急 剧增加，如何从规模越来越大的数据库中提取出人们感兴趣的信息以及知识，即数据挖 掘技术早已成为计算机科学的热门研究领域。关联规则挖掘是数据挖掘研究领域中的重 要分支，用于挖掘反映数据库中一组数据项之间的某种潜在关系的规则，具有重要的研 究价值以及应用价值。 频繁模式挖掘技术是关联规则挖掘技术中的关键步骤，其效率对整个关联规则挖掘 的效率起着决定作用。以往的研究工作主要集中在基于深度优先搜索策略的挖掘算法的 研究上，而对其它搜索策略下的挖掘算法以及频繁模式存储结构的研究很有限。针对以 上的研究现状，本文首先提出了两种新的存储频繁模式的数据结构：后缀树和有序图， 并且提出了在后缀树和有序图上进行集合的查找、添加以及删除操作的算法，经实验证 明，这两种存储的结构的性能优于以往的频繁模式存储结构。本文还提出了一个新的挖 掘频繁闭模式的算法：e i s a m 算法。e i s a m 算法没有采用传统的深度优先或广度优先 的搜索策略，而是提出了一种新的搜索策略：元素增长搜索策略，从而使算法具有增量 维护的特性。为了进一步提高算法的性能，还提出了高效的削减策略以及预处理优化技 术，使算法具有更加广泛的适用性。实验结果表明，e i s a m 算法的性能优于以往的频 繁闭模式挖掘算法。 本文首先对相关背景知识以及以往的研究工作进行简要介绍，然后提出后缀树和有 序图的存储结构以及有关操作的算法，接着提出了基于元素增长搜索策略的e i s a m 算 法，最后通过实验测试了提出的存储结构以及算法的性能。 关键词：频繁闭模式；后缀树；有序图：元素增长；e i s a m ，0 _ _ _ _ _ _ _ 一 东北大学硕士学位论文 a b s t r a c t r e s e a r c ha n d i m p l e m e n t a t i o n o nf r e q u e n t c l o s e dp a t t e r nm i n i n g a l g o r i t h m b a s e do n e l e m e n t i n c r e a s i n gs e a r c h i n gs t r a t e g y a b s t r a c t t h ea m o u n to fd a t ai si n c r e a s i n gr a p i d l yw i t ht h ef a s td e v e l o p m e n to fd a t a b a s et e c h n i q u e a n dt h ed i v e r s i f i c a t i o no fm e t h o d so fa c q u i r i n gd a t a h o wt oe x t r a c tu s e f u li n f o r m a t i o na n d k n o w l e d g ef r o mh u g e ra n dh u g e rd a t a b a s eh a sa l r e a d yb e e nah o tr e s e a r c hf i e l do fc o m p u t e r s c i e n c et e c h n i q u e ，w h i c hi st h ed a t am i n i n gt e c h n i q u e a s s o c i a t er u l e sm i n i n gi sa ni m p o r t a n t b r a n c ho fd a t am i n i n gf i l e d a s s o c i a t er u l e sm i n i n g ，w h i c hh a sg r e a tr e s e a r c hv a l u ea n d a p p l i c a t i o nv a l u e ，i st om i n er u l e sr e f l e c t i n gs o m ed e e pr e l a t i o n s h i po fi t e m si nad a t a b a s e m i n i n gf r e q u e n tc l o s e dp a r e m si sap i v o t a ls t e po fa s s o c i a t er u l e sm i n i n g ，w h i c h d e t e r m i n et h ee n t i r ep e r f o r m a n c eo fa s s o c i a t er u l e sm i n i n g p r e v i o u sr e s e a r c hw o r km a i n l y f o c u s e do na l g o r i t h m sb a s e do nd e p t hf i r s ts e a r c h i n gs t r a t e g y , a n dv e r yl i m i t e dr e s e a r c h e s w e r ed o n eo na l g o r i t h m sb a s e do no t h e rs e a r c h i n g s t r a t e g i e sa n dt h es t o r a g es t r u c t u r eo f f r e q u e n tp a r e m s a c c o r d i n gt ot h er e a s a r c hs t a t u sm e n t i o n e da b o v e ，t h i st h e s i sf i r s tp r o p o s e s t w on o v e ld a t as t r u c t u r e sf o rf r e q u e n tp a a e r n s s t o r a g e ：s u f f i xt r e ea n do r d e r e dg r a p h , a n d p r o p o s e sa l g o r i t h m so fq u e r yas e t ，a d das e ta n dd e l e t eas e to ns u f f i xt r e ea n do r d e r e d g r a p h e x p e r i m e n t a lr e s u l t ss h o wt h a tt h et w os t o r a g es t r u c t u r e sb o t hp e r f o r mb e r e rt h a n p r e v i o u ss t o r a g es t r u c t u r e s t h i st h e s i sa l s op r o p o s e san o v e la l g o r i t h mo ff r e q u e n tc l o s e d p a t t e r nm i n i n g ：e i s a ma l g o r i t h m t h ea l g o r i t h mu s e san o v e ls e a r c h i n gs t r a t e g y ：e l e m e n t i n c r e a s i n gs e a r c h i n gs t r a t e g yi n s t e a do fu s i n gt h et r a d i t i o n a ld e p t hf i r s to rb r e a d t hf i r s t s e a r c h i n gs t r a t e g i e s ，w h i c hm a k e se i s a ma l g o r i t h mh a st h e p r o p e r t y o fi n c r e m e n t m a i n t e n a n c e e f f i c i e n tp r u n i n gr u l e sa n dp r e - p r o c e s st e c h n i q u e sa r ea l s op r o p o s e di no r d e rt o i m p r o v et h ep e r f o r m a n c eo ft h ea l g o r i t h m ，w h i c hm a k et h ea l g o r i t h mu s e f u lu n d e rm o r e s i t u a t i o n s e x p e r i m e n t a lr e s u l t ss h o wt h a tt h ep e r f o r m a n c eo fe i s a m a l g o t i t h mi sb e a e rt h a n p r e v i o u sa l g o r i t h m s t h i st h e s i sf i r s tb r i e f l yi n t r o d u c e st h eb a c k g r o u n dk n o w l e d g ea n dp r e v i o u sw o r k ，a n d t h e np r o p o s e st h es t r u c t u r e so fs u 珩xt r e ea n do r d e r e dg r a p h a n do p e r a t i o n sr e l a t e d t h e e i s a ma l g o r i t h mb a s e do ne l e m e n ti n c r e a s i n gs e a r c h i n gs t r a t e g yi sp r o p o s e dn e x t ，a n da tl a s t e x p e r i m e n t sw e r ed o n ei no r d e rt ot e s tt h ep e r f o r m a n c e so ft h es t o r a g es t r u c t u r e sa n dt h e a l g o r i t h m k e y w o r d s ：f r e q u e n tc l o s e dp a t t e r n ；s u f f i xt r e e ；o r d e r dg r a p h ；e l e m e n ti n c r e a s i n g ；e i s a m i i i 一 1 k t 东北大学硕士学位论文目录 目录 独创性声明i 摘要i i a b s t r a c t i i i 第一章绪论1 1 1 数据挖掘技术概述1 1 1 1 数据挖掘的概念及主要研究方向1 1 1 2 数据挖掘技术的应用一2 1 2 关联规则挖掘技术概述3 1 2 1 关联规则挖掘的基本概念4 1 2 2 关联规则挖掘的研究方向4 1 2 3 关联规则挖掘面临的挑战5 1 3 论文组织结构6 第二章相关研究工作7 2 1 频繁模式挖掘技术概述7 2 1 1 频繁模式挖掘在关联规则挖掘中的重要性7 2 1 2 频繁模式挖掘的研究现状一8 2 2 频繁模式挖掘算法9 2 2 1a p r i o r i 算法1 0 2 2 2f p 。g r o w t h 算法11 2 2 3c l o s e t 算法l3 2 2 4d m i n e r 算法1 6 2 3 频繁模式挖掘的研究方向以及面临的挑战1 9 2 4 本章小结2 0 第三章频繁模式的存储结构2 1 3 1 频繁模式的概念2 1 3 2 频繁模式的后缀树存储结构2 1 3 2 1 后缀树的结构2 2 3 2 。2 后缀树的操作2 3 3 2 3 后缀树的性能分析2 6 3 3 频繁模式的有序图存储结构2 8 3 3 1 有序图的结构2 8 一一 东北大学硕士学位论文目录 3 3 2 有序图的操作3 0 3 3 3 有序图的性能分析3 7 3 4 本章小结3 8 第四章频繁闭模式挖掘算法e i s a m 3 9 4 1 频繁闭模式挖掘的问题描述3 9 4 2e i s a m 算法概述4 0 4 2 1e i s a m 算法的搜索策略4 0 4 2 2e i s a m 算法与以往算法的比较4 3 4 3e i s a m 算法的削减规则4 5 4 3 1 削减规则的提出4 5 4 3 2 削减规则对算法性能的提升4 6 4 3 3 削减规则的实现4 8 4 4e i s a m 算法提高性能的预处理技术5 0 4 4 1 选择枚举对象5 0 4 4 2 按项目支持度递增排序5 0 4 4 3 处理特殊的项目51 4 5 本章小结5 2 第五章实验及结果分析5 3 5 1 实验环境及实验数据集5 3 5 2 存储结构性能测试5 3 5 2 1 压缩效率测试5 4 5 2 2 操作效率测试5 5 5 3 削减规则及预处理性能测试5 6 5 4e i s a m 算法与其它算法性能比较5 8 5 4 1 改变阈值参数5 8 5 4 2 改变数据集规模6 0 5 5 本章小结6 1 第六章结论6 3 6 1 本文工作总结6 3 6 2 今后工作展望6 3 参考文献6 5 致谢6 9 攻读硕士期间发表的论文一7 1 一v 一 东北大学硕士学位论文第一章绪论 第一章绪论弟一早珀下匕 随着数据库技术的飞速发展以及人们获取数据手段的多样化，人类所拥有的数据急 剧增加，可是目前用于对这些数据进行分析处理的工具却很少。数据库系统所能做到的 只是对数据库中已有的数据进行存取和简单的操作，人们通过这些数据所获得的信息量 仅仅是整个数据库所包含的信息量的很少一部分，隐藏在这些数据之后的更重要的信息 是关于这些数据的整体特征的描述及对其发展趋势的预测，这些信息在决策制定的过程 中具有重要的参考价值。需求是发展之母，人们对隐藏在数据之后的信息的迫切需求促 使了数据挖掘这一技术的诞生。 1 1 数据挖掘技术概述 数据挖掘是2 0 世纪9 0 年代中期兴起的一项新技术，它是知识发现过程中的关键步 骤。国内外学术界和企业界，都非常重视对数据挖掘技术和软件工具的研究和开发。数 据挖掘是多门学科和多种技术相结合的产物，也是一个非常年轻而又活跃的研究领域。 1 1 1 数据挖掘的概念及主要研究方向 数据挖掘是知识发现的核心工作。1 9 8 9 年8 月，在美国底特律召开的第1 l 届国际 人工智能联合会议的专题讨论会上，首次提出知识发现，即k d d ( k n o w l e d g ed i s c o v e r y i nd a t a b a s e ) 技术的概念。它是一门交叉性学科，涉及机器学习、模式识别、统计学、 智能数据库、知识获取、数据可视化、高性能计算、专家系统等领域，内涵极为广泛， 理论和技术难度很大，从而使针对大型数据库的k d d 技术一时还难以满足应用需要。 于是，1 9 9 5 年的美国计算机学会会议提出了数据挖掘( d a t am i n i n g ) 的概念，它形象 地把大型数据库看成是存放有价值信息的矿藏，通过有效的知识发现技术，从中挖掘或 开采出有用的信息。 自从数据挖掘概念的提出以来，其定义随着人们研究的不断深入也在不断完善，但 由于定义者的观点和背景不同，目前还没有一个统一的标准定义。下面给出一个目前比 较公认的定义：数据挖掘就是从大量的、不完全的、有噪声的、模糊的、随机的实际应 用数据中，发现隐含的，规律性的、人们事先未知的、但又潜在有用的并且最终可理解 的信息和知识的过程。 数据挖掘的主要研究方向有六个方面：关联分析、时序模式、聚类、分类、偏差检 测以及预测【3 1 1 ，下面分别简述其主要研究内容： ( 1 ) 关联分析：关联分析是从数据库中发现知识的一类重要方法。若两个或多个数 一1 一 东北大学硕士学位论文第一章绪论 据项的取值之间重复出现且概率很高时，就存在某种关联，可以建立起这些数据项的关 联规则。例如，买面包的顾客有9 0 的人还买牛奶，这就是一条关联规则。若商店中将 面包和牛奶放在一起销售，将会提高它们的销量。 ( 2 ) 时序模式：通过时间序列搜索出重复发生概率较高的模式。这里强调时间序列 的影响。例如，在所有购买了激光打印机的人中，半年后8 0 的人再购买新硒鼓，2 0 的人用旧硒鼓装碳粉；在所有购买了彩色电视机的人中，有6 0 的人再购买v d c 产 品。 ( 3 ) 聚类：数据库中的数据可以划分为一系列有意义的子集，即类。在同一类别中， 个体之间的距离较小，而不同类别的个体之间的距离偏大。聚类增强了人们对客观现实 的认识，即通过聚类建立宏观概念。例如鸡、鸭、鹅等都属于家禽。 ( 4 ) 分类：分类是数据挖掘中应用得最多的任务。分类是找出一个类别的概念描述， 它代表了这类数据的整体信息，即该类的内涵描述。一般用规则或决策树模式表示。该 模式能把数据库中的元组映射到给定类别中的某一个。 ( 5 ) 偏差检测：偏差检测即检测数据库中的数据存在的异常情况，包括分类中的反 常实例、模式的例外、观察结果对模型预测的偏差、量值随时间的变化等。偏差检测的 基本方法是寻找观察结果与参照之间的差别。观察结果常常是某一个域的值或多个域值 的汇总。参照是给定模型的预测、外界提供的标准或另一个观察。 ( 6 ) 预测：预测是利用历史数据找出变化规律，建立模型，并用此模型来预测未来 数据的种类、特征等。典型的方法是回归分析，即利用大量的历史数据，以时间为变量 建立线性或非线性回归方程。预测时只要输入任意的时间值，通过回归方程就可求出该 时间的状态【z j 。 1 1 2 数据挖掘技术的应用 自从数据挖掘技术产生以来，许多优秀的科研人员投入了大量的精力致力于数据挖 掘技术的研究，取得的成果也十分丰硕。尽管数据挖掘技术尚未完全成熟，但是它在一 些领域中的成功应用，鼓舞着人们将数据挖掘应用到更多、更广泛的领域中去。根据著 名的数据挖掘网站k d n u g g e t s ( h t t p ：k d - n u g g e t s t o m ) 所做的一个投票调查结果，可以 大致地了解目前数据挖掘应用领域的分布情况，见表1 1 。 随着数据挖掘应用的日益广泛，数据挖掘技术的研究也越来越受到重视，其发展的 速度也越来越快。下面是对数据挖掘技术的发展趋势的展望【3 j ： ( 1 ) 数据挖掘的应用范围将会更广，门槛日益降低。 ( 2 ) 数据挖掘将成为企业信息系统基础设施的一种标准能力。 ( 3 ) 数据挖掘将作为一项隐含的功能部件嵌入到智能软件系统中。 一2 一 东北大学硕士学位论文第一章绪论 表1 1 数据挖掘的应用 t a b l e1 1a p p l i c a t i o no fd a t am i n i n g ( 4 ) 数据挖掘过程将走向标准化。 ( 5 ) 数据挖掘的全面可视化。 ( 6 ) 处理大量数据的能力。 ( 7 ) 数据挖掘将致力于研究多媒体数据、文本数据、地理空间数据等复杂数据类型 的处理技术。 ( 8 ) w e b 挖掘将成为数据挖掘中一个最重要和最繁荣的领域。 ( 9 ) 保护隐私的数据挖掘研究有着独特的重要意义。 1 2 关联规则挖掘技术概述 关联规则是数据挖掘的众多知识类型中最为典型的一种1 1 1 。关联规则挖掘问题是 r a g r a w a l 等人【4 1 首先提出来的，是描述数据库中一组数据项之间的某种潜在关系的规 则。其最初的应用是在商务领域的购物篮分析，通过对数据库中的销售记录进行分析， 提取出反映顾客购物习惯和偏好的有用规则，对于企业制定生产销售策略、产品分类设 一气一 东北大学硕士学位论文第一章绪论 计、产品摆放、市场分析以及市场营销策略等方面都是很有价值的。随着关联规则研究 的进展，其应用也涉及工程、医疗保健、生物信息学、金融证券分析、电信和保险业等 在占 守o 1 2 1 关联规则挖掘的基本概念 关联规则所挖掘的数据库可看作是一组事务( t r a n s a c t i o n ) 的集合，其中每一个事 务又是一组项目( i t e m ) 的集合。这里用d 表示数据库，用t 表示一个事务，用i 表示 一个项目，下面给出关联规则挖掘的相关定义： 定义2 1设i = i l ，i 2 ，i p ) 是d 中全体项目组成的集合，i 的任何子集x 称为d 中的 项目集( i t e m s e t ) ，若ix i _ k ，称集合x 为k 项集。设t 为d 中的一个事物，如果x c t ， 称事物t 包含项目集x 。 定义2 2 数据集d 中包含项目集x 的事物的数目称为x 的支持数，记为仃r 。项 目集x 的支持度记为s u p p o r t ( x ) ，s u p p o r t ( x ) = 听ld 1 ，即d 中包含项目集x 的事物 所占的百分比。 定义2 3 关联规则( a s s o c i a t i o nr u l e ) 可以表示为：x j y ，其中，x c i ，y c i ， 并且x n y g ，它表示如果项集x 在某一事务中出现，则必然会导致项集y 也会在同 一事务中出现。x 称为规则的先决条件，y 称为规则的结果。 定义2 4 关联规则x j y 的支持度，记为s u p p o r t ( x j y ) ，是数据库中包含x u y 的事务占库中所有事务的百分比。即s u p p o r t ( x j y ) = s u p p o r t ( x u y ) 。 定义2 5 关联规则x j y 的置信度c o n f i d e n c e ( x jy ) 是包含x t oy 的事务数与包 含x 的事务数的比值。即c o n f i d e n c e ( x j y ) = s u p p o r t ( x t j y ) s u p p o r t ( x ) 。 关联规则挖掘问题就是找出满足最小支持度和最小置信度的所有关联规则。假设用 户给定的最小支持度为s ，最小置信度为c ，关联规则挖掘问题就是找出所有的关联规 则x j y ，满足s u p p o r t ( xy ) 芝s 并且c o n f i d e n c e ( x j y ) 芝c 。 1 2 2 关联规则挖掘的研究方向 根据不同的标准，关联规则的研究可以分为以下的研究方向【2 】： ( 1 ) 根据规则中所处理的值的类型可分为： 布尔型关联规则：布尔型关联规则处理的值都是离散的、种类化的，它显示了这些 变量的存在与否。例如：性别= “女”一职业= “秘书”是布尔型关联规则。 数值型关联规则：数值型关联规则可以和多维关联或多层关联规则结合起来，对数 值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理，当然数值 型关联规则中也可以包含种类变量。例如性别= “女”_ a v g ( 收入) = 2 3 0 0 是数值型关联 一4 一 东北大学硕士学位论文第一章绪论 规则。 。 ( 2 ) 根据规则中数据的抽象层次可分为： 单层关联规则：在单层的关联规则中，所有的变量都没有考虑到现实的数据是具有 多个不同的层次的。 多层关联规则：在多层的关联规则中，对数据的多层性已经进行了充分的考虑。例 如：i b m 台式机- - * s o n y 打印机，是一个细节数据上的单层关联规则：台式机- - , s o n y 打 印机，是一个较高层次和细节层次之间的多层关联规则。 ( 3 ) 根据规则中涉及到的数据的维数可分为： 单维关联规则：在单维的关联规则中，我们只涉及到数据的一个维，如用户购买的 物品。单维关联规则是处理单个属性中的一些关系。 多维关联规则：在多维的关联规则中，要处理的数据将会涉及多个维。多维关联规 则是处理各个属性之间的某些关系。 例如：啤酒一尿布，这条规则只涉及到用户的购买的物品；性别= “女”一职业= “秘 书”，这条规则就涉及到两个字段的信息，是一条二维的关联规则。 1 2 3 关联规则挖掘面临的挑战 关联规则挖掘技术作为数据挖掘技术中的一项重要技术，还属于一种新兴的技术， 还没有达到类似数据库技术那样成熟的技术以及广泛和深入的应用。对于进一步的研 究，可能面临着以下的挑战： 更大的数据库：关联规则挖掘将面对更大的数据库，这些数据库可能拥有着数百个 字段和表，数百万条记录和数g 个字节大小的容量，甚至几千个g 字节大小的数据库 已经开始出现。处理这样大量的数据需要更有效的算法，包括取样、近似和大规模的并 行处理技术。 高维度：数据库中不仅经常拥有大量的记录，也经常有很多的字段( 属性、变量等) ， 这样，问题的维度就很高。一个高维度的数据集将会爆炸性地增加归纳模型的搜索空间。 而且，它还会增加关联规则挖掘算法发现虚假的、不能推及一般模式的机会。 数据和知识的变化：数据的快速和不稳定的变化使得先前发现的模式变得无效。另 外，度量一个给定应用数据库的变量可能随着时间而被修改、删除或增加新的度量变量。 这就要求挖掘模式能够具有前瞻性和可扩充性，以适应数据和知识的变化。 缺失数据和噪音数据：这个问题在商业数据库中尤其敏感。现实世界的数据总是不 完美的，有各种各样的原因会导致数据失去一致性和完整性。某些感兴趣的属性可能并 不包含在数据库中，因为数据库并不是为了关联规则挖掘而设计的。因此，数据预处理 的技术显得格外重要，目前尽管有少数数据预处理软件产品，但这一领域的研究相对而 一5 一 东北大学硕士学位论文第一章绪论 言仍然是落后的。 字段间的复杂关系：数据库中的大量字段之间存在着层次结构关系以及更复杂的语 义关系等，良好的关联规则挖掘算法应该能够充分地利用这些信息以得到更好的结果。 因此，关联规则挖掘算法如何解决字段间的这种复杂数据关系和语义关系，保证挖掘模 式充分运用字段与数据间的各种关系，将成为关联规则挖掘必须重视的问题。 模式的易懂性：在很多应用中，重要的是使用户更容易地理解所发现的模式。所以， 将模式翻译或转换为易于识别的知识，将成为考察关联规则挖掘实用性的一个重要方 面。 用户交互和先验知识：很多现有的关联规则挖掘方法和工具不能真正的具有交互 ，也不能把关于某个问题的先验知识很容易的包含进来。而实际上，领域知识的应用 关联规则挖掘的各个阶段都很重要。因此，建立领域知识的挖掘知识库将会大大改善 联规则挖掘的交互接口，确保关联规则挖掘的深度。 与其它系统的集成：一个孤立的关联规则挖掘系统并不能完全的发挥关联规则挖掘 效能，只有将若干各具特色的关联规则挖掘系统集成一体，才能充分体现关联规则挖 的能力。典型的集成问题包括：与数据库管理系统的集成、与电子表格或可视化工具 集成以及与实时数据感应器的集成等。 3 论文组织结构 本文的内容一共分为六章。第一章对本文研究的背景知识数据挖掘技术以及关联规 挖掘技术进行了简要的介绍；第二章介绍了频繁模式挖掘技术以及频繁闭模式挖掘技 的研究现状以及几个有代表性的挖掘算法；第三章提出了两种存储频繁模式的数据结 ：后缀树和有序图，并分别介绍了在这两种结构上进行集合相关操作的算法；第四章 出了一种新的元素增长搜索策略，并提出了基于这个策略的频繁闭模式挖掘算法 s a m 算法，以及提高算法性能的削减规则和预处理技术；第五章通过实验首先比较 后缀树、有序图和以往存储结构的性能，然后对e i s a m 算法以及以往的挖掘算法的 能进行了比较；最后第六章是对全文工作总结及今后工作的展望。 一6 一 东北大学硕士学位论文 第二章相关研究工作 第二章相关研究工作 频繁模式挖掘是关联规则的核心步骤，也是最重要的步骤。可以说找到频繁模式， 关联规则的生成就是很简单的工作了。所以，对于关联规则挖掘技术研究的重心一直集 中在对频繁模式挖掘技术的研究上。 2 1 频繁模式挖掘技术概述 频繁模式挖掘技术一直是关联规则挖掘的核心研究课题，许多优秀的研究人员投入 了大量的精力致力于频繁模式挖掘算法的研究工作，取得了很多丰硕的成果。随后的频 繁闭模式概念的提出更使频繁模式挖掘技术达到了新的高度，也促使了许多挖掘频繁闭 模式的高效算法的产生。最近，又有人提出了在三维数据集上挖掘频繁闭模式的方法， 也预示着频繁模式挖掘技术的广阔发展空间。 2 1 1 频繁模式挖掘在关联规则挖掘中的重要性 谬 关联规则挖掘通常分为以下两个步骤：( 1 ) 找出所有的频繁模式。( 2 ) 从频繁模式生 成关联规则。 其中第一步，找出所有的频繁模式是决定关联规则挖掘算法效率的关键步骤，也是 最为费时的步骤。一旦找出所有的频繁模式以后，关联规则的生成就变得非常直接。根 据频繁模式生成关联规则的算法如算法2 1 所示： 算法2 1 关联规则生成算法r g e n a l g o r i t h m 2 1a s s o c i a t i o nr u l e sg e n e r a t i n ga l g o r i t h mr g e n 算法2 1 r g e n ( f p ，m i n c ) 输入：频繁模式集合f p ，最小置信度阈值m i n c 输出：关联规则结果集合r 算法描述 1 r = a ： 2 对于频繁模式中的每个频繁项集尸； 3 对于每个频繁项集q c p ，且饼a ； 4 i f ( s u p p o r t ( p ) s u p p o r t ( q ) m i n c ) 5 将p j q 存入结果集合r ； 6 e n di f 4 可见一旦找到所有的频繁模式，生成关联规则的工作是很简单的，而且生成关联规 一7 一 东北大学硕士学位论文 第二章相关研究工作 则的代价与挖掘频繁模式的代价相比是很小的。所以，频繁模式的挖掘已经成为关联规 则挖掘的主要研究方向。 2 1 2 频繁模式挖掘的研究现状 a g r a w a l 等人提出的a p r i o f i 算法【5 1 是第一个经典的频繁模式挖掘算法。a p r i o r i 算法 是根据有关频繁项集的特性的先验知识( p r i o rk n o w l e d g e ) 而命名的。该算法利用广度 优先的搜索策略来完成频繁项集的挖掘工作，其核心思想是利用k 项集来产生( k + 1 ) 项集，不断循环下去直到无法发现更多的频繁项集为止。随后，许多研究人员对其性能 进行了诸多方面的改进，从而出现了一系列基于a p r i o r i 思想的算法，如h o u t s m 等提出 的s e t m 算法【13 1 、p a r k 等提出的d h p 算、法【1 2 1 、s a v a s e r e 等提出的p a r t i t i o n 算法【1 4 】、 m a n n i l a 、t o i v o n e n 等提出的s a m p l i n g 算法【1 5 ，1 6 1 、b r i n 等提出的d i c 算法【1 7 1 、d b u r d i c k 等提出的m a f i a 算法【2 2 】等等。后来，j i a w e ih a r t 等人提出了性能更好的f p g r o w t h 算 法【6 】，构建一颗能够压缩存储频繁模式信息的f p 树，并在f p 树上进行频繁模式的挖掘， 这也导致了一系列基于f p t r e e 的算法的出现，并使越来越多的研究人员投入到频繁模 式挖掘技术的研究中【2 4 。0 1 。 p a s q u i e r 等人【7 1 首先注意到频繁模式产生的结果中有许多结果是包含在其它结果中 的，即频繁模式的如下性质： 性质2 1 设i l 、1 2 是数据集d 中的项集，若i ic 1 2 ，且1 2 是频繁项集，则1 1 也是 频繁项集。即若1 2 及其支持事物集合是频繁模式，则i l 及其支持事物集合也是频繁模式。 可见，如果一个项集i 是频繁项集，则它的所有子集也都是频繁项集；也就是说， 频繁模式的项集的所有子集及其支持事物集合组成的模式也是频繁模式。为了避免在频 繁模式挖掘中挖掘大量这样的冗余信息，p a s q u i e r 等人首先提出了频繁闭模式的概念： 定义2 1设i 是数据集d 中的项集，若i 满足如下的条件，则称i 为频繁闭项集： ( 1 ) i 是频繁项集； ( 2 ) 不存在频繁项集i ，使得i c _ i ，且s u p p o r t ( i ) - - s u p o r t ( i ) 。频繁 闭项集对应的模式就称作频繁闭模式。 此外，还有人提出了最大频繁模式的概念： 定义2 2 设i 是数据集d 中的项集，若i 满足如下的条件，则称i 为最大频繁项 集：( 1 ) i 是频繁项集； ( 2 ) 不存在频繁项集i ，使得i c _ i 。最大频繁项集对应的模式 就称作最大频繁模式。 最大频繁模式挖掘的结果所对应的项集中不存在任何的超集一子集关系，没有考虑 事物集合的因素，因而其结果集合的数量又远小于频繁闭模式的结果数量。但是，不考 虑事物集合的因素将导致信息的丢失，所以最大频繁模式的挖掘没有成为主流的研究方 一8 一 东北大学硕士学位论文 第二章相关研究工作 向。若用f p ( f r e q u e n tp a t t e r n s ) 表示频繁模式，用f c p ( f r e q u e n tc l o s e dp a t t e r n s ) 表示 频繁闭模式，用m f p ( m a x i m a lf r e q u e n tp a t t e r n s ) 表示最大频繁模式，则三者的关系可 以表示为：m f p f c p f p 。 频繁闭模式概念的提出将频繁模式的挖掘技术引入了崭新的领域，也是目前模式挖 掘技术的主流研究方向。有代表性的挖掘频繁闭模式的算法有f p a n 等提出的c a r p e n t e r 算法【18 1 、c o b b l e r 算法【1 9 】、j w a n g 等提出的c l o s e t + 算法【2 0 1 、m z a k i 等提出的c h a r m 算法等等。 算法2 2a p r i o r i 算法 a l g o r i t h m2 2a p r i o r ia l g o r i t h m 算法2 2a p r i o r i ( d ，m i n t ，m i n i ) 输入g待挖掘数据库d ，最小支持度阈值m i n t ，最短项集阈值m i n i 输出：频繁模式结果集合f p 算法描述 1 将所有的频繁项目存入p ； 2 k = 2 ： 3 i f ( ，囝) 4 c k = a g e n 魄j ) ： 5 f o r ( 任意事务t e d ) 6 f o r ( 任意候选项集c c k ) 7 i f ( c _ c t ) 8 c c d o 玎，+ + ： 9 e n di f 7 1 0 e n d f o r 6 1 1 e n d f o r 5 1 2 将c 七中所有支持度大于等于m i n t 的候选项集存入凡： 1 3 i f ( k _ 勘n i n ) 1 4 将r 存入即； 1 5 e n d i f 1 3 1 6 1 【+ + ： 1 7 e n d i f 3 2 2 频繁模式挖掘算法 频繁模式挖掘技术经历了从频繁模式挖掘到频繁闭模式挖掘的发展过程。其中频繁 模式挖掘的代表性算法是a p r i o r i 算法和f p g r o w t h 算法，大多数的频繁模式挖掘算法 的思想都是基于这两个算法的；频繁闭模