（计算机应用技术专业论文）贝叶斯方法用于多关系数据挖掘的研究.pdf

摘要 摘要 多关系数据挖掘( m r d m ：m u l t i r e l a t i o n a ld a t am i n i n g ) 的研究领域涉及 多个学科，它在由多张表构成的关系数据库中进行知识发现。挖掘由复杂结构 化对象构成的数据也属于该研究范畴，因为在一个关系数据库中，要把这些目标 数据进行标准化表述需要用到多张表。多关系数据挖掘旨在将一些已存在的并较 为成熟的学科知识整合在一起，如归纳逻辑程序设计( i l p ：i n d u c t i v el o g i c p r o g r a m m i n g ) ，知识发现( i ( d d ) ，机器学习，关系数据库等等，以此来为挖掘 多关系的数据生成新的方法，并为这些新的方法生成可用于实践的应用软件。 传统的数据挖掘算法是在数据库的一张单一的表中查找模式。然而在现实应 用中，把多张表中的数据挤压进一张表需要花费大量的心思和工夫，而且还可能 造成信息的丢失。现在，多关系数据挖掘的时代已经来临了。 本文在传统数据挖掘的算法基础上对多关系数据挖掘的主要研究方法进行 了介绍和比较，然后从分类的效率和正确率出发，对各种基于贝叶斯原理的方法 进行了仔细研究并将之应用到多关系数据挖掘中。 第一章是绪言，首先简要介绍了多关系数据挖掘的定义，然后根据它的研究 意义和研究范畴分析了它的应用现状。最后是论文的组织结构。 第二章对传统数据挖掘技术的概念，过程以及一些分析方法进行了综述。 第三章介绍了多关系数据挖掘技术的常用方法，包括i l p 、多关系关联规则、 多关系分类、多关系聚类等等。 第四章开始对多关系数据挖掘中的分类算法展开了仔细研究。本章主要是运 用各种贝叶斯方法到多关系分类的规则连接中，先后讨论了朴素贝叶斯、t a n 、 d l b a n 各自的优缺点，并用c l p 实现了完整的贝叶斯分类器。 第五章提出了一种基于语义关系图的多关系朴素贝叶斯分类器，该方法将三 种技术：语义关系图，元组标识传播，多关系朴素贝叶斯相互融合，共同实践应 用到多关系的分类算法中，再经实验证实了它的高效性和高正确率。 第六章是对全文的总结和对未来研究工作的展望。 贝叶斯方法用于多关系数据挖掘的研究 论文的主要工作和特色如下： 1 )将三种基于贝叶斯网络的方法即朴素贝叶斯、t a n 、d l b a n 运用到多 关系分类算法的规则连接中，并用c l p 实现了完整的贝叶斯分类器。 2 )提出一种多关系朴素贝叶斯分类器，仔细阐述了如何对分类过程中 的语义关系图进行剪枝优化，从实验中可看出这种方法具有非常强 的实用性和非常高的效率和正确性。 关键词：多关系数据挖掘，i l p ，分类，贝叶斯，元组标识传播 a b s t r a c t m u l t i r e l a t i o n a ld a t am i n i n g ( m r d m ) i st h em u l t i - d i s c i p l i n a r yf i e l dd e a l i n g 、析t l lk n o w l e d g ed i s c o v e r yf r o mr e l a t i o n a ld a t a b a s e sc o n s i s t i n go fm u r i p l et a b l e s m i n i n gd a t aw h i c hc o n s i s t so fc o m p l e x s t r u c t u r e do b j e c t sa l s of a l l sw i t h i nt h es c o p e o ft h i sf i e l d ，s i n c et h en o r m a l i z e dr e p r e s e n t a t i o no fs u c ho b j e c t si nar e l a t i o n a l d a t a b a s er e q u i r e sm u l t i p l et a b l e s t h ef i e l da i m sa ti n t e g r a t i n gr e s u l t sf r o me x i s t i n g f i e l d ss u c ha si n d u c t i v el o g i cp r o g r a m m i n g , k d d ，m a c h i n el e a r n i n ga n dr e l a t i o n a l d a t a b a s e s ；p r o d u c i n gn e wt e c h n i q u e sf o rm i n i n gm u l t i - r e l a t i o n a ld a t a ；a n dp r a c t i c a l a p p l i c a t i o n so f s u c ht e c h n i q u e s t y p i c a ld a t am i n i n ga p p r o a c h e sl o o kf o rp a t t e r n si nas i n g l e r e l a t i o no fa d a t a b a s e b u tf o rm o s tr e a l - w o r da p p l i c a t i o n s ，s q u e e z i n gd a t af r o mm u l t i p l er e l a t i o n s i n t oas i n g l et a b l er e q u i r e sm u c ht h o u g h ta n de f f o r ta n dc a l ll e a dt ol o s so f i n f o r m a t i o n a n dn o w , m r d mi st h ef i e l dw h o s et i m eh a sc o m e o nt h eb a s i so f r e s e a r c hu p o nt r a d i t i o n a ld a t am i n i n ga r i t h m e t i c ，t h i sd i s s e r t a t i o n i n t r o d u c e sa n dc o m p a r e ss o m em a i nt e c h n i q u e so fm u l t i r e l a t i o n a ld a t am i n i n g ，a n d t h e nf r o mt h ea n g l eo f e f f i c i e n c ya n da c c u r a c y , i tr e s e a r c h e si n t ov a r i o u st e c h n o l o g i e s b a s e do nb a y e s i a nm e t h o da n da p p l i e st h e mt om r d m c h a p t e r1 i sap r e f a c e ，i nw h i c ht h ed e f i n i t i o no fm r d mw i l lb r i e f l yb e i n 灯o d u c e da b o v ea l l ，a n dt h e na c c o r d i n gt ot h er e s e a r c hf i e l d s ，a n dt h es i g n i f i c a n c eo f m r d m ，w ew i l la n a l y s i si t sa p p l i c a t i o ns t a t u si nq u o i nt h ee n d , i tw i l lg i v et h e f r a m e w o r ko f t h i sd i s s e r t a t i o n c h a p t e r 2s u m m a r i z e st r a d i t i o n a ld a t am i n i n gt e c h n i q u e s c o n c e p t i o n s ， p r o c e d u r e sa n ds o m ea n a l y s i sw a y sa n dm e a n s mt h et h i r dc h a p t e r , w ew i l lp r e s e n tt e c h n i q u e si nc o r n n o no fm r d m , i n c l u d i n gi l p , m u l t i - r e l a t i o n a l a s s o c i a t i o nr u l e s ，m u l t i - r e l a t i o n a lc l a s s i f i c a t i o n , m u l t i - r e l a t i o n a lc l u s t e r i n g ，e t e f r o mc h a p t e r4o n , w ew i l ld o $ o m es p e c i f i ca n dd e t a i l e dr e s e a r c ho n c l a s s i f i c a t i o no fm r d m c h a p t e r4m a i n l ya p p l i e sv a r i o u sb a y e s i a nt e c h n i q u e st o i h 贝叶斯方法用于多关系数据挖掘的研究 c o m b i n i n gr u l e si nm u l t i - r e l a t i o n a lc l a s s i f i c a t i o n a f t e rd i s c u s s i n gn a i v eb a y e s i a n ， t a na n dd l b a ns u c c e s s i v e l ya n dc o m p a r i n gt h e i ro w ne x c e l l e n c e sa n d s h o r t c o m i n g s ，w ep r e s e n ta f u l lb a y e s i a nc l a s s i f i e ri m p l e m e n t e da sac l p p r o g r a m i nt h ef i f t hc h a p t e r , w ep u tf o r w a r dam u l t i - r e l a t i o n a ln a i v eb a y e s i a nc l a s s i f i e r b a s e do ns e m a n t i cr e l a t i o n s h i pg r a p h t h r e et e c h n i q u e s ，i e s e m a n t i cr e l a t i o n s h i p g r a p h ，t u p l ei dp r o p a g a t i o n , a n dm u l t i r e l a t i o n a ln a i v eb a y e s i a na l ei n t e g r a t e dt ob e a p p l i e dt om u l t i r e l a t i o n a lc l a s s i f i c a t i o na l g o r i t h m f r o mt h ee x p e r i m e n t ，w e c a n c o n c l u d et h a to u rm e t h o dh a sg r e a te f f i c i e n c ya n dh i g ha c c u r a c y i nt h es i x t hc h a p t e r , is u m m a r i z em yr e s e a r c hw o r ko f t h i sd i s s e r t a t i o n , a n di l l a k e ap r o s p e c to f m yf u t u r ew o r k g e n e r a l l ys p e a k i n g t h e m a i nw o r ka n df e a t u r eo f t h i sd i s s e r t a t i o na r e 鹊f o l l o w ： ( 1 )a p p l y i n gt h r e et e c h n i q u e sb a s e do nb a y e s i a nw e bt h e o r y , i e n a i v e b a y e s i a n , t a na n dd l b a nt or u l ec o m b i n i n go fm u l t i - r e l a t i o n a l c l a s s i f i c a t i o n , a n dt h e np r e s e n taf u l lb a y e s i a nc l a s s i f i e ri m p l e m e n t e da s ac l p p r o g r a m ( 2 ) p u t t i n gf o r w a r dam u l t i r e l a t i o n a ln a i v eb a y e s i a nc l a s s i f i e r , a n de x p l a i n i nd e t a i l e dh o wt ou s eap r u n i n gs t r a t e g yt oo p t i m i z et h es e m a n t i c r e l a t i o n s h i pg r a p hi nt h ep r o c e s so fc l a s s i f i c a t i o n f r o mt h ee x p e r i m e n t , w ec a nc o n c l u d et h a to u rm e t h o dh a ss t r o n gp r a c t i c a l i t ya sw e l la sg r e a t e f f i c i e n c ya n dh i g ha c c u r a c y k e y w o r d ：m r d m ，i l p , c l a s s i f i c a t i o n , b a y e s i a n , t u p l e i dp r o p a g a t i o n 独创性声明 卒人声明所呈交的学位论文是本人在导师指导f 进行的研究工作及取得的 研究成果。据我所知，除了文甲特别加以标注和致请l 的地方外，论文c p 不包含 其他人已经发表或撰写过的研究成果，也不包含为获得逮徽大鸯毫其他教育 机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何 学位论文版权使用授权书 本学位论文作者完全了解更微大学有关保留、使用学位论文的规定， 有扳像留并向困家有关邵 或机构送交论泛的复印件釉磁盘，危许论文被查阅 和借阅。岑人搜徽大蟛霹啦将学位沧支的金部或帮分内容编入有关数据库 避行检索，可以采用影国、缩印或扫描等复制手段保存、汇编学位沦文： ( 保密的学位论文在解密后适用本授权书) 学位论文作者鲐柔 日勿 锄鼢都涸 签字譬期：2 0 0 6 篮5 月8 日签字| j 期：却步多年厂月p 葺 学位论文作者毕、泣去向： i 作淬，侄 通随地址 电话 鄙编 8霹s年 ，p 2 期 意 空。 谢 签 良 孵勿 谢口h 的确 瑚、呆 作 巾名p、又竹殳 沦 考疗p伦 已 足均“啦 献 位 l 见 毕 图表索目 图表索引 x 图1 1 传统的数据挖掘方法在孤立的“平面的”关系上从事知识发现的任务l 图2 1 数据挖掘的过程1 0 图3 1f a m i l y 关系问题的精炼图的一部分2 3 图3 2 关系分类树 图3 3 关系回归树 图3 4 成员p e r s o n l 的信息层次 图3 5r d b c 聚类 图4 1 朴素贝叶斯模型 图4 2t a n 模型 图4 3d l b a n 模型 图5 1 元组标识在多表间传播的实例。 图5 2 实验数据库模型 园 3 0 。3 l 3 6 4 2 4 3 4 5 6 1 表1 1 由2 张表组成的关系数据库2 表1 2 分类的命题规则和关系规则表3 表2 1 常用数据挖掘软件 表3 1 数据库和逻辑程序的术语 表3 2 一个简单的i l p 问题：学习女儿关系 表3 3w a r m r 的一个说明语言指标举例 表3 4 关系分类树的决策表和逻辑程序表示 表3 5 关系的距离标准的学习示例 表5 1r e s e a r c h e r 表 表5 2 u n i v e r s i t y 表 表5 3 表5 4 表5 5 表5 6 表5 7 1 5 1 7 1 9 2 7 3 2 5 4 5 4 5 4 5 5 5 6 5 8 6 1 绪言 第一章绪言 1 1 多关系数据挖掘简介 1 1 1 什么是多关系数据挖掘 所谓数据挖掘，就是在数据中寻找模式。数据挖掘是从大量的、不完全的、 有噪声的、模糊的、随机的数据集中识别有效的、新颖的、潜在有用的，以及最 终可理解的模式的非平凡过程。它是一门涉及面很广的交叉学科，包括机器学习、 数理统计、神经网络、数据库、模式识别、粗糙集、模糊数学等相关技术。 那么，什么又是多关系数据挖掘呢? 多关系数据挖掘( m u l t i r e l a t i o n a l d a t am i n i n g ，m r d m ) 是数据挖掘研究方向热点研究课题之一，然而，与现有的大 多数经典的数据挖掘方法不同的是，多关系数据挖掘不是只在一张单独的数据表 中发掘模式，它是在关系数据库的多张表( 或关系) 中进行 图1 1 传统的数据挖掘方法在孤立的“平面的”关系上从事知识发现的任务 ( f i g u r e1 1t r a d i t i o n a ld a t am i n i n ga p p r o a c h e sw o r ko ns i n g l e ”f l a t 。r e l a t i o n s ) 从历史的角度看，如同k d d 的早期发展受机器学习领域的研究影响一样，多 关系数据挖掘是在关系学习发展的背景下产生发展起来的。关系学习的核心方法 是归纳逻辑程序设计i l p ( i n d u c t i v el o g i cp r o g r a m m i n ) 多关系数据挖掘的起 源可以追溯到上世纪9 0 年代初的i l p 研究。 对于许多实际应用来说，把多个关系的数据挤塞进一张表需要花费大量的心 思和工夫，而且还可能造成信息的丢失和数据的冗余。这些弊端直接促进了多关 贝叶斯方法用于多关系数据挖掘的研究 系数据挖掘的发展：多关系数据挖掘可以直接对多关系数据库中的数据进行分 析，它不需要第一步把这些数据统统挤压进一张表里。因此，被挖掘的关系可以 存储在关系数据库中，也可以存储在演绎数据库( d e d u c t i v ed a t a b a s e ) 中。 多关系数据挖掘m r d m 也常常被简称为关系数据挖掘r d m ”1 。在这一部分， 我们来看看多关系数据挖掘的数据、模式和算法。 关系数据( r e l a t i o n a ld a t a ) 关系数据库通常是由一些表( 关系) 而不是一张表组成。表i 1 所示的数据 库包含两个关系：c u s t o m e r 和m a r r i e d t o 。关系可以直观地用二维图表来定义， 也可以用表述清晰的逻辑规则来含蓄地定义，后者一般代表可从其它关系推导出 的关系，例如，已知父亲母亲的关系表述后，我们就可以隐含地定义出祖父祖母、 兄弟姐妹及祖先关系。 表i 1 由2 张表组成的关系数据库 ( t a b l e1 1ar e l a t i o n a ld a t a b a s ew i t ht w ot a b l e s ) c u s t o m e r 表 g e n d e ra g ei n c o m e t o t a l s p e n tb i g s m a r r i e d t o 表 m a l e3 02 1 4 0 0 0 f e m a l e1 91 3 9 0 0 0 m a l e5 55 0 0 0 0 f e m a l e4 82 6 0 0 0 m a l e6 31 9 1 0 0 0 m a l e6 31 1 4 0 0 0 m a l e5 83 8 0 0 0 m a l e2 23 9 0 0 0 1 8 8 0 0 1 5 1 0 0 1 2 4 0 0 8 6 0 0 2 8 1 0 0 2 0 4 0 0 1 1 8 0 0 5 7 0 0 s p o u s e ls p o u s e 2 c l c 2 c 3 c 4 c 5 c 6 c 2 c l c 4 c 3 c 1 2 c 1 4 关系模式( r e l a t i o n a lp a t t e r n s ) 关系模式包括关系数据库中的多重关系。比起单数据表中的模式，它们要用 更具表现力的语言来描述。主要的关系模式扩展了单表数据挖掘中的命题模式 ( p r o p o s i t i o n a lp a t t e r n ) 类型。因此，我们就有了相应的关系分类规则，关 系回归树，关系关联规则。 表1 2 给了一个分类的命题规则和关系规则的例子，其中用至u t c u s t o m e r 关 系和m a r r i e d t o 关系。上面一条是命题规则，它把一个人定义为大顾客的条件是 要求这个人本身有高收入；下面的一条是关系规则，这条关系规则的意思是，如 ：墨 d一口；阱凹h 绪 言 果一个人c 1 和一个高收入的人c 2 结了婚，那么这个人c 1 就是大主顾，请注意，c 1 和c 2 是通过m a r r i e d t o 的婚姻关系联系起来的。 表1 2 分类的命题规则和关系规则表 ( t a b l e1 2p r o d o s l t l o n a lr u l ea n dr e l a t l o n a lr u l eo fc l a s s l f l c a t l o l l ) 命题规则 i fi n c o m e 1 0 8 0 0t h e nb i g s p e n d e r = y e s 关系规则 b i g s p e n d e r ( c 1 ，a g e l ，i n e o m e l ，t o t a l s p e n t l ) 一 m a r r i e d _ t o ( c 1 ，c 2 ) a c u s t o m e r ( c 2 ，a g e 2 ，i n c o m e 2 ，t o t a l s p e n t 2 ，b s 2 ) a i n c o m e 2 1 0 8 0 0 0 关系模式常用一阶逻辑谓词或者叫做关系逻辑的集合来表示。上例中的谓词 逻辑主要包括谓词m a r r i e d t o 和变量( e l ，c 2 ) ，这些在命题逻辑中并不出现。因 此，关系模式比命题模式更具表现力。 一般来说，一阶逻辑的程序设计子集同演绎数据库有密切联系，它是关系模 式的标准表述。例如，表1 2 中的关系规则就是逻辑程序子句。另外，关系数据 库中的关系与一阶逻辑谓词相一致。 传统数据挖掘用于多关系数据库的方法 多关系数据挖掘工具可以直接被应用到多关系数据中来寻找涵盖多张表的 关系模式。大部分其它的数据挖掘方法都假设数据存储于一张单表中，在应用之 前要进行预处理，以把不同表中的数据集成到一张单表中。然而，把不同表中的 数据通过连接或集合的方法集成到一张表中常会引起意义或信息的丢失。 假设我们有以下两种关系：c u s t o m e r ( c u s t l d ，n a m e ，a g e ，s p e n d s a l o t ) 和 p u r c h a s e ( c u s t i d ，p r o d u c t l d ，d a t e ，v a l u e ，p a y m e n t m o d e ) ，其中，每位顾客 都可以购买多于一件的物品，并且我们只对找出那些花大钱的顾客感兴趣。通过 自然连接，我们可以把这两个关系合并起来，生成关系p u r c h a s e l ，其中每行对 应一次购买而不是一位顾客；另一种可能的集成结果是表c u s t o m e r l ( c u s t l d ， a g e ，n o f p u r c h a s e s ，t o t a l v a l u e ，s p e n d s a l o t ) ，很显然，在这种集成方法的过 程中已经有一些信息完全丧失了 如果把关系c u s t o m e r 和p u r c h a s e - - 起考虑，就可以发现下面的模式： 贝叶斯方法用于多关系数据挖掘的研究 c u s t o m e r ( c i d ，n a m e ，a g e ，y e s ) + - a g e 3 0 p u r c h a s e ( c i d ，p i d ，d ，v a l u e ，p m ) a p m = c r e d i t c a r d a v a l u e 1 0 0 这个校式足说：如果一个人3 0 岁以上，并且他买了一件价值超过1 0 0 的物品， 并且他是用信用卡付的帐，那么他就是大主顾。若想从关系p u r c h a s e l 或表 c u s t o m e r l 中推出这个规则是绝不可能的。 除了能够直接处理存储在多张表中的数据，多关系数据挖掘系统通常能够考 虑到一般有效的背景( 领域) 知识，这些背景知识是作为逻辑程序已破告知的。 能够处理背景知识，并且对已发现的模式语言有强大的表现力，这两点是多关系 数据挖掘的特色之处。 一般来说，在单张表中发掘模式的数据挖掘方法被认为是属性值或命题的学 习方法，因为它发现的模式能用命题逻辑来表示。多关系数据挖掘的方法也被认 为是一阶学习的方法或关系学习的方法，因为它发现的模式能用一阶逻辑的关系 形式来表示。关于单表数据挖掘用于多关系数据库的方法及由此引发的问题，以 及多关系数据挖掘如何改善这些问题的细节讨论，可参见w r o b e l 的文献啊。 多关系数据挖掘的算法 多关系数据挖掘算法的目标是在一个给定数据库的关系模式语言中搜索有 效的模式。这里使用的搜索算法与用在单表数据挖掘中非常类似：你可以穷尽式 地搜索，也可以启发式地搜索( 包括贪婪算法，最佳优先算法等等) 。 就像许多传统的数据挖掘算法都是来自于机器学习领域，许多多关系数据挖 掘算法都是来自于i l p 领域o 。处于机器学习和逻辑程序设计的交界地，i l p 已 经涉足到寻找用逻辑程序来表示的模式。原先，i l p 的研究集中于从例子中自动 地合成p r o l o g 程序，然而近些年来，由于知识发现和数据挖掘的研究的兴起，i l p 的研究范围已经覆盖了整个数据挖掘的领域( 包括分类，回归，聚类，关联分析 等等) ，大部分一般的模式类型已经扩展到了相应的关系模式( 如关系分类规则， 关系回归树，关系关联规则) 中，并已有了主要的数据挖掘算法( 决策树归纳， 基于距离的聚类，预测等等) 。， v a nl a e r 和d er a e d t 嘲提出了将单表数据挖掘算法( 命题学习器) 升级到多 关系数据挖掘算法( 一阶学习器) 的一般性方法。他们的工作并不是无关紧要的。 扩展一些关键概念，比如说为多关系数据定义距离标准，需要相当的洞察力和刨 绪言 造力。效率也是非常重要的考虑因素，因为测试一个给定关系模式的有效性的运 算代价就已经很昂贵了，更不用说在模式空间中搜索有效模式了。另外一种多关 系数据挖掘的替换方法，叫做命题化( p r o p o s i t i o n a l i z a t l o n ) ，是用有条理的 系统分类方法( s y s t e m a t i c ) 来从多关系数据库中创建一张表。1 ，这种方法共享 一些有功效的特性，有一定的表现力。 模式语言通常由数量非常大的一些可能模式组成，甚至在单表情况下也一 样。而实际应用中，这个数目常会受到一些参数的限制( 比如，关联规则发掘中 常见项目集的最大数目) 。对于关系模式语言来说，可能模式的数目会更大，所 以需要提供更多明确的约束来限制可能模式的空间。这些约束通常会指定以下内 容：模式中应含盖哪些关系，怎样使关系变得相互关联，以及这个模式还需要遵 守哪些其它的语法约束。这样的明确模式语言说明( 或者是模式语言约束) 被称 为说明指标( d e c l a r a t i v eb i a s ) 嗍。 1 1 2 多关系数据挖掘的研究意义与研究范畴 如前所述，传统的数据挖掘方法一般是在数据库的一张单独的表里寻找模 式，遇到关系数据库时，则要把多张表里的数据强行挤压进一张表里，这里就产 生了问题，因为在这种方法的处理过程中，不光需要花费大量的心思和工夫，而 且还可能造成信息的丢失和数据的冗余。 虽然在原则上，多个关系表可以集成到一个单关系表中，但在实践中这一方 法存在许多问题。一般情况下，如果使用传统命题学习算法，组成一个关系数据 库的多个关系表就应集成到一个单关系表中，有如下两种方法实现这种集成嗍： ( 1 ) 在所有的关系上通过关系连接操作重构一个单一的泛关系，但这一方 法有许多潜在问题： 计算泛关系的时空代价异常大，最终得到的泛关系中存在大量冗余数 据。更为重要的是，整体数据量与原始数据比，异常的大，最糟情况下 最终数据量随数据库中原始关系数量与单一关系中元组数指数生长，这 样加剧了海量数据处理问题的难度。 在多对一关系形成的泛关系中，一个样例由多行组成，按照属性值学习 方法的每一行代表一样例的假定，结果会出现语义偏差。另外，对于涉 贝叶斯方法用于多关系数据挖掘的研究 及自连接的关系表，难以确定其连接深度。 如果将样例的所有信息放入结果关系的单一元组中，则对于复杂数据 库，一方面会出现大量空值属性，另一方面，确定结果关系的全部属性 非常困难。 数据重复导致统计偏差。 在许多问题上，属性值方法的学习效率非常低。 ( 2 ) 为避免冗余，可以在某些表上作聚合操作，所得聚合值代表这些表中 的信息加入一个核心关系表中，而这些表的原始元组不必被加入，但是仍有两个 问题： 许多细节信息在聚合操作后丢失了。 聚合属性的选择需要对问题域有良好的理解，如果理解出现错误，那么 与使用细节信息的情况相比，结果会较差。 以上原因直接推动了多关系数据挖掘研究的发展。有了多关系数据挖掘，我 们可以直接对多关系数据库中的数据进行分析，不需要第一步就把这些数据统统 挤压进一张表里。多关系数据挖掘方法不仅可以大大缩短知识发现的过程，也可 以提高算法的效率和准确率。 另外，数据挖掘算法研究的一个重要课题是如何行之有效地用于大型数据 库，在包含相对复杂模式的数据库中进行数据挖掘时，尤其应当注意算法的有效 性“。有些大型数据库中模式的搜索空间可能会非常大，以致于在这些数据库中 使用传统的数据挖掘算法几乎是不可能的。 现在大多数基于机器学习算法的经典的数据挖掘工具都只适用于属性值格 式的数据学习方法，在这种学习方法下，每一样例以属性值元组的形式表示，属 性种类是固定的，每个属性有一个给定的值相对应，从而整个数据集可以被视为 关系数据库中的一个表或关系，表中的每一行相应于一个样例，而每一列相应于 一个属性。 假设语言是命题逻辑语言，相应的命题以如下形式给出：“a t t r i b u t e 毋 v a l u e ”，其中的。是预先定义的操作符集合 v 1p a r e n t ( x ，y ) 。子句也被看成是文字 ( 1 i t e r a l s ) 的集合，其中每一个文字是原子或原子的否定。因此可把以上的子 旬设置成 f a t h e r ( x ，y ) ，m o t h e r ( x ，y ) ，- ip a r e n t ( x ，y ) ) 。 与完全( f u i l ) 子旬相比起来，肯定子句( d e f i n i t ec l a u s e s ) 在h e a d 部 分只能包含一个原子与肯定子句比较起来，程序子句( p r o g r a mc l a u s e s ) 在 b o d y 中也可包括否定原子。上段所示中的子句是完全子句，子句a n c e s t o r ( x ， 贝叶斯方法用于多关系数据挖掘的研究 y ) 一p a r e n t ( z ，y ) aa n c e s t o r ( x ，z ) 是肯定子句，它也是递规子句。子句 m o t h e r ( x ，y ) 一p a r e n t ( x ，y ) 八n o tm a l e ( x ) 是程序子旬。 子句的集合叫做子句理论( c l a u s a lt h e o r y ) 。逻辑稃序( l o g l cp r o g r a m ) 是程序子句的集合。h e a d 部分有相同谓词的程序子旬的集合叫做谓词定义 ( p r e d i c a t ed e f i n i t i o n ) 。大多数的i l p 方法学习谓词定义。 逻辑程序中的谓词对应于关系数据库中的关系。一个n - a r y 的关系p 形式上 定义为一个数组，也就是说，是n 个域d 1 d 2 x d n 的卡迪尔积的子集， 其中一个域( 或类型) 是一组数值。我们假定关系是有限的( f i n i t e ) 除非特别 声明。关系数据库( r d b ) 就是一组关系的集合。 因此，谓词对应于关系，谓词的主目语( a r g u m e n t ) ，即参数，对应于关系的 属性，主要的区别是关系的属性是类型限定的，也就是说每个域与每个属性相关 联。举例来说，在关系l i v e s i n ( x ，y ) 中，我们需要说明x 是人物类型，y 是城 市类型。数据库子句是类型限定的程序子句。 演绎数据库( d e d u c t i v ed a t a b a s e ：d d b ) 是一组数据库子句的集合。在演 绎数据库中，关系可以被扩展地定义为元组( t u p l e ) 的集合或严格地定义为数 据库子句的集合。数据库子句使用谓词主目语中的变量和函数符号，演绎数据库 语言比关系数据库语言更具有表现力。演绎d a t a l o g 数据库由不包含函数符号的 肯定数据库子句组成。 表3 1 数据库和逻辑程序的术语 ( t a b l e3 1d a t a b a s ea n dl o g i cp r o g r a m m i n gt e r m s ) 数据库术语逻辑程序术语 关系名p 关系p 的属性 元组 关系p 定义为元组的集合 关系q 定义为视图 谓词符号p 谓词符号p 的参数 基础事实p ( a l ，a n ) 谓词p 定义为基础事实的集合 谓词q 定义为规则( 子句) 的集合 3 1 2 关系规则归纳中i l p 的任务 作为一阶逻辑的子集，逻辑程序设计( l o g i cp r o g r a m m i n g ) 最关心的是演 绎推理( d e d u c t i v ei n f e r e n c e ) ，而归纳逻辑程序设计( i n d u c t i v el o g i c 多关系数据挖掘技术 p r o g r a m m i n g ) 关心的是归纳推理( i n d u c t i v ei n f e r e n c e ) 。有了背景知识，它 可以从个体实例( i n d i v i d u a li n s t a n c e ) 中总结和概括出来，旨在发现关于未 知实例的规律假定。 i l p 最一般的任务就是学习关系的逻辑定义“”，其中元组( 数组) 属不属于 目标关系是以实例的方式告知的。然后从训练实例中，i l p 归纳出逻辑程序( 谓 词定义) ，与根据其它关系( 作为背景知识已知) 所定义的目标关系的视图相一 致。这个经典的i l p 任务已经由深具开创性的m i s 系统”1 ( 被视为最有影响的 i l p 祖先) 和最有名的i l p 系统f o i l “”实现了。 已知一组实例，也就是说，数组属于目标关系p ( 肯定实例) 或不属于目标 关系p ( 否定实例) 已知。还知道背景关系( 背景谓词) q i ，q i 组成背景知识， 可用于学习定义p 。最后，指定关于p 定义的语法约束的假设语言也是己知的。 任务是找出一致( c o n s i s t e n t ) 和完善( c o m p l e t e ) 的目标关系p 的定义，也就 是说，解释所有的肯定的数组，而否定的数组全不作解释。 在形式上，已知一组实例e = p u n ，这里p 代表肯定实例，n 代表否定实 例，b 代表背景知识。我们的任务是找出假设h ，使得v e e p ：b a h _ e ( 此时， 我们说h 是完善的) ，v e p ，b a h 睁e ( 此时，我们说h 是一致的) ，这里， 卜代表逻辑隐含或推论。这种定义，是由m u g g l e t o n 洲引入的，所以也叫做限 定继承的学习方法( 1 e a r n i n gf r o me n t a i l m e n t ) 。d er a e d t 和d _ z e r o s k i “”提 出了另一种定义的方案，他们把条件b a h 卜e 换成了在b a e 的最小h e r b r a n d 模式中h 为真：这种设置被称为从解释( i n t e r p r e t a t i o n s ) 中学习的方法。 在大多数一般的公式中，每一个e ，b 和h 都可以是子句理论。实际上，每 一个e 最经常是背景实例( 元组) ，b 是关系数据库( 可以包括或不包括视图) ，h 是肯定逻辑程序。语义限定继承( ) 在实际中替换为句法约束继承( 卜) 或可证明 性，结论推论规则( r e s o l u t i o ni n f e r e n c er u l e ) 最经常被用来从假设和背景 知识中证明实例。在限定继承的学习方法中，如果一个肯定事实可以在由数据库 b 上的查询p _ b 所生成的h 的替换结果中出现，那么，我们就解释它，其中，h + _ b 是h 的子句。在从解释中学习的方法中，如果b 上的查询b a - 1h 为假，则h 的子句 h + - - b 在b 的最d , h e r b r a n d 模式上为真。 举个例子，看如表3 2 所示的这个i l p 任务，根据背景关系f e m a l e 和p a r e n t 贝叶斯方法用于多关系数据挖掘的研究 来定义关系d a u g h t e r ( x ，y ) ，用以说明x 人是y 人的女儿。这些关系包括目标关 系d a u g h t e r 的两个肯定和两个否定实例。 表3 2 一个简单的i l p 问题：学习女儿关系 ( t a b l e3 2as i m p l ei l pp r o b l e m ：l e a r n i n gd a u g h t e rr e l a t i o n ) 训练实例背景知识 d a u g h t e r ( m a r y ，a n n ) o d a u g h t e r ( e v e ，t o m ) o d a u g h t e r ( t o m ，a n n ) e d a u g h t e r ( e v e ，a n n ) e ( 肯定的实例用0 标注，否定的实例用e 标注) 在肯定程序子旬的假设语言中，用公式来表示下面的目标关系是可能的： d a u g h t e r ( x ，y ) * - f e m a l e ( x ) ，p a r e n t ( y ，x ) 这与背景知识和训练实例都是一致和完善的。 一般地，根据背景知识、假设语言和目标概念的复杂性，目标谓词的定义可 由一组子句组成，例如： d a u g h t e r ( x ，y ) + - f e m a l e ( x ) ，m o t h e r ( y ，x ) d a u g h t e r ( x ，y ) + - f e m a l e ( x ) ，f a t h e r ( y ，x ) 如果关系m o t h e r 和f a t h e r 替换关系p a r e n t 在背景知识中已知。 假设语言通常是程序子句语言的子集。随着假设语言的表现力日益增强，学 习的复杂性也变大了，需要在假设子句上加上约束。约束常是递规的排除 ( e x c l u s i