（计算机软件与理论专业论文）基于网络抱团发现的命名实体关系抽取.pdf

顾士学位论文 m s t e r st h e s i s 摘要 关系抽取是是信息抽取研究领域的一个重要课题。关系抽取的目的是从文本中 发现两命名实体间的关系。近年来，该技术得到越来越多的关注，被运用到各个领 域中，如：信息抽取，本体构造，问答系统，生物技术等。 自从1 9 9 5 年，第六届信息理解会议( t h es i x t hm 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 em u c 一6 ) 提出关系抽取这个概念以来，在命名实体关系抽取方面已经开 展了大量的研究工作，但绝大部分研究都是基于有导学习的。有导学习方法最大的 问题在于需要花大量的时间去标注足够数量的训练语料，此外系统很难从一个领域 移植到另外一个领域中。为了突破有导学习方法中的限制，无导方法被提出来。但 是，目前无导方法仍然存在一些问题：( 1 ) 命名实体对一般是通过定范围内的上 下文来进行描述地，但是如何设置上下文窗口大小，直以来都没有一个客观的标 准；( 2 ) 在命名实体对的聚类过程中，往往存在着很大的噪音，如何能在噪音存在 的情况下保证较好的聚类效果：( 3 ) 命名实体对之间的语义关系是具有层次结构的， 如何描述这种层次结构的关系。 针对以上问题，本文尝试性地提出了一种基于网络化数据挖掘的命名实体对关 系抽取的方法。在该方法中，我们采用了如下三种关键技术：1 、利用网络化结构 来表示命名实体对；2 、基于抱团现象的命名实体对聚类；3 、基于语义层次的命名 实体关系描述。特别值得一提的是在关键技术l 中我们着重解决了实体对上下文窗 口大小的设置的问题，在关键技术2 中我们创新性的提出了一个如何在带权网络中 发现抱团现象的方案。 为了验证提出的命名实体对关系抽取方法的可行性和有效性，我们以半年人民 日报为语料进行实验。结果表明，本文提供的方法不但可以以较高的准确率发现命 名实体间的语义关系，而且能够恰当地标注命名实体间的语义关系。 关键词：信息抽取；网络化数据挖掘；命名实体对；语义关系；聚类；介数 a b s t r a c t r e l a t i o ne x t m d i o na m o n gn a m e de n t i t j e s 州r ) i sam a j o rt a s ki i lt h er e s e a f c ho f i n f o m l a t i o ne x t m c t j o n ( i e ) 1 1 1 eg o a lo fn ri st o 缅dr c l a t i o n s h i p sb c 咐e e nm on 锄e d e n t i t i e s 疗d mt e x tc o n t e t s r e c e n t l y ，nh a sr e c e i v e dm o r ea i l dm o r ea n e n t i o ni nm a l l y a r e a s ，e g ，i n f 0 皿a t i o ne x t r a c t i o n ，o n t o l o g yc o n s t m c t j o n ，q u e s t i o n a n s w e i i n gs y s t e m ， a n db i o i n f o 肌a t i c s c t c s i n c et l l e c o n c c p to fr e l a t i o ne x t r a d i o nw a si n t r o d u c e di m u c6 ( d e f c n s e a d v a i l c e dr c s c a r c hp r o j e c t sa g c n c y ，1 9 9 5 ) ，t h e r ch a sb e c nc o 鹏i d e r 曲l ew o r ko n s 叩e r v i s e dl e a r n i n go fr e l a t i o np a t t e m s ，u s i n gc o 邛o r aw l l i c hh a v cb e e n 枷o t a t e dt o i i l d i c a t et h ei 椭a t i t ob e “t r a d e d h o w c v c r ，m a i l u a l l yt a g 毋n go fl a r 髀砌o u n t so f t r a i i l l gd a t ai sv e r yt i l l l e 哪n s u m i n g ；f h n l l e 珊o r e ，i ti sd i 伍c i l l tf o ro n ee x 扛a c t i o ns y s t e m t ob ep o n c dt o 卸o t h c r0 n e d u et om e1 i n l i t a t i 衄sa b o v c ，u n s u p e r v i d 印p r o a c h e sw e r e p u tf o r w a r d f o f 也eu n s l l p e r v i s c da p p r o a c h ，w en o t i c e ds o m ep r o b l c m s ( 1 ) t h en 锄c d c n t i t yp a i r sa r ea w a y sd e s 丽b e db yt t i cc o n t e x t h o w e v e r ，t h e r ei sn 0p r o p e ri n e t h o dt o d e f i n et l l es i z eo ft h ec o n l c x tw i l l d o w ；( 2 ) h o wt og e tag dr e s u l to fd u s t e r i n gi l lt h e c a s eo fn o i s ee x i s t i n g ；( 3 ) h o wt on 栅et h er c l a t i o n s 咖o n gn 锄e de n t 谢e sw i t h h i c r a r c h y i nt l l i sp a p e r ，w ep r o p o s e da nu s u p e i s e dm e t h o df o r 亿l a t j o nc x t r a c t i o n t h e m e t h o dd r a w s0 nt h el a t e s t 觚i t si l lt h ef i e l do fn e t w o r k e dd a t am i n i i l g 1 1 l r c ck e y t e c h n o l o g i e sa r ea d o p t e di l l 也i sm e t h o d ：( 1 ) n e t w o r kr e p r e s e m a t i o n so fn a m e de n m y p a i r s ；( 2 ) e i l t i t yp a i r sd u s t e 咖gb yd i s c o v e 由gc o m m 朋i t i e s ；( 3 ) r e l a t i o nd c s c i i p t i o n b a s e do nh i e r a r c h y e s p e c i a l l y ，w es o l v et h ep r o b l e mo fd e f i l l i gt h es i z eo fc o n t e x t w i n d o w i k c yt e c h 0 1 0 9 yo n ea n dd i s c 0 v e 血gt h ec o 衄u i l i t i e si i law e i g h t c dn e t w o r k i nk e yt e c h n o l o g yt 、o o u re x p e r i m e t su s i n gh a l fy e a ro fn e w s p a p e r sf e v e a l sn o to n l yt h a tt t l er e l a t j o n s 枷衄gn 栅c dc n t i t i e sc o u l db ed e t e c t e dw i t t ih i 曲p r c c i s i o n ，b u ta l s ot h a t 印p r 叩r i a t e l a b e l sc o u l db ea u t o m a t i c a l l yp r o v i d e df o rm er c l a t j o n s k qw o r d s ：i n f b n a t i o ne x t r a c t i o n ；n e t w o _ r k e dd a t am i n i n g ；n 锄e de n t i t yp a i r ；r e l a t i o n ； c l u s t e r i n g ；b e “v e e n n e s s 硕士学位论文 m a s t e r st h e s i s 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工作 所取得的研究成果。除文中已经标明引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体，均已在 文中以明确方式标明。本声明的法律结果由本人承担。 作者签名： 苍品 日期： 口6 年6 7 月智日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即：学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库进 行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 作者签名： 杏晶 日期： 口0 年0 月g 日 导师签名： 日期：年月日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人的 学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中的 规定享受相关权益。园意逾塞埕窒卮溢蜃! 旦主生；旦= 生；旦三生蕉查! 作者签名：套晶 日期：o6 年g 月留日 导师签名： 日期：年月日 硕士学位论文 m a s t e r st h e s i s 第1 章绪论 1 1 命名实体对语义关系抽取的研究意义 随着计算机的普及以及互联网( w w w ) 的迅猛发展，大量的信息以电子文档 的形式出现在人们面前。为了应对信息爆炸带来的严重挑战，迫切需要一些自动化 的工具帮助人们在海量信息源中迅速找到真正需要的信息。在这种背景下，信息抽 取( 1 n f 0 哪a t i o ne 】【t 豫c t i o n ) 研究产生了。 信息抽取系统的主要功能是从文本中抽取出特定的事实信息( f a c t u a l i 1 1 陆m a t i o n ) 。比如，从新闻报道中抽取出恐怖事件的详细情况：时间、地点、作案 者、受害者、袭击目标、使用的武器等；从经济新闻中抽取出公司发布新产品的情 况：公司名、产品名、发布时间、产品性能等；从病人的医疗记录中抽取出症状、 诊断记录、检验结果、处方等等。通常，被抽取出来的信息以结构化的形式描述， 可以直接存入数据库中，供用户查询以及进一步分析利用。 信息抽取虽然需要对文本进行一定程度的理解，但与真正的文本理解( t e x t u n d e r s t a l l d i n g ) 还是不同的。在信息抽取中，用户一般只关心有限的感兴趣的事实 信息，而不关心文本意义的细微差别以及作者的写作意图等深层理解问题i n 。因此， 信息抽取只能算是一种浅层的或者说简化的文本理解技术。 命名实体是文本中基本的信息元素，是正确理解文本的基础。狭义地讲，命名 实体是指现实世界中的具体的或抽象的实体，如人、组织、公司、地点等，通常用 唯一的标志符( 专有名称) 表示，如人名、组织名、公司名、地名等。广义地讲， 命名实体还可以包含时间、数量表达式等。至于命名实体的确切含义，只能根据具 体应用来确定。比如，在具体应用中，可能需要把住址、电子信箱地址、电话号码、 舰船编号、会议名称等作为命名实体。 命名实体之间语义关系的抽取是信息抽取领域的一项基础性研究，其目的是从 文本中找到两命名实体间的语义关系。例如，若文本中存在句子“6 月2 1 日，在国 务院全体会议上，曾荫权被任命为中华人民共和国香港特另q 行政区行政长官”，则 通过命名实体语义关系抽取，应该得到三元组( 曾荫权，香港特别行政区，行政长 官) ，其中“曾荫权”为命名实体1 ，“香港特别行政区”为命名实体2 ，“行政长官” 为命名实体1 与命名实体2 问的语义关系。 硕士学位论文 m a s t e r l st h e s l s 除信息抽取外，命名实体间语义关系抽取技术还被广泛地应用到许多其它研究 领域，如：信息检索( y a n g a r b e re ta 1 ，2 0 0 0 ) 【2 】、问答系统( r a v i c h a n d r a i l ，2 0 0 2 ) 【3 1 、本 体的构建( n a v i g l i 锄dv c l a r d i ，2 0 0 4 ) 1 4 】、生物技术( h u a n ge ta 1 ，2 0 0 4 ) 【5 1 等。 1 2 国内外研究状况 从自然语言文本中获取结构化信息的研究最早开始于2 0 世纪6 0 年代中期，这 被看作是信息抽取技术的初始研究，它以两个长期的、研究性的自然语言处理项目 为代表i 6 1 。 美国纽约大学开展的工j n g i l i s t i cs t r i n g 项目1 7 l 开始于6 0 年代中期并一直延续到 舳年代。该项目的主要研究内容是建立一个大规模的英语计算语法，与之相关的应 用是从医疗领域的x 光报告和医院出院记录中抽取信息格式( i n f o 】眦a t i o n f o 册a t s ) ， 这种信息格式实际上就是现在我们所说的模板( t e m p l a t c s ) 。 另一个相关的长期项目是由耶鲁大学r o g c r s c h 孤k 及其同事在加世纪7 0 年代 开展的有关故事理解的研究。由他的学生g e f a l dd ej o n g 设计实现的f r u m p 系统【8 l 是根据故事脚本理论建立的一个信息抽取系统。该系统从新闻报道中抽取信息，内 容涉及地震、工人罢工等很多领域或场景。该系统采用了期望驱动( t o p d o w n ，脚 本) 与数据驱动( b o t t 叫一u p ，输入文本) 相结合的处理方法。这种方法被后来的许 多信息抽取系统采用。 从2 0 世纪8 0 年代末开始，信息抽取研究蓬勃开展起来，这主要得益于消息理 解系列会议( m u c ，m 鹤s a g eu n d e r s t 孤d i i l gc o n f e r c n c e ) 的召开。正是m u c 系列 会议使信息抽取发展成为自然语言处理领域一个重要分支，并一直推动这一领域的 研究向前发展。 从1 9 8 7 年开始到1 9 9 8 年，m u c 会议共举行了七届，它由美国国防高级研究 计划委员会( d a i u p a ，t h ed e f e n s ea d v 锄c e dr e a r c hp r o j e c t sa g e n c y ) 资助。m u c 的显著特点并不是会议本身，而在于对信息抽取系统的评测【9 1 。只有参加信息抽取 系统评测的单位才被允许参加m u c 会议。在每次m u c 会议前，组织者首先向各 参加者提供样例消息文本和有关抽取任务的说明，然后各参加者开发能够处理这种 消息文本的信息抽取系统。在正式会议前，各参加者运行各自的系统处理给定的测 试消息文本集合。由各个系统的输出结果与手工标注的标准结果相对照得到最终的 评测结果。最后才是所谓的会议，由参与者交流思想和感受。后来，这种评测驱动 的会议模式得到广泛推广，如1 9 9 2 年开始举行的文本检索会议t r e c 等。 在删c 中，衡量信息抽取系统的性能主要根据两个评价指标：召回率和准确率 【1 0 l 。召回率等于系统正确抽取的结果占所有可能正确结果的比例；准确率等于系统 正确抽取的结果占所有抽取结果的比例。为了综合评价系统的性能，通常还计算召 回率( r e c ) 和准确率( p r e ) 的加权几何平均值，即f 指数，它的计算公式如下： f m e a s u r e =延掣z ! ：壁j ! 罂：丝竺 帖e 胁) 2 p 肥j + r e c 其中，b e t a 是召回率和准确率的相对权重。 于l 时，准确率更重要一些；b e t a 小于l 时， b e t a 取值一般为l 、l 2 、2 。 b e t a 等于1 时，二者同样重要；b e t a 大 召回率更重要一些。在m u c 系列会议中， m u c 系列会议对信息抽取这一研究方向的确立和发展起到了巨大的推动作用。 删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 ) 评测会议。这项评测从1 9 9 9 年7 月开始酝酿，2 0 0 0 年1 2 月正式开始启 动。这项评测旨在开发自动内容抽取技术以支持对三种不同来源( 普通文本、由自 动语音识别a s r 得到的文本、由光学字符识别o c r 得到的文本) 的语言文本自动处理， 研究的主要内容是自动抽取新闻语料中出现的实体、关系、事件等内容，即对新闻 语料中实体、关系、事件的识别与描述。最近一次评测( a c ep h a s e2s u 黜re v a l u 8 t i o n ) 主要有两大任务：实体识别与跟踪( e d t ，e n t i t yd e t e c t i o na n dt r a c k i n g ) 、关系 识别与描述( r d c ，r e l a t i o nd e t e c t i o n8 n dc h a r a c t e r i z a t i o n ) l l l j 。 与舶c 相比，目前的a c e 评测不针对某个具体的领域或场景，采用基于漏报( 标 准答案中有而系统输出中没有) 和误报( 标准答案中没有而系统输出中有) 为基础 的一套评价体系，还对系统跨文档处理( c r o s s d o c u m e n tp r o c e s s i n g ) 能力进行 评测。这一新的评测会议将把信息抽取技术研究引向新的高度。 中文信息抽取方面的研究起步较晚，主要的研究工作集中在对中文命名实体的 识别方面，在设计实现完整的中文信息抽取系统方面还处在探索阶段。其中，国立 台湾大学( n a t i o n a lt a i w a nu n i v e r s i t y ) 和新加坡肯特岗数字实验室( k e n tr i d g e d i g i t a ll a b s ) 参加了m i j c 一7 中文命名实体识别任务的评测f 1 习1 1 3 1 。i n t e l 中国研究中 心的z h a n gy i _ m i n 和z h o uj o ef 等人在a c l 一2 0 0 0 上演示了他们开发的一个抽 取中文命名实体以及这些实体间相互关系的信息抽取系统，该系统利用基于记忆的 学习( m b l ，m e m o r y b a s e dl e a r n i n g ) 算法获取规则用以抽取命名实体及它们之间 的关系1 1 4 j 。 自从1 9 9 5 年，第六届信息理解会议( t h es i x mm e s s a g eu n d e r s t 姐d i n gc o n f e r e n c e m u c 6 ) 【1 5 】提出关系抽取这个概念以来，在命名实体关系抽取方面已经开展了大量 的研究工作，但绝大部分研究都是基于有导学习的。k e m e lm e t l i o d s ( z e l e n k oe ta 1 ， 2 0 0 2 1 1 1 6 l 是其中比较有代表性的一种方法。在该方法中，系统通过学习已经标记好 的语料库获取规则，经训练后的系统根据规则，对新文本进行浅层句法分析，并得 到命名实体间的语义关系。该方法的最大问题是需要花大量的时间去标注足够数量 的训i 练语料。同时，命名实体间的关系只能为事先定义好的几种语义关系，而不能 自动获取新的语义关系。 为了突破有导学习方法的限制，弱指导的方法被提出来。其中比较有表性的为 b 血( 1 9 9 8 ) f 切、a g i c h t e i n ( 2 0 0 0 ) 【1 引、s u d o c 2 0 0 3 ) 1 1 9 】等。在这些方法中，系统预先定义 一些关系和关系实例作为种子，然后通过机器学习，发现一些新的关系模板。这种 方法的主要问题在于如何定义那些初始的关系和关系实例的集合。 2 0 0 4 年，通过无指导的方法实现命名实体对语义关系的抽取被提出来。其中具 有代表性的工作有h a s e g a w a ( 2 0 0 4 ) 【2 0 1 、c h j i n x i u ( 2 0 0 5 ) f 2 l 】等。无导的方法主要 基于以下假设：拥有相同语义关系的实体对，其上下文环境较为相似，并且可以在 这些上下文中找到一个具体的词汇来表示这种语义关系。在这种思想指导下，无指 导名实体对中语义关系的抽取过程被划分为3 个部分：( 1 ) 命名实体对的形式化描 述；( 2 ) 命名实体对的聚类；( 3 ) 标注各个命名实体对类中命名实体间的语义关系。 1 3 存在的问题及关键技术 1 3 1 存在的问躁 目前，无导命名实体关系抽取还处于起步阶段，仅有很少的研究成果发表。在 研究过程中，我们发现目前无导命名实体关系抽取中存在的主要问题有： 1 、上下文范围的确定。目前无导命名实体关系抽取都是基于以下假设：命名 实体对周围一定范围的上下文可以为命名实体对的定义提供较为充分的语言信息， 上下文环境可以用来定义命名实体对。因此，无论是命名实体对关系的发现还是命 名实体对关系的标注都是基于上下文环境的。上下文范围确定的是否合适，直接影 响着实验结果。而传统方法主要是通过经验值来确定上下文范围，但是由于实验语 4 顾士学位论文 m a s t e r st h e s i s 料不同，经验值的可靠性值得商榷。 2 、命名实体对的选取过程中产生的“噪音”。在无导命名实体关系抽取过程中， 我们认为如果两命名实体在文本中距离很近且结构紧凑，即两命名实体间的词汇数 目较少且在同一句子中，则表明这两命名实体联系紧密，它们之间存在着一定的语 义关系。我们定义这样的两命名实体组成一个命名实体对。但根据定义得到的命名 实体对存在着很大的噪音，即许多命名实体对所包含的两命名实体间不存在明显的 语义关系。这些“噪音”对传统的聚类方法提出了挑战。 部分学者也认识到了该问题，不过他们没有把研究重心放在聚类方法的选取 上，而是力图减少这种“噪音”。但是，都存在一定的问题。如：h a s c g a w a ( 2 0 0 4 ) 通过去掉出现频率较低的命名实体对来减少“噪音”，可是与此同时他也遗漏掉许 多有效的命名实体对；c h j i n x j u ( 2 0 0 5 ) 从a c e 语料中提取出存在语义关系的命 名实体对实例来达到消除噪音的目的，但是实际情况下，我们无法事先得知哪些命 名实体对拥有语义关系，哪些命名实体对不存在语义关系。 3 、语义关系的发现及其标注。目前的命名实体语义关系的发现是通过对命名 实体对聚类得到的。在聚类过程中，大多数研究者采用的是非层级聚类的方法。受 此影响，在关系标注环节，往往是通过从一类命名实体对的上下文中提取重要词汇 来标注该类命名实体对两命名实体间的语义关系。但是，我们认为命名实体对两命 名实体间的语义关系应该呈现为一个树型结构，观测者有权利根据自己的需要来决 定观察不同粒度的语义关系。因此，在聚类过程中采用非层级聚类方法是不合适的。 同时，由于在树型结构中所处层次较高的语义关系较为抽象，是否能在上下文中找 到合适的词汇来描述它值得探讨。 1 3 2 关键技术概述 针对以上问题，我们尝试性地提出了一种基于网络化数据挖掘的命名实体对关 系抽取的方法。该方法包括以下三种关键技术； l 、命名实体对的网络化表示 该技术的提出使网络化数据挖掘技术运用于命名实体关系抽取成为可能。在命 名实体对的网络化表示过程中，我们利用命名实体对的上下文信息来对命名实体对 进行描述，在此基础上计算命名实体对问的相似度，并构建出命名实体对的网络结 构。 在这里仍然存在着如何客观的定义命名实体对上下文窗口大小的问题。本文考 虑到上下文词汇与命名实体对的相对位置的不同，利用信息增益的方法对上下文词 汇赋予不同的权值，在此基础上确定命名实体对上下文窗口的大小、构造命名实体 对上下文特征向量。这种做法较为客观的反映了人们的认知过程，即上下文对命名 实体对的描述能力随着相对位置由近及远而逐渐递减，即通过已知上下文推断空缺 词语时，近距离的上下文在推断中所起的作用比远距离的上下文更有价值。同时， 也为上下文窗口大小的设置提供的有效的依据。 2 、基于网络抱团发现的命名实体对聚类 该技术的提出解决了命名实体对的选取过程中产生的“噪音”问题。即使命名 实体对不包含明显语义关系或者重要语义关系，我们仍将其保留，并在聚类过程中 根据其与重要语义关系之间联系的紧密程度，将它们归类到各种主要的语义关系 中。“噪音”不对聚类效果产生太大影响。另一方面，该聚类方法属于层级聚类， 可以发现不同层次的语义关系，或具体，或抽象。 3 、基于语义层次的命名实体关系描述 该技术的提出解决了对不同层次的语义关系进行描述的问题。对于层次结构 中，所处层次较底的语义关系，其关系比较具体，通过上下文词汇来描述；对于在 抱团层次结构中，所处层次较高的语义关系，其关系比较抽象，因此从现有语义资 源h o _ 【v n e t 中提取一组有序的义元来描述。 1 4 文本组织 笫l 章是绪论，介绍了命名实体对语义关系抽取的研究意义和相关概念，命名 实体对关系抽取的国内外研究情况，命名实体对语义关系抽取研究存在的若干问题 以及为了解决这些问题所提出的几种关键技术。 第2 章至第4 章是对提出的关键技术的详细介绍。第2 章研究了命名实体对的 网络化表示方法；第3 章研究了基于网络抱团发现的命名实体对聚类方法；第4 章 研究了基于语义层次的命名实体关系描述方法 第5 章介绍了在以上关键技术的支持下所进行的实验，并对实验结果进行了评 估。同时，讨论了该方法中尚存在的一些问题以及解决思路。 第6 章是全文内容的总结。 项士学位论文 m a s t e r st h e s i s 第2 章命名实体对形式化表示 2 1 向量空间模型( v s m ) 介绍 在自然语言处理的各个研究领域，对文本各级语言单位进行形式化的表达是一 个既基础，而又重要的问题。而形式化表达其根本目的就在于力图将各种无结构化 的文本单元转换成为便于计算机处理的结构化表达形式，以支持后续一系列语言处 理应用的需要。 向量空间模型( v s m ) 作为文本单元表达的一种经典模型，自6 0 年代末s a l t o n 提出以来，就一直受到众多研究人员的关注和推崇。当然，这与它表现出来的最大 优势，即表达简单，应用方便的特性是密不可分的。 在v s m 模型中，文本的各级语言单元被映射成n 维向量空间中的对应向量， 而各个向量则通过文本中的特征的重要度来形式化表达。值得注意的是，这里所谈 到的文本中的特征既可以指文本中所包含的字、词，也可以是更加复杂的特征，如 概念、句法结构等，至于具体选用什么样的特征往往与实际的应用需求有关，不可 一概而论。 任意给定一个文本单元d ( 如句子、段落等) ，我们可以建立该单元的向量空间 模型，将单元d 映射成文本特征的权值向量v d ，v d = ( w d l ，w d 2 ，w d n ) ； 这里，n 表示文本中选用的不同特征的总数，w d i 表示第i 个特征在文本单元d 中 的权值。关于w d i 的计算方法很多，如t f 法、t p i d f 法、m u t u a li n f o r m 舶n 【2 2 l 法等。 此外，文本单元之间的语义相似度可以通过计算它们各自对应的特征向量的向量距 离来度量。常用的度量方式有向量之间的内积、向量之间的夹角余弦、向量之间的 欧拉距离等。这里，仅以向量之间的欧拉距离为例来具体介绍向量距离的度量方法。 设有两个m 维的特征向量x i 、x j ，x i = ( x mx b ，x 蛔) 、x j = ( x i l ，x i 2 ，- ，x i m ) ， 则可定义x i 与x j 之间的欧拉距离d “如公式2 1 所示： d d =再j 7 ( 2 1 ) 2 2 潜在语义分析方法介绍 在w e b 上对某个特定领域的信息进行采集，首先需要让采集系统了解这个领域 的精确描述。通常是给定一个样本文档集合，采用合适的代数模型进行描述。 传统的检索模型描述中【2 3 l ，无论布尔模型、向量空间模型( v e c t o rs p a c em o d e l v s m ) 还是概率模型，尽管实现方法上有很多差异，但对文本的过滤、检索等操作都 是通过文档之间的词匹配来实现的。由于词具有同义性、多义性和使用上的概念相 关性，仅仅通过字面的匹配不能准确地进行各种功能操作。 从1 9 8 8 年开始，d u m a i s 等进行了一系列的研究，提出了新的信息检索代数模 型，主要是为克服现有的查询词与文档匹配检索技术的缺点而设计的f 2 4 1 在v s m 基础上，利用线性代数的知识，通过矩阵的奇异值分解( s i n g u l a rv a l u e d e c o m p o s i t i o n ，s v d ) 来进行潜在语义索引的方法，简称为l s i ( l a t e n ts e 腑n t i c i n d e x i n g ) 或者l s a ( l a t e n ts e 衄n t i ca n a l y s i s ) 。l s i 通过数学分析计算出文档 集合中潜在内涵的概念之间关系，通过潜在概念集表示所有的概念空间，减少了概 念表示之间的模糊性，避免了v s m 中各维之间概念正交的假设。它把观测到项文 档关联数据的不可靠性看作是一种统计问题，认为在数据中存在一种潜在的语义结 构，这种结构由于检索词出现的多样性被干扰。l s i 使用统计技术去估计这些潜在 的语义结构，去掉这种“噪声”。针对一些t r e c 文档库的实验结果及一些初步的理 论分析，证实了l s i 的优越性。 通过特定领域样本文档集l s i 矩阵，获得样本集潜在语义的矩阵描述，可以很 好地计算文档之间内在内容的相关性，是目前在信息检索领域最具有前景的发展方 向之一嘲。 具体地说，在v s m 中，一个文档集合可以表示为一个盾_ r 7 的项文档矩阵几。， _ ，7 表示文档集合的文档数，脚表示文档集合中所有不同标引词的个数。每个不同的 标引词对应于儿m 的一行，每个文档对应于以m 的一列。对任意矩阵儿舶，由线 性代数的知识可知，它可分解为 爿= u 矿。 ( 22 ) 其中，从堤正交阵( 彬= 矿矿： 奇异向量矩阵；三= d i a g ( a 。，a 。， j r ) ，分别为矩阵也x 。奇异值对应的左右 a k ，a ，) ， ( a l ，a 2 ，a k ，a 。 硕士学位论文 m a s t e r st h e s i s 为a 的奇异值) 是递减排列的对角阵。在l s i 中通过取前五个最大的奇异值，而将剩 余的值设为o 来近似式( 2 ，2 ) 。 用以= 醵西表征文档集合中标引词和文档之间的关系，并在以的基础上进 行各种文档处理操作，就是隐含语义索引技术。文献【2 6 l 证明了以是以。最小二乘 意义上的最优七秩近似矩阵，即l s i 在经过把高维儿舶映射到低维m 后，最优 地保留了原项文档矩阵的表示能力。 尽管l s i 也是用文档中标引词来表示文档的语义的，但不同于传统的信息检索 代数模型，它并不是直接把标引词作为文档概念的可靠表示，而是通过奇异值分解 和取以的五秩近似矩阵，减少了文档中由于用词的多样性、词的同义性、多义性 在项文档矩阵儿m 中包含的“噪声”，更加凸现出文档和潜在内涵概念词的语 义关系。 与传统的信息检索代数模型相比，l s i 具有如下优点： ( 1 ) 以表示的不仅仅是所有标引词的简单出现频度和分布关系，而是所有标 引词在样本文档集合中的潜在语义关系，通过m 对样本文档集合的文档操作语义 精度得到较大的提高。 ( 2 ) m 采用一个低秩近似矩阵替代了项文档矩阵也舶，存储、计算效率上 得到较大的提高。 ( 3 ) a 不仅表示了标引词和文档之间的关系，而且包含了不同词之间的潜在关 系，可以表示标引词之间、文档之间、标引词与文档之间、查询伪文本和文档之间 的各种相似度，使用上更加灵活。 l s i 模型的主要问题是从高维盘x 。映射到低维以时如何确定膏值，目前还 没有比较成熟的理论。一方面希望七足够大，能够适合所有的潜在语义结构，但膏 太大会导致噪声，对于l s i 使用产生影响；如果量太小，则不能适应样本的误差 或其他次要的细节，保留下来的结构太少，无法把握运算的结果。实际中，往往需要 通过多次的试验，以选取针对具体文档集合操作效率最好的丘值。对于非常大的 文档集合，斤取1 0 0 3 0 0 比较适合【2 7 l 。中文文档集合l s i 初步测试基本吻合英文 的取值范围。另外，由于矩阵的s v d 分解对数据的变化较为敏感，文档集合任何的扩 充和变动会对l s i 模型有全局的影响，因此需要对l s i 模型整体重新计算，效率较 低。在文本集合变化较频繁的情况下，l s i 运用受到局限。 2 3 基于信息增益和潜在语义分析的命名实体对特征向量构造 2 3 1 命名实体对的上下文表现形式 本文认为，如果两命名实体在文本中距离很近且结构紧凑，即两命名实体间的 词汇数目较少且在同一句子中，则表明这两命名实体联系紧密，它们之问存在着一 定的语义关系。我们将这样的两命名实体组成一个命名实体对。 一个命名实体对的上下文环境作为一种可用资源，已经为该命名实体对的语义 提供了较为充分的语言信息。基于这一认识，本文用处于命名实体对两命名实体间 和命名实体对左、右一定范围内上下文环境的集合来描述这个命名实体对，更明确 地讲，这个集合就是命名实体对的定义。为了形象地描述，我们将它称为命名实体 对矩阵。在命名实体对矩阵中，每行是命名实体对的一个上下文环境，每列是命名 实体对上下文环境中相对位置上的上下文词语。命名实体对矩阵的形式为命名实体 对向量表示的进一步形式化提供了一种直接的表示方式。 2 3 2 上下文有效范围大小的确定 命名实体对周围一定范围的上下文可以为命名实体对的定义提供较为充分的 语言信息，如何确定上下文范围的大小是本节讨论的主要问题。 我们在这里采用鲁松( 2 0 0 2 ) 【硐中提到的信息论中信息增益的计算方法来实现上 下文有效范围的量化确定。 为了实现词语的消歧，鲁松( 2 0 0 2 ) 用词语左、右一定范围内上下文环境的集合 来定义这个词，并将它称为词矩阵( w o r dm a t r i 】【) 。在词矩阵中，每行是词语的一个 上下文环境，每列是词语上下文环境中相对位置上的上下文词语。 鲁松( 2 0 0 2 ) 基本思路是：将词矩阵形式化为一个信号系统，从实验语料中统计 的5o o o 高频词( 为获得基于语料库的上下文位置权重统计性平均结果，文中未对5 0 0 0 高频词作任何人为加工和词性上的限制) 作为核心词构成的词矩阵基础上，每个 词作为类，计算整个系统的统计不确定性( c t r o p y ) ，即为公式( 2 3 ) 中的h ( d ) ；其 次，计算在已知每个相对位置的前提下整个系统的不确定性，即：条件熵，公式( 2 3 ) 中的e ，。协p x h p ；二者求差后( 公式( 2 3 ”即为该相对位置对整个系统提供的 1 0 硕士学位论史 m a s t e r l st h e s i s 信息量。这个信息量作为信息增益就是该位置在整个系统中的权重。由此我们可以 凭借量化的权重来确定上下文范围选取的大小。计算公式如下： ，g p = h ( d ) 一k 荆日( d v ) ( 2 3 ) 公式( 2 3 ) 中的h ( d ) 为 日( d ) = 一。d p ) l o g zp ) ( 2 4 ) 其中 州) _ 龋 眨s ， 这里，e i 舡r c 功i 为50 0 0 高频词的在语料中出现的总频率；j - e f 矽i 为 在语料中出现的频率。 设核心词语( f o c i l s w o r d ) 的上下文形式为删d - 8 ，w d 7 、柑- 6 ，w d - 5 ，w d - 4 ，w d 3 ，w d 一2 ，w d l ，f b c u s w o r d ，w d + t tw d + 2 ，w d + 3 ，w d “，w d + s ，w d “，w d + 7 ，w d + b ， 其上下文各个位置权重的计算结果见表2 1 。 表2 1 上下文位置信息增益 左上下文 右上下文 位置信息增益位置 信息增益 w 正l 3 9 7 9 8 7 52 2 6 2 7 2 4 9 7 w d + l 4 0 0 57 3 7 0 4 6 2 6 33 7 7 w d 2 2 8 0 0 9 4 38 6 58 6 1 “3 w d + 2 2 9 3 18 3 4 0 5 7 1 2 36 1 w d - 3 2 1 8 32 8 71 9 85 8 79 8 5 w d + 32 2 8 7 0 2 0 5 1 81 0 9 0 5 1 w 也 1 7 0 9 5 0 4 2 5 12 1 3 9 6 8 w d “1 - 8 1 0 5 3 0 9 5 9 8 1 14 5 9 w 电 1 3 6 l6 3 78 6 0 6 6 16 0 6 w d + 51 4 3 7 9 5 2 7 7 5 0 0 4 0 1 w d 6 1 0 7 46 0 6 2 0 3 3 7 63 3 4 w d “ 1 1 3 79 7 97 4 64 3 79 8 8 w d 70 3 0 46 0 6 2 0 33 7 6 3 3 4 w d + 7 0 8 2 13 3 0 4 3 2 3 8 3 4 9 8 7 w d 8o 2 9 89 9 2 3 0 4 0 3 98 7 w 也b0 4 1 9 4 7 2 0 4 87 6 9 5 7 3 4 计算结果反映了这样个情况：上下文对核心词语的描述能力随着相对位置由 近及远而逐渐递减，即通过已知上下文推断空缺词语时，近距离的上下文在推断中 所起的作用比远距离的上下文更有价值。 这一计算结果与人们的认知过程基本一 致。虽然是近似结果，但在一定程度上具有统计意义。 这里需要强调的是鲁松( 2 0 0 2 ) 提到的“位置”是指一个待消歧词汇的上下文相 对于这个待消歧词汇的相对位嚣，而我们这里的“位置”是指一个命名实体对的 上下文相对于这个命名实体对中两个命名实体的相对位置。因此，我们在计算命名 实体对的上下文位置权重时需要同时考虑上下文分别对于两命名实体的相对位置， 将两部分上下文位置信息增益累加做为命名实体对的上下文位置信息增益。对于每 个命名实体对实例( 卧白) ，其上下文词汇矿的位置权重如公式( 2 6 ) 所示： 肫劬f ( p ) - 蜘r ( p l ，眇1 ) + 坳r ( e2 ，p ! ) ( 2 6 ) 其中，p d s ，为上下文词汇与命名实体日，的相对位置，p 口曲为上下文词汇与命 名实体毋的相对位置；如舫伯，p d 乳j 为位置p o s ，相对于命名实体b 的信息增 益( 见表2 1 ) ，肋，d ，向，p d 如) 为位置p d 岛相对于命名实体岛的信息增益( 见 表2 1 ) 。 根据计算，本文中上下文范围确定为2 6 2 ，即两命名实体间的距离不超过6 ， 取第一个命名实体前两个词，第二个命名实体后两个词，以及两命名实体间的所有 词，作为命名实体对的上下文。 2 3 3 命名实体对特征向量的构造 我们可以为命名实体对构造一个向量空间模型，向量空间中的每一维是命名实 体对矩阵中的一个上下文词语，其值是该上下文词语在表示此命名实体对两命名实 体间的语义时所具有的重要程度，即权重。其中，命名实体对矩阵中有多少个上下 文词语，向量空间中就有多少维。 命名实体对映射到向量空间中，其向量表示如下： v e i y - p 山= ( w t 廿m1 ，w t 付m _ 2 ，w t c 咖j ，w t 唧i n ) 其中，向量中每个分量w * 。j 为词语把朋j 的权重值，其形式见公式( 2 7 ) 。 f o o 椭e 雌 一。1 w 啦彘f ( p )若把删j 出现在命名实体对的上下文中2 7 ) 如果细协j 在此命名实体对上下文中出现，即f e 湘j 在命名实体对的上下文窗 口中，则词语把册j 的权重值w t 。l j