何国英,高 炜
(1.云南师范大学经济与管理学院,昆明 650500;2.云南师范大学信息学院,昆明 650500)
作为一种结构化存储和表示数据的模型,本体近几年来得到了广泛的关注并应用于计算机科学的各个领域。作为一种模型和工具,随着本体技术的不断完善,它又从原先的计算机领域应用到生物医学〔1〕、地理信息系统〔2〕、教育学〔3〕等其他学科领域。在具体工程应用中,用本体图G=(V,E)来表示本体的概念层次结构,其中本体图中的顶点集合V对应相关概念集合,边集合E对应概念之间的关系集合。本体应用的本质概括起来可分为两大类:本体相似度计算和本体映射。这两种应用的实质问题都是本体图顶点间的相似度计算。
随着信息处理数据量的日趋庞大,学习算法被引入到本体相似度计算和本体映射中,并逐渐代替原有的启发式算法。本体学习算法的本质是通过样本的学习,得到最优函f:V →R。从而得到定义在顶点集V 上的实值得分函数f 将本体图中每个顶点映射成对应实数,进而通过计算顶点对应实数间的差值的大小来判定两顶点对应概念间的相似度。该技术的优点在于:由于本体图被映射到了实直线,两顶点的相似度变成了它们对应实数在实数轴上的距离,从而增加了直观性。
文献〔4〕将排序学习技术应用于在不同本体之间建立本体映射,得到f;文献〔5〕将图学习方法与本体图的结构相融合,得到对应的本体算法;文献〔6〕和〔7〕给出新的本体相似度计算方法,通过图上的正则化模型的求解得到实值得分函数f,由此得到本体相似度计算和本体映射策略;文献〔8〕将k-部排序和半监督算法相融合,提出k-部排序半监督学习算法,并应用于本体。文献〔9〕和〔10〕对这些本体算法的收敛性进行了理论上的分析。
文献〔11〕将传统的回归方法应用于本体相似度和本体映射并得到相应的算法,同时给出了一些算法的理论结果。该方法与众不同之处在于它直接得到相似度函数f:V × V → R+⋃ {0},即f 将每一对顶点映射成非负实数。在此基础上,我们对文献〔11〕的计算模型加以改进,运用特殊惩罚项对目标函数的光滑性加以控制。本文的组织结构如下:首先提出基于TCP 的新本体回归模型;其次,得到基于TCP 学习模型的新本体相似度计算和本体映射算法;最后,将此算法应用于生物学“GO”本体和物理教育学本体,通过实验数据的对比分析来说明本文所提算法的有效性。
对本体图或多本体图中部分顶点对给定标记yi∈R+⋃{0},样本集可表示为S={(v1,,y1),…,(vn,,yn)}。学习的过程是通过样本集S的学习得到相似度函数f:V×V →R+⋃{0}。设亏损函数由于无法预先得知样本分布情况,因此通过如下经验模型得到f〔11〕:
本文的主要贡献体现在对算法(1)的改进,着眼于惩罚项λN(f)的讨论。关于惩罚项的选择,一般可选取融合惩罚项,其中函数h可选择为Lq泛数,例如选择L1-泛数后该惩罚项为
文献〔12〕指出:在回归经验模型中使用Lasso惩罚可得到无偏参数估计。文献〔13〕提出缩减Lasso惩罚(truncated Lasso penalty,简称TLP)如下:
其中参数τ 事先给定。本文将算法(1)的框架和缩减Lasso 惩罚项相融合,并采用L2-泛数来计算α,得到如下经验模型:
算法(2)与算法(1)相比,改进之处在于使用了L2-泛数缩减Lasso 惩罚,使得算法理论上成立无偏参数估计,同时与一般Lasso惩罚相比简化了模型,降低了计算量。
由以上分析我们得到基于TLP 经验模型的本体算法,其整体描述如下。
算法A 基于TLP经验模型的本体相似度计算算法
A1:对本体图进行预处理。将本体图中每个顶点的信息用一个向量表示。
A2:选取样本集,计算标记从而得到S。
A3:通过模型(2)得到最优本体函数f。
A4:将实值得分函数f 作用于本体图G 中的每个顶点对,得到顶点对应概念之间的相似度。
算法B 基于TLP经验模型的本体映射算法
B1:对多本体图进行预处理。设图G1,G2,…,Gm分别对应本体 O1,O2,…,Om,令G=G1+G2+…+Gm。将G中每个顶点的相关信息用一个向量来表示。
B2:选取样本集,计算标记从而得到S。
B3:通过模型(2)得到最优本体函数f。
B4:将实值得分函数f 作用于G 中来自不同本体间的顶点对,得到不同本体顶点对应概念之间的相似度。
B5:根据B4得到的相似度,选择映射策略生成本体映射。
在这一节中,我们将通过两个具体的实验来分析新算法的有效性。对于平衡参数λ,可用cross validation 技术〔14〕来得到最优的λ。为了简化计算,这里我们统一取γ=10-1。在两个实验中,第一个实验本体顶点数量庞大,第二个实验本体顶点数较少,因此τ的值分别取0.2 和0.5。在选择了顶点对后,标记yi的值采用如下计算方法得到:
其中vi和分别表示顶点vi和对应的向量。
3.1 本体相似度实验第一个实验是采用生物GO本体O1(其数据来自http://www.geneontology.org,大致结构可参考图1)来验证算法A 的效率。实验结果采用P@N〔15〕平均准确率来衡量。
另外,分别将本体回归算法〔11〕、快速排序算法〔16〕和标准本体排序算法〔4〕作用于GO 本体。将这3种算法得到的P@N准确率与本文算法A得到的准确率进行比较,部分数据见表1。
表1 实验1部分数据
由表1准确率对比可知,算法A对于GO本体的效率明显高于本体回归算法、快速排序算法和标准排序算法。
3.2 本体映射实验本文的第二个实验是采用下面两个“物理教育”本体O2和O3(这2 个本体由文献〔16〕构建)来验证算法B的效率。
图2 “物理教育”本体O2
图3 “物理教育”本体O3
同样地,分别将本体回归算法、快速排序算法和标准本体排序算法作用于“物理教育”本体,将这3种算法得到的P@N准确率与本文算法B得到的准确率进行比较,部分数据见表2。
表2 实验2部分数据
由表2 准确率对比可知,算法B 对于“物理教育”本体O2和O3间建立本体映射的效率明显高于本体回归算法、快速排序算法和标准排序算法。
本文利用对惩罚项的改进进而得到新的经验计算模型,由此得到基于TLP经验模型的本体相似度计算和本体映射算法。由于新模型采用了TLP作为惩罚项,使得算法在理论上具有参数无偏估计的特征,进而在一定程度上提高了效率。
〔1〕MORK P,BERNSTEIN P. Adapting a generic match algorithm to align ontologies of human anatomy〔C〕//20th International Conferrence on Data Engineering. 2004:787-790.
〔2〕FONSECA F,EGENHOFER M,DAVIS C,et al. Semantic Granularity in Ontology-Driven Geographic Information Systems〔J〕.AMAI Annals of Mathematics and Artificial Intelligence- Special Issue on Spatial and Temporal Granularity,2002,36(1-2):121-151.
〔3〕BOUZEGHOUB A,ELBYED A. Ontology mapping for web-based educational systems interoperability〔J〕. Interoperability in Business Information Systems,2006,1(1):73-84.
〔4〕高炜,兰美辉.基于排序学习方法的本体映射算法〔J〕.微电子学与计算机,2011,28(9):59-61.
〔5〕高炜,梁立,张云港.基于图学习的本体概念相似度计算〔J〕.西南师范大学学报:自然科学版,2011,36(4):64-67.
〔6〕高炜,梁立.基于超图正则化模型的本体概念相似度计算〔J〕.微电子学与计算机,2011,28(5):15-17.
〔7〕高炜,朱林立,梁立. 基于图正则化模型的本体映射算法〔J〕.西南大学学报:自然科学版,2012,34(3):118-121.
〔8〕高炜,梁立,徐天伟,等.半监督k-部排序算法及在本体中的应用〔J〕. 中北大学学报:自然科学版,2013,34(2):140-146.
〔9〕高炜,张云港,梁立.Cs相似度函数下正则谱聚类的收敛阶〔J〕. 兰州大学学报:自然科学版,2011,47(2):109-111.
〔10〕高炜,周定轩.与一般相似度函数相关的谱聚类的收敛性〔J〕.中国科学:数学,2012,42(10):985-994.
〔11〕GAO Y,GAO W.Ontology similarity measure and ontology mapping via learning optimization similarity function〔J〕. International Journal of Machine Learning and Computing,2012,2(2):107-112.
〔12〕FAN J,LI R. Variable selection via nonconcave penalized likelihood and it oracle properties〔J〕. JASA,2001(96):1348-1360.
〔13〕SHEN X,PAN W,ZHU Y. Likelihood-based selection and sharp parameter estimation〔J〕. JASA,2012(107):223-232.
〔14〕CAPONNETTO A,YAO Y. Cross validation based adaptation for regularization operators in learning theory〔J〕.Anal Appl,2010(8):161-183.
〔15〕CRASWELL N,HAWKING D. Overview of the TREC 2003 web track〔C〕//Proceedings of the Twelfth Text Retrieval Conference.2003:78-92.
〔16〕HUANG X,XU T,GAO W,et al. Ontology Similarity Measure and Ontology Mapping Via Fast Ranking Method〔J〕.International Journal of Applied Physics and Mathematics,2011,1(1):54-59.