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

摘要 作为数据库研究领域中的热点，数据库中的知识发现( 简称k d d ) 正在受到越来越多的关注。它被定义为在数据中寻找正确的、有趣的、 潜在有用的并最终可以理解的模式。对关联规则的挖掘在许多数据挖 掘任务中都有重要作用，有着广泛的应用范围。随着被挖掘的数据集 在大小和复杂度上的飞速增长，研究高效可伸缩的挖掘算法对保证系 统的可伸缩性和交互性至关重要。 关联规则挖掘算法使用格理论中的组合特性来将原始问题分解 为许多更小的互相独立的问题。最有名的和最有影响力的算法包括 a p r i o r i 算法和f p g r o w t h 算法。 粗集理论根据对一个系统的观察和测量所得的现实数据信息，从 分类的观点，以集合近似、近似分类与不可分辨的概念为基础，通过 知识约简从中发现、推理知识和分辨系统的特点、过程、预测系统的 结果等。d m r 算法尝试利用粗集理论中关于等价类的概念，针对单 维布尔关联规则问题提出的一种挖掘算法，并利用兴趣度对规则进行 评价。d m r 算法借助不可分辨关系的概念，将事务数据库按照交易 集合划分等价类。该算法从k 一候选项集中可以直接产生k 一频繁项集， 同时还可以生成( k + 1 ) 一候选项集而无需搜索数据库，因此d m r 算法 只需在生成卜候选项集时对数据库进行一次搜索，这会大大减少计 算时间。 通过对各项交易设定不同的m i f 值，用户可以灵活控制不同的关 联规则的最小支持度阈值，可以发现包含非频繁交易的具有较低支持 度的关联规则以及具有较高支持度的包含频繁交易的关联规则，同时 又不会引入过多无意义规则。 由于现实世界事务数据库中，数据是随时间的变化而变化的，当 前已发现的最大频繁项集可能不再生效，而新的有效最大频繁项集有 待于重新去发现。因此，迫切需要设计高效的算法来管理、维护和更 新已挖掘出来的最大频繁项集。目前国内外在对这一问题的相关研究 中提出了p i n c e rs e a r c h 、i u a 、f i u a 、f u f i a 、f u m f i a 等算法，这些 算法主要是针对频繁模式树来进行单双向剪枝与重构，需要额外的存 贮空间和较大的运算开销。 v 对此，本文提出了一种增量式更新最大频繁项集算法f a u m f i ( f a s ta l g o r i t h mf o ru p d a t i n gm a x i m u mf r e q u e n ti t e m s e t s ) ，该 算法将充分利用已有的一切信息( 如旧的最大频繁项集、原来的 b i t m a t r i x 等) ，以高效地发现最新事务数据库中所有的最大频繁项 集，并分析了算法的效率。 关键词数据挖掘，关联规则，粗集，位阵，频繁项集 v i a b s t r a c t 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 ) h a sr e c e i v e di n c r e a s i n g a t t e n t i o na n dh a sb e e nr e c o g n i z e da sap r o m i s i n gf i e l do fd a t a b a s e r e s e a r c h i ti sd e f i n e da st h en o n - t r i v i a lp r o c e s so fi d e n t i f y i n gv a l i d ， n o v e l ，p o t e n t i a l l yu s e f u la n du l t i m a t e l yu n d e r s t a n d a b l ep a a e m si nd a t a m i n i n ga s s o c i a t i o nr u l e sf r o ml a r g ed a t a b a s e sp l a y sa ne s s e n t i a lr o l ei n m a n yd a t am i n i n gt a s k sa n dh a sb r o a da p p l i c a t i o n s h i 曲一p e r f o r m a n c e s c a l a b l e c o m p u t i n gi s c r u c i a lf o re n s u r i n gs y s t e m s c a l a b i l i t y a n d i n t e r a c t i v i t ya sd a t a s e t sg r o wi n e x o r a b l yi ns i z ea n dc o m p l e x i t y t h ea s s o c i a t i o nr u l e m i n i n ga l g o r i t h m u s el a t t i c e - t h e o r e t i c c o m b i n a t o r i a lp r o p e r t i e st od e c o m p o s et h eo r i g i n a lp r o b l e mi n t os m a l l i n d e p e n d e n ts u b - p r o b l e m s t h em o s tf a m o u sa n di n f l u e n t i a la l g o r i t h m s a r ea p r i o r ia n df p g r o w t h w h e na l lm a x i m a lf r e q u e n ti t e m s e t sa r es h o r t ， t h e s e a l g o r i t h m sp e r f o r mr e a s o n a b l yw e l l h o w e v e r ，p e r f o r m a n c e d r a s t i c a l l yd e c r e a s e sw h e na n yo f t h em a x i m a li t e m s e t sb e c o m e sl o n g e r i nd a t am i n i n ga p p l i c a t i o n sw h e r ei t e m sa r ec o r r e l a t e d ，m a x i m a lf r e q u e n t i t e m s e t sc o u l db el o n g a l g o r i t h md m ri so n em i n i n ga l g o r i t h mp r o p o s e dt od e a lw i t h a s s o c i a t i o nr u l e s a l g o r i t h md m rl i e so nt h ec o n c e p to fe q u i v a l e n t c l a s si nr o u g hs e tt h e o r y c o n s i d e r i n gt h el o c a l i z a t i o no fa s s o c i a t i o n r u l e ss e t t i n gs i n g l em i n i m u ms u p p o r tt h r e s h o l d ，i tb r i n g sf o r w a r dt h e d i s c o v e r yo fn u m e r o u si t e mc l a s st h r o u g hm a n ym i n i m u ms u p p o r t sa n d e v a l u a t i n gr u l et h o u g hi n t e r e s t i n g n e s s a l g o r i t h md m _ rs i g n i f i c a n t l y r e d u c e st h et i m ef o rp a t t e r nm a t c ha n di sm o r ee f f i c i e n tt h a nt h ep r e v i o u s a l g o r i t h m s t h ep r o b l e mo fi n c r e m e n t a lu p d m i n go fm f ii sa l s oi n t r o d u c e d ，a n d c o r r e s p o n d i n ga l g o r i t h m s ，f a u m f i ，i sp r o p o s e d t h ep r o p o s e d a l g o r i t h mm a k e sf u l l u s eo fab u i l t u pbi t m a t r i xa n dm a xf r e q u e n t i t e m s e t s ( m f i ) ，t h u s i tc a nm a i n t a i na n du p d a t em f ie f f i c i e n t l y a n y m o r e ，t h ee x e c u t i o no fa l g o r i t h m si si l l u s t r a t e d k e yw o r d sd a t am i n i n g ，a s s o c i a t i o nr u l e ，r o u g hs e t ，b i t m a t r i x ， f r e q u e n ti t e m s e t s v i i 中南人学博士学位论文 目录 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均己在在论文中作了明确的说 明。 作者硌趟吼啤年卫月一日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位论文。 作者签名：汹师签作者签名：主必师签 1 1 1 日期： 丛月一日 中南大学硕士学位论文 第一章绪论 1 1 课题的提出和意义 第一章绪论 数据挖掘是近年来信息技术领域讨论和研究的热点之一，也是数据库系统 应用研究的一个重要方向。知识发现和数据挖掘受到当今国际人工智能和数据 库界的广泛关注。关联规则是知识发现中的一个重要课题，旨在发现事务数据 库中不同项目之间的有趣联系。数据挖掘是信息科学革命性发展的直接结果。 从信息科学的发展历程来看，首先成熟的是以文件系统为代表的数据采集技术。 当数据的收集不再是问题以后，对数据的处理( 包括存贮，检索等等) 就成为系 统的瓶颈。于是数据库技术应运而生。数据库技术成功地解决了上述问题后， 人们就希望能够对数据进行更好的分析和理解。这样就产生了数据仓库和在线 数据分析( o l a p ) 技术。这部分地解决了人们的需求。比如o l a p 的工具支持多维 分析，一定范围内的决策支持等等。但人们还需要对数据做出更深入的分析( 如 数据的分类、聚类、特征等等) 。以难以想象的高速度所收集的大量数据被存贮 在超大规模的数据库中，远远超出了人们能理解它的能力，这被称为“数据丰 富而信息贫乏 。结果是数据库往往变成了“数据的坟墓 ，很少被人访问， 决策更多地不是依赖信息，而是依赖决策者的直觉。数据挖掘就是要改善“数 据丰富而信息贫乏 的情况，将“数据的坟墓变成隐藏着知识的“金矿 。 1 2 数据挖掘概述 一般来说，数据挖掘指的是从大量的数据中发现知识。“大量的数据意 味着可伸缩性对数据挖掘甚至比效率还重要，而知识不仅可以是频繁的模式， 也可以是异常乜1 。有人认为数据挖掘和数据库中的知识发现( k d d ) 是同义词，但 也有人认为数据挖掘是k d d 的一个步骤。 数据挖掘包括如下的过程口1 ： ( 1 ) 数据清洗( 从数据中去除噪音和不一致的数据) ； ( 2 ) 数据整合( 不同来源的数据被合并在一起) ； ( 3 ) 数据选择( 选择和分析任务相关的数据) ； ( 4 ) 数据变换( 将数据转换成挖掘所需要的形式) ； ( 5 ) 模式析取( 这是数据挖掘的核心过程，用来从数据中找到模式) ； 1 中南大学硕士学位论文 第一章绪论 ( 6 ) 结果评价( 通过定义好的兴趣度量标准来衡量所挖掘到的结果是否有 趣) ； ( 7 ) 知识表示( 用可视化或其它形式将挖掘到的知识展现给用户) 。 数据挖掘是一个交互的过程，用户用数据挖掘语言来表达挖掘任务，用户 也能对挖掘到的知识提出意见，这些意见将被用来指导对数据库进行更进一步 的挖掘。怎样将用户已有的知识结合到数据挖掘过程中是很有趣的研究问题。 数据挖掘可以在传统意义的关联数据库上实行，也很适合在数据仓库上实 行。 因为数据仓库一般己实现了数据挖掘的前两个步骤的功能( 即数据清洗和 数据整合) 。现在的很多数据库管理系统也在考虑加大对数据挖掘的支持力度， 将许多数据挖掘所需要的功能整合到数据库管理系统中去。文献 4 中还提出了 一个设想，能在o l t p 系统上几乎不增加额外开销就能实现数据挖掘的功能。其 它的可以挖掘的数据源包括事务数据库、面向对象数据库、空间数据库、时态 数据库、文本数据库以及i n t e r n e t 上的万维网网页等等一1 。著名的万维网网页 搜索引擎g o o g l e 就是在搜索引擎中使用数据挖掘技术的成果婿1 。 数据挖掘按挖掘的知识来分类，大致包括特征( c h a r a c t e r i z a t i o n ) 、关 联( a s s o c i a t i o n ) 、分类( c l a s s i f i c a t i o n ) 和聚类( c l u s t e r ) 等等叫。特征是指找 出每一类数据的特点，关联是找出不同属性之间的相关性，分类是指对给出的 几类数据找出分类的规则，聚类是指将给出的数据按相似性分成几类嘲。近年来 新提出的一个有趣的数据挖掘任务是在关系数据库中象使用w e b 搜索引擎一样 按关键字搜索数据n0 1 1 3 。另一个有趣的挖掘任务是，在 1 2 中，作者不是研究在 给定的环境下什么模式是频繁的，而是给定的模式在什么环境下是频繁的。在 1 3 一文中作者还讨论了使用统一模型来对待所有的数据挖掘任务的问题。 数据挖掘的主要技术有： 1 ) 数据清理：这包括清除无用的、冗余的或者是错误的数据。 2 ) 关联分析：在大型数据集中发现项之间感兴趣的关联关系。例如：我们 可以通过对数据的分析得出啤酒一 尿布的关联规则。即买啤酒的人往往会买尿 布。 3 ) 分类分析：通过分类可以找出描述并区分数据类或概念的模型( 或函 数) ，以便能够使用模型预测类标记未知的对象类。 4 ) 聚类分析：根据最大化类内的相似性、最小化类间的相似性的原则将对 象聚类或分组，所形成的每个簇( 聚类) 可以看作一个对象类，由它可以导出 规则。聚类也便于分类编制，将观察到的内容组织成类分层结构，把类似的事 件组织在一起。 2 中南大学硕士学位论文 第一章绪论 5 ) 演变分析：描述行为随时间变化的对象的规律或趋势，并对其建模。包 括时间序列分析、序列模式分析、周期模式匹配等。 6 ) 异常分析：一个数据集中往往包含一些特别的数据，它们数据的行为和 模式与一般的数据不同，这些数据对象称为“异常。对“异常”数据的分析 称为“异常分析 。它在欺诈甄别、网络入侵检测等邻域有着广泛的应用。 从数据分析的观点来看，数据挖掘分为两类：描述性数据挖掘和预测性数 据挖掘。描述性数据挖掘以概要方式描述数据，提供数据有趣的一般性质；预 测性数据挖掘分析数据，建立一个或一组模型，产生关于数据的预测。 本文对数据库中的关联规则挖掘算法进行研究。 1 3 关联规则挖掘概述 关联规则挖掘的目的是寻找在大量的数据项中隐藏着的联系或者相关性。 当收集了越来越多的数据时，人们逐渐对这些数据中隐含着的联系产生兴趣。 比如说电子商务中商家对顾客网上所购买的东西之间的联系很有兴趣n 钉。发现 这些有趣的关联能帮助他们做出决策( 比如市场分析、信用卡风险鉴别、网络故 障诊断、天体识别、基因的相似性分析等等) n 部。 关联规则的一个典型例子是售货篮分析。售货篮分析指的是通过对顾客在 同一售货篮中所购买的商品之间的联系的分析来调查顾客的购买行为模式。它 能辅助零售商来制定市场营销策略。比方说，在卖场时，将顾客经常一同购买 的商品( 如牛奶和面包) 放置在一起，刺激顾客的消费欲望，增加销售额。 我们将在2 1 节中给出关联规则挖掘的形式化定义。这最早是在 1 6 中提 出的，它还提出了关联规则的挖掘可以分为两个步骤。第一步是找出数据库中 的所有频繁项集的集合及其支持度，第二步是通过第一步所得到的频繁项集的 信息来生成所有的关联规则。其后的研究绝大多数也遵循这两个步骤。又因为 第二个步骤计算量相对非常小，因为它不需要到数据库中去读取信息，所以关 联规则挖掘研究的重点就放在了第一个步骤上，即查找数据库中的所有频繁项 集及其支持度。 查找频繁项集按策略来说可分为三大类，即经典的、基于精简集( c o n d e n s e d r e p r e s e n t a t i o n ) 的和基于最大频繁项集( m a x i m a lf r e q u e n ti t e m s e t ) 的。 经典的方法查找频繁项集集合的全集。这其中，广度优先搜索策略n 7 j 町的典 型代表是a p r i o r i 算法，它也是最经典最有影响力的算法。深度优先搜索策略 的典型代表是f p - g r o w t h 算法n 引。这两类算法各有优缺点啪3 。其它比较著名的 算法还包括t r e ep r o j e c t i o n 雎1 1 ，p a s c a l r 2 2 1 等。 中南大学硕士学位论文第一章绪论 与经典的方法不同，基于精简集的方法并不查找频集项集的全集，而是查 找它的一个称为精简集的子集口3 1 ，可以利用这个子集再生出完整的频繁项集的 全集及其支持度来。理想的精简集应该远小于整个频繁项集集合，这样就可以 极大地提高挖掘的效率。己知的精简集包括。l o s e d 集1 ，f r e e 集 矧，d i s j u n c t i o n - f r e e 集捌，n d i 乜7 1 等。开采精简集的主要算法包括a - c l o s e 渊 等。 基于最大频繁项集的方法与前面两者都不同，它查找最大频繁项的集合。 所谓最大频繁项集，指的是它本身是频繁项集，但它的任何一个超集都不是。 文献 1 8 中提出的著名的a p r i o r i 属性，频繁项集的任何子集都是频繁项 集，最大频繁项集集合的每一个元素的所有子集的集合的并集就是完整的频繁 项集集合，但这还不能求出每一个频繁项集的支持度，还需要对数据库额外做 一趟扫描以求出每一个频繁项集的支持度，这一趟扫描通常很花时间。基于最 大频繁项集的算法包括m a x m i n e r 例，p i n c e r s e a r c h 啪3 ，m a f i a 口妇等。 不管是查找完整的频繁项集集合，还是精简集，还是最大频繁项集集合， 都存在算法的效率问题。有许多方法己被提出用来加速关联规则挖掘的算法。 这包括从减少数据库的扫描趟数入手的p a r t i o n 口2 3 算法，d i c 算法口踟等，从加快 支持度计数入手的t i d 链n 6 和垂直格式b 钔等，从候选集剪枝入手的d h p 算法 1 ，o s s m 算法啪3 等以及其它一些方法如抽样叫1 ，增量式挖掘“，并行等。这 些方法极大地提高了关联规则算法挖掘的效率。 4 3 中用真实数据而非人造数 据对己有的算法性能做了大量测试。 4 4 发现现有算法的性能还很有改善的余 地。 与传统观点不同，有一派的观点认为，关联规则挖掘的数据库应该使用垂 直的数据格式，而不是传统的水平格式，这方面的工作包括 4 5 - 4 7 等。 有些应用领域并不要求关联规则挖掘有非常精确的结果，但需要很快的系 统的响应速度，这时人们常常考虑在降低精确性的基础上极大的增加挖掘速度 4 8 。 随着应用领域要求的不同，关联规则有不少变种h9 1 。可以大致将它们分为 两类：一类是从扩展关联规则的形式出发，增强关联规则的描述能力，这包括 5 0 5 1 等。另一类是从提出新的兴趣度量标准出发，更好地表达用户的兴趣所 在，这包括 5 2 5 4 等， 5 5 中更是分析了几种已经提出的兴趣度量标准。这些 变种增强了关联规则的描述能力，拓广了关联规则的应用领域。 对关联规则的研究还包括分布式环境下的关联规则挖掘蜘7 1 、和时态相关的 关联规则挖掘、基于粗集理论上的模糊关联规则挖掘璐9 1 、在多个关系上挖掘 关联规则呻1 、更好的结果表达方式( 如可视化) 1 、在关联规则挖掘中保护数 4 中南大学硕士学位论文第一章绪论 据的隐密以保护用户的隐私泓喵1 、给用户提供更多的交互机制等等。关联规则 还能对其它的数据挖掘任务提供支持，比如分类砸瑚1 。 1 4 本课题的国内外研究现状 1 9 8 9 年8 月举行的第1 1 届国际联合人工智能学术会议上首次出现数据库 知识发现( 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 ) 这个术语，随后引起了国 际人工智能和数据库等领域专家的广泛关注。1 9 9 5 年在加拿大蒙特利尔市召开 了第一届数据库知识发现与数据挖掘( k d d d a t am i n i n g ) 国际学术会议，此后， k d d d a t am i n i n g 国际学术会议每年召开一次，随后在数据库、人工智能、信 息处理、知识工程等领域的国际学术刊物也纷纷开辟了k d d 专题或专刊。经过 十多年的努力，数据挖掘技术的研究己经取得了丰硕的成果。 自a g r a w a lr 1 9 9 3 年提出布尔型关联规则问题及相应的a p r i o r i 算法以 来，数据挖掘领域的研究者在关联规则与分类规则挖掘上做了大量的工作。关 联规则挖掘的研究工作主要包括：a p r i o r i 算法框架的扩展、关联规则的扩展、 量化关联规则的挖掘、关联规则的增量式更新、挖掘以及最大频繁项集的挖掘 和无须生成候选项集的关联规则研究等。 数据挖掘领域的研究者目前在挖掘关联规则上也做了大量的工作，主要致 力于改进算法，提高算法速度和有效性。由于在许多应用中，数据库是动态的， 这就要求挖掘出的规则具有动态可更新性。针对新增数据库添加到原数据库中 的关联规则更新问题，现有的研究主要包括：( 1 ) 如何利用已有的频繁项集来 高效地挖掘增量更新频繁项集； ( 2 ) 如何挖掘项目加权的增量更新关联规则； ( 3 ) 考虑到新增数据库的新颖性问题时，如何加权挖掘增量式的关联规则。 对这一问题，国际上进行广泛的研究。目前尤其是快速更新最大频繁项集 和加权关联规则的问题受到许多学者的极大关注，并相继提出了多种快速发现 最大频繁项集的挖掘算法如m a x m i n e r 、p i n c e r s e a r c h 、i d m f i a 、b i t m a t r i x 旧1 、 w d m f s m l 等，这些算法能有效地挖掘出静态事务数据库中的最大频繁项集或加权 关联规则。然而，在现实世界事务数据库中，数据是随时间的变化而变化的。 商业机构中的交易是一个不断进行的过程，交易行为的模式很可能随时间呈现 出某种发展趋势，使得当前已发现的最大频繁项集或加权关联规则可能不再生 效，而新的有效最大频繁项集或加权关联规则有待于重新去发现。能否有效地 挖掘出动态事务数据库中的频繁项集或关联规则成为衡量一个算法好坏的关键 因素，因此，迫切需要设计高效的算法来更新、维护和管理已挖掘出来的最大 中南大学硕士学位论文 第一章绪论 频繁项集。目前国内外在对这一问题的相关研究中提出了i u a 口、f i u a 别、 f u f i a 7 驯、f u m f i a 口4 1 等算法，这些算法充分利用原有的信息来高效地发现新的最 大频繁项集或加权关联规则或频繁项集。但它们主要是针对f p t r e e 进行的算 法研究。 文献 3 0 介绍了最大频繁项集生成算法p i n c e rs e a r c h ，它采用了自底向上 和自顶向下的双向搜索策略，但其第k 次的最大频繁候选项集( m f c s ) 是由k 1 次的m f c s 中的非频繁项集去掉一个f p t r e e 结点元素来生成，产生了过多的无 用候选项集，其c 。的生成采用类似于a p r i o r i 生成候选项集的方法，对海量数 据库来讲，将陷于n p 难的陷阱。 朱玉全等将关联规则挖掘更新的问题划分为三种情况n 引：( 1 ) 事务数据库不 变，最小支持度发生变化时，最大频繁项集的高效更新问题；( 2 ) 最小支持度不 变，一个事务数据集d b 添加到事务数据库d b 中去时，如何生成最新事务数据 库d bud b 中的最大频繁项集；( 3 ) 最小支持度不变，从事务数据库d b 中删除一 个事务数据集d b 后，如何高效地生成事务数据库d b - d b 中的最大频繁项集。至 于其它情况，可由上述3 种情况组合而成，因此，这3 种情况是更新问题的基 础和核心。他讨论了样本数据库在发生以上3 种变化的情况下的关联规则的更 新算法。但其操作是通过重新构建p i n c e r - s e a r c h 树的方法来实现关联规则的 更新过程。该文献仅对第二种情况进行了讨论，提出了d w a r i u a 算法。宋余庆 等人也讨论了通过对已有的p i n c e r s e a r c h 树的剪枝更新来实现关联规则的快 速更新算法i u a ，但i u a 仅能就一个方向实现对f p t r e e 的快速剪枝和重新生成， 算法的效率不高。吉根林等人首次考虑在p i n c e r s e a r c h 算法的基础上按自顶 而下和自底而上两个方向对f p - t r e e 进行剪枝，利用原有的f p t r e e 快速生成 新的最大频繁项集( m f s ：m a x i m u mf r e q u e n ti t e ms e t s ) ，提出了f u m f i a 算 法，进一步提高了快速更新f p t r e e 生成m f s 的效率。但总体而言，由于f p t r e e 的存储开销总体偏大，相应的创建与剪枝算法的复杂度较高。 为节省样本数据的存储空间，文献 6 9 提出了最大频繁项集生成算法 b i t m a t r i x ，它也采用了自底向上和自顶向下的双向搜索策略，并通过构造 b i t m a t r i x 来存储数据库，只需对数据库访问读取一次即可得到数据库的位阵表 示，在以后的运算中不再访问数据库。但其第k 次的m f c s 也需在过多的无用候 选项集中剪枝生成。 为实现对无用的非频繁项集的双向剪枝，m a u r i c eh o u t s m a ，r r y m o n 联合 提出了基于集合运算的关联规则挖掘算法m j 7 1 ，该算法适合于从两个方向上实现 对非频繁项集的剪枝操作，能较快地构造m f s 集合。但该算法仍需较大的候选 集合的存储开销。 6 中南大学硕士学位论文第一章绪论 文献 7 0 介绍了一种基于集合枚举树的最大频繁项集生成算法w d m f s ，它也 通过构造b i t m a t r i x 来存储数据库的集合枚举树，并通过对集合枚举树采用自 底向上和自顶向下的双向搜索策略，分别利用一个搜索方向搜索到的信息对另 一个方向的候选项集进行剪枝，提高了发现最大频繁项集的速度，显著降低了 系统的i o 成本和c p u 时间。 文献 7 8 提出了长模式关联规则模型及相应的挖掘算法。但对于长模式关 联规则的增量式更新问题，国内外目前对这一问题仅只开展了一些理论探讨， 还没有很好的模拟和实现相关算法。 1 5 本文的研究内容与目标 本文提出了一种增量式更新最大频繁项集算法的研究课题，旨在充分利用 已有的一切信息( 如旧的最大频繁项集、原来的b i t m a t r i x 等) ，以高效地更新 最新事务数据库中所有的最大频繁项集，实现关联规则的快速挖掘与更新。 1 6 本文的贡献 本文主要在以下方面有所贡献： ( 1 ) 利用粗集理论中关于等价类的概念，4 2 节针对单维布尔关联规则挖掘 问题提出了d mr 算法。 d 趾r 算法按照某项交易是否出现将事务集合划分为不同等价类，并通过对 各项交易定义最低交易频度，间接设定多个最小支持度阈值，以更好地进行频 繁项集的挖掘，并在此基础上生成强关联规则集合。由于单个最小支持度阈值 不能反映数据表中各项交易出项频率的差别，提出使用多个最小支持度的办法 进行频繁项集的发现，并利用兴趣度对规则进行评价，能较好地反映事务数据 库的本质。 ( 2 ) 针对前期更新频繁项集的算法主要是针对频繁模式树来进行单双向剪 枝与重构，需要额外的存贮空间和较大的运算开销，5 2 节提出了一种增量式更 新最大频繁项集算法f a u m f i 。 算法f a u m f i 针对最大频繁项集的更新问题的几种典型情况，充分利用已有 的一切信息( 如旧的最大频繁项集、原来的b i t m a t r i x 等) ，以高效地更新最新 事务数据库中所有的最大频繁项集。 7 中南大学硕士学位论文 第一章绪论 1 7 本文的组织 木文的组织如下： 在讨论数据挖掘技术的发展的基础上，着重研究与剖析经典的关联规则挖 掘算法。对两种最为重要，最为经典，最有影响力的算法a p r i o r i 算法和 f p g r o w t h 算法进行深入探讨，并分析了两者的优缺点。 然后提出了几个可以和其它算法相结合的增量式挖掘关联规则的算法 ( d mr 算法及针对三种不同情况的f a u m f i 算法) 。它们可以辅助绝大多数关联 规则的挖掘算法( 如a p r i o r i 算法) 提高效率。 关联规则挖掘算法是特别为大规模数据集设计的一种相当高效的算法，关 于关联规则算法的研究往往强调的是计算效率，而不是对算法产生规则的解释。 基于粗集针对单维布尔关联规则挖掘问题的d m _ r 算法按照某项交易是否出现将 事务集合划分为不同等价类，并通过对各项交易定义最低交易频度间接设定多 个最小支持度阈值，以更好地进行频繁项集的挖掘，并在此基础上生成强关联 规则集合。 由于现实世界事务数据库中，数据是随时间的变化而变化的，当前已发现 的最大频繁项集可能不再生效，而新的有效最大频繁项集重新去发现。因此， 迫切需要设计高效的算法来更新、维护和管理已挖掘出来的最大频繁项集。目 前国内外已有的算法主要是针对频繁模式树来进行单双向剪枝与重构，需要额 外的存贮空间和较大的运算开销。对此，提出一种增量式更新最大频繁项集算 法f a u m f i ( f a s ta l g o r i t h mf o ru p d a t i n gm a x i m u mf r e q u e n ti t e m s e t s ) ，该算 法将充分利用已有的一切信息( 如旧的最大频繁项集、原来的b i t m a t r i x 等) ， 以高效地发现最新事务数据库中所有的最大频繁项集，并分析了算法的效率。 在第一章中，我们讨论关联规则挖掘的背景，意义，应用范围和国内外的 研究概祝，并指出了本文的贡献。第二章介绍了数据挖掘技术的基本理论和经 典的关联规则算法，主要是对a p r i o r i 和f p g r o w t h 这两种算法做了剖析，并 讨论了相关的改进研究。第三章讨论基于粗集的单维布尔关联规则的挖掘算法， 提出了d m _ r 算法。第四章针对更新、维护和管理已挖掘出来的最大频繁项集的 迫切需要，提出了一种增量式更新最大频繁项集算法f a u m f i ，该算法将充分利 用已有的一切信息，以高效地发现最新事务数据库中所有的最大频繁项集，并 分析了算法的效率。最后一章总结全文并给出了以后的研究方向。 8 中南火学硕士学位论文 第二章经典的关联规则挖掘算法 第二章数据挖掘的基本理论与经典的关联规则挖掘算法 在上一章中我们已经对关联规则挖掘的任务进行了简单的介绍。本章我们 来看关联规则挖掘的形式化定义与经典的关联规则挖掘算法。 2 1 关联规则的基本理论 2 1 1 关联规则的基本概念 关联规则是由a g r a w a l 等人首先提出的一个重要k d d 研究课题，它反映了 大量数据中项集之间有趣的关联或相关联系。 设i = t 2 j m ，是元素的集合，其中的元素称为项( i t e m ) 。记d 为交易 ( t r a n s a c t i o n ) t 的集合，这里交易t 是项的集合，并且t i 。对应每一个交易 有惟一的标识，如交易号，记作t i d 。设x 是一个工中项的集合，如果x c t ，那么 称交易t 包含x 。 一个关联规则是形如x y 的蕴涵式，这里x c i ，y c i ，并且x n y = 矿。规则 x j y 在交易数据库d 中的支持度( s u p p o r t ) 是交易集中包含x 和y 的交易数与 所有交易数之比，记为s u p p o r t ( x jy ) ，即s u p p o r t ( x j y ) = l t ：xuy t ，t d i ld 规则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 j y ) ，即c o n f i d e n c e ( x j y ) = l t ：x u y e t ，t d ) l l t ：x - c t ，t d ) i 项的集合称为项集( i t e m s e t ) 。包含k 个项的项集称为k 一项集。项集的出现 频率是包含项集的事务数，简称为项集的频率、支持度或计数。如果项集满足最 小支持度( 由用户或领域专家设定) ，则称它为频繁项集。给定一个交易集d ，挖掘 关联规则问题就是产生支持度和置信度分别大于最小支持度( m i n _ s u p ) 和最小 置信度( m i n c o n f ) 的关联规则。 2 1 2 关联规则挖掘的方法步骤 关联规则挖掘主要是强规则挖掘，一般由发现大项集和生成强规则两部分 组成。具体步骤为： ( 1 ) 找出存在于事物数据库中的所有大项集：先计算候选卜项集( k 一项集 是含有k 个项目的集合) ，找出频繁1 一项集；根据频繁卜项集，确定候选2 9 中南大学硕士学位论文第二章经典的关联规则挖掘算法 项集，找出频繁2 一项集，依次类推，直到不再有候选项集为止。最后得到 的项集就是所求的大项集。 ( 2 ) 用大项集按生成规则和置信度产生所需要的强规则。 2 1 3 关联规则的种类 ( 1 ) 按变量的类别 基于规则中处理的变量的类别，关联规则可以分为布尔型和数值型。布尔型 关联规则处理的值都是离散的、种类化的，它显示了这些变量之间的关系。数值 型关联规则可以和多维关联或多层关联规则结合起来，对数值型字段进行处理， 将其进行动态的分割，或者直接对原始的数据进行处理。 ( 2 ) 按数据的抽象层次 基于规则中数据的抽象层次，可以分为单层关联规则和多层关联规则。在单 层关联规则中，所有的变量都没有考虑到现实的数据是具有多个不同的层次的。 在多层关联规则中，对数据的多层性进行了充分的考虑。 ( 3 ) 按数据的维数 基于规则中涉及到的数据的维数，关联规则可以分为单维和多维。单维关联 规则是处理单个属性中的一些关系；多维关联规则是处理各个属性之间的某些 关系。 2 1 4 关联规则挖掘的任务 关联规则挖掘的任务可以分解为两个子问题： ( 1 ) 支持度高于支持度阈值的项集我们称为频繁项集。第一步就是要找出所 有的频繁项集及其支持度。 ( 2 ) 有了所有的频繁项集及其支持度的信息后，我们就能生成所需要的关联 规则。例如，项集a b c d 和项集a b 是频繁项集，那么关联规则a b = y c d 的可信度 就等于s u p p o r t ( a b c d ) s u p p o r t ( a b ) 。这里我们用s u p p o r t ( x ) 表t 项集x 的支 持度，即d 中有百分之多少的事务包含x 。如果a b = c d 的可信度高于可信度阈 值，那么这就是一条我们需要的关联规则。 容易看出，第二步的计算量很小( 因为它不需在数据库中读取信息) ，所以， 关联规则挖掘的任务主要是第一个步骤，即找出所有的频繁项集。 找出所有的频繁项集并不是件轻而易举的事情。所有可能的频繁项集的 个数与全部项目的个数成指数关系。令iil = m ，即一共有m 个不同的项目，那 最多可能有2 个频繁项集。想像一下m 为1 0 0 0 或1 0 0 0 0 是很平常的事情，2 很 容易就成为一个天文数字。这2 一个项集都是i 的子集，它们构成了一个高度为 m 的格( l a t t i c e ) 。下面我们来看一个例子。事务数据库d 中有5 条事务，如表 2 一l 所示。 l o 中南大学硕士学位论文第二章经典的关联规则挖掘算法 表2 - 1一个事务数据库d 。 t i di t e m s 1 0 0 a ，c ，d 2 0 0 a ，b ，c 3 0 0 b ，c ，e 4 0 0 b ，c ，d 5 0 0 a ，b ，c ，e 数据库d 中可能的频繁项集构成了一个格如图2 - 1 所示。 图2 - 1d 的项集格 这个格中一共有3 2 个项集，高度为5 0 依据支持度阈值的设定，这个格中 只会有一部分项集是频繁项集。例如，支持度阈值设定为2 ( 4 0 ) 时，这3 2 个项 集中只有1 5 个是频繁的。 一个天真的办法就是测试项集格中所有项集的支持度，这样只需对事务数 据库d 做一趟扫描。但显然，这对于比较大的m 来说是行不通的。 项的集合称为项集( i t e m s e t ) 。包含k 个项的项集称为k 一项集。项集的出现 频率是包含项集的事务数，简称为项集的频率、支持度或计数。如果项集满足最 小支持度( 由用户或领域专家设定) ，则称它为频繁项集。给定一个交易集d ，挖掘 中南大学硕士学位论文第二章经典的关联规则挖掘算法 关联规则问题就是产生支持度和置信度分别大于最小支持度( m i n _ s u p ) 和最小 置信度( m i n _ c o n f ) 的关联规则。 这样我们就需要按照一定的顺序分次分批地对项集格( i t e m s e tl a t t i c e ) 这 个巨大的搜索空间进行访问。经典的关联规则挖掘算法需要找出所有的频繁项 集，即遍历搜索空间中的每一个频繁项集所代表的结点。有两种主要的搜索策 略，它们是广度优先策略( b r e a d t h f i r s t ) 和深度优先策略( d e p t h f i r s t ) 。在 本章的2 2 节我们将介绍a p r i o r i 算法，它使用的是广度优先的搜索策略。 a p r i o r i 算法提出之后，几乎所有其它采用广度优先搜索策略的算法都使用 a p r i o r i 算法的框架。在本章的2 3 节我们将介绍f p g r o w t h 算法，它借助于一 个称为f p 树的数据结构实现了深度优先的搜索策略。这两种经典关联规则挖掘 算法分别是这两种搜索策略的典型代表，包含了这两种搜索策略的所有的最重 要的思想。需要指出的是，广度优先和深度优先这两种搜索策略各有所长，谁 更好一直是学术界激烈讨论的问题，至今没有定论。我们将在本章的小结中( 2 5 节) 对这两种最经典最重要的算法做一个简单的比较和总结。 2 2a p rio fi 算法 2 2 1a p rio fi 算法流程 a p r i o r i 是一个通过挖掘频繁项集来挖掘布尔型关联规则的很有影响的算 法。 a p r i o r i 这个名字的来由是因为这个算法使用了频繁项集的一些特性，即先 验的知识( p r i o rk n o w l e d g e ) ，我们将在2 2 2 中加以介绍a p r i o r i 算法使用 的是广度优先的搜索策略，分层的( 1 e v e l w i s e ) 迭代的( i t e r a t i v e ) 搜索项集格 空间。已得到的k 一项集的信息会被用来加速对( k + 1 ) 一项集的搜索。k 一项集表示 长度为k 的项集。 a g r a w a l 等人于1 9 9 3 年首先提出了挖掘顾客交易数据库中项集间的关联规 则，并设计了一个基本算法，其核心是基于频集理论的递推方法，即基于两阶段 频集思想的方法，将关联规则的设计分解为两个子问题：发现频集。这个子问 题是最重要的，开销最大，因此，各种算法主要致力于提高发现频集的效率。根 据所获得的频繁项集，产生强关联规则。根据定义这些规则必须满足信任度阈 值。由于步骤中的操作极为简单，因此挖掘关联规则的整个性能就由步骤中 的操作处