实体识别是数据质量的一个关键方面,对于数据集成和数据挖掘都至关重要。本文将研究结构化数据的实体识别。数据集成和数据挖掘都可能涉及多个数据源,不同的数据源有不同的描述实体的方式。由于拼写错误、缩写方式不同、描述格式不同、属性值缺失、实体的某些属性值随着时间推移发生演化(比如年龄、居住地点、工作单位)等,描述同一真实世界实体的不同数据对象存在差异。实体识别是将一个或多个数据源中描述同一真实世界实体的数据对象识别出来。实体识别最早出现在人口普查和医疗卫生等社会公共服务领域,很早就受到公共机构的重视和依赖,从而促进了实体识别的研究。实体识别已经有几十年的研究历史,出现了许多有效的实体识别技术。然而,已有工作依然存在一些不足,其中包括以下四个方面:(1)已有的实体识别方法,要么需要领域专家设计匹配规则,要么需要较大量的人工标注的训练集才能学习匹配规则(也称为实体识别分类器)。(2)多类型关联数据中的实体关系可以促进实体识别,然而已有的工作无法同时地①解决数据对象属性值缺失的问题,②解决数据对象重名(主要指人名)的问题,以及③利用实体关系来提高实体识别的精确性和优化识别顺序。(3)已有的工作通常利用通用的聚类算法来解决非监督的实体识别中匹配决定的问题,由于通用的聚类算法没有考虑实体识别的特点,其精确性有限。(4)面对渐近式实体识别需求,现有的渐近式实体识别方法需要已知最优的分块键或排序键,并且无法从数据集中直接选择冗余度最高的数据。针对上述四点不足,本文的主要创新点如下:(1)针对监督的实体识别,提出一个基于遗传算法和主动学习的、监督的实体识别方法,可以用较少量的人工标注数据生成高效的实体识别分类器。该方法通过遗传进化来学习实体识别分类器,遗传进化包括种群初始化、个体选择、个体复制、基因的交叉和变异等。特别地,提出了一组特殊的交叉操作,分别针对分类器的一个特定方面:相似度函数交叉负责为不同的属性比较分别选择合适的相似度函数,阈值交叉负责为每个属性比较设定适当的阈值,聚集交叉负责将多个属性比较有效地、逻辑地组合起来。这三个特殊的交叉操作有利于生成高效的分类器。同时将利用主动学习来减少学习过程所需的人工标注数据,提升学习速度。通过在多个数据集上充分的实验,证明本文提出的方法比己有方法具有更高的精确性,并且需要更少的人工标注的训练数据。(2)针对联合式实体识别,提出一个基于图的、迭代的联合式实体识别方法,用于识别多类型的关联数据。首先,利用多类型的、关联的数据对象集合构建数据对象关系图,将基于语义路径的相似度和属性相似度结合起来判断数据对象是否匹配;然后,合并匹配成功的数据对象,并对对象图中的相应数据对象结点及其周边执行局部图收缩,这两个操作使对象图的局部语义变得更丰富,促使在局部范围内产生出新的候选匹配对象对,以待后续识别,实现相似度传递,形成一个迭代的识别过程。随着不断迭代,对象图的语义不断丰富,提高了联合式实体识别的精确性。通过实验证明本文提出的联合式实体识别方法比己有的联合式实体识别方法和基于对象关系的单类型实体识别方法具有更高的精确性。(3)针对非监督的实体识别,提出一个基于图聚类的、非监督的实体识别方法。首先,利用数据对象及其相似度构建带权重的数据对象相似图。然后,聚类的基本逻辑是,类簇迭代地吸收离它最近的结点。聚类过程中,利用相似图上重启式随机游走来动态地计算类簇与结点的相似度。提出数据对象排序方法来优化聚类的顺序,提高聚类的精确性;提出一个优化的随机游走平稳概率分布计算方法,降低聚类的开销。通过在真实数据集和合成数据集上的实验,验证了本文提出的图聚类算法在实体识别匹配决定中的有效性。(4)针对渐近式的数据管理需求,提出一个基于多路分块的渐近式实体识别方法。该方法不要求提供最优的分块或排序的键,并且可以直接找出脏数据集中冗余度最大的区域。分为两个阶段,初始化阶段和迭代阶段。在初始化阶段,初步地生成候选数据对象对,并按匹配可能性排序后加入到候选队列。在迭代阶段,每次选择候选队列队首的候选对(即最可能匹配的)来处理,并且根据实时的实体识别结果,动态地更新候选对的匹配可能性,调整候选队列。这样减少了无用的数据对象比较,使得实时的识别结果最优化,提高了实体识别的渐近性。通过在真实数据集和合成数据集上的实验对比,说明本文提出的基于多路分块的渐近式实体识别方法显著地优于己有工作。