（计算机应用技术专业论文）关系数据库中多表间关联规则算法研究.pdf

哈尔滨理工大学t 学硕士学位论文 关系数据库中多表间关联规则算法研究 摘要 随着数据库技术的飞速发展以及i n t e r n e t 的迅猛普及，数据库技术已成 为信息社会中对大量数据进行有效组织与管理的重要技术。特别是近些年在 各大商场、书店等使用的条码技术，更为各企业方便快捷地收集数据提供了 帮助。数据挖掘技术正好可以从大量数据中发现隐藏在数据背后的知识，从 而帮助人们更好地理解事物的本质。 关联规则是数据挖掘中一种重要的知识类型。随着关系数据库的广泛使 用，研究关系数据库中的关联规则挖掘算法有着广阔的发展前景。当前这方 面的常用算法是基于单表的，这些算法虽可以应用于多个表上，但需进行相 应的转化一将多个表转换为一个表后才可应用。另外，还有基于i l p 技术提 出的算法等，这些算法分别在挖掘效率及应用范围、模式表示等方面存在一 些不足，这就要求提出新的关联规则挖掘算法以适应需求。 本文通过研究分析，借鉴传统的a p r i o r i 关联规则算法的先进思想，分 析了该算法在时间复杂度以及只应用于事务数据库的不足的基础上，结合 c r o s s m i n e 算法中的元组标识传播( t u p l ei dp r o p a g a t i o n ) 的思想，提出了一 种新的应用于关系数据库中多表间关联规则挖掘的算法b m m 。该算法通过 分析关系数据库中关联规则的多值、多维等特性，针对这些特征采取相应的 措施来解决：首先对关系数据集进行数据预处理，以适应关联规则的发现， 然后，通过扩展元组标识传播的思想得到每个属性所对应的目标关系l d ， 以此可以通过目标关系i d 将所有考察的多表间的属性联系起来，从而可以 直接作用在多个表上：最后，算法中的数据结构采用了链表结构来表示频繁 项集及其对应的目标关系i d ，以达到减少对数据库的访问次数。 最后通过实验验证b m m 算法。同时将b m m 算法与基于s q l 的算法 进行比较做出了比较分析，实验证明该b m m 算法表现出更好的时间性能。 关键词关系数据库：数据挖掘：关联规则；多表 哈尔滨理工大学t 学颂上学位论文 r e s e a r c ho fa s s o c i a t i o nr u l e s a l g o r i t h m s b a s e do nm u l t i p l et a b l e sf o rr e l a t i o n a ld a t a b a s e a b s t r a c t d a t a b a s et e c h n o l o g yh a sb e c o m et h et e c h n o l o g yw h i c hi s i m p o r t a n tf o r m a s sd a t a o r g a n i z i n ga n dm a n a g i n gi ni n f o r m a t i o ns o c i e t yw i t ht h er a p i d d e v e l o p m e n t so fd a t a b a s et e c h n o l o g ya n dw i d e s p r e a do fi n t e r n e t t h en e w b a r c o d et e c h n o l o g ya d o p t e di ns u p e r m a r k e t ，b o o k s t o r es p e c i f i c a l l yp r o v i d e se v e n m o r eh e l po nc o l l e c t i n gd a t aw h i c hi sf a s ta n dc o n v e n i e n tf o re n t e r p r i s e d a t a m i n i n gt e c h n o l o g yh a p p e n st or e v e a lt h ek n o w l e d g eh i d d e nb e h i n dd a t af r o mt h e m a s sd a t aw h i c hc a l lh e l pp e o p l eb e t t e ru n d e r s t a n dt h en a t u r eo fo b j e c t a s s o c i a t i o nr u l ei sa l li m p o r t a n tk n o w l e d g et y p ei nd a t a m i n i n g 。t h e a l g o r i t h ms t u d y i n go nt h ea s s o c i a t i o nr u l eo fr e l a t i o n a ld a t a b a s eg i v e saw i d e d e v e l o p m e n tp r o s p e c t c u r r e n t l y , t h er e g u l a ra l g o r i t h mi sb a s e do ns i n g l et a b l e o nt h i s a s p e c t ，e v e nt h o u g ht h e s ea l g o r i t h m sc a nt r a n s f e rt om u l t i p l et a b l e s ， c o r r e s p o n d i n gt r a n s f o r m a t i o ni sn e e d e dw h i c hi st r a n s f o r m i n gm u l t i p l et a b l e s i n t oo n e i na d d i t i o n ，o t h e ra l g o r i t h m sa r ep r o p o s e d ，s u c ha st h ea l g o r i t h mb a s e d o ni l pw h i c hh a v es o m ef l a w si n m i n i n ge f f i c i e n c y , f i e l do fa p p l i c a t i o na n d m o d ew h i c hr e q u e s tn e wa s s o c i a t i o nr u l em i n i n ga l g o r i t h mb e i n gp u tf o r w a r dt o a d o p tr e q u i r e m e n t a f t e rg i v i n ga n a l y s i sa n du t i l i z a t i o no ft h ea d v a n c e di d e so ft r a d i t i o n a l a p r i o r ia s s o c i a t i o nr u l ea l g o r i t h m ，c o m b i n e dt h et u p l ei dp r o p a g a t i o n tc o n c e p t i nc r o s s m i n ea l g o r i t h m ，t h i sd i s s e r t a t i o np u tf o r w a r dan o v e la l g o r i t h mb m m a p p l i e do na s s o c i a t i o nr u l em i n i n ga m o n gm u l t i p l et a b l e si nr e l a t i o n a ld a t a b a s e b a s e do nt h ea n a l y s i so ft h et i m ec o m p l e x i t yo ft h i sa l g o r i t h ma n dt h er e s t r i c t i o n t h a tc a no n l yb ea p p l i e do nt r a n s a c t i o n a ld a t a b a s e a f t e rt h ec h a r a c t e r i s t i c s a n a l y s i so fm u l t i v a l u ea n dm u l t i - d i m e n s i o n n ，m e a s u r e sa r et a k e nt os o l v et h e s e a c c o r d i n gt ot h e s ec h a r a c t e r i s t i c s ：d a t aa r ep r e p r o c e s s e di nr e l a t i o n a ld a t as e tt o a d j u s tt h ef i n d i n go fa s s o c i a t i o nr u l e ，t h e nt h eo b j e c tr e l a t i o ni dc o r r e s p o n d i n gt o 1 1 哈尔滨理_ t 大学工学硕l ：学位论文 e a c hp r o p e r t yi so b t a i n e dt h r o u g he x t e n d i n gt h et u p l ei dp r o p a g a t i o nc o n c e p t ， w h i c hi sa b l et oc o n n e c tt h ep r o p e r t i e sa m o n gm u l t i p l ei n s p e c t e dt a b l e su s i n g o b i e c tr e l a t i o ni d ，w h i c ha c t sd i r e c t l yo nm u l t i p l et a b l e s ，e v e n t u a l l y , c h a i nl i s t s t r u c t u r ei su s e da sd a t as t r u c t u r ei nt h ea l g o r i t h mt oi n d i c a t ef r e q u e n ti t e m s e t a n dr e l a t e do b j e c tr e l a t i o ni dt or e d u c et h ed a t a b a s ea c c e s s i n gt i m e s a tt h ee n do ft h i sd i s s e r t a t i o n ，t h ee x p e r i m e n ti sp e r f o r m e dt ov e r i f yb m m a l g o r i t h m b m ma l g o r i t h ma n dt h ea l g o r i t h mb a s e do ns o l a r ec o m p a r e da n d a n a l y s i si sg i v e nw h i c hs h o w s t h a tb m m a l g o r i t h mo w n ss h o r t e re x e c u t i n g t i m e k e y w o r d sr e l a t i o n a ld a t a b a s e ，d a t am i n i n g ，a s s o c i a t i o nr u l e s ，m u l t i p l et a b l e s n 1 哈尔滨理工大学硕士学位论文原创性声明 本人郑重声明：此处所提交的硕士学位论文关系数据库中多表间关联规则 算法研究，是本人在导师指导下，在哈尔滨理工大学攻读硕士学位期间独立进 行研究工作所取得的成果。据本人所知，论文中除已注明部分外不包含他人已发 表或撰写过的研究成果。对本文研究工作做出贡献的个人和集体，均已在文中以 明确方式注明。本声明的法律结果将完全由本人承担。 作者签名：笔禹弗 日期： 加7 年弓月2 。同 哈尔滨理工大学硕士学位论文使用授权书 关系数据库中多表间关联规则算法研究系本人在哈尔滨理工大学攻读硕 士学位期间在导师指导下完成的硕士学位论文。本论文的研究成果归哈尔滨理工 大学所有，本论文的研究内容不得以其它单位的名义发表。本人完全了解哈尔滨 理工大学关于保存、使用学位论文的规定，同意学校保留并向有关部门提交论文 和电子版本，允许论文被查阅和借阅。本人授权哈尔滨理工大学可以采用影印、 缩印或其他复制手段保存论文，可以公布论文的全部或部分内容。 本学位论文属于 保密n ，在年解密后适用授权书。 不保密i 习。 ( 请在以上相应方框内打) 作者签名：笼茹昂日期：山印年弓月加日 导师签名：4 4 家- 季日期：，z 卯罗 年弘月孑日 哈尔滨理工大学工学硕? j 二学位论文 1 1 引言 第1 章绪论 随着数据库和信息技术的高速发展，在商业部门、科研和工业设计等多个 领域都广泛的使用了数据库技术。尤其是近些年超市、书店等大型商店都采用 的条码技术，使得数据库技术显得越来越重要。显然，数据库的发展为人们带 来了许多便利的操作。 然而，在网络技术的高速发展的带动下，各企业更加方便、快捷的收集数 据，这使得数据库的存储量急剧增加。面对大量数据，人们若只是做些统计分 析之类的简单操作，那么这无疑是对数据库的存储空间和时间的浪费。为了更 好地利用这些数据，发现隐藏在海量数据背后的有用的规则和知识，彻底突破 被描述为“数据丰富，但信息贫乏 的局面，需要有更好的技术和方法来处理 这些数据。数据挖掘技术便是为了解决上述问题而发展起来的。数据挖掘n 1 是 指从海量数据中自动、高效地提取出隐含的、先前未知的、有价值的知识和信 息。这为海量数据向有用信息和知识的转换架起了桥梁，不但可以帮助人们从 数据库特别是数据仓库的相关数据中提取出所感兴趣的知识、规律或更高层次 的信息，而且也可以帮助人们从不同程度上去分析它们，从而可以更有效地利 用数据库或数据仓库中的数据。它不仅可以用于描述过去数据的发展过程，而 且还能进一步预测未来的发展趋势。关联规则是关系数据挖掘中的一个重要研 究内容，它是从大量数据中发现数据项间的关联关系，从而能够更好的认识事 物的客观规律。 传统的数据挖掘方法是基于属性值( 又称命题的) 的单一表进行数据挖 掘。但在普遍使用关系数据库的今天，数据库中的关系表不只一个，而是多 个，而且表同表之间还存在着各种联系，极大的影响了数据挖掘的精度。因 此，基于关系数据库的多表的数据挖掘( 即关系数据挖掘) 的研究便提出来了。 作为一个学科分枝，关系数据挖掘( r e l a t i o n a ld a t am i n i n g ，r d m ) 是一个跨学 科的领域。它结合了关系数据库、机器学习、统计理论等多个领域的研究成 果，致力于处理由多关系组成的关系数据库知识发现问题，研究挖掘关系型数 据的新型技术及其有效的应用实践。其中的关系关联规则可以直接应用于关系 数据库的多表结构中，无需向单一数据表转换，并从中挖掘出有用的知识和信 哈尔滨理1 二大学工学硕：l j 学位论文 息。在关系数据库大范围使用于多种行业的今天，研究基于关系数据库的关联 规则挖掘成为一个很必然的选择。此外，关系数据库理论在有效存储和处理结 构化数据方面有着丰富的理论，这些理论会有利于多关系数据挖掘技术的发 展。 1 2 研究现状及发展前景 1 2 1 数据挖掘研究现状 数据挖掘( d a mm i n i n g ，d m ) 是近年来的研究热焦，是在1 9 8 9 年8 月于美 国底特律市召开的第十一届国际联合人工智能学术会议上正式形成的，常常与 k d d ( 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 ) 混用。从1 9 9 5 年开始，每年主办一次 k d d 国际学术会议，将k d d 和d m 方面的研究推向了高潮。 信息技术的飞速发展推动了对数据挖掘的需求。需求促进发展，从出现到 现在，数据挖掘有了飞快的发展。目前，国外在基于关系数据库和事务数据库 进行数据挖掘和知识发现的各种知识模型的研究己经取得了一定的进展，最有 影响的发现算法有：密西根州立大学e r i c kg o o d m a n 的遗传算法、加拿大 s i m o nf r a s e r 大学h a nj i a w e i 教授的概念树提升算法位1 、m m 的a g r a w a l r 的关联规则算法伸3 、澳大利亚的0 u i n l a njr 教授的分类算法1 等。 数据挖掘技术的提出是应于应用的需求，所以，近些年在上述理论基础上 数据挖掘应用工具的开发方面也有一定的成果。如g t e 、m i c r o s o f t 、 i n t c g r a l s o l u t i o n s ，u n i c a t e c h n o l o g i e s ，t h i n k i n gm a c h i n e s ，d a t a m i n d 、i b m ， u r b a ns c i e n c e 等公司，相继开发出一些实用的k d d 商业系统和原型系统，另 外还有欺诈预警用的f a l c o n 、f a i s 、c l o n e d e t e c t o r ，市场分析用的 b e h a v i o r s c a n 、e x p l o r e r 、m d t ( m a n a g e m e n td i s c o v e r yt 0 0 1 ) ，金融投资领域的 s t o c ks e l e c t o r 、a i ( a u t o m a t e di n v e s t o r ) 等各种实用的数据挖掘工具层出不穷。 相较于国外来说，国内数据挖掘的研究还不是很多，但已有一些大学、研 究院开始了数据挖掘的相关研究，并已有一些相关论文出现于国内刊物上。如 北京系统工程研究所对模糊方法在知识发现中的应用进行了较深入的研究，北 京大学正从事数据立方体代数的研究，空军第三研究所、其中安徽大学、华中 理工大学、复旦大学、浙江大学、中国科技大学、中科院数学研究所、吉林大 学等单位进行了对关联规则挖掘算法的优化及相关领域的研究，取得了一定的 成果，南京大学、四川联合大学和上海交通大学等单位探讨、研究了非结构化 哈尔滨理工大学1 = 学硕l ：学位论文 数据的知识发现以及w e b 数据挖掘。还有清华大学、中科院计算技术研究 所、海军装备论证中心等单位也进行了研究。 1 2 2 关联规则研究现状 关联规则嫡1 是由a g r a w a lr 等人提出的，自从提出以后，该问题的研究 得到了迅速的发展。到目前为止，其主要的研究方向在多种文献中都有所介 绍，现列举如下： 1 多循环挖掘算法这类算法可以分为基于完全搜索思想和基于裁减搜 索思想两个分枝。其中由a g r a w a lr 等人提出的性能较差的a i s 算法属于 完全搜索算法，a p r i o r i 算法和a p r i o r i h y b i r d 、p a r kjs 等人提出的d h p 1 算 法属于裁剪搜索思想，以及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 h 提出的抽样算法s a m # i n g 等等。其中最有效和有影响的算法为：a p f i o f i ， d h p 和n 螺t 1 0 n 算法。 2 增量式更新算法关联规则的增量式更新问题主要有两类：一是当事 物数据库d b 中的数据增多时，如何能够保证在原来给定的最小支持度和最小 置信度下生成新数据库中的关联规则；二是当最小支持度和最小可信度发生改 变时，如何能够生成满足原事务数据库d b 的新的关联规则。其中，文献【7 】考 虑了上述更新问题中的第一类问题，给出了一个基本框架与算法f u p 。文献【8 】 则针对关联规则更新的第二类问题进行了研究分析，并给出了相应的算法i u a 和p i u a 。 3 基于约束的关联规则的研究对于海量数据集来说，如果使用传统的 关联规则挖掘算法，则一定会挖掘出大量用户不感兴趣的规则，这为用户理 解、解释和规则的使用都将会带来不便。所以简单利用最小支持度和最小置信 度来限制或约束关联规则便显得有点力不从心了，于是有人提出了以减少算法 生成的规则的数量为目的的基于约束的关联规则挖掘的方法。 在这方面，r a y m o n dtn g 等人提出了一些算法。他们指出传统的关联规 则存在一些缺陷，用户只能被动地等待挖掘结果。为解决上述问题，他们提出 了一个用户参与的方案，以及两个约束属性：反单调型( a n t i m o n o t o n i c i t y ) 和 简洁型( s u c c i n c t n e s s ) ，并提出了一个基于约束的关联规则挖掘算法c a p l 9 i ，基 于约束的关联规则算法研究也成为了一个热门研究，如文献 1 0 】、【1 1 等。 4 并行关联规则的算法研究由于数据库的规模一般很大而且不只在一 个站点，为了加快关联规则的挖掘速度和提高挖掘效率，数据挖掘的并行算法 哈尔滨理工大学工学硕1 j 学位论文 被提了出来。 目前已提出的并行关联规则挖掘的算法有：a g r a w a lr 等人提出的 c o u n t 分布、d a t a 分布和c a n d i d a t e 分布算法，h a ne u i h o n g 等人提出的智能数 据分布算法i d d 和混合分布算法h d ，d a v i dw a i l o kc h e n u n g 等人提出的 d m a 、f d m 和a p m 算法等。其中，c o u n t 分布算法是a p r i o r i 算法在并行环 境下的应用，它要求计算机p i ( i = 1 ，2 ，n ) 对d b i ( i _ 1 ，2 ，n ) 进行多趟扫 描，具有速度快、易实现和要求各个机器间同步次数少等优点，但是c o u n t 分 布算法中产生的通信量和候选项目集的数量都很大。i d d 算法能有效地利用并 行环境的聚集内存来执行算法，通信量和候选项目集都比c o u n t 分布算法大大 减少了，它更适合于单一数据源。i - i d 算法合并了i d d 算法和c o u n t 分布算法 的优点，因而更有效。d m a 和f m a 算法虽然克服了c o u n t 分布算法的部分缺 点，但却增加了各个机器间同步次数，a p m 算法运行在共享内存的多处理器 上，它扫描数据库的次数要小于c o u n t 分布算法，并且生成更少的候选项目 集。文献【1 2 1 在分析各并行算法的基础上，提出了一种f p a r m 的并行算法。 5 多层关联规则的研究传统的关联规则挖掘算法是依据数据库中发生 的具体项目进行非常细节的挖掘，对不同牌子的同一种商品( 例如“绿茶”和 “红茶”) 将被看作不同的项目，然而有时用户可能想发现更高层次的规律， 例如所有茶类的商品或者所有饮料类的商品等，为此提出了多层关联规则的挖 掘问题。以图1 - 1 为例，若在原始的概念层上，算法在“绿茶”和“白酒”之 图1 - 1 多层关联规则 f i g 1 - 1m u l t i l a y e ra s s o c i a t i o nr u l e 间很难发现购买规则，但容易发现6 0 买饮料的顾客也买酒类，所以在归纳抽 象层上或多层次上挖掘关联规则有重要意义。目前关联规则发现已经从单一概 念层发展到多概念层，在概念层次上一层层往下，从一般到具体，其发现的关 联规则所提供的信息也更具体，逐步深化的知识发现。 哈尔滨理工人学_ 学硕士学位论文 y o n gi i a f u 等人提出用规则模板来限制或指导挖掘过程的方法。 r a m a k r i s h n a n 提出了挖掘通用或泛化的关联规则问题。h a nj i a w e | 和y o n g j i a f u 提出了m lt 2 l 1 的算法，该算法首先根据要发现的任务从数据库中生成 一个包含概念层次信息的新数据库，然后在新数据库上自顶向下逐层递进，在 不同层次上发现相应的关联规则，该算法有三个变种：m tt 1 l a 、m l t m l l 和m l t 2 l a 。 6 意外关联规则的挖掘传统的关联规则挖掘算法，一般用来发现数据 库中大多数数据所遵循的规律，但同时数据库中还存在有另外一些规律。这些 规律用传统的关联规则挖掘算法无法发现的，而且常常又容易被人们所忽视， 因此称它们为意外或例外规贝u ( e x c e p t i o nr u l e s ) ，例外规则常常有很大的价值。 h o s c h k apm 等人提出了e x o l o r a 系统来发现例外规则，该系统利用专业人 员的背景知识来发现例外规则。 一 7 数字属性或量化关联规则的研究经典的关联规则挖掘是指事务数据 库中的规则，其属性为布尔属性。然而现实生活中除了布尔属性外，还有数字 属性( 或量化属性，例如：年龄、薪资、订购量和工程量等) 和分类属性( 例 如：动物、国籍和职业等) 的数据。为处理这类属性的数据，提出了数字属性 的关联规则挖掘问题。 r a m a k r i s h n a n 等人提出把量化和分类属性的数据按区间映射成布尔属性的 数据，然后再在此基础上利用传统的关联规则挖掘方法来挖掘这些属性的数 据。t a k e s h i 等人提出了数字属性优化关联规则的问题，即最优支持度规则( 置 信度不低于用户指定的最小置信度而支持度最大的规则) 和最优置信度规则( 支 持度大于或等于用户指定的最小支持度而置信度为最高的规则) ，两者统称优 化关联规则。 8 基于k d d 内在机理的关联规则算法的研究当前k d d 发展的主流是 寻找在各类数据库和应用问题的背景下高性能、高扩展性的挖掘算法。 1 9 9 6 年，a n a n dss 等提出了基于证据理论的数据挖掘一般框架e s d ，提 及了“用户的先验知识与先前发现的知识可以耦合到发现过程中”。 2 0 0 2 年后，杨炳儒的系列论文k d d 中双库协同机制的研究( i ) 引，从多种 角度独立地提出了双库协同机制，并构建了将k d d 与双库协同机制相结合的 k d d * 结构，在结构与功能上形成了相对于k d d 而言的一个开放的、优化的 扩体。提出了基于双库协同机制的挖掘关联规则算法m a r a d b c r n 。 9 遗传算法、神经网络算法挖掘关联规则普通的关联规则的挖掘存在 些许缺陷。针对这些缺陷，近两年少数的研究者尝试用遗传算法和神经网络算 哈尔滨理1 二大学工学硕士学位论文 法来挖掘关联规则。 遗传算法由于其解决问题以混沌、随机和非线性为典型特征，这为其它科 学技术无法解决或难以解决的复杂问题提供了新的计算模型。对于大量的数据 的乱杂无序的特征，遗传算法是有效的解决方法之一。目前基于遗传算法的数 据挖掘的研究主要集中在分类系统的方面，而对于关联规则的提取，遗传算法 的应用还处于尝试的阶段，例如文献 1 4 1 。 神经网络正是由于其本身良好的鲁棒性、自组织适应性等特性，特别适用 于有噪声的数据、有冗余的信息以及数据不完整等情况下来挖掘数据库中的知 识。 另外，对于多关系间关联规则挖掘技术也有多方面的研究。对于基于多个 表的关联规则挖掘技术，i l p 技术是最早应用于将传统数据挖掘算法扩展到关 系数据库中数据挖掘的技术之一n 射。早期基于这种思想的算法有，1 9 9 9 年， t o i v o n e nh 与d e h a s p el 结合i l p n 力技术与a p r i o r i 算法的思想，提出 了多表环境下的第一个关联规则挖掘算法w a r m r n 巩坞1 。另一个典型算法是 f a r m e r 他啪算法。f a r m e r 算法与w a r m r 一样，都是使用一阶逻辑的 表达方式来定义项目集和支持度，但算法效率却比w a r m a 更高。接着也有 许多算法被提出： g o e t h a l sb 提出源自w a r m r 的w a r m e r 的算法捌。该 算法不依赖于关键参数，并可挖掘出全部多关系关联规则。另外， c l a r ea 等 提出了内存限制更小的r a d a r 算法心引，r a d a r 算法使用文档检索系统中的 倒排索引技术来优化模式评估阶段的性能。 与上述发现关系关联规则模式不同的方法是非基于i l p 技术的关系关联规 则挖掘算法。从知识表示方式的角度，这些方法可以分为基于“选择图 的多 关系数据挖掘方法心乱2 副和“基于图的数据挖掘方法m 2 7 1 。 相对于国外发展态势而言，多关系关联规则在国内的发展还处于刚起步的 阶段。但国内学者对i l p 方法的研究已经相当成熟了，这为关系关联规则的发 展奠定了良好的基础。如由张润琦等提出f o i l p l u s 算法幢引：克服了原来f o i l 算法的常量序限制的缺点。并且，国内学者开始利用多关系方法解决空间数据 挖掘( s d m k d ) 的复杂语义表达问题，其最为直接的方法是引入空间谓词，同 时采用多关系数据挖掘技术俚9 l 。另外，空间关联规则挖掘是一个多关系关联 规则挖掘问题1 3 ，其问题本质上是属于多关系关联规则任务，通过利用m r a r 技术，国内研究者在该方向已获得一些研究成果。如，张伟提出的m r f p d a 算法通过引入优化的具体化算子，较w a r m r 算法与f a r m e r 算法具有良好 的效率与扩展性。 哈尔滨理丁大学工学硕士学位论文 1 2 3 发展前景 数据挖掘涉及多学科技术的集成，包括数据库技术、统计学、机器学习、 高性能计算、模式识别、神经网络、数据可视化、信息检索、图像与信号处理 和空间数据分析等学科。单从数据库角度来说，数据挖掘可以在任何类型的信 息存储上进行。包括关系数据库、数据仓库、事务数据库、高级数据库系统、 展开文件和w w w 。因此，数据挖掘是信息产业最有前途的交叉学科。 1 3 主要内容和组织结构 1 3 1 主要内容 数据挖掘是一门结合了多种学科的交叉学科，是一门新兴的学科，也是很 有发展前途的学科。文章介绍首先介绍了数据挖掘的基础知识，并详细介绍了 关联规则的概念以及分类。接着介绍了经典的关联规则算法a p r i o r i 以及常见 多关系中关联规则的挖掘算法的思想，并分析其中存在的不足。在此基础上拟 提出一个基于关系数据库中多关系间关联的关联规则算法，该算法借鉴了传统 a p r i o r i 算法的思想精髓，联系关系数据库中关联规则的特征对其进行改进，并 结合元组标识传播的方法来完成多表关联的。新的算法可以直接应用于关系数 据库中的多个表上，并用实验验证了算法的正确性以及与其它算法的比较分 析。 1 3 2 组织结构 全文共分六章，下面是各章的结构安排： 第1 章绪论。介绍本文的课题背景、国内外研究现状、发展前景以及文章 的主要内容和组织结构。 第2 章数据挖掘技术及相关理论。介绍了数据挖掘的概念、分类、分析 了数据挖掘的系统结构，并介绍了数据挖掘的应用情况。 第3 章关联规则挖掘及算法分析。介绍了关联规则挖掘的概念、关联规则 挖掘的过程、并对经典的关联规则挖掘算法a p r i o r i 算法和常见关系间关联规 则算法的思想进行介绍，指出其中存在的缺陷和不足。 第4 章提出新的算法。本章是本文的中心：在分析关系数据库中关联规则 哈尔滨理工火学工学硕士学位论文 的特征的基础上，对经典算法a p r i o r i 进行改进，并对改进后的算法进行了定 性分析，而后结合元组传播的思想提出了一种适合于关系数据库中多关系间关 联规则挖掘的算法。 第5 章主要对提出的算法进行实验验证，并与其它算法进行比较分析。 结论。对全文进行了总结性分析，并对今后的工作做出了进一步的展望。 哈尔滨理t 大学1 = 学硕，i j 学位论文 2 1 引言 第2 章数据挖掘技术及相关理论 自2 0 世纪6 0 年代以来，数据库和信息技术已经系统地从原始的文件处理 演化到复杂的、功能强大的数据库系统，从层次和网状数据库系统发展到关系 数据库系统。而计算机硬件稳定的、迅速的进步导致了功能强大的计算机、数 据收集设备和存储介质彬 y 的蕴含式我们称之为关联规则，其中x cl ，y ci ，并且x n y = f 。 定义3 3 支持度嘲1 ( s u p p o r t )指项集t 在事务数据库中出现的概率p c o ， 是由包含项集xuy 的事务数与总事务数的相除得到的。支持度表示的是关联 规则在数据库中的重要性，表示了规则出现的频度。如，对于关联规则 x = y ，其支持度是p ( x u y ) ，如式( 3 1 ) 所示。 s u p p o r t ( x = y ) = s u p p o r t ( xuy ) = p ( x u y )( 3 1 ) 定义3 4 置信度( c o n f i d e n c e ) 表示为p ( y i x ) ，是由包含项集x ny 的事务 数与包含项集x 的事务数相除得到的。置信度衡量关联规则的可信程度，表示 规则的强度。如，对于关联规则x = y 的置信度则是i ( v l x ) ，计算方法如式 ( 3 2 ) 所示。 c o n f i d e n c e ( xuy ) = s u p p o r t ( xuy ) s u p p o r t ( x )( 3 2 ) 如何找到代表有用信息的规则的两个衡量标准就是支持度和置信度，这两 个阀值是描述关联规则的重要概念。为了方便，我们用m i n 表示最小support 哈尔滨理工人学工学硕士学位论文 支持度，用r a i nc o n f i d e n c e 表示最小置信度。其中，最小支持度表示项目集在 统计意义上的最低重要性；最小置信度表示规则的最低可靠性。 为了除去无意义的规则，一般使用限值。这样，如果能够得到这样一条规 则，它的支持度一定大于等于最小支持度，并且它的置信度也一定大于等于最 小置信度的。这样的规则才是有趣的规则，也是我们所要挖掘的。 定义3 5 频繁项目集如果项集满足最小支持度r a i n ，即项目集的出sup 现频度大于或等于最小支持度m i l ls u p 与数据库d 中事务总数的乘积( 即 s u p p o r t ( a ) = m i n _ s u p ) ，则称它为频繁项目集，频繁k - 项目集记为k 。 定义3 6 非频繁项目集如果项目集a 不满足最小支持度，则称为非频 繁项目集。 定义3 7 候选项目集懈1由支持度可能大于或等于最小支持度的项目组成 的项集则称为候选项集。 3 3 关联规则的分类 关联规则按照不同的分类方法有多种类别： 1 根据规则中所处理的数据值的类型分类如果所处理的数据值仅有两 个值，或者考虑的是项目存在与否，则称此类规则为布尔关联规则；如果所处 理的数据值是量化的项或属性之间的关系，则称此为量化关联规则。 2 根据规则中涉及的数据维分类如果关联规则中的所有的项仅涉及一 个维，则称此为单维关联规贝u ( s i n g j e d i m e n s i o n a la s s o c i a t i 衄r u l e ) 。如式( 3 3 ) 所示。 b u y ( x ，“k e y b o a r d ”) = b u y ( x ，“m o u s e )( 3 3 ) 如果规则涉及的是多个维，则称它为多维关联规则。如式( 3 4 ) 所示。 a g e ( x , “3 0 3 9 ”) a i n c o m e ( x , 4 2 k 4 8 k ，) = b u y ( x ，“h i 曲- 1 v ，) ( 3 4 ) 3 根据规则中所涉及的抽象层分类如果关联规则中的项涉及到不同的抽 象层，称之为多层关联规则；反之为单层关联规则。 3 4 传统关联规则挖掘算法分析 关联规则的挖掘主要包括两个步骤：一是找出所有的频繁项集，也就是通 过用户给定的m i n s u p p o r t 寻找所有频繁项目集，即满足s u p p o r t 不小于 m i n _ s u p p o r t 的项目集，事实上这些频繁项集之间可能具有包含关系，一般我 哈尔滨理工大学工学硕士学位论文 们只关心那些不被其他频繁项目集包含的所谓大频繁项集的集合，这些大频繁 项集是形成关联规则基础；二是由频繁项目集生成强关联规则，通过用户给定 的m i n c o n f i d e n c e ，在每个最大频繁项目集中寻找c o n f i d e n c e 不小于 m i n c o n f i d e n c e 的关联规则。第二步比较简单，所以目前的算法大多是针对第 一步来说的。本节主要分析经典的关联规则算法和常见的几种多关系间关联规 则算法。 3 4 1 a p r i o r i 算法与分析 传统关联规则的挖掘主要是基于事务数据库的，常见的算法有a p r i o r i 算 法和f p g r o w t h 算法以及它们的变形。 3 4 1 1a p r i o r i 算法数据挖掘领域挖掘关联规则最著名的算法是a p r i o d 算法， 也是第一个关联规则挖掘算法，由a g r a w a lr 等人提出。现在很多关联规 则挖掘算法都是通过优化和完善a p r i o f i 算法而得到的。 a p r i o r i 算法使用一种称作逐层搜索的迭代方法，k 一项集用于探索( k + 1 ) 项 集。首先找出频繁1 项集l l ，根据l 1 找到k ，如此下去，直到不能找到频繁 k - 项集为止。这其中主要利用了a p f i o f i 算法的核心原理：频繁项集的子集是 频繁项目集；非频繁项目集的超集是非频繁项目集。也就是说：频繁项目集的 所有非空子集都必须也是频繁的。 整个a p r i o r i 算法主要是分为两步来进行的： 1 连接o o i n ) ：为得到k ，通过k 1 与自己连接，从而得到候选k 项集 c k 。 2 剪枝( p r u n e ) ：上一步得到的c k 是k 的超集，c k 中的成员可以是也可 以不是频繁的。但所有的频繁k - 项集都包含在c k 中。扫描数据库，确定c k 中 每个候选项的计数，从而确定k 。但是，c k 可能会很大，此时，将运用一个 很重要的性质：任何频繁项集的所有非空子集都必须也是频繁的，即非频繁项 集的超集不可能是频繁的。通过该性质可以筛选c k ，以减小q 的个数。 算法描述如下： a p r i o r i 算法如下： 输入：事务数据库d ；最小支持度m i n s u p 输出：d 中频繁项集l p r o c e d u r eg e n _ f r e q u e n t _ i t e m s e t s 0 1 ：l i = f i n d 一_ f r e q u e n t 哈尔滨理t 火学- 亡学硕士学位论文 2 ： f o r ( k = 2 ；l t 4 f ；k + + ) d o 3 ： c k = a p r i o r i _ g e n ( l k _ l ，m i ns u p ) ； 4 ：f o re a c ht r a n s a c t i o nt dd o 5 ： c t = s u b s e t ( c k ，t ) ； 6 ：f o re a c hc a n d i d a t ec ec l 7 ： c c o u n t + + ； 8 ： ) 9 ：l k = c c d c c o m a t = m i n _ s u p ； 1 1 ：) 1 2 ：r e t u r nb u k l k ； 3 4 1 2 算法分析从上述算法可知a p f i o r i 算法采用的是逐层搜索的迭代方 法，即( k + 1 ) 项集是依据k - 项集生成的。其中，该算法存在很多问题： 1 每得到一个k 都需要访问一次数据库，多次访问数据库，势必会造成 时间代价大、i o 负载大的问题；再有就是候选项集是通过自身连接，当属性 值很大时可能会产生大量的候选项集c k ，而这在时间和主存空间上都是不允 许的。 2 当数据库中数据量发生变化时，必须重新执行h p r i o r i 算法，以此来发 现适应新数据库的关联规则，这也意味着之前发现的关联规则不能使用了。 3 a p r i o f i 算法是基于数据库容量较小，在主存容量范围之内，则当随着 存储数据的增加数据库的容量变大时，该算法便不能再运用了。 4 该算法仅考虑了事务数据库中关联规则的挖掘，对于实际应用中的多 关系型数据、文本型数据以及w w w 类型数据，该算法不再适用，所以，其 应用范围很小。 另外，还有一些从a p r i o r i 算法优化而来的新算法。这些算法主要从两方 面入手来提高算法效率：一是减少对数据库的访问次数；二是尽量减小候选项 集的规模。如：由p a r kjs 等人提出的使用散列技术的d h p 算法1 、 s a v a s e r e 等人提出的基于p a r t i t i o n 划分的算法 ( 该算法减少了对数据库的访问 次数) 、由m a n n i l a 等人提出的基于采样的算法1 38 | 、基于动态项目集计数的优化 算法以及基于事务压缩的优化算法等。