（计算机软件与理论专业论文）频繁模式挖掘技术的研究.pdf

论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或其它机构已经发表或撰写过的 研究成果。其他同志对本研究的启发和所做的贡献均已在论文中作了明确的声明 并表示了谢意。 作者签名：峄日期：璺2 蚴 论文使用授权声明 本人完全了解复旦大学有关保留、使用学位论文的规定，即：学校有权保留 送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其它复制手段保存论文。保密的论文在解密后遵守此 规定。 作者签名：懈 导师签名 竺生嗍疯拿 摘要 摘要 随着信息技术的发展，人们在日常事务处理和科学研究中积累了大量宝贵的 数据。如何从中提取或挖掘用户所需要的信息，是当前信息科学和技术领域面临 的一大挑战。关联规则( a s s o c i a t i o nr u l e s ) 挖掘在数据领域是一个重要的研究内 容，而频繁模式挖掘是产生关联规则的第一步。其研究内容一般包括事务、序列、 树和图。其方法被广泛应用于许多其它数据挖掘任务中，如相关性分析，周期分 析，最大模式，闭合模式，查询，分类，索引等等。由于问题本身的基础性和内 在复杂性，频繁模式挖掘方法成为许多研究者关注的课题。 本文对频繁模式挖掘相关技术进行了研究。重点研究了以下几个问题：基于 互关联后继矩阵的区间频繁模式挖掘方法；基于位图( b i t v e c t o r ) 频繁模式挖掘 算法；基于表构投影模型( p r o t a b l e ) 的频繁闭合模式挖掘算法及相关的实现技 术等。本文研究内容和创新工作主要包括以下三个方面： ”基于i r s m 模型的区间频繁模式挖掘方面 互关联后继矩阵模型是一种新型的全文存储索引模型。这种模型充分利用了 字符序列的有序性和冗余性，适用于海量的全文存储和索引。其优势在于：既是 全文索引模型，又是全文存储模型；对任意一全文都能构造其互关联后继矩阵， 同时对于互关联后继矩阵，也能还原其对应的原文；具有极佳的空间效率；具有 领域独立性和查询的完备性。本文扩展了互关联后继矩阵的应用领域，首次提出 一种基于互关联后继矩阵模型的频繁模式挖掘算法。其优点在于：挖掘任务只局 部关联于后继矩阵的一行，有较好的可扩展性；算法简单容易理解；具有与 f p g r o w t h 算法相当甚至更高的效率。 2 ) 基于位图的频繁模式挖掘方法 在通常的水平数据布局的频繁模式挖掘算法的基础上，本文提出一种垂直数 据布局的频繁模式挖掘算法即基于位图模型的频繁模式挖掘算法b i t v e e t o r 。采用 0 ，1 的形式来表示该项是否存在，并且巧妙地采用了r l e 压缩技术，等价类思 想和混合遍历的方法。该算法无论在空间和时间效率上对于特定的数据集都有较 好的效率。 3 ) 基于表构投影模型的闭合频繁模式方法 频繁闭合模式提供了完全频繁模式的所有信息，但数量却可以少几个数量 级。本文给出一种基于p r o t a b l e 的算法特点是：只需要扫描一遍事务库；该二维 矩阵模型结构简单，利用代数运算来生成闭合频繁项集。与f p c l o s e 算法相比 较，在稠密数据集上p r o t a b l e 有较好的效率。 关键词：数据挖掘，频繁模式，互关联后继矩阵，位图，表构投影，频繁闭 摘要 合模式 中图分类号：t p 3 1 1 a b s t r a c t w i t l lt h ep o p u l a r i t yo fc o m p u t e ra n di n f o r m a t i o nt e c h n o l o g y , ag r e a ta m o u n to f d a mi sa c c u m u l a t e di nd a i l yw o r ka n di ns c i e n t i f i cr e s e a r c h h o wt oe x t r a c to rm i n e u s e f u li n f o r m a t i o nf r o mt h e s ed a t ai sa g r e a tc h a l l e n g ef o rt o d a y sr e s e a r c hw o r k e r si n i n f o r m a t i o ns c i e n c e a s s o c i a t i o nr u l ei sa l l i m p o r t a n tt o p i ci nd a t am i n i n ga n d f r e q u e n tp a a e mm i n i n gi st h ef i r s ts t e po fg e n e r a t i n ga s s o c i a t i o nr u l e s i ti n c l u d e s m i n i n gt r a n s a c t i o n s ，s e q u e n c e s ，t r e e sa n dg r a p h s t h ea l g o r i t h mf o ri th a sb e e n p r e v a l e n t l yu s e di nm a n yo t h e rd a t am i n i n gt a s k , s u c h 鹊a s s o c i m i o na n a l y s i s p e r i o d s a n a l y s i s ，m a x i m a la n dc l o s e dp a t t e r n s ，q u e r y , c l a s s i f i c a t i o na n di n d e xt e c h n o l o g ye t c s i n c ei tl a y sg r o u n d w o r kf o ro t h e rp r o b l e ma n di t si n t r i n s i cc o m p l e x i t y , t h ea l g o r i t h m f o rf y e q u e n tp a t t e r nm i m i n gh a sb e c o m et h ef o c u so f m a n yr e s e a r c hw o r k e r s s o m er e l e v a n tt e c h n i q u e sa b o u tf r e q u e n tp a t t e r nm i n i n ga r ea d d r e s s e di nt h e t h e s i s ，w h i c hc o v g t sm i n i n gf r e q u e n tp a t t e r n sb a s e do ni r s mm o d e l ；m i n i n gf r e q u e n t p a t t e r n sb a s e do nb i t v e c t o ra n dm i n i n gc l o s e d 疗e q u e n tp a a e r n sb a s e do np r o t a b l e m a j o rc o n t r i b u t i o n so f t h i st h e s i si n c l u d e ： 1 ) f r e q u e n tp a t t e mm i n i n gb a s e do ni r s m i r s mi san o v e lm a t h e m a t i c a lm o d e lp r e s e n t e dr e g e n t l y , w h i c hh a sb e e n s u c c e s s f u l l ya p p l i e dt of u l l t e x ti n d e xa n ds t o r a g ei nt e x td a t a b a s e i nt h i st h e s i s ，i t s a p p l i c a t i o ni se x t e n d e dt od a t am i n i n ga n da na l g o r i t h mi sp r e s e n t e df o rm i n i n g f r e q u e n tp a t t e r n sb a s e do ni r s m t h ea l g o r i t h ms g a l 碍t h et r a n s a c t i o nd a t a b a s eo n l y o n c e t h em i n i n gp r o c e s si so n l ya s s o c i a t e d 、i t ho n er o wo ft h em a t r i x 触i r s m c a l lb ee a s i l ye x t e n d e da n dt h ea l g o r i t h mi se a s y t h ea l g o r i t h ms h o w se f f i c i e n t p e d o r m a l l c ec o m p a r i n gt of p - g r o w t h 2 ) m i n i n gf r e q u e n tp a t t e r n sb a s e do nb i t v e e t o r g e n e r a l l y , t h ed a t al a y o u to ft h em i n i n ga l g o r i t h mi sh o r i z o n t a l w ei n t r o d u c ea n e wa l g o r i t h mb a s e do nt h ev e r t i c a ld a t al a y o u t ，w h i c hi sb i t v e c t o r b i t v e e t o ru s g s0 a n d1r e p r e s e n t i n gt h ei t e me x i t so rn o t i tu s e st h ec o m p r e s s i n gt e c h n i q u ec a l l e dr l e ， t h ee q u a lc l a s st e c h n i q u ea n dt h em i x t u r et r a v e r s e 3 ) m i n i n g c l o s e df r e q u e n tp a t t e r n sb a s e do np r o t a b l e f r e q u e n tc l o s e dp a t t e r n sh a ss a m ep o w e ra sc o m p l e t ef r e q u e n tp a t t e r n s ，y e tt h e y c a nb eo r d e r so fm a g n i t u d es m a l l e r i nt h i st h e s i s ，w ep r e s e n tp r o t a b l e ，a ne f f i c i e n t m g o f i t h mf o rm i n i n gf r e q u e n tc l o s e dp a t t e r n s t h ea l g o r i t h ms e a n st h et r a n s a c t i o n d a t a b a s eo n l yo n c e a n dt h ea l g o r i t h mu s e st h es i m p l et w o m a t r i xm o d e la n d m i n i n g 3 - c l o s e dp a t t e m su s i n ga l g e b r a i cm e t h o d t h e a l g o r i t h mh a s8 1 1e f f i c i e n tp e r f o r m a n c e o nd e n s ed a t a s e tc o m p a r i n gw i t hf p - c l o s e k e yw o r d s ：d a t am i n i n g , f r e q u e n tp a t t e m s ，i n t e r r e v e l a n ts u c c e s s i v em a t r i x ， b i t v e c t o r , p r o t a b l e ，f r e q u e n tc l o s e dp a t t e r n s ， c l c ：t p 3 1 1 4 第一章绪论 第一章绪论 本章一方面l 鞫迷本文的研究背景，较系统地阐述了数据挖掘，关联规则挖掘以及频 繁模式挖掘问题的研究现状和已经取得的成果；另一方面，介绍本文的研究内容以及 组织结构 1 1 研究背景 随着计算机与信息技术的普及以及大容量存储技术的发展，成千上万个数据 库被用于商业管理、政府办公、科学研究和工程开发等等，这种应用仍将持续并 发展下去。人们从日常事务处理和科学研究中积累了大量宝贵的数据，并且信息 量在急剧上升，可称为进入了信息爆炸的时代，信息过量几乎成为人们需要直接 面对的问题。数据的丰富带来了对强有力的数据分析工具的需求。然而，大量的 数据却往往被描述为“数据丰富，信息贫乏”。这是因为，快速增长的海量数据 收集，存放在大型和大量数据库中，由于没有强有力的分析工具，理解它们已经 远远超出了人的能力。如果不能加以正确分析利用，财富就反而会变成“数据坟 墓”，变成人们沉重的包袱和巨大的压力。不可否认，在这些极度膨胀的数据背 后，有着极为重要的商业知识和科学规律，只不过其中大部分信息是潜在的，隐 含的，事先未知的。要想使数据真正成为一个公司的资源，只有充分利用它为公 司自身的业务决策和战略发展服务才行，否则大量的数据可能成为包袱，甚至成 为垃圾。因此，如何从海量的数据中提取或挖掘知识，日益成为当前信息科学与 技术领域科学工作者们面临的一大挑战，数据挖掘和知识发现( d m k d ) 技术应 运而生，并得以蓬勃发展，越来越显示出其强大的生命力。 数据挖掘( d a t a m i n i n g ) 就是从大量的、不完全的、有噪声的、模糊的、随机 的数据中，提取隐含在其中的，人们事先不知道的，但又是潜在有用的信息和知 识的过程。还有很多和这一术语相近似的术语，如从数据库中发现知识( k d d ) 、 数据分析、数据融合( d a t af u s i o n ) 以及决策支持等。 简单地说，数据挖掘就是从数据库中挖掘知识的过程。原始数据可以是结构 化的，如关系数据库中的数据；也可以是非结构化的，如文本、图形和图像数据； 甚至可以是分布在网络上的异构数据。发现知识的方法可以是数学的，也可以是 非数学的：可以是演绎的，也可以是归纳的。发现的知识可以用于信息管理，查 询优化，决策支持和过程控制等。总之，数据挖掘是- - f 广义的交叉学科，它把 第一章绪论 人们对数据的应用从低层次的简单查询，提升到从数据库中挖掘知识，提供决策 支持。该技术涉及数据库，人工智能，数理统计，机器学习，模式识别，知识获 取，专家系统，数据可视化和并行计算等多个领域。自提出这个概念以来，数据 挖掘一直是信息科学与技术领域的具有挑战性的研究课题。 特别要指出的是，数据挖掘技术从一开始就是面向应用的。它不仅是面向特 定数据库的简单检索查询，而且要对这些数据进行微观，宏观的统计、分析、综 合和推理，以指导实际问题的求解，企图发现事件间的相互关联，甚至利用已有 的数据对未来的活动进行预测。例如加拿大b c 省电话公司要求加拿大s i m o n f r a s e r 大学k d d 研究组，根据其拥有十多年的客户数据，总结、分析并提出新 的电话收费和管理办法，制定既有利于公司又有利于客户的优惠政策。美国著名 国家篮球队n b a 的教练，利用i b m 公司提供的数据挖掘技术，临场决定替换队 员，一度在数据库界被传为佳话。这样一来，就把人们对数据的应用，从低层次 的未端查询操作，提高到为各级经营决策者提供决策支持。这种需求驱动力，比 数据库查询更为强大。同时需要指出的是，这里所说的知识发现，不是要求发现 放之四海而皆准的真理，也不是要去发现崭新的自然科学定理和纯数学公式，更 不是什么机器定理证明。所有发现的知识都是相对的，是有特定前提和约束条件、 面向特定领域的，同时还要能够易于被用户理解，最好能用自然语言表达发现结 果，因此d m k d 的研究成果很讲求实际。1 9 9 7 年第3 届k d d 国际学术大会上 进行的实实在在的数据挖掘工具的竞赛评奖活动，就是一个生动的证明。最近， 还有不少d m k d 产品用来筛选i n t e r n e t 上的新闻，保护用户不受无聊电子邮件 的干扰和商业推销，受到极大的欢迎。 通过数据挖掘过程所推导出的关系经常被称为模型( m o d e l ) 或模式( p a t t e r n ) 。 例如线性方程、规则、聚类、树结构、图结构、和用时间序列表示的循环模式。 模型结构往往定义为对数据集的全局性总结，它对整个测量空间作出描述。例如， 它可以把空间中的一个点分配到一个聚类或者预测出某个其他变量的值，比如类 别。 与模型的全局性相反，模式结构( p a a e r ns t r u c t u r e ) 仅对变量变化空间的一个 有限区域作出描述。一个例子是以下这种形式的简单概率性结论：如果x x 1 ， 那么y y l 的概率为p i 。这个结构由变量x 和变量y 的值的约束组成，并以概率 规则的形式将这两个变量联系起来。另一种描述方法是将这个关系描述为条件概 率p ( y y , i x x i 户p l 。在语义上二者等价。另一个例子是，人们可能注意到事务 6 第一章绪论 记录中的某类记录没有显示出大多数记录所显示出的特征，因此需要进一步分析 其中的原因。 局部模式仅与一部分数据或空间有关，或者，仅有一部分记录具有某种特性， 模式就是用来刻画这一部分数据的。例如，搜索通过邮件订购商品的数据库，可 能发现购买某个商品组合的顾客也可能购买其他的商品。再如，标识出和大多数 记录完全不同的孤立记录。局部模式探测方法可以应用于工业生产中的故障探 测，银行或其他商业活动中的欺诈行为探测，或用于帮助商家进行交叉销售。 1 2 目前研究状况 本节首先介绍了数据挖掘的发展历史和研究现状，接着给出了关联规则挖掘 的概念和定义，最后给出了频繁模式挖掘算法的研究状况。 1 2 1 数据挖掘 1 9 8 9 年，在第1 1 届国际人工智能联合会议( u c a i ，i n t e r n a t i o n a lj o i n t c o n f e r e n c eo na r t i f i c i a ii n t e l l i g e n c e ) 的专题研讨会上，首次提出了基于数据库的知 识发现( k d d ，k n o w l e d g ed i s c o v e r yi nd a t a b a s e ) 技术。迄今为止，由美国人工智能 协会主办的k d d 国际研讨会已经召开了7 次，规模由原来的专题讨论会发展到 国际学术大会。其他内容的专题会议也把数据挖掘和知识发现列为议题之一，成 为当前计算机科学界的一大热点。 i e e e 的k n o w l e d g ea n dd a t ae n o n e e r i n g 会刊领先在1 9 9 3 年出版了k d d 技 术专刊，所发表的5 篇论文代表了当时k d d 研究的最新成果和动态，较全面地 论述了k d d 系统方法论、发现结果的评价、k d d 系统设计的逻辑方法，集中 讨论了鉴于数据库的动态性冗余、高噪声和不确定性、空值等问题，k d d 系统 与其它传统的机器学习、专家系统、人工神经网络、数理统计分析系统的联系和 区别，以及相应的基本对策。6 篇论文摘要展示了k d d 在从建立分子模型到设 计制造业的具体应用。 在此基础上，1 9 9 5 年，在美国计算机年会( a c m ) 上，正式提出了数据挖掘 ( d a t am i n i n g ) 的概念。数据挖掘领域的资深专家h a n d 先生将数据挖掘定义为： “数据挖掘就是对观测到的数据集( 经常是很庞大的) 进行分析，目的是发 现未知的关系和以数据拥有者可以理解并对其有价值的新颖方式来总结数据”。 第一章绪论 1 2 2 关联规则 1 2 2 1 关联规则的概念和定义 关联规则挖掘是数据挖掘的主要方法之一，也是一个重要的课题，最近几年 已经被广泛研究和关注。关联规则就是发现大量数据中项集之间有趣的关联或相 关联系，一个典型例子是购物篮分析。关联规则研究有助于发现交易数据库中不 同商品( 项) 之间的联系，找出顾客购买行为模式，如购买了某一商品对购买其 他商品的影响。一个典型的关联规则的例子就是。9 0 的顾客在购买面包的同时 也会购买牛奶”。其直观意义为顾客在购买某些商品的同时有多大可能购买另外 一种商品。可以将顾客的购物模式的分析结果应用于商品货架布局、货存安排以 及根据购买模式对用户进行分类。首先介绍一下关联规则挖掘的概念以及定义。 设l = o t ，如，纠是项的集合，其中的元素称为项( i t e m ) 。记d 为事务 ( 1 l - a n s a c t i o n ) t 的集合( 一般为交易型数据库) ，这里事务丁是项的集合，并且7 垒，。 对应每一个事务有唯一的标识，如事务号，记作t i d 。设x 是一个，中项的集合， 如果娜那么称事务丁包含工 定义1 关联规贝u ( a s s o c i a t i o nr u l e ) 就是形如x = y 的蕴涵式，这里x c , y c ， 并且x n y = o 。 定义2 规则的支持度( s u p p o r t ) 。规则x - y 在事务数据库d 中的支持度 ( s u p p o r t ) 是事务集中包含x 和y 的事务数与所有事务数之比，记为 s u p p o r t ( x = y ) ，即 s u p p o r t ( x f f i y ) f f ip u 矽 定义3 规则的置信度( c o n f i d e n c e ) 。规则x j y 在事务集中的置信度 ( c o n f i d e n c e ) 是指包含x 和y 的事务数与包含x 的交易数之比，记为 c o n f i d e n c e ( x = y ) ，即 c o n f i d e n c e _ y ) = p ( x 1y ) 定义4 闽值。为了在事务库中找出有用的关联规则，需要由用户确定两个 阈值：最小支持度( m i n s u p ) 和最小置信度( m i n c o n f ) 。 定义5 项的集合称为项集( i t e m s c t ) ，包含k 个项的项集称为k 项集。如果 项集满足最小支持度，则该项集为频繁项集( f r e q u e n ti t e m s c t ) 。 定义6 关联规则。同时满足最小支持度( m i n s u p ) 和最小置信度( m i n c o n o 的规 则称为关联规则，即s ( x = y ) = r a i n _ s u p 且c ( x = y ) = m i n _ c o n f 成立时，规 则x = y 称为关联规则，也可以称为强关联规则。 一8 第一章绪论 1 2 2 2 关联规则挖掘 关联规则的挖掘过程可以分成两个步骤： 1 根据最小的支持度，在大量事务中寻找高频率出现的频繁项集( i t e m s e t ) 。 2 根据最小的置信度，由已经找到的频繁项集产生关联规则。 其中第二个步骤比较容易，一般经过第一步的筛选后的频繁项集都不会很 多，通过子集产生法就可以产生关联规则。第一个步骤是需要在大量的事务数据 集中寻找高频率出现的项集i t e m s e t ，所以就需要一个比较高效的搜索查找方法。 1 2 2 3 关联规则的分类 基于规则中处理的变量的类别，关联规则可以分为布尔型关联规则和数值型 关联规则。其中布尔型关联规则处理的值都是离散的、种类化的，它显示了这些 变量之间的关系；数值型关联规则可以和多维关联或多层关联规则结合起来，对 数值型字段进行处理，将其进行动态的分割，或者直接对原始的数据进行处理， 当然数值型关联规则中也可以包含种类变量。 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。其中 在单层关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次 的；在多层关联规则中，对数据的多层性已经进行了充分的考虑。 基于规则中涉及到的数据的维数，关联规则可以分为单维的和多维的。其中 在单维关联规则中，我们只涉及到数据的一个维，如用户购买的物品；在多维关 联规则中，要处理的数据将会涉及多个维。 1 2 3 频繁模式挖掘算法的分类 本文所关注的频繁模式属于局部模式结构。频繁模式挖掘是数据挖掘领域的 一个基本问题。1 9 9 4 年，为了寻找大量商务事务库中的项集之间的有趣联系， a g r a w a l 开创性地提出了关联规则挖掘问题，并发表了著名的a p r i o r i 算法【l 司， 用频繁项集产生关联规则，发现顾客购买的不同商品之间的联系，分析顾客的购 物习惯，帮助零售商制定营销策略。1 9 9 5 年，为描述同一顾客在多次所购物品 之间可能存在的某种关联关系，a g r a w a l 又发表了序列模式挖掘算法。此后，频 繁项集与频繁序列挖掘算法被广泛应用于许多其它数据挖掘任务中，如相关性分 析，周期分析，最大模式，闭合模式，查询，分类，索引等等。 频繁项集挖掘一直是数据挖掘领域的重点课题，所做的工作与取得的成果也 比较多。经过十几年的研究，已经奠定了较成熟的频繁模式挖掘方法的理论基础。 - 9 第一章绪论 根据不同的挖掘策略，数据的布局的特征以及生成的频繁模式的特征，频繁模式 挖掘算法大致可以从以下几个方面进行分类。 首先从挖掘策略上来说，频繁模式挖掘方法大致可以分为宽度优先挖掘和深 度优先挖掘，宽度优先挖掘是指按层次的方法，有k 频繁项集通过连接，剪枝的 方法生成可k + 1 候选项集，再通过扫描数据库，确定k + l 频繁项集。宽度优先 算法的典型算法是a 面o r i 【1 】【2 】。其它研究者先后引入划分技术哆散列方法【4 】， 选样方法1 5 j 1 6 】对其改进。但候选集的产生与验证过程始终是这类算法性能的一个 瓶颈。深度优先算法以深度优先的方法遍历项集，其算法的典型代表是 f p g r o w t h 算法哺】1 9 1 。它首先将事务压缩组织成树，然后用模式增长的策略不断 在动态构建的条件f p t r e e 上挖掘频繁模式。之后，其它研究者相继提出一些优 化方法：h - m i n e 方法将事务组织成数组，但在挖掘稠密数据集时仍采用 f p - g r o w t h 算法【；h p 方法根据数据子集的局部特征，动态的调整基于树或数 组的事务表示方法i l “。f p g r o w t h 算法是目前效率最高的算法之一。 数据布局即数据的表示和组织形式。从概念上讲，一个事务库可以看成是一 个二维的数组，其中行用来表示每个顾客的购买商品的行为，列表示每一种商品 的销售情况。这个二维数组我们可以用如下的四种方式来组织，即水平项数组 ( h i v ) ，水平项列表( h i l ) ，垂直的序列数组( v t v ) 和垂直的序列列表( v t l ) 。 其中水平的项数组( h ) ：数据库被组织成一些行的集合，这些行存储了一个事 务标识( t i d ) 和一个b “( o 和1 ) 数组，用来表示正在销售的每一件商品；水 平的项列表( h i l ) ：这个数据库的组织与h i v 很相似，除了它的每一行存储的是 个项标识的有序链表，该链表的值就是那些顾客实际购买的商品序号；垂直的 序列数组( v t v ) ：数据被组织成一些列的集合，每一列存储了一个项标识和一个 b i t ( o 和1 ) 数组，用来表示所用顾客的购买行为：垂直的序列列表( v t l ) ：这 个数据库的组织与上面的v t v 的组织很相似，除了它的每- - n 存储的是一些事 务标识的链表，其中这些事务标识就是那些确实购买了该商品的顾客序号。可以 发现v t l 的存储空间与h i l 的空间相同。实际上我们可以看到，h w 的数据布 局就是一种最常见的数据布局方式，原始的事务库就是以这种方式存储的。 数据挖掘算法以通过限制挖掘出的模式彼此之间的关系，又可分为完全频繁 模式挖掘，最大频繁模式挖掘和频繁闭合模式挖掘。完全频繁模式在许多数据挖 掘任务中起着重要作用，但其数量之大却往往令用户无所适从，由此产生的关联 规则亦难以理解与运用；最大频繁模式，其虽然能够挖掘出所有的频繁模式，但 第一章绪论 却损失了支持度信息；频繁闭合模式包含完全频繁模式的所有信息，能够确定任 一频繁模式的精确支持度，包含尺寸却能够小很多。通过频繁闭合模式还可以得 到数量少很多的精简关联规则集。 1 3 本文的研究内容和组织结构 本文围绕频繁项集挖掘技术展开研究。重点研究了以下几个问题：基于互关 联后继矩阵的区间频繁模式挖掘算法；基于位图的频繁模式挖掘算法和基于表构 投影的频繁闭合模式挖掘算法。理论和实验表明，这些方法不仅使用简单，也有 较好的时空效率，可广泛应用于与频繁模式相关的诸多领域中，具有广泛的应用 前景。 本文内容围绕频繁模式挖掘的方法与实现技术展开，总共分为六章，具体安 排如下： 第一章绪论 介绍数据挖掘，关联规则挖掘，频繁模式挖掘的研究背景和目前的研究状况， 引出相关研究课题，概述了国内外最近有关的研究动态，介绍了本文的主要研究 内容。 第二章经典频繁模式挖掘算法介绍 该章主要回顾了频繁模式挖掘算法的研究成果，以及重点介绍两个经典频繁 模式挖掘算法a p r i o r i 和f p g r o w t h 算法的主要性质，主要挖掘算法步骤和适用 的数据集的特点，以及这两个算法的演变算法。 第三章基于i r s m 模型的区间频繁模式挖掘 本章首先主要引入了新型的索引模型一互关联后继矩阵模型的相关概念和 定义，接着介绍了基于i r s m 的区间频繁模式挖掘算法的相关原理和算法概述， 并进行了实验比较，实验对比表明，该算法有较好的时间效率。 第四章基于位图( b i t v e c t o r ) 的频繁模式挖掘 该章首先介绍了频繁模式挖掘算法相关的四种数据布局的定义和特点，并在 此基础上提出了一种垂直数据布局的频繁模式挖掘算法b i t v e c t o r 。该算法利用了 r l e 压缩技术，等价类的思想和混合遍历的方法。实验表明，该算法有较好的 时间和空间效率。 第一章绪论 第五章基于表构投影( p r o t a b l e ) 闭合频繁模式挖掘 该章首先引入了频繁闭合模式的相关概念和定义；再引入了表构投影模型的 相关定义，在此基础上提出了一种基于表构投影的闭合频繁模式挖掘算法，该算 法的二维矩阵模型相对比较简单，采用代数的方法进行频繁闭合模式挖掘。试验 表明，该算法在稠密数据集上具有较好的效率。 第六章总结和展望 该章对全文的工作进行了总结，并对今后的工作提出了新的研究方向。 第二章经典频繁模式挖掘 第二章经典频繁模式挖掘 本章介绍了经典的频繁模式挖掘算法a p f i o r i 和f p g r o w t h 的主要性质和算法的主要步 骤，以及这两种算法的优缺点和所适用的数据类型的特点，最后介绍了这两种算法的各种演 变算法 2 1 引言 频繁模式挖掘是数据挖掘领域的一个基本问题。经过十几年的研究，已经奠 定了较成熟的频繁模式挖掘方法的理论基础。 1 9 9 4 年，为了寻找大量商务事务库中的项集之间的有趣联系，a g r a w a l 开创 性地提出了关联规则挖掘问题，并发表了著名的a p f i o r i 算法【i 捌，用频繁项集产 生关联规则，发现顾客购买的不同商品之间的联系，分析顾客的购物习惯，帮助 零售商制定营销策略。算法具有可能产生大量的候选集以及可能需要重复扫描数 据库的两大缺点，针对这两个缺点，其它研究者进行进一步的改进。 但侯选集的产生与验证过程始终是这类算法性能的一个瓶颈。针对a p n o d 算法的固有缺陷，j h a r t 等提出了不产生候选挖掘频繁项集的方法 f p g r o w t h 3 4 1 。采用分而治之的策略， 频集压缩进一棵频繁模式树( f p - t r c e ) ， 在经过第一遍扫描之后，把数据库中的 同时依然保留其中的关联信息，随后再 将f p - 仃e e 分化成一些条件库，每个库和一个长度为1 的频集相关，然后再对这 些条件库分别进行挖掘。当原始数据量很大的时候，也可以结合划分的方法，使 得一个f p n _ c e 可以放入主存中。 本章具体内容安排如下：第二节介绍a p r i o r i 算法的相关知识和该算法的演 变算法，第三节给出f p g r o 砌算法的相关定义和该算法的演变算法。 2 2a p r i o r i 算法挖掘频繁模式 a g r a w a l 等于1 9 9 4 年提出了一个挖掘顾客交易数据库中项集间的关联规则 的重要方法即经典a p r i o r i 算法【旧。通过遍历一大堆事务数据库，从一个一个的 单个项开始计数，每次遍历完所有的事务后，裁减掉支持度计数小于用户给定的 支持度的项，然后逐步扩展到多项事务。最后保留下来的频繁项集，通过子集产 生法来产生关联规则，然后去掉其中置信度低于用户指定的最低置信度的关联规 则，最后剩下的就是满足用户需要的关联规则。该算法的核心是基于两阶段频集 第二章经典频繁模式挖掘 思想的递推算法。在关联规则分类上属于单维、单层、布尔关联规则。 a p f i o f i 算法的特点就是在于从单项开始，每次剪裁一点，利用a p f i o d 性质， 有效避免了对很多不可能的项的搜索过程。 2 2 1a p r i o r i 性质 a p r i o r i 性质：频繁项集的所有非空子集都必须也是频繁的。 该性质表明，如果项集i 不满足最小支持度阈值r a i ns u p ，则i 不是频繁的， 即p ( i ) m i n _ s u p 。如果项a 添加到i ，则结果项集( it ja ) 不可能比i 更频繁出 现。因此，( i ，a ) 也不是频繁的，即p ( iua ) m i a _ c o n f i d c n c 宅，则可以产生强关联规则b = c 。 2 2 4a p r i o r i 基本算法的缺陷 数据挖掘作为o l a p 的数据分析处理，数据f o 效率往往都是其算法实现的 瓶颈。a p r i o r i 算法在寻找频繁项集的时候，需要多次重复扫描数据库，所以其 效率并不理想。同时，a p r i o r i 逐步迭代产生候选项集规模也可能十分巨大，呈 现组合式的增长速度。比如，当长度为1 的频繁项集有1 0 0 0 0 个的时候，长度为 2 的候选项集个数将会超过i o m 。 第二章经典频繁模式挖掘 2 2 5 算法演变的讨论 为了提高算法的效率，m a n n i l a 等引入了修剪技术来减小候选集q 的大小， 由此可以显著地改进生成所有频集算法的性能。算法中引入的修剪策略基于这样 一个性质：一个项集是频集当且仅当它的所有子集都是频集。那么，如果c i c 中 某个候选项集有一个( k - 1 ) 一子集不属于k l ，则这个项集可以被修剪掉不再被考 虑，这个修剪过程可以降低计算所有的候选集的支持度的代价。 但是在实际应用中，还是存在不令人满意的地方，于是人们相继提出了一些 优化的方法，先后引入划分技术【3 】，散列方法【4 】，选样方法 5 】【6 】，压缩方法 7 】 对其改进。 1 ) 基于划分的方法 3 1 。s a v a s c r c 等设计了一个基于划分( p a r t i t i o n ) 的算法， 这个算法先把数据库从逻辑上分成几个互不相交的块，每次单独考虑一个分块并 对它生成所有的频集，然后把产生的频集合并，用来生成所有可能的频集，最后 计算这些频集的支持度。这里的分块的大小选择要使得每个分块可以放入主存， 每个阶段只需被扫描一次。而算法的正确性是每一个可能的频集至少在某一个分 块中是频集保证的。该算法是可以高度并行的，可以把每一分块分别分配给某一 个处理器生成频集。产生频集的每一个循环结束后，处理器之间进行通信来产生 全局的候选k 一项集。通常这里的通信过程是算法执行时间的主要频颈；而另一 方面，每个独立的处理器生成频集的时间也是一个瓶颈。其他的方法还有在多处 理器之间共享一个杂凑树来产生频集。 2 ) 基于散列的方法【4 】。p a r k 等提出了一个高效地产生频集的基于杂凑( h a s h ) 的算法。该算法采用了基于h a s h 的方法建立h a s h 表达到减少候选集的大小， 通过试验我们可以发现寻找频繁项集的主要的计算是在生成频繁2 一项集h 上， p a r k 等就是利用了这个性质引入杂凑技术来改进产生频繁2 一项集的方法。 3 ) 基于采样的方法。基于前一遍扫描得到的信息，对此仔细地作组合分析， 可以得到一个改进的算法，m a n n i l a 5 】等先考虑了这一点，他们认为采样是发现 规则的一个有效途径。随后又由t o i v o n e n l 6 i 进一步发展了这个思想，先使用从数 据库中抽取出来的采样得到一些在整个数据库中可能成立的规则，然后对数据库 的剩余部分验证这个结果。t o i v o n e n 的算法相当简单并显著地减少了f o 代价， 但是一个很大的缺点就是产生的结果不精确，并存在所谓的数据扭曲( d a t a s k e w ) 。分布在同一页面上的数据时常是高度相关的，可能不能表示整个数据库 中模式的分布，由此而导致的是采样5 的交易数据所花费的代价可能同扫描一 遍数据库相近。 4 ) 交易压缩方法。减少用于未来扫描的事务集的大小。一个基本的原理就 是当一个事务不包含长度为k 的大项集，则必然不包含长度为k + l 的大项集。 第二章经典频繁模式挖掘 从而我们就可以将这些事务移去，这样在下一遍的扫描中就可以减少进行扫描的 事务集的个数。这个就是a p r i o r i t i d l ；q 算法的基本思想。 2 3f p - 6 r o w t h 算法挖掘频繁模式 a 研o r i 算法有一些固有的缺陷： 可能会产生大量的候选集。当长度为l 的频繁集有1 0 0 0 0 个的时候，长 度为2 的候选集的个数将会超过i o m 。还有就是如果要生成一个