1、第 46 卷第 6 期2023 年 6 月重庆大学学报Journal of Chongqing UniversityVol.46 No.6Jun.2023 基于进化算法的生物医学本体匹配技术王颖1，薛醒思1，卢家伟1，黄艺坤2（1.福建工程学院 信息科学与工程学院，福州 350118；2.福建师范大学协和学院 信息技术系，福州 350117）摘要：由于生物医学本体拥有规模庞大的概念和复杂概念间关系，已有本体匹配技术难以高效确定生物医学本体匹配结果。为解决这一问题，构建了生物医学本体匹配问题优化模型，提出基于进化算法的生物医学本体匹配技术来确定最优匹配结果。在求解生物医学本体匹配问题时，采用一种
2、新的生物医学本体概念相似度度量来确保匹配结果质量，并通过基于推理的概念对剪枝技术缩小算法的搜索空间，提高算法效率。实验结果表明，基于进化算法的生物医学本体匹配技术能有效匹配生物医学本体。关键词：进化算法；生物医学本体匹配；概念对剪枝中图分类号：TP182 文献标志码：A 文章编号：1000-582X(2023)06-130-06Evolutionary algorithm based biomedical ontology matching techniqueWANG Ying1,XUE Xingsi1,LU Jiawei1,HUANG Yikun2(1.School of Informati
3、on Science and Engineering,Fujian University of Technology,Fuzhou 350118,P.R.China;2.Department of Information Technology,Concord University College Fujian Normal University,Fuzhou 350117,P.R.China)Abstract:Since biomedical ontologies own large-scale concepts and complex relationships among them,the
4、 existing ontology matching techniques are not able to determine the biomedical alignment efficiently.To tackle this challenge,a mathematical optimal model for biomedical ontology matching problem is first constructed,and then an evolutionary algorithm(EA)based biomedical ontology matching technique
5、 is proposed to determine the optimal alignment.In particular,when solving the biomedical ontology matching problem,a novel biomedical concept similarity measure is utilized to ensure the quality of the alignment,and a reasoning-based concept pruning approach is used to reduce the algorithms search
6、space and improve its efficiency.The experimental results show that EA-based biomedical ontology matching technique is able to match the biomedical ontologies effectively and efficiently.Keywords:evolutionary algorithm;biomedical ontology matching;concept pair pruningdoi:10.11835/j.issn.1000.582X.20
7、23.06.012收稿日期：2020-04-21 基金项目：国家自然科学基金资助项目（62172095）；福建省自然科学基金资助项目（2020J01875）；福建省本科高校教学改革研究项目（FBJG20190156）。Supported by National Natural Science Foundation of China(62172095),National Natural Scientific Foundation of Fujian Provnce（2020J01875）and Fujian Province Undergraduate Universities Teaching
8、 Reform Research Project(FBJG20190156).作者简介：王颖(1980)，高级实验师，主要从事智能计算和本体匹配技术方向研究，（E-mail）。通信作者：薛醒思，教授，（E-mail）。王颖，等：基于进化算法的生物医学本体匹配技术第 6 期生物医学本体是对生物医学领域中存在的概念、实例及它们之间关系的规范化描述，使基于生物医学知识的智能系统之间准确理解彼此数据的真实含义，在语义层面上实现系统间的交互与协作12。近年来，生物医学本体被广泛应用在诸如病历的语义标注3、医学数据格式标准化4、医疗知识表示和共享5、临床数据集成和辅助诊疗等6应用领域。为满足不同领域需求，
9、本体工程师开发了如基因本体(gene ontology,GO)7、人类表型本体(human phenotype ontology,HPO)8、国家癌症研究术语本体(national cancer institute thesaurus,NCI)9和医学系统术语本体(systemized nomenclature of medicine,SNOMED-CT)10等众多生物医学本体。由于本体工程师们对于客观事物的认识、描述角度各不相同，导致不同生物医学本体之间存在严重异质问题，阻碍生物医学智能系统间的交互与协作。生物医学本体匹配技术可通过确定本体中异质概念间的对应关系来解决生物医学本体异质问题。A
10、greementMakerLight11、YAM-BIO12、XMap13和 LogMapBio14等目前已有的本体匹配技术在求解生物医学本体匹配问题时需要消耗大量时间且无法保证匹配结果质量。因此，如何有效识别异质的生物医学概念、提高生物医学本体匹配过程效率是求解生物医学本体匹配问题的关键。为有效且高效求解生物医学本体匹配问题，研究构建了生物医学本体匹配问题优化模型，并利用进化算法15确定最优匹配结果。笔者采用一种新的生物医学本体概念相似度度量技术确保匹配结果质量，通过基于推理的概念对剪枝技术来缩小算法的搜索空间并提高算法效率。1生物医学本体匹配问题生物医学本体是生物医学概念及概念间关系集合，
11、生物医学本体匹配结果是 2个本体中语义相同的概念对集合。本体匹配结果的质量通常利用查全率、查准率和 F度量16来评价，但需要专家提供标准的本体匹配结果。由于生物医学中的概念规模庞大，专家无法事先提供标准本体匹配结果，笔者提出一种近似度量技术评价生物医学本体匹配结果质量。通过实验观察发现，生物医学本体匹配结果的质量同匹配结果中的概念对数量和平均相似度值成正比。给定一个生物医学本体匹配结果A，提出如下公式近似评价生物医学本体匹配结果质量f(A)=2 r()A p()Ar()A+p()A，(1)式中：r(A)=|AM；|A|是A中概念匹配对的数量；M是大的正整数；p(A)=sim(ai)|A，sim
12、(ai)表示A中第i个概念对的相似度值。在此基础上，给定 2个生物医学本体O1和O2，生物医学本体匹配问题的数学优化模型定义如下 max f()Xs.t.X=()x1,x2,x|O1Txi0,1,2,|O2，(2)式中：|O1|和|O2|分别表示O1和O2中的概念数量；xi=j,j=1,2,;|O2|表示O1中第i个概念同O2中第j个概念形成概念对（若xi=0，则O1中第i个概念没有匹配上任何一个概念）；X表示一个本体匹配结果，该模型的目标是最大化f(X)的值。2生物医学概念相似度度量技术概念相似度度量技术是本体匹配技术的基础，生物医学概念的异质性高、专业性强、结构复杂，因此已有概念相似度度量
13、技术难以有效识别语义相同的生物医学概念。在基于概念名称、背景知识库和本体概念体系关系结构这三类相似度度量技术基础上，提出混合度量技术以识别异质的生物医学概念。给定 2个生物医学概念c1和c2，利用本体概念体系关系结构获取二者直接的子概念集合C1和C2，分别抽取出C1和C2中所有概念的名称和属性名称构建二者对应的信息档案p1和p2，通过其对应的信息档案p1和p2的相似度值来度量c1和c2的相似程度，相关的计算公式如下131重 庆 大 学 学 报第 46 卷sim(c1,c2)=i=1|p1maxj=1,2,|p2()sim()p1i,p2j+j=1|p2maxi=1,2,|p1()sim()p1
14、i,p2j|p1+|p2，（3）式中：|p1|和|p2|分别是p1和p2中元素的个数；p1i和p2j分别是p1和p2中第i个和第j个元素。当p1i和p2j在生物医学知识库 Unified Medical Language System(UMLS)16中是同义词时，sim(p1i,p2j)=1，否则sim(p1i,p2j)=N-gram(p1i,p2j)，其中 N-gram距离17是用于度量生物医学概念名称编辑距离最有效技术。3求解生物医学本体匹配问题的进化算法生物医学本体匹配问题是一个复杂的大规模优化问题，进化算法具有全局寻优能力、自动获取和指导优化搜索空间并自适应调整搜索方向，是求解该问题的
15、有效方法。提出的用于求解生物医学本体匹配问题的进化算法框架如表 1所示。该算法初始化进化代数t并随机初始化种群Pt，对种群中每个个体的质量进行评价；在每一代的进化过程中，通过赌轮盘方法来选出新一代种群，依据交叉概率对种群中的个体执行单点交叉操作以实现个体间的信息交换，依据变异概率对种群中的个体执行位点变异操作以保证种群多样性；最后更新精英个体（历史最优解）并将精英个体取代种群中适应度值最低的个体以保证精英个体不会在进化过程中丢失，当精英个体被更新后，算法依据新的精英个体信息对概念进行剪枝以缩小算法的搜索区域，当算法进化到最大代数tmax后终止，输出精英个体elite。3.1编码机制假设|C1|
16、和|C2|分别是 2个生物医学本体中概念集C1和C2中元素的个数，进化算法中的每个个体可表示为长度为|C1|的一维数组N1N2N|C1，其中，Ni0,1,2,|C2|。当Ni=j 1,2,|C2|时，表示C1中的第i个概念同C2中的第j个概念匹配上；当Ni=0时，表示C1中的第i个概念没有匹配上C2中的任何一个概念。3.2基于推理的生物医学概念对剪枝针对大规模本体匹配问题，目前是通过本体划分算法将大规模生物医学本体划分为若干本体分块，问表 1进化算法框架Table 1The framework of Evolutionary Algorithmt=0;/初始化进化代数initialize the Population Pt;/初始化种群evaluate(Pt);/评价种群while t tmaxSt=select(Pt);/选择操作Ct=crossover(St);/交叉操作Pt+1=mutation(Ct);/变异操作evaluate(Pt+1);save elite();/保留精英个体if elite is updatedpruning mapping pairs;/概念对剪枝en