多信息加权融合实体对齐算法
2021-07-16马建红刘双耀
马建红 刘双耀 杨 珺
(河北工业大学人工智能与数据科学学院 天津 300401)
0 引 言
近年来,知识图谱[1]一直是各领域研究的热点,知识图谱的构建能够在一定程度上促进创新的发展,构建完整的知识图谱需要通过融合多个异构数据源来解决单一数据源知识涵盖不足、属性缺失等问题。因此多源异构知识库的融合问题,便成为知识图谱发展过程中的研究热点,其中实体对齐是异构数据源融合的关键步骤,即发现两个或多个数据源中指向现实中同一物质的实体对[2]。由于不同数据源本体的异构性,导致知识的分类结构、表述规范存在一定的差异,如何解决这些差异,并完成多个数据源实体的对齐任务成为了实体对齐算法的难点。
数据源中实体普遍存在“一词多义”和“一义多词”等问题,如“氧气”可以代表化学元素、歌曲名称、电影名称、手机应用等多种物质;物理领域“磁通量”这个实体在不同的百科网站有不同的名称,在百度百科中命名为“磁通量”,在互动百科中命名为“磁通”。因此仅通过实体的名称属性难以确定两个实体是否为现实中同一实体,需要借助有效的实体对齐算法来判断两个实体是否为现实中同一实体,从而完成异构数据源的知识融合任务。
1 实体对齐算法
实体对齐算法基本分为两个方向,基于实体相似度理论[3]的实体对齐算法和基于表示学习[4]的实体对齐算法。文献[5]提出了一种实体属性与上下文主题特征相结合的实体对齐算法,该算法以人物类和影视类百科数据为测试集取得了不错的实验效果,但针对不具备完整上下文信息的数据表现不佳。文献[6]提出了一种基于网络语义标签的中文知识库实体对齐算法,在综合计算多种标签相似度的情况下取得了较好的对齐效果,其优点是充分利用了百科网站的分类标签,解决了实体属性信息缺失、摘要缺失的问题,但存在过度依赖实体标签的问题。文献[7]针对异构数据源提出了HistSim和DisNGram两种选择算法,HistSim利用实体对齐的历史数据计算实体对相似度,修剪不匹配的实体,DisNGram算法通过字符级别相似性度量来选择候选对齐实体。文献[8]针对大规模数据提出了一种基于贪心算法的实体间对齐关系的推断方法SiGMa,该方法组合字符串、属性和结构信息以贪婪的局部搜索方式发现可对齐的实体。文献[9]提出一种基于知识图谱嵌入的Bootstrapping实体对齐算法,通过迭代标注出可能对齐的实体,生成新数据加入知识嵌入的模型中进行训练,综合利用图谱全局信息进行实体对齐。
本文提出一种结合动态规划求解最小编辑距离及引入Doc2vec[10]模型挖掘文本语义特征的实体对齐算法。该算法主要分为两个部分,第一部分是对实体结构化信息进行数据规范化处理,制定统一描述框架,并通过最小编辑距离求解结构化属性相似度;第二部分是通过Doc2vec模型对已经去除停用词和分词的非结构化文本进行训练,提取包含其语义信息的特征向量,并通过余弦相似度进行相似度求解。最终通过权值调整,综合结构化属性相似度及非结构化文本相似度求解实体综合相似度进行实体对齐判断。同时设置对比实验对本文算法进行验证,实验表明,本文算法在准确率和迁移性上均有所提高。
2 多信息加权融合实体对齐框架
本文所解决的实体对齐问题主要针对百科网站及专业化学网站等数据源,通过设计网络爬虫爬取各数据源中实体的名称、简介、信息表、正文和标签等信息作为实验数据。
(1) 通过数据统计算法对原始数据进行数据分析,制定统一的知识表述规范,同时构建专业名词词典,用于训练分词工具及扩展知识库。
(2) 针对数据预处理后的结构化属性引入动态规划最小编辑距离求解其结构化属性相似度。
(3) 利用Doc2vec模型深度挖掘非结构化文本语义信息,生成包含文本语义信息的特征向量,并求解余弦相似度获取非结构化文本相似度。
(4) 通过权值调整,融合结构化属性相似度及非结构化文本相似度,获取实体综合相似度生成候选集合。
(5) 设定阈值进行实体对齐判断,输出可对齐实体集合。
多信息加权融合实体对齐框架如图1所示。
图1 多信息加权融合实体对齐框架
2.1 研究思路
(1) 通过对多个数据源的本体分析,制定统一的资源描述框架,用于融合后的数据存储。构建包含五万余条专业名词的领域词典,用于实现数据扩充和训练分词工具解决分词过程中专业名词强拆分等问题,提高实体对齐算法的实用性。
(2) 针对实体结构化属性及非结构化文本,分别采用动态规划最小编辑距离和Doc2vec模型深度挖掘包含文本结构信息及语义信息的特征向量求解其相似度,最终加权平均融合实体多信息,获取实体综合相似度,提高实体对齐算法的准确性。
2.2 数据预处理
2.2.1制定统一描述框架
各个数据源中实体属性信息包含了实体所拥有的所有属性及属性值等信息,但是由于数据源的本体异构性导致实体存在相同属性不同表达方式、相同属性值不同表述规范等问题,如百科中“分子量”就存在“分子量”“分子质量”“相对分子质量”等多种表达方式,同时相同的物质分子量值存在“16”“16g/mol”“16g·mol-1”等多种表达方式,这种问题会降低模型所求取的实体相似度,从而影响实体对齐的准确率。因此本文通过数据统计将从多数据源所爬取实体的所有属性及属性值的表示方式进行整合,结合众包及人工审核的方式,选取化学领域中常用的属性及属性值表示方式为模板,构建了统一的知识库表述规范。
2.2.2创建领域词典辅助分词
通过数据统计及众包分析,将所有百科网页中化学资源实体的名称及别名进行筛选、分类,同时爬取专业化学网站的化学词条名称,构建了包含52 124条化学实体名称的化学领域词典。
本文采用jieba分词工具对非结构化文本进行分词,但现有的jieba分词工具无法识别专业领域的新型名词,会产生强拆分问题,例如:“硝基丙烷”会被拆分为“硝基”“丙烷”;“甲苯磺酰氯”会被拆分为“甲苯”“磺酰氯”等,这样会严重影响训练模型的结果。因此,将整理的化学领域词典引入jieba分词工具进行训练,解决专业名词强拆分问题,最终完成对非结构化文本信息的分词工作,保证分词的准确性。
Doc2vec模型是一种用于句向量训练的模型,在输入层增添了一个新的句子向量Paragraph,并在同一个句子的若干次训练中是共享的,克服了词袋模型中忽略词序的缺点。由于Doc2vec模型需综合考虑语句中各词的前后信息,因此在去除停用词阶段仅去除正文中的标点符号及各类中英文符号。
2.3 最小编辑距离求解结构化属性相似度
2.3.1最小编辑距离
字符串的最小编辑距离是形容字符串Str1转换为字符串Str2的最少操作数,字符的操作包含插入、删除、替换三种,通过对字符串中字符的操作,使两个字符串相同,则最少的操作数为两个字符串的最小编辑距离[11],两个字符串的最小编辑距离越小证明两个字符串越相似,相同字符串的最小编辑距离为0。
将两个句子Str1与Str2当作两个字符串,假设Str1与Str2的长度分别为m和n,两者的编辑距离则可以表示为edit[m][n],则对句子进行操作时包含以下几种情况。
1)Str1与Str2末尾字符相同情况下不需要进行任何操作,则满足条件edit[m][n]=edit[m-1][n-1]。
2)Str1与Str2末尾字符不相同情况下则需要对两者之一的末尾字符进行相应操作,并计数加1,具体操作如下:
(1) 对Str1或Str2的末尾字符进行替换操作,使之相等,则此时edit[m][n]=edit[m-1][n-1]+1。
(2) 删除Str1末尾的字符,使Str1与Str2相等,则此时edit[m][n]=edit[m-1][n]+1。
(3) 删除Str2末尾的字符,使Str2与Str1相等, 则此时edit[m][n]=edit[m][n-1] + 1。
(4) 在Str1的末尾添加Str2的末尾字符,使Str1与Str2相等,则此时Str1的长度变为m+1,但Str1和Str2的末尾字符已经相等,因此只需要比较Str1的前m个字符与Str2的前n-1个字符,满足edit[m][n]=edit[m][n-1]+1。
(5) 在Str2的末尾添加Str1的末尾字符,使Str2和Str1相等,此时的情况与(4)相同,满足edit[m][n]=edit[m-1][n]+1。
3) 特殊情况,当Str1为空时,edit[0][n]=n;当Str2为空时,edit[m][0]=m。
根据以上情况可以得到求解最小编辑距离的动态规划方程为:
edit[m][n]=
(1)
其中flag计算式表示为:
(2)
因此可以通过动态规划方法求取两个句子的最小编辑距离edit(Str1,Str2),同时规定两个句子之间的最小编辑距离与最长句子长度的比值为两句子相似度。
2.3.2结构化属性相似度求解
通过数据预处理,实体E的结构化属性已经规范化,相同属性及属性值的表达形式及表述规范都有了极大的相似度,因此可以通过最小编辑距离来比较高效地判断两个属性对是否为同一属性以及属性值是否相同。定义实体属性S1与S2的最小编辑距离为edit(S1,S2),长度分别表示为len(S1)和len(S2),则实体属性S1与S2的相似度Sim(S1,S2)计算式为:
(3)
定义数据源A中实体Ea的m个结构化属性为Pa={Pa1,Pa2,…,Pam},对应的属性值为Va={Va1,Va2,…,Vam};
定义数据源B中实体Eb的n个结构化属性为Pb={Pb1,Pb2,…,Pbn},对应的属性值为Vb={Vb1,Vb2,…,Vbn};
实体Ea与实体Eb的t个公共属性集合CP=Pa∩Pb;
通过式(4)分别计算公共属性集合CP中t个属性的相似度SimCP(Pai,Pbi),其中edit(Vai,Vbi)表示实体Ea与实体Eb第i个公共属性的最小编辑距离,len(Vai)和len(Vbi)分别表示实体Ea与实体Eb第i个公共属性的长度。
(4)
最终定义wi为实体第i个结构化属性的权值,则通过式(5)求取实体Ea与实体Eb最终的结构化属性相似度SimZ(Ea,Eb)。
(5)
2.4 Doc2vec模型求解非结构化文本相似度
待对齐的实体除了包含结构化属性信息外还包含大量的非结构化文本信息,这些非结构化文本信息也包含大量的实体特性,如果实体的结构化属性稀疏或缺失,则难以依靠仅有结构化属性进行相似度求解,充分利用非结构化文本信息的特性,可以达到更好的实体对齐效果[12]。在非结构化文本的相似度求解过程中主要分为两个步骤,第一步是通过Doc2vec模型对已经预处理的非结构化文本进行联合训练,生成包含文本语义信息的特征向量;第二步是获取训练后实体各个非结构化属性的特征向量并迭代求解其余弦相似度。
2.4.1Doc2vec模型
Doc2vec模型是一种非监督式算法,可获得短语、句子和文章等文本的向量表达,Doc2vec模型主要包含“句向量的分布记忆模型(PV-DM)”和“分布词袋模型(PV-DBOW)”两种训练模式[13]。
如图2所示,在句向量的分布记忆模型(PV-DM)中每一个段文本用唯一的句向量来表示,存储在Paragraph矩阵的每一列中,同时每一个词用词向量来表示并存储在矩阵Word的某一列中,每次从一句话中滑动采样固定长度的词,取其中一个词作预测词,其他的作输入词。输入词对应的词向量Wordi和本句话对应的句向量Paragraph作为输入层的输入,将本句话的向量和本次采样的词向量相加求平均或者累加构成一个新的向量X,进而使用这个向量X预测此次窗口内的预测词Word4。
图2 句向量的分布记忆模型(PV-DM)原理图
句向量的分布记忆模型(PV-DM)从固定长度的句子中采用滑动窗口取样,通过随机梯度下降的方法训练句向量和词向量,在此过程中通过反向传播获得梯度,并针对每一个随机句子去更新模型参数,同时在预测阶段通过梯度上升方式获取一个新句子的句向量[14]。在这个模型里通过前后词语向量的首尾相连或求均值来预测新增词语,则最终生成的句向量可表示从当前上下文得来的信息,可以被当作包含句子语义信息的特征向量。
如图3所示,分布词袋模型(PV-DBOW)这种方式不把上下文中的词作为输入,而是强制这个模型在输出过程中从句子中随机抽取词来进行预测[15]。即在每次迭代的时候,从文本中采样得到一个窗口,再从这个窗口中随机采样一个单词作为预测任务,让模型去预测,输入就是句向量Paragraph。实际上,其意义在于从每一个随机梯度下降的循环中,抽取一个文本窗口,然后从该文本窗口中抽取一个词,最终通过一个分类任务得到句向量。
图3 分布词袋模型(PV-DBOW)原理图
2.4.2获取非结构化文本语义特征向量
Word2vec模型只是基于词的维度进行“语义分析”,并不具有上下文句子“语义分析”的功能。而Doc2vec模型是对Word2vec模型的改进,在训练过程中增加了一个段向量,通过在已有上下文和段向量的基础上预测单词存在的概率。因此Doc2vec模型的训练过程是对文本语义的挖掘过程,最终生成的文本表征向量包含了文本的语义信息。
将两个数据源中所有实体的非结构化文本属性进行编号,并放入同一个文件进行存储,以换行符进行分割。使用参数化的Doc2vec模型进行句向量训练,设置处理的滑动窗口大小为8个单词,将每个句向量的维度设置为100维,并从训练结果中提取每个非结构化文本属性的句向量表示,生成特征向量文档[16-19]。
2.4.3非结构化文本相似度求解
定义数据源A中实体Ea的m个非结构化文本属性为Fa={Fa1,Fa2,…,Fam};对应的特征向量为Va={Va1,Va2,…,Vam}。
定义数据源B中实体Eb的n个非结构化文本属性为Fb={Fb1,Fb2,…,Fbn};对应的特征向量为Vb={Vb1,Vb2,…,Vbn}。
提取每个待对齐实体对的非结构化文本属性特征向量V,将实体Ea的每个非结构化文本属性特征向量Va分别与实体Eb的n个非结构化文本属性特征向量Vb进行余弦相似度求解,|Vai|和|Vbi|表示特征向量Vai和Vbi的模长,则实体对间每个非结构化属性相似度Sim(Fai,Fbi)的计算式表示为:
(6)
设置相似度阈值为0.4,选取相似度最高属性对,若相似度大于阈值0.4,则归为相似属性,记录相似度,循环比较后最终得到的t个相似属性对,则通过式(7)求取实体Ea与实体Eb的非结构化文本相似度SimF(Ea,Eb)。
(7)
2.5 实体对齐判断
当通过动态规划最小编辑距离及Doc2vec模型训练语义特征向量等方法完成了待对齐实体对的结构化属性相似度SimZ(Ea,Eb)及非结构化文本相似度SimF(Ea,Eb)的求解后,定义w1、w2分别为结构化属性及非结构化文本所占的权值,最终通过式(8)对实体Ea、Eb的结构化属性相似度SimZ(Ea,Eb)及非结构化属性相似度SimF(Ea,Eb)进行权值归一获取实体综合相似度SimE(Ea,Eb)。
SimE(Ea,Eb)=w1·SimZ(Ea,Eb)+w2·SimF(Ea,Eb)
(8)
针对数据源A中的每个实体Ea通过SimE(Ea,Eb)值对数据源B中的实体Eb进行降序排序,生成最优候选序列,选取相似度最高且大于设定阈值的实体Eb当作可对齐实体。
3 实验与结果分析
3.1 实验数据集描述
百度百科及互动百科包含丰富的实体资源及较为完整的属性信息,因此为了验证本文算法的有效性,本文分别从百度百科及互动百科中随机抽取了部分化学领域实体,抽取的实体信息包含实体名称、实体摘要、实体信息表、实体正文等,同时通过数据统计及人工标注的方法形成了一定数量的测试集,具体数据量如表1所示。
表1 实验数据集
3.2 评价指标
实验采用评价指标为准确率P、召回率R、综合指标F1值,其定义如下:
(1) 准确率计算式表示为:
P=NT/(NT+NF)
(9)
式中:NT为实验对齐结果中正确对齐的实体对数目;NF为实验对齐结果中错误对齐的实体对数目。
(2) 召回率计算式表示为:
R=NT/NA
(10)
式中:NA为测试集中存在的可对齐实体对数目。
(3) 综合指标F1值计算式表示为:
F1=2PR/(P+R)
(11)
准确率表示通过本文实体对齐算法后所得到正确对齐结果的准确程度;召回率表示通过本文实体对齐算法后得到的准确对齐实体数占测试集中所有可准确对齐实体的比率;F1值为衡量准确率与召回率的综合指标。
3.3 实验设置
(1) 权值w1、w2。本文中实体对齐算法是将实体结构化属性相似度与非结构化文本相似度通过权值融合,求解实体综合相似度,并生成可对齐实体候选集合,判断实体对齐结果。因此在权值确定过程中人工抽取500对可对齐数据,分别采取结构化属性权值与非结构化文本权值w1:w2由大到小进行测试实验,以平均相似度高低为评价指标,结果如图4所示。
图4 w1、w2实验结果
由于实验数据是人工整理的可对齐数据,因此500对实验数据的平均相似度越高则权值比例越符合要求。实验结果表明结构化属性与非结构文本权值w1:w2调节为7 ∶3时最合适。将w1、w2代入式(8)可计算实体Ea和Eb的综合相似度SimE(Ea,Eb)。
(2) 相似度上界u、下界d、中间界限w。经过对多批数据集的实验结果总结,实体综合相似度SimE大于0.9的实体对可认定为一定可对齐实体,实体对相似度小于0.3的实体对可认定为一定不可对齐实体。因此设置相似度上界u为0.9,相似度下界d设置为0.3。
在实体对齐实验中实体综合相似度SimE需要在0.3与0.9之间取相似度阈值w,实体综合相似度小于w的认定为不可对齐实体,相似度大于w的认定为可对齐实体,w的取值直接影响实验结果的准确率、召回率及F1值。具体结果如图5所示。根据实验结果分析可得出如下结论,所取的相似度阈值w越大,实验结果的准确率越高,召回率越低,反之所取的相似度阈值w越小,实验结果的准确率越低,召回率越高。F1值是评价准确率和召回率的综合指标,因此相似度阈值的取值应根据F1值进行选取,由图5可知当相似度阈值取在0.5与0.6之间的时候F1值达到峰值,实验中取w为0.55。
图5 w取值实验结果图
3.4 实验结果
确定好模型及参数后,在整理好的实验数据集上进行测试,实验结果如表2所示,表中分别列出了百度百科及互动百科部分实体名称及通过多信息加权融合实体对齐算法求取的相似度,以及实体对齐结果。实验结果可以验证在预先设定的相似度阈值w为0.55情况下,多信息加权融合实体对齐算法可以获得很好的对齐效果。
表2 实体对齐结果
3.5 对比实验
为了进一步验证本文算法(MED+Doc2vec)的有效性,设置了如下对比实验,对比实验结果如表3所示。
表3 对比实验及结果
(1) MED+Doc2vec。采用最小编辑距离(MED)求解结构化属性相似度,Doc2vec模型挖掘非结构化文本语义信息,生成包含语义信息的特征向量,求解相似度,除召回率略低于LCS-LDA方法,准确率及F1值较其他方法均有提高。综合各项评价指标,可验证本文算法的有效性。
(2) MED+Word2vec。采用最小编辑距离(MED)求解结构化属性相似度,Word2vec模型训练特征词向量,采用向量拼接方法获取非结构化文本特征向量,计算非结构化文本相似度,最终综合求解实体相似度判断对齐结果。由于Word2vec模型主要是针对词向量进行训练,只考虑词的前后信息,经过拼接形成的句向量无法完全体现句子的语义信息导致准确率较低。
(3) LCS+LDA。采用最长公共子序列(LCS)求解结构化属性相似度,LDA提取非结构化文本主题词,构建特征向量,计算非结构化文本相似度,最终综合求解实体相似度判断对齐结果。由于LDA是一种词袋模型,主要通过提取的主题词进行向量建模,导致特征向量不能完全体现句子的完整信息造成准确率略低于本文算法。
(4) LCS+TF-IDF。采用最长公共子序列(LCS)求解结构化属性相似度,TF-IDF提取非结构化文本特征,构建特征向量,计算非结构化文本相似度,最终综合求解实体相似度判断对齐结果。由于TF-IDF仅考虑句子中出现词的词频特征,导致无法充分体现句子的语义信息,造成实验准确率较低。
通过对比实验结果可得多信息加权融合实体对齐算法除召回率略低于LCS+LDA实体对齐算法外,准确率及F1值较其他实体对齐算法均有明显提高。召回率略低于LCS+LDA实体对齐算法是实验数据中实体信息的缺失导致的,由于Doc2vec模型更注重通过词语顺序挖掘句子的语义信息,因此相比于LDA模型更加依赖信息的完整程度。但综合多项评价指标及最终实验结果,多信息加权融合实体对齐算法在准确率及实用性上均表现更佳。
4 结 语
为了解决多源异构数据库融合过程中实体对齐的问题,本文针对现有实体对齐算法的不足之处,提出一种多信息加权融合的实体对齐算法。通过动态规划最小编辑距离求解实体结构化属性相似度,结合Doc2vec模型深度挖掘非结构化文本语义信息,并求解包含语义信息的特征向量相似度,最终通过权值调节,融合结构化及非结构化属性相似度,获得实体综合相似度完成实体对齐任务。以百度百科及互动百科化学领域实体为数据集进行了实验验证,并通过与多种实体对齐算法的比较,有效验证了多信息加权融合实体对齐算法的有效性。
后续的研究将进一步对算法进行优化调整,并将本文算法应用于多种不同领域进行实验验证,同时深入研究大规模数据环境下实体对齐算法的效率问题,这对异构数据源的融合及完整知识图谱的构建有非常重要的意义。