（计算机软件与理论专业论文）基于动态粒度思想的实体关系识别方法研究.pdf

摘要 信息抽取是自然语言处理领域的一个重要分支，它的研究内容是从 海量信息源中迅速找到真正需要的信息，主要目的是将无结构的文本转 化为结构化或半结构化的信息，并以数据库的形式存储，供用户查询以 及进一步分析利用。 中文信息抽取研究起步较晚，主要研究工作集中在中文命名实体的 识别方面。近年来，随着实体识别研究逐步实用化，实体关系识别的研 究也越来越受到人们的重视。实体关系识别对于篇章理解、信息检索、 信息抽取、问答系统、机器翻译等方面的研究有着非常积极的意义。目 前汉语实体关系识别的研究刚起步，研究者主要是采用基于特征向量的 机器学习算法识别中文文本中的实体关系，取得了定的效果。 实体关系的识别完全依赖文本中的特征，不同的特征粒度对识别结 果有较大影响。分析以往的方法，都是采用统一粒度的特征来进行关系 识别，这样会产生由于特征粒度比较“细”，问题粒度相对比较“粗” 而不能识别的区域，为了解决这个问题，本文提出了采用基于动态粒度 下粗集近似思想的方法进行实体关系识别。 本文首次应用动态粒度思想，对识别特征逐步进行了细化，构建了 一个具有偏序关系的特征族，经过训练，用来识别实体关系，耳义得了较 好的效果。本文主要： 作如下： 1 语料标注。对8 1 8 篇3 1 1 马德里爆炸新闻语料，约4 0 万字， 进行丁实体标注，l 训时少量标注丫7 7 伦敦地铁爆炸新i ：l i ：jg l ；- ；h ，做开放 测试语料。 2 实体对聚类。在分析真实语料的基础上，本文采用了o p t i c s 的聚类算法对实验语料中实体对进行了初始聚类。 3 特征选择。从聚类结果中，根据一些特征选择的规则，产生每 类关系的识别特征。 4 构造偏序特征集。应用动态粒度下粗集近似思想，对特征细化， 产生一组由粗到细、有偏序关系的特征族。 按照上面提出的方法，本文设计并实现了基于动态粒度思想的实体 关系识别实验，封闭测试结果，各类实体关系的f 均值都达到了8 0 ， 与采用统一粒度特征的方法相比，f 均值平均提高了5 个百分点，最好 的提高了8 个卣分点。开放测试中，采用本文方法比一般统一粒度方法 高出近7 个百分点。 最后，本文详细分析了实验结果中的错误实例，分析r 原因，并对 一些问题提出了解决的办法，以便进一步研究。 本文采用基于动态粒度思想进行实体关系识别，取得了较好的效 果，今后将在进一步扩大资源，增加特征的基础上进行更深入的研究。 关键词：统一粒度；实体关系；动态粒度；粗集近似；偏序关系 a b s t r a c t i n f o r m a t i o ne x t r a c t i o ni sam a i nb r a n c ho fn a t u r a ll a n g u a g ep r o c e s s i n g f i l e d ，a n di t sf o c u s e so nq u i c ke x t r a c t i n g t r u en e e d e di n f o r m a t i o nf r o m p l e n t yo fi n f o r m a t i o n s o u r c ef o rt r a n s f o r m i n gn o n s t r u c t u r e dt e x ti n t o s t r u c t u r e do rh a l f - s t r u c t u r e di n f o r m a t i o n ，a n ds a v i n ga sad a t e b a s e ，s oi ti s c o n v e n i e n tf o ru s e r s i n q u i r i n g ，a n a l y s i sa n du t i l i z a t i o n t h er e s e a r c ho nc h i n e s ei n f o r m a t i o ne x t r a c t i o nh a saq u i t el a t es t a r t ， a n di ti sc o n c e n t r a t e do ni d e n t i f y i n gm e t h o do fc h i n e s en a m e de n t i t y i n r e c e n t y e a r s ，t h es t u d y o n e n t i t y r e l a t i o n r e c o g n i t i o n b e c o m e sm o r e i m p o r t a n tw i t he n t i t ye x t r a c t i o nr e s e a r c hs t e p b y s t e pp r a c t i c a l i t y e n t i t y r e l a t i o nr e c o g n i t i o nh a sp o s i t i v es e n s eo nt e x tu n d e r s t a n d i n g ，i n f o r m a t i o n r e t r i e v a l ，i n f o r m a t i o ne x t r a c t i o n ，e as y s t e m ，m a c h i n et r a n s l a t i o n a t p r e s e n t ，t h es t u d yo ne n t i t yr e l a t i o nr e c o g n i t i o ni s s t i l li ni n c i p i e n ts t a g e r e s e a r c h e r sa d o p t e dm a c h i n el e a r n i n gb a s e do nf e a t u r ev e c t o rt oi d e n t i f y c h i n e s ee n t i t yr e l a t i o n e n t i t y r e l a t i o n r e c o g n i t i o nd e p e n d o nt e x t c h a r a c t e r s ，d i f f e r e n t c h a r a c t e rg r a n u l a t i o nh a v es i g n i f i c a n te f f e c to ne x t r a c t i o nr e s u l t s a sf o r f o r m e rm e t h o d ，i tu s e du n i f i c a t i o ng r a n u l a t i o nf e a t u r et oe x t r a c tr e l a t i o n ，i t w o u l dr e s u l ti 1 1i d e n t i f i c a t i o ns h a d o wz o n e sw h i c hi sd u et or e l a t i v e t h i n g t a n u l a rf e a t u r e ，w h i l er e l a t i v er o u g hg r a n u l a rq u e s t i o n f o rt h ep u r p o s e ，w e p l o v i d e a ni d e n t i f i c a t i o nm e t h o db a s e do nr o u g hs e ta p p l o x i m a t i o nu n d e r d y n a m i cg r a n u l a t i o nt oi d e n t i f ye n t i t yr e l a t i o n t h ei d e ao fd y n a m i cg r a n u l a r i t yi su s e di nt h i sp a p e rf o rt h ef i r s tt i m e w et h i ni d e n t i f i e df e a t u r eg r a d u a l l y ，c o n s t r u c tac h a r a c t e rs e t so fp a r t i a l o r d e rr e l a t i o n ，t h e ni d e n t i f ye n t i t yr e l a t i o nt h r o u g ht r a i n i n g ，g e tb e t t e rr e s u l t s t h em a i no b j e c t i v eo ft h i ss t u d yw a sa sf o l l o w i n g s 1 l a b e lc o r p u s 。w ec o n d u c t e de n t i t yl a b e l ，a c c o r d i n gt o8 0 0p a p e r si n 3 11a b o u te x p l o s i o nn e w sc o r p u si nm a d r i dw i t h a b o u tf o u rh u n d r e d t h o u s a n dw o r d s a tt h es a m et i m e ，as m a l lq u a n t i t yo fs u b w a ys t a t i o n e x p l o s i o nn e w sc o r p u so f7 7i nl o n d o nw a sa l s ol a b e l e d ，a n du s e da so p e n t e s tc o u s 2 e n t i t yp a i rc l u s t e r i n g o nt h eb a s eo fa n a l y z i n gr e a lc o r p u s ，o p t i c s c l u s t e r i n ga r i t h m e t i cw a su s e di nt h i ss t u d yt oc o n d u c ti n i t i a lc l u s t e r i n go f e n t i t yi ne x p e r i m e n t a lc o r p u s 3 c h a r a c t e rc h o o s i n g a c c o r d i n gt os o m er u l e so fc h a r a c t e rc h o o s i n g p r o d u c i n ge x t r a c t i o nc h a r a c t e ro fe v e r yt y p er e l a t i o nf r o mc l u s t e r i n gr e s u l t s 4 c o n s t r u c tc h a r a c t e rs e t so fp a r t i a lo r d e rr e l a t i o n a p p l y i n gt h ei d e a o fr o u g hs e t a p p r o x i m a t i o n u n d e r d y n a m i cg r a n u l a t i o n ，w e t h i n n e d c h a r a c t e r s ，a n dp r o d u c e dag r o u po fc h a r a c t e rs e t so fp a r t i a lo r d e rr e l a t i o n f r o mr o u g ht ot h i n a c c o l l d i n g t ot h e m e t h o d ，w ed e s i g n e d a n dr e a l i z e d 1 e c o g n i t i o n e x p e l i m e n to fe n t i t y 1 e l a t i o nb a s e d0 1 3d y n a m i cg r a n u l m i t yi nc l o s et e s t 1 e s u h s a v e l a g ef - s c o l l eo fc v e l y1 y p ee n t i t yw a sa b o v e8 0 i nc o n t l a s tt o t h em e t h o do fu n i f i c a t i o ng r a n u l a t i o nc h a r a c t e r ，a v e r a g ef s c o r ei n c r e a s e d5 p e r c e n t a g ep o i n t s ，e v e nt h eb e s tw a sa b o u t8p e r c e n t a g ep o i n t s i no p e nt e s t t h em e t h o di nt h i ss t u d yw a sa b o u t7p e r c e n t a g ep o i n th i g h e rt h a nt h ef o r m e r m e t h o d a tl a s t ，w ea n a l y z e dw r o n gi n s t a n c e si ne x p m i m e n tr e s u l t sa n dt h e c o r r e s p o n d i n gr e a s o n s ，a n db r o u g h tf o r w a r ds o m es o l u t i o n s i n t h i ss t u d y ，w eu s e dd y n a m i cg r a n u l a r i t yi d e at oi d e n t i 考e n t i t y r e l a t i o n ，a n dh a db e t t e rr e s u l t s m o r ed e e p l yr e s e a r c hi st ob es t u d i e do nt h e b a s i so fm o r er e s o u r c e sa n dc h a r a c t e r si nt h ef u t u r e k e y w o r d s ：u n i f i c a t i o ng r a n u l a t i o n ；e n t i t yr e l a t i o n ；d y n a m i cg r a n u l a t i o n ； r o u g hs e ta p p r o x i m a t i o n ；p a r t i a lo r d e rr e l a t i o n 第一章引言 1 1 课题的研究意义 随着计算机的普及以及互联网的迅猛发展，大量的信息以电子文档的形式出现 在人们面前。为了应对信息爆炸带来的挑战，迫切需要一些自动化的工具帮助人们 在海量信息源中迅速找到真诈需要的信息。信息抽取( i n f o r m a t i o ne x t r a c t i o n ) 研究 正是在这种背景下产生的”。信息抽取是指借助自然语言处理技术，通过对文本中 的句子以及篇章进行分析处理，从文本中直接获得指定的信息，然后将这些无结构 的文本转化为结构化或半结构化的信息，并以数据库的形式存储，供用户查询以及 进一步分析利用。般来晓，信息抽取处理的对象是电子文本，但广义上讲，语音， 图像，视频等其他媒体类型的数据都可以是信息抽取的对象”。信息抽取是多种自 然语言处理技术的综合，应用领域十分广泛。 命名实体识别是信息抽取中重要的研究课题，命名实体是文本中基本的信息元 素，是正确理解文本的基础。狭义地讲，命名实体是指现实世界中的具体的或抽象 的实体，如人、组织、公司、地点等。广义地讲，命名实体还可以包括时间f t 、数量 表达式等川。然而，在大多数的应用中，不但要识别文本中的实体，还要确定这些 实体之间的关系，与实体识别类似，实体关系的类型电是预先定义的，例如：地理 位最关系( p h y s ) 、雇佣关系( e m p o r g ) 等等。如文本中提到“美国纽 约”，其中“纽约”和“美国”都是地点实体，而它们又构成了一种地理位置 关系中的部分一整体关系，即“纽约”是“美国”的一部分。如果说信息抽取的主 要功能是自动将文本转化为数据表格，实体识别确定了表格中各个元素的话，实体 关系识别则是确定这些元素在表格中的相对位置。由此可见，实体关系识别是信息 抽取中的重要环节【2 1 。实体关系识别是篇章理解的一个核心技术，同时对信息抽取 ( i n f o r m a t i o ne x t r a c t i o n ) 、问答系统( q u e s t i o na n s w e r i n g ) 、机器翻译( m a c h i n e t r a n s l a t i o n ) 等有着非常积极的意义，是大多数自然语言处理任务中必不可少的环 节，在自然语言处理中有着重要的作用。现在实体关系识别已经逐渐成为自然语言 处理的一个热点问题。 1 2 国内外相关研究概述 近年来，随看实体以别研究逐步实用化，实体关系u 别的研究也越来越受到人 摹于动态粒度思想的实体关系识别方法i i j f 究 们的重视。其中美国国防高级研究计划委员会( d a r p a ，t h ed e f e n s ea d v a n c e d r e s e a r c hp r o j e c t s a g e n c y ) 资助的m u c ”j ( m e s s a g e u n d e r s t a n d i n gc o n f e r e n c e ) 会议 于1 9 9 8 年最后一次m u c 一7 1 4 】上首次引入了关系抽取( 模板关系，t e m p l a t er e l a t i o n ) 任务2 1 。 随着m u c 会议的停办，美国国家标准技术研究院( n i s t ) 组织了自动内容抽 取( a c e ，a u t o m a t i cc o n t e n te x t r a c t i o n ) 评测口】，它从1 9 9 9 年丌始继续进行信息抽 取方面的评测”1 。a c e 评测1 9 9 9 年7 月丌始酝酿，2 0 0 0 年1 2 月丁f 式开始启动，迄 今已经举办过五次评测( 2 0 0 0 年5 月、2 0 0 2 年2 月、2 0 0 2 年9 月、2 0 0 3 年1 0 月、 2 0 0 4 年8 月) 。其研究的主要内容是自动抽墩新闻语料中出现的实体、关系、事件 等内容。目前a c e 评测主要有两大任务：实体识别( e d r ，e n t i t yd e t e c t i o na n d r e c o g n i t i o n ) 和关系识别( r d r ，r e l a t i o nd e t e c t i o na n dr e c o g n i t i o n ) 。其中，r d r 定义了较为详细的关系，包括6 个大类和若干子关系。六个大类分别是p h y s i c a l ( 自 然) ，p a r t w h o l e ( 部分一整体) ，p e r s o n a l s o c i a l ( 个人一社会) ，o r g a f f i t i n i o n ( 机 构一从属) ，a g e n t - a r t i f a c t ( 代理一人造) ，g e n e r a l a f f i l i a t i o n ( 一般从属) 。其中每 类关系都有若干个子关系，p h y s i c a l 又包含l o c a t e d ( 位于) 和n e a r ( 相邻) 两种关 系，p a r t w h o l e 包含g e o g r a p h i c a l ( 地理位置) 、s u b s i d i a r y ( 附属) 和a r t i f a c t ( 人 造) 三种关系，p e r s o n a l s o c i a l ( 个人一社会) 包括b u s i n e s s ( 工作) ，f a m i l y ( 家庭) 和l a s t i n g - p e r s o n a l ( 持续性关系) 6 1 。其余关系就不在此列出了，相关信息见附录。 a c e 评测提供的语料不仅是英文，还包括中文和阿拉伯文【7 】。 中文信息抽取方面的研究起步较晚，主要的研究工作集中在对中文命名实体的 识别方面，对命名实体关系识别的研究刚刚开始，主要采用的研究方法是基于特征 向量的机器学习算法，并取得了一定的效果。中科院计算所的姜吉发 8 1 研究了一种 自举的二元关系获取方法，该方法从种子集合出发，获取任意给定的二元关系；哈 工大车万翔2 1 参加了a c e2 0 0 4 的实体关系评测，利用a c e 的训练数据，分别对s v m 模型、w i n n o w 算法进行了训练，进行特征选择，并以此进行实体关系的自动抽取， 其f 值均达到了7 3 ；i n t e l 中圈研究中心存a c l2 0 0 0h 寅示了他们丌发的命名实 体及其关系的信息抽取系统，该系统利用记忆获墩胤则从而抽取相关内容h j 。 1 3 课题研究内容 文体父系l ! 别足信息抽取研究领域中的重要研究课题，从文档巾抽取各利，关系 引言 并将之结构化存储是进一步数据查询和数据挖掘的前提，也是深入理解文档的基 础。本文希望能够用于“突发事件信息抽取系统”的研究中，故主要针对突发事件 新闻报道进行实体关系的界定和识别。经过我们的考察，发现在突发事件报道中， 地名、人名和机构名对发生的事件而言，有着非常重要的意义，通常是指出发生事 件的相关信息，而且这几类实体一起出现的频率很高，形成了多种关系，由于实体 间关系包含较多对事件了解相当有用的信息，所以对这些实体关系的识别，对整个 文档的突发事件信息的挖掘是非常有帮助的。因此本文将研究点定位于突发事件中 人物、地理位置和组织机构实体之削的关系识别技术研究。 本文的研究以同事件、多文本为处理对象，实验对象选用对同一事件的多篇相 关报道。发生在2 0 0 4 年3 月1 1r 的西班牙恐怖爆炸事件造成了2 0 0 多人死亡，5 0 0 0 多人受伤，伤亡之惨重震动了世界，我们选择3 1 1 事件作为实验对象在国际恐怖主 义猖獗的今天，具有很强的现实意义和应用价值。 对于实体之间关系的以别，以前的方法使用的都是统一粒度的特征，即特征的 粒度大小是固定的，在关系识别过程中，特征粒度是固定的，不会变化。而统一粒 度特征产生的无法识别的区域，就是固定的，不会变化。基于此，本文提出了一种 基于动态粒度下粗集近似的方法，采用动态粒度的特征族来识别实体关系，即采用 不同粒度大小的特征族，米解决统一粒度下产生的识别盲区不能变化的问题，使得 识别盲区逐渐减小直至消失。 本文的主要：l ：作集中于实体对聚类和构建动态粒度的具有偏序关系的特征族。 聚类使用o p t i c s 的聚类算法，它是一个基于密度的聚类算法，不过度依赖固定参 数，从结果中提取特征。基于核和重要度的概念构造了算法，产生具有偏序关系的 动态粒度特征族。 1 4 论文结构 第一章引言 介绍了课题的研究背景和主要的研究内容，并对所采用的方法进行了初步介 绍。 第二章实体关系识别方法 介绍了围, j 外常用的实体关系u 别方法 i hj 7 本文提“；的笑系u 别方法。 3 基于动态粒度思想的实体关系识别方法研究 第三章粒度计算 介绍了粒度计算的基本概念和主要研究的三个理论工具，最后重点介绍了本文 所应用的动态粒度思想。 第四章实体对聚类和特征抽取 介绍了常用的一些聚类方法，本文对实体对进行聚类的意义，特征抽取的一些 规则。 第五章实体关系识别实验与结果分析 描述了实体关系识别实验的殴计和组织、实验的评测标准，最后分析了实验结 果。 第六章结论 对课题做了总结以及对下一步工作做了展望。 4 实体关系识别硼j 珐 第二章实体关系识别方法 关系抽取是近些年才丌始研究的，美国国防高级研究计划委员会( d a r p a ，t h e d e f e n s ea d v a n c e dr e s e a r c hp r o j e c t sa g e n c y ) 资助的m u c ( m e s s a g eu n d e r s t a n d i n g c o n f e r e n c e ) 会议于1 9 9 8 年最后一次m u c 7 上首次引入了关系抽取( 模板关系， t e m p l a t er e l a t i o n ) 任务。实体关系抽取要更晚一些，随着m u c 会议的停办，美国 国家标准技术研究院( n i s t ) 组织了自动内容抽取( a c e ，a u t o m a t i cc o n t e n t e x t r a c t i o n ) 评测，在近几次评测中才加入了实体关系抽取评测，丌始只有英文、日 文的评测，后来加上了中文的评测。 2 1 常用识别方法介绍 实体关系识别研究方法目前主要是采用基于机器学习的方法和自举获取关系 的方法。 2 11 基于机器学习的方法 通常，人们将关系抽取问题转化为一个分类问题，即首先列出一个句子中所有 的实体对，然后使用一个分类器决定哪些是我们真正需要的关系”。和分类问题通 常的解决办法一样，人们最初也是使用知识库的方法来解决该问题。但方法需要专 家构筑大规模的知识库”1 ，这不但需要有专业技能的专家，也需要伺出大量劳动。 为了克服知识库方法的缺点，人们后来使用机器学习的方法来解决此问题“，” 。该 方法不需要有专业技能的专家书写知识库，只需要有一定专业知识的人对任意两个 实体之间的关系做出是与不是我们需要的关系的判断即可。然后以此为训练数据， 使用各种学习方法构造分类器。 1 基于特征向量的学习算法 通常的机器学习算法需要构造特征向量形式的训练数据。然后使用各种机器学 习算法，如支持向量机( s v m ) 1 3 1 、w i l l l l o w 等作为学习机构造分类器。这种方 法被称作基于特征向量的学习算法。该方法最重要的过程是实例特征构造，选取恰 当的特征能够较好的对实体进行表述，有利于学习效果的提高。识别效果与特征有 直接关系，不足就是目前的特征单一，效果不能令人非常满意，如能找到更多、更 好的特征，构造特征丰富的特征向量，以别效果会更好一些。 哈尔滨工业大学4 ：万翔采用支持向量机( s v m ) 和w i n n o w 分别构造了分类器， 基于动态粒度思想的实体关系识别方法 i ；| f 究 支持向量机( s v m ) 采用台湾大学的l i b s v m 算法库 1 5 j ，并使用默认的参数，w i n n o w 算法使用u i u c 大学的s n o w 算法库【1 6 1 ，迭代次数设置为3 0 0 0 次。采用实体周围的 词作为特征，窗口大小从0 到3 ，从结果中来看，两种分类器从效果匕看都是在窗 口为2 的时候，同时得到最优的结果，而且s v m 算法比w i n n o w 算法结果要好， 但是，在测试和运行的过程中，s v m 算法都需要较长的时间。从最终结果来看， 使用相同的特征，效果差别并不大，在选择算法的时候，当对学习效率要求不高， 而对最终的学习性能要求较高t 0 ，可以选择s v m 算法；相反，对学习效率要求很 高，对最终学习性能要求不高时，可以选择w i n n o w 算法【2 j 。 2 ，不需要特征向量的学习算法 基于k e r n e l 的学习算法，它最早在支持向量机( s v m ) 方法中被引入，后来 发现多种学习方法可以使用k e r n e l 的形式来表示。它们又被称作基于k e m e i 的学 习算法。在自然语言处理领域应用基于k e r n e l 的学习算法旧1 8 】，与基于特征向量的 学习算法不同，基于k e r n e l 的学习算法不需要构造特征向量，而是直接使用字符串 的原始形式作为处理对象，需要做的只是计算任何两个对象之问的k e r n e l ( s i m i l a r i t y ) 函数。z e l e n k o 等以及c u l o t t a 等【2 0 】使用k e m e l 的方法解决关系识 别问题，取得了较好的结果，他们使用的方法需要对处理对象进行浅层的句法分析。 然而k e r n e l 的一个致命缺点是训练和预测的速度太慢，不适于处理大量的数据。 21 2 自举获取关系的方法 还有些研究者采用滚雪球式的方法自动获取实体关系。一般的过程是先给定几 个属于某个二元关系类别的种子二元关系，然后就能在文本中获取更多的该类关系 二元关系模式, u - - 元关系。 国内中科院计算所姜吉发等用这种方法研究了关系模式的自动抽取，他提出了 一种自举的二元关系和二元关系模式的获耿方法b r p a m ( b o o t s t r a p p i n gr e l a t i o n a l p a t t e r n a c q u i s i t i o nm e t h o d ) 。b r p a m 的基本思想是：首先人工给出几个属于某个二 元关系类别的种了二元关系，然后到一个大的自由文本集合d 中找这些种子二元关 系的文本出现，并从这些文本出现中生成新的二元关系模式，然后用这些新的二元 关系模式到d 中找新的二元关系，阿从d 中找这些新的二，i 关系的文本出现，力 从这文本 i ；现中生成新t q - ：a 关系模式，如此循环，所得的二元关系模，数 | 1 越来越多，所得的二元关系也越术越多，直到达到某个终j i 条件为i l 。终i t ：条什 实体关系识别方法 可能是用户设定的某个固定的循环次数，也可能足新的二元关系模式或二元关系不 再n d i ：i 。 但是这种方法也有明显的缺点就是容易造成错误累积，如果在某次循环时引入 了质量不高的模式，则可能在下次循环时在该模式的指导下获得错误的二元关系， 而错误的二元关系在下次循环时又会生成错误的模式。所以，在每次循环时保证所 获得的模式或二元关系具有良好的质量是至关重要的。需要有一种方法来评估所获 得的模式或二元关系的质量，去掉那些质量不好的模式或二元关系。他在研究中分 别定义了模式和二元关系的可信度公式，在每次循环时，用来评估模式和二元关系 的质量，保证它们的质量。最后从实验结果来看，效果还是不错的，准确率达到了 9 3 ，d 回率也达到了7 9 。 图2 1 显示出了b r p a m 进行二元关系模式和二元关系获取的基本做法 8 。 图2 1b r p a m 进行二元关系模式和二元关系获取的基本做法 国外的s u r g e yb r i n l 2 。】提出了d i p r e 算法从w e b 网页中进行二元关系抽取，其 算法是 由用户给出一个小的样例r ； 存待测文档中找出所有和r 相同或近, f 以, f l t l 等的r 生成抽取模型 4 抽取结果加到r ； 5 跳到2 ，直至r 足够大； d i p r e 算法不需要专门的命名实体u 别软件支持，只是在模式表示1 1 ，列实体类 皋于动态粒度思想的实体关系识别方法研究 a u t h o r 和t i t l e 的字符串组成结构作了必要的约束。 哥伦比亚大学的e u g e n ea g i c h t e i n ，l u i sg r a v a n o 在基于d i p r e 算法上做了一 个s n o w b a l l 的系统口2 l 用来在大规模真实文本中抽取关系，同时为了防止噪声的累 积，加入了信任度评测，自动评测元组和模型的信任度，每次取信任度较高的元组 和模型进行下一次循环，这样就能尽可能的避免噪声，提高系统的性能。s n o w b a l l 系统的主要结构如图2 2 所示 2 2 】： 图2 2s n o w b a l l 系统的结构图 2 2 本文采用的方法 以上介绍的研究方法，在特征的选择上，有一个共性，就是特征的粒度大小是 固定的，即采用了统一粒度的特征。特征如果和待解决问题的粒度大小不匹配，问 题就没有精确解，我们换个思路，应用动态粒度思想，也就是特征的粒度大小是变 化的。如果这个特征粒度大小和问题不匹配，那就换下一个来试，依此类推，直到 问题解决了或者所有特征都使用了。这样，特征的粒度是可以变化的，待解决的集 合也就是变化的，而传统的统一粒度特征方法，待解决的集合是不会变化的。每次 新的特征解决的都是上个特征识别后的不能解决的问题集合，这个集合会越来越 小，直到这个集合为空，也就是所有问题都解决了，或者所有不同粒度特征都使用 了。这个方法的新颖之处就在于采用多个粒度大小不同的特征术逐个匹配问题，这 样漏识别的情况会大人减小，在t j 别效果上会比j 帅1 方法好。 粒度计算 第三章粒度计算 什么是粒度，顾名思义，就是取不同大小的对象。也就是说，将原来“粗粒度” 的大对象分割为若干“细粒度”的小对象，或者把若干小对象合并成一个大的粗粒 度对象，进行研究 2 3 】。 31 粒度计算 粒度计算( g r a n u l a rc o m p u t i n g ) 是信息处理的一种新的概念和计算范式，覆盖 了所有有关粒度的理论、方法、技术和： 具的研究m 2 5 , 26 1 。凡是在分析问题和求解 问题中，应用了分组、分类和聚类手段的一切理论与方法都属于粒度计算的范畴。 粒度计算的内容包括两个主要的方面，一个是如何构建信息粒度，另一个是如何利 用粒度去计算。前者处理粒度的形成、表示、和语义解释，而后者处理怎样利用粒 度计算去求解问题。例如，信息粒子的大小，信息粒度的形成，信息粒度的语义解 释，信息粒度的运算，信息粒度之间及其与外部环境的关系等口“。 颗粒的解释主要集中在颗粒结构的语义方面，它说明了两个对象为什么要归入 一类的问题。典型地，在一个颗粒内的所有元素是通过它们的不可分辨性、相似性、 近似性或作用一致性被划分存起的。进步讲，信息粒度是依赖于有效的知识的。 在粒度结构里，依据有效的信息，研究是否两个对象应当被放入同一个颗粒的决策 规则是相当必要的。换句话晓，它必须提供诸如不可分辨性、相似性和近似性等概 念的必要的语义解释，也必须研究从研究对象的不同粒度中衍生出来的粒度结构。 信息颗粒的形式和表示处理粒度结构的规则问题，它们说明了两个对象怎样放入同 一颗粒的问题。为有效地构造信息颗粒，这些规则必须研究和探讨。 类似地，粒度计算也必须从语义和规则两个方面进行研究 2 8 j 。一方面，粒度计 算必须解释颗粒之间的不同关系，比如近似关系、依赖关系和交关系，进而定义和 解释对信息颗粒的操作。另一方面，它也需要为粒度计算设计一些模型和工具，比 如近似、因果以及演绎推理等等。 目前有关粒度计算的理论与方法，主要有三个。一个是z a d e h l 2 42 5 埘1 的“词计 算理论( t h e o r yo f w o r k sc o m p u t i n g ) ， 。是p a w l a k 2 9 ，3 0 1 的“粗糙集理论”( t h e o r y o f r o u g hs e t ) ，还有一个是“商空刚理论”川( t h e o r yo f q u o t i e n ts p a c e o 基于动态粒度思想的实体关系识别方法研究 31 1 词计算理论 z a d e h 在讨论模糊信息粒度理论时，提出人类认知的三个主要概念，即粒度 ( g r a n u l a t i o n ) 、组织( o r g m l i z a t i o n ) 、因果( c a u s m i o n ) ( 粒度包括将全体分解为部 分，组织包括从部分集成为全体，因果包括因果的关联) 。并进一步提出粒度计算。 他认为，粒度计算是一把大伞它覆盖了所有有关粒度的理论、方法沦、技术和工具 的研究。指出：“粗略地况，粒度计算是模糊信息粒度理论的超集，而粗糙集理论 和区间计算是粒度数学的子集”1 2 4 1 。 z a d e h 认为人类在进行思考、判断、推理时主要是用语言进行的，而语言是一 个很粗的“粒度”，如我们说“九寨沟的风景很美”，其中“很美”这个词就比较“笼 统”，也就是说其粒度很粗，如何利用语言进行推理判断，这就是要进行“词计算”， 早在二十世纪六十年代z a d e h 提出模糊集理论，就是“词计算”的雏形。沿z a d e h 的模糊集理论的方向，用模糊数学的方法进行有关粒度计算的方法和理论的研究， 就构成“粒度计算”的一个非常重要的方法和方向。这也是人们比较熟悉的一个方 法1 23 1 。 令是划象u 上的一个变量，在x 的取值l 二的归纳约束用x i s r 月来表示，r 是个约束关系，i s r 是一个可变的联系词，r 是一个取值独立的变量，它定义了r 约束x 的方式。例如，相等、可能、相似，模糊等约束。例如，一个相等约束， r 二e 是由x i s ea 所给出的，意思就是x = a 。一个可能性约束r = b l a n k ，是由x i sr 给出的，r 是的一个- j 月z 。k 性分配。由于一般性约束的引入，一个颗粒可以用一个 模糊集合来定义： g = ix i s r 尺 。 由于约束的类型不同，可以获得不同的颗粒分类。对一个简单的颗粒，我们可 以通过考虑约束的并来获得一个笛卡儿积粒度集合。 可以用自然语言的词汇来标记一个颗粒，这是用词进行计算的基础。作为模糊 逻辑的核心思想，c w 可以处理一下形式的模糊： j f x i s l lat h e n 】7 i s r 2b ， 这里的r l 和r 2 可能不是同类型的约束， 尽管它也经常是相同的。个模糊 i f - t h e n 枷则可以用个模糊圈来解释。崩模糊i f t h e n 规则! 哎者模糊幽【i j 以进行演绎 摊理。 n 粒度计算 3 12 粗糙集理论 波兰学者p a w l a k 在二十世纪八十年代，提出了粗糙集理论，他提出一个假设： 人的智能( 知识) 就是一种分类的能力，这个假设可能不是很完备，但却非常精炼。 在此基础上提出，概念可以用论域中的子集来表示，于是在论域中给定一组子集族， 或浇给定一个划分( 所渭划分，是指将x 分成两两不相交的子集之并) 。从数学上 知道，给定x 上的一个划分，等价于在x 上给定一个定价关系r 。p a w l a k 称之为 在论域上给定了一个知识基( x ，r ) 。然后讨论一个一般的概念x ( x 中的一个子 集) ，如何用知识基中的知识来表示，就是用知识基中的集合的并来表示。对那些 无法用( x ，r ) 中的集合的并来表示的集合，他借用拓扑中的内核和闭包的概念， 引入r 下近似r ( x ) ( 相当- j 二x 的内核) 和r 上近似r ( x ) ( 相当于x 的闭包) ，当 r 一( x ) r 一( x ) h q ，就称x 为粗糙集，从而创立了“粗糙集理论”1 2 3 j 。粗糙集理论主 要处理信息粒度的近似方面的问题。目前粗糙集理论己被广泛应用于各个领域，特 别是数据挖掘领域，以集合的近似为基础，在信息表里可以进行数据分析和挖掘任 务，例如属性约简，相关性分析和决策规则的学习，并获得成功吲。 313 商空间理论 基于粗糙集理论的模型，其论域只是简单的点集，元素之间没有拓扑关系。为 了解决论域元素存在有拓扑关系的情况，即论域是个拓扑空问，张铃、张钹提出 了模糊商空问理论川。 他们认为概念可以用子集来表示，不同粒度的概念就体现为不同粒度的子集， 一簇概念就构成空间的一个划分商空间( 知识基) ，不同的概念簇就构成不同 的商空间。故粒度计算，就是研究在给定知识基上的各种子集合之间的关系和转换。 以及对同 问题，取不同的适当的粒度，从对不同的粒度的研究中，综合获取了对 原问题的了解。这种对粒度的理解与模糊集对粒度的理解不完全一样。 商空间模型用个三元组来表示，即( x r t ) ，其中x 是论域，f 是属性集， t 是x 上的拓扑结构。当我们取粗粒度时，即给定一个等价关系r ( 或醴是一个划 分) ，于是我们说得到一个列应于r 的商集汜为【x ，它对应于的三元组为 ( x ， f ， 1 、 ) ，称之为对应于r 的商空问。商空问理论就是研究各商空问之间的关 系、各商空间的合成、综合、分解和在商宁问中的推理。 在这个模型下，可建立对应的推理模型，并有如下性质。 基十动态粒度思想的宴体关系识别方法研究 a 商空间模型中推理的“保假原理”( 或“无解保持原理”) 。 b 商空间模型中推理合成的“保真原理”。 所谓“保假原理”是指若命题在粗粒度空间中是假的，则该命题在比它细的商 空问中一定也无解。 所谓“保真原理”是指，若命题在两个较粗粒度的商空间中是真的，则( 在一 定条件下) 在其合成的商空间中对应的问题也是真的。 这两个原理在商空间模型的推理中起到很重要的作用，如若我们要对一个问题 进行求解，当问题十分复杂时，常先进行初步分析，即取一个较粗粒度商空间，将 问题化成在该空间上的对应问题，然后进行求解，若得出该问题在粗粒度空问中是 无解，则由“保假原理”，立即得原问题是无解的。因为粗粒度