（计算机软件与理论专业论文）基于约束的关联规则挖掘.pdf

华中科技大学硕士学位论文 摘要 关联规则挖掘是发现大量数据中项集之间有趣的关联或相关关系。它是数据挖 掘中的一个重要的问题，其研究目标是找出满足最小支持度和最小可信度要求的关 联规则。 针对传统的关联规则发现模式缺乏用户的主动参与和控制、缺乏针对性、效率比 较低等缺点，在可交互的关联规则发现模式中，允许用户对挖掘的对象提出各种约 束。要挖掘满足约束的规则，一种方法是先生成所有的规则，然后再检验其是否满 足约束。这种方法不能避免大量无用的规则的生成，因而效率很低。另一种方法是 利用约束的性质，将其推进到频繁项集的生成过程中，使得产生的只是满足约束的 项集，相对来说这个集合要小很多，而且效率高。为了将约束很好地推进到频繁项 集的生成过程中，需要分析约束的性质。从性质上可将约束分为五类：反单调的、 单调的、简洁的、可转变的和不可转变的。其中，单调、反单调和简洁的约束可以 很好地推进到a p r i o r i 类算法中；可转变的约束只能在f p g r o w t h 类算法中实现； 不可转变的约束现在还没有很好的解决办法。 用户的约束需求往往是多个的，而c a p 算法框架只能实现反单调、简洁这两种约 束在此基础上，c a p + 算法框架中增加了单调、可转变、不可转变约束的实现思路， 能同时实现多种约束。 针对单调约束的性质，m c a 算法在“单调基础项集”概念的基础上，利用反单调 约束进行剪枝，能同时实现单调、反单调约束。该算法是基于a p r i o r i 逐层搜索算 法的，是正确与完整的。实验结果表明，该算法具有很好的性能。 关键词：数据挖掘，关联规则，约束，单调性 华中科技大学硕士学位论文 a b s t r a c t a s s o c i a t i o nr u l em i n i n gi so n eo f t h em o s ti m p o r t a n tt a s k so fd a t am i n i n g ，w h i c hi s t of i n dt h er u l e sw i t ht h es u p p o r ta n dc o n f i d e n c eg r e a t e rt h a n t h et h r e s h o l d s t h e r ea r em a n yd i s a d v a n t a g e si nt h et r a d i t i o n a la s s o c i a t i o nr u l em i n i n gp r o c e s s f o r e x a m p l e ，u s e r sc a l l te x p r e s st h e i rf o c u sa n dc o n t r o lt h em i n i n gp r o c e s s ，a n da l s oi t s n o t e f f i c i e n t b u ta l lt h e s ed i s a d v a n t a g e sc a nb er e s o l v e di nt h ei n t e r a c t i v ea s s o c i a t i o nr u l e m i n i n gp r o c e s s t h e r ea r et w ow a y st o m i n ea l lr u l e sw h i c hs a t i s f yc o n s t r a i n t st h eu s e r d e f i n e d o n ei sg e n e r a t ea n dt e s t ，i nw h i c ha l lr u l e si n c l u d i n gl a r g en u m b e ro fu s e l e s s r u l e sa r eg e n e r a t e df i r s t l y ，t h e nt e s t e dw i t hc o n s t r a i n t s t h eo t h e ri st op u s hc o n s t r a i n t si n t o t h ef r e q u e n ti t e m s e t sm i n i n gp r o c e s ss ot h a tt h er e s u l t sa r ej u s tt h o s ei t e m s e t ss a t i s f y i n g c o n s t r a i n t s b e c a u s e 也er e s u l t sb e c o m es m a l l e r , t h el a t t e rw a yi s m o r ee f f i c i e n t a c c o r d i n gt ot h e i rp r o p e r t i e s ，c o n s t r a i n t sc a nb ed e v i d e di n t oa n t i m o n o t o n e ，m o n o t o n e ， s u c c i n c t ，c o n v e r t i b l ea n di n c o n v e r t i b l ec o n s t r a i n t s a l lt h ea n t i - m o n o t o n e ，m o n o t o n ea n d s u c c i n c tc o n s t r a i n t sc a l lb ep u s h e dd e e p l yi n t ot h ea p r i o r ia l g o r i t h m , w h i l ec o n v e r t i b l e c o n s t r a i n t sc a r to n l yb ep u s h e di n t of r e q u e n t - p a t t e r ng r o w t ha l g o r i t h ma n di n c o n v e r t i b l e c o n s t r a i n t sc a nb ed o n ei nn e i t h e r t h ec a p + f r a mc a l li m p l e m e n td i f f e r e n tk i n d so fc o n s t r a i n t s i nc o n t r a s t 晰t 1 1c a p , m o n o t o n e ，c o n v e r t i b l e ，i n c o n v e r t i b l ec o n s t r a i n t sa r ea l lc o n s i d e r e d a c c o r d i n gt ot h ep r o p e r t yo fm o n o t o n ec o n s t r a i n t ，t h en e wa l g o r i t h mn a m e dm c a ， w h i c hi sb a s e do nt h en e wn o t i o no fb a s e dm o n o t o n es o t s c o m b i n e dw i t ha n t i m o n o t o n e c o n s t r a i n t ， c a l l s i m u l t a n e o u s l yi m p l e m e n t m o n o t o n ec o n s t r a i n ta n da n t i - m o n o t o n e c o n s t r a i n t sw i t hg o o d e f f i c i e n c y k e y w o r d s ：d a t a m i n i n g ，a s s o c i a t i o nr u l e ，c o n s t r a i n t ，m o n o t o n e u 独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他 个人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：扬药、 日期：硼碍年令月多日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权华中科技大学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 保密口，在年解密后适用本授权书。 本论文属于 不保密囱。 ( 请在以上方框内打“”) 学位论文作者签名：物葛、 日期：呻争年呤月易日 华中科技大学硕士学位论文 1 1 研究背景 1绪论 随着数据库技术的迅速发展以及数据库管理系统的广泛应用，商业、政府和科 研机构积累了越来越多的数据。在这些大量的数据背后势必隐藏着许多重要的信息， 可以支持人们进行决策。然而，目前的数据库系统可以高效地实现数据的录入、查 询、统计等功能，但无法对数据进行更高层次的分析，无法发现数据中存在的关系 和规则，无法根据现有的数据预测未来的发展趋势，从而导致了“数据爆炸但知识 贫乏”的现象。因此，从已有的资料中发现有价值的信息或知识，达到为决策服务 的目的，成为迫切的任务。 数据挖掘( d a t am i n i n g ，简记为d m ) ，又称知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e s ，简汜为k d d ) ，是人工智能、机器学习与数据库技术相结合的产物，它指 的是从大型数据库或数据仓库等数据存贮中提取人们感兴趣的知识，这些知识是隐 含的、事先未知的、潜在的有用信息“。“。 关联规则挖掘( a s s o c i a t i o ne u l em i n i n g ) 是数据挖掘研究的一个重要分支，用 来发现大量数据中项集之间有趣的关联或相关关系。从大量商务事务记录中发现有 趣的关联关系，可以帮助许多商务决策的制定，如分类设计、交叉购物等。挖掘关 联规则已经成为近年来数据挖掘研究领域中的一个热点。1 。 交互式关联规则挖掘能有效的体现用户的关注，并能显著提高挖掘的效率。用 户的关注就是约束，如何利用约束，更快更好的挖掘出用户感兴趣的规则，这是本 文的研究所在。 1 2 国内外研究概况 1 2 1 数据挖掘的国内外研究状况 k d d 一词，首先出现在1 9 8 9 年的第十一届国际联合人工智能学术会议上，到目 前为止，由美国人工智能协会主办的k d d 国际研讨会，其规模由原来的专题讨论会 发展到国际学术大会，研究重点也逐渐从发现方法转向系统应用，注重多种发现策 华中科技大学硕士学位论文 略和技术的集成，以及多种学科之间的相互渗透。1 9 9 3 年i e e e 率先出版了k d d 技术 k n o w l e d g ea n dd a t ae n g f n e e r i n g 会刊。1 9 9 5 年数据挖掘界召开了第一届知识发现 与数据挖掘国际学术会议，该会议是由1 9 8 9 至1 9 9 4 年举行的四次k d d 国际研讨会 发展起来的。1 9 9 7 年k l u w e r s 出版社开始出版专题杂志d a t am i n i n ga n dk n o w l e d g e d i s c o v e r y 。1 9 9 8 年a c m 一8 i g k d d ，即a c m 下的数据库中的知识发现专业组成立。另 外还有一些国际或地区性数据挖掘会议，如“知识发现与数据挖掘太平洋亚洲会议” ( p a k d d ) ，“数据库中知识发现原理与实践欧洲会议”( p k d d ) ，和“数据仓库与知识 发现国际会议”( d a w a k ) 。并行计算、计算机网络、信息工程等其他领域的国际学会 或学刊也把数据挖掘和知识发现列为专题和专刊讨论。此外，在i n t e r n e t 上还有不 少k d d 电子出版物，其中以半月刊k n o w l e d g ed i s c o v e r yn u g g e t s 最为权威 ( h t t p ：w w w k d n u g g e t s c o m s u b s c r i b e h t m l ) 。 目前，数据挖掘己成为一个炙手可热的行业，世界上知名大学的研究机构和各 大i t 公司的研究部门，如i b m ，s a s ，s p s s ，c o g n o s ，b o ，a c c r u e 等，对此 都投入了大量精力进行研究，并取得了诸多的研究成果，形成了很多的数据挖掘商 业产品。从类型上，这些典型的产品可以分为以下几种： 1 提供广泛的d m 能力：i b m 的i n t e l l i g e n tm i n e r ，s a s 的e n t e r p r i s em i n e r ， 美国斯坦福大学智能数据库系统实验室的d b m i n e r 挖掘系统，i b m 的a l m a d e n 实验室 的d b 2i n t e lli g e n tm i n e rf o rd a t a ： 2 为特定部门求解特定问题：u n i e a 公司的r e s p o n s em o d e l e rs e g n e n t o r ，i b m 公司的b u s i e s sa p p o c a t o p m 等： 3 与服务一起提供：n e o v i s t a ，h y p e r p a r a l l e l ，h n cm a r k s m a n ： 4 黑匣工具：g r o u p m o d e l l ，m o d e l m a x ，n e w r a l w a r e 的p r e d i c t ： 5 解决客户问题：m a r k e t i e rp a r e g r a m ，e x c h e m g ea p p li c a t i o n 等。 与国外相比，国内对d m 的研究稍晚一点。1 9 9 3 年国家自然科学基金首次支持对 该领域的研究项目。目前，国内的许多科研单位和高等院校竞相开展知识发现的基 础理论及其应用研究，这些单位包括清华大学、中科院计算技术研究所、空军第三 研究所、海军装备论证中心等。其中，北京系统工程研究所对模糊方法在知识发现 中的应用进行了较深入的研究，北京大学也在开展对数据立方体代数的研究，华中 2 华中科技大学硕士学位论文 科技大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、吉林大学等 单位开展了对关联规则发现算法的优化和改造；南京大学、四川联合大学和上海交 通大学等单位探讨、研究了非结构化数据的知识发现以及w e b 数据挖掘等。 1 2 2 关联规则发现的研究工作 关联规则挖掘是发现大量数据中项集之间有趣的关联或相关关系。它是数据挖 掘中的一个重要问题，其研究目标是找出满足最小支持度和最小可信度要求的关联 规则。关联规则是形如a j b 的蕴涵式，其中a 、b 都是项集。一般地，关联规则发现 分为找出所有的频繁项集和由频繁项集产生强关联规则两个步骤，其中找出所有的 频繁项集是关联规则算法的性能瓶颈。因此绝大部分对关联规则算法的研究都集中 在第一步，即如何在保证精度的基础上提高算法的运行效率，其中精度是指所找出 的频繁项集的满足要求的程度。 1 9 9 3 年，a g r a w a l 等提出了关联规则发现问题“3 ，同时提出了第一个频繁项集发 现算法。此后，在各种问题背景下，围绕着提高算法效率和结果的有用性( 即用户 对其感兴趣程度) ，研究者们提出了各种频繁项集发现算法”“1 。根据这些算法的研 究重点不同，可将其分为基本频繁项集发现算法和增强频繁项集发现算法。 基本频繁项集发现算法致力于设计各种算法框架，高效地发现所有支持度大于某 个不变的最小支持度的频繁项集。但是它存在一些缺陷，比如所发现的频繁项集的 有用性不高、发现的频繁项集数量过多、遗漏用户感兴趣的频繁项集等等。 增强频繁项集发现算法致力于提高发现结果的有用性，它通过引入概念层次结 构、约束条件、可变支持度等方式来克服基本频繁项集算法的缺陷。 基本频繁项集发现算法是在单数据库、单概念层次和最基本要求( 即使用相同的 最小支持度发现所有频繁项集) 的条件下发现频繁项集，它是其它更r 高级”频繁 项集发现算法的基础。根据算法提出的时间和算法原理的不同，可将它们细分为 a p r i o r i 算法出现之前的算法、a p r i o r i 类算法、基于分块的算法、基于采样的算法、 新出现的高性能算法、基于最大频繁项集的算法和频繁封闭项集发现算法等。其中 后三类算法在分析强相关性数据时有明显的性能优势。 1 9 9 3 年，a g r a w a l 等提出面向单个事务的频繁项集发现算法a i s 。1 9 9 5 年， h o u t s m a 等提出面向集合的频繁项集发现算法s e t m 川。这是两种在a p r i o r i 算法出现 华中科技大学硕士学位论文 之前的算法，它们根据每个事务中的已发现频繁项集和此事务中的其它项生成候选 频繁项集，因此生成的非候选频繁项集数量很多，导致性能在各种情况下都不如 a p r i o r i 算法，因此没有得到实际应用。 1 9 9 4 年，a g r a w a l 等提出简单高效的频繁项集发现算法a p r i o r i ”1 。该算法是基 于广度优先搜索策略的，它利用了频繁项集的反单调性频繁项集的子集必定是 频繁的，通过在第( k 1 ) 次扫描数据库后所得到的长度为( k 一1 ) 的频繁项集( 简记为 ( k 一1 ) 一频繁项集，下同) 生成k 一候选频繁项集，然后在第k 次扫描数据库时统计k 一 候选频繁项集的频繁度。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 算法需要多次扫描数据库，造 成沉重的i o 负担。 a g r a w a l 等还发现，a p r i o r i 算法的最大运行时间开销阶段是刚开始的几次生成 一检验循环，特别是发现2 一频繁项集的循环，在此阶段生成了大量无效的候选频繁项 集，限制了算法的效率。 大部分改进的算法把注意力集中在生成大项目集的优化上，主要有四种优化方 法：基于划分的方法，基于h a s h 表的方法，减少对交易数据库的遍历次数，基于随 机采样技术的方法。 1 9 9 5 年s a v a s e r e 等设计了一个基于划分原理的p a r t i t i o n 算法”1 。p a r t i t i o n 算法将原数据库逻辑地分成若干个互不相交的子数据库，其中每个子数据库都充分 小，足以放入内存。由于任何频繁项集至少在其中一个子数据库中是频繁的，所以 可先分别发现每个子数据库中的频繁项集，然后将这些频繁项集汇总作为总候选频 繁项集，再扫描一遍原数据库发现其中满足全局支持度条件的频繁项集。由于每个 子数据库可放入内存，所以发现其中的频繁项集不需要使用非常耗时的i 0 操作， 算法总体执行速度比较快。另外，p a r t i t i o n 算法还是一种本质并行算法。不过，当 子数据库数目增大时，p a r t i t i o n 算法生成的无效总候选频繁项集数目快速增长，导 致效率降低，因此p a r t i t i o n 算法在较大数据库上的性能不如a p r i o r i 算法。b r i n 等提出d i c ( 动态项集计数) 算法，可视为一种串行化的p a r t i t i o n 算法“。 华中科技大学硕士学位论文 采用哈希修剪技术在快速发现2 一项集的过程中十分有效，p a r k 等在这个方法的 基础上引入哈希技术来改进产生2 一项集的方法，提出a p r i o r i 算法的一种改进- - d h p ( 直接乱散与删剪) 算法“。通过使用哈希技术，d h p 比a p r i o r i 算法少生成一个数 量级的2 一候选频繁项集，从而提高了算法性能。另外，由于所生成的2 一候选频繁项 集数量大大减小，所以d h p 算法可在发现2 一频繁项集之后就从数据库中删掉无需再 考虑的事务和项。 a p r i o r i t i d 算法“”与a p r i o r i 算法的思路基本一致，不同在于：前者在经过一 次扫描数据库后，不再利用数据库来计算项目集的支持度，而利用候选项集来计算， 因而减少了对交易数据库的遍历次数，提高了效率。 基于采样的技术，是先利用从数据库中抽取出来的采样，生成一些可能的规则， 然后再针对数据库中剩余的部分验证这些规则。t o i v e n e n 在文献 1 3 中提出的随机 抽样技术可以节约相当可观的z o 代价，但是一个很大的缺点就是产生的结果不精 确，即存在所谓的数据扭曲( d a t as k e w ) 。分布在同页面上的数据时常是高度相关 的，可能不能表示整个数据库中模式的分布，由此而导致的是采样5 的交易数据所 花费的代价可能同扫描遍数据库相近。l i n 和d u n h a m 讨论了反扭曲( a n t 卜s k e w ) 算法来挖掘关联规则“，他们引入的技术使得扫描数据库的次数少于2 次。b r i n 等 “”提出的算法使用比传统算法少的扫描遍数来发现频繁项集，同时比基于采样的方 法使用更少的候选集，这些改进了算法在低层的效率。具体的考虑是：在计算k 一项 集时，一旦我们认为某个( k + 1 ) 一项集可能是频繁项集时，就并行地计算这个( k + 1 ) 一 项集的支持度。该算法需要的总的扫描次数通常少于最大的频繁项集的项数。这里 他们也使用了杂凑技术，并提出产生“相关规则”( c o r r e l a t i o nr u l e s ) 的一个新 方法。 z a k i 等认为，在频繁项集发现过程中使用采样技术至少可提高一个数量级的速 度，而且精度损失不多“。1 9 9 6 年，t o i v o n e m 提出一种基于采样的频繁项集发现算 法“，其基本思想是对数据库进行采样，形成采样数据库；然后用较小的最小支持 度发现采样数据库中的频繁项集s ：再将s 和它的负边界b d 一( s ) 合并，构成候选频 繁项集s u b d 一( s ) ；接着扫描一遍原数据库从s v 0b d 一( s ) 中发现所有频繁项集s 7 ：如 果其中b d 一( s ) 包含频繁项集，那么说明原数据库中可能存在还未被发现的频繁项集， 5 华中科技大学硕士学位论文 这时需要用公式s j = s + ub d 一( s 7 ) 叠代计算直到s 不再增大，然后将s j 作为候选集再扫 描一遍原数据库，发现所有被遗漏的频繁项集。此算法在一般情况下只需扫描数据 库一次，在最差情况下需要扫描两次。1 9 9 7 年，p a r k 等提出两个可调节精度的算法 d s 和s h “。其中d s 算法可视为d h p 算法加入采样技术之后的推广。d s 和s h 算法可 用于为了提高效率而允许损失一些精度的场合。 a p r i o r i 类算法在数据库为高密度、长模式或低支持度等情况下性能急剧下降， 针对这个问题，一些新的高性能频繁项集发现算法被提出来。 2 0 0 0 年，a g a r w a l 等提出一种全新的高效算法t r e e p r o j e c t i o n ”。此算法构造 一个词典树，并根据已发现的频繁项集，将数据库投影到一组精简的子数据库上。 由于词典树提升了检验候选频繁项集的效率，并且此算法还使用其它各种提高效率 的技术，所以t r e e p r o j e c t i o n 算法比a p r i o r i 算法的性能高一个数量级。 2 0 0 0 年，h a n 等提出一种不需要生成候选频繁项集的算法f p - g r o w t h 。“。此算法 是基于深度优先搜索策略的：首先扫描两遍数据库，生成信息高度压缩的高频模式 树，该树中仍保留了项集的关联信息；然后在其上递归生成条件高频模式树，同时 找出所有频繁项集。由于此算法不需要生成候选频繁项集，避免了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 算法。两者各有所长。 如果一个频繁项集不是其它频繁项集的真子集，那么称此频繁项集为最大频繁项 集。最大频繁项集集合的每一个元素的所有子集的集合的并集就是完整的频繁项目 集集合，但每一个频繁项目集的支持度不能由最大频繁项集推导出来，因此还需要 对数据库扫描一次并进行计数，这一趟扫描的时间花销通常很大。典型的基于最大 频繁项目集的算法是z a k i 等在1 9 9 7 年提出的算法c u s t e r a p r o “。该算法首先使用 聚类技术将相关的项集分组，以此得到最大频繁项集集合的超集，然后生成此超集 的所有子集，将这些子集作为候选频繁项集，最后扫描遍数据库验证此候选频繁 项集。c l u s t e r a p r 算法的性能优于a p r i o r i 算法，逊于p a r t i t i o n 算法。在文献 2 3 中s h e n 等提出与z a k i 算法类似的基于最大频繁项集的频繁项集发现算法，并且此 算法具有本质并行性。 6 华中科技大学硕士学位论文 = = = = = = = = = = = = = = = = = = = = = = = = ；= = ；= = = = 一 封闭项集是一组事务都包含的项的最大项集。一个数据库的频繁封闭项集集合与 其频繁项集集合的信息量相等，但是前者比后者小得多，因此发现频繁封闭项集能 够减少数据库的扫描遍数和c p u 开销，从而提升频繁项集发现的效率，并大幅减少 输出冗余信息。 1 9 9 9 年，p a s q u i e r 等提出基于a p r i o r i 算法框架的频繁封闭项集发现算法 c l o s e “。相对于a p r i o r i 算法，c 1 0 s o 算法在分析强相关数据时具有明显的性能优 势，可将数据库扫描遍数减少到原来遍数的1 4 到i 2 。 1 9 9 9 年，z a k i 等提出使用垂直数据库结构的频繁封闭项集发现算法c h a r m “”。 c l o s e 算法和c h a r m 算法在发现长模式或低支持度阈值时效率不高。2 0 0 0 年，p e i 等 提出基于f p - g r o w t h 算法框架的频繁封闭项集发现算法c l o s e t o “。 项一般具有概念层次关系。当存在概念层次关系时，用户通常对包含不同概念层 次的项的规则感兴趣，并称这种规则为广义关联规则或多层关联规则发现。广义关 联规则发现算法提高性能的关键也在于广义频繁项集发现的效率。 1 9 9 5 年，s r i k a n t 等提出直接推广a p r i o r i 算法的广义频繁项集发现算法 c u m u l a t e 算法。此算法将数据库中所有事务的每个项的所有高层次概念项都加入 到此事务中，形成扩展事务，然后再套用a p r i o r i 算法。由于和高层次概念有关的 项集一般有较大的支持度，和低层次概念有关的项集一般有较小的支持度，而 c u m u l a t e 算法对不同类型项集只能使用相同的最小支持度，导致其发现结果不太有 用。 1 9 9 5 年，h a n 等在a p r i o r 算法基础上提出多层频繁项集发现算法m lt 2 l 1 1 。 该算法首先将所有项替换为最高层次上的项，同时设置较高的最小支持度，然后找 出满足支持度要求的第层次频繁项集l l 。在l l 基础上，将所有项替换为第二层次 上的项，降低最小支持度，找出第二层次频繁项集l 2 。反复进行，直到l k 为空。 在传统的关联规则发现中，用户仅仅设置了初始闽值( 包括支持度，置信度) ， 然后就是等待系统交付最终的结果。系统往往需要经过几个小时或者更长多时问来 产生大量的关联规则，而在这些关联规则中，往往只有小部分是用户关心的。显然， 如果用户能对关联规则的发现过程进行指导，使得产生的关联规则就是用户需要的， 这样不仅规则的数目大大减少了，而且挖掘的效率更高m 1 。 华中科技大学硕士学位论文 1 9 9 4 年，k 1 e m e t t ir e n 等提出在关联规则中应用模板以发现用户感兴趣的关联 规则m 1 。模板是用户自定义词汇表示的规则，其中词汇使用项集进行定义。如果一 条规则满足模板，那么这条规则就是用户感兴趣的。但是由于用户自定义模板的复 杂性，频繁项集发现算法难以高效地检验一个频繁项集是否满足模板。l 9 9 5 年，f u 提出元规则指导的关联规则发现。“。元规则可视为k l e m e t t i n e n 等提出的模板概念 的一种简单推广。这种类型的发现算法首先由用户给定要发现的关联规则的元模式 或模板，然后根据这些模板在数据库中发现与模板相适应的实际存在的关联规则。 f u 提出了两个相应的算法：大谓词增长算法和直接p 一谓词剥试算法。 文献 3 2 】中研究了在提供布尔表达式约束情况下的关联规则发现问题。这种布尔 表达式约束允许用户指定他所感兴趣的关联规则的集合，这种约束不仅可以用来对 事务数据库进行预加工，而且可以把它集成在挖掘算法内部，从而提高算法的执行 效率，文中根据这种集成方式的不同给出了三种实现项约束的算法：m u l t i p l ej o i n s 、 r e c o r d e r 、d i r e c t 。其中项约束就是要求所发现的频繁项集必须包含或不包含用户所 指定的若干项。这三种算法推广了a p r i o r i 算法的候选频繁项集生成过程，在生成 候选频繁项集时检验其满足项约束的情况。崔立新提出d i r e c t 算法的改进算法 s e p a r a t e 。 用户往往只对满足一定约束条件的频繁项集感兴趣，因此如果频繁项集发现算法 只发现满足用户指定约束条件的频繁项集，那么将大量节省用户处理不感兴趣的频 繁项集的时间，同时也可提高算法执行速度。 1 9 9 8 年，n g 等在分析一般挖掘过程缺乏用户反馈与指导的弊端的基础上，提出 两阶段的关联规则挖掘系统结构，提出并分析了反单调性、简洁性这两种性质的约 束。这里，约束形式可以是项的合取和否定，以及求均值等集合操作“。按照约束 的性质将约束分为反单调、简洁、顽固的三大类，同时将反单调、简洁性的约束进 行组合，将其运用到频繁项集的剪枝过程中，提出了可使用单维变量约束的c a p 算 法。该算法是基于a p r i o r i 算法的，通过使用约束对中间频繁项集进行剪枝，使得 频繁项集的发现效率提高了一个数量级。 随后l a k s h m a n a n 等提出可使用二维变量约束的频繁项集发现算法 。由于二维 变量约束大部分不满足反单调性、或者简洁性，因此提出一个“类简洁性，约束， 8 华中科技大学硕士学位论文 先将二维的约束转换或弱化成两个一维的简洁性约束，然后再运用c a p 算法。简单 的说，就是把多维约束转换成一维约束，这里提出了一个转换的基本思路。 在对约束的性质讨论上，前后共提出五类性质的约束，分别是反单调的、单调 的、简洁的、可转变的、不可转变的，针对这些性质，关联规则挖掘算法又有了很 大发展5 “+ ”1 。 j e a n f r a n c o i s 等人在文献 3 8 ，3 9 ，4 0 ，4 1 ，4 2 中提出一个“负边界”的思想，将 单调约束与反单调约束结合起来，提出了一个在a p r i o r i 基础上的实现框架，同时 论证了将反单调约束推进到a p r i o r i 算法中是有利的，论证了f r e e 集是一种反单调 的约束。 在文献 4 3 中提出了一个利用阳树实现简洁约束的算法f p s ，而且能实现复杂 的简洁约束，有很高的性能。 p e i 等提出可使用可转变约束的频繁项集发现算法( 算法f i c 。、f i c ) ”。其基 本思想是对项集进行某种次序的排序，使得约束满足反单调性或单调性。可转变的 约束可以在f p g r o w t h 算法框架中实现，不能在a p r i o r i 算法框架中实现。文献 4 4 中提出一种前缀增长函数( p r e f i xi n c r e a s i n gf u n c t i o n ) ，利用该函数，可以比较容易 的判断一些形式复杂的约束函数是否是可转变的，是哪种可转变的。这里，将可转 变的约束细分为单调可转变的、反单调可转变的、强可转变的三类。该算法不能解 决多个需要不同方式排序的可转变约束。 支持度约束也是一种反单调的约束。a p r i o r i 算法适用的前提之一是对于所有频 繁项集使用相同的最小支持度。如果在数据库中存在出现频率较低的项( 称为稀疏 项) ，同时用户对这些稀疏项又比较感兴趣，那么需要使用可变的最小支持度以发现 包含稀疏项的频繁项集，同时不发现太多的用户不感兴趣的频繁项集。 l e e 将数据库根据项出现频率分为几部分，然后对每部分应用不同的最小支持度 进行频繁项集发现。此方法难以发现跨越不同部分的频繁项集。而h a r t 等将若干相 关的稀疏项合并为高层次概念的项，以增加稀疏项的支持度，但这种方法无法发现 包含单个稀疏项的频繁项集。1 9 9 9 年，l i u 等提出的m s a p r i o r i 算法是a p r i o r i 算 法的一种推广“。此算法赋予每个项一个最小项支持度( m i s ) ，并以频繁项集所包 9 华中科技大学硕士学位论文 含的项的最小项支持度作为频繁项集支持度的推广定义。通过将项根据其m i s 值从 小到犬排序，就可满足推广的频繁项集的逆单调性。2 0 0 0 年，w a n g 等提出实现非统 一的支持度( s u p p o r t ) 约束的算法a d a p t i v ea p r i o r i ”，将a p r i o r i 算法推广到使 用可变的最小支持度的情况，这样可以避免很多“无意义”的中间频繁项集的生成， 使得结果对于用户更有意义。 a p r i o r i 算法首先解决的是布尔关联规则( b o o e a na s s e t i a t i nr u l e s ) 的挖掘问 题，其后又扩展到对数值型关联规则( o u a n t i t a t i v ea s s o c i a t i o nr u l e s ) 及分类关 联规则( c a t e g o r i c a la s s o c i a t i o nr u l e s ) 的挖掘，与布尔关联挖掘不同的是在挖掘 前需要对数值及分类属性进行必要的预处理。 长模式频繁集的发现，也有很多的进展。1 9 9 7 年，o u n o p u l o s 等提出一种可用 于长模式发现的随机频繁项集发现算法“”。算法循环地试图随机扩展一个工作项集， 直到失败。由于是随机算法，所以此算法不能保证发现所有的长模式，但能够有效 地发现其中的一部分，不过它不能处理内存放不下的数据库。z a k i 等提出的m a x e c l a t 和m a x c l i q u e 算法使用a p r i o r i 算法框架，试图在其生成一检验循环开始前识别长模 式，以减少候选频繁项集的生成数目。l i n 等提出p i n c e r s e a r c h 算法“，此算法同 样使用a p r i o r i 算法框架，并在其生成一检验循环中识别长模式。1 9 9 8 年，b a y a r d o 等提出专门的长模式发现算法m a x m i n e t 算法“，此算法按照启发式知识对项进行 排序，以提高发现长模式的效率。在某些数据集上m a x m i n e r 算法比a p r i o r i 算法 快1 到2 个数量级，而且其运行时间与最大频繁项集数目和数据库大小成线性关系， 与最长频繁项集的长度无关。 由于关联规则挖掘是一项非常耗时的工作，从而导致了很多并行算法的相关研 究，这些并行算法的主要特征是充分利用并行系统的强大运算能力，通过对发现频 繁集这个任务的有效分割提高算法的效率。 频繁项集发现算法发展到目前为止，已经获得了长足的进步。作为许多面向应 用的数据挖掘技术的基础，提高频繁项集发现算法的性能、满足不同应用背景下的 不同要求，依然是一项值得研究的课题。 另外，还有很多其他的关联规则的研究。l i u 等人提出利用x 2 检验缩小规则数量 的方法”“1 ，p a d m a n a b h a n 等人提出置信驱动的关联规则挖掘算法( b e l i e f d r i v e n 华中科技大学硕士学位论文 m e t h o df o rd i s c o v e r i n gu n e x p e c t e dp a t t e r n ) 3 ，同时提出了两个算法e s t m e r g e 和c u m u l a t e ，解决泛化( g e n e r a l f z e d ) 关联规则的问题。s a v a s e r e 等“2 1 研究了挖掘 否定关联规则的问题，他们的方法是使用分组信息如项之间的层次关系，以及现有 数据中的正关联性来导出与正关联中的项“相近”的项之间的否定规则。 1 3 本文的主要工作 本文对数据挖掘中的基于约束的关联规则挖掘问题进行了深入的研究。在分析 约束的性质后，对已有的一种带约束的关联规则挖掘算法框架进行了扩充，并实现 了一个新的带单调约束的挖掘算法。本文主要工作如下： 1 介绍了目前数据挖掘技术与关联规则挖掘的国内外概况。 2 介绍了数据挖掘的基本知识，重点分析了数据挖掘的系统结构，适用的各种 应用模型。 3 关联规则挖掘综述。介绍关联规则挖掘的有关概念，给出了关联规则挖掘的 一般步骤，针对传统的关联规则挖掘过程在表现用户的主动探索方面的不足，介绍 了能体现用户关注的基于约束的交互式关联规则挖掘过程。 4 针对约束的性质，重点分析和研究了反单调、单调、简洁、可转变的、不可 转变的这五类约束，并根据其性质特征，分别分析了在关联规则算法中的实现方式。 针对单调约束的性质，提出了一个单调基础项集的新概念，并实现了一个能同时实 现单调、反单调约束的算法m c a ，从性能上分析其可靠性。并基于这五类约束，改 进了一个能同时实现多种约束的算法框架。 华中科技大学硕士学位论文 2 数据挖掘的概念及相关知识 2 1 数据挖掘概述 在传统的决策支持系统中，知识库中的知识和规则是由专家或程序人员建立的， 是由外部输入的。而数据挖掘的任务是发现大量数据中尚未被发现的知识，是从系 统内部自动获取知识的过程。对于那些决策者明确了解的信息，可以用查询、联机 分析处理( o nl i n ea n a l y t i c a lp r o c e s s i n g ，简写为o l a p ) 或其它工具直接获取；而另 外一些隐藏在大量数据中的关系、趋势，即使是管理这些数据的专家也是没有能力 发现的，这些信息对于决策可能又是至关重要的，这类问题就可以用数据挖掘束解 决。 数据挖掘指的是从大型数据库或数据仓库等数据存贮中提取人们感兴趣的知 识。这些知识是隐含的、事先未知的潜在有用的信息。数据挖掘是目前国际上数据 库和信息决策领域的最前沿研究方向之一。 数据挖掘技术作为种重要的商业决策技术已经越来越受到国际上的重视，并 成为企业界研究的一个热点。例如，电讯企业通过分析登陆记录来识别线路故障： 保险公司在制定新的保险项目时通过历史记录来预测某项投保的风险性：超市通过 分析购买记录来作出能够促进销售的经营策略等等，无一不用到数据挖掘的方法。 数据挖掘发现的知识可以直接提供给决策者，用以辅助决策过程，或者提供给 领域专家，修正专家已有的知识体系，也可以作为新的知识转存到应用系统的知识 存储机构中，比如专家系统规则库等。 数据挖掘是一个多学科交叉领域，涉及到机器学习、模式识别、统计学、智能 数据库、知识获取、数据可视化、高性能计算、专家系统等多个领域。数据挖掘的 成果可咀用在信息管理、过程控制、科学研究、决策支持等许多方面。 2 2 数据挖掘的过程 数据挖掘包括如下的过程。“： 1 数据清洗：从数据中去除噪音和不一致的数据 1 2 华中科技大学硕士学位论文 2 数据整合：将不同来源的数据合并在一起； 3 数据选择：选择和分析任务相关的数据： 4 数据变换：将数据转换成挖掘所需要的形式： 5 模式析取：这是数据挖掘的核心过程，用来从数据中找到模式； 6 结果评价：通过定义好的兴趣度量标准来衡量所挖掘到的结果是否有趣； 7 知识表示：用可视化或其它形式将挖掘到的知识展现给用户。 数据挖掘是一个交互的过程，用户可以对挖掘到的知识提出意见，这些意见将 被用来指导对数据库进行更进一步的挖掘。 2 3 数据挖掘的系统结构 典型的数据挖掘系统结构如图2 1 所示，它由以下几个主要成分组成： 1 ) 数据库、数据仓库或其他信息库：这是个或一组数据库、数据仓库、电子 表格或其他类型的数据库。可以在数据上进行数据清理和集成。 2 ) 数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或数据仓库服 务器负责提取相关数据。 3