（计算机应用技术专业论文）约束归纳逻辑程序设计研究.pdf

摘要 竺= = ! ! ! ! 皇竺! 苎! 竺! ! ! ! ! ! = ! ! ! 暑暑毫! ! ! ! 竺兰! ! ! = ! = ! ! ! ! 竺苎! ! ! ! ! ! ：= = 墨! 竺 摘要 数据挖掘需要解决许多不同类型的问题。大多数数据挖掘方法针对的是传 统的单表形式的数据。然而，通常应用领域包含很多不同类型的实体( 多表) 。 对这样的数据的挖掘形成了关系数据挖掘研究领域。关系数据挖掘技术主要技 术之一是归纳逻辑程序设计( i n d u c t i v el o g i cp r o g r a m m i n g i l p ) 。 i l p 是机器学习与逻辑程序相交叉形成的研究领域，与传统机器学习方法 有所不同的是，l p 借助逻辑程序设计的理论与方法，利用背景知识学习一阶 规则。一阶规则较之基于属性值表示方式的命题级规则具有更强的表达能力。 随着i l p 开始应用于数据挖掘问题，成为关系数据挖掘的技术源泉，i l p 技术 研究的重要性更加显著。 由于以p r o l o g 作为表示语言，i l p 系统处理( 特别是实数域r 上的) 数值 量的能力较弱。而现实世界的数据中数值量又是经常出现的，这使得数值量的 处理问题成为将i l p 技术应用于数据挖掘的瓶颈。约束归纳逻辑程序设计 ( c o n s t r a i n ti n d u c t i v el o 西cp r o g r a m m i n g ，c i l p ) 是i l p 研究中较新的研究领 域，致力于解决i l p 中处理数值量的问题，即研究向数值约束方向扩充i l p ， 使得学习到的结果是约束逻辑程序( c o n s t r a i n tl o g i cp r o g r a m ，c l p ) 。 当前c i l p 技术的局限性主要表现在：一般只能导出不超过两个变量的约 束；考虑的约束形式比较简单，通常为线性约束；需要关于约束的附加的背景 知识( 预先给出约束构成的特征描述，如约束表达式的项数以及其中的若干常 数的值) ；导出约束的过程需要依赖约束求解器；很难处理不精确数值等。因 此，研究新的c i l p 技术具有重要的理论与实践意义。 当前经验式i l p 是i l p 研究的主流。经验式i l p 有两种主要技术：一般化 技术和特殊化技术，分别对应以自底向上的方式和以自顶向下的方式对假设空 间进行搜索。通过分析这两种i l p 技术的特点，本文选择特殊化技术( 自顶向 下的搜索) 作为研究c i l p 新技术的基础。 针对当前c i l p 技术的局限性，本文研究能够导出包含多个变量的多项式不 等式近似等式近似非等式约束的c i l p 新技术，并研制了一个自顶向下的c i l p 原型系统b p u c i l p 。b p u c i l p 系统采用b e a ms e a r c h 搜索策略，搜索的启发 函数为加权信息赢取。在对当前子句进行一步特殊化操作时，为导出候选约束， b p u c i l p 首先把当前子旬的绑定表投影到n 维实数空间对( h 为绑定表中数 值属性的个数) ，得到上若干标记为正，负的两类点。然后，b p u c i l p 引入 模式识别和多元统计分析中的方法，探测出若干实多项式约束，最后选择其中 些启发函数值较大的作为候选实多项式约束。 在本文c i l p 新技术的研究中，候选约束分为不等式约束和近似等式非等 北京工业大学工学博士学位论文 式约束两大类。本文首先从线性不等式约束入手，将多元数据分析和模式识别 研究领域中的f i s h e r 判别方法引入c i l p ，从而有效地导出线性不等式约束。在 此基础上，本文提出通过将数值数据转化成更高维空间的数据来推广导出线性 约束的方法，从而得到多种形式的多项式约束。其中在转化所得的高维空间上 导出线性约束时，本文提出将要导出的各种形式的约束的复杂度排序，从而使 算法易于导出形式简单的约束子旬。 在导出近似等式和非等式约束时，提出用动态聚类算法和主成分分析中的 方法导出近似线性等式约束，并简要介绍了与之相似的导出线性近似非等式约 束的方法。用在前面介绍的将数据转化为更高维数据的方法，可以得到导出多 项式近似等式非等式约束的方法。 基于本文的c i l p 新技术，本文初步实现了b p u c i l p 原型系统。实验表 明，本文提出的c i l p 新技术能够克服现有c i l p 方法的局限性，有效地处理不 精确数值，在不需要附加的背景知识、不依赖约束求解器的情况下，导出含多 个变量的多种形式的多项式约束，从而为关系数据挖掘提供了新的有力的技术 支持。 关键词数据挖掘：归纳逻辑程序设计；约束归纳逻辑程序设计；模式识别 多元统计分析 h a b s t r a c t a b s t r a c t t h ed e v e l o p m e n to fd a t am i n i n gm e t h o d s r e q u i r e s t h es o l u t i o no fs e v e r a l d i f f e r e n tt y p e so fp r o b l e m s m o s td a t am i n i n gm e t h o d sh a v eb e e nd e v e l o p e df o r d a t ai nt h et r a d i t i o n a ls i n g l e t a b l ef o r m h o w e v e r , t h ea p p l i c a t i o nd o m a i nc o n t a i n s s e v e r a l t a b l e s a i m i n g a td a t a m i n i n g o ns u c hd a t a , t h er e s e a r c ha r e an a m e d r e l a t i o n a ld a t a m i n i n g ( r d m ) e m e r g e d i n d u c t i v el o g i cp r o g r a m m i n g ( i l p ) i so n e o f t h em a j o r t e c h n i q u e so f r d m i l pi st h ea r e aa tt h ei n t e r s e c t i o no fm a c h i n el e a r n i n ga n dl o g i cp r o g r a m m i n g ， a i m i n g a tt h e s y n t h e s i s o f l o g i cp r o g r a m s f r o m e x a m p l e s a n d b a c k g r o u n d k n o w l e d g e d i f f e r e n tf o r mw h a tt y p i c a ld a t am i n i n gm e t h o d sd o ，i l pi n h e r i t st h e t h e o r ya n dm e t h o d so fl o g i cp r o g r a m m i n g ，t a k e si n t oa c c o u n tt h eb a c k g r o u n d k n o w l e d g ea n dl e a r n sf i r s to r d e rr u l e s f i r s to r d e rr u l e sa r em o r ee x p r e s s i v et h a nt h e a t t r i b u t e v a l u eb a s e dr u l e s a f t e rb e i n ga p p l i e di nd a t am i n i n ga n db e c o m i n gt h e r o o to fr e l a t i o n a ld a t am i n i n g ，t h er e s e a r c ho fi l ph a sb e e nm o r ea n dm o r e i m p o r t a n t w i t h i ni l pp a r a d i g m ，n u m e r i c a lr e a s o n i n gi sp o o r l yh a n d l e d ，w h i c hi si n h e r i t e d f r o mt h ec h o i c eo f l o g i cp r o g r a m a st h er e p r e s e n t a t i o nl a n g u a g e o nt h eo t h e rh a n d ， n u m e r i c a ld a t aa l w a y sa p p e a ri nr e a lw o r d ，w h i c hm a k e st h ep r o b l e mo fh a n d l i n g n u m b e rb e c o m et h eb o t t l e n e c ko f a p p l y i n g i l p t e c h n i q u e i nd a t a m i n i n g c o n s t r a i n ti n d u c t i v el o g i cp r o g r a m m i n g ( c l l p ) i sar e l a t i v en e wb r a n c hi ni l p , w h i c hf o c u s e so ns o l v i n gt h ep r o b l e mo f h a n d l i n gn u m b e ri ni l p , i e e x p a n d i n gi l p w i t ht h ed i m e n s i o no fn u m e r i cc o n s t r a i n t t h er e s u l tt h a tc i l pd e r i v e si sc o n s t r a i n t l o g i cp r o g r a m c u r r e n tc i l pm e t h o d sh a v es o m ea p p a r e n ts h o r t c o m i n g s ，s u c ha sc o n s i d e r i n g o n l yc o n s t r a i n t s w i t ht w ov a r i a b l e s , g e n e r a t i n go n l yl i n e a rc o n s t r a i n t s ，r e q u i r i n g a d d i t i o n a l b a c k g r o u n dk n o w l e d g e a b o u t c o n s t r a i n t s ( i e f i x i n g o nt h es o m e c h a r a c t e r so ft h ec o n s t r a i n t si na d v a n c e ，f o re x a m p l et h en u m b e ro ft e r m s i n c o n s t r a i n te x p r e s s i o n sa n dv a l u e so fs o m ec o e 舒c i e n to ft h o s et e r m s ) d e p e n d i n go i 1 p a r t i c u l a rc o n s t r a i n t ss o l v e ra n db e i n gi n c a p a b l et oh a n d l ei m p r e c i s ed a t a h e n c e ，i t i so fg r e a tt h e o r e t i c a la n da p p l i e ds i g n i f i c a n c e t od or e s e a r c ho nn e wc i l p t e c h n i q u e t h em a i n s t r e a mo fi l pi s s o c a l l e d e m p i r i c a l i l eg e n e r a l i z a t i o n a n d s p e c i a l i z a t i o na r et w ob a s i ct e c h n i q u e so fe m p i r i c a li l ps y s t e m s ，a n dt h e f o r m e r s e a r c ht h eh y p o t h e s i ss p a c ew i t ht h eb o t t o m - u pm a l l n e rw h i l e t h el a t t e rd o e si tw i t h t h et o p d o w nm a n r t e r t h ea u t h o ra n a l y z e st h ep r o p e r t i e so f t h et w ob a s i ct e c h n i q u e s i i i 北京工业大学工学博士学位论文 a n ds e l e c t st h es p e c i a l i z a t i o nt e c h n i q u ea st h ef o u n d a t i o no f t h er e s e a r c ho nn e w c i l p t e c h n i q u e a i m i n ga to v e r c o m i n gt h es h o r t c o m i n g so fc u r r e n tc i l p t e c h n i q u e s ，t h i sp a p e r p r o p o s e sn e w c i l p t e c h n i q u e ，w h i c hc a ng e n e r a t ep o l y n o m i a li n e q u a t i o n s ，i n e x a c t e q u a t i o n sa n di n e x a c td i s e q u a t i o n si ns e v e r a ld i m e n s i o n s t h e n ，t h ea u t h o rd e s i g n s at o p d o w n ( r e f i n e m e n tb a s e d ) p r o t o t y p eo fc i l ps y s t e m ，n a m e db p u c i l p , i n w h i c ht h es e a r c hs t r a t e g yi sb e a ms e a r c ha n dt h eh e u r i s t i ct oa d da l i t e r a lt oc u r r e n t c l a u s ei sw e i g h t e di n f o r m a t i o ng a i n i no n e s t e ps p e c i a l i z a t i o no f c u r r e n tc l a u s e ，t o g e n e r a t ec a n d i d a t ec o n s t r a i n t s ，b p u c i l pf i r s tp r o j e c t st h eb i n d i n gt a b l eo fc u r r e n t c l a u s et o 月- d i m e n s i o n a lr e a ls p a c e r n ( w h e r e ni st h en u m b e ro fn u m e r i c a la t t r i b u t e s o ft h eb i n d i n gt a b l e ) ，w h i c h p r o d u c e ss o m ep o i n t sl a b e l e da sp o s i t i v ea n dn e g a t i v e i n t h e n b p u c i l pi n t r o d u c e sm e t h o d sf r o mp a t t e r n r e c o g n i t i o n a n d m u l t i v a r i a t es t a t i s t i c a l a n a l y s i st o d e t e c ts e v e r a lr e a lp o l y n o m i a lc o n s t r a i n t s ，a n d s e l e c tf r o mt h e ms o m e o p t i m a l o n e sa st h ec a n d i d a t ec o n s t r a i n t s t o g e n e r a t e c a n d i d a t ec o n s t r a i n t s ，t h ea u t h o rs t a r t sf r o m g e n e r a t i n g l i n e a r i n e q u a t i o n s ，a n dp r o p o s e st oi n t r o d u c e f i s h e r sl i n e a rd i s c r i m i n a n tt oc i l p i nt h i s w a y , t h el i n e a ri n - e q u a t i o n sc a nb eg e n e r a t e de f f i c i e n t l y f u r t h e rm o r e ，t h ea u t h o r p r o p o s e s t ot r a n s f o r mt h eo r i g i n a lp o i n t st oh i g h e r - d i m e n s i o n a lp o i n t s ，a n dt h e n g e n e r a l i z et h em e t h o d s f o rl i n e a rc o n s t r a i n t st og e n e r a t ep o l y n o m i a lc o n s t r a i n t s f o r t h ep u r p o s eo f g e n e r a t i n gs i m p l ec o n s t r a i n t sm o r el i k e l y , t h ea u t h o r a l s op r o p o s e st o s o r tt h ec o m p l e x i t i e so fc o n s t r a i n t st ob eg e n e r a t e d b e f o r ep r e s e n t i n gt h em e t h o dt og e n e r a t ei n e x a c te q u a t i o n sa n dd i s e q u a t i o n s ， t h ea u t h o ri n d i c a t e st h a ti ti sd i m c u l tf o rc u r r e n tm e t h o d st h a ta i ma tg e n e r a t i n g e x a c te q u a t i o n sa n dd i s 。e q u a t i o n st oh a n d l eal a r g en u m b e ro fh i g h e r d i m e n s i o n a l i m p r e c i s ed a t at h a to f t e na p p e a r i nr e a lw o r l d t h e nt h ea u t h o rp r o p o s e st og e n e r a t e i n e x a c tl i n e a r e q u a t i o n s w i t ht h em e t h o d so fd y n a m i cc l u s t e r i n ga n dp r i n c i p a l c o m p o n e n ta n a l y s i s t h em e t h o d t og e n e r a t ei n e x a c tl i n e a rd i s e q u a t i o n si ss i m i l a r t ow h i c ht og e n e r a t ei n e x a c tl i n e a re q u a t i o n s a l s o ，w i t ht h em e t h o dt r a n s f o r m i n g o r i g i n a l d a t at o h i g h e r - d i m e n s i o n a l d a t a , b p u c i l p c a n g e n e r a t e i n e x a c t p o l y n o m i a le q u a t i o n s a n d d i s e q u a t i o n s w i t ht h en e w t e c h n i q u ed e s c r i b e da b o v e ，t h ea u t h o ri m p l e m e n t s a p r o t o t y p eo f b p u c i l ps y s t e m e x p e r i m e n t s o nb p u c i l ps h o wt h a t t h en e wt e c h n i q u e o v e r c o m e ss o m es h o r t c o m i n g so f c u r r e n tc i l pt e c h n i q u e s ，i tc a nh a n d l ei m p r e c i s e d a t aw e l la n dg e n e r a t ee f f i c i e n t l ys e v e r a lk i n d so fp o l y n o m i a lc o n s t r a i n t so f s e v e r a l d i m e n s i o n s ，w i t h o u tn e e do f a d d i t i o n a lb a c k g r o u n dk n o w l e d g ea n dc o n s t r a i n ts o l v e r h e n c e ，t h en e wc i l pt e c h n i q u ep r e s e n t e d i nt h i sp a p e rc a np r o v i d er e l a t i o n a ld a t a m i n i n g w i t hn e w , s t r o n g e rt e c h n i c a ls u p p o r t i v a b s n a 就 k e yw o r d sd a t am i n i n g ；i n d u c t i v el o g i cp r o g r a m m i n g ；c o n s t r a i n ti n d u c t i v e l o g i cp r o g r a m m i n g ；p a t t e r nr e c o g n i t i o n ；m u l t i v a r i a t es t a t i s t i c a la n a l y s i s v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：整日期：兰! ! 垒：至：1 2 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名：塑叠导师签名日期：2 翌生：至：i 第1 章绪论 第1 章绪论 由于计算机数据采集工具以及关系数据库技术的发展，目前各行业存储了大 量的数据。传统的数据分析手段难以应付，导致越来越严重的数据灾难，迫使决 策者出现或是穷于应付，或是置之不理的事实。关系数据库提供的简单查询及报 表生成功能，只能获得数据的表层信息，而不能获得数据属性的内在关系和隐含 的信息，即淹没了包含的知识，造成了资源的浪费。【i j 为了使消耗大量财力与物力所收集与整理的宝贵数据资源得以利用，有效解 决数据丰富性及知识贫乏性的矛盾，需要新技术智能、自动地分析处理原始数据， 促使了数据库中的知识发现( 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 ) 和数据挖 掘( d m ，d a t am i n i n g ) 技术的出现。 1 1 数据挖掘 数据挖掘就是对观测到的数据集( 经常是很庞大的) 进行分析，目的是发现 未知的关系和以数据拥有者可以理解并对其有价值的新颖方式来总结数据。【2 】 通过数据挖掘过程所推导出的关系和摘要经常被称为模型( m o d e l ) 或模式 ( p a t t e m ) 。 1 1 k d d 与数据挖掘 在k d d 9 6 国际会议上，f a y y a d ，p i a t e t s k y s h a p i r o 和s m y t h 对k d d 作了如 下描述：k d d 是从数据库中获取正确、新颖、有潜在应用价值和最终可理解的 模式的非平凡过程。在这个描述中，“数据”是一系列事实的集合，“模式”是 指用语言上来表示的一个表达式e ，它可用来描述数据集的特性，e 所描述的数 据是集合f 的一个子集民。“过程”是在k d d 中包含的步骤，如数据的预处理、 模式搜索、知识表示及知识评价等。“非平凡”是指它已经超越了一般封闭形式 的数量计算，而将包括对结构、模式和参数的搜索i l l 。 现在一般认为k d d 是一个综合的过程，它包括数据录入、迭代求解、用户 交互以及许多定制要求和决策设计等，而数据挖掘只是k d d 中的一个具体却是 关键的步骤。“数据库中的知识发现”术语在1 9 8 9 年的第一届k d d 专题讨论会 上被首次采用，它强调了知识是数据发现的最终产品。图( 1 - 1 ) 示出了k d d 的一 般步骤，从中可以看到数据挖掘与k d d 的关系。 北京工业大学工学博士学位论文 日 数据源 1 1 2 数据挖掘任务 图卜1k d d 过程 f i g u r e1 - 1t h e k d dp r o c e s s 数据挖掘的任务一般可分为：数据总结、关联分析、时序模式、聚类、分类、 偏差检测、预测。”“ 1 数据总结 数据总结的目的是对数据进行浓缩，给出它紧凑的描述。传统的也是最简单 的数据总结方法是计算数据的和、平均值、方差等统计值，或者用直方图、饼状 图等图形方式表示。数据挖掘主要关心从数据泛化的角度来来讨论数据总结。数 据泛化目前主要有两种技术：多维数据分析方法和面向属性的归纳方法e 2 关联分析 关联分析是从数据库中发现知识的一类重要方法。若两个或多个数据项的取 值之间重复出现且概率很高时，它就存在某种关联，可以建立起这些数据项的关 联规则。在大型数据库中，这种关联规则是很多的，需要进行筛选，一般用“支 2 第l 章绪论 持度”和“可信度”两个阈值来淘汰那些无用的关联规则。 3 时序模式 通过时间序列搜索出重复发生概率较高的模式。这里强调时间序列的影响。 在时序模式中，需要找出在某个最小时间内出现比率一直高于某一最小百分比 ( 阈值) 的规则。 4 聚类 数据库中的数据可以划分为一系列有意义的子集，即类。在同一类别中，个 体之间的距离较小，而不同类别上的个体之间的距离偏大。聚类增强了人们对客 观现实的认识，即通过聚类建立宏观概念。 聚类方法包括统计分析方法，机器学习方法，神经网络方法等。在统计分析 方法中，聚类分析是基于距离( 如欧氏距离，海明距离等) 或相似性度量的聚类。 这种聚类分析方法是一种基于全局比较的聚类，它需要考察所有的个体才能决定 类的划分。在机器学习方法中，聚类是无监督的学习。在这里距离是根据概念的 描述来确定的，故聚类也称概念聚类，当聚类对象动态增加时，概念聚类则称谓 概念形成。在神经网络中，自组织神经网络方法用于聚类。 5 分类 分类是数据挖掘中应用的最多的任务。分类是找出一个类别的概念描述，它 代表了这类数据的整体信息，即该类的内涵描述。一般用规则或决策树模式表示。 分类函数或分类模式( 也常常称作分类器) 能把对象映射到给定类别中的某一个。 分类器的构造方法有统计方法、机器学习方法、神经网络方法等。统计方法 包括贝叶斯法和非参数法，对应的知识表示为判别函数和原型事例。机器学习方 法包括决策树法和规则归纳法，前者对应的表示为决策树或判别树，后者则一般 为产生式规则。神经网络方法主要是b p 算法，它的模型表示是前向反馈神经网 络模型，它的本质是一种非线性判别函数。现实世界的数据的不精确性、不确定 性和不完备性是影响分类算法的性能的重要因素。 6 偏差检测 偏差检测致力于通过数据数据分析，发现数据中存在的异常情况。偏差检测 的基本方法是寻找观察结果与参照之间的差别。观察常常是某一个域的值或多个 域的值的汇总。参照是给定模型的预测、外界提供的标准或另一个观察。 7 预测 预测是利用历史数据找出变化规律，建立模型，并用此模型来预测未来数据 的种类，特征等。典型的方法是回归分析，即利用大量的历史数据，以时间为变 量建立线性或非线性回归方程。预测时，只要输入任意的时间值，通过回归方程 就可求出该时间的状态。近年来发展起来的神经网络方法实现了非线性样本的学 习，能进行非线性函数的判别。分类和回归都可以用于预测，不同点在于：分类 北京工业大学工学博士学位论文 = ! = = = = ! ! ! ! ! ! ! ! = s = = = = ! ! ! ! = ! = ! ! ! ! 输出的是离散的类别值，而回归输出的则是连续值。 1 1 3 数据挖掘方法和技术 数据挖掘方法是由人工智能、机器学习的方法发展而来，结合传统的统计分 析方法、模糊数学方法、粗集方法以及科学计算可视化技术等，以现实世界的数 据为研究对象，形成了数据挖掘方法和技术。当前的数据挖掘方法和技术主要有 以下几种“。5 1 。 1 决策树方法 决策树方法利用信息论中的互信息( 信息增益) 寻找数据库中具有最大信息 量的字段，建立决策树的一个结点，再根据字段的不同取值建立树的分支：在每个 分支子集中，重复建立树的下层结点和分支的过程，即可建立决策树。 2 神经网络方法 神经网络方法模拟了人脑神经元结构，以m p 模型和h e b b 学习规则为基础， 建立了前馈式网络、反馈式网络、自组织网络三类神经网络模型。神经网络的知 识体现在网络连结的权值上，是一个分布式矩阵结构。神经网络的学习体现在神 经网络权值的逐步计算上( 包括反复迭代或者是累加计算) 。 3 遗传算法 遗传算法是模拟生物进化过程的算法。它由繁殖繁殖( 选择) 交叉( 重组) 变异( 突变) 三个基本算子组成：遗传算法中产生的后代需要满足适应值，经过 若干代的遗传，得到满足要求的后代( 问题的解) 。遗传算法已在优化计算和分 类机器学习方面发挥了显著的效果。 4 覆盖正例排斥反例方法 覆盖正例排斥反例方法是利用覆盖所有正例、排斥所有反例的思想来寻找规 则。首先在正例集合中任选一个种子，到反例集合中逐个比较。与字段取值构成 的选择子相容则舍去，相反则保留。按此思想循环所有正例种子，将得到正例的 规则( 选择子的合取式) 利用覆盖所有正例排斥所有反例的思想来寻找规则。 5 模糊数学方法 模糊数学方法利用模糊集合理论对实际问题进行模糊评判、模糊决策、模糊 模式识别和模糊聚类分析。系统的复杂性越高，精确能力就越低，模糊性就越强。 这是z a d e h 总结出的互克性原理。模糊集是表示和处理不确定数据的重要方法。 模糊集不仅可以处理不完全数据、噪音和不精确数据，而且在开发数据的不确定 性模型方面是有用的，能提供比传统的方法更灵巧、更平滑的性能。 6 粗集( r o u g h s e t ) 方法 在数据库中将行元素看成对象，将列元素看成属性( 分为条件属性和决策属 4 第1 章绪论 ! ! ! ! ! = ! 毫! 竺! 暑! ! ! 鼍! ! 竺竺皇竺= = = = 詈! 竺! ! ! ! ! = ! ! 暑皇! 暑! ! 竺= = = = ! ! ! 性) 。等价关系r 定义为不同对象在某个或几个属性上取值相同，满足等价关系的 对象组成的集合被称为等价关系r 的等价类。条件属性上的等价类e 与决策属 性上的等价类j ，之间的关系分三种情况： ( 1 ) 下近似：f 包含e 。对下近似建立确定性规则。 ( 2 ) 上近似：y 和e 的交非空。对上近似建立不确定性规则( 含可信度1 。 ( 3 ) 无关： r 和e 的交为空。无关情况不存在规则。 7 公式发现 公式发现在工程和科学数据库( 由实验数据组成) 中对若干数据项( 变量) 进行一定的数学运算，求得相应的数学公式。b a c o n 是公式发现的代表系统， 它的基本思想是对数据项进行初等数学运算( 加、减、乘、除等) 形成组合数据 项，若它的值为常数项，就得到了组合数据项等于常数的公式。 8 统计分析方法 在数据库字段项之问存在两种关系：函数关系( 能用函数公式表示的确定性关 系) 和相关关系( 不能用函数公式表示，但仍是相关确定性关系) ，统计分析方法利用 统计学原理对数据库中的数据进行分析，主要有相关分析、回归分析、主成分分 析、因子分析、判别分析、聚类分析等。 9 可视化技术 可视化数据分析技术拓宽了传统的图表功能，使用户对数据的剖析更清楚。 例如把数据库中多维的数据变成多种图形，这对于揭示数据中的状况，内在本质 以及规律性起到很强的作用。 1 0 贝叶斯网络( b a y e s i a n n e t w o r k s ) 方法 贝叶斯网络是描述数据变量之间依赖关系的一种图形模式，是一种用来进行 推理的模型。贝叶斯网络提供了一种方便的框架结构来表示因果关系，这使得不 确定性推理变得在逻辑上更为清晰、可理解性强。贝叶斯网络由以下两部分组成： ( 1 ) 贝叶斯网络结构贝叶斯网的网络结构是一个有向无环图( d i r e c t e d a c y c l i cg r a p h ) ，其中每个结点代表一个属性或者数据变量，结点问 的弧代表属性( 数据变量) 间的概率依赖关系。 ( 2 ) 条件概率表贝叶斯网络中的条件概率表是结点的条件概率的集合。 当使用贝叶斯网络进行推理时，实际上是使用条件概率表当中的先验 概率和已知的证据结点来计算所查询的目标结点的后验概率的过程。 1 1 归纳逻辑程序设计( i n d u c t i v el o g i cp r o g r a m m i n g ，i l p ) 归纳逻辑程序设计是由机器学 习( m a c h i n el e a m i n g ) n i 翌_ 辑程序设计( l o g i c p r o g r a m m i n g ) 发展并结合所形成的一个研究领域。与传统数据挖掘方法不同， i l p 借助逻辑程序设计的理论与方法，利用背景知识发现一阶规则。一阶规则较 之基于属性一值表示方式的规则具有更强的表达能力，使归纳结论内涵更加丰富 北京工业大学工学博士学位论文 5 1 1 1 = ! ! ! ! ! ! ! ! ! ! = 2 = ! ! = ! ! ! = = ! !：! ： 和精确。以归纳逻辑程序设计为核心技术形成的数据挖掘研究领域称为关系数据 挖掘( r e l a t i o n a ld a t a m i n i n g ) 。 1 2 研究约束归纳逻辑程序设计技术的意义 数据挖掘方法的发展需要解决许多不同类型的问题。数据可能有很大的维 数，导致考虑所有的变量不可行；数据集中可能包含海量的数据，因此只能对其 中有限的数据进行分析；数据可能来自一个我们知之甚少的领域，于是就几乎没 有可以利用的背景知识，因此很难选择合适的模型；有时可用的背景知识又很多， 忽略了这些背景知识的数据挖掘方法很难成功。 大多数数据挖掘方法针对的是传统的矩阵形式的数据( 即单表数据) ，矩阵 的行表示对象，列表示变量。这种统计学中传统的数据表示方法有很多优点，例 如用矩阵运算可以非常方便地表达很多数据分析过程，这使得矩阵形式的数据表 达对设计高效的数据挖掘算法非常有利。 然而，现实世界中矩阵形式的数据很少。通常应用领域包含很多不同类型的 实体，而每类实体中又包含不同类型的数据( 即多表数据) 。对这样的数据的大 规模的研究还是最近才出现的，该研究领域被称为关系数据挖掘( r e l a t i o n a ld a t a m i n i n g ，r d m ) 1 6 1 。 关系数据挖掘研究从包含不同类型实体信息的数据库中发现知识的方法，这 里的数据库就是通常的包含多个表的数据库。因此关系数据挖掘领域的研究具有 很强的实用性。 关系数据挖掘的主要技术之一是归纳逻辑程序设计( 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 l p ) 。i l p 方法使用逻辑程序设计语言，从多关系的数据中学习出 有效的模式，其中逻辑程序设计语言( 如p r o l o g ) 是一阶谓词演算的子集。关系 数据库的形式体系一关系代数，也是一阶逻辑的子集。逻辑程序设计领域和数据 库领域术语之间的关系是：一个谓词对应一个关系：谓词的变元对应关系的属性； 由视图定义的关系对应谓词的内涵式定义。在这种背景下，术语“关系学习”、 “关系数据挖掘”和i l p 是相同的概念。 i l p 是机器学习与归纳逻辑程序相交叉形成的研究领域”1 ，它致力于从例子 和背景知识中导出逻辑程序。i l p 的这个基本的任务可以被看作概念学习( 导出 二值分类器) ，也可看作学习关系的逻辑( 内涵) 定义。与传统机器学习方法有 所不同的是，i l p 借助逻辑程序设计的理论与方法，利用背景知识学习一阶规则。 一阶规则较之基于属性值表示方式的规则具有更强的表达能力，使归纳结论内 涵更加丰富和精确。因此i l p 有能力克服存在于传统机器学习中的两个主要限 制，即知识表示机制的限制与学习中背景知识利用的限制悼。i l p 的研究不但 6 第1 章绪论 为机器学习提供深入的理论与方法，也为知识工程等人工智能的应用领域提供新 的强有力的技术支持，因而i l p 成为机器学习的前沿研究课题7 1 。随着i l p 开始 应用于数据挖掘问题，随着近年来关系数据挖掘技术成功应用不断出现哺3 ，i l p 技术的适用范围被大大拓宽了。作为关系数据挖掘的技术源泉之一，i l p 技术研 究的重要性更加显著。 i l p 研究领域形成于二十世纪九十年代，它继承了逻辑程序设计的坚实的理 论基础，继承了机器学习的实验的方法和面向实际应用的方向，在研究上和应用 上都取得了丰硕的成果【1 1 , 1 2 1 。然而，i l p 领域仍然有一些问题有待于深入地研究 和探讨【l ，其中数值量的处理问题显得尤为突出。由于以p r o l o g 作为表示语言， i l p 系统处理数值量的能力较弱。而现实世界的数据中数值量又是经常出现的， 这使得数值量的处理问题成为将i l p 技术应用于数据挖掘的瓶颈。 约束归纳逻辑程序设计( c o n s t r a i n ti n d u c t i v el o g i cp r o g r a m m i n g ，c i l p ) 是 i l p 研究中较新的研究领域 1 4 - 1 8 1 ，致力于解决i l p 中处理数值量的问题，即研究 向约束方向扩充i l p ，使得学习到的结果是约束逻辑程序( c o n s t r a i n tl o g i c p r o g r a m ，c l p ) 【”1 。 当前c i l p 技术的局限性主要表现在：一般只能导出不超过两个变量的约束； 考虑的约束形式比较简单，通常为线性约束：需要关于约束的附加的背景知识( 给 出过强的语言偏向) ，即预先给出约束构