（计算机应用技术专业论文）基于文本挖掘技术的蛋白质相互作用预测方法研究.pdf

摘要 后基因组时代，随着高通量生物技术的发展，生物医学的实验手段 和研究方法均发生了巨大变革，生物医学文献的数量呈“指数型”增长， 应用文本挖掘技术从海量的医学文献中提取蛋白质的相关信息，建立蛋 白质相互作用关系的网络图，已成为生物信息学和蛋白质组学领域的研 究热点。 本文首先介绍了文本挖掘技术及其应用，接着介绍了文本挖掘技术 在生物医学领域的应用现状。对支持向量机( s v m ) 算法的基本原理做了 阐述，在此基础上我们研究了一种基于支持向量机的蛋白质相互作用预 测算法，该算法首先应用支持向量机算法提取文献中蛋白质名称信息， 并引入了上下文线索提高提取算法的性能，实验证明，上下文线索的引 入使提取结果的三项评价指标都有明显提高。接着我们选取交互词特 征、词项特征、实体距离特征和链接语法特征作为特征向量，应用支持 向量机算法对蛋白质相互作用进行预测，在损失较少关系抽取召回率性 能的情况下，较大地提高了准确率，从而最终提高了综合分类率。 在提出的算法的基础上，本文采用分布式计算系统来解决生物信息 学计算中大规模数据处理。将系统分解为若干个子任务。将子任务分配 给网络中其他客户端计算机完成，从而在一定程度上提高了生物信息学 中海量计算的效率。 关键词文本挖掘，蛋白质相互作用，支持向量机，分布式系统 a b s t r a c t p o s t g e n o m i ce r a ，w i t h t h e h i g h - t h r o u g h p u td e v e l o p m e n t o f b i o t e c h n o l o g y , b i o m e d i c a lr e s e a r c ht o o l sa n de x p e r i m e n t a lm e t h o d sh a v e u n d e r g o n et r e m e n d o u sc h a n g e si nt h ea m o u n to fb i o m e d i c a ll i t e r a t u r e w a s e x p o n e n t i a l g r o w t hi nt h ea p p l i c a t i o no ft e x tm i n i n gt e c h n o l o g y f r o mt h em a s so fm e d i c a ll i t e r a t u r ep r o t e i ne x t r a c tr e l e v a n ti n f o r m a t i o n ， t oe s t a b l i s ht h er e l a t i o n s h i pb e t w e e np r o t e i n - p r o t e i ni n t e r a c t i o nn e t w o r k h a sb e c o m eab i o i n f o r m a t i c sa n dp r o t e o m i c sr e s e a r c hi nt h ef i e l do fh o t s p o t s 1 1 1 i sa r t i c l ei n t r o d u c e st h et e x t m i n i n gt e c h n o l o g y a n di t s a p p l i c a t i o n s ，a n dt h e ni n t r o d u c e dt h et e x tm i n i n gt e c h n o l o g yi nt h ef i e l d o fb i o m e d i c a la p p l i c a t i o n s o ns u p p o r tv e c t o rm a c h i n e ( s v m ) a l g o r i t h m i sd o n eo nt h eb a s i cp r i n c i p l e s ，o nt h eb a s i so fo u rr e s e a r c h ，as u p p o r t v e c t o rm a c h i n eb a s e do nt h e p r o t e i n - p r o t e i n i n t e r a c t i o n p r e d i c t i o n a l g o r i t h mi st h ef i r s ta p p l i c a t i o no fs u p p o r tv e c t o rm a c h i n ea l g o r i t h mf o r e x t r a c t i n gp r o t e i n n a m e so ft h e1 i t e r a t u r e i n f o r m a t i o n ，a n d t h e i n t r o d u c t i o no fc o n t e x tc l u e st oi m p r o v et h ep e r f o r m a n c eo fe x t r a c t i o n a l g o r i t h m ，t h ee x p e r i m e n tp r o v e dt h a tt h ei n t r o d u c t i o no fc o n t e x tc l u e st o m a k ee x t r a c t i o no ft h et h r e ee v a l u a t i o nr e s u l t sh a v es h o w nam a r k e d i n c r e a s e t h e nw es e l e c tt h ei n t e r a c t i v ef e a t u r e so ft h ew o r d ，t h ew o r do f t h ec h a r a c t e r i s t i c s ，p h y s i c a lc h a r a c t e r i s t i c sa n dd i s t a n c ec h a r a c t e r i s t i e so f t h el i n kg r a m m a ra saf e a t u r ev e c t o r , t h ea p p l i c a t i o no fs u p p o r tv e c t o r m a c h i n ea l g o r i t h mt op r e d i c tp r o t e i n - p r o t e i ni n t e r a c t i o n ，t h er e l a t i o n s h i p b e t w e e nt h el o s sl e s st h er a t eo fe x t r a c t i o nr e c a l lp e r f o r m a n c e ，t h el a r g e r a n d i m p r o v e da c c u r a c y a n d u l t i m a t e l yi m p r o v e t h er a t eo fa c o m p r e h e n s i v ec l a s s i f i c a t i o n i nt h ep r o p o s e da l g o r i t h mb a s e do nd i s t r i b u t e dc o m p u t i n gs y s t e m s u s i n gb i o i n f o r m a t i c st os o l v el a r g e s c a l ed a t a - p r o c e s s i n gc a l c u l a t i o n 胁e s y s t e mi sb r o k e nd o w ni n t os e v e r a ls u b t a s k s s u b t a s k sw i l lb ef l l o c a t e d t ot h en e t w o r kc l i e n tc o m p u t e rt oc o m p l e t et h eo t h e r , t h u st os o m ee x t e n t i n c r e a s e dm a s sb i o i n f o r m a t i c sc o m p u t i n ge f f i c i e n c y k e yw o i m st e x tm i n i n g ，p r o t e i ni n t e r a c t i o n ，s u p p o r tv e c t o rm a c h i n e s ， d i s t r i b u t e ds y s t e m s l l 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。 作者签名：埤嗍卑让月丛日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 期：地卜年上月生日 硕士学位论文第一章绪论 1 1 课题研究背景 第一章绪论 随着高通量生物技术的发展，生物医学的实验手段和研究方法均发生了巨 大的变革，生物医学领域内实验数据呈“指数性”增长，面对海量的生物医学数 据，如何做好存储、传输、应用，是当前数学、化学、药学、统计学和计算机科 学等领域专家日益关注的问题，并取得了大量成果。生物医学文献作为学术交流 和成果展示的主要方式之一，其数目之大，增长速度之快远远超过了其他学科领 域，面对如此大规模的、快速增长的科学文献数据，传统的信息检索技术、文档 文本处理技术已经不能适应日益增加的海量文本数据处理的需要，于是在生物医 学领域的文本挖掘技术就充分体现出其在处理海量数据，特别是在非结构化数据 处理方面的优势。 文本挖掘技术可以在多方面辅助生物医学研究者的工作：信息检索技术可 以帮助用户在海量文档信息集合中快速有效地查找到有用的信息：信息抽取技术 可以从生物医学文献中抽取出特定的事实信息( 主要是生物实体如疾病、药物、 基因、蛋白质间的关系) ，对整个生物知识网络的建立、生物体关系的预测、新 药的研制等均具有重要的意义；文本分类技术可以通过粗粒度的筛选从而缩小搜 索的范围，为进一步的信息处理作准备；假设生成技术可以从文献中挖掘出来实 验假设和实验建议，以便生物学家验证得到新的科学发现；自动摘要技术可以利 用计算机自动地从原始生物医学文献中提取出文摘，使研究者不用花费太多的时 间就可以从大量的文献中获得有用的信息。 许多组织和机构也在积极促进文本技术在生物医学文献中研究工作。如美 国国家标准技术协会( n i s t ) 和美国国防部高级研究计划局( d a r p a ) 共同主办的文 本检索会议( t e x tr e t r i e v a lc o n f e r e n c e ，t r e c ) 在2 0 0 3 年增加了基因组学研 究( g e n o m i c st a s k ) 项目，其主要内容可以从它的数据、任务、用户、实验等方 面来描述。其中数据包括全文、基因数据库、基因蛋白质功能标记；任务包括 了回溯检索、问答系统、查找综述信息、分类输出等。面对如此巨大的研究前 景，许多国际著名的计算机公司和大学纷纷加大投入力度，其中i b m 公司为其代 表。o r a c l e 和s u n 公司也先后投入巨资进行生物信息学领域的开发和研究。 1 。2 国内外的相关研究 应用文本挖掘技术从海量的医学文献中提取蛋白质名称信息，进而预测蛋 硕十学位论文第一章绪论 白质相互作用关系是近几年来生物信息学领域研究的热点之一。 e d w a r dm m a r c o t t e 瞳1 采用统计的方法，从m e d l i n e 数据库选出具有蛋白质 相互作用关系的2 6 0 篇论文。选出这些文献中的8 0 个特异字，利用统计学中的 贝叶斯概率理论，把这2 6 0 篇论文作为训练集( t r a i n i n gs e t ) 来判断一篇文章中 是否含有蛋白质相互作用信息。但是e d w a r d 的方法的缺点是：它采用部份己经 统计过和文章属性相关的关键词，缺乏语言学合理性。例如：若出现否定词n o 或连接词( a n d ，b u t ) 等在语句中影响句子逻辑判断时，它的有效性就降低。 t h o m a s 口1 利用一体化医学语言系统( u n i f i e dm e d i c a ll a n g u a g es y s t e m ， u m l s ) ，再锁定关键词动词，配合已开发的a r b i t e r 程序，继续完善到能判断一 篇生物医学文献中是否含有蛋白质相互作用关系的记录。t h o m a s 的方法偏重当 关键动词出现在描述蛋白质相互作用文章中时，所分析的句子的组态和现有程序 a r b i t e r 的配合应用。不过，当关键词动词增多( 或要应用在其它类似文献提取 应用) 时，他们的系统可能会变得过于复杂，难以实用。 m a r kc a r v e n 4 1 则是配合生物学家，阅读部份酵母蛋白数据库( y e a s t p r o t e i nd a t a b a s e ，y p d ) 文献，将已经审查和分类好的文章分成五大类，并应用 人工神经网络方法和贝叶斯概率统计自动分类。但是当文章类别更加细分后，他 们的试验模型会有贝叶斯概率统计原理假设条件和实际文献分类不一致的困难。 s e k i m i z u 1 使用商业程序e n g c g 来实现基因相互作用关系判断。他们的方 法是先判断关键动词，再利用自然语言原理，找出句子中的主语、宾语，最后判 断基因之间是否存在相互作用。但缺点是必须配合e n g c g 程序的开发和更新，有 一定的局限性，其它地方难以应用。 c l a d u er o u x 】贝0 提出一种语意分析( 1 i n g u i s t i ca n a l y s i s ) 及知识处理 ( k n o w l e d g ep r o c e s s i n g ) 系统，作为基因相互作用的辅助提取系统，目前未完成。 目前国内在生物医学文本挖掘领域的研究相对还比较少，发表的相关研究 文章也不多见，且多是综述性的文献。开展的研究主要是以医学情报人员为研究 主体的文献计量学研究。主要有清华大学和哈尔滨工业大学，上海生命科学研究 院生物信息中心，均取得了一定成果。清华大学研究者在蛋白质关系抽取方面做 了深入研究，其主要工作包括：基于动态规划算法的模式匹配方法，用于抽取蛋 白质交互作用关系，取得了8 0 的查全率和正确率h 1 ；在此基础上采用最小描述 长度原理进行模式优化，进一步提高了抽取正确率。他们还将模式匹配与浅层句 法分析结合起来，通过句法和语义约束，很好地识别了生物医学文本中的同位和 并列句，将原模式匹配方法的正确率和综合评价指标f 测度提高了7 隅1 。哈工大 研究人员主要致力于生物医学命名实体识别和关系的识别的研究，先后尝试了多 种机器学习方法。先后应用s v m 算法、g e n e r a li z e dw i n n o w 、c r f 等方法进行命 2 硕十学位论文第一章绪论 名实体识别，在实现中选择了丰富特征并结合后处理过程，在相同测试集上取得 了优于国际同类研究的结果。目前，他们在综合多种统计学习方法进行多分类器 融合的研究上取得了一定的成果，进一步提高了生物医学命名实体识别的正确率 和查全率9 1 。 1 3 研究的目的及意义 蛋白质组学研究n 2 1 是2 1 世纪细胞生物学研究领域最重要的内容，当前不 仅仅是生物医学方面的专家，许多数学、化学、统计学和计算机科学等领域的学 者也纷纷在自身的研究领域开展蛋白质组学的研究。蛋白质相互作用研究是蛋白 质组研究中的重要内容。通过分析一个蛋白质是否跟功能已知的蛋白质相互作用 可以预测其功能。经验告诉我们，如果两个蛋白质相互作用，那么它们一般参与 相同或相关的细胞活动。从近期蛋白质组学研究的发展动向可以看出，揭示蛋白 质之间的相互作用关系，建立相互作用关系的网络图n 引，已成为揭示蛋白质组复 杂体系与蛋白质功能模式的先导和蛋白质组学领域的研究热点。 随着生物学的实验手段和研究方法的飞速发展，生物医学领域的研究产生了 海量的生物数据。据权威机构统计，生物数据量呈指数级增长，同时网络上可访 问的生物数据源数量也以平均每1 5 个月翻一番的速度快速增长，其发展的速度 超过了摩尔定律。隶属于美国国家生物技术信息中心的文献摘要库m e d l i n e n 制， 是世界上最大的、最具权威性的著名生物医学文献数据库，收集了全世界4 8 0 0 多种生物学及医学杂志上1 7 0 0 万余篇文献信息，并且正以每个月超过万篇的速 度增长。面对如此大规模的、快速增长的科学文献数据，传统的信息检索技术、 文档文本处理技术已经不能适应目益增加的海量文本数据处理的需要，于是在生 物医学领域的文本挖掘技术就充分体现出其在处理海量数据，特别是在非结构化 数据处理方面的优势u 引。 在计算机科学与生物医学相结合的领域生物信息学纠羽中，应用文本挖 掘技术从海量的医学文献中抽取蛋白质实体名称信息，并用其相关信息预测蛋白 质的相互作用是目前蛋白质组学研究的热点问题之一。蛋白质在所有的生命活动 中担当了一个很重要的角色。蛋白质是基因组编码的产物，它参与了很多重要的 过程，如信号传导、基因表达、细胞调亡、细胞周期与分化、癌基因产物功能、 基因表达调控等。这些过程都与蛋白质及其他生物大分子间的相互作用有密切关 系。因此，理解蛋白质组成、结构和行为是研究生物系统的基础n 叼啪1 。通过预测 蛋白质相互作用关系可以帮助建立蛋白质知识网络、预测蛋白质关系以及辅助新 药的研制，因此具有重要的研究意义口1 l 乜副。 硕七学位论文第一章绪论 1 4 主要的研究内容及构成 本文的研究重点在于应用文本挖掘技术从海量的生物医学文献中提取蛋白 质名称信息，预测蛋白质相互作用关系。主要完成的任务是： 1 、文本挖掘技术在生物信息学领域的应用研究。 2 、提出了一种基于文本挖掘技术的蛋白质名称提取以及蛋白质相互作用关 系预测的方法。该方法通过适当特征的选取，利用s v m 分类器提取文本中蛋白质 名称信息，并根据提取的蛋白质名称信息进一步判断句子中每对蛋白质( 基因) 是否存在相互作用关系。 3 、设计一个分布式系统，采模块化设计，分模块实现蛋白质相互作用关系 预测的功能，在一定程度上提高了生物信息学中海量计算的效率。 论文后续章节安排如下： 第二章主要文本挖掘技术的相关问题进行探讨，介绍了文本挖掘技术的基本 概念，介绍了文本挖掘技术领域的关键技术，对支持向量机( s v m ) 算法的基本原 理做了阐述，并且分析了文本挖掘技术在生物信息学领域的应用，是后面章节的 研究基础。 第三章提出一种基于文本挖掘技术的蛋白质相互作用预测方法，该方法法首 先应用支持向量机算法提取文献中蛋白质名称信息，并引入了上下文线索提高提 取算法的性能，实验证明，上下文线索的引入使提取结果的三项评价指标都有明 显提高。接着我们选取交互词特征、词项特征、实体距离特征和链接语法特征作 为特征向量，应用支持向量机算法对蛋白质相互作用进行预测，在损失较少关系 抽取召回率性能的情况下，较大地提高了准确率，从而最终提高了综合分类率。 第四章在提出的算法的基础上，本文提出一种分布式计算系统来解决生物信 息学计算中大规模数据处理。将系统分解为若干个子任务。将子任务分配给网络 中其他客户端计算机完成，从而在一定程度上提高了生物信息学中海量计算的效 率。 第五章对论文所做研究工作进行总结，并提出今后进一步的研究方向。 4 硕士学位论文第二章文本挖掘技术及其在生物信息学中的应用 第二章文本挖掘技术及其在生物信息学中的应用 在现实世界中，可获取的大部分信息是以文本形式存储在文本数据库中的， 由来自各种数据源的大量文档组成，如新闻文档、研究论文、书籍、数字图书馆、 电子邮件和w e b 页面。由于电子形式的文本信息飞速增涨，文本挖掘已经成为信 息领域的研究热点。文本数据库中存储的数据可能是高度非结构化的，如w w w 上 的网页；也可能是半结构化的，如e m a i l 消息和一些x m l 网页；而其它的则可能 是非结构化的。非结构化文本数据的典型代表是图书馆数据库中的文档，这些文 档可能包含结构字段，如标题、作者、出版日期、长度、分类等等，也可能包含 大量非结构化文本成分，如摘要和内容。如何快速、准确地从来自非结构化的数 据源的大规模的文本信息资源中提取符合需要的简洁、精炼、可理解的知识，这 就涉及到文本知识挖掘。 文本挖掘是近几年来数据挖掘领域的一个新兴分支，在国际上，文本挖掘是 一个非常活跃的研究领域。从技术上说，它实际是数据挖掘和信息检索两门学科 的交叉心引。文本挖掘与传统数据挖掘的差别在于文本数据与一般数据的巨大差 异。传统数据挖掘所处理的数据是结构化的，如关系的、事务的、数据仓库的数 据，其特征数目通常不超过几百个，而文本数据没有结构，转换为特征矢量后特 征数将达到几万甚至几十万。所以，文本挖掘既采用了很多传统数据挖掘的技术， 又有自己的特性。 2 1 文本挖掘技术概述 2 1 1 文本挖掘的基本概念 文本挖掘( t m ，t e x tm i n i n g ) 口钔是以计算语言学、统计数理分析为理论基础， 结合机器学习和信息检索技术，从文本数据中发现和提取独立于用户信息需求的 文档集中的隐含知识。它是一个从文本信息描述到选取提取模式，最终形成用户 可理解的信息知识的过程。 文本挖掘是一个交叉的研究领域，它涉及到自然语言处理幢朝、机器学习汹3 、 数据挖掘、信息检索啪1 等多个领域的内容，不同的研究者从各自的研究领域出 发，对文本挖掘的含义有不同的理解，不同应用目的文本挖掘项目也各有其侧重 点。 直观的说，当数据挖掘的对象完全由文本这种数据类型组成时，这个过程就 硕士学位论文第二章文本挖掘技术及其在生物信息学中的应用 称为文本挖掘。文本挖掘也称为文本数据挖掘或文本知识发现，文本挖掘的主要 目的是从非结构化文本文档中提取有趣的、重要的模式和知识。可以看成是基于 数据库的数据挖掘或知识发现的扩展。文本挖掘是从数据挖掘发展而来，因此其 定义与我们熟知的数据挖掘定义相类似。但与传统的数据挖掘相比，文本挖掘有 其独特之处，主要表现在：文档本身是半结构化或非结构化的，无确定形式并且 缺乏机器可理解的语义；而数据挖掘的对象以数据库中的结构化数据为主，并利 用关系表等存储结构来发现知识舢。 2 1 2 文本挖掘的一般过程 文本挖掘通常包括信息检索、信息抽取、数据挖掘三个步骤。其中信息检索 ( i n f o r m a t i o nr e - t r i e v a l ，i r ) 用于识别相关文本，信息抽取( i n f o r m a - t i o n e x t r a c t i o n ，i e ) 用于识别实体、关系、事件等信息，数据挖掘( d a t am i n i n g ， d m ) 则从结构化信息中识别出相互间的关联口。 ( 1 ) 信息检索 1 ) 文本预处理心钔 文本预处理是文本挖掘的第一个步骤，对文本挖掘效果的影响至关重要，文 本的预处理过程可能占据整个系统的8 0 的工作量。与传统的数据库中的结构化 数据相比，文档具有有限的结构，或者根本就没有结构，即使具有一些结构，也 还是着重于格式，而非文档的内容，且没有统一的结构，因此需要对这些文本数 据进行数据挖掘中相应的标准化预处理；此外文档的内容是使用自然语言描述， 计算机难以直接处理其语义，所以还需要进行文本数据的信息预处理。信息预处 理的主要目的是抽取代表文本特征的元数据( 特征项) ，这些特征可以用结构化的 形式保存，作为文档的中间表示形式。 i n t e r n e t 上的大部分网页是h t m l 文档或x m l 文档，文本的预处理首先要做 的是，利用网页信息抽取模块将网页的内容，去掉跟文本挖掘无关的标记，转换 成统一格式的t x t 文本存放在文件夹中以备后续处理。中文文本的预处理较英文 文本的预处理更为复杂，因为中文的基元是字而不是词，字的信息量比较低，句 子中各词语间没有固有的分隔符( 如空格) ，因此对中文文本还需要进行词条切分 处理。 2 ) 文本的表示 文本的内容是人类所使用的自然语言，表达了丰富的信息，但是要把这些信 息编码为一种标准形式是非常困难的。基于自然语言处理和统计数据分析的文本 挖掘中的文本特征表示指的是对从文本中抽取出的元数据( 特征项) 进行量化，以 结构化形式描述文档信息。这些特征项作为文档的中间表示形式，在信息挖掘时 6 硕十学位论文第二章文本挖掘技术及其在生物信息学中的应用 用以评价未知文档与用户目标的吻合程度，这一步又叫做目标表示。 文本表示的模型1 常用的有：布尔逻辑模型，向量空间模型( v s m ，v e c t o r s p a c em o d e l ) ，潜在语义索引( l s i ，l a t e n ts e m a n t i ci n d e x i n g ) 和概率模型 ( p r o b a b l i s t i cm o d e l ) 。其中向量空间模型法是近年来在文本挖掘系统中应用较 多且效果较好的一个方法。 ( 2 ) 信息抽取 1 ) 特征提取 特征提取( f e a t u r ee x t r a c t i o n ) 是对文件中出现的词汇、短语的特征提取， 由原始数据创建新的特征集，将非结构化的数据转化成可以直接记录在数据库中 的结构化数据，生成挖掘目标的特征矢量，特征项集提取应该根据两个基本原则 即完全性和区分性原则来进行，并将提取得到的特征矢量经过特征子集的选取后 存放到文本特征库中形成文本中间表示形式嗍。 特征提取的方式有4 种： 用映射或变换的方法把原始特征变换为较少的新特征。 从原始特征中挑选出一些最具代表性的特征。 根据专家的知识挑选最有影响的特征。 用数学的方法进行选取，找出最具分类信息的特征，这种方法是一种比 较精确的方法，人为因素的干扰较少，尤其适合于文本自动分类挖掘系 统的应用。 提取的特征大部分是文本集中表示的概念，这些概念包含着重要的信息，因 此要提前定义哪些信息必须被抽取和被怎样抽取，这需要有较好的专业知识。目 前使用的方法主要有向量空间模型和布尔模型两种，其中向量空间模型是近年来 应用较多并且效果较好的方法之一。 2 ) 特征集约减 特征集约减的目的有三个： 为了提高程序效率，提高运行速度； 数万维的特征对文本分类的意义是不同的，一些通用的、各个类别都普 遍存在的特征对分类的贡献小，在某个特定的类中出现的比重大而在其 他类中出现比重小的特征对文本的贡献大： 防止过拟合( o v e r f i t ) 。对每一类，去除对分类贡献小的特征，筛选出针 对反映该类的特征集合。 用向量空间法表示文档时，文本特征向量的维数往往达到数十万维，即使经 过删除停用词表中的停用词以及应用z i p 法l 1 则删除低频词，仍会有数万维 特征留下。最后一般只选择一定数量的最佳特征来开展各种文本挖掘工作，所以 7 硕士学位论文第二章文本挖掘技术及其在生物信息学中的应用 进一步对特征进行约减就显得异常重要。 通常，特征子集的提取是通过构造一个特征评估函数嘶训，对特征集中的每 个特征进行评估，每个特征获得一个评估分数，然后对所有的特征按照评估分大 小进行排序，选取预定数目的最佳特征作为特征子集。文本特征选择中的评估函 数是从信息论中延伸出来的，用于给各个特征词条打分，很好地反映了词条与各 类之间的相关程度。常用的评估函数有文档频数( d o c u m e n tf r e q u e n c y ) ，信息增 益( i n f o r m a t i o ng a i n ) ，期望交叉熵( e x p e c t e dc r o s se n t r o p y ) ，互信息( m u t u a l i n f o r m a t i o n ) ，x 2 统计( c h i ) ，单词权( t e r ms t r e n t h ) ，文本证据权( t h ew e i g h t o fe v i d e n c ef o rt e x t ) 和几率比( o d dr a t i o ) 等。 ( 3 ) 数据挖掘 经过上述两个步骤后，文档以其特征信息存储在数据库中，因此记录在数据 库中的已是结构化的数据，这就可以对文档中的特征信息集合进行分类、聚类和 关联分析等挖掘处理了。 1 ) 文本分类 文本分类是一种有指导机器学习问题，它需要事先定义一些主题类别，然后 根据文本的内容自动将每篇文档归入其中的一个类别，这样用户即可以根据自己 的所需来选择信息。从数学角度来看，文本分类其实就是一个映射的过程，它将 未标明类别的文本映射到已有的一个或多个类别中。分类系统一般分为训练和分 类两个阶段。 分类算法很多，主要有向量空间模型呻1 、朴素贝叶斯分类( n a t i v eb a y e s ) h 、 决策树、支持向量机s v m ( s u p p o r t v e e t o r m a c h i n e s ) h 射、后向传播分类、遗传算 法、基于案例的推理、k 一最临近、基于中心点的分类方法h 3 1 、粗糙集、模糊集以 及线性最小二乘( l i n e a rl e a s ts q u a r ef i t ，l l s f ) h 4 1 等。 本文将重点介绍文本挖掘中关于文本分类部分，其中支持向量机s v m 是本文 关注的重点。 2 ) 文本聚类 与文本分类不同的是：文本聚类不需要预先定义主题的类别，由聚类学习算 法来自动确定其类别，是一种无指导的机器学习过程。它将文档集合分成若干个 簇，要求同一簇内文档内容的相似度尽可能地大，而不同簇间的相似度尽可能地 小“5 1 。常用的聚类方法有两种类型：以g - h a c 为代表的层次凝聚法啪1 ( 又分为聚 合聚类和分裂聚类) 和以k - m e a n s 为代表的平面划分法h7 | 。其中层次凝聚法是最 为常用的聚类方法。 层次聚类过程构造出一棵生成树，其中包含了类的层次信息以及所有类内和 类间的相似度，但在每两个类合并时，需要全局地比较所有类之间的相似度，确 8 硕+ 学位论文第二章文本挖掘技术及其在生物信息学中的应用 定适当的相似度阀值，选出最佳的两个类，因此运行速度较慢，不适合于大量文 档的集合。 3 ) 关联分析 关联分析是指从文档集合中找出不同词语之间的关系。f e l d m a n 和h i r s h 研 究了文本数据库中关联规则的挖掘h 圳，文献n 刚提出了一种从大量文档中发现一对 词语出现模式的算法，并用来在w e b 上寻找作者和书名的出现模式，从而发现了 数千本在a m a z o n 网站上找不到的新书籍；文献唧1 以w e b 上的电影介绍作为测试 文档，通过使用o e m 模型从这些半结构化的页面中抽取词语项，进而得到一些关 于电影名称、导演、演员、编剧的出现模式。 2 1 3 文本挖掘的应用 文本挖掘作为数据挖掘领域日趋流行并且重要的研究课题，随着技术的同趋 完善，应用前景越为广泛。 ( 1 ) 文本检索：文本检索主要研究对整个文档文本信息的表示、存储组织和 访问，即根据用户的检索要求，从数据库中检索出相关的信息资料( 文本挖掘简 述) 。这种检索方法有三种啼：布尔模型，如清华大学的中国学术期刊( 光盘版) ； 概率模型，如美国马萨诸塞大学开发的i n q r e r y 文本检索系统；向量空间，如美 国康乃尔大学基于向量空间模型开发了s m a r t 文本检索系统。 ( 2 ) 文本自动分类：文本分类是指按照预先定义的主题类别，为文档集合中 的每个文档确定一个类别。这样用户不仅可以方便地阅读文档，而且可以通过限 制搜索范围来使文档查找更容易。 ( 3 ) 文档总结：文档总结也是w e b 文本挖掘的一个重要内容。它是指从文档 中抽取关键信息，用简洁的形式，对文档内容进行摘要和解释，这样用户不需阅 读全文就可了解文档或文档集合的总体内容。搜索引擎向用户返回查询结果时， 通常给出文档摘要，这就是文档总结的一个实例。 ( 4 ) 信息表现：信息挖掘技术关系的是信息的方方面面，力求从多角度表现 信息的本质和特征。文本挖掘技术能动态地、实时在线地表现信息的相关属性， 发现概念之间的相互关系，使用户及时发现信息，更新信息和发现信息的演变方 向。 ( 5 ) 信息智能代理：主要为在分布式信息网络环境下的信息的查询服务。信 息智能代理使用户可以不知道所要检索信息的具体形式，存储于何处、何种介质 中，只要用户提出查找要求，文本挖掘技术会自动地把各种信息源中各种形式的 相关信息检索出来，使用户可以迅速获得较为满意的检索结果。 9 硕士学位论文第二章文本挖掘技术及其在生物信息学中的应用 2 2 文本挖掘关键技术分析 在生物信息学领域的文本挖掘，由于处理的对象是半结构化或非结构化的文 档，自然语言处理技术( n a t u r a ll a n g u a g ep r o c e s s i n g ，n l p ) 唧3 成为实现生物 信息学文本挖掘的主要技术手段，而随着计算技术的发展，机器学习( m a c h i n e l e a r n i n g ) h 作为一种在众多的学科领域都有应用的基础性、透明化的“支持技 术、服务技术 在生物医学文本挖掘也发挥着日益重要的作用。因此，自然语言 处理技术和机器学习成为生物医学文本挖掘的主要支撑技术。本文介绍的生物医 学文本挖掘技术相关工作主要依赖于机器学习方法( 支持向量机) 。下文对机器学 习原理及方法进行介绍。 2 2 1 机器学习原理 机器学习喳硇的核心是学习。学习是人类智能的主要标志和获得智慧的基本 手段，是人类智能的主要标志和获得智慧的基本手段，是人类具有的一种重要智 能行为。目前在机器学习研究领域影响较大的是h 。s i m o n 的观点：学习就是系 统在不断重复的工作中对本身能力的增强或者改进，使得系统在下一次执行同样 任务或类似任务时，会比现在做得更好或效率更高。 机器学习就是要使计算机能模拟人的学习行为，自动通过学习获取知识和技 能，不断改善性能，实现自我完善。机器学习研究的就是如何通过识别和利用现 有知识来获取新知识和新技能。 学习过程与推理过程是紧密相连的，按照学习中使用推理的多少，机器学习 所采用的策略大体上可分为4 种：机械学习、示教学习、类比学习和示例学习。 学习中所用的推理越多，系统的能力越强。机器学习系统的基本结构如图2 1 所 示。 机器学习的实现方法大致可分为三种：第一种是经典的( 参数) 统计估计方 法。包括模式识别、神经网络等。第二种方法是经验非线性方法，如人工神经网 络( a n n ) 。第三种是基于统计学习理论的方法，如在次理论基础上发展的一种新 的通用学习方法一支持向量机( s u p p o r t v e c t o rm a c h i n e 或s v m ) 。 图2 - 1 机器学习系统结构图 l o 硕士学位论文 第二章文本挖掘技术及其在生物信息学中的应用 机器学习方法较其他方法的优势在于不需要付出繁重的努力去定义规则或 语法，它自动提取实体交互模式而不需要人的参与。目前已经出现了许多基于蛋 白质称名共现的机器学习与统计的方法。其中根据挖掘单位( 如摘要、句子等) 又分为不同的类型。a n d r a d e 汹3 等和m a r c o t t l e 刚等的方法在摘要集合中提取蛋 白质交互关系。前者将一组相关文档与一组随机选取的文档对比来提取领域知识 ( 如基因功能和交互) ；后者检索到可能包含蛋白质交互关系的文档；c r a v e n 啪1 等最早开发了基于机器学习的句子级蛋白质交互关系抽取系统。使用贝叶斯分类 器，对于一个包含2 个实体名的句子，返回它们存在交互关系的概率。后续的研 究者使用了包括隐马尔科夫模型、支持向量机的机器学习方法来判别包含蛋白质 交互关系的句子；还有的方法研究句子中一对实体存在交互关系的概率。 s t a p l e y 嘲1 等使用固定的基因名列表，借助共现方法在m e d l i n e 记录中构建每个 基因对的相似性矩阵来检测它们的关系。j e n s s e n 呻1 等采用类似的方法发现了 d n aa r r a y 实验中的人类基因聚类间的关系。 本文提出了一种基于支持向量机( s u p p o r tv e c t o r m a c h in e s ， s v m ) 的蛋白质 交互作用关系预测方法。该方法通过适当特征的选取( 包括词项特征、关键词特 征、实体距离特征、链接特征以及链接语法分析特征) ，利用s v m 分类器判断句 子中每对蛋白质( 基因) 是否存在相互作用关系。实验证明这种方法可以获得比基 于自然语言处理更高的查全率。 2 2 2 支持向量机( s v m ) 算法 支持向量机( s v m ) 算法由c o r t e s & v a p n i k 于1 9 9 5 年首次提出田门h 6 2 1 ，该算法 基于机器学习理论、统计学习理论，现已被广泛运用于模式识别、函数拟合和生 物信息学等领域。与传统模式识别方法相比，s v m 主要不同之处在于先通过非线 性变换将输入空间变换到一个高维空间，然后在这个新空间中进行分界面寻优。 这种非线性变换通过定义适当的内积函数来实现。 支持向量机是从数据分类问题的研究中发展起来的，它实质上是统计学习理 论在实际应用中的一种实现方法嘲，它具有理论完备，适应性强，全局优化，训 练时间短和泛化性能好等优点，在解决小样本、非线性及高维模式识别问题中表 现出许多特有的优势，而且可以推广应用到函数估计等其他机器学习问题中嘲1 。 ( 1 ) 最优超平面哺钉 假设存在样本( 而，乃) ，( 而，乃) ，x r ，y + l ，- 1 ) ，l 为样本数，n 为输入维数。 对于这个假设，分类的目的就是找到一个超平面将这两类样本完全分开。该超平 面描述为： 硕士学位论文第二章文本挖掘技术及其在生物信息学中的虑用 ( x ) + b = 0 其中，“是向量点积。分类的结果如下： 而+ b 0 ， 五+ b 0 ，舅= 世 是超平面的法线方向，恻l 为单位法向量， 此时假设空问为： l 6 2 s g n ( c a 。x + 6 ) 对( 缈，6 ) 进行如下约束： m i n ( o , x j ) + b i - - 1 i = i ，2 , - - - , 公式( 2 - 1 ) 公式( 2 - 2 ) 其中恻l 是欧氏模函数。 公式( 2 - 3 ) 公式( 2 - 4 ) 如果训练样本可以被无误差的划分，以及每一类数据与超平面距离最近的向 量与超平面之间的距离最大，则称这个超平面为最优超平面。 h 图2 - 2 最优超平面示意图 图2 2 中日为分类超平面，日t 、z 分别为各类中离分类超平面最近的样本 且平行于分类超平面的平面，它们之间的距离叫做分类间隔( m a r g i n ) 。 由约束条件( 2 - 4 ) 可知： h ：( w x ) + b = 0 日l ：( w 船) + 6 1 ，弘= 1 h 2 ：( w 勋) + 6 - 1 ，弘= - 1 归一化得： 1 2 硕十学位论文 第二章文本挖掘技术及其在生物信息学中的应用 弘( ( w 蔚) + 6 ) 1 i = l ，公式( 2 - 5 ) 其中，日。和日：到日的距离为l | 1 w 0 ，分类间隔为2 j f w 0 。 ( 2 ) 线性可分情况 对线性可分的情况，求解最优超平面的问题可以归结为如下二次规划问题： m 甜i n 三l f z 1 1 2 s j 弘( 彩勋+ 6 ) l ，i = 1 ，2 ，公式( 2 - 6 ) 式( 2 6 ) 表示在经验风险为零的情况下使v c 维的界最小化，从而最小化 v c 维，这正是结构风险最小化原理。这是一个凸规划问题，引入拉格朗日函数 进行求解： 三c o , b , a ) = 三1 11 1 2 ；倪抄，( m ) 一- ) s j o f f 0 公式( 2 - 7 ) 其中，口，为每个样本对应的拉格朗同乘子。一般地，解中只有一部分( 通 常是一少部分) 口，不为零，对应的样本x t 就是支持向量( s u p p o r tv e c t o r ，s v ) 。 图2 2 中在h 、h ：上的点就是支持向量。这样，国可以表示为： 口) + = 亿i y ；y 公式( 2 8 ) 缈2 己口，x f y 。 公瓦( 2 8 ) 二次规划问题( 2 6 ) 的对偶问题为求解如下目标函数的极大化： n ( 口) = 善i 口，一j 1 善1 优，口，y ，y ，( x ，x ，) 珐i = l 晓，) ，= o 口。0 ，i 芝l ， 公式( 2 9 ) 为了在样本为线性不可分的情况下构造最优超平面，可知式( 2 - 5 ) 中增加 一个松弛项乡。( 孝，o ) ，即一个松弛项jt ( j