本站原创摘 要:将本体图中每个顶点的相关信息用一个向量表示.根据本体图自身的结构将顶点分成k个部分.在每个部分中选取样本点组成S,并选择相应的排序亏损函数.运用k.部排序学习算法得到最优排序函数,从而将本体结构图中每个顶点映射成一个实数,通过比较实数间的差值判断两概念的相似程度.实验表明该方法对于计算本体概念间的相对相似度是有效的.
关 键 词:本体；相似度计算；k.部排序；排序函数；排序亏损函数
中图分类号:
TP393.092文献标志码:A
Ontologysimilarityputationusingk.partiterankingmethod
LANMei.hui1*,RENYou.jun1,XUJian1,GAOWei2,3
(
1．CollegeofComputerScienceandEngineering,QujingNormalUniversity,QujingYunnan655011,China,
2．CollegeofInformation,YunnanNormalUniversity,KunmingYunan650092,China,
3．CollegeofmathematicalSciences,SoochowUniversity,SuzhouJiangsu215006,China
Abstract:
Thispaperrepresentstheinformationofeachvertexinontologygraphasector.Accordingtoitsstructureofontologygraph,theverticesaredividedintokparts.Itchoosesverticeromeachpart,andchoosesthefunctionasrankingloss.Itusesk-partiterankinglearningalgorithmtogettheoptimizationrankingfunction,mapseachvertexofontologystructuregraphintoarealnumber,thencalculatestherelativesimilaritiesofconceptsbyparingthedifferencebetweenrealnumbers.Experimentalresultshowsthatthemethodforcalculatingtherelativesimilaritybetweentheconceptsofontologyiseffective.
Thispaperrepresentedtheinformationofeachvertexinontologygraphasector.Accordingtoitsstructureofontologygraph,theverticesweredividedintokparts.Itchoseverticeromeachpart,andchosethe
rankinglosunction.Itusedk.partiterankinglearningalgorithmtogettheoptimizationrankingfunction,mappedeachvertexofontologystructuregraphintoarealnumber,andthencalculatedtherelativesimilaritiesofconceptsbyparingthedifferencebetweenrealnumbers.Theexperimentalresultsshowthatthemethodforcalculatingtherelativesimilaritybetweentheconceptsofontologyiseffective.
Keywords:
ontology,similarityputation,k.partiteranking,rankingfunction,rankinglosunction
0引言
在计算机科学领域,本体被定义为共享概念模型的形式化规范说明.目前本体已应用在智能信息集成、协作信息系统、信息检索、电子商务和知识管理等领域.作为一种有效表现概念层次结构和语义的模型,本体技术经过近十年的发展已经成熟,目前已经具备比较系统、完善的工程理论、表示方法和构造工具.近年来,本体相似度计算的研究已经成为信息科学领域研究的热点,并应用于医学［1］、生物学［2］、社会科学［3］等诸多领域.期间,大量优秀的本体相似度计算方法脱颖而出,并取得巨大的成功.部分计算方法可参考文献［4-8］.
排序学习算法由于其广泛的应用背景而越来越受到国内外学者的关注.设X为实例空间,X中的每一个元素代表一个需要被排序的对象,称为实例.排序函数f：X→R,是一个得分函数.它将每个实例映射成一个实数,通过比较实数间的大小来对实例进行排名.即,设xi,xj∈X,若f(xi)>f(xj),则xi的排名高于xj.排序学习算法的目标是需找最优排序函数.著名的排序学习算法有RankBoost算法［9］、rankingSVMs［10］、RankNet算法［11］、MFoM算法［12］、Magnitude.Preserving排序算法［13］、基于回归的子集排序算法［14］、RLR算法［15］、p.泛数推进排序算法［16］.
本文将提出一种基于k.部排序学习方法的本体相似度计算算法.本文的组织结构如下：首先,我们将对k.部排序学习算法作一个大致的介绍；其次,我们将在第三节中分析已有本体相似度计算算法的弊端,并阐明我们的动机,即为什么要用k.部排序学习方法来计算本体相似度,它的优点在哪里；再次,并通过一个例子对算法进行具体的描述,最后,通过实验说明本文提出的算法是有效的.
1k.部排序学习算法k.部排序学习算法［17］是一种特殊的排序学习算法.其训练实例分成k个子集:S1等于(x11,等,x1n1),等,Sk等于(xk1,等,xknk),它们的选取分别独立地服从X上的随机分布D1,等,Dk.Sa中每个元素的排名高于Sb中任何一个元素(a 摘 要:将本体图中每个顶点的相关信息用一个向量表示.根据本体图自身的结构将顶点分成k个部分.在每个部分中选取样本点组成S,并选择相应的排序亏损函数.运用k.部排序学习算法得到最优排序函数,从而将本体结构图中每个顶点映射成一个实数,通过比较实数间的差值判断两概念的相似程度.实验表明该方法对于计算本体概念间的相对相似度是有效的. 关 键 词:本体；相似度计算；k.部排序；排序函数；排序亏损函数 中图分类号: TP393.092文献标志码:A Ontologysimilarityputationusingk.partiterankingmethod LANMei.hui1*,RENYou.jun1,XUJian1,GAOWei2,3 ( 1．CollegeofComputerScienceandEngineering,QujingNormalUniversity,QujingYunnan655011,China, 2．CollegeofInformation,YunnanNormalUniversity,KunmingYunan650092,China, 3．CollegeofmathematicalSciences,SoochowUniversity,SuzhouJiangsu215006,China Abstract: Thispaperrepresentstheinformationofeachvertexinontologygraphasector.Accordingtoitsstructureofontologygraph,theverticesaredividedintokparts.Itchoosesverticeromeachpart,andchoosesthefunctionasrankingloss.Itusesk-partiterankinglearningalgorithmtogettheoptimizationrankingfunction,mapseachvertexofontologystructuregraphintoarealnumber,thencalculatestherelativesimilaritiesofconceptsbyparingthedifferencebetweenrealnumbers.Experimentalresultshowsthatthemethodforcalculatingtherelativesimilaritybetweentheconceptsofontologyiseffective. Thispaperrepresentedtheinformationofeachvertexinontologygraphasector.Accordingtoitsstructureofontologygraph,theverticesweredividedintokparts.Itchoseverticeromeachpart,andchosethe rankinglosunction.Itusedk.partiterankinglearningalgorithmtogettheoptimizationrankingfunction,mappedeachvertexofontologystructuregraphintoarealnumber,andthencalculatedtherelativesimilaritiesofconceptsbyparingthedifferencebetweenrealnumbers.Theexperimentalresultsshowthatthemethodforcalculatingtherelativesimilaritybetweentheconceptsofontologyiseffective. Keywords: ontology,similarityputation,k.partiteranking,rankingfunction,rankinglosunction 0引言 在计算机科学领域,本体被定义为共享概念模型的形式化规范说明.目前本体已应用在智能信息集成、协作信息系统、信息检索、电子商务和知识管理等领域.作为一种有效表现概念层次结构和语义的模型,本体技术经过近十年的发展已经成熟,目前已经具备比较系统、完善的工程理论、表示方法和构造工具.近年来,本体相似度计算的研究已经成为信息科学领域研究的热点,并应用于医学［1］、生物学［2］、社会科学［3］等诸多领域.期间,大量优秀的本体相似度计算方法脱颖而出,并取得巨大的成功.部分计算方法可参考文献［4-8］. 排序学习算法由于其广泛的应用背景而越来越受到国内外学者的关注.设X为实例空间,X中的每一个元素代表一个需要被排序的对象,称为实例.排序函数f：X→R,是一个得分函数.它将每个实例映射成一个实数,通过比较实数间的大小来对实例进行排名.即,设xi,xj∈X,若f(xi)>f(xj),则xi的排名高于xj.排序学习算法的目标是需找最优排序函数.著名的排序学习算法有RankBoost算法［9］、rankingSVMs［10］、RankNet算法［11］、MFoM算法［12］、Magnitude.Preserving排序算法［13］、基于回归的子集排序算法［14］、RLR算法［15］、p.泛数推进排序算法［16］. 本文将提出一种基于k.部排序学习方法的本体相似度计算算法.本文的组织结构如下：首先,我们将对k.部排序学习算法作一个大致的介绍；其次,我们将在第三节中分析已有本体相似度计算算法的弊端,并阐明我们的动机,即为什么要用k.部排序学习方法来计算本体相似度,它的优点在哪里；再次,并通过一个例子对算法进行具体的描述,最后,通过实验说明本文提出的算法是有效的. 1k.部排序学习算法k.部排序学习算法［17］是一种特殊的排序学习算法.其训练实例分成k个子集:S1等于(x11,等,x1n1),等,Sk等于(xk1,等,xknk),它们的选取分别独立地服从X上的随机分布D1,等,Dk.Sa中每个元素的排名高于Sb中任何一个元素(a +∪{0}为排序亏损函数,对于排序函数f：X→ 及x,x′,排序亏损函数分配一个非负实数l(f,x,x′)用来衡量当f(x)与f(x′)的大小关系与x,x′的实际排名顺序不符时的惩罚量.一类重要的排序亏损函数lγ(γ>0)定义如下: lγ(f,x,x′)等于 1(f(x)－f(x′))≤0 1－(f(x)－f(x′))γ,0<(f(x)－f(x′))<γ? 0,(f(x)－f(x′))≥γ k.部排序学习函数f的好坏一般可用期望l.误差 Rl(f)等于1∑k－1a等于1∑kb等于a+1nanb∑k－1a等于1∑kb等于a+1nanbEx～Da,x′～Db{l(f,x,x′)}(1) 来衡量,Rl(f)越小说明f越好.但由于无法预知D1,等,Dk,因此在实际应用中Rl(f)是无法计算的.由于排序函数f是通过样本集S训练得到的,从而使用经验l.误差: R^l(f,S1,等,Sk)等于 1∑k－1a等于1∑kb等于a+1nanb∑k－1a等于1∑kb等于a+1∑i:xai∑j:xbjl(f, xai,xbj)(2)来判断f的好坏.但最小化R^l(f,S1,等,Sk)所得到的f有可能光滑性较差,上下波动很大.这会导致f泛化性能差,无法应用于S以外的数据.通常需要增加一个正则项来达到平衡的效果,即最小化正则经验l.误差: R^λl(f,S1,等,Sk)等于 1∑k－1a等于1∑kb等于a+1nanb∑k－1a等于1∑kb等于a+1∑i:xai∑j:xbjl(f, xai,xbj)+λN(f)(3) 来得到排序函数.这里,F是X上的实值函数类,N：F→ +∪{0}为正则化函数,λ>0为正则化参数.最终通过训练样本S等于(S1,等,Sk)输出的排序函数fS1,S2,等,Sk∈F满足： fS1,S2,等,Sk等于argminf∈FR^λl(f,S1,等,Sk)(4) 例1当k等于2时即为著名的二部排序学习算法.其训练实例分成两个子集：正实例集S+等于(x+1,等,x+m)和负实例集S－等于(x－1,等,x－n),它们的选取分别独立地服从X上的随机分布D+、D－.正实例集中每个元素的排名高于负实例集中任何一个元素.训练集S等于(S+,S－)∈Xm×Xn共有mn个训练数据. 第4期 兰美辉等：k.部排序本体相似度计算 计算机应用第32卷 2算法思想 2.1已有算法的弊端 目前大部分本体相似度计算方法都是根据某种启发式规则设计两顶点间相似度计算公式,两两计算相似度,此类方法计算量非常大,而且往往需要由领域专家来确定诸多参数. 例2一类传统的本体相似度计算模式如下： Sim(A,B)等于α1Simname(A,B)+α2Siminstance(A,B)+ α3Simattribute(A,B)+α4Simstructure(A,B)(5) 其中αi(1≤i≤4)是由领域专家或经验值决定的参数,满足α1+α2+α3+α4等于1.即A,B的相似度由它们的名称、结构、实例、属性四个方面的相似度加权得到.这种方法存在计算量大、待定参数多、不直观等诸多弊端. 一种改进的方法是将本体图映射成实直线,对应地每个顶点映射成实数,通过比较顶点对应实数间的差值来判断相似性. 例3［8］利用图上顶点所含信息相近的原则,将问题转换为寻找如下函数： f等于argmin‖f‖等于1∫‖f‖2(6) 进而运用谱图理论,将问题转化为求解图的拉普拉斯矩阵（可以看成流形拉普拉斯Beltrami算子在图上的Laplacian逼近）的次小特征值对应特征向量问题. 但此类方法同样存在弊端：当本体图的顶点数量非常庞大时,拉普拉斯矩阵的阶非常大,如果直接计算其次小特征值对应的特征向量,计算量非常大.特别是在本体应用于生物学,遇到信息量非常大的基因本体,此类方法几乎无效. 2.2算法设计思路 本文算法设计的思想是：不能用传统的启发式计算公式来两两计算相似度.沿用例3的思路,将本体图映射成实直线,将图中每个顶点映射成实数.通过比较实数间的差值的大小来判断两个概念是否有较高的相似度；其次,在本体顶点数量庞大的情况下,不能直接计算拉普拉斯矩阵.因此我们想到运用排序学习方法,取一部分顶点作为样本集来得到排序函数,从而将本体图中每个顶点映射成实数. 广义上的排序函数均可以用如式(7)表示： FS(u)等于1m2∑z1,z2∈Sh(u,z1,z2)(7) 其中：h是排序亏损函数,u是排序函数,S是样本集,m是S中样本的数量.可见,一般排序学习算法需要对样本集中每一对样本进行比较.如果m的值很大,得到最优排序函数的计算量还是非常大的.另一方面,由于本体图是一个自上而下的层次结构,并且在多数应用背景下可视为树,同一分支下顶点的相似度高于不同顶点下顶点的相似度.因此最高层顶点下的每一个分支可以看成一个部分.有时为了均衡,可以把某个顶点数量较多的分支分成几个部来处理.并且根据它们的关系将这些部进行排序.然后在每个部分中抽取一部分顶点组成S,得到fS1,S2,等,Sk. 由此可见,运用k.部排序学习方法来得到最优排序,从而将本体图映射成实直线的方法既在广义排序学习算法的基础上减少了计算量（只对比不同分支的样本,来自同一分支的样本不需要比较）,又充分利用了本体图自身的结构特点. 3新算法描述 步骤1预处理.将本体图中每个顶点的信息用一个向量表示. 5结语 本文给出了基于k.部排序学习算法的本体相似度计算.该算法最大的优点在于适用于顶点数量庞大的情景.因此本算法对于生物学基因分析等特殊领域有重要的参考价值.由于本文算法中得到的最优函数fS1,S2,等,Sk依赖于S的选取,在不同的样本集合下得到的排序是不同的.对于样本的选取对最后排序结果的影响,有待我们进一步分析.参考文献: ［1］ MORKP,BERNSTEINP.Adaptingagenericmatchalgorithmtoalignontologiesofhumananatomy［C］//Proceedingsof20thInternationalConferenceonDataEngineering.LosAlamitos:IEEEComputerSociety,2004:787-790. ［2］ LAMBRIXP,EDBERGA.Evaluationofontologymergingtoolsinbioinformatics［EB/OL］.[2011-06-10].helix.web.stanford.edu/psb03/lambrix.pdf. ［3］ BOUZEGHOUBA,ELBYEDA.OntologymappingforWeb.basededucationalsystemsinteroperability［J］.InteroperabilityinBusinessInformationSystems,2006,1(1):73-84. ［4］ WANGY,GAOW,ZHANGY,etal.Ontologysimilarityputationuserankinglearningmethod［C］//3rdInternationalConferenceonComputationalIntelligenceandIndustrialApplication.Washington,DC:IEEEComputerSociety,2010:20-23. ［5］ WANGY,GAOW,ZHANGY,etal.Pushrankinglearningalgorithmongraphs［C］//InternationalConferenceonCircuitandSignalProcessing.Washington,DC:IEEEComputerSociety,2010:368-371. ［6］ LANM,XUJ,GAOW.Ontologysimilaritymeasurebasedonpreferencegraphs［C］//InternationalConferenceonE.businessandInformationSystemSecurity.Washington,DC:IEEEComputerSociety,2011:667-670. ［7］ LANM,XUJ,GAOW.OntologymappingalgorithmbasedonprimalRankRLS［C］//InternationalConferenceonE.businessandInformationSystemSecurity.Washington,DC:IEEEComputerSociety,2011:788-790. ［8］ 兰美辉,徐坚,孙瑜.基于谱图理论的本体相似度计算［J］.计算机工程与应用,2011,47(28):110-112. ［9］ CYNTHIAR,ROBERTE,INGIRDD.Boostingbasedonaoothmargin［C］//Proceedingsofthe16thAnnualConferenceonComputationalLearningTheory.Berlin:Springer.verlag,2004:502-517. ［10］ JOACHIMST.Optimizingsearchenginesusingclickthroughdata［C］//Proceedingsofthe8thACMSIGKDDInternationalConferenceonKnowledgeDiscoveryandDataMining.NewYork:ACM,2002:133-142. ［11］ BURGESC.Learningtorankusinggradientdescent［C］//Proceedingsofthe22ndInternationalConferenceonMachineLearning.NewYork:ACM,2005:89-96. ［12］ CHUATS,NEOSY,GOHHK,etal.TRECVID2005bynuspris［C/OL］.[2011-10-01]..nlpir.nist.gov/projects/tvpubs/tv5.papers/nus.pdf. ［13］ CORINNAC,MEHRYARM,ASHISHR.Magnitude.preservingrankingalgorithms［C］//Proceedingsofthe24thInternationalConferenceonMachineLearning.NewYork:ACM,2007:169-176. ［14］ DIDC,TONGZ.Subsetrankingusingregression［C］//19thAnnualConferenceonLearningTheory.Berlin:Springer.verlag.2006:605-619. ［15］ RONGY,ALEXANDER,HAUPTMANND.Efficientmargin.basedranklearningalgorithmorinformationretrieval［EB/OL］.[2011-06-20].省略rmedia.cs.cmu.edu/documents/CIVR06_yan.pdf. ［16］ CYNTHIAR.Rankingwithap.normpush［C］//19thAnnualConferenceonLearningTheory.Berlin:Springer.verlag,2006:589-604. ［17］ RAJARAMS,AGARWALS.Generalizationboundork.partiteranking［EB/OL］.[2011-06-25].drona.csa.iisc.er.in/～shivani/Publications/2005/nips05workshop.pdf. ［18］ theGeneOntology[EB/OL].[2011-08-01]..省略. ［19］ CRASWELLN,HAWKINGD.OverviewoftheTREC2003Webtrack［EB/OL］.[2011-06-01].did.省略/pubs/overview_trecweb2003.pdf.
X×X×X→