复杂网络构建中信息抽取技术综述，本文主要内容关键词为：技术论文,网络论文,信息论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
D01:1 0.3772/j.issn.1673-2286.2008.06.006
1 引言
近年来，真实网络中小世界效应和无标度特性的发现激起了各界对复杂网络的研究热潮。复杂网络的研究，为我们提供了一个复杂性研究的新视角、新方法，并且提供了一个比较的视野，可以在复杂网络研究的旗帜下，对各种复杂网络进行比较、研究与综合概括。随着复杂网络分析算法的不断成熟和完善，针对复杂网络的应用，其构建已成为关键。通过网络分析所得到信息的丰富和完整程度，往往取决于其构建过程中每个节点和边所包含的信息量。而现实的大多数应用中，待构建网络的节点和边往往隐藏在非结构化或半结构化的文本信息中，如何从中准确而全面地抽取节点和边信息，成为构建复杂网络的关键问题。
信息抽取是一门正走向成熟的技术，在信息处理自动化中具有基础性的地位，将信息抽取融合到复杂网络中，能够有效地抽取网络的节点和边信息，为复杂网络的构建和表示提供数据准备，这将大大扩展复杂网络的应用范围。Xin Li等[1]通过信息抽取技术，将复杂网络的应用范围扩展到web页面，先抽取命名实体构建网络，再通过社区发现等方法在web上挖掘出知识来。Dennis M.Wilkinson等[2]，通过信息抽取技术，提取出与某一疾病相关的共现基因，而后构建成网络，划分一些相关基因的社区，从而能够帮助专家们发现出基因间的相互作用和它们之间的一些潜在联系。这些网络构建与分析方法都为复杂网络的应用提供了新的思路。
随着非结构化和半结构化数据的增加，基于这些信息进行复杂网络分析已经成为一种必然趋势，信息抽取将会扮演越来越重要的角色，这也将大大促进复杂网络的发展。信息抽取与复杂网络的融合将是一个新的研究和应用热点问题。本文鉴于信息抽取对复杂网络的重大意义，对信息抽取作了简要介绍，并针对复杂网络的构建，描述了如何通过信息抽取技术抽取节点及其属性信息（包括通过实体解析对抽取节点进行预处理），如何抽取边的信息，并给出了一些应用实例，很具有启发意义。
2 信息抽取简介
2.1 信息抽取的概念
信息抽取是从自然语言文本中抽取指定类型的实体、关系、事件等事实信息，并形成结构化数据输出的文本处理技术[4]。
信息抽取作为自然语言处理中一个发展很快的研究领域，它有如下特征：首先信息抽取是当前文本挖掘中最为突出的一项技术，这一技术结合了自然语言处理、语料资源以及语义技术，目前正趋于成熟；其次，信息抽取不是从文件集中选取一个与用户需求相关的子集，而是从文献中直接抽取与用户需求相关的事实或信息；再次，信息抽取是一个从无结构的自由文本或其他信息资源中抽取出结构化、无二义性信息的过程。
2.2 信息抽取的类型
信息抽取技术有多种分类方式。根据各种工具采用的原理可分为五类：基于自然语言处理方式的信息抽取、包装器处理归纳方式的信息抽取、基于Ontology方式的信息抽取、基于HTML结构的信息抽取和基于Web查询的信息抽取[3]。较具有代表性的消息理解会议(MUC)系列研究项目根据信息抽取内容以及抽取出信息的集聚水平的不同，将信息抽取分为以下几类[4]：
(1)命名实体识别(NE)信息抽取：NE信息抽取是最为基本的任务，实现从众多信息中表示并分离出相关的命名实体，这是正确理解文本的基础。此类信息抽取需要系统能够识别出实体名，并将相应的实体名进行归类。这需要信息抽取系统能够从自由文本中识别并抽取出人名、地名、机构名、时间以及某种类型的数字表达式（如货币数量、百分数），并在文本中对这些信息进行标注。命名实体识别具有非常直接的使用价值，在对文本中的实体进行标注之后，即提供了对这些信息进行检索的可能。对于许多语言处理系统，命名实体识别都是其中一个很重要的组件，是目前最有使用价值的一项技术。
(2)多语言实体识别(MET)信息抽取：MET信息抽取除了能够对英文命名实体进行识别外，还能够对多语种的命名实体进行识别，例如可以对日文、中文或西班牙文等进行命名实体识别。
(3)模板元素(TE)信息抽取：TE信息抽取将特定的描述信息与实体联系起来，它是从文本的任何地方将与组织、人物或其它实体相关的基本信息抽取出来，并将这些信息作为实体的属性进行聚集，形成实体对象。TE系统需要能够从文本中抽取特定类型的实体信息，并将这些信息填写到预先定义的小型属性模块之中。
(4)参照(CO)信息抽取：CO信息抽取在进行NE或TE任务时，从文本中表示出对同一实体的不同表达方式。CO可以将散布在文本中不同地方的同一实体的描述信息连接起来，同时分析实体在文本中不同地方出现的情况，以及次实体在不同场合与其它实体之间的关系，有助于情节信息的抽取。
(5)模板关系(TR)信息抽取：TR信息抽取需要在TE的基础上表示出模板元素之间的关系。TR是MUC7定义的一项新任务，它的抽取包括相关元素模板以及元素之间的相互关系。
(6)情节模板(ST)信息：抽取ST主要是抽取某一事件中的时间信息并将时间信息与某个组织、人物或其它实体相关联。ST需要表示出特定时间及时间的相关属性，包括将事件中的各个实体填充到事件的相应角色中，通过对象之间的关系，能够还原出整个事件的“原型”。
2.3 信息抽取的方法
设计信息抽取系统的方法基本分为两种：基于知识工程的方法和基于自动训练的方法。第一种知识工程方法，由专家对语料库进行分析、调整从而人工制定规则、模板。这种方法需要有经验的语言工程师来开发，个人的直觉能够对系统的性能起到很大的影响，性能较好，开发周期较长，一旦成型之后不容易进行修改；第二种自动训练方法，给出标注的例子文档集，通过机器学习来推导模板和模板的自动填充规则，也可以应用统计学的方法来抽取。使用这种方法的开发者并不需要掌握语言工程知识，但需要大量的经过标注的训练数据，如果需要对这类系统的核心进行修改，则相应的所有训练数据也需要重新标注。
3 复杂网络构建中的信息抽取技术
节点和边是复杂网络的两个最基本的元素。欲对某一复杂性问题构建网络研究时，首先就应抽象出网络的节点和边。因此，复杂网络构建中信息抽取技术的应用，主要集中在通过信息抽取技术，抽取出网络的节点信息和边信息。
3.1 节点信息的抽取技术
3.1.1 命名实体及属性信息抽取
实际应用中，构建复杂网络的每个节点往往是一个个命名实体，它们组成了复杂网络的研究对象。命名实体抽取是信息抽取中最为基础的类型，它需要系统能够从众多信息中标识并分离出相关的命名实体。对于科技文献中命名实体的抽取不只局限在人名、地名、机构名的抽取上，还包括一些专门的术语、概念的抽取，比如在医学领域，需要识别出药品名、蛋白质名、基因名等等。目前命名实体识别的难点在于：在不同领域、场景下，命名实体的外延有差异；数量巨大，不胜枚举，难以全部收录在词典中；某些类型的实体名称变化频繁，并且没有严格的规律可以遵循。
命名实体识别研究至今已经有近20年的发展历史，已经成为自然语言处理领域的一项重要技术，并取得了很多成果。与大多数自然语言处理技术一样，命名实体识别的方法主要分为两大类：基于规则的方法和基于统计的方法。较早的命名实体识别方法多采用手工构造有限状态机的方法，用模式和字符串相匹配。在基于规则的方法中，命名实体识别使用的不仅有各种命名实体的构成规则，还有实体本身和上下文的关系以及用词情况。但是基于规则的方法缺乏鲁棒性和可移植性，对于每个新领域的文本都需要更新规则来保持最优性能，而这需要大量的专门知识和人力，代价往往非常大。相比较而言，基于统计的方法利用原始或经过加工的语料进行训练，语料的加工也不一定需要非常广博的语言学知识，较小规模的语料也可以在可接受的时间和人力代价内完成。更重要的是，用统计方法实现的系统在移植到新的领域时可以不作或作较少的改动，只要利用新领域的语料进行训练即可。此外，由于统计方法对具体语言特性的依赖相对较少，因此基于统计的系统要移植到不同的自然语言也相对容易一些。用于命名实体识别的统计方法中，最主要有最大熵方法(ME)[5]、隐马尔可夫方法(HMMs)[6]、最大熵的隐马尔可夫方法(MEMMs)[7]、条件随机场(CRF)[8]以及核的方法[9]等等。
在具体的应用中，王浩畅等人[25]使用了基于支持向量机的方法对生物医学文本中的命名实体进行了识别。系统中结合了丰富的特征集，包括局部特征、全文特征和外部资源特征，对不同的特征及其组合对系统的贡献进行了评测和实验。为了进一步提高系统的性能，还引入了缩写词识别模块和过滤器模块，取得了较好的识别效果。Tsuruaka[10]中对于基于字典方法和机器学习方法相结合的蛋白质名实体识别作了细致的讨论，先是通过蛋白质词典和近似搭配算法确定蛋白质名候选词，解决了拼写多样化的问题，提高了查全率，然后通过机器学习方法训练一个分类器，把利用近似搭配算法错误识别出来的假蛋白质名过滤掉以提高识别的准确率。刘非凡等人[26]则提出了一种基于层级隐马尔可夫模型的产品命名实体识别方法，实现了汉语自由文本中产品命名实体识别和标注的原型系统。该方法通过融合两个统计模型以及同知识库、启发式规则的有机结合，综合利用了不同层次的上下文特征进行产品命名实体识别，在电子数码和手机领域均取得了令人满意的效果。
实体的抽取仅仅完成了复杂网络基本拓扑中的一个个点的提取，实际应用中，往往我们需要节点的更丰富的信息，以备复杂网络分析和展示所用。例如，对于我们构建的科技合作网（以论文的作者为节点，作者的合作关系为边）中，针对某位作者的查询，我们不仅需要知道该作者在网络中的拓扑信息，还需知道作者所在的实验室，作者的研究方向等属性信息，并且，对该网络划分社区后，对于某一社区即一个研究团队，应如何进行描述呢？这也得借助社区中每个节点的属性信息，比如通过综合社区中每个人的研究方向，可以得到该团队的研究方向等等。总之，节点的属性信息为后续复杂网络的分析提供了必不可少的信息，属性信息的抽取同样具有重要的意义。
对于固定格式的半结构化文本，可以通过一个属性模板来抽取属性信息，比如，科技文献都有固定的格式信息（作者、期刊号等），通过特征模板，来抽取这些属性信息。对于无结构化的文本，则首先要找出属性集，而后再进行属性信息抽取。Liu Bing[11]研究的工作是要找出用户对某产品的评价信息，也就是提取针对每个属性的描述评价信息。文中主要是通过有指导规则的方法进行的，首先人工标注训练集，再应用关联规则挖掘算法进行规则生成，经过后续处理，去掉无用的规则，再应用这些规则，提取出产品的属性，通过词频校正一些错误的属性，最后将属性信息映射到相应的属性上，完成属性信息的抽取。王璐等[29]使用共现分析的方法从术语定义抽取术语属性。文中以科技术语和词为基本处理单元，通过词在术语定义群中出现的总次数，最终能够得到定义空间内的术语与术语属性之间的同现概率矩阵。通过这个矩阵可以得到术语定义群中相应的科技术语及其属性的同现概率，并用该矩阵对关键词进行修正，这样，概率大的词权重就得到了加强，术语属性可能性率大表示该词术语属性可能性大，就认为这是一个比较重要的词，对反映术语的定义具有重要的贡献，相应的该词的权重应该得到加强。
3.1.2 实体解析
抽取实体后，还不能直接构建成正确的网络。现实中，存在着大量的“同物异名”、“同名异物”现象，如何合并“同物异名”，如何区分“同名异物”，称之为实体解析，它是构建复杂网络必须解决的一个难题。
在对文献的分析中，同一作者姓名可能有不同的表述或多个作者对应同一姓名标识的情况相当常见，因此在实体解析中，对人名解析的需求更为迫切。
Indrajit等作者在聚类过程中将节点属性、链接属性以及链接结构等因素作为相似性衡量标准来挖掘图结构中数据实体的方法GBC-ER[12]，采用聚类方法将属性相似性与链接相似性通过加权公式把两者的效果“并行”加入到聚类过程中进行实体解析。Lise Getoor等人利用LDA模型来进行实体解析的方法LDA-ER[13]，Byung等人利用DistQC取得了很好的效果[14]。
吴斌等[27]提出了一种新的实体解析方法NDC，这种方法专门针对中文文献索引数据库中的重名问题。该方法包含以下三个步骤：第一步分离实体属性，用优化了的中文字符串匹配算法来计算同名作者之间属性的相似性并根据相似性标准来合并作者实体；第二步，利用复杂网络理论分析作者的链接属性、链接结构，做进一步的判断来压缩网络；第三步，利用协同分析方法分析作者合作信息，合并实体从而更进一步地压缩网络。通过实验对比发现NDC方法能够获得较为理想的F值，同时执行效率也能满足实际应用的要求。该方法已经用于数字图书馆的新型检索系统的数据预处理。
3.2 边信息的抽取技术
如果说实体抽取构建了复杂网络的节点，那么实体关系抽取显然是要找出节点之间的边。与实体抽取类似，实体关系的类型也是预先定义的，例如：地理位置关系、雇佣关系等等。在yahoo网对娱乐明星进行搜索时，yahoo会为我们展示关于该明星的一张较为全面的社会关系网，比如该明星的父母、子女、伴侣、好友、经纪人等等信息，让人一目了然，这也是实体关系抽取在复杂网络构建中的一个典型应用，通过实体间各种关系的抽取，生成节点间具有各种不同属性的边。
实体关系抽取也有基于规则的方法和基于统计的方法。在现有的基于规则学习的关系抽取算法中，SRV是一个较好的算法[15]。SRV考虑的是单个词的形式特征，不涉及词性、语义等。SRV是一个基于FOIL的关系抽取算法，它基于两类特征进行归纳：一类是符号特征，将词映射到一个任意值；一类是关系特征，将一个词映射到同一文档中的另一个词。SRV通过一个自顶向下的覆盖算法覆盖整个样本。在学习一条规则的过程中，它考虑的样本是所有的负例和还未被当前规则覆盖的正例，选择局部最优并添加文字到规则的前件，直到当前规则不再覆盖反例或找不到下一个文字。每生成一条规则，移去其覆盖的正例，然后生成下一条规则。基于统计的方法则主要是通过机器学习的方法。通常的机器学习算法需要构造特征向量形式的训练数据，然后使用各种机器学习算法，如支持向量机[16]、Winnow[17]等作为学习机构造分类器。这种方法被称作基于特征向量的学习算法。接着又出现了基于Kernel的学习算法[18]，与基于特征向量的学习算法不同，其不需要构造特征向量，而是直接使用字符串的原始形式作为处理对象，需要做的只是计算任何两个对象之间的Kernel函数，Kernel的一个致命缺点是训练和预测的速度太慢，不适于处理大量的数据。
具体应用中，Liu Xin[1,19]的研究，试图从文本资料中，发现基于命名实体的可重叠社区。文中先是识别并标记出命名实体，对于出现在同一句话中的多个同类型实体之间则被认为存在某种联系，作为边并构建出网络，而后进行社区发现等分析。Wilkinson[2]和Adamic[20]的研究通过抽取文献集中的基因构建网络进行分析，节点为抽取的基因，在医学文摘中如果两个基因与某一疾病有关并共同出现至少一次，这两节点就有边的关系，构建出复杂网络，并进行特征分析，社团发现等网络挖掘，得出了不少有价值的信息。张素香[30]针对中文信息抽取系统中建立提取事件模板的难点问题，基于Bootstrapping思想，提出了一种简单、可行的实体关系自动生成方法，利用由种子词和种子模板组成的知识库建立学习器，采用标量聚类的方法，通过种子模板抽取更多的与种子词相似语义关系的特征词。在此基础上，利用最近邻居的原则，进而生成更多的关系抽取模板。2004年的ACL会议上，无指导的语义关系抽取方法首次被提出[31]。在该方法中，作者首先过滤掉出现频率较低的命名实体对，然后提取每个命名实体对实例的上下文；接下来对这些实体对应的上下文进行聚类；最后对得到的类进行统计找出相对重要的词汇，并以该词汇标注该类命名实体对的关系。
4 小说人物关系自动提取实例分析
4.1 相关工作
目前，国内外在小说人物关系展示和分析这方面的研究不是很多。刘婷等[33]从名著《红楼梦》中选取主要人物以家族关系为依据生成了一个社会网络，网络中的点代表小说中的人物，边表示亲属关系，然后通过MCG社团发现算法，得到家族社团结构图。沈项军[34]对Knuth根据法国小说作家维克多·雨果的小说《悲惨世界》按照不同场景出现的关联人物所构建的网络进行了分析，并分割出子网络。赫南等[35]对于搜集的国内2001～2006年拍摄电影的数据，应用复杂网络的理论和方法，对其中的演员合作关系所形成的网络进行了初步研究。
本节基于信息抽取技术，试图自动抽取出小说人物关系，构建出复杂网络，然后对网络进行展示与分析。
4.2 构建方法
本文的实验样本是文本小说——《三国演义》［白话版］，欲对小说人物及其关系进行信息抽取，然后分别作为节点和边构建成复杂网络，最后将网络可视化并进行分析。
具体实验中，首先对文本数据进行常规的自然语言处理，包括分词和词性标注，然后基于最大熵的隐马尔可夫模型识别出人名，作为复杂网络的节点；设置上下文窗口，比如设置为8，即在一句话中出现的两个实体，并且中间间隔小于或等于8个词，认为它们之间存在某种关系，抽取出来组成实体对，然后应用Hasegawa[31]所提出的思路，先根据实体对出现频次进行过滤，然后抽取实体对的上下文，并对实体对的上下文进行聚类，最后用Chen jinxiu[32]提出的DCM关系描述方法对聚出的类别进行描述，作为人物之间的关系描述。由于小说中出现的人物较多，为了凸现主要人物之间的关系，设阈值对实体对进行过滤，实验中，人物出现频率阈值设为30，实体对共现阈值设为2，展示这一复杂网络如图1。
图1 《三国演义》人物及其关系展现
4.3 结果评价
通过网络图，能较为清晰地展示出小说的主要人物及其之间大致关系。共展示出29个人物，其中节点的度是人物重要性的一个直接反映；聚出了34种人物关系，标识着76条边。有了这一网络，不仅能从总体上把握小说的人物及关系，而且通过复杂网络的挖掘算法，比如社区发现等还能够挖掘出更多的隐藏信息。
实验中加入了少量的人工干预过程，有少数错误识别的人名被人工过滤掉了，而且关系的描述词中也过滤了一些没有明显关系意义的词汇。如何完全脱离人工而又比较准确地抽取信息是我们下一步努力的方向。
5 结语
信息抽取经过20多年尤其是最近10多年的发展，已经成为自然语言处理领域一个重要分支，其独特的发展轨迹——通过系统化，大规模的定量评测推动研究向前发展，使信息抽取技术走向成熟。而近几年，复杂网络研究也方兴未艾，对于各类网络特征的研究也越来越受到不同领域的研究者的关注。对于将来的复杂网络研究，应当充分利用完善的信息抽取技术，使其发挥巨大的作用，应用了信息抽取技术的复杂网络将会为我们提供更丰富更全面的信息。
收稿日期：2008-05-01
标签：自然语言处理论文; 复杂网络论文; 命名实体识别论文; 实体关系图论文; 文本分类论文; 相关性分析论文; 网络节点论文; 文本分析论文;