（计算机应用技术专业论文）基于区别度概念格的关联规则挖掘算法设计.pdf

河南大学研究生硕士学位论文第j 页 摘要 关联规则是最常见的知识表示方法之一，频繁项集挖掘是关联规则挖掘中的 重要课题，它已经被广泛的应用于各个领域。概念格是一个非常有用的形式分析 工具，通过i - i a s 图它可以生动、简洁的表现这些概念之间的泛化和特化关系。另 外，概念格中的每个节点本质上是一个频繁项目集，并且频繁项集和概念格的内 涵之间有一种一一对应的关系。因此，利用概念格来挖掘频繁项集和关联规则显 得水到渠成。基于概念格的频繁项集与关联规则的挖掘，很多学者对此已经进行 了深入的研究并取得了很大的进步，但大部分都是假定由属性组成概念格中内涵 的重要性均匀平等、同等重要，而基于这种思想的概念格提取关联规则存在着明 显的不足：( 1 ) 这将导致组合爆炸和冗余问题；( 2 ) 由于建格时没有考虑到属性 重要性的差别，形成包含所有属性的概念格的结点，因此建格时间长、效率低。 针对以上不足，本文首先提出一个新的概念内涵区别度，基于内涵区别 度来建造概念格将有力的减少格中的频繁项集的数量，主要原因是区别度低的内 涵将不参与格的构造，这在一定的程度上缓和了组合爆炸的问题，使关联规则提 取的难度系数也有所降低。其次本文给出了基于内涵区别度的格的构造算法，不 再是建造概念格的每一个节点都扫描数据库，而是有条件的扫描数据库并计算和 重置区别度的值，这就减少了数据库扫描的次数，从而减少了生成概念格的时间， 提高效率。另外，改进了基于概念格的关联规则提取的算法，将置信度剪枝的概 念引入基于概念格的关联规则提取中，减少了关联规则提取时置信度计算的时间， 从而有效的提高了关联规则提取的效率，最后将本文提出的改进算法应用了基于 区别度概念格的关联规则提取中，并给出了相应的提取算法。基于概念格的关联 规则的挖掘关键在于概念格的构造，首先将频繁项集和内涵区别度存储在格上， 然后在创建好的概念格上根据规则生成关联规则。 本文的主要贡献如下： 第j l 页河南大学研究生硕士学位论文 1 ) 提出内涵区别度的概念，基于内涵区别度建造概念格将有力的减少频繁项 集的数目，缓和组合爆炸的问题； 2 ) 给出了基于区别度概念格的频繁项目集提取算法，在构造概念格时不再每 一个节点的生成都扫描数据库，减少了扫描数据库的次数，提高了时间效 率； 3 ) 改进了基于概念格的关联规则提取的算法，将置信度剪枝的概念引入基于 概念格的关联规则提取中，从而有效的提高了关联规则提取的效率； 4 ) 将本文提出的改进算法应用了基于区别度概念格的关联规则提取中，并给 出了相应的提取的算法。 关键词：关联规则；内涵区别度；概念格；置信度 河南大学研究生硕士学位论文第l li 页 a b s t r a c t a s s o c i a t i o nr u l e si so n eo ft h em o s tk n o w l e d g er e p r e s e n t a t i o nm e t h o d s ，f r e q u e n t p a t t e r nm i n i n ga saf u n d a m e n t a ld a t am i n i n gt a s kh a sw i d e s p r e a da p p l i c a t i o n si nm a n y d i f f e r e n td o m a i n s c o n c e p tl a t t i c ei sav e r yu s e f u lf o r m a la n a l y s i st o o la n dc a l ls h o wt h e r e l a t i o n s h i pa m o n gt h ec o n c e p t sv i v i d l ya n db r i e f l y i na d d i t i o n , e v e r yn o d ei nt h e c o n c e p tl a t t i c e si saf r e q u e n ti t e m s e t s ，a n dt h e r ei sao n e - t o - o n ec o r r e s p o n d e n c eb e t w e e n c o n c e p ti n t e n s i o n sa n df r e q u e n ti t e m s e t s a b u n d a n tl i t e r a t eh a sb e e nc o n d u c t e di n - d e p t h r e s e a r c hi nm i n i n gf r e q u e n ti t e m s e t sa n da s s o c i a t i o nr u l e sb a s e do nt h ec o n c e p tl a t t i c e h o w e v e r , m o s to ft h e md i dn o tt a k ei n t oa c c o u n tt h ed i f f e r e n c e so fa t t r i b u t e sw h e n c o n c e p tl a t t i c ei sb u i l d t h e r ea r et w oo b v i o u sd e f i c i e n c i e sb a s e do nt h i si d e a ：( 1 ) i tw i l l l e a dt ot h ei s s u e so fc o m b i n a t o r i a le x p l o s i o na n dr e d u n d a n c y ；( 2 ) i tn e e dal o n gt i m et o c o n s t r u c tt h ec o n c e p tl a t t i c ea n dl o we f f i c i e n c y , b e c a u s ew ed i dn o tt a k ei n t oa c c o u n t t h ed i f f e r e n c e so fa t t r i b u t e si nt h ep r o c e s so f b u i l d i n gc o n c e p tl a t t i c e i nt h i sp a p e r , ip r o p o s ean e wc o n c e p tc a l l e dd i s c r i m i n a t i v ei n t e n s i o n e v e r y a t t r i b u t e sh a sad i s c r i m i n a t i v ep o w e r ( d i s p ) i nt h ep r o c e s so fb u i l d i n gc o n c e p tl a t t i c e , b yr e m o v i n gt h ea t t r i b u t e so fl o wd i s c r i m i n a t i v ep o w e r , i tw i l lr e d u c et h en u m b e ro f f r e q u e n ti t e m s e t s ，t h e ns p e e du pt h es t e po fc o n s t r u c t i n gt h el a t t i c e ；n e x t ，t h e r eh a sb e e n an e wm e t h o dt oc a l c u l a t et h ed i s pa n dr e s e tt h ev a l u eu n d e rs o m ec o n d i t i o n ，a n ds c a n t h ed a t a b a s eo ne a c hl a y e r , b yw h i c hi tc a l lr e d u c et h et i m e so fs c a n n i n gt h ed a t a b a s e ， t h e nd e c r e a s et h et i m eo fg e n e r a t ea s s o c i a t i o nr u l e s ；f u r t h e r m o r e , b yi m p r o v i n gt h e a l g o r i t h mo fm i n i n ga s s o c i a t i o nr u l e sb a s e do nt h ec o n c e p tl a t t i c e , w ei n t r o d u c et h e c o n c e p to fc o n f i d e n c et ot h em i n i n ga s s o c i a t i o nr u l e s ，d e c r a e s et h et i m eo fc a l c u l a t e c o n f i d e c ea n di m p r o v et h ee f f i c i e n c y ； f i n a l l y , g i v i n gt h ea l g o r i t h mo fm i n i n g a s s o c i a t i o nr u l e sb a s e do nt h ec o n c e p tl a t t i c eo fd i s c r i m i n a t i v ep o w e rd a t am i n g i n go f 第l v 页河南大学研究生硕士学位论文 a s s o c i a t i o nr u l e sb a s e do nt h ed i s c r i m i n a t i v ei n t e n s i o n , i th a st w os t e p s ：( 1 ) t h eb u i l d i n g o fc o n c e p tl a t t i c e ；( 2 ) m i n i n gf r e q u e n ti t e m s e t sa n da s s o c i a t i o nr u l e sb a s e do nt h e c o n c e p tl a t t i c e t h em a i nc o n t r i b u t i o n sa r ea sf o l l o w s ： 1 ) p r o p o s i n gan e wc o n c e p tc a l l e dd i s c r i m i n a t i v ei n t e n s i o n ，i tw i l lr e d u c e t i o nt h e n u m b e ro ff r e q u e n ti t e m s e t sb a s e do nt h i sc o n c e p t ，t h e ns p e e du pt h es t e po f c o n s t r u c t i n gt h el a t t i c e ； 2 ) p r o p o s i n gan e wm e t h o d t oc a l c u l a t et h ed i s pa n dr e s e tt h ev a l u eu n d e rs o m e c o n d i t i o n ，s c a nt h ed a t a b a s eo ne a c hl a y e r , c a nr e d u c et h en u m b e ro fs c a n n i n g t h ed a t a b a s e ，t h e nd e c r e a s et h et i m eo fg e n e r a t ea s s o c i a t i o nr u l e s ； 3 ) i m p r o v i n gt h ea l g o r i t h mo f m i n i n ga s s o c i a t i o nr u l e sb a s e do nt h ec o n c e p tl a t t i c e , i n t r o d u c i n gt h ec o n c e p to fc o n f i d e n c et ot h em i n i n ga s s o c i a t i o nr u l e s ，a n d d e c r a e s e i n gt h et i m eo f c a l c u l a t ec o n f i d e c ea n di m p r o v et h ee f f i c i e n c y ； 4 ) g i v i n gt h ea l g o r i t h mo fm i n i n ga s s o c i a t i o nr u l e sb a s e do nt h ec o n c e p tl a t t i c eo f d i s c r i m i n a t i v ep o w e r k e yw o r d s ： a s s o c i a t i o nr u l e s ；d i s p ；c o n c e p tl a t t i c e ；c o n f i d e n c e 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位申请。本人郑重声明：所呈交的学位论文是 本人在导师的指导下独立完成的。对所研究的课题有新的见解据我所知。除 文中特别加以说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为获得任何教育、科研机构的擘住或证书而 使用过的材料。与裁一同工作的同事对本研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 。 ， j jy ， 。j ，| 。 学住申请人( 学位论文作者) 签名：至趁蝗 年月功日 ： j；， ? ， r 0 ：。，。+ 二： z j一， 、1 ； 关于学位论文著作权使用授权书 ： 4 。e j 。一| _ ，o | i 二f ? | 本人经河南大学审核批准授子硕士学位。作为学位论文的作者，本人完全 了解并同意河南大学有关保留，使用学住论文的要求，即河南大学有权向国家 图书馆、科研信息机构、数据收集机构和本校图书馆等提供学位论文( 纸质变 本和电子文本) 以供公众检索、查阅。本人授权河南大学出于宣扬、展览学校 学术发展和进行学术交流等目的，可以采取影印、缩印、扫描和拷贝等复制手 段保存、汇鳊学位论文( 甄质文本和电子文本) 。 ( 涉及保密内睿的学位论文在解密后适用本授权书) 学位获得者( 学位论文作者) 釜名：王趁垃 2 0 学位论文指导教师签名： 2 0 0 年iap a 河南大学研究生硕士学位论文第1 页 第1 章绪论 数据挖掘( d a t am i n i n g , d m ) 技术是二十世纪八十年代末兴起的，它是指从大量 数据中挖掘出隐含的、先前未知的、对决策有潜在价值的知识和规则的高级处理 过程。它不仅是面向特定数据库的简单检索查询调用，而且要对这些数据进行微 观、中观乃至宏观的统计、分析、综合和推理，以试图发现事件间的相互联系， 指导实际问题的求解，并且可以利用己有的数据对未来的活动进行预测。关联规 则是数据挖掘中最常见的知识表示方法之一，其效率问题是关联规则在具体应用 中的重要问题之一，因此，本论文提出了基于区别度概念格的关联规则提取算法， 它是对基于概念格的关联规则挖掘算法的改进，该算法不仅提高了挖掘关联规则 的效率，而且非常容易实现对关联规则的可视化，也方便用户寻找感兴趣的规则。 1 1 课题背景 关联规则是数据挖掘中的一个重要课题，它提取的主要目的是发现交易数据 库项目之间有趣且有用的联系。在关联规则挖掘的方法中有两个最基本的也是最 重要的方法：一是a p r i o r i m ，它是最有影响的挖掘布尔型频繁项集的算法，该算法 采用逐层搜索迭代：首先找出频繁1 一项目集j ，在，。上找出频繁2 一项目集，：，依 次类推，直到找不到频繁k 一项目集，。为止；另一个是f p g r o w t h t s l ，该算法将频繁 项目集的数据库压缩到频繁模式树f p t r e e ，然后根据频繁模式树求关联规则。很 多学者对a p r i o r i 和f p g r o w t h 算法进行深入地研究【i - - 9 l ，提出许多改进算法，都在不 同程度上改进了算法的时间复杂度或空间复杂度，但仍然存在着不足： a p r i o r i 主要缺点是需要多次扫描数据库，浪费时间，且有组合爆炸的问题： f p g r o w t h 算法在递归构造条件f p t r e e 及其遍历时的c p u 和存储开销都很大。 这两点都是相应算法本身所固有的问题，单靠简单的算法改进是不能从根本 上解决问题的。要想彻底解决问题，就要另辟蹊径。本文通过和概念格相结合的 方法来解决此问题。 第2 页河南大学研究生硕士学位论文 概念格是形式概念分析的一个有力的工具，它的每个节点是一个形式概念，由 两部分组成：外延，即概念所覆盖的实例；内涵，即概念的描述，该概念覆盖实 例的共同特征。另外，概念格通过h a s s e 图生动和简洁地体现了这些概念之间的泛 化和特化关系。因此，概念格在信息检索、数字图书馆、软件工程和知识发现等 方面得到了一定的应用。在知识发现领域，概念格可以从关系数据中构造出来， 然后从概念格上可以提取各种类型的知识，如蕴含规则、关联规则、分类规则等 等t l o ； 概念格可以很好的表达属性之间的内在关系，并且频繁项集和概念格的内涵 之间有一种一一对应的关系，基于以上优势利用概念格来挖掘关联规则就显得水 到渠成。基于概念格的频繁项集与关联规则的挖掘，很多学者对此已经进行了深 入的研究并取得了很大的进步1 3 s - 5 0 ，但大部分都是假定由属性组成概念格的内涵的 重要性均匀平等、同等重要，而基于这种概念的概念格提取关联规则存在着明显 的不足：由于建格时没有考虑到属性重要性的差别，形成了几乎包含所有属性的 概念格，因此建格时间长、效率低。 针对内涵重要性的不同，本文首先提出一个新的概念内涵区别度，基于 内涵区别度来建造概念格将有力的减少格中的频繁项集，主要原因是区别度低的 内涵将不参与格的构造，这在一定的程度上缓和了组合爆炸的问题，使关联规则 提取的难度系数也有所降低；另外针对概念格的构造过程本文也有了新的突破， 不再是每一层格的建造都扫描数据库，而是有条件的扫描数据库并计算和重置区 别度的值，这就减少了数据库扫描的次数，从而减少了生成概念格的时间；最后 改进了基于概念格的关联规则提取的算法，将置信度度量对关联规则进行剪枝的 概念引入基于概念格的关联规则提取中，减少了关联规则提取时置信度计算的时 间，从而有效的提高了关联规则提取的效率。 基于区别度概念格的关联规则的挖掘主要有两步：一是概念格的构造，首先 将项目集和内涵区别度存储在概念格上，然后在创建好的概念格上根据一定的规 则提取关联规则。 河南大学研究生硕士学位论文第3 页 1 2 国内外研究现状 关联规则挖掘是近年来研究的一个热点，在关联规则挖掘中，频繁项集的挖 掘是一个关键，很多学者在这方面进行了深入的研究并取得了巨大的成就，但它 也有它本身所固有的一些不足。把概念格引入关联规则的挖掘中主要是基于一下 几方面的原因：首先概念格的每个节点本质上是一个频繁项目集，非常有利于关 联规则的挖掘；其次是属性值集合( 即项目集) 之间的关系在概念格之间得到了 体现；最后是基于概念格的关联规则的挖掘可以非常容易实现对关联规则的可视 化，也方便用户寻找感兴趣的规则。以下从常规关联规则挖掘和基于概念格的关 联规则挖掘技术两个方面来讨论其研究的现状。 1 2 1 常规关联规则挖掘研究现状 关联规则作为重要的知识表示方法之一，其挖掘过程就是从数据库的数据中 挖掘出有潜在价值的知识和规则，从而为管理决策者提供高级的数据分析手段。 最早开展关联规则挖掘研究的是美国i b ma l m a d mr e s e a r c hc e n t e r 的a g r a w a l r 领 导的研究组，他们在1 9 9 3 年给出了一个称为a i s 的算法 6 1 ，并于1 9 9 4 年提出了挖掘 关联规则的经典算法a p r i o r i 算法7 】及其改进算法a p r i o r i t i d t s j 。后来有不少学者对关 联规则问题进行了大量的研究。提出了许多a p r i o r i 算法的变形，例如，引入h a s h 方法、划分技术、随机采样、动态项集计数技术等，旨在提高算法挖掘规则的效 率，但这些算法都不能避免a p n o r i 系列算法固有的缺陷，即需要多次重复扫描数 据库，而且可能产生大量的侯选项集。 1 9 9 8 年，r o b e r t o 和b a y a r d o 利用自底向上搜索和项集排序的方法建立了一种挖 掘长型频繁项集的m a x m i n e r 算法 9 1 ，m a x m i n e r 算法提出了“向前看的剪枝策 略，以尽可能早地剪枝无用的候选项集。通常，这种剪枝技术能够有效地缩小算 法搜索空间。除此之外，m a x m i n e r 算法还采用了一种启发式重新排序的技术来增 加超集剪枝效果。但是，m a x m i n e r 算法使用水平数据库格式和宽度优先( b r e a d t h 第4 页河南大学研究生硕士学位论文 f i r s t ) 的搜索策略，可能需要多次扫描数据库，并且会产生许多无用的候选项集， 带来代价昂贵的i 0 开销以及计算开销。 l i n 和k e d e m 提出了一种双向钳形搜索p i n c e r - s e a r c h 算法0 0 1 ，利用自底向上搜索 产生的非频繁项集来约束和修剪自顶向下方向的最大候选频繁项集，能够大大减 少扫描数据库的次数。但是，其候选k 项集c k 的生成方法类似于a p r i o r i 算法的方法， 在数据量非常大时，不可避免地将产生“组合爆炸 问题，而且其生成算法可能 会遗漏某些频繁项集，为此，还需要一个“恢复 程序来生成遗漏的项集，增加 了额外的计算量。p i n c e r - s e a r c h 算法需要维护一个最大频繁模式的超集最大候选 集，其代价通常也是很高的。 2 0 0 0 年j i a w e ih a r t 等人提出了一种不产生候选项集的f p 增长算法f i l l ，利用扩展 前缀树这种数据结构存储经过压缩的频繁项集关键信息，虽然不需要生成频繁候 选项集且只需要扫描数据库两次，但如果长型项集的数量很多，并且如果由原数 据库得到的f p t r e e 的分支很多且分支很长时，该算法将需要构造出数量巨大的条 件f p t r e e ，费时且占用大量空间，并且采用递归算法本身效率也较低。 因为最大频繁项集隐含了所有的频繁项集【i j ，所以有很多学者提出了直接挖掘 最大频繁项集的算法，如g t m o p u l o s 等人提出的随机算法使用了垂直位向量的数据 结构来表示事务数据库，但它无法保证发现所有的最大频繁项集；m a f i a 算法是 b u r d i c k 等人提出来的最大频繁项集挖掘算法，但该算法仍需要多次重复扫描数据 库；d h p 算法利用h a s h 方法来减少2 项集的产生，而且使用剪枝技术来修剪事务数 据库，但构造h a s h 表的开销较大，而且为了剪裁数据库，要扫描数据库中的每个 事务以确定项集在事务中包括那些候选项目；d l g 算法构造关联图来挖掘频繁项 集，不用生成候选2 项集，且需扫描事务数据库一次，但构造关联图的代价较高且 不易实现。挖掘关联规则的挑战性在于要挖掘的数据量很大，算法的效率是关键， 因此有必要研究出占用内存小、f o 操作少、执行速度快的高效算法。 河南大学研究生硕士学位论文第5 页 1 2 2 基于概念格的关联规则挖掘的研究现状 概念格( c o n c e p t l a t t i c e ) 是德国的r w i l l e 教授在2 0 世纪8 0 年代初提出的， 它作为形式概念分析的一种核心的工具，近十几年来已成功地应用于医疗案例数 据分析、c b r ( 基于案例的推理) 、图书馆的信息检索、数据挖掘等领域。概念格 用于数据挖掘有以下优点：1 ) 概念格的每个节点本质上是一个频繁项目集，非 常有利于关联规则的挖掘。2 ) 属性值集合( 即项目集) 之间的关系在概念格之 间得到了体现。3 ) 基于概念格的关联规则的挖掘可以非常容易实现对关联规则 的可视化，也方便用户寻找感兴趣的规则。 概念格构造算法分为两大类：批处理算法和渐进式算法。批处理算法的思想 是首先生成所有概念，然后根据它们之间的直接前驱后继关系，生成边，完成概 念格的构造，例如b o r d a t 的算法，o s h a m 算法，c h e i n 的算法，g a n t e r 的算法， n o u r i n e 的算法等；渐进式算法的思想首先初始化概念格为空，将当前要插入的对 象和现有格中所有的形式概念作交运算，根据交的结果不同采取不同的行动，典 型的算法有g o d i a n ，c a p i n c t o 和t b h 0 的算法等。国内外学者对上述的有些算法 进行研究并做了一些改进，例如改进了的b o r d a t 算法挖掘关联规则【，s l 、扩展概念 格的渐进式构造算、法【5 田、基于索引树的概念格渐进式构造算法1 4 6 1 等等。 基于概念格的关联规则的挖掘，很多专家学者都进行了大量的研究，并取得 了巨大进步1 3 5 - 5 0 | ，但大部分都是假定由属性组成概念格的内涵的重要性均匀平等、 同等重要，而基于这种概念的概念格提取关联规则存在着明显的不足：由于建格 时没有考虑到属性和属性集的重要性的差别，形成包含所有属性对的概念格的结 点，因此建格时间长、效率低。 1 2 3 存在的问题和主要研究的内容 根据以上分析，不管是传统的关联规则挖掘算法，还是引入概念格的关联规 则挖掘算法，它们都有这样一些缺点，现归纳如下： 第6 页河南大学研究生硕士学位论文 1 ) 要多次扫描数据库，算法效率低。 2 ) 在关联规则挖掘过程中产生的侯选项集数量巨大。 3 ) 与用户的交互性差。 针对以上问题，本文提出了基于区别度概念格的关联规则挖掘方法，有效的 解决了这些问题。本文主要研究内容有： 1 ) 针对要多次扫描数据库的问题，本文给出了一个新的算法，该算法在构造 概念格的过程中不在是每一个概念的的插入都扫描数据库，而是根据区别度的大 小有条件的扫描数据库，这就减少了数据库扫描的次数，从而减少了生成概念格 的时间。 2 ) 关于第二个问题，本文提出一个新的概念内涵区别度，基于内涵区别 度来建造概念格将有力的减少格中的频繁项集，主要原因是区别度低的内涵将不 参与格的构造，这在一定的程度上缓和了组合爆炸的问题，使关联规则的提取的 难度系数也有所降低。 3 ) 本文给出了一个基于概念格的关联规则提取的改进算法。在改进算法中， 我们使用了置信度度量对关联规则进行剪枝的策略，减少了关联规则提取时置信 度计算的时间，从而进一步提高了关联规则提取的效率。 4 ) 将本文提出的改进算法应用了基于区别度概念格的关联规则提取中，并给 出了相应的提取的算法。 1 3 论文结构 本文的主要研究内容是基于区别度概念格的关联规则挖掘，它给出了区别度 概念格上关联规则挖掘的全过程，首先是给出一个新的概念内涵区别度；然 后提出了区别度概念格的构造算法；最后改进了基于概念格的关联规则提取算法， 并将其应用于区别度概念格的关联规则提取中。基于区别度概念格的关联规则挖 掘方法有效的减少了扫描数据库的次数，提高了关联规则挖掘的效率。同时在实 验部分，除了常规实验本文还增加了用户交互界面，实验不仅证明该算法的有效 性、正确性，而且方便了用户查询，提高了算法的交互性。本文内容组织如下： 河南大学研究生硕士学位论文第7 页 第一章介绍了基于区别度概念格的关联规则挖掘的背景及研究意义，并分析 了在数据挖掘领域引入概念格原因，指出了本文研究的主要内容。 第二章介绍了基于区别度概念格挖掘关联规则的理论基础，包括关联规则基 本概念、概念格的基本概念，基于概念格的关联规则的挖掘过程，关联规则的常 用挖掘算法分析，关联规则价值衡量的方法等内容，为第三章区别度概念格的构 造奠定了理论基础。 第三章介绍了基于区别度概念格的频繁项目集的提取。给出了区别度概念格 的构造过程，区别度概念格的构造算法，并用理论分析的方法证明了区别度概念 格构造算法的优越性。 第四章给出了一个基于概念格的关联规则提取的改进算法。在改进算法中， 我们使用了置信度度量对关联规则进行剪枝的策略，减少了关联规则提取时置信 度计算的时间，从而有效的提高了关联规则提取的效率。 第五章通过实验验证了基于区别度概念格的关联规则挖掘算法是有效的、正 确的，除传统的实验证明外，本文在实验中加入了用户交互界面，这也在一定程 度上增加了算法的交互性。 第六章是全文的总结，对本文的主要研究工作进行简要的阐述，并探讨和展 望了在未来时间内继续研究及应当完善的问题。 第8 页河南大学研究生硕士学位论文 2 1 引言 第2 章关联规则挖掘研究 关联规则挖掘是知识发现领域的一个重要课题，它主要是从大量的数据中挖 掘出有价值的用于描述数据项之间相互联系的知识。自1 9 9 3 年a g r a w a l 等人提出 关联规则挖掘技术以来，人们对关联规则的挖掘研究逐渐深入广泛，尤其是把概 念格应用于关联规则之后，使得关联规则的挖掘技术更上一个台阶。许多商业企 业在日复一日的运营中积累了大量的数据，并且迫切需要将这些数据转换成有用 的信息和知识，因此把数据操作从低层次的查询统计操作，提高到为人事部门或 经营决策者提供决策辅助支持的层面上来显得势在必行。然而，要想应用基于区 别度概念格的关联规则挖掘技术，必须先了解概念格的基本概念及关联规则挖掘 的原理和方法，所以了解概念格和关联规则相关概念是我们下一步工作的基础。 2 2 基本概念 令i = i l , 2 ，i 3 ，) 是刀个不同项目的集合( i t e ms e t ) 。在一个事务数据库 d = 瓴，t ：，t 3 ，f 。) 中，每个事务r 都用唯一的加来标识。一个项目集合p ，p 是 由，中的一些项集组成，如果尸r ，我们说r 包含p 。记作t ( p ) 。 例如：i = a ，b ，c ，d ，e ，f ) ，表2 一l 是一个事务数据库的例子。 河南大学研究生硕士学位论文第9 页 表2 - 1 一个事务数据库d 定义2 1 项目集合尸的事务占总事务的百分比叫作尸的支持度，用s ( p ) 来表 示。 s ( p ) 爿z ( d l id i( 2 - 1 ) 其中i d i 是数据集d 的事务数，给定一个最小支持度阈值汐，如果s ( p ) 缈，我 们就说项目集合尸是频繁模式( 或频繁项集) 【1 】，否则称尸为非频繁模式( 或小项 目集) 。 定理2 1 设置，b 是数据集d 中的项目集： 1 ) 若丑最，贝0 s ( p 1 ) s ( p 2 ) 。 2 ) 若丑b ，如果只是非频集，则最也是非频集。 3 ) 若置b ，若b 是频集，则只也是频集。 由上述定义可知，定理2 一l 成立是显然的( 证明略) 。 定义2 2 数据挖掘背景k = ( g ，m ，) 是一个三元组，其中g 是对象的集合，膨 是属性的集合，是g 与膨之间的二元关系，( g ，m ) ei 表示对象g 具有属性m 。 关系，也称为是背景关联的关系。另外我们还用m 来表示【4 | j ( g ，枘，。 一个小的背景可以用一个矩形的表来表示，每一行是一个对象，每一列是一个属 性。u 行m 列的交叉处用0 或1 表示，1 表示对象蹦有属性朋，o 表示对象“没有 属性m 第10 页河南大学研究生硕士学位论文 表2 2 与表2 - 1 相对应的形式背景 abcdef 定义2 3 设彳是对象g 的一个子集，我们定义f ( a ) ：= m miv g a ，g i m ( a 中对象共同属性的集合) 。相应地设b 是属性集合m 的一个子集，我们定义 g ( b ) = g giv m b ，g l m ) ( 具有口中所有属性的对象的集合) 。 定义2 4 背景k = ( g ，m ，d 上的一个形式概念( f o r m a lc o n c e p t ) 是二元组 c = ( 彳，口) ，其中彳互g ，b c _ m ，而且满足f ( a ) = b ，g ( b ) = 彳。我们称彳是概念c 的外延，本文用e x t e n t ( c ) 表示的外延c ；b 是概念c 的内涵，本文用i n t e n t ( c ) 表 示c 的内涵。用s ( k ) 表示背景k 上的所有概念的集合。 性质1 如果k = ( g ，m ，i ) 是一个形式背景，4 、4 g 是对象的集合， 且、岛m 是属性的集合，则； ( 1 ) 4s 4j 厂( 4 ) 互f ( a t ) ； ( 2 ) 马岛g ( 岛) g ( 垦) 。 证明： ( 1 ) 若小( 4 ) ，则v g e 4 都蔫j g i m 。但4 以，所以v g 4 ，也有g i m 。 所以m f ( a 。) ，所以厂( 4 ) s 厂( 4 ) 。 ( 2 ) 同理可证。 定义2 5 对于给定的形式背景k = ( g ，m ，d ，若概念q - ( 4 ，蜀) 和 g - - ( a ，岛) ，满足4s4 ，或岛蜀，则称0 。，b 。) 为子概念( 或亚概念) ，心，岛) 为父概念( 或超概念) ，记为：( 4 ，蜀) “，岛) 。若不存在c 3 = “，岛) ，满足 “，j 9 i ) 似，骂) “，垦) ，则称0 ，b 。) 为直接子概念，易) 为直接父概念。这种由 o 1 l l l 1 o 0 l o l l l 1 o o 0 1 o o 0 l o l l l l 1 1 l 2 3 4 5 河南大学研究生硕士学位论文第11 页 形式背景中所有形式概念的超概念一亚概念的偏序关系( 也称泛化一特化关系) 所形成的格称为概念格( c o n c e p tl a t t i c e ) 1 6 1 ，记为l ( k ) 。 定义2 - 6 闭项集( c l o s e di t e r n s e t ) 项集x 是闭的，如果它的直接超集都不具 有和它相同的支持度计数 频繁闭项集是支持度大于或等于最小支持度阈值的闭项集。 2 3 关联规则的挖掘过程 对于一个给定的事务数据库d ，一般先由用户指定最小支持度缈和最小可信度 ( m i n c o n t ) ，然后根据给定的阂值找出有意义的关联规则，这个过程就叫做关 联规则挖掘过程。一般地，关联规则挖掘包括两个阶段： 1 ) 找出频繁项目集 通过用户给定的驴，找出所有支持度不小于矽的项目集，这些项目集就是频 繁项集( f r e q u e n ti t e m s e t ) 。事实上，有些频繁项集之间存在包含关系，而概念格可 以很好的表达项集之间的这种内在关系，并且频繁项集和概念格的内涵之间有一 种一一对应的关系，基于以上优势利用概念格来挖掘关联规则就显得水到渠成。 2 ) 产生关联规则 根据用户给定的m i n c o n y ，在每个频繁项目集中，寻找置信度不小于 m i n c o n y 的关联规则。本文从概念格上提取关联规则可以更容易实现对关联规则 的可视化，增加系统的交互性同时也方便用户寻找感兴趣的规则。 对于关联规则挖掘的两个阶段，第一个阶段就是快速高效地找出所有的频繁 项集，频繁项集的挖掘是关联规则挖掘的核心问题，也是衡量关联规则挖掘算法 的重要标准；第二个阶段可以根据用户给定的r a i n c 0 矿和概念格本身的蕴含关系 较容易、直接的的提取关联规则，关联规则挖掘的基本模型l l 如图2 1 ： 第12 页河南大学研究生硕士学位论文 图中a l g r i t h m - l 算法用于挖掘频繁项目集，a l g r i t h m - 2 算法用于求取关联规则， 缈表示最小支持度，m i n _ c o n f 表示最小可信度。 2 4 关联规则挖掘的算法分析 从1 9 9 4 年a g r a w a l 等人提出挖掘频繁项目集的a p r i o r i 算法以来，国内外专家学 者针对数据量、属性量不同的关系型数据库提出了多种关联规则挖掘算法，有的 以减少访问数据库次数和占用内存空间为目的对先验算法进行了改进，有的采用 了不同于a p r i o r i 算法的数据存储技术和搜索方法进行数据挖掘。本节阐述了常见 且与本文相关的一些关联规则挖掘算法的基本思想，并对每种算法性能的优略进 行了比较分析。 2 4 1 经典先验算法 先验算法即a p r i o r i 算法是关联规则挖掘算法中最经典的一个算法，该算法将 挖掘关联规则的理论第一次应用到现实世界中，并且很多专家以减少访问数据库 次数和占用内存空间为目的对先验算法进行了改进。 先验算法的两个基本性质： 1 ) 任何频繁概念的超概念都是频繁的； 2 ) 任何非频繁概念的子概念都是非频繁的。 先验算法是基于先验知识，使用一个逐层搜索的迭代方法进行频繁项目集的 挖掘，主要思想是利用k 一项集来产生( k + 1 ) 一项集。具体的过程如下：首先第一次 扫描找出所有的频繁卜项集，记为l l ；然后利用l i 来产生频繁2 一项集即l 2 ；如此不 河南大学研究生硕士学位论文第13 页 断地循环直至找不到频繁k 一项集为止。先验算法产生频繁项目集的算法如下所示： 算法2 1 先验算法的频繁项目集生成 l ：k = l 2 ：最= fii ， 盯( f ) ) n xm i n s u p ) 发现所有的一项集) 3 ：r e p e a t 4 ：k = k + l 5 ： q = a p r i o r i - g e n ( f k 1 ) 产生候选项集) 6 ：f o r 每个事务t t d o 7 ： c = s u b s e t ( c k ，t ) 识别属于t 的所有选项， 8 ：f o r 每个候选项目集c e d 0 9 ： a ( c ) = o r ( c ) + 1 支持度计数增值) 1 0 ：e n d f o r 1 1 ：e n df o r 1 2 ： e = c 1c g o r ( c ) n x m i n s u p ) 提取频繁k 一项集) 1 3 ：u n t i l 疋= ! ! ! 壁兰些丝三! ! ； 一 a p r i o r i 算法的缺点：在数据规模较大或属性个数较多的情况下，a p r i o r i 算法会 产生大量的候选项集；另外，要多次扫描数据库，因为每一次候选项目集的产生 都要扫描一遍数据库d ，通常数据库的数据量都是庞大的，所以这就在无形之中增 加了算法的额外开销，降低算法的效率。 针对a p r i o r i 算法中存在的一些问题，一些专家为了提高a p r i o r i 算法的效率，主 要采用以下一些技术：基于散列技术、基于事务压缩方法、基于划分方法、基于 采样方法、动态项集计数等等，但是这些技术的应用对先验算法效率的提高是有 限的，它的一些固有的缺点仍然取法克服。 2 4 2f p g r o w t h 算法 无论是先验算法，还是先验算法的改进算法，都无法克服它固有的多次扫描 数据库的缺陷，即使是在某些方面进行了优化，其效率也仍然不能令人满意。为 第14 页河南大学研究生硕士学位论文 了克服类先验算法多次扫描数据库的缺点，h a nj i a w e i 等人【】于2 0 0 0 年首先提出了 将频繁项目集压缩到频繁模式树，然后根据频繁模式树发现频繁项目集的方法， 即我们经常提到的f p 树算法。 f p 树算法是一种输入数据的压缩表示，它通过逐个读入事务，并把每个事务 映射到f p 树中的一条路径来构造。该算法仅需要扫描数据库两次就可以把所有的 频繁项目集压缩至i j f p 树中，并通过递归调用的方法来产生频繁项目集，不需要产 生庞大的候选项目集，这在一定程度上也克服了数据组合爆炸的问题，同时也减 少了扫描数据库的次数，提高了频繁项目集挖掘的效率。其具体算法如下所示： 算法2 2f p 树算法的频繁项目集生成 输入：事务数据库d ，支持度阈值伊 输出：相应的f p 树 算法流程 1 ：第一次扫描数据库d ，得到所有的频繁一项集的集合f 和每个频 繁项的支持度，并把f 按支持度递减的顺序进行排序，结果记为 l ： 2 ：算法第二次扫描数据库，创建f p 树。首先创建根节点，记为n u l l ， 然后对d 中的每个事务t ，根据l 中的顺序选出并排序t 中的事务 项； 3 ：递归调用插入函数将所有的事务插入f p 树中，不同的事务可以共 享相同的前缀。 f p 树算法利用扩展前缀树( 数据结构) 存储经过压缩的频繁项集关键信息， 然后，在f p - t r 中通过递归调用f p g r o w t h 方法来直接产生频繁项目集，不需要生 成频繁候选项集，且只需扫描数据库两次。虽然减少了扫描数据库的次数，并且 不再生成候选项目集，但是f p 树算法也有缺点，一是需要构造数量巨大的条件f p 树，费时且占用空间大；二是采用递归算法本身效率较低。 2 4 3 基于概念格的关联规则挖掘算法 概念格是r w i l l e 于1 9 8 2 年首先提出来的，它利用概念外延和内涵的关系来 河南大学