（计算机应用技术专业论文）统计关系学习若干问题研究.pdf

摘要 摘要 统计关系学习是人工智能领域的一个新研究热点，其目的是在多关系的数据 集中挖掘出数据中的统计关系模型。统计关系学习是集关系、逻辑表示，似然推 理机制，机器学习、数据挖掘于一体。现有的统计关系学习，大多数似然关系模 型下的研究都是基于完备数据条件下进行的，而现实问题中，数据通常是不完备 的。同时也由于不完备的关系数据问题非常复杂，因此传统的机器学习领域中处 理不完备数据的学习的方法，也很难直接应用到统计关系学习中。因此解决从不 完备数据中学习统计关系模型的问题是非常必要的。 在传统的机器学习方法中，数据通常以“属性一值”的方式存在，即表示为 单表形式。但在现实世界中，许多数据都存在着内部关系，即表示为多表形式的 关系数据。因此，该问题不满足传统机器学习中普遍要求的独立同分布假设。在 此类数据的样本之间或者样本的属性之间，往往存在着内在的关系或结构。由于 关系数据的表示形式与“属性一值”的形式截然不同，传统的基于“属性一值” 表示的机器学习技术难以用于解决这类问题。于是，统计关系学习这一研究领域 应运而生，并且受到了越来越多研究者的重视。 似然关系模型( p r o b a b i l i s t i er e l a t i o n a lm o d e l s ，p r m ) 是一类基于贝叶斯网 ( b a y e s i a n ) 的统计关系学习方法，它是标准贝叶斯网模型的扩展，p r m 使用表 示实体间关系的实体关系模型( e n t i t yr e l a t i o n s h i pm o d e l ，e r ) 作为基本的表示 框架，将p r m 看成是描述关系型数据库上概率分布的模板 9 】。模型的结构描述 关系模式及属性间的依赖，模板的参数定义对象属性依赖关系的概率分布。于是， 该模型除了能使用概率进行表示和不确定推理外，还可以处理关系数据，具有更 强的表达能力，可以用来在复杂的系统上建模，这对智能信息系统的开发研究有 着特别重要的意义。 g d t ( g e n e r a l i z a t i o nd i s t r i b u t i o nt a b l e ) 的方法，描述了属性值的所有组合 可能情况，对实例的所有泛式的可能概括，以及实例与其泛式间的概率分布。同 时g d t 方法，通过概括强度、规则置信度和规则强度，充分考虑到数据的不完 整性，并可以把背景知识，背景知识的先验概率自然得用于学习过程。目前， g d t 的思想在处理不完备数据的完备化问题中，缺省数据规则发现，应用背景 知识对已有不完备数据进行优化学习一阶规则等方面已经有了广泛的应用。所以 g d t 的方法能够很高的解决不完备数据完备化的问题。 现有的关系学习研究大多是基于完备数据进行的，而现实问题中，数据通常 是不完备的。在传统的机器学习领域中，从不完备数据中学习的问题已经得到了 研究，但不完备的关系数据问题非常复杂，因此，几乎没有任何一项技术可以直 接被扩展到关系学习领域。传统的机器学习算法可以被看成是数据集中仅有的一 北京丁业大学t 学硕f ：学位论文 个表，并且不存在关系的学习算法。例如，b a y e s i a n 网络可以看成是仅包含一 个属性类，并且不存在关系的p r m 。因此，p r m 结构学习的复杂度至少相当于 b a y e s i a n 网络学习的复杂度。由于具有多个局部极值，如果将传统的机器学习 中处理不完备数据问题的算法直接扩展到关系学习中，学习的复杂度将会明显提 高，并且会得到较差的结果。因此，从不完备的关系数据中学习是关系学习领域 中一个重要的、有待解决的问题。 在此基础上本文主要完成了以下工作：本文提出了一种基于g d t 的从不完 备关系数据中学习似然关系模型p r o b a b i l i s t i cr e l a t i o n a lm o d e l s ，简称p r a m s ) 的方 法。该方法首先使用g d t 技术来对缺失数据进行预处理，填充不完备关系数据 得到完备关系数据；然后从通过g d t 填充的数据样本中，采用启发式搜索方法 学习得到似然关系模型并作为初始p r m 网络，并利用学习过程中前一步得到的 网络结构中的规则强度形式的一节规则对数据集进行重优化：直到学习得出概率 关系模型。 本文分别在一个模拟问题和一个真实问题域上进行了实验讨论。在模拟的 s c h o o l 问题域上，生成具有5 0 0 0 个数据样本的4 个数据集。分别在具有1 0 ， 2 0 ，3 0 ，4 0 的丢失数据这4 个数据集上进行测试。在真实的m o v i e 域问题 上，我们在数据库中选出了一个含有5 0 0 0 个m o v i e 、3 0 0 0 个a c t o r 和1 5 0 0 个 d i r e c t o r 的子集。 由于现存的放法中几乎没有从不完备数据中学习p r m s 的方法，因此，实验 中用于比较的方法是先随机填充不完备数据，然后开始学习得到p r m s 的方法。 基于g d t 的方法填充不完备关系数据并得到完备的关系数据，然后，算法通过 将进化过程中最好的网络结构嵌入到不完备数据集中，有效地修复噪声数据。随 着迭代的进行，修正的数据越来越好，数据趋于稳定并最终收敛。通过实验我们 发现基于g d t 的这种学习似然关系模型的方法，能够很有效的对不完备数据进 行预处理，得到基于g d t 的完备数据。将g d t 的方法应用到统计关系学习p r m s 的网络构造中，并且能够从不完备数据中学习到一个较好的模型结构。并且通过 反复的迭代过程产生的冗余边也是比较少的。因此这种方法对统计关系学习具有 一定得理论意义和现实价值。 关键词统计关系学习；g d t ；不完备数据；概率关系模型( p r m s ) i i a b s t r a c t a b s t r a c t s t a t i s t i c a lr e l a t i o n a l l e a r n i n g ( s r l ) ，i n t e g r a t i n gt h er e l a t i o n a l o rl o g i c a l r e p r e s e n t a t i o n ，p r o b a b i l i s t i cr e a s o n i n gm e c h a n i s m sw i t i lm a c h i n el e a r n i n ga n dd a t a m i n i n gp r i n c i p l e st oo b t a i nt h ep r o b a b i l i s t i cm o d e li nt h em u l t i - r e l a t i o n a ld a t a ，i sa h i g h l i g h ti na 1r e s e a r c hf i e l d e x i s t i n gr e l a t i o n a ll e a r n i n ga p p r o a c h e su s u a l l yw o r ko n c o m p l e t er e l m i o n a ld a t a h o w e v e r , i nr e a l w o r l da p p l i c a t i o n s ，d a t aa r eo f t e n i n c o m p l e t e a n da st h ec o m p l e x i t yo ft h ei n c o m p l e t er e l a t i o n a ld a t a , t h et r a d i t i o n a l m e t h o dc o u l dn o ts o l v et h i sp r o b l e mp e r f e c t l y s ot h ea p p r o a c ho fs o l v i n gt h i s p r o b l e mi sv e r yi m p o r t a n t i nt r a d i t i o n a lm a c h i n el e a r n i n gm e t h o d s ，d a t ai su s u a l l y ”a t t r i b u t e v a l u e o ft h e w a y , i tm e a n st h a tt h ef o r mo fas i n g l et a b l e b u ti nt h er e a lw o r l d ，t h e r ea r em a n yd a t a 晰mr e l a t i o n s h i p s ，i tm e a n st h a tt h ef o r mo fm u l t i r e l a t i o n a ld a t at a b l e s t h e r e f o r e ，t h e i s s u ed o e sn o tm e e tt h et r a d i t i o n a lr e q u i r e m e n t so fm a c h i n el e a r n i n gi ng e n e r a lt h e a s s u m p t i o no fi n d e p e n d e n ta n di d e n t i c a l l yd i s t r i b u t e d s u c hd a t ao f t e ne x i s ti n h e r e n t s t r u c t u r e s a se n t i r ed i f f e r e n c e sb e t w e e nt h er e l a t i o n s h i p d a t a ，a n dt h ef o r mo ft h e a t t r i b u t e - v a l u e ，t h et r a d i t i o n a lm a c h i n el e a r n i n gt e c h n o l o g yb a s e do nt h e a t t r i b u t e v a l u e ”t h a tc a l lh a r d l yb e u s e di nr e s o l v i n gs u c hp r o b l e m s t h u s ，t h es t a t i s t i c a l r e l a t i o n s h i pb e t w e e nt h el e a r n i n go ft h i sr e s e a r c hc a m ei n t ob e i n g ，a n dr e s e a r c h e r s h a v eb e e nm o r ea n dm o r ea t t e n t i o n p r o b a b i l i s t i cr e l a t i o n a lm o d e l s ( p r m ) i sal ( i n do fb a y e s i a nn e t w o r k b a s e d s t a t i s t i c a lr e l a t i o n a ll e a r n i n gm e t h o d i ti sas t a n d a r de x t e n s i o no ft h eb a y e s i a n n e t w o r km o d e l ，p r mu s et h ee n t i t yr e l m i o n a lm o d e la st h ef r a m e w o r kt od e n o t et h e r e l a t i o n s h i po ft h ee n t i t y t h u s ，t h em o d e li na d d i t i o nt ot h eu s eo fp r o b a b i l i t ya n d u n c e r t a i n t yt h a tr e a s o n i n g ，a n da l s o c a nd e a lw i t hr e l a t i o n a ld a t a ，嘶t hs t r o n g e r c o m m u n i c a t i o ns k i l l s ，c a nb eu s e di nc o m p l e xs y s t e m sm o d e l i n g ，i n t e l l i g e n t i n f o r m a t i o ns y s t e m sf o rr e s e a r c ha n dd e v e l o p m e n to fas p e c i a li m p o r t a n c e 。 n l eg d t ( g e n e r a l i z a t i o nd i s t r i b u t i o nt a b l e ) b a s e da p p r o a c hf o rr u l e sd i s c o v e r y f r o mi n c o m p l e t ei n f o r m a t i o ns y s t e m si sp r o p o s e d t h i sa p p r o a c hi n t r o d u c e st h eg d t t e c h n i q u et oe x t r a c tr u l e s 、析t hs t r e n g t h t h i sp a p e r p r o p o s e s t h eg d t - b a s e dm e t h o dt ol e a ms t r u c t u r e so ft h e p r o b a b i l i s t i c r e l a t i o n a lm o d e l s ( p r m s ) f r o mi n c o m p l e t er e l a t i o n a ld a t a ，n l e i n c o m p l e t er e l a t i o n a ld a t aa r ef i l l e dg d t - b a s e da tf i r s t ， a n dao r i g i n a lp r m si s g e n e r a t e df r o me a c hc o m p l e t e d d a t as a m p l e t h i sp o p u l a t i o no fp r m si st h e ne v o l v e d t h r o u g ha ne v o l u t i o n a r yc o m p u t i n gp r o c e s s ，a n dt h ei n c o m p l e t ed a t aa r em o d i f i e db y u s i n gt h el a s ts t r u c t u r ei ne a c hg e n e r a t i o n a sar e s u l t ，t h ep r o b a b i l i s t i cs t r u c t u r ei s l e a r n e d as i m p l ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h eg d t - b a s e dp r mm e t h o dc a n l e a r ng o o ds t r u c t u r e sf r o mi n c o m p l e t er e l a t i o n a ld a t a f i n a l l y ，t h r o u g he x p l a i n i n gt w o r e a l w o r l de x a m p l e su s i n gt h ea p p r o a c h ，w ea n a l y z et h er e s u l ta n di ts h o w st h a tt h i s i i i 北京t 业大学t 学硕f ：学位论文 a p p r o a c hi sa ne f f e c t i v ei n c o m p l e t er e l a t i o n a ld a t a i nt h i sp a p e r , t h ep r o b l e mi nas i m u l a t e da n dar e a lp r o b l e md o m a i na r e d i s c u s s e do nt h ee x p e r i m e n t s c h o o li s s u e si nt h es i m u l a t i o nd o m a i n ，t h eg e n e r a t e d d a t aw i t h5 0 0 0s a m p l e so ft h ef o u rd a t as e t s ，r e s p e c t i v e l y , w i t h10 ，2 0 ，3 0 ， 4 0 o ft h el o s so fd a t at h a tt h ef o u rd a t as e t sf o rt e s t i n g m o v i ei nar e a ld o m a i n ，w e s e l e c t e di nt h ed a t a b a s et h a tc o n t a i n sa5 0 0 0m o v i e ，3 0 0 0m o n t h sa c t o ra n dd i r e c t o ro f t h e15 0 0s u b s e t a sar e s u l to ft h ee x i s t i n gm e t h o di sa l m o s tn e v e ra b o u tf r o mt h ec o m p l e t ed a t a t ol e a r np r m s t h e r e f o r e t h ee x p e r i m e n tu s e dt oc o m p a r et h em e t h o dw i t ht h ew a y f i r s t l yf i l l e dw i t hr a n d o md a t an o tc o m p l e t e d ，a n dt h e ns t a r t e dt ol e a r nt h em e t h o d st o b ep r m s t h eg d t - b a s e da l g o r i t h mt h r o u g ht h ee v o l u t i o no ft h eb e s tn e t w o r k s t r u c t u r ee m b e d d e di ni n c o m p l e t ed a t a t h ee r i e c t i v er e h a b i l i t a t i o no ft h en o i s ed a t a w i t hi t e r a t i o n t h ed a t ar e v i s e db e t t e ra n db e t t e r w eh a v ef o u n dt h r o u g he x p e r i m e n t s t h em e t h o do fg d t - b a s e di sv e r ye f f e c t i v ef o rt h ep r e t r e a t m e n tp r o c e s so ft h e i n c o m p l e t ed a t a ，t h eg d t - b a s e dm e t h o dw i l la p p l yan e t w o r ks t r u c t u r e 。t h e r e f o r e ， t h i sm e t h o dh a sat h e o r e t i c a la n dp r a c t i c a lv a l u e k e y w o rds s t a t i s t i c a lr e l a t i o n a ll e a r n i n g ；g d t ；i n c o m p l e t ed a t a ；p r o b a b i l i s t i c r e l a t i o n a lm o d e l s i v 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研 究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他 人已经发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构 的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均 已在论文中作了明确的说明并表示了谢意。 签名：盘，姿日期：里芝至墨旦堡堂 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵守此规定) 签名卜挞 导师签名：鱼：3 日期：芝= ! ：窆 1 1 研究背景 第1 章绪论 统计关系学习( s t a t i s t i c a l re l a t i o n a l l ea r n i n g ，s r l ) 是1 9 9 8 年左右出现的 一个新的研究领域，它集关系( 逻辑) 表示、似然推理( 不确定性处理) 和机器 学习( 数据挖掘) 于一体，目的是获取关系数据( 关系数据系指数据之间通常具 有多种多样的关系，而非指关系数据库中的数据) 中的似然模型。统计关系学习 又称似然逻辑学习( p r o b a b i l i s t i cl o g i c l e a r n i n g ，p l l ) ，多关系数据挖掘 ( m u l t i r e l a t i o n a ld a t am i n g ，m r d m ) ，关系学习( r e l a t i o n a ll e a r n i n g ) 。 1 1 1 统计关系学习 传统的数据挖掘算法都是基于表中属性值的设置，每个对象由一个固定的属 性集合来描述，其中每个属性只能取一个值。这类算法的问题在于它们只在单表 ( 单关系) 中适用，即分析简单对象时有效。但是多数现有的不同领域的数据库 都并非以单关系存储，而是包含若干关系的关系数据库。一个关系数据库包含若 干表所构成的表集合和每对表之间关系( 描述一个表中的记录如何与另一个表中 记录相关联) 所构成的关系集合。关系数据库中的复杂对象由多表中的多记录来 描述，为了正确分析包含多关系的关系数据库，必须处理好关系数据库中出现的 结构信息。于是，人们开始关注对复杂对象进行建模，从而进一步发现关系数据 中的有效知识。 统计关系学习重点研究的多关系数据挖掘方法( m u l t i r e l a t i o n a ld a t a m i n i n g ，m r d m ) ，这一类方法可以处理以多表形式存储的关系数据，而无需像 传统的方法那样将关系表转换为单表。 这里的所谓“统计( 或概率) ”是指应用统计学习和推理技术及基于概率论的 概率表示和推理机制，如贝叶斯网、( 隐) 马尔卡夫模型、随机文法、马尔卡夫网 等，这些表示方法已经成功应用于很多领域，并由此得到了许多不确定性推理模 型；所谓“关系( 或逻辑) ”系指关系和一阶逻辑表示，使用这些方法的好处是能够 很好地表示包括多个对象及对象间关系在内的复杂情况；所谓“学习”，在这里与 数据挖掘等同，系指在数据基础上得到概率关系模型【l j 。 统计关系学习的早期研究多集中于归纳逻辑程序设计( i l p ) 1 2 ，引，随着对s r l 研究的不断深入，许多不基于i l p 技术的统计关系学习方法被陆续提出。根据 统计关系学习方法所用似然关系模型的不同大致可分为 3 1 ：基于b a y e s i a n 网的 s r l 方法( 如：p r m - - p r o b a b i l i s t i cr e l a t i o n a lm o d e l ) 。基于m a r k o v 网的s r l 方 北京t q k 大学t 学硕士学位论文 法( 如：m l n - - m a r k o vl o g i cn e t w o r k ) 。基于随机文法的s r l 方法( 如：s l p - - s t o c h a s t i cl o g i cp r o g r a m ) 。基于( 隐) m a r k o v 模型的s r l 方法( 如：r m m r e l a t i o n a lm a r k o vm o d e l ，) 。 1 1 2s r l 的应用领域和研究方向 i 应用领域 互联网( t h ew o r l d w i d ew e b ) 可将互联网看成是一个巨大的图，并且网页之 间是相互联系的，这使得w e b 搜索1 5 , 6 1 和w e b 分类【j 7 1 演化为挖掘w e b 的链接结 构( i i n ks t r u c t u r e ) 。统计关系学习可以进行链接结构的挖掘，并可将这种连接关系 ( ”l i n kt o ”r e l a t i o n ) 与网页的文本内容、h t m l 结构结合起来。 社会网( s o c i a ln e t w o r k s ) 社会网分析【8 】着重于社会参与者之间关系的建模，从 一般意义上讲，它与上述所有的应用有关。社会网建模是统计关系学习的一个主 要任务。 信息提取( i n f o r m a t i o ne x t r a c t i o n ) 网络上的文本信息越多，信息提取技术的 作用就越大。信息提取的目标是从文本中生成数据库，要达此目的需要理解文本 实体间明显和隐含的关系，因此信息提取从本质上说是一个关系问题。 计算生物学( c o m p u t a t i o n a lb i o l o g y ) i l p 在分子生物学应用领域已经取得了 一些令人瞩目的成功【9 j 。更重要的是，生物学正从研究单个的基因和蛋白质转向 研究它们在细胞中的相互作用。对这些相互作用关系、这些相互作用与观察结果 间的关系、这些相互作用与参与作用的分子特性间的关系进行建模是统计关系学 习的一个巨大应用领域。 2 研究方向 统一框架【lo 】迄今为比，虽然已提出大量的统计关系学习模型，但统计关系学 习所研究的问题和所用方法的多样性使人们难以认识它们的本质。缺乏对不同方 法的优缺点，以及它们之间关系的比较研究，使一个应用中的新方法很难在其它 应用中被使用。因此，迫切需要研究统计关系学习的统一框架，以及可以描述、 关联不同任务、方法的通用语言。 应用领域知识结合领域知识对k d d 项目的成功至关重要。由于应用领域极 其庞大和复杂( 专家的头脑也是如此) ，所以很难获得纯逻辑形式的领域知识。 如果统计关系学习方法可以利用不确定推理来获取领域知识，将在很大程度上提 高领域知识的可用程度。 推理算法和学习算法现有模型的推理【1 0 】和学习算法的复杂性都是指数阶的， 特别对大规模的数据集和似然模型实例，其执行效率儿乎是难于接受的，进一步 提高推理和学习算法的效率是目前的研究热点之一。似然关系模型的表达能力与 其上的推理算法、学习算法的运行效率之间，存在着相互制约的关系，在应用中 第l 苹绪论 不得不在能力和效率之间做出折中。研究基于仿生计算的学习方法已为众多学者 所认同。 从多种信息源学习统计关系学习的数据通常来自不同的信息源，因此可能包 含许多不同的类型( 如关系数据库、纯文本、h t m l ，x m l 、音频、视频、传感 器等) 。既便是同种类型，不同来源的数据对同一个实体会经常使用不同的表示 方法。人们期望统计关系学习系统可以自动地将源信息映射到系统感兴趣的对象 和关系上。这要求系统具有使用元数据和自描述数据的能力，使用机器学习技术 从己知的映射向未知的映射拓展的能力，自动测定信息源质量的能力。除了上述 问题外，学习随时间变化的关系数据、与传统的k d d 方法相结合、与数据库系 统相结合等也是统计关系学习未来的主要研究问题【1 1 1 。 1 1 3 不完备数据下p r m s 研究现状 现有的关系学习研究大多是基于完备数据进行的，而现实问题中，数据通常 是不完备的。在传统的机器学习领域中，从不完备数据中学习的问题已经得到了 研究【1 2 13 1 ，但不完备的关系数据问题非常复杂，因此，几乎没有任何一项技术可 以直接被扩展到关系学习领域。传统的机器学习算法可以被看成是数据集中仅有 的一个表，并且不存在关系的学习算法。例如，b a y e s i a n 网络可以看成是仅包 含一个属性类，并且不存在关系的p r m 。因此，p r m 结构学习的复杂度至少相 当于b a y e s i a n 网络学习的复杂度。由于具有多个局部极值，如果将传统的机器 学习中处理不完备数据问题的算法直接扩展到关系学习中，学习的复杂度将会明 显提高，并且会得到较差的结果。因此，从不完备的关系数据中学习是关系学习 领域中一个重要的、有待解决的问题。 通常，从不完备数据中学习b a y e s i a n 网络需要对不完备数据进行估计。类 是基于蒙特卡洛或采样1 1 4 】的方法使用这种方法能够得到非常准确的结果，但计算 复杂度随变量增加呈指数集级增长，并且变量较多时很难实现。另一类是基于 e m ( e x p e c t a t i o n m a x i m i z a t i o n ) 算法的方法【1 2 1 。对于从不完备数据中进行参数估计 来说，标准的e m 算法具有很强大的能力。结构学习中潜在、可能的结构数量 巨大，对于e m 算法中的e 步来说，如何有效地确定当前结构是否适合非常困 难。文献【15 】中指出，由于搜索空间巨大且具有多个局部极值，此类方法通常易于陷 入局部最优。 在文献【1 6 】中也提到对于不完备关系数据的参数学习问题，但并未涉及从不完 备关系数据中学习模型结构的问题。g e t o o r 等人【1 7 】通过建立属性和与其相关的 结构之间相互关系的模型将p r m 进行扩展。s a n g h a i 等人【ls j 将动态b a y e s i a n 网 络加以扩展。将每个时间片表示成一个p r m 等等。但是，现有的关系学习研究 大多是基于完备数据进行的，几乎没有其他算法能够解决从不完备关系数据中学 北京工业人学1 = 学硕l ：学位论文 习p r m 结构的问题。 1 2 本课题的主要研究内容及意义 本课题基于g d t 思想在处理不完备数据是的优势，提出一种基于g d t 的从 不完备关系数据中学习概率关系模型( p r o b a b i l i s t i cr e l a t i o n a lm o d e l s ，简称p r m s ) 的方法。根据g d t 的方法对缺失数据进行预处理，将不完备关系数据填充得到 完备关系数据。然后从通过g d t 填充的数据样本中分别生成p r m 并作为初始 p r m 网络，再利用学习过程中前一步得到的网络结构反复修正不完备数据集， 最后得到概率关系模型。 通过简单的虚拟的例子对数据的预处理及算法的设计和实现进行说明和演 示。用以确定这种基于g d t 的算法在处理不完备数据时学习p r m 网络的可行 性。最后通过对两个实世界的问题阐述了该方法的实施过程和实验结果，将这种 新的方法用实验加以检验和证明。 本课题提出的这种方法，能够很有效的对不完备数据进行预处理，得到基于 g d t 的完备数据。将g d t 的方法应用到统计关系学习p r m s 的网络构造中，并 且能够从不完备数据中学习到一个较好的模型结构。并且通过反复的迭代过程产 生的冗余边也是比较少的。因此本文的结果对统计关系学习具有一定得理论意义 和现实价值。 1 3 本文的组织 本文在绪论中介绍了本研究领域的学术背景及理论基础。包括统计关系学习 的基本概念，以及不完备数据下p r m s 学习的研究进展和不足；明确了本文的研 究内容。 第二章将详细介绍相关问题的研究，主要是：似然关系模型和g d t 的思想， 对他们的理论进行详尽的讨论。 第三章将具体的讨论我们设计的算法的具体实线框架与创新点。 第四章中列出了我们的实验结果并进行了结果的分析。 最后是对本次课题中所做工作的总结包括创新与不足，以及对未来工作的展 望。 第2 章相关问题的研究介绍 第2 章相关问题的研究介绍 2 1 似然关系模型 b a y e s i a n 网是最重要、最有效和最优雅的使用概率进行表示和推理的模型。 然而，传统b a y e s i a n 网是命题逻辑的概率扩展，该方法针对扁数据，不能处理 丰富的关系数据，且表达能力有限。将传统b a y e s i a n 网与一阶逻辑相结合( 一 阶贝叶斯逻辑) 或将b a y e s i a n 网与实体关系模型相结合( 似然关系模型) ，就 可以处理关系数据，并具有更强的表达能力【1 9 】。 似然关系模型( p r o b a b i l i s t i cr e l a t i o n a lm o d e l s ，p i 蝴) 是一类基于贝叶斯网 ( b a y e s i a n ) 的统计关系学习方法，它是标准贝叶斯网模型的扩展，p r m 使用表 示实体间关系的实体关系模型( e n t i t yr e l a t i o n s h i pm o d e l ，e r ) 作为基本的表示 框架，将p r m 看成是描述关系型数据库上概率分布的模板。模型的结构描述关 系模式及属性间的依赖，模板的参数定义对象属性依赖关系的概率分布。于是， 该模型除了能使用概率进行表示和不确定推理外，还可以处理关系数据，具有更 强的表达能力，可以用来在复杂的系统上建模，这对智能信息系统的开发研究有 着特别重要的意义。 2 1 1 一阶逻辑 一阶谓词逻辑是谓词逻辑中最直观的一种逻辑，它以谓词形式来表达动作的 主体、客体( 可有多个) ，简称为一阶逻辑。一阶逻辑是建立在一阶语言基础上 的逻辑体系【2 0 】。作为一阶逻辑的形式语言，一阶语言主要由个体词、谓词符号、 函词符号、量词符号、联结词符号、蕴含词符号、等价词符号、括号与逗号连结 而成。 下面给出一阶逻辑有关概念、术语的正式定义【2 0 j 定义3 1 个体词是指所研究对象中可以独立存在的具体的或抽象的客体；将 表示具体或者特定的客体的个体词称为个体常项：将表示抽象或者泛指的个体词 称为个体变项：个体变项的取值范围称为个体域( 记为d ) 。 定义2 1 谓词是用来刻画个体词性质及个体词之间相互关系的词，n 元谓词 是从d n 到 t ，f ) 的映射。 定义2 2 函词是个体词到个体词的映射，n 元函词是从d n 到d 的映射。 定义2 - 3 量词是表示个体常项和个体变项之间数量关系的词，包括全称量词 v 和存在量词了。 北京t 业大学t 学硕卜学位论文 一阶逻辑知识库是一阶逻辑公式所构成的集合2 2 1 一阶逻辑中的基本推理问 题就是判断： 知识库k b 是否可推出公式f ? 例2 1 我们以一个只包含两个公式f 1 和f 2 的简单知识库为例，这两个 公式分别为： f 1 ：吸烟致癌 f 2 ：若两人是朋友，则吸烟习惯相同 谓词包括： s m ( x ) ：x 吸烟 c a ( x ) ：x 患癌症 f r ( x ，y ) ：x 与y 使朋友 表2 1 给出了该知识库所对应的一阶逻辑形式和字句形式。 表2 1 知识库的描述 4 8 】 t a b l e2 1t a b l ed e s c r i b e do ft h ek n o w l e d g eb a s e 人类语言一阶逻辑形式字句形式 吸烟致癌v x ，s m ( x ) _ c a ( x )一跏( x ) vc a ( x ) 若两人是朋 v x v y ， 一乃( x ，j ，) vs m ( x ) x - - , s m ( y ) 友，则吸烟习惯相同f r ( x ，y ) j ( 跏( x ) b o ，0 8 - 则a f ( a o b o c 0 a 0 * c 0 ) = 0 8 x 2 符合分支条件1 a f ( a o b l c 0 i a o c 0 ) = ( 1 0 8 ) ( 2 1 ) x 2 = 0 2 x 2 符合分支条件2 第2 章相关问题的研究介绍 根据背景概率知识修改过的g d t 的概率分布为： 表2 - 6 修改过的g d t m l b l e2 6r e v i s e dg d t 2 多条背景概率知识情况 背景概率给出形式为a i d l - 巩j ，q 。 a f s ( p i i p g ) = 兀彳z ( i 尸g ) 当i e b s ，p g ，j j 【s ，p g ，i 】，p i i 2a i j a f i ( p i i p g ) = q i j n i ( 公式3 11 ) 当i b s ，p g ，vj 0 j s ，p g ，i 】) ，p i i a i j l 一g a f “p i | p g ) 2 j - 褊吩 其他情况 a f i ( p i i p g ) = i 说明： b s ，p g 】：满足条件p g i l _ a i l j l ，p g i 】= 幸的属性集合。i e 1 m ) j s ，p g ，i 】：取b s ，p g lq b 的属性i ，所对应的属性值的序列集合。j l n i ( 2 8 ) ( 2 9 ) ( 2 1 0 ) 北京t , l k 大学1 二学硕七学位论文 2 2 3 规则强度 在用g d t 思想开发的g d t - r s 系统中，规则通常以x y w i t hs 的形式表 示，含义是如果x 那么y 规则强度是s ，规则强度的定义是s = p x ( 1 r ) 。其中 p 是泛式x 的强度，r 是噪音率，换言之，规则强度表现了由未记录的实例和噪 音引起的规则的不完备性和不确定性。p 记录了泛式x 和满足泛式x 的实例间 的先验概率之和。它所表达的是在满足泛式x 的所有实例中显式出现在数据库 中的实例情况。p 的初始值为0 ，随着数据库中数据的不断变化，p 值动态改变。 如果所有满足泛式的实例都出现了，p 值为1 。 不考虑背景知识时 p ( p g ) = p ( p l ti p g ) = f n s - r e l ( p g ) ( 2 1 1 ) 1 v p g 其中一脚( p g ) 是满足泛式p g 的实例个数。 考虑背景知识时 p ( e g ) = 如( l 尸g ) = ( b 灯( 一l p g ) ) ( 2 1 2 ) ，l v p g 在上述两个公式中实例个数求和时，重复实例只计算一次。 r ：反映了分类的噪音情况，当规则具有相同的条件属性，不同的决策属性 时，称规则具有噪音。 ，( x 专j ，) ：型型= 型茎2 二丝型= ! 纽! 茎：望( 2 1 3 ) 。 n 恬。天x 、) 以s - t e l ( x ) 是满足泛式x 的实例的个数。一幽( x ，l ，) 是满足泛式x ，属于 决策属性y 的实例个数。 g d t 考虑到了数据不完整性和噪音的影响，挖掘出较为精练的，附有预测 强度的决策规则【4 0 】。通常，训练例仅为所有可能实例中的一部分，如果没有考虑 到除训练例外剩下的其余部分，那么我们从这个数据集中发现出的规则在实际分 类中的性能将会达不到应有的效果。从这个意义上说，规则强度的引入使我们能 够在一个开放的世界假设中考虑问题，使得发现出的规则能有效的处理未知实例 的分类。 2 3 本章小结 本章介绍了似然关系模型的基本概念和关系表示方式。似然关系模型 ( p r o b a b i l i s t i cr e l a t i o n a lm o d e l s ，p r m ) 是一类基于贝叶斯网( b a y e s i a n ) 的统计 关系学习方法，它是标准贝叶斯网模型的扩展。模型的结构描述关系模式及属性 间的依赖，模板的参数定义对象属性依赖关系的概率分布。于是，该模型除了能 使用概率进行表示和不确定推理外，还可以处理关系数据。 第2 苹相关问题的研究介绍 g d t 思想的优点在于：通过概括强度、规则置信度和规则强度，充分考虑 到数据不完整性和噪音引起的不确定性。并且，基于属性学习存在背景知识只能 以相当有限的形式加以表示的局限性。而g d t 思想可以把背景知识，背景知识 的先验概率自然得用于学习过程，使学习出的规则精确度高，对未出现情况的预 测更准确。 第3 章基于g d t 的不完备数据似然关系模型的学习 第3 章基于g d t 的不完备数据似然关系模型的学习 在不完备的数据集下学习似然关系模型问题的关键是首先如何将不完备的 数据完