（运筹学与控制论专业论文）生物医学文献中的蛋白质名识别.pdf

大连理一1 ：大学硕士学位沦文 摘要 近年来，由于人类基因组计划( h u m a ng e n o m ep r o j e c t ) 的实施以及分子生物学、 信息科学的发展，d n a 、r n a 以及蛋白质等生物数据量空前增长，同时功能基因组和蛋 白质组的大量数据已开始涌现。生物医学文献的数量也是在迅速的膨胀，数据不等同于 知识，但却是信息和知识的源泉。激增的数据背后隐藏着许多重要的信息，如何从海量 的医学数据中抽取知识成为当前一个研究的热点，要从生物医学文献中抽取知识，首先 要做的就是正确识别文献中出现的大量的生物实体名。实体识别准确率的高低直接影响 着数据挖掘系统的好坏与否，因此实体识别在生物医学文献的挖掘中成为关键性的一 步。 目前列于实体识别采用的方法主要有以下几种，基于人工组织规则的方法，基于词 典的方法和基于机器学习的方法，比较常用的就是基于词典的方法和基于机器学习的方 法。词典法可以提供实体名的i d 信息，机器学习法可以在训练中逐步提高自己的识别 能力，但是由于生物实体名的特殊性，比如没有统一的命名规则，同一实体，可能会有不 同的命名，两种方法还都没有达到理想的效果，第一个问题就是由于蛋白质名拼写的多 样性造成了大量的错误的t ! = 别。另一个问题就是很多的蛋白质名是由两个或两个以上的 单词组成，多个单词组成实体名就出现词序问题，词典中只有一种最常用的排列，而常 用的搭配算法很难把文献中出现的其他的顺序的实体名全部找到，因而造成很多变形写 法不能识别。因此不能简单的通过查找在词典中出现的词作为目标词。机器学习方法经 实验证明是一个非常有效的方法，只是它不能提供关于被识别词条的验证信息。另外机 器学习的方法需要大规模的训练文本来提高识别能力，但是目前这样的训练文本还不够 多。 本文就生物实体识别进行了研究，结合了词典法和机器学习法的优点，提高了识别 的准确率和查全率，识别过程包含两个步骤：一是识别阶段，即通过蛋白质名词典和近 似匹配算法确定蛋白质名候选词，解决了拼写的多样化的问题，提高了查全率；二是过 滤阶段，即通过机器学习方法训练一个分类器，把利用近似匹配算法错误识别出来的假 蛋白质名过滤掉，以提高识别的准确率。但是仍然有些问题没有解决，例如词序颠倒的 问题，本文做了一些改进，引入了d i c e 系数和首词计算法，提高了查全率，同时解决 了词序颠倒的问题，并且降低了计算量。试验结果表明改进是有效的。 关键词：实体识别；蛋白质名识别；候选词；编辑距离；分类器 李刚：生物医学文献中的蛋白质名识别 t h er e c o g n i t i o no fp r o t e i nn a m ei nt h eb i o m e d i c a ld o c u m e n t s a b s t r a c t i nr e c e n ty e a r s ，a sar e s u l to f t h eh u m a ng e n o m ep r o j e c ta sw e l la st h em o l e c u l a rb i o l o g y ， t h ei n f o r m a t i o ns c i e n c ed e v e l o p m e n t ，d n a ，i 斟aa sw e l la st h ep r o t e i nb i o l o g yd a t aq u a n t i t y u n p r e c e d e n t e dg r o w t h ，s i m u l t a n e o u s l yt h ef u n c t i o ng e n eg r o u pa n dt h ep r o t e i ng r o u p 。sm a s s d a t as t a r t e da l s ot oe m e r g e t h eb i o m e d i c i n e1 i t e r a t u r eq u a n t i t yi nt h er a p i di n f l a t i o n t h ed a t a d o e sn o te q u a t et ot h ek n o w l e d g e b u ta c t u a l l yw a st h ed a t ab a c kw h i c ht h ei n f o r m a t i o na n d t h ek n o w l e d g ef o u n t a i n h e a di n c r e a s e ds h a r p l ya c t u a l l yi sh i d i n gm a n yi m p o r t a n ti n f o r m a t i o n t h er a d i di n c r e a s eo fm a c h i n er e a d a b l eb i o m e d i c a lt e x t sm a k e sa u t o m a t i ci n f o r m a t i o n e x t r a c t i o nf r o mt h o s et e x t sm u c hm o r ea t t r a c t i v e e s p e c i a l l ye x t r a c t i n gi n f o r m a t i o no f p r o t e i n - p r o t e i ni n t e r a c t i o nf r o mm e d l i n e a b s t r a c ti sr e g a r d e da so n eo ft h em o s ti m p o r t a n t t a s kt o d a y t oe x t r a c ti n f o r m a t i o no fp r o t e i n s o n eh a st of i r s tr e c o g n i z ep r o t e i nn a m e si na t e x t t h i s1 ( i n do fp r o b l e mh a sb e e ns t u d i e di nt h ef i e l do fn a t u r a ll a n g u a g ep r o c e s s i n ga s n a m e de n t i t yr e c o g n i t i o nt a s k s a tp r e s e n t ，t h em e t h o dw h i c hu s e dr e g a r d i n gt h ee n t i t yr e c o g n i t i o nm a i n l yt oh a v e f o l l o w i n gs e v e r a lk i n d s ，b a s e do nt h ea r t i f i c i a lo r g a n i z a t i o nr u l em e t h o d ，d i c t i o n a r y b a s e d a p p r o a c ha n dm a c h i n el e a r n i n gt e c h n i q u e s t h e r ea r es o m er e s e a r c he f f o r t su s i n gm a c h i n e l e a r n i n gt e c h n i q u e st or e c o g n i z eb i o l o g i c a le n t i t i e si nt e x t ，o n ed r a w b a c ki st h a tt h e yd on o t p r o v i d ei d e n t i f i c a t i o ni n f o r m a t i o no fr e c o g n i z e dt e r m s d i c t i o n a r yb a s e da p p r o a c h e sp r o v i d e i di n f o r m a t i o nb e c a u s et h e yr e c o g n i z eat e r mb ys e a r c h i n gt h em o s ts i m i l a ro n ei nt h e d i c t i o n a r yt ot h et a r g e tt e r m ，h o w e v e r ，d i c t i o n a r yb a s e da p p r o a c hh a v et w os e r i o u sp r o b l e m s ， o n ei st h es p e l l i n gv a r i a t i o n ，t h eo t h e rp r o b l e mi ss h o r tn a m e s i nt h i sp a p e rw ep r o p o s eat w o p h a s ep r o t e i nn a m er e c o g n i t i o nm e t h o d t nt h ef i r s tp h a s e ， w es c a nt h et e x t sf o rp r o t e i nn a l n ec a n d i d a t e su s i n gap r o t e i nn a m ed i c t i o n a r ya n da n a p p r o x i m a t es t r i n gs e a r c ht e c h n i q u e w ea l s oi n t r o d u c e dt h ed i c ec o e 伍c i e n ta n dt h ef i r s t w o r dc o m p u t a t i o nm e t h o d r e s o l v et h ep r o b l e mo ft h eo r d e ro fw o r d si nap r o t e i nn a l i l ei s a l t e r e d ，e n h a n c e dt h er e c a l l ，i nt h es e c o n dp h r a s ew ef i l t e rt h ec a n d i d a t e su s i n gam a c h i n e l e a r n i n gt e c h n i q u e t h ee x p e r i m e n t a lr e s u l th a di n d i c a t e dt h ei m p r o v e m e n tw a st h ee f f e c t i v e k e yw o r d s ：e n f i t yi d e n t i f i c a t i o n ；p l o t e i n n a m ei d e n t i f i c a t i o n ；c a n d i d a t e s e d i t _ d i s t a n c e ：c l a s s i f i e r 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方外， 论文中不包含其他入已经发表或撰写的研究成果，也不包含为获得大连理 工大学或者其他单位的学位或证书所使用过的材料。与我一同工作的同志 对本研究所做的贡献均已在论文中做了明确的说明并表示了谢意。 作者签名： 人连理一大学硕士研究生学位论文 大连理工大学学位论文版权使用授权书 本学位论文作者及指导教师完全了解“大连理工大学硕士、博士学位论文版权使用 规定”，同意大连理工大学保留并向国家有关部门或机构送交学位论文的复印件和电子 版，允许论文被查阅和借阅。本人授权大连理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，也可采用影印、缩印或扫描等复制手段保存和汇编学位论 文。 作者签名 导师签名 錾叫 虐痪过7 鲁蛱延 。! 扯年里月五 大连理工大学硕士学位论文 弓口 近年来，由于人类基因组计划( h u m a ng e n o m ep r o j e c t ) 的实施以及分子生物学、信 息科学的发展，d n a 、r n a 以及蛋白质等生物数据量空前增长，同时功能基因组和蛋白 质组的大量数据已开始涌现。生物医学文献的数量也是在迅速的膨胀，数据不等同于知 识，但却是信息和知识的源泉。为了更好地利用这些数据，帮助进行临床诊断、药物临 床作用的测定，以及对实验数据的统计分析等，就迫切需要提供种自动的数据分析 方法，对数据进行更高层次的分析【1 _ 3 】。正是基于这种情况，人们产生了运用数据来挖 掘相关知识的要求。其实很早就有人开始关注生物医学文献数据库，并且取得了很不错 的成绩。早在1 9 8 6 年，s w a n s o n 在对医学文献研究中发现雷诺氏病是一种治疗方法和 病因都未知的| ：f 】l 液循环紊乱，有文献中记载了部分雷诺氏病患者血液中有某种异常，比 如血液黏度升高。同时，又在其他文献中发现食用鱼油能纠正这种异常，例如，它可以 降低血液黏度。因此，s w a n s o n 把这两种知识联系起来得出食用鱼油应该对雷诺氏病患 者有帮助的假设 4 】。在这个假说提出大约两年后，有人通过临床实验证实了这一点【“。 1 9 8 8 年，s w a n s o n 用其他的方法又提出了周期性偏头痛与镁缺乏之间的联系。后来这 种关系也被临床证实 6 。7 。此后，他又发现了很多具有隐藏联系的例子，他的研究成果 引起了人们极大的兴趣。人们首次认识到从文献中可以发现或者挖掘到以前未知的，而 且是对医学的研究很有帮助的知识。 目前，对生物医学文献的挖掘已经成为一个热点，焦点大都集中在运用自然语言处 理的手段从医学文献中自动的抽取信息。早期信息抽取系统的目的就是找到给定基因的 信息或者找到特定的基因之间的联系。进行数据挖掘目的是希望得到隐藏在事物之间的 联系，要想找到事物之间的联系，就必须首先确定这些事物到底是哪些事物。就生物医 学数据挖掘来说，要想得到蛋白质基因以及疾病等等之间的联系，就必须首先能够在文 献中识别基因、蛋白质等生物实体。所以说，在生物医学文献挖掘的挖掘中，第一步要 做的就是进行生物实体识别。具体来讲生物实体识别的目的是在分子生物学及医学领域 对专业词汇加以确认和分类，这类实体包括：p r o t e i n s ，g e n e s ，d n a ，r n a ，e e l 卜t y p e ， e e l 卜l i n e 等。在更高一级的信息处理技术中，比如信息抽取，摘要和问答系统中都是 一个主要的组成部分。那些工作的目的就是帮助使用者将非结构化的数据结构化，发现 相关的信息。随着信息量的不断增加，这个工作显得更加的有意义。f 是因为如此，生 物实体识别不仅是生物医学文献挖掘的第一步，也是关键性的一步。基本的生物实体的 识别方法有两种：一是基于词典的方法，_ 是基于机器学习的方法。基于词典的方法通 过词典来提供被识别词条的i d 信息，从而就可以依照词典从文献l 中自动抽取生物实体 李刚：生物医学文献中的蛋白质名识别 名。这是最直接的一神方法，也是比较常用的方法 8 】，词典的质量和匹配算法的优劣直 接影响着识别结果的好坏。对于基于机器学习的方法，它不需要词典来提供工d 信息， 但是它需要很大的训练集来训练它，提高系统的识别能力 9 】。下面分别来介绍这两种方 法。 对于词典法识别生物体名，一是要建立一个质量好的词典，二是有好的匹配算法， 有许多快速的匹配算法可以用，比如b o y e r m o o r e 算法【1 。这类算法的优点是查找速 度快，但是效果却不是很好。因为到目前为止，生物医学实体还没有统一的命名规则， 这就使得同样的一个实体名，由不同的人写进文章中会有不同的格式，即使是一个简单 的实体名，比如：“e g r 一1 ”，也至少有6 种不同的拼写形式( 根据概率公式计算应该 是2 5 种不同的形式，其中有些是不常用的，常用的格式有：e g r 一1 ，e g r1 ，e g r l ，g g r 1 ，e g r 一1 ，e g r1 ) 。如果实体的名字稍长一点，拼写的形式更是多种多样，如果把所 有的形式都包括到词典当中几乎是不可能的，那样会导致查询的效率过低，词典中只能 是包含比较常用的生物实体名在里面，这就是b o y e r m o o r e 算法不太好用的原因。那么 如何解决词典中不存在但在文献中却出现的生物实体名呢? 最好的解决办法就是找到 一种“弹性”的匹配算法，把在文献中出现的那些与词典中的实体名相似的词的也提取 出来作为候选词，从而解决拼写多样的问题。于是引入了一个新的概念“相似度”，这 个概念很简单，就是比较两个事物之间相似的程度，只不过在这里要求必须通过数学计 算把相似度给求出来。于是就出现了很多关于“相似度”的计算方法，通常就是把两个 要比较的对象映射成向量空间中的两个向量，然后计算它们的欧几里得距离或者两个向 量夹角的余弦值来表示其相似程度，此外还可以通过计算两个序列之间的编辑距离或者 d i c e 系数表示其相似度i j “。 机器学习的方法在实体识别中的应用也是比较广泛的，常用的分类器模型有： s u p p o r tv e c t o rm a c h i n e s ( s v m s ) 刚2 1 ，h i d d e n m a r k o vm o d e l ( h m m s ) ”l ，m a x i m u me n t r o p y m a r k o vm o d e l s ( m e m m s ) “ ，c o n d i t i o n a lr a n d o mf i e l d s ( c r f s ) 1 1 5 四种。它们需要经 过“学习”之后，才4 可以用来识别实体。学习的过程就是训练的过程，使用己经标注好 的文本集来训练，同时还需要另外一些标注好的文本集来测试系统的识别能力。这两部 分数据分别称为：训练集和测试集。训练和测试通常是使用g e n i av e r s i o n3 0 2 c o r p u s 怕】。它是由从m e d l i n e 抽取的2 0 0 0 篇摘要，并且对摘要中出现的所有的生物实 体名都进行了人工标注。使用g e n i ac o r p u s 有两个重要的原因：首先，在分子生物学 领域的实体识别工作独自提供了标注好的训练集，其次就是它的详细的分类，共有3 6 个分类，常用的分类一般有p r o t e i n s ，d n a ，r n a ，c e l 卜t y p e ，c e l 卜l i l i e 几类。 火连理工大学硕士学位论文 对于实体名的识别主要有以上两种方法，如何来评判生物医学文献中的实体识别 呢? 通常用下面的三个标准来评测： ( 1 ) 准确率( p r e c i s i o n ，p ) ，p 表示系统从文献中提取的实体中正确的实体所占比 重。 ( 2 ) 查全率( r e c a l l ，r ) ，r 表示正确识别的实体占文献所包含实体总数的比重。 ( 3 ) f 值( f - s c o r e s ，f ) ，f = ( 2 p r ) ( p + r ) 。其计算公式分别为： 准确率：垩塑塑型塑塞皂里鱼；查全率：至婴望型丝至皂星墨； 所有的蛋白质名候选词应有的所有的蛋白质名 f 信：! ! 堡塑皇：奎全奎。 准确率+ 奄全率 目前，在生物医学文献中的生物实体的自动识别虽然取得了一定的成绩，但是其结 果和普通的文本中的一般实体的识别结果还是存在着一定的差距。普通的文本，其作者 一般都是专业的作家，写作的目的就是为了传递信息，让尽可能多的读者明白其写作意 图，但是科学文献却不是这样，其作者很可能是那些第一语言不是英语的科学家们，写 作的主要目的是研究而不是简单的描述，读者群也将是本领域的一些专家学者，很多的 背景知识被省略了，却增加了许多本领域的行话，基于上面的原因，无疑就增加科学文 献信息抽取的难度。另外生物实体目前还没有一个统一的命名规则，都是发现者随机取 的名字，很难只从实体本身来判断他是否是表示的一个生物实体，不仅如此，在生物医 学文献中还存在着大量简写的实体名，虽然书写方便，却也造成了许多的歧义。这些因 素使得在生物医学文献中的实体识别更加具有挑战性，因此，生物医学文献中的实体识 别还有一段很长的路要走。 论文组织如下： 第一章：主要是概述了国内外命名实体研究的一些情况； 第二章：介绍了词典法识别实体名的情况，主要讨论了所使用的匹配算法，以及对 算法的一些改进i 第三章：介绍了机器学习法对实体名的识别，详细介绍了其原理和训l 练过程； 第四章：详细介绍了基于词典法和机器学习法相结合的蛋白质名识别； 总结：本文针对如何识别蛋白质名进行了有益的尝试，主要采用了基于词典的方 法，其中运用了近似搭配算法和首词查询的方法进行蛋白质名识别，同时结合机器学习 方法训练了一个分类器来过滤候选词以提高识别的准确率。 李刚：生物医学文献中的蛋白质名识别 1 命名实体识别研究 命名识别的研究( n a m e de n t i t yi d e n t i f i c a t i o n ，通常称之为专有名词识别) 是自 然语言处理中的一项基本工作，在大规模真实文本的处理中尤其重要。本章的内容就是 介绍命名实体的识别。 本章包括两部分，第一部分说明命名实体识别的任务以及研究命名实体识别的意 义，并介绍其在自然语言处理中的应用；第二部分介绍命名实体识别的一些方法。 1 1 简介 1 1 1 命名实体识别的任务 一般来说，命名实体识别的任务就是对于一篇待处理文本，能够识别出其中出现的 人名( p e r s o n ) 、地名( l o c a t i o n ) 、机构名( o r g a n i z a t i o n ) 、日期( d a t a ) 、时问( t i m e ) 、 百分数( p e r c e n t a g e ) 、货币( m o n e t a r yv a l u e ) 这七类命名实体( 1 ”，对于本文的处理对象 主要是生物医学文献，任务是识别其中的生物实体名( 比如蛋白质，d n a ，基因等) 如图 1 1 所示，在图1 1 的例子中，i n t e r l e u k i n - i ，i l 一1 ，i 乙一2 都是蛋白质名，也是本文 重点研究的对象。 剧i1 以x 札格式标注好的生物实体名的m e d l i n e 句子 f i g1 1e x a m p l em e d l l n e s e n t e n c em a r k e du pi nx m lf o rm o l e c u l a rb i o l o g yn a m e de n t i t i e s 11 2 命名实体识别的意义 为什么要研究命名实体的识别呢? 最重要的一点：命名实体的识别是一项基础工 作，可以应用到自然语占处理的各个方面，例如：句法分析( p a r s e r ) 、信息抽取 ( i n f e r m a t io ne x t r a c t i o n ) 、信息检索( i n f o r m a t i o nr e t r i e v a l ) 、机器翻译( m a c h i n e 火连理1 1 ：火学硕+ 学位论文 t r a n s l a t i o n ) 、文本校对( s p e l l i n gc h e c k e r ) 、问题回答( q u e s t i o na n s w e r i n g ) 等中。 例如，要找到两种生物实体之间的关系，首先就得从文本中识别此两种实体名。又如， 在阅读一篇文章以前，读者可以预先浏览文中的人名、地名、机构名、日期、时间等， 它能够帮助读者快速而有效的了解此文本的大致内容。同样，命名实体的识别也是句法 分析、机器翻译、信息抽取等任务的一个非常重要的预处理模块。在文本校对中，命名 实体的识别可以在一定程度上克服误检错问题，提高文本校对的准确率。 相对于中文，英文命名实体的识别容易一些。这是由中文本身的特点确定的：中文 文本中词与词之间没有分隔符，中文文本的分词和中文命名实体的识别是互相缠绕的、 密不可分的。但是对于英文也有自身的一些特点，尤其是针对于生物医学文献，其生物 实体名一般包括多个单词组合，由于命名规则的不统一，对于同一实体会出现很多的命 名，也可能同一名称代表了不同的实体，即使是一个实体有了统一的命名，还存在书写 顺序以及大小写等问题，给识别造成了很大的困难，降低了识别的准确率和查全率。 1 2 命名实体识别方法 英文命名实体的识别随着m u c 一6 和m u c 7 机器理解会议的举行获得了较大的发展。 这些系统按照方法的不同，大体可以分为三类：基于人工组织规则的方法；基于机器学 习的方法；人工组织规则和机器学习相结合的方法。 1 21 基于人工组织规则的方法 基于人工组织规则的方法的典型代表是纽约大学( n e wy o r ku n i v e r s i t y ) 的p r o t e u s 系统、i s o q u e s ti n e 的n e t o w l 系统、曼彻斯特科技大学( u n i v e r s i t yo fm a n c h e s t e r i n s t t u t eo fs c i e n c ea n dt e c h n o l o g y ) 的f a c i l e 系统。这个三个系统都参加了m u c 一7 的测试，并且都采用了模式匹配的方法，不同之处是这些系统采用的模式( 或规则) 外 在表达方式不同。 p r o t e u s 系统包括很多的语境相关的推导规则，并且这些推导规则很直观。例子如 下： t i t l ec a p i t a l i z e d _ w o r dt i t l e p e r s o n n a m e m o n t h n a m en u m b e r l e s s t h a n 一3 2 一d a t e f r o md a t et odate-d a t e 利用这些规则进行命名实体识别的方法是在句子中的每一位置用所有的规则进行 自左到右的扫描，从而找到最长( 或最大概率等其它标准) 匹配的规则，用这条规则来 对该句子进行归结处理，然后从下一个没有匹配的位置刀：始实施相同的操作，以此类推 李刚：生物医学文献中的蛋白质名识别 直到此句子结束。 n e t o w l 系统和f a c i l e 系统也是采用了人工组织规则的方法，同时利用了常用命名 实体词典，对不同规则还可以赋予不同的权重，以便当对相同内容采用不同的规则识别 出不同的命名实体时，这种歧义可以通过选择最大权重的规则来解决。 不过，我们可以发现，对于这类采用人工组织规则的系统，主要存在以下缺点： ( 1 ) 人工组织规则的代价非常昂贵，并且主要依赖于有经验的计算语言学家。 ( 2 ) 当把此系统移植到不同领域时，需要大量的人工修改工作。 ( 3 ) 当把此系统移植到新的语种时，这些规则需要重新书写和组织。 ( 4 ) 语言学家书写规则的经验和所花费的人力劳动的大小对性能的影响很大。 1 2 2 基于机器学习的方法 基于机器学习的命名实体识别主要包括以下方法：基于决策树模型( d e c i s i o n t r e e ) 、基于隐马尔科夫模型( h m m ) 、基于最大熵模型( m a x i m u me n t r o p y ) 等。 1 2 2 1 基于决策树模型的命名实体识别 基于决策树模型的命名实体识别的工作主要包括b e n n e t t 、s s e k i n e 等。b e n n e t t 等利用二叉决策树来决定在输入序列中是否插入类别开始符号、类别结束符号、什么也 不插入这三个操作。 s s e k i n e 把n 类命名实体的识别问题( 对于m u c - 7 ，n = 7 ) 抽象为对每一符号( 词) 标注为4 n + l 中的哪一类标记问题。对n 类命名实体中的每一特定命名实体x ，定义了4 个状态：x s t a r t ，x c o n t i n u e ，x e n d ，x u n i q u e ，另外，还定义了状态“o t h e r ”来 标记某一符号( 词) 不是命名实体的一部分。所以，对于n 类命名实体，需要定义4 n + 1 个标记。例如，对于字符串 j e l l yl e el e w i sf l e wt op a r i s 应该标记为 j e l l y l p e r s o ns t a r tl e e l p e r s o n _ c o n t i n u el e w i s p e r s o n _ e n df l e w l o t h e rt o l o t h e r p a r i s l l o c a t i o n _ u n i q u e 利用决策树模型进行标注，主要包括两个部分：决策树的构造和利用决策树进行标 注，其中关键问题是怎样构造决策树。构造决策树的基本想法是在每一个给定节点处， 从所有的问题集合中寻找一个最优的问题，依次递归或循环就可以构造一颗完整的决策 树。其中，在每一节点处最优的评价标准是指在此节点处对于决策树的输出的不确定性 减小最大，不确定性是通过条件熵来描述的： 大连理工大学硕士学位论文 a ； a l lp o s s i b l ea n s w e r st oq u e s t i o nw f e a l lp o s s i b l et a g ) ( ，ia ) = 一p ( q ) p ( f l q ) l o g ( f g ) q e af e f 此外，s s e k i n e 在命名实体识别的过程中还利用的资源包括一系列的词典( 命名 实体的前缀、后缀、以及一些常用的命名实体) 。 1 2 2 2 基于隐马尔科夫模型( h m m ) 的命名实体识别 基于隐马尔科夫模型的命名实体识别的主要工作是b b n 公司的b i k e l ，1 9 9 7 实现的 i d e n t i f i n d e r 系统。其基本的想法为每一类实体建立一个独立的2 元语言模型，另外还 建立了一个2 元模型，此模型刻画的是：基于前一单词和其相应实体类别的条件下，来 预测当前词所属类别的概率大小。 它们的系统可以简化为下面的两个公式来表示： p ( n c i n c 一廿等等掣 吖c 咖m p ，n c ) = 等筹等 ( 1 2 ) ( 1 3 ) 其中，n c 表示当前命名实体的类别，n c _ ，表示当前词的前面第x 个词的实体类别， c ( w ) 表示在训练语料中，事件w 出现的次数，w 表示一个单词，f 表示一个特征。 如果上面的模型已经训练得到，那么可以利用v i t e r b i 搜索算法得到最大概率的名 字类别序列，由此可以得到文本中的命名实体。b b n 的系统在m u c 一7 的命名实体识别测 试中获得了较大成功，在1 2 个系统中获得第3 名。 1 2 2 3 基于最大熵模型的命名实体识别 基于最大熵模型的命名实体识别的工作主要包括纽约大学的b o r t h w i c h ，1 9 9 9 等。在 b o r t h w i c h 的基于最大熵模型中，命名实体识别问题可以概括为 p ( f1h ，j = p ( fh i s t o r yi n f o r m a t i o 咒r e l a t i v et ot o k e nf j( 1 4 ) 李月u ：生物医学文献中的蛋白质名识另0 其中f ( f u t u r e s ) 、h ( h i s t o r i e s ) 分别表示输出空间的一个实例和历史语境空间的一个实 例。在最大熵模型中，吖厂i j 是紧密的依赖于特征空间，特征的不同对系统的影响很 大。b o r t h w i c h 把特征定义为f 和h 的二值函数，例如，其中一个特征如下： 扛a t u r h ，j ) = 1 0 矿c u r r e n t _ t o k e n c a p i t a l i z e d ( h ) = t r u ea n d = l o c a t i o ns t a r t e l s 8 此特征表示当前符号的首字母是大写，并且当前符号可以是地名的开始符号时， f e a t u r e ( h ，= j ，否则f e a t u r e ( h ，厂，= 0 。 在定义特征和特征空间的基础上，最大熵模型的训练问题其实质就是为每一个特征 i 估计其对应的参数a f 。最终，可以计算目标函数 n 垡帆i j p 1 ) h 。：p 1 1 h j = j 矿 z 。r n ，= 爹 9 口夕“，p f 6 ， ( 1 6 ) f 1 7 ) 其最大熵模型的训练模块( 参数估计) 采用了r i s t a d ，1 9 9 8 的工具包。在识别部 分，对于每一历史语境h ，计算每一个输出f 的条件概率，然后利用v i t e r b i 搜索算法 得到最优路径。 1 2 3 人工组织规则和机器学习相结合的方法 在m l c 一7 评测中，爱丁堡大学的a m i k h e e v 等在命名实体识别过程中采用了规则 和最大熵模型相结合的方法。其明显的特点是把识别过程分五个步骤完成，每一步完成 特定的任务。这五个步骤分别是：确定性触发规则、局部匹配l 、约束较弱的规则、局 部匹配2 、标题的特殊处理。 在识别过程中，采取的是多遍扫描的方法，每一遍扫描实施的操作不同。第一步实 施的是确定性的触发规则。f 面是确定性的触发舰则的例子： 大连理i 大学硕士学侥论文 图1 2 确定性触发规则 f i g 1 2t h er u l eo f t h ed e f i n i t i o nt r i g g i n g 利用这些人工编写的正则表达式规则进行命名实体识别，能够获得很高的准确率。 但是存在的问题是查全率较低。所以，又采取一些措施来提高命名实体识别的查全率。 在局部匹配1 阶段，首先收集该文本中已经识别出来的命名实体，对这些命名实体的各 种局部( 当然顺序保持不变。例如：已经识别出4 b c 作为机构名，那么a b 、b c 作为候 选的机构名) 都作为候选的对应类别的命名实体，这些候选实体经过最大熵模型进行进 一一步的确认和过滤。第三步采用约束较弱的规则，这些规则具有较弱的语境约束，并且 能够充分利用已经存在的信息和词典。在局部匹配2 的处理中，系统充分利用已经识别 出来的人名、地名、机构名进行局部匹配，然后经过最大熵模型进行进一步的确认和过 滤。最后对文本标题中的候选命名实体通过另一最大熵模型( 此最大嫡模型是基于文本 标题训练得到) 进行确认。后面的这四步大大提高了系统的查全率，并且对准确率没 有多大的降低。 总之，英文命名实体识别的研究采用的方法为基于人工组织规则的方法、机器学习 的方法、人工组织规则和机器学习相结合的方法。英文命名实体的识别已经取得了很大 的成绩，对于生物医学文献中的生物实体名的识别有很大的帮助，我们可以借鉴其中的 方法，提高生物实体名的识别准确率和查全率，同时针对于生物一些文献中的生物试题 名的特殊性，方法也不能简单生硬照搬。下面介绍在生物医学文献中的实体识别的主要 的方法。 李刚：生物医学文献中的蛋白质名识别 2 基于词典法的生物实体识别研究 2 1 词典的建立 对于生物医学文献中的生物实体名识别最直接也是最容易想到的方法就是词典法， 词典法对生物实体名识别的一个优点就是它可以提供实体名的d 信息，通过相应的匹 配算法，扫描待查找的文献，就可以识别出文献中出现的实体名。因此通过词典法来识 别生物实体名有两个主要的方面，第一是词典的质量，第二就是搭配算法的好坏。 词典的好坏直接影响了识别的效率和准确率，主要是因为生物实体名的特殊性决定 的，表现为： 第一，没有统一的命名规则，到目前为止蛋白质还没有统一的命名规则。不同的学 者研究的重点不同，比如功能，序列特征，基因名，细胞位置等等，因此就有了不同的 命名，即使是有一个统一的名字，在不同的文献中出现也会有很多的形式，比如一个很 简单的实体名“e g r - 1 ”，也至少有6 种常用的不同拼写形式，即e g r l ，e g r l ，e g r 。1 ， e g r1 ，e g r - , l 和e g r1 。如果某个蛋白质的名字稍长一点，那么拼写的形式更是多种多样。 如果把所有的形式都包括到词典中又会造成词典容量过大，效率不高。 第二，文献中还存在大量的简写，在带来书写方便的同时也造成了识别的困难。所 以词典中的词就必须选择最有代表性的词，词典的质量。 2 2 匹配算法 词典建立之后，要寻找文献中的实体名就必须有相应的匹配算法，匹配算法主要有 两种，其一是“精确”匹配算法，比如b m 算法【1 0 】，其二是“弹性”的匹配算法，通过 计算两个序列的相似度，来查找相似词。分别介绍两种匹配算法。 2 2 1 “精确”匹配算法 顾名思义，精确匹配就是要找到和词典中的词完全一致的词，这样的匹配算法很多， 但是由于生物实体本身的一些特点，词典中不能把所有的可能形式都包含在里面，所以 精确的匹配算法效果不是很理想，这里只介绍一种快速匹配算法，b m 算法【l 。用一个 具体的例子来说明这个快速匹配算法： 算法的目的是如何迅速确定待查询词在句子中的位景，比如确定词“a t t h a t ”在 句子“w h i c h f i n a l l y - h a l t s 一a t t h a t p o i n t ”中的位置就可以这样查找。 步骤一：首先让待查找的词和序列的首字符对齐 大连理1 1 火学硕士学位论文 词： a t t h a t 序歹0 ：w h i c h - f i n a l l y h a l t s a t t h a t p o i n t 乍 词“a t t h a t ”中含有7 个字符，最后一个字符“t ”正好和序列中的第7 个字符 “f ”对齐，显然字符“f ”没有出现在词“a t t h a t ”中，搭配不符，继续下一步： 步骤二：继续下移7 个字符，变到如下的格式 词： a t t h a t 序歹0 ：w h i c h f i n a l l y h a l t s a t t h a t p o i n t 个 可以看到字符“一”在词“a t t h a t ”中出现了，让“一”和”对齐 步骤三：让上下两个词中重复出现的字符对齐 词： a t t h a t 序歹u ： w h i c h f i n a l l y h a l t s a t t h a t p o i n t 个 仍然发现上下两个词没有完全匹配，继续上面的步骤 步骤四：继续下移7 个字符 词： a t t h a t 序列：w h i c h f i n a l l y h a l t s 一a t t h a t p o i n t 个 仍然是没有完全匹配，但是“a t ”可以匹配； 步骤五：对齐字符“a t ”和“a t ” 词： a t t h a t 序列： w l i c i 卜f i n a l l y h a l t s _ a tt h a t p o i n t 个 李刚：生物医学文献中的蛋白质名识别 从而发现，上下两个词可以完全匹配，经过5 个步骤，或者说移动5 次，比较5 次 就可以找到完全匹配的词的位景。比一次移动一个字符迅速的多，这就是“快速”匹配 算法的优点之，但是它也有自身的不足，只能找到完全的匹配。虽然速度很快，精确 度也很高，但是对于生物实体名的识别是远远不够的。 2 2 2 “弹性”匹配算法 因为“精确”匹配算法不能很好的解决问题，为了提高识别的查全率，最好的解决 办法就是使用“弹性”匹配算法，类似的算法有很多，因为本文的主要创新也就在于改 进了一种“弹性”匹配算法，下面将对其做详细的介绍。 “弹性”匹配的关键就是在匹配的过程中引入了“相似度”的概念，相似度的计算 有很多种，比如用夹角余弦，或者欧式距离等等，比较常用的还是用编辑距离来表示两 个序列之间的相似度，可以通过动态规划方法来计算两个序列之间的编辑距离，编辑距 离越大表示两个序列的相似度越小。 2 2 2 1 编辑距离法 2 2 2 1 1 编辑距离简介 在文本编辑，模式搜索和近似匹配【1 8 - 1 9 1 等的应用中，编辑距离常用于衡量两个模式 之间的差异程度，在文本编辑中，模式字符串同目标字符串之间的差异即编辑距离，该 距离定义为两个字符串通过插入字符、删除字符、改写字符而变为相同字符串所需要的 操作数。举例说明一f 。 d ( “a b c ”，“a b d ”) = 1 d ( “a b c ”，“a b ”) = l d ( “a b c ”，“a b c d f ”) = 2 d ( “s e r v e r u ”，“s e r - u ”) = 4 w a g n e r 和f i s c h e r 2 0 1 给出了求解编辑距离的动态规划算法，该算法在时间和空间上 的开销均为o ( m 1 1 ) ，其中m ，n 分别为模式字符串和目标字符串的长度。动态规划算法 d p 使用一个二维表存放编辑距离，该表可以用于计算字符编辑的操作顺序。下面详细介 绍编辑距离的计算。 2 2 2 1 2 词和词之间的编辑距