（应用数学专业论文）基于粒计算与完全图的关联规则算法研究.pdf

河南大学研究生硕士学位论文第1 页 摘要 数据挖掘作为一门新兴的交叉学科，其主要任务是面对庞大的应用数据库， 研究并探索有效的信息提取方法，从海量信息库中提炼隐藏的有用信息。 本文在分析传统关联规则算法的基础上，发现大多算法产生频繁项集时需要 先产生候选项集，并且需要多次遍历整个数据库进行模式匹配。为了提高算法的 运行效率，本文利用粒计算计算代价小的特点，用粒计算代替传统的模式匹配； 同时，为了避免对整个数据库进行扫描，提出利用完全图划分挖掘区域的方法， 只在可能产生频繁项集的范围内进行挖掘。 主要研究内容如下： 1 、g r c _ g 算法。总结学习他人经验，对粒计算理论进行分析，把粒计算引入 到关联规则挖掘中，提出了二进制粒和完全组合粒的概念；提出一种利用完全图 缩减挖掘区域的方法。最后，给出该算法，并通过仿真实验证明了该算法具有较 好的性能。 2 、t g r c g 算法。分析常见的实际数据库中记录信息的多种属性特征可知， 其中所蕴含的某些属性间的关联规则往往是遵循一定的规律成对共存，然而进行 简单的频繁项集挖掘不能有效地发现这些规则。因此对g r c - g 算法进行改进，并 提出了挖掘双向关联规则的算法t g r c - g 。建立强双向关联规则和强弱双向关联规 则的概念；为减少冗余规则的产生，提出一种删除冗余规则的方法。给出该算法， 并通过仿真实验证明该算法能够有效地减少冗余规则的产生，并且能够发现也许 会更有意义的强弱双向关联规则。 3 、佃一g r t g 算法。g r c - g 算法虽然有效，然而在很多情况下，人们感兴趣的 知识往往出现在多维空间中。为此，以g r c g 为基础提出该多维关联规则挖掘算 法，通过事务投影的方法挖掘多维频繁项集，并在此基础上进行关联规则的产生。 给出该算法，并通过仿真实验证明了该算法能够有效地发现多维关联规则，并且 时间效率较高。 4 、为了更好的证明本文所提出的改进算法的有效性和实用价值，本文在实验 室仿真测试算法性能的同时，选择中医药方剂数据库进行实际挖掘实验。实验结 第l l 页；, - i 南大学研究生硕士学位论文 果表明本文的改进算法确实能够有效地发现实际应用中的有趣关联规则。目前， 中医药领域尚未有引入数据挖掘理论进行研究的完善而成熟的先例。 关键词：粒计算：完全图；关联规则；频繁项集 a bs t r a c t a sa ne m e r g i n gi n t e r d i s c i p l i n e ，t h em a i nt a s ko fd a t am i n i n gi s t or e s e a r c ha l l d e x p l o r ee 行e c t i v em e t h o d so fi n f o r m a t i o n e x t r a c t i o na n de x t r a c tu s e f u l i n f o r m a t i o n h i d d e nf r o mh u g ed a t a b a s e s b a s e do nt h ea n a l y s i so ft h et r a d i t i o n a la s s o c i a t i o nr u l ea l g o r i t h m s ，i ti sf o u n dt h a t m o s to ft h e mg e n e r a t i n gf r e q u e n ti t e m s e t sf r o mc a n d i d a t ei t e m s e t sa n dh a v i n gp a t t e i t i m a t c h i n gt h r o u g hs c a n n i n gt h ee n t i r ed a t a b a s em o r e t h a no n e i no r d e rt ol m p r o v et h e e f f i c i e n c yo fa l g o r i t h m s ，t h i sp a p e rr e p l a c e st h et r a d i t i o n a lp a t t e r nm a t c h i n g t og 瑚u l a r c o m p u t i n g ( g r c ) b e c a u s eo ft h ec h a r a c t e r i s t i c s o fi t sl o wc o s t a tt h es a m et i m e ，m o r d e rt oa v o i dm u l t i p a s ss c a n n i n gt h ee n t i r ed a t a b a s e ，t h ec o m p l e t eg r a p h 1 su s e dt o d i v i d em i n i n gr e g i o na n dm i n i n gf r e q u e n ti t e m s e t so n l yi np o s s i b l es c o p e t h em a i nr e s e a r c hi nt h i sp a p e rt a i lb ec l a s s e da sf o l l o w s ： 1 g r cga l g o r i t h m ( a l g o r i t h mb a s e do ng r c a n dc o m p l e t eg r a p h ) a tt h eb a s eo t l e 踟i n gf r o mo t h e r s ，a n a l y s i st h et h e o r yo fg r c ，a n da p p l yt h ei d e at oa s s o c i a t i o nr u l e s m i n i n g p u tf o r w a r dt w on e wc o n c e p t s ：b i n a r yg r a n u l ea n dc o m p l e t ec o m b i n a t i o n o f b i n a r yg r a n u l e a n dam e t h o do f r e d u c em i n i n gs p a c eb a s e do nc o m p l e t eg r a p hl sb n n g f o r w a r d a tl a s t ，g i v et h ea l g o r i t h ma n dt h es i m u l a t i o nt e s t ss h o wt h a tt h i sa l g o r i t h mh a s b e t t e rp e r f o r m a n c e s 2 t g r c ga l g o r i t h m ( a l g o r i t h mf o rm i n i n g t w o w a ya s s o c i a t i o nr u l e sb a s e do n g r cg ) a n a l y s i st h ev a r yc h a r a c t e r i s t i c so fa t t r i b u t e s i nc o m m o n l ya c t u a ld a t a b a 8 e ， w ec a i ls e e , s o m eo fw h i c hc o n t a i n st h er e l a t i o n s h i pb e t w e e na t t r i b u t e s o f t e nf o l l o w c e r t a i nr u l e so fc o e x i s ti np a i r s ，b u ts i m p l y e f f e c t i v er u l e s t h e r e f o r ei m p r o v eg r c g f r e q u e n ti t e m s e t sm i n i n gc a r ln o tf i n dt h e s e a l g o r i t h ma n dp r o p o s eam i n i n ga l g o r i t h m f o r 铆o w a ya s s o c i a t i o nm l e 卜t g r c ga l g o r i t h m b u i l dt h ec o n c e p t so fs t r o n g t w o w a ya s s o c i a t i o nr u l e sa n ds t r o n g - w e a ka s s o c i a t i o nr u l e s a n di no r d e r t or e d u c et h e r e d u n d a n tr u l e sg e n e r a t e d ，am e t h o dt od e l e t er e d u n d a n tr u l e s i sp u tf o r w a r d t h e a l g o r i t h mi sg i v e na n ds i m u l a t i o nt e s t ss h o wt h a tt h ea l g o r i t h mc a l l e f f e c t i v e l yr e d u c e 第1 v 页河南大学研究生硕士学位论文 t h er e d u n d a n tr u l e sg e n e r a t e d ，a n dc a nf i n dm a y b em o r em e a n i n g f u ls 仃o n g 。w e a k t w o - w a y a s s o c i a t i o nr u l e s 3 m d g r c g a l g o r i t h m ( g r c _ ga l g o r i t h mi nm u l t i d i m e n s i o n a ls p a c e ) g r c g a l g o r i t h mm a yb ee f f e c t i v ei nm a n yc a s e s h o w e v e r , i nm a n ys i t u a t i o n s ，p e o p l ea r e i n t e r e s t e di nk n o w l e d g ei nt h em u l t i d i m e n s i o n a ls p a c e f o rt h i sp u tf o r w a r dt h i s a l g o r i t h mf o rm i n i n gm u l t i d i m e n s i o n a la s s o c i a t i o nr u l e sb a s e do n g r c g i tc a nm i n e m u l t i d i m e n s i o n a lf r e q u e n ti t e ms e t st h r o u g hp r o j e c t i o na n dt h e ns e l e c t et h ea s s o c i a t i o n r u l e s g i v et h ea l g o r i t h m ，a n dt h es i m u l a t i o nr e s u l t ss h o wt h a tt h ea l g o r i t h m c a n e f f e c t i v e l yd i s c o v e rm u l t i d i m e n s i o n a la s s o c i a t i o nr u l e sa n dh a sh i g h e rt i m ee f f i c i e n c y 4 i no r d e rt ob e t t e rp r o v et h a tt h ei m p r o v e da l g o r i t h m sp r o p o s e di nt h i sp a p e rh a v e e f f e c t i v e n e s sa n dv a l u e ，a tt h es a m et i m eo ft e s tb yl a b o r a t o r ys i m u l a t i o n ，h a v ea na c t u a l m i n i n gt e s t i nt h ed a t a b a s eo ft r a d i t i o n a lc h i n e s em e d i c i n e ( t c m ) p r e s c r i p t i o n t h e r e s u l t so ft e s ts h o wt h a tt h ei m p r o v e da l g o r i t h m sa r ei n d e e da b l et oe f f e c t i v e l yf i n d i n t e r e s t i n ga s s o c i a t i o nr u l e si nt h ep r a c t i c a la p p l i c zi i o n a tp r e s e n t ，t h ef i e l do ft c m h a sn o tt h ep e r f e c ta n dm a t u r ep r e c e d e n to fr e s e a r c hb yi n t r o d u c i n gt h et h e o r yo fd a t a m i n i n gi n k e y w o r d s ：g r a n u l a rc o m p u t i n g ；c o m p l e t eg r a p h ；a s s o c i a t i o nr u l e s ；f r e q u e n t i t e m s e t s 关子学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学侄申请。本人郑重声明：所呈交的学位论文是 本八在导师的指导下独立完成的，对所研充酌课题有新的见解。据我所知，除 文中特别加以说明、标注和致谢的地方外，论灭中不包括其他人已经发表或j 笋 写过的研充成栗，也不包括其他人为获得任何教育科研机构的学位或证书而 使用过的材料。与我一同工作的同事对奉研究所做的任何贡献均已在论文中作 了明确的说明并表示了谢意。 学住肆请人( 孝位论又作者) 釜名： 2 。o r 7 卑6 月 曰 关于学位论文著作权佳用授板书 本人经河南大学审核批准捩子硕士学，互主。作为学位论欠的作者，本人完全 了解并同意河南大学有关保留、使用学谊论文1 酌要求，即河南大学有权向圉謇 图书馑科研信息机构、数据收集丰凡桐乖丰板图书馆等提供学位论文( 纸质文 不和屯于又太) 以供公众检索、查阅。本人授权河南大拿出于宣扬展览李校 学术发展和进行学术交流等目韵。可以采取影印、缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 纸质支本和电子文表) 。 ( 涉及保右肉容的学伍论文左解卺后适用本授权书) 学位获得者( 学位论文作者) 签名：蠢 2 00 掌1 主论夏耗导教师釜名： 矽矽7 垆多月 河南大学研究生硕士学位论文第】页 第1 章绪论 随着科学技术和信息技术的广泛使用，产生了海量数据。这些巨量的数据使 得人们不知所措，从这些数据中挖掘重要的、有价值的信息就变得越来越迫切。 正是在这样的背景下，数据挖掘( d a t am i n i n g ) 技术应运而生。数据挖掘技术是 一个新兴的研究方向，涉及统计分析、数据可视化、人工智能、机器学习和 数据库技术等众多领域，并在商业、金融、生物学、医学、电信等各个行业 进行了应用。关联规则是数据挖掘中的一项重要技术，用于挖掘大量数据中项 目集之间有趣的关联，然而基本的算法在多种复杂的实际的应用中往往显得不尽 完善。 1 1 课题的研究现状及存在的问题 自从l9 9 3 年a g r a w a l 等人首先提出了关联规则问题之后，众多的数据挖 掘研究人员就开始对关联规则的挖掘问题进行了大量和深入地研究，使得数 据挖掘技术走进越来越多的领域，具有普遍意义和实际意义。关联规则能够 发现数据间隐藏的有用信息，并且形式简洁、易于解释和理解，因此从大型 数据库中挖掘关联规则的问题已经成为近年来数据挖掘研究领域中的一个热 点问题。而且关联规则挖掘可以发现用传统的人工智能和统计方法所无法发 现的规律，因而关联规则挖掘具有重要的研究价值。 1 1 1 国内外研究现状 美国i b ma l m a d e nr e s e a r c hc e n t e r 的a g r a w a l r 等人最早开展关联规 则挖掘研究，并在19 9 3 年提出了a i s 算法，1 9 9 4 年提出了挖掘关联规则的 经典算法a p r i o r i 及其改进算法a p r i o r i t i d 。之后，又有大量的数据挖掘研 究人员对关联规则问题进行了大量地研究，并提出了许多基于a p r i o r i 算法 的改进算法，例如，杂凑方法、采用划分技术、随机采样、动态项集计数技 术等，这些算法虽然在一定程度上能够提高算法挖掘规则的效率，但它们都 第2 页河南大学研究生硕士学位论文 无法避免a p r i 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 算法但3 。该算法采用自下而上的搜索策略，并对项集进行排序。为了把无用 的候选项集尽早剪枝，m a x m i n e r 算法提出了一种能够有效地缩小算法搜索 空间的“向前看”的剪枝策略。另外，为了增加超集剪枝的效果，m a x m i n e r 算法采用了一种肩发式重新排序的技术。但是，如果数据库格式是水平的， 或者搜索策略是采用宽度优先的方式，则可能需要多遍扫描数据库，并且会 有许多无用的候选项集产生，并有效降低算法的效率。 l i n 和k e d e m 提出了一种能够大大减少扫描数据库次数的双向钳形搜索 p i n c e r - s e a r c h 算法1 。该算法利用自下而上搜索产生的非频繁项集来约束和 修剪自上而下方向的最大候选频繁项集。但是，由于它的候选k 一项集c 。的生 成方法和a p r i o r i 算法的方法有点类似，当数据量非常大时，将不可避免地 产生“组合爆炸”问题，而且按照该生成算法执行可能会有某些频繁项集遗 漏。为了生成遗漏的频繁项集，就需要一个专门用于“恢复”的程序，从而 这就增加了额外的计算量。另外，该算法需要维护最大候选集即最大频繁模 式的超集，这也要付出很高的代价。 j i a w e ih a n 等人在2 0 0 0 年提出一种f p 一增长算法h 1 。该算法不产生候选 项集，把频繁项集关键信息利用扩展前缀树这种数据结构进行压缩存储。该 算法虽然不需要生成频繁候选项集，并且只需要扫描两次数据库；但是在某 些情况下，算法的效率仍然不是很高：一方面，当长型项集的数量很多，并 且如果在由原始数据库构造f p - 树时，发现树的分支很多且很长，为了构造 出数量巨大的条件f p - 树，就需要浪费大量的时间和空间；另一方面，算法 本身是递归实现的，因而效率也较低。 由于最大频繁项集包含了它所有的频繁项集，利用最大频繁项集能够发 现所有可能的规则，所以有很多人提出了一些算法以直接挖掘最大频繁项集。 g u n o p u l o s 等人提出了随机算法，该算法的优点是事务数据库是采用垂直位 向量的数据结构来表示的，缺点是它无法保证发现所有的最大频繁项集。 b u r d i c k 等人为了挖掘最大频繁项集，提出了m a f i a 算法，该算法存在一个 缺点就是仍需要对数据库进行多遍扫描。d h p 算法的优点有两点，一是为了 河南大学研究生硕士学位论文第3 页 减少2 一项集的产生，采用了杂凑方法；二是为了修剪事务数据库而使用了剪 枝技术；缺点是，构造哈希表所需要的开销较大，而且为了剪裁数据库，确 定哪些候选项目集在事务中，就需要对数据库进行多遍扫描。随着大型数据 库的开发，要挖掘的数据量越来越大，这就需要研究出时间和空间效率较高 的关联规则挖掘算法。 1 1 2 存在的问题 当前，关联规则技术研究已取得了很大进展，但由于不同数据特点有不 同的挖掘需求，另外由于普通关联规则自身所存在的一些不足，它还存在着 如下一些急需克服的困难： 1 、频繁模式挖掘算法的效率仍待提高。 虽然现在关联规则挖掘的研究经常集中在频繁模式的高效发现上，并且 也出现了大量的改进算法，但是由于频繁模式挖掘在关联规则挖掘中最耗时 间，而且随着数据库容量的增大，重复访问数据库、外存，将导致性能低下。 因此，探索新的理论和算法来减少数据库的扫描次数，提高算法的效率己经 成为近年来关联规则挖掘研究的热点之一。 2 、需要更有效地组织和处理挖掘得到的关联规则怕1 。 由于经过关联规则挖掘，往往会得到大数量级的规则，而用户要找出感 兴趣的关联规则，就只能对这些大数量级的规则进行分析。因此，为了方便 用户从中找到感兴趣的知识，便于分析和决策，就需要考虑如何对挖掘结果 进行有效地组织。 3 、需要研究和开发新型扩展型关联规则模型拍1 。 不同扩展类型的关联规则具有不同的应用范围，在不同数据特点的情况 下，就需要开发不同类型的扩展型关联规则模型，以满足用户的实际需要。 1 2 本文的主要工作 针对现有关联规则技术存在的困难，本文提出的改进算法如下： 1 、为了提高关联规则挖掘的效率，结合粒计算的思想，提出了一种基于 第4 页河南大学研究生硕士学位论文 粒计算与完全图的关联规则挖掘算法g r c g 算法。该算法采用二进制粒，通 过粒计算发现频繁项集，避免了模式的匹配运算；只需扫描一遍数据库，避 免了对数据库的重复扫描；提出了完全组合粒的概念，完全组合粒中任意一 对二进制粒都是频繁2 一项集，基于频繁项集不可能分布在多个不同的完全组 合粒中，即频繁项集只可能出现在同一个完全组合粒中的思想，对运算范围 进行了划分，使得挖掘频繁项集的操作只在可能形成频繁项集的集合中进行； 在一个完全组合粒中挖掘频繁项集时，若粒中元素个数为3 ，只需进行一次 “与 运算就可以了，若超过3 ，采用深度优先的方式，反复进行“与”运 算，就可以发现频繁项集，并且不用产生候选项集，不需要连接步，因而能 大大提高运算效率。 2 、分析常见的实际问题数据库中记录信息的多种属性特征可知，其中所蕴含 的某些属性间的关联规则往往是遵循一定的规律成对共存，然而进行简单的频繁 项集挖掘不能有效地发现这些规则。针对这种情况，对g r c g 算法进行进一步改 进，给出一种挖掘双向关联规则算法t g r c - g ，该算法中除了提出强双向关联规则 外，还提出强弱双向关联规则。另外，该算法将互为前件、后件的单向关联规则 合为一条双向规则，这使得挖掘结果得到了更好的组织。 3 、现存的多维关联规则挖掘算法往往假定对象属性具有单值性，考虑到在 实际应用过程中所面对的客观庞大信息库，每一维上通常都有多个值，因而在 g r cg 算法的基础上，提出一种适合挖掘每维上具有多值的数据库中的多维关联规 则挖掘算法肋一g r c g 。该算法利用g r c g 算法在a ，维上挖掘出频繁项集，然后利 用二进制粒对数据库进行投影，挖掘出投影数据库中a ：维上的频繁项集，随后进 行项集的合并，反复此过程，直至挖掘出k 维频繁项集。 1 3 引入算法价值评估的意义 算法研究中采用模拟数据进行性能评估只能够在一定意义上说明算法的可行 性和理论特性，完全不能确定和判断其运用于实际的使用效果、实际性能、实际 意义和价值。原因之一，实验室模拟数据大都带有随机性和研究人员自身的主观 倾向性，与实际问题中数据的属性本质和实际数据的分布规律往往大相径庭，所 以实验室模拟数据评估得到的算法的性能特征和算法在实际问题的运用中所反映 河南大学研究生硕士学位论文第5 页 出的特征往往差别很大；原因之二，众所周知，数据挖掘算法的构造本源出发点 是试图在海量数据库中挖掘其潜在而有用的隐藏信息旧7 1 ，但是其构思理论依据往 往不一定正确而充分，即使依据先前成熟的数据挖掘理论基础，但结合应用问题 的特点所作出的算法变换不一定是j f 确的，进而再用其不确定的实验室模拟数据 进行性能评估所得到的评估结果，就更谈不上其可信度和应用有效性。 综上所述，本文在对所研究算法进行实验室仿真、常规性能评估的基础上选 择一个新的应用领域进行实际性能的价值评估，在从理论上给出算法的性能评估 同时用客观事实论证了算法的可用性和使用价值，是一种值得探讨和尝试的研究 方法。与此同时，也为这种所选评估实验的应用领域本身提供一种研究路径，意 义深远。 考虑到目前大多数应用领域都已经运用了数据挖掘技术，但是中医药领域尚 未成功引入数据挖掘技术进行系统研究。所以本文选用该领域中的中医药方剂数 据库做为数据源对算法进行性能评估。 1 4 本文组织结构 正文共分为六章，各章节内容安排如下： 第l 章，论述课题的相关理论研究现状和存在问题，介绍本文的主要工作、 研究意义以及论文组织结构。 第2 章，为构造高性能的挖掘算法，初步研究关联规则算法中的一些基本定 义、关联规则的挖掘步骤以及常用的一些关联规则算法，并对关联规则算法的研 究和发展方向进行分析。 第3 章，研究粒计算的相关概念、词计算理论、r o u 曲集理论、粒化模型等； 提出基于完全图的划分挖掘区域的方法；介绍g r c - g 算法中的基本定义和性质， 并对算法思想进行描述，提供一个应用实例，最后将该算法与其他算法进行性能 比较。 第4 章，考虑到g r c g 算法只能挖掘传统的单向关联规则，对其进行改进以 挖掘双向关联规则，并提出t g r c - g 算法。建立强双向关联规则和强弱双向关联 规则的概念；为减少冗余规则的产生，提出一种删除冗余规则的方法。 第5 章，分析多维关联规则的本质，给出如一g r c _ g 算法。g r cg 算法虽然有 第6 页河南大学研究生硕士学位论文 效，然而在很多情况下，人们感兴趣的知识出现在多维空间中，为此，以g r c g 为基础提出该允许单维上具有多值的多维关联规则挖掘算法。该算法通过事务投 影的方法挖掘多维频繁项集，在此基础上产生多维关联规则，并通过仿真实验对 算法进行性能测试。 第6 章，采用中医药领域中的方剂数据库作为数据源对算法进行实际性能测 试及价值评估。利用本文提出的改进算法挖掘中医方剂中的药对，以及挖掘药物 和功效间的关联模式，并将研究结果与当前传统研究方法所得到的结果进行对比 分析，阐述本文研究成果的合理性和可信性，阐述这种研究手段和方法的意义、 实用价值以及应用前景。 河南大学研究生硕士学位论文第7 页 第2 章关联规则概述 关联规则反映大量数据中项目集之间有趣的关联。目前，关联规则挖掘是数 据挖掘中最活跃的研究方法之一。本章对关联规则挖掘的基本概念、方法及算法 等进行介绍，为本文研究的中心内容提供基本依据。 2 1 关联规则中的基本定义 定义2 1 令i = f 1 ，之，厶) 是购物篮数据中所有项的集合，而t = 轧f 2 ，t n ) 是所 有事务的集合。每个事务包含的项集都是i 的子集。在关联规则中，包含o 个或多 个项的集合被称为项集。如果一个项集包含k 个项，则称它为k 一项集。空集是指不 包含任何项的项集。 定义2 2 关联规则是形如x _ y 的蕴涵式，其中x 和y 是不相交的项集，即 x n y = g 。 定义2 3 支持度和置信度。支持度表示规则x y 可以用于给定数据集的频繁 程度，而置信度表示y 在包含x 的事务中出现的频繁程度。这两种度量的定义如下： s u p ( x 一：燮半笋型 ( 2 _ 1 ) l c o n f ( x - - y ) = 型圣型兰型! 三! ! ! ( 2 2 ) 7 i t ii x t i , t i t ) i 支持度和置信度是两种重要的度量。因为支持度很低的规则可能只是偶然出 现，从商务的角度来看，低支持度的规则多半也不会令人感兴趣。而置信度度量 通过规则进行推理的可能性。 定义2 4 强关联规则。支持度大于或等于最小支持度阈值m i n _ s u p 匾 时置信度 大于或等于最小置信度阈值r a i n c o n f 的关联规则称为强关联规则。 第8 页河南大学研究生硕士学位论文 2 2 关联规则的种类 将关联规则按不同的情况进行分类汨1 ： l 、根据规则中所处理的数据类型不同，可以分为布尔型关联规则和数值型关 联规则。 如果关联规则处理的数据对象是离散化的，则称之为布尔型关联规则，用于 表示变量之间的关系；如果关联规则处理的数据对象是连续的，则称之为数值型 关联规则。可以将数值型关联规则和多维或多层关联规则结合起来，并对数值型 字段进行进行动态的分割，或者直接对原始的数据进行处理，并且数值型关联规 则中也允许包含离散化的变量。 2 、根据规则中数据的抽象层次不同，可以分为单层和多层关联规则。 在一个抽象层次上挖掘数据产生的关联规则称为单层关联规则；在多个抽象 层次上挖掘数据产生的关联规则称为多层关联规则。例如：l a p t o pc o m p u t e r _ 旧 p r i n t e r ，是单层关联规则；i b ml a p t o pc o m p u t e r - 专h pp r i n t e r ，是一个涉及较 高层次和细节层次之间的多层关联规则。 3 、根据关联规则中涉及到的数据的维数不同，可以分为单维关联规则和多维 关联规则。 如果关联规则只涉及到数据的一个维，则称为单维关联规则；如果关联规则 涉及到两个或多个维的数据，则称为多维关联规则。 例如：人参_ 黄芪，这条规则只涉及到药物的组成，是一个维上的数据，因而 称为单维关联规则；药物= “鸡内金 一功效= “助消化，这条规则就涉及药物 组成和功效两个维上的数据，因而称为多维关联规则。 对关联规则算法进行分类后，在实际的应用中，根据具体问题的不同，就可 以采用某一类合适的关联规则方法进行处理。 2 3 关联规则挖掘步骤 给定一个事务数据库，关联规则挖掘问题就是通过用户指定最小支持度阈值 和最小置信度阈值来寻找强关联规则的过程，大多关联规则挖掘算法是由发现频 繁项目集和生成强规则两部分组成9 1 。具体步骤为： 河南大学研究生硕士学位论文第9 页 1 、找出存在于事务数据库中的所有频繁项目集：先计算候选卜项集，并从中 找出频繁卜项集：根据频繁卜项集，确定候选2 项集，并从中找出频繁2 一项集， 依此类推，直到不再有候选项集产生为止。 2 、用频繁项集根据最小置信度产生所需要的强规则。 相对于第1 个子问题而言，由于第2 个子问题相对简单，而且在内存、i o 以及 算法效率上改进余地不大。因此，第1 个子问题是近年来的研究热点。 2 4 关联规则挖掘算法 a p r i o r i 算法和f p 一树频集算法是关联规则挖掘的经典算法，在此基础上又出 现了大量的优化算法。 2 4 1 a p t io ri 算法 a p r i o r i 算法是第一个关联规则算法。该算法的实现基于先验原理：如果一个 项集是频繁的，则它的所有子集一定也是频繁的。根据先验原理，采取一种基于 支持度的剪枝技术，从而控制候选项集呈指数增长。 a p r i o r i 算法的频繁项集产生有两个重要的特点：第一，它是逐层实现的，即 从频繁卜项集到频繁k 一项集( k 1 ) ，它每次遍历产生项集中的一层；第二，它使 用产生一测试策略来发现频繁项集。在每次迭代过程中，新的候选项集由前一次迭 代发现的频繁项集产生，然后计算每个候选项集的支持度，通过和最小支持度阈 值进行比较，从中找出频繁项集。 1 、a p r i o r i 算法分析 a p r i o r i 算法是a g r a w a l 等人于1 9 9 4 年提出的，算法的基本思想是重复扫描 数据库，首先找出所有的频集，然后由频集产生强关联规则。 其核心程序简要描述如算法2 1 所示： 算法2 1 ： ( 1 ) k = l ； ( 2 ) 发现所有的频繁卜项集l 。； ( 3 ) r e p e a t 第1o 页河南大学研究生硕士学位论文 ( 4 )k = k + l ： ( 5 )由l h 产生候选k 项集c 。； ( 6 )根据支持度阈值从c 。中产生频繁k 一项集； ( 7 ) u n t i ll k = o ； ( 8 ) r e s u l t = l 1ul 2u ul k ； 算法2 1 的主要缺点是算法执行过程可能产生大量的候选集，而且可能需要重 复扫描数据库。 2 、a p r i o r i 算法的性能瓶颈 很显然，算法2 1 有两个致命的性能瓶颈。叫： ( 1 ) 需要多遍扫描事务数据库，这就要付出昂贵的i o 代价。从候选k 一项集c 。 产生频繁k 一项集l 。时，需要对c 。中的每一个元素都扫描一次数据库以判断是否加入 l 。假如有一个频繁项集包含m 个项的话，那么就至少需要扫描事务数据库m 遍。 ( 2 ) 可能会产生庞大的候选集。由频繁k - i 项集l h 产生候选k 一项集c 。时，是呈 指数增长的。产生如此大的候选需要浪费大量的空间和时间。 2 4 2f p - 树频集算法 jh a n 等人提出了一种f p 一树频集算法一副。该算法的特点是采用了一种分而 治之的策略，在经过数据库的第一遍扫描之后，利用频繁模式树对数据库中的频 繁项集进行压缩，并保留其中的关联信息。然后再将f p 树转化成一些和长度为1 的 频集相关的条件库，之后再分别对这些条件库进行挖掘。该算法只需要对数据库 扫描两遍，并且能够避免产生大量候选集。根据实验结果可以发现，该算法针对 不同长度的规则都具有很好的适应性，同时发现该算法的执行效率比a p r i o r i 算法 有较大的提高。 2 4 3 频集算法的优化算法 在算法2 1 的基础上，产生了大量的优化算法，下面介绍几种常见的情况。 1 、杂凑算法 1 9 9 5 年p a r k 等人提出了d 职( d y n a m i ch a s h i n ga n dp r u n i n g ) 算法：1 3 1 引，这是 河南大学研究生硕士学位论文第11 页 一种基于杂凑( h a s h ) 的算法，它能够高效地产生频繁项集。d h p 算法在计算频繁卜 项集时，首先利用杂凑表先估算出2 一项集的支持度，从而减少候选2 一项集的数量。 2 、划分 s a v a s e r e 等人提出了一个基于划分的算法n 副，该算法从逻辑上对数据库进行 划分，并划分成各不相交的块。每次在一个分块内挖掘出局部的频繁项目集，然 后把每个分块内产生的频集进行合并，形成候选的全局频繁项目集，并从中找出 不小于最小支持度阈值的项集，从而形成全局频繁项目集。该算法的优点是：第 一，能够减少i o 负载。因为当数据集很大时，无法一次将全部数据都导入内存， 所以一些算法就只能付出昂贵的i o 代价，而该算法将数据集进行分割，每次只需 将一块数据导入内存就可以了，从而能够在很大程度上减小i o 负载；第二，因为 对数据集进行了分割，产生局部频繁项目集时是在不同的分块内进行的，因此可 以由不同的处理器来完成不同分块内的局部频繁项目集的产生，从而便于进行并 行数据挖掘。 3 、采样 t o i v e n e n 提出了一种基于采样的s a m p l i n g 算法钔。该算法的的核心是从数据 库中随机采集一个子集，并把该子集作为数据挖掘的对象，然后利用数据库中采 样后剩余的部分作为测试用样本，验证在数据子集中得到的关联规则是否准确。 采集样本的大小主要看能不能够一次在内存中完成频繁项集的挖掘。整个算法只 需要扫描数据库一遍，但是由于挖掘的是采样子集的频繁项集而不是整个数据库 中的，这就使得一些全局的频繁项集可能会被漏掉。 4 、动态项集计数 b r i n 等人提出了一种动态项集计数算法n7 1 。该算法根据是否所有子集都是频 繁的进行候选项集的添加。按照特定的大小，把数据库分成若干区间，首先在第 一个区间上计算候选卜项集的支持度，并根据它们产生候选2 一项集，然后在剩余 的区间上继续计算候选2 一项集和候选卜项集的支持度，直到再也没有新的候选项 集产生并且所有候选项集都在整个数据库上计算了支持度时为止。该算法的优点 是减少了数据库的遍历次数，缺点是该算法的性能和效率与数据分布密切相关。 综上，基于a p r i o r i 的频集方法即使进行一些优化，但是a p r i o r i 方法一些固 有的缺陷还是无法克服。 第12 页河南大学研究生硕士学位论文 2 5 关联规则算法的研究方向 根据不同的应用领域有着不同的研究方法和方向，这里介绍几类不同研究方 向的关联规则挖掘算法h 8 j 。 l 、多循环方式的挖掘算法 多循环方式的挖掘算法有a g r a w a l 等人提出的a i s 算法、a p r i o r i 算法、 a p r i o r i t i d 算法，h y b r i dp a r k 等人提出的d h p 算法，s a v a s e r e 等人的提出的 p a r t i t i o n 算法，另外还有t o i v o n e n 提出的抽样算法s a m p l i n g 等等。其中，a p r i o r i 和d h p 算法是最有效和有影响的算法。 2 、增量式更新算法 关联规则的增量式更新算法主要解决两个问题： ( 1 ) 在给定的最小支持度阈值和最小置信度阈值下，当把一个新的事务数据集 添加到旧的事务数据库中时，如何在更新后的数据库中生成关联规则； ( 2 ) 对于给定事务数据库，如果最小支持度阈值和最小可信度阈值发生变化， 如何生成数据库中的关联规则。 针对解决第一类问题的算法有f u p 算法，该算法的基本框架与算法a p r i o r i 相 一致；解决第二类问题的算法有i u a 算法和p i u a 算法。 、 3 、并行发现算法 目前，己经提出的并行挖掘关联规则算法有a g r a w a l 等人提出的c d 、c a d 、d d 算法，p a r k 等人提出的p d m 算法，c h u e n g 等人提出的d m a 和f d m 算法等。 4 、挖掘一般或多层关联规则 在关联规则挖掘的研究过程中，许多学者发现，在一些实际应用中数据有时 比较少，这使得好多项集没有足够的支持度计数，这样，就很难在原始的概念层 次上发现强关联规则。为了挖掘出有趣的关联规则，就只能在较高的概念层次上 进行。通常采用一个非循环图来表示待挖掘数据库中的不同概念层次，并称高层 次的项是低层次项的父亲。根据要挖掘的数据库中的概念层次不同，研究人员提 出了许多高效发现一般或多层关联规则的算法，这些算法主要有h a r t 等人的 m l - t 2 l 1 算法及其变种m l t 1 l a 、m l t m l i 、m l t 2 l a 等。 5 、挖掘多值属性关联规则 河南大学研究生硕士学位论文第13 页 根据所处理的数据对象类型不同，关联规则可分为布尔型关联规则和多值属 性关联规则。多值属性又可分为数量属性和类别属性。目前提出c | 勺挖掘多值属性 关联规则的算法中，大多都是把多值属性关联规则挖掘问题转化为布尔型关联规 则挖掘问题进行的。这些算法首先把多值属性的值划分为多个区间，然后将每个 区间算作一个属性，或将类别属性的每一个类别当作一个属性，之后再采用挖掘 布尔型关联规则的算法进行挖掘。 6 、基于约束的关联规则挖掘 数据挖掘过程可以从给定的数据集中发现数以千计的规则，其中大部分规则 与用户不相关或用户不感兴趣。通常，用户具有很好的判断能力，知道该如何进 行挖掘、该挖掘出什么样的关联规则，这种策略称作基于约束的挖掘 ( c o n s t r a i n t - b a s e dm i n i n g ) 。这些约束包括知识类型约束、数据约束、维层 约束、兴趣度约束和规则约束等等。通常基于约束的关联规则挖掘算法往往能够 发现更有趣的、更实用的和更特别的关联规则。 7 、其它方面 除了以上列举的比较常用的研究方向外，还有其它一些研究方向，如对发现 关联规则的语言的研究、挖掘长模式和密集数据集的研究、挖掘相关性和因果关 系的研究等等。 2 ，6 关联规则的发展方向 随着数据挖掘技术走进越来越多的领域，关联规则的应用也越来越广泛，从 事关联规则挖掘技术研究的人也越来越多。虽然目前国内外对关联规则挖掘算法 的研究己经取得了较大的进步，但是关联规则挖掘技术在有些方面仍然存在着不 足，需要进一步研究和发展。 关联规则的第一个发展方向是要提高关联规则挖掘算法的交互性。目前的许 多算法在进行关联规则挖掘时，一般都需要用户首先规定最小支持度阈值和最小 置信度闽值等参数，然后进行数据集的扫描以发现所有的频繁项目集，并从发现 的频繁项目集中产生关联规则。最后再由用户对挖掘出的关联规则进行审查，如 果用户对所得结果不满意，则需要重新修改最小支持度阈值和最小置信度阈值等 参数，并再次运行关联规则挖掘算法。可能需要重复多次上述过程，直到用户满 第1 4 页河南大学研究生硕士学位论文 意为止，这可能会占用较多时间。因此，如何提高挖掘算法与用户的交互性是一 个值得关注的发展方向。 关联规则的第二个发展方向是提高挖掘算法挖掘效率。随着大规模数据库的