（计算机应用技术专业论文）一种基于关联规则数据挖掘改进算法的研究.pdf

华中科技大学硕士学位论文 摘要 数据挖掘是近年来发展r 分迅速而且非常活跃的研究领域。关联规则挖掘是数据挖 掘中的个重要课题，关联规则挖掘侧重于确定数据中不同属件域之间的联系，找出满 足特定要求的数据属性域之间的相互天系。 针对传统的关联规则挖掘没有考虑与项日相关的数量型数据，将模糊理论和关联划 则挖掘技术相结合，捕述了模糊关联规则的定义和性质，从理论上探讨了模糊关联规则挖 掘过程和多层关联规则挖掘方法，研究了模糊多层关联规则挖掘算法，设计和实现了用 v f p 6 o 产生模糊频繁集的程序，并利用它运行的结果来进行算法举例和分析。模糊多 层关联规则挖掘可以看作是关联规则挖掘的一个扩展，该方法更能反映现实世界事物具 有的模糊特性，能充分表达数据问的各种模糊关系其挖掘结果更容易被用户理解和接 受。 为了更好地提高模糊多层关联规则挖掘的效率，引入了三角模、模糊蕴含算子和蕴 涵度的概念，使用了由t 模计算支持度的公式和由支持度计算蕴涵度的公式。利用蕴涵 度代替置信度的方法，研究了基于蕴涵度的模糊多层关联规则挖掘箅法。在由模糊频繁 项集生成强模糊关联规则时，为了减少模糊候选项集中计算蕴涵度的时日j ，在处理儿余 模糊关联规则的基础上，进一步改进了基于蕴涵度的模糊多层关联规则挖掘算法，理论 和实验结果分析证明算法是正确的和有效的。 关键词：数据挖掘，关联规则，模糊多层关联规则，模糊蕴含算子，蕴涵度 i 华中科技大学硕士学位论丈 a b s t r a c t d a t ai i l i n i n gi sav e r y 盯n v er e s e 甜c bn e l dw h j c bh a sm a d eav e r yr 印j dd e v e i o p m e n ti n r e c e my e a r s a s s o c 商i 叫m l e sm i r l i n gi s0 n eo f 1 ei n o s ti l l l p o r t 蚰tt a s k so fd a t am i n i n g ， w 1 1 i c hp l a c e se x ae m p h a s i so nc o i m m gr e l a t i o n sa 1 1 1 0 n gd i 任毫r e n ta n r i b u t ed o m a i n sa n d n n d i n gt h ei n t e r r e l a n o n sw “hp a n i c u l a rr e q u e s ta m o n gd i 圩b r e n td a t aa n r i b u t ed o m a i 1 1 r a 小“o n a ia s s o c j a l o nr u l e sm j n i n gd dn o tt a k eq u a n 廿诅t i v ed a t ac o r r e l a t e d 埘mi 胁s i n t oc o n s i d e 谢o n ，i nt l l e 恤s i s ，t l l ed e f i n i t i o n s 趾dc b a r a c t e r so ff l l z 苟7a s s o c i a t i o nr l d e sa r e d e s c r i b e d ，c o m b i n m gf h z z yt h e o r yw j t ha s s o c i a d o nm l e sm i n i n gt e c l l i l i q ，t h ep r o c e s so f f 沁z ya s s o c i a t i o nn i l e sm i i n g 趿dt l l em e t h o do fm u h i p l e - l c v e i e da s s o c i a t i o nn l l e sm i n i n g a r ed i s c u s s e di i lt h e o r y ，m ea l g o 一岫o f 血z z ym u l t i p l e l e v e i e da s s o c l a n o r l l l e sm i l l i n gi s s n l d i e d ，t h ep f o g r a n lf o rg e n e r a t i n gf h z z y 丘弓q u e mi t 铷s c t si sd e s i g n e d 锄di l n p l e m e n t e d 谢t l l s u a lf o x p r o6 0 ，晰t 1 1t h eu s eo fm er e s u 】t st h a t 吐l ep r o g r 跚p r o d u c e s ，锄a l g 州m m “锄p l ca n da i l a l y s i s j s g e n f l l z z ymu 1 邮l e 一】e w 】e d 船s o c i 撕o r u l e sm m i n gc 明 c o n s i d e r e d 船锄e x p a n s i o no fa s s o c i 撕o nm l e sm i n i n 晷w h i c h m c hm o f ec a nr e n e c lf u z z y c h a r a c t e r i s t i c st l l a tt h er e a l 吐l i n g sh a v ea n df u l l yc x p r e s sa i lh n d so f 如z z yr c l a t i o n s 锄o n g d i 丘b r e n td a t a ，“sm i n i n gr e s u l t sa r em o r ee a s i l yc o m p r e h e n d e d 卸da c c e p t e d b y t h e c u s t o m e r s i no r d e rt 0j m p r o v et h ee m c i e n c yo ff h z z ym u l t i p l e i “e l e da s s o c i a t i o nm l e sm i n i n g m u c hm o r e ，b ym e a n so f t 一鲫g u l a r 加皿a n d 如z z yi r i l p l i c a t i o no p e r a t o ra n di m p l i c 甜o n d e g r e e ，t h ef o r l l l u l a so fd l es u p p o r td e 芦e ec o m p u t e db yt - n o r ma n dt h ej 唧1 i c a t i o d e g r e e c o m p u t c db yt h es u p p o r td e f e ea r eu s e d u s i n gt l i em d h o do fi m p l i c a t i o nd e g r e ej n s t 髓do r c o n n d e n c ed g r e e ，a 血z z ym m n p l e - l e v c k da s s o c i a t i o nm l e sm i t l i n ga l 酬岫b a 0 n i i i l p l i c a t i o nd e g r e eh a sh e e ns t u ( 1 i e dw b e nt 1 1 e 血z 巧f e q u e mi t e ms c t sg e n e r a t es t r o n g 娩z y a s s o c i a t i o nm l e s ，f o rt h es a k eo rr e d u c gt i l l l et o c o m p u t ei m p l i c a 虹o nd e f e ci n 血z z y c a i l d i d a t ei t e ms e t s ，o nt 1 1 eb a s i so fd e a l i n gw i t hr e d u n d a n tf l l z z ya s s o c i a t i o nr uj e s ，t h ef 血z y m u l t i p 忙l e v e l e da s s o c i a t i o nn l l e s 商n i n ga 1 9 0 r i 岫b a s eo ni m p l i c a t i o nd e g r e eh a v ef m h c r a m e l j o r a t e d ，w h j c hh a sb e c np r o v e dt ob ea c c i l r a t ea 1 1 de 任b c t i v eb yt h c o r i c sa n dt 1 1 er e s u l t so f i i 华中科技大学硕士学位论文 k e y w o r d s ：d a t a m i i l i n g ，a s s o c i a t i o nr u i e s ，血z 巧t n u l t i p l e - 】e v e l e d 够s o c i a t i o n r l i l e s ， 如z z yi m p l i c a “o no p e r a t o li m p b c a t i o d e g r e e i 独创性声明 本人声明所呈交的学位论文是我个人在导师指导f 进行的研究工作及取得的 研究成果。尽我所知，除文中已经标明引用的内容外，本论文不包含任何其他个 人或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中以明确方式标明。本人完伞意识到= ；串= 声明的法律结果由本人承担。 学位论文作者签名 日期：州年华月矽日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅 和借阅。本人授权华中科技人学可以将本学位论文的全部或部分内容编入有关数 据库进行检索，可以采用影印、缩印或扫描等复制手段保存和扯编本学位论文。 保密口，在年解密后适用本授权书。 木论文属于 不保密曰。 ( 请在以上方框内打“”) 学位论文作者签名：檄 日期：彦护g 年月夕日 华中科技大学硕士学位论文 1 绪论 1 1 研究背景 随着计算机技术和信息技术的快速发展和广泛应用，成千上万个数据库被用于石油 勘探、政府办公、金融管理、商业销售和科学研究等领域，并且呈增量发展趋势。随着 数据库技术的成熟和数据应用的普及，人类积累的数据量正在以指数速度迅速增长。近 十年柬互连网应用的不断深入，以及随之而来的企业内部网、企业外部网和虚拟私有网 的产生和应用，业务数据量急剧增长，人们可以跨越时空在网上交换数据信息和协同合 作。这样，人们面对的是浩瀚无垠的信息海洋，海量数据或称数据洪水t f 向人们滚滚涌 柬。 面对海量数据，人们往往无所适从，无法发现数据巾存在的关系和规则，无法根据 现有的数据预测未来的发展趋势。据估计，现今一个大型企业数据库中的数据，只有百 分之七得到了很好应用。这样一来，人们一方而感到“数据过剩”和“信息爆炸”，另一方 面又感到“信息贫乏”和“数据关在牢笼中”。奈斯伯特惊呼“w ea r ed m w n i n gi n n f o r i l 】a t i o n ，b u ts t a n r i n gf o rk 玎o w l e d g e ”( 我们正被数据信息淹没，却又饥渴于知识) 。 于是，一个新的挑战被提了出来：在这被称之为信息爆炸的时代，信息过量儿乎成 为人人需要面对的问题。如何才能不被信息淹没，而是从中及时发现有用的知识，提高 信息利用率呢? 海量的数据若能为企业自身的业务决策和战略发展服务，则它就是企业 最宝贵的资源，否则，人量的数据只能成为沉重的负担。因此，面对“人们被数据信息 淹没，却叉饥饿于知讨l ”的两难境遇，各种各样的可_ q j 的信息和数据的“井喷”，提供r 前所未有的机会去开发白动的数掘驱动技术来提取有用的知识。数据挖掘和知训发现 ( d a 【am i n i n ga 1 1 dk n o w l e d g ed i s c o v e d m k d ) 技术应运而生，并得以蓬勃发展，越米 越碌示出其强大的生命力。 近年来，由于快速增长的数据量和口益贫乏的信息量之问的矛盾运动，致使数据挖 掘技术己经引起了信息产业界的广泛关注，对数据挖掘技术进行系统和深入细致的研究 是垒球信息化发展的客观要求。数据挖掘技术有很多研究领域，其中关联规则就是一个 重要的研究方向，有着极其重要的应用价值。 关联规则( a s s o c i a t i o nr u l e s ) 是数据挖掘中一个重要的课题，虽近几年已被业界所广 泛研究。关联规则挖掘是挖掘发现大量数据叶1 项集( i t e m s e t ) 之间有趣的关联或相关联系。 关联规则挖掘的一个典型例子是购物篮分析。从大量交易数据库中不同商品之间的关联 华中科技大学硕士学位论文 联系，找出顾客购买行为模式，可以应用于商品货架设计、货存安排、分类没计和商务 决策制定等。 使用精确关联规则挖掘算法对数量型数据进行关联规则挖掘，不会得到预期的效 果，对于许多应用来讲，由于数据在多维空问中存在多样性，凶此要想从低层次概念上 发现强关联规则可能是较为困难的，虽然多层关联规则可以挖掘高抽象层次概念卜的强 关联规则，但是计算复杂性高，如何利用模糊理论和蕴涵度，更好更高效地挖掘数量型 和多层关联规则，这足本文的研究所在。 1 2 国内外研究概况 121 数据挖掘的国内外研究状况 数据挖掘( d a t am i n i “g ) ，顾名思义就是从大量的数据中挖掘出有用的信息，即从大 量的、不完争的、有噪声的、模糊的、随机的实际应用数据中发现隐含的、规律的、人 们事先未知的、但又是潜在有用的并且最终可理解的信息和知识非平凡过程。这些数 据可以是结构化的如关系数据库中的数据，也可以是半结构化的，如文本，图形，图像 数据，甚至是分布在网络上的异构型数据。发现知识的方法可以是数学的，也可以足非 数学的，可以是演绎的，也可以是归纳的。发现了的知识可以被用于信息管理、查询优 化、决策支持、过程控制等，还可以进行数据自身的维护，数据挖掘与传统分析方法是 有区别的，数据挖掘与传统的数据分析( 如查询、报表、联机应用分析) 的本质区别是数 据挖掘是在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的信息应具 有先未知，有效和可实用i 个特征。先前未知的信息是指该信息是预先未曾预料到的，即 数据挖掘是要发现那些不能靠直觉发现的信息或知识，甚至是违背直觉的信息或知识，挖 掘出的信息越是出乎意料，就可能越有价值。在商业应用中虽贝型的例了就是家连锁店 通过数据挖掘发现了小孩尿布和啤酒之阳j 有着惊人的联系。数据挖掘f d a t a m 洒n g ) 是一 个多学科交叉研究领域，它融合r 数据库a t a b a s e ) 技术、人工智能( a 州n c i a l i m e l l i g e n c e ) 、机器学习( m a c l l j n el e a m i n 曲、统计学( s t a m t i c s ) 、知识工程( k n o w l e d g e e n g t m e e 曲g ) 、面向对象方法( o b j e c t o d e n t c dm e t h o d ) 、信息检索( i n f o 咖a t i o nr e 岍e v 幽、 高性能计算( h i g h - p e r f o n n 柚c ec o m p u t i n g ) 以及数据可视化( d a t a s u a l iz a _ 丘o n ) 等最新技 术的研究成果。绎过十几年的研究，产生了许多新概念和方法。特别是最近几年，一些 基本概念和方法趋于清晰，它的研究j f 向着更深入的方向发展。 1 9 8 9 年8 月，在美国底特律召开的第1 1 届围际人工智能联合会议的专题讨论会上 华中科技大学硕士学位论文 首次出现k d d 这个术语，随后在1 9 9 1 ，1 9 9 3 ，1 9 9 4 年都举行了k d d 专题讨论会，集 中讨论数据统计、海量数据分析算法、知识表示、知识运用等问题。k d d 凼际学术大 会研究重点逐渐从发现方法转向系统麻用，并且注重多种发现策略和技术的集成，以及 多种学科之间的相互渗透，数据挖掘和知识发现成为当前计算机科学界的一大热点。 1 9 9 8 年在美国纽约举行的第四届知识发现与数据挖掘国际学术会议上有3 0 多家软件公 司展示了数据挖掘软件产品，不少软件已经在北美和欧洲的国家得到应用。 m e l ag r o u p 曾做出这样的评论：“全球重要的企业、组织会发现，到2 1 世纪数据 挖掘技术将是他们商业成功t j 否的举关重要的影响因素”。i b m 公司发布了基丁标准的 数据挖掘技术。i b m d b 2 智能挖掘器积分服务，可用于个性化的解决方案。曲大统计软 件公司s a s 和s p s s 也推出了各自的数据挖掘工具e n t e 巾d s e m i n e r 和c l e m e 埘n e 。此外， 在i n t e m e t 上还有不少k d d 电了出版物，其中以半月刊k n o w l e d g cd i s c o v e r yn u 錾g e l s 最为权威，另一份在线周刊为d s r 决策支持) ，1 9 9 7 年开始出版。自由论坛d me m a i lc h l b 可以通过电子邮件讨论数据挖掘和知识发现的热点问题。数据挖掘是数掘库和信息决策 领域的最盼沿的研究方向之，已引起了国内外学术界的j 1 。泛关注。 与国外相比，国内对d m k d 的研究稍晚，没有形成整体力量。1 9 9 3 年国家自然科 学基金首次支持我们对该领域的研究项目。甘前，国内的许多科研单位和高等院校竞相 开展知识发现的基础理论及其应用研究，这些单位包括清华大学、中科院计算技术研究 所、窄军第三研究所、海军装备论证中心等。其中，北京系统t 程研究所对模糊方法在 知识发现中的应用进行了较深入的研究，北京大学也在外展对数据立方体代数的研究， 华中科技大学、复旦人学、浙江大学、中国科技大学、中科院数学研究所、吉林大学等 单位开展了对关联规则开采算法的优化和改造；南京大学、四川联合大学和i 海交通大 学等单位探讨、研究了非结构化数据的知识发现以及w e b 数据挖掘。 日前数据挖掘的几个热点包括网站的数据挖掘( w e bs 沁d a t a m i n i 雌) 、牛物信息 或基因( b i o i n f o r m a t i c s 幢e n o m j c s ) 的数据挖掘及其文本的数据挖掘( 1 e x m a lm i n i n g ) 。 随着计算机计算能力的发展和业务复杂性的提高，数据的类型会越来越多、越来越复杂， 数据挖掘将发挥出越来越大的作用。 1 2 2 关联规则挖掘算法的研究状况 关联规则( a s s o c a t i o nr u l e s ) 尾挖掘发现大量数据中项集( i t e m s e t ) 之间有趣的关联或 相关联系，它在数据挖掘中是个重要的课题，虽近几年已被业界所广泛研究。关联规 则挖掘的个典型例子是购物篮分析。从大量交易数据库中不同商品之间的关联联系， 华中科技大学顽士学位论文 找出顾客购买行为模式，可以应用于商品货架设计、货存安排以及根据购买模式对用户 进行分类等。 关联规则的发现可分为两步，第步是迭代识别所有的频繁项目集，要求频繁项日 集的支持率不低于用户设定的最低值，第一步是从频繁项日集中构造可信度不低于用户 设定的最低值的规则，识别或发现所有频繁项目集足关联规则发现算法的核心，也是计 算最最大的部分。 从近年来的文献中可以看出，除了不断地提出一些新的挖掘技术外，人量的有关数 据挖掘的文章集中于讨论如何提高数据挖掘系统，尤其是关联规则挖掘的性能，这包括 算法的有效性、可伸缩性和并行处理。 由a g r a w a l ，i 商e l m s k i 和s w 帅i 吲首先提出了挖掘顾客交易数据库中项集问的关联 规则问题。最为著名的关联规则发现方法a 面o r i 算法由a g r a w a l 和s r i k 掣提出。为 了提高算法的效率，m a n n 帆t 0 i v o n e n 和v e r k a n l o 【4 】引入了修剪技术来减小候选集的大 小，由此可以显著地改进生成所有频集算法的性能，算法中引入的修剪策略基于这样一 个性质：一个项集是频集当且仅当它的所有子集都是频集。那么，如果候选k 项集中某 个候选项集有一个( k 1 ) 项子集不属于频繁k 项集，则这个项集可以被修翦掉不再被考 虑，这个修剪过程可以降低计算所有的候选项集的支持度的代价。结合这些工作的联合 出版物稍后出现在a g r a w a l m a n l l i l a ，s r i k a n t 0 i v o n e n 和v e r k a 1 0 吼产生关联规则的方 法在a g r a w a i 和s m r 锄t m l 中介绍，其核心是基于两阶段频集思想的递推算法，该关联规 则在分类上属于单维、单层、和尔关联规则。 p a r k ，c h e n 和y u f 在1 9 9 5 年提出了使用h a s h 表提高关联规则挖掘效率的算法，通 过实验发现寻找频繁项集的主要计算是在生成频繁2 项集上，p 破，c h e n 和y u 就是利 用这个性质引入散列技术束改进产生频繁2 项集的方法。其基本思想是：当扫描数据库 中每个事务，由候选l 项集产生频繁2 一项集时，对每个事务产生所有的2 项集，将它 们散列到散列表结构的不同桶中，并增加对应的桶计数，在散列表中对麻的桶计数低于 支持度阀值的2 项集不可能是频繁2 项集，可从候选2 项集中删除，这样就可大大压 缩了要考虑的2 项集。 一个高效地产牛频集的基丁杂凑的算法由p 盯k ，c h e n 和y u 口】提出，通过实验我们可 以发现寻找频集主要的训算是在生成频繁2 项集上，p a r k 等就是利用了这个性质引入 杂凑技术来改进产生频繁2 项集的方法。 事务压缩技术在a g r a w a l 和s r i k a n t l 8 l ，h a n 和f u 唧，以及p 龃k ，c h e n 和y u 【7 1 中介绍，因 华中科技大学硕士学位论文 为小包含任何k 项集的事务，不可能包含任何( k 十1 ) 项集，可对这些事务加上删除标 志，扫描数据库时不再考虑。 划分技术由s a v a s e r e o m i e c i s k j 和n a v a i h e 【1 0 】提出，这个算法先把数据库从逻辑上 分成几个互不相交的块，每次单独考虑一个分块并对它生成所有的频集，然后把产生的 频集合并，用来牛成所有可能的频集，最后计算这砦项集的支持度。这里分块的大小选 择要使得每个分块可咀被放入主存，每个阶段只需被扫描一次。而算法的正确性是由每 一个可能的频集至少在某一个分块中是频集保证的。上面所讨论的算法是可以高度并行 的，可以把每分块分别分配给某一个处理器生成频集。产生频集的每一个循环结束后， 处理器之间进行通信来产生全局的候选k 项集。通常这里的通信过程是算法执行时间的 主要瓶颈；而另一方面，每个独立的处理器生成频集的时间也是一个瓶颈。其他的方法 还有在多处理器之间共享个杂凑树来产生频集。存a p r i o r i 框架下，早期的并行和分 布关联规则挖掘被p a r k ，c h e n 和y u 【】l j ，a 鲜删a 1 和s h a 矗一1 引，c h e u n g ，h a i l ，n g 等研究。 选样方法在t 0 i v o n e n i l ”中讨论。基术思想是在给定数据的一个子集挖掘。对前一遍 扫描得到的信息，仔细地组合分析，可以得到1 个改进的算法，m a 【l i l a ，t o i v o n e n 和 v e r k a m o 先考虑了这一点【 j ，他们认为采样是发现规则的一个有效途径。随后又由 t o i v o n e n 进一步发展_ r 这个思想l l ，先使用从数据库巾抽取出来的采样得到一些在整个 数据库中可能成立的规则，然后对数据库的剩余部分验证这个结果。t o i v o n e n 的算法相 当简单并显著地减少了i 0 代价，但是一个很大的缺点就是产生的结果不精确，即存在 所谓的数据扭曲( d a l as k e w l 。分布在同一页面上的数据时常是高度相关的，可能不能表 示整个数据库中模式的分布，由此而导致的足采样5 的交易数据所花费的代价可能同 扫描一遍数据库相近。 动态项集计数在b m ，m o t w a n j ，u 1 1 m a l l 和1 j u r 州中给出，该技术将数据库划分为标 记开始点的块，不象a d r i 耐仅在每次完整的数据库扫描之前确定新的候选，在这种变 形中，可以在任何开始点添加新的候选项集。该技术动态地评估以被计数的所有项集的 支持度，如果一个项集的所有子集以被确定为频繁的，则添加它作为新的候选。结果算 法需要的数据库扫描比a 口r i o r i 少。 对于很多的应用来说，由于数据分布的分散性，所以很难在数据最细节的层次上发 现一些强关联规则，在i i a n 和f u p i ，s m a m 和a g r a w a l ”呻研究了多层关联规则挖掘。 对于多维数据库而言，除维内的关联规则外，还有一类多维的关联规则。根据是否 允许同个维重复出现，可以又细分为维间的关联规则( 不允许维重复出现) 和棍台维 华中科技大学硕士学位论文 关联规则( 允许维在规则的左右同时出现) 。在挖掘维间关联规则和混合维关联规则的 时候，还要考虑不同的宁段种类：种类型和数值犁。对于种类型的字段，原先的算法都 可以处理。而对于数值型的字段，需要进行一定的处理之后才可以进行。k m b e b 王a l l 和c l l i a n 一7 1 使用量化属性的静态离散化和数据立方体，研究了挖掘多维关联规则。挖掘 区问数据上的( 基于距离的) 关联规则由m i l 】e r 和y a n “提出。 关联规则挖掘有许多扩充，例如，在a g r a w a l 和s 缺a m i ”】中的序列模式挖掘，在 m 咖讧1 “v o n e n 和v e r k a l i l o 口0 1 中的e s p i s o d e s 挖掘，在k o p e r s l i 和h a n 口1 】中的挖掘空间 关联规则，在o z d e n ，r 锄a g w 砌y 和s i l b e r s c h a l 妒础中的有环的关联规则挖掘，在s a v 船e f e ， o m - c c i n s 虹和n a v a t h e 口3 1 中的否定的关联规则挖掘，在l u ，h m 和f e n 产4 1 中的事务间关 联规则挖掘年l | 在r a l l l a s w 乳m a h a j a i l 和s i l b e r c h a t z l 2 ”中的日历购物篮分析。频繁闭合 项集的挖掘由p a s q u i e lb 舶t i d e ，1 抽u i l 和l a k h a l 俐提出，而有效的挖掘算法由p e i ，h 妯 和m a 0 口”提出。频繁项集的深度优先产生由a 影m a l ，a g g a r w a l 和p m s a d 2 8 魄出。挖掘 频繁模式而不产生候选的方法 _ | = ih a n ，p e i 和y i n 1 提出。挖掘关联规则的有效增量更新 由c h e l l n 舀h 锄，n g 和w o n g 提出。 强关联规则的必趣度问题被c b e n ，h a i l 和y u p “，b n ，m o t w a n i 和 s i i v e r s t e i n 3 2 l ，a g g a n v a l 和y u 讨论。推广关联到相关的有效方法在b r i i l ，m d t w i 和 s i i v e r s t e i n 口4 中给出。评估关联规则兴趣度的支持度一置信度框架的其他替代在a h m e d ， e 1 m a k k v 和t a h a 俐中提出。s i l v e r s t e i n ，b n ，m o 硼：l i 平uu i l i l l a i l 研究了挖掘事务数据 库因果关系结构的问题。在s r i k a n t 和a g r a w 甜”1 巾，多层关联规则挖掘以概化关联规则 的形式研究，并提mr - 兴趣度度量，以删除冗余规则。 基于约束的关联规则挖掘在n g ，l 础s h m a n a n ，h a n 和p a 【l g l 3 6 】，l a k s 蚰a i l a i l ，n g ，h a l l 和p m g p e i 和h 中研究。挖掘受| 5 艮的相关集的有效方法在g 咖m e ，l a k s h m a n a i l 和w 口g 3 9 1 中给出。 上述关联规0 挖掘算法是针对非数量数据而言，首要考虑的是算法的效率与可扩展 性问题。这些算法对于挖掘布尔型关联规则是非常有效的。由于关系数据库中的属性类 型较为丰富，它可包含数量类型( 如年龄、月薪等) 和枚举类型( 如学历、职称等) ，因而 又提出了基于数量类型和枚举类型的关联规则的挖掘问题，现对此已提出了多种挖掘算 法。这些关联规则、描述的都是确定和精确的概念之问的关系。关联规则的前件和后件 用确定的、精确的概念表示，称为确定性关联规则。由丁客观世界的多样性和复杂性， 许多事物难f 用精确和确定的概念表示，例如，人的高、矮等，难于用具体的数值表达， 华中科技大学硕士学位论丈 确定性关联规则在此情况下，不能有效地表达数据之间的关联关系。这样，若仍然使用 精确关联规则挖掘算法对这些数据源进行关联规则挖掘，就不会得到预期的效果。因此， 模糊集理论被引入到量化关联规则的挖掘中。将模糊集理论引入到关联规则的研究中， 利用模糊概念对数据进行概括和抽象，通过定义模糊关联规则的概念，拓广了传统的确 定性关联规则的表示和应用范围，用模糊关联表示数与数之间的关系，得到的关联规则 更易被一般用户理解，而且知识的指导性较强。 模糊数学是研究和处理模糊现象的数学，这阜的模糊性主要是指客观事物的差异在 中介过渡时所呈现的“亦此亦彼”性。1 9 6 5 年，美国计算机与控制专家l a z a d e h 教授发 表了模糊集合论论文【4 w ，提出用“隶属函数”这个概念来描述现象差异的中间过渡， 从而突破了古典集合论中属于或不属于的绝对关系。l a z a d e h 教授这一开创性的工作， 标志着数学的一个新的分支一模糊数学的诞生。 近年来，为处理现实中更常见的数值型数据，研究者的兴趣开始转向量化关联规则 的挖掘。模糊集理论被引入到量化关联规则的挖掘中，提出了一些模糊关联规则的挖掘 算法4 “”“”。针对数据挖掘中的“尖锐边界”问题，朱天清，熊平删提出了将事务属性模糊 集中的元素作为甲一属性来处理的方法。熊肖华，姚建初m 1 采用模糊集理论，对模糊属 性进行了转换。刘耀和，胡宝清l 通过定义模糊事务数据库用模糊概念表示事务数据 之间的关联关系，研究了模糊关联的性质。蓝荣钦，刘增良，杨晓梅1 4 7 1 研究了模糊空间关 联规则挖掘的理论。董豆豆，李登峰，程春田【4 ”针对普通关联规则不能表达挖掘对象中模 糊信息的关联性的问题，给出了一系列有关模糊关联规则的定义。 1 3 本文的主要工作 本文对数据挖掘中的模糊多层关联规则挖掘算法和基于蕴涵度的模糊多层关联规 则挖掘算法问题进行了深入的研究。在分析数量型和多层关联规则挖掘特性的基础上， 引入模糊集理论和蕴涵度的知识，研究了模糊多层关联规则挖掘算法和基于蕴涵度的模 糊多层关联规则挖掘算法。本文主要工作如下： 1 介绍了目前数据挖掘的国内外研究状况和关联规则挖掘算法的研究状况。 2 数据挖掘和关联规则综述。数据挖掘综述介绍数据挖掘的概念、过程、功能、常 用技术。关联规则综述介绍关联规则的基本概念和分类，重点介绍了关联规则的典型挖 掘算法( 搜索算法、a p i o r i 类算法和频繁模式增长算法) 和关联规则挖掘算法的扩展。 详细介绍了a 州o r i 算法的性质、频繁项集的产生过程和存在的不足。 华中科技大学硕士学位论文 3 介绍了模糊集理沦的基本概念，揣述了模糊关联规则的定义和性质，并从理论上 探讨了模糊关联规则挖掘过程。在探讨了多层关联规则挖掘方法的基础上，鼓计了模糊 多层关联规则挖掘算法，且设计和实现了用v f p 6 o 产生模糊频繁集的方法，并利用它 运行的结果来进行算法举例和结果分析，最后指出了算法的特点和不足。 4 引入了三角模、模糊蕴含算子和蕴涵度的概念，使用了由t - 模计算支持度的公式 和由支持度计算蕴涌度的公式，利用蕴涵度代替置信度的方法，设计了基于蕴涵度的模 糊多层关联规则挖掘算法。在处理冗余模糊关联规则的基础上，进一步改进了基于蕴涵 度的模糊多层关联规则挖掘算法，理论和实验结果分析证明算法是正确的和有效的。 华中科技大学硕士学位论文 21 数据挖掘综述 2 数据挖掘和关联规则综述 2 1 1 数据挖掘的概念 数据挖掘( d a t am i n i n g ) ，顾名思义就是从大量的数据中挖掘 h 有用的信息，即从大 量的、不完全的、有噪声的、模糊的、随机的实际应用数据中发现隐含的、规律的、人 们事先未知的、但又是潜在有用的并且蛙终可理解的信息和知识非平凡过程“。这些数 掘可以是结构化的，如关系数据库中的数据，也可以是牛结构化的，如文本，图形，图像 数据，甚至是分布在网络上的异构型数据。 2 12 数据挖掘的过程 数据挖掘是一个复杂的过程，通常包含多个相互联系的步骤，并且随着应用需求和 数据基础的不同，数据挖掘处理的步骤可能也会有所小同。通常数据挖掘的基本步骤包 括： 1 问题定义：清晰地定义山业务问题确定数据挖掘的目的。 2 分析数据：数据分析的目的是辨别出需要分析的数据集合，缩小处理范围，提高 数据挖掘的质量。 3 准备数据：数据准备具体包含数据清理、数据集成、数据选择、数据变换、数据 规约和数据质量分析等步骤。 ( 1 ) 数据清理：在数据中消除错误和不一致，并解决对象识别问题的过程。 ( 2 ) 数据集成：将多个数据源中的数据合并存放在一个统一的数据存储中f 可以采用 数据仓库技术) ，数据集成将多个数据源中的数据合并处理，解决语义模糊性并整合成 一致的数据存储。 ( 3 ) 数据选择；抽取与分析任务相关的数据，在尽可能保持数据原貌的前提下展大 限度地精简数据量。通过数据选择可以使得数据的规律性和潜在性史加明显。数据选择 包括属性选择和数据抽样。 ( 4 ) 数据转换：数据转换或合并成适当的形式，以利于挖掘。数据转换包括数据离 散化、新建变量、转换变量、拆分数据和格式变换等内容。 ( 5 ) 数据归约：数据归约将辨别出需要挖掘的数据集合，缩小处理范围，是在数据 9 华中科技犬学硕士学位论文 选择基础上对挖掘数据的进步约简。数据归约又称数据缩减或数据浓缩，数据归约就 是将初始数据集转换到某种更加紧凑的形式而又不丢失有意义的语义信息的过程。 ( 6 ) 数据质量分析：数据挖掘的效果和数据质量之问有着紧密联系。所谓“垃圾入， 垃圾出”，即数据的质量越好，则挖掘的结果就越精确，反之则不可能取得好的挖掘结 果。数据质量的含义包括数据的正确性、数据的一致性、数据的完整性、数据的可靠性 四个方面。 5 建立模型：在问题进一步明确，数据结构和内容进一步调整的基础上，就可以形 成知识的模型。对历史数据建立一个预测模型，然后冉用另外一些数据对这个模型进行 测试。这一步是数据挖掘的核心环节，一个好的模型没有必要与已有数据1 0 0 地相符， 但模型对未来的数据应有较好的预测。建立模型是一个反复的过程。需要仔细考虑不同 的模型以判断哪个模型对所需解决的问题最有用。 6 评价模型：数据挖掘得到的模型有可能是没有实际意义或没有使用价值的也可 能不能准确反映数据的真实意义，甚至在某些情况下是与事实相反的，因此对于数据挖 掘的结果需要进行评估，确定数据挖掘是否存在偏差挖掘结果是否正确，确定哪些是 有效的、有用的模犁，是否满足用户需求。评价模犁将发现的知识以用户能了解的方式 呈现，根据需要对数据挖掘过程中的某些处理阶段进行优化，直到满足要求。 7 数据挖掘：对所得到的经过转换的数据进行挖掘。除了完善从选择合适的挖掘算 法外，其余一切工作都能自动地完成。 8 数据解释：l ：d d 由于最终是面向人类用户的，因此可能要对发现的模式进行可 视化，或者把结果转换为用户易懂的另一种表示，如把分类决策树转换为“i f t l 】e n ” 规则。 2 1 3 数据挖掘的功能 数据挖掘的功能主要是关联分析、聚类分析、概念类描述、分类和预测、孤立点分 析、演变分析、刚序模式和偏差分析等。 1 关联分析 关联分析发现关联规则，这些规则展示了给定数据集巾数据项之问的潜在的联系。 关联分析广泛应用于购物储或事务数据分析中。 2 聚类分析 聚类是把数据按照相似性归纳成若干类别，同一类中的数据彼此相似，不同类中的 数据相异。聚类分析可以建立宏观的概念，发现数据的分布模式，以及可能的数据属性 0 华中科技大学硕士学位论文 之制的相互关系。 3 分类和预测 分类就是找出一个类别的概念描述，它代表，这类数据的整体信息，即该类的内涵 描述，并用这种描述柬构造模型。一般用援划或决第树模式表示。预测是构造和使用模 越评估无标号样本类，或评估给定样本可能具有的属性值或值区间。分类和预测的区别 在于：分类是预测分类标号( 或离散值) ；预测是建立连续值函数模型。 4 演变分斩 数据演变分析描述行为随时间变化的对象的规律或趋势，并对其建模。它包括时间 序列数据分析、序捌或周期模式匹配和基于类似性的数据分析。 5 ，时序模式 时序模式是指通过时问序列搜索出的重复发生概率较高的模式。与回归一样，它也 是用己知豹数据预测寒来的值，健这些数据的区别是变量所处时间的不同。 6 孤立点分析 孤立点可能是度量或执行错误所导致的，也可能琵固有的数据变异性的结采。许多 数据挖掘算法试图使孤立点的影响虽小化或捧除它们。但这可能导致重要信息的丢失， 凼为孤立点本身可能是非常重要的。 7 偏差分析 在偏差中包括很多有用的知识，数据库中的数据存在很多异常情况，发现数据库中 数据存在 f 匀异常情况是非常重要的。，偏差检验的基本方法就是寻找观察结果与参照之间 的差别。 2 ，1 4 数据挖掘常用技术 1 遗传算法 遗传算法是一种基于生物自然选择与遗传桃理的隧机搜索算法，屉一种仿生全局优 化方法。遗传算法具有的隐含并行性、易于和其它模型结合等性质使得它在数据挖掘中 被加以虚用。s u l l “已成功地开发了一个幕于遗传算法的数据挖掘工具，利用该工具对 两个飞机失事的真实数据痒进行了数据挖掘实验，结果表明遗传算法是进行数据挖握的 有效方法之一。但遗传芹法的算法较复杂，收敛十局部极小的较早收敛问题尚未解决。 2 神经嗣络方法 神经网络由于本身良好的鲁棒性、自组织自适应性、并行处理、分布存储和高度容 鞲等特性非常适合解决数据挖掘的问题，因此近年来越来越受到人们的关注。神绎网络 华中科技大学硕士学位论文 方法的缺点是”黑箱”性，人们难以理解网络的学习和决策过程。 3 决策树方法 决策树是种常用丁预测模型的算法，它通过将大量数据有日的分类，从中找到一 些有价值的，潜在的信息。它的主要优点是描述简单，分类速度快，特别适合大规模的 数据处理。最有影响和最早的决策树，法是冉q u i n l a n 提出的著名的基于信息熵的i d 3 算法。 4 覆盖正例排斥反例方法 它足利用覆盖所有币例、排斥所有反例的思想来寻找规则。比较典型的算法有 m i c h a l s k j 的a q l l 方法、洪家荣改进的a o l 5 方法以及其他的a e 5 方法。 5 统计分析方法 在数据席字段项之问存在两种关系：雨数关系( 能用函数公式表示的确定性关系) 和 相关关系( 不能用函数公式表示，但仍是相关确定性关系) ，对它们的分析可采用统计学 方法，可进行常川统计、幽归分析、相关分析、差异分析等。 6 粗糙集方法 粗糙集坪论是一种研究不精确、不确定知识的数学工具。粗糙集方法有几个优点： 不需要给出额外信息，简化输入信息的表达空间，算法简单，易于操作。目前成熟的关 系数据库管理系统和新发展起束的数据仓库管理系统，为粗糙集的数据挖掘奠定了坚实 的摹础。但粗糙集的数学基础是集合沧，难以直接处理连续的属性。i f i i 现实信息表中连 续属性是普遍存在的，因此连续属性的离散化是制约粗糙集理论实用化的难点。 7 模糊集方法 利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊模式识别和模糊聚类 分析。系统的复杂性越高，模糊性越强，一般模糊集合理论采用隶属度来刻画模糊事物 的亦此亦彼性。李德毅等人在传统模糊理论和概率统计的基础上，提出了定性定量不确 定性转换模型云模型，并形成了云理论。 2 2 关联规则综述 2 2 1 关联规则的基本概念 定义2 1 数据项与数据项集h m 设i = i 1 ，玩，i m 是m 个不同项口的一个集合，每个i k ( k = 1 ，2 。，m ) 称为数据项( i t e m ) 数据项的集合i 称为数据项集( i t e m s e t ) ，简称为项集，其元素个数称为数据项集的长度 华中科技大学硕士学位论文 长度为k 的数据项集称为k 维数据项