高煒，蘭美輝

（1.云南師范大學(xué)信息學(xué)院，云南昆明650500；2.曲靖師范學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院，云南曲靖655011）

基于排序支持向量機(jī)的本體學(xué)習(xí)算法

高煒1，蘭美輝2

（1.云南師范大學(xué)信息學(xué)院，云南昆明650500；2.曲靖師范學(xué)院計(jì)算機(jī)科學(xué)與工程學(xué)院，云南曲靖655011）

作為概念結(jié)構(gòu)化表示、存儲(chǔ)和管理的模型，本體越來(lái)越受到計(jì)算機(jī)各領(lǐng)域?qū)W者的重視，并廣泛應(yīng)用于生物學(xué)、醫(yī)學(xué)、制藥學(xué)、地理信息系統(tǒng)等其他學(xué)科領(lǐng)域。該文提出了一種基于排序支持向量機(jī)的本體學(xué)習(xí)算法，其特點(diǎn)是樣本集由頂點(diǎn)對(duì)構(gòu)成，并采用帶有敏感參數(shù)的虧損函數(shù)。最后，將新本體算法應(yīng)用到生物基因?qū)W本體和仿生機(jī)器人本體，分別驗(yàn)證了算法對(duì)本體相似度計(jì)算和本體映射有較高的效率。

本體；相似度計(jì)算；本體映射；排序支持向量機(jī)

作為一種概念語(yǔ)義表示模型，本體自20世紀(jì)90年代引入計(jì)算機(jī)領(lǐng)域以來(lái)，一直受到極大的關(guān)注，并得到長(zhǎng)足的發(fā)展。該模型已經(jīng)應(yīng)用于信息檢索、查詢擴(kuò)展、圖像檢索和數(shù)據(jù)集成等諸多領(lǐng)域。在近30年的發(fā)展中，本體作為一種強(qiáng)大的工具模型，被應(yīng)用在多個(gè)學(xué)科，比如醫(yī)學(xué)、生物學(xué)、制藥學(xué)、地理科學(xué)、心理學(xué)和教育學(xué)等。一般用本體圖G=（V，E）作為模型來(lái)表示本體O，其圖中頂點(diǎn)表示概念，邊表示概念之間的從屬關(guān)系。本體在各學(xué)科中的應(yīng)用，其核心問(wèn)題是本體概念之間的相似度計(jì)算，進(jìn)而在本體圖模型中使用學(xué)習(xí)方法的過(guò)程，即通過(guò)樣本得到最優(yōu)本體函數(shù)f：V→R，由此將本體圖中每個(gè)頂點(diǎn)映射成實(shí)數(shù)。最后，本體概念之間的相似度則通過(guò)概念對(duì)應(yīng)頂點(diǎn)在本體函數(shù)下的像的幾何距離來(lái)衡量。最簡(jiǎn)單的方法是通過(guò)對(duì)應(yīng)實(shí)數(shù)在實(shí)數(shù)軸上的距離來(lái)衡量，距離越小，相似度越高。

文獻(xiàn)[1]將一般排序?qū)W習(xí)方法引入到本體映射；文獻(xiàn)[2]將流形上拉普拉斯算子反映到圖上，從而把問(wèn)題歸結(jié)于求本體圖拉普拉斯矩陣次小特征值對(duì)應(yīng)的特征向量，該向量第i個(gè)分量即為第i個(gè)頂點(diǎn)對(duì)應(yīng)的實(shí)數(shù)；文獻(xiàn)[3－4]利用有向圖和無(wú)向圖上正則化模型得到本體相似度計(jì)算和本體映射學(xué)習(xí)算法；文獻(xiàn)[5]充分利用本體圖樹形結(jié)構(gòu)特征，并充分考慮到未標(biāo)記數(shù)據(jù)特征，由此提出k-部排序半監(jiān)督學(xué)習(xí)算法；此外，文獻(xiàn)[6]利用正則化瑞利系數(shù)，提出新的半監(jiān)督k-部排序?qū)W習(xí)算法；文獻(xiàn)[7]給出一類新的迭代計(jì)算方法，并將此方法應(yīng)用于本體半監(jiān)督學(xué)習(xí)。

筆者利用排序支持向量機(jī)，提出一種新的本體學(xué)習(xí)算法，并將新算法應(yīng)用于本體工程中的本體相似度計(jì)算和本體映射算法。實(shí)驗(yàn)部分將該算法應(yīng)用于生物基因領(lǐng)域驗(yàn)證其對(duì)本體相似度計(jì)算的有效性，并應(yīng)用于仿生機(jī)器人領(lǐng)域來(lái)驗(yàn)證算法對(duì)構(gòu)建本體映射的效率。

1 新算法描述

為了將本體概念的相關(guān)信息融入到學(xué)習(xí)方法中，首先需要對(duì)本體概念信息進(jìn)行預(yù)處理，其中關(guān)鍵的一步是將每個(gè)概念對(duì)應(yīng)頂點(diǎn)的信息封裝到一個(gè)固定維度的向量中。不失一般性，設(shè)每個(gè)頂點(diǎn)的信息都用p維向量來(lái)表示。并且在不引起混淆的情況下，用v={v1，…，vp}同時(shí)表示頂點(diǎn)v以及頂點(diǎn)v對(duì)應(yīng)的向量?；谂判蚍椒ǖ谋倔w學(xué)習(xí)算法，其目標(biāo)可概括為通過(guò)本體樣本集S的學(xué)習(xí)得到本體函數(shù)f：V→R，該函數(shù)是一個(gè)得分函數(shù)，將所有本體頂點(diǎn)均映射到實(shí)數(shù)，通過(guò)實(shí)數(shù)之間的幾何距離來(lái)衡量?jī)身旤c(diǎn)對(duì)應(yīng)本體概念之間的相似程度。

排序與之前傳統(tǒng)的分類和回歸算法有著本質(zhì)的區(qū)別，此類學(xué)習(xí)算法關(guān)注的是由排序函數(shù)得到的實(shí)數(shù)在

實(shí)數(shù)軸上的相對(duì)位置。一般來(lái)說(shuō)，本體學(xué)習(xí)的樣本是一個(gè)頂點(diǎn)集合S={（v1，y1），…，（vn，yn）}，對(duì)應(yīng)的經(jīng)驗(yàn)?zāi)Ｐ涂梢员硎緸?/p>

l：RV×V×V→R為本體虧損函數(shù)，用來(lái)衡量排序出錯(cuò)時(shí)的懲罰量。最優(yōu)本體函數(shù)f通過(guò)最小化R?（f，S）得到。

下面給出基于排序支持向量機(jī)（RankSVM）的本體學(xué)習(xí)算法。與經(jīng)典排序支持向量模型相比，文中針對(duì)本體的具體應(yīng)用，對(duì)如下兩點(diǎn)作了改進(jìn)：（1）傳統(tǒng)排序支持向量機(jī)模型采用部分實(shí)例集作為樣本，而在本體具體應(yīng)用中，可能只需對(duì)部分本體頂點(diǎn)對(duì)進(jìn)行相似度計(jì)算，因而文中采用一個(gè)本體頂點(diǎn)對(duì)的集合E′作為樣本，并且假設(shè)頂點(diǎn)對(duì)中前一個(gè)頂點(diǎn)在排序函數(shù)下的得分比后一個(gè)頂點(diǎn)要高；（2）傳統(tǒng)排序支持向量機(jī)模型采用平方虧損、指數(shù)虧損、對(duì)數(shù)虧損、鉸鏈虧損等虧損函數(shù)，文中考慮排序算法的實(shí)際特征，允許f（v）和標(biāo)記y之間存在一定范圍的誤差，進(jìn)而采用帶敏感參數(shù)的虧損函數(shù)。

具體地說(shuō)，考慮上述（1），采用如下經(jīng)驗(yàn)?zāi)Ｐ?/p>

其中E′是頂點(diǎn)對(duì)（v，v′）構(gòu)成的集合，并且它們對(duì)應(yīng)的標(biāo)記滿足y＞y′；I是真值函數(shù)，當(dāng)下標(biāo)所示論斷為真時(shí)值為1，否則函數(shù)值為0。由于真值函數(shù)不可導(dǎo)，因此，直接計(jì)算公式（1）的難度很大。用連續(xù)凸虧損函數(shù)取代真值函數(shù)，即

其中取K：V×V→R為了核函數(shù)（比如高斯核、熱核、多項(xiàng)式核等），F(xiàn)即為與核函數(shù)K相關(guān)聯(lián)的再生核希爾伯特空間，C為平衡參數(shù)，項(xiàng)的作用是控制本體函數(shù)f的光滑性，從而使算法具有較強(qiáng)的泛化性。引入個(gè)變量αij，則優(yōu)化模型又可以寫成

s.t.0≤αij≤對(duì)任意（vi，vj）∈E′成立。

由統(tǒng)計(jì)學(xué)習(xí)理論中的表示理論可知，最優(yōu)解可表示成

最后，將虧損函數(shù)替換為帶敏感參數(shù)的形式，得到

其中ε>0表示誤差量，一般取值較小。優(yōu)化模型（6）可用經(jīng)典梯度下降策略得到最優(yōu)解。

特別地，當(dāng)敏感參數(shù)為0或者不帶敏感參數(shù)的情況下，除了經(jīng)典梯度下降策略，文中還給出了如下迭代計(jì)算方法。

算法A：不帶敏感參數(shù)條件下基于排序支持向量機(jī)的迭代計(jì)算方法

輸入：訓(xùn)練樣本E′以及樣本頂點(diǎn)對(duì)中每個(gè)頂點(diǎn)對(duì)應(yīng)的標(biāo)記y，核函數(shù)K，參數(shù)C，T，η

循環(huán)：For t＝1 to T do

在上述算法中，Q（α）表示公式（4）的二次目標(biāo)函數(shù)。

2 實(shí)驗(yàn)

下面通過(guò)兩個(gè)具體的仿真實(shí)驗(yàn)來(lái)分別驗(yàn)證算法對(duì)基因領(lǐng)域相似度計(jì)算和仿生機(jī)器人領(lǐng)域構(gòu)建本體映射的效率。特別需要提醒的是，兩個(gè)實(shí)驗(yàn)驗(yàn)證的算法均是模型（6），而上節(jié)給出的迭代計(jì)算方法由于不涉及敏感參數(shù)，故不作為文中實(shí)驗(yàn)的對(duì)象。

2.1 本體相似度計(jì)算實(shí)驗(yàn)

由http://www.geneontology.Org網(wǎng)站構(gòu)建的生物學(xué)領(lǐng)域GO本體（該本體為基因相關(guān)本體，記為O1），其結(jié)構(gòu)如圖1所示，其目的是從語(yǔ)義的角度來(lái)分析原子作用、分子結(jié)構(gòu)以及生物過(guò)程之間的相互關(guān)聯(lián)。對(duì)生物和基因領(lǐng)域工作者來(lái)說(shuō)，它是個(gè)有效的數(shù)據(jù)庫(kù)，用于相關(guān)信息的檢索和查詢，并可以通過(guò)檢索來(lái)了解其他關(guān)聯(lián)信息。該實(shí)驗(yàn)是驗(yàn)證文中算法對(duì)GO本體進(jìn)行相似度計(jì)算的效率。實(shí)驗(yàn)結(jié)果的好壞用P@N[8]平均準(zhǔn)確率來(lái)衡量。另外，還將本體回歸算法[9]、快速排序算法[10]和標(biāo)準(zhǔn)本體排序算法[1]也應(yīng)用于該生物基因GO本體。表1顯示了當(dāng)N取3、5、10時(shí)，四種方法得到數(shù)據(jù)的對(duì)比。

圖1 GO本體O1

表1 GO本體上四種方法數(shù)據(jù)對(duì)比

由表1中P@3、P@5、P@10準(zhǔn)確率對(duì)比可知，文中算法對(duì)于生物基因GO本體而言，其效率高于其他三類算法。

2.2 本體映射實(shí)驗(yàn)

為驗(yàn)證文中算法對(duì)建立本體映射的有效性，下面采用仿生機(jī)器人本體O2（如圖2）和O3（如圖3）作為實(shí)驗(yàn)對(duì)象。其目標(biāo)是在O2和O3之間建立基于相似度的本體映射。將標(biāo)準(zhǔn)本體排序算法[1]、快速排序算法[10]和基于NDCG測(cè)度的本體學(xué)習(xí)算法[11]也分別應(yīng)用于仿生機(jī)器人本體，并同樣采用P@N準(zhǔn)確率作為標(biāo)準(zhǔn)對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比。取N的值分別為1、3、5，部分?jǐn)?shù)據(jù)見(jiàn)表2。

圖2 仿生機(jī)器人本體O2

圖3 仿生機(jī)器人本體O3

表2 仿生學(xué)本體四種方法數(shù)據(jù)對(duì)比

根據(jù)表2中準(zhǔn)確率對(duì)比可知，文中基于排序支持向量機(jī)的本體算法對(duì)于在仿生機(jī)器人本體O2和O3間建立本體映射的效率明顯要高于其他三種學(xué)習(xí)算法。

3 結(jié)語(yǔ)

筆者提出一種基于排序支持向量機(jī)的本體算法，其特點(diǎn)是學(xué)習(xí)樣本由本體頂點(diǎn)對(duì)構(gòu)成，并在虧損函數(shù)的選擇上選取帶敏感參數(shù)的虧損函數(shù)。兩個(gè)實(shí)驗(yàn)結(jié)果表明基于排序支持向量機(jī)的本體算法對(duì)本體相似度計(jì)算和本體映射構(gòu)建都有較高的效率。從而說(shuō)明算法在本體應(yīng)用領(lǐng)域有廣泛的前景。

[1]高煒，蘭美輝.基于排序?qū)W習(xí)方法的本體映射算法[J].微電子學(xué)與計(jì)算機(jī)，2011，28（9）：59-61.

[2]高煒，梁立，張?jiān)聘?基于圖學(xué)習(xí)的本體概念相似度計(jì)算[J].西南師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2011，36（4）：64-67.

[3]高煒，梁立.基于超圖正則化模型的本體概念相似度計(jì)算[J].微電子學(xué)與計(jì)算機(jī)，2011，28（5）：15-17.

[4]高煒，朱林立，梁立.基于圖正則化模型的本體映射算法[J].西南大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，34（3）：118-121.

[5]高煒，梁立，徐天偉，等.半監(jiān)督k-部排序算法及在本體中的應(yīng)用[J].中北大學(xué)學(xué)報(bào)（自然科學(xué)版），2013，34（2）：140-146.

[6]高煒，梁立，徐天偉.基于正則化瑞利系數(shù)的半監(jiān)督k-部排序?qū)W習(xí)算法及應(yīng)用[J].西南師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2014，39（4）：124-128.

[7]彭波，徐天偉，李臻，等.迭代拉普拉斯半監(jiān)督學(xué)習(xí)本體算法[J].計(jì)算機(jī)工程與科學(xué)，2014，36（11）：2164-2168.

[8]CRASWELL N,HAWKING D.Overview of the TREC 2003 web track[C]//Proceedings of the Twelfth Text Retrieval Conference.Gaithersburg, Maryland，NIST Special Publication，2003：78-92.

[9]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.

[10]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.

[11]GAO W，LIANG L.Ontology similarity measure by optimizing NDCG measure and application in physics education[J].Future Communication，Computing，Control and Management，2011，142：415-421.

Ontology learning algorithm based on ranking SVM

GAO Wei1，LAN Meihui2
（1.School ofInformation，Yunnan Normal University，Kunming 650500，China；2.Department of Computer Science and Engineering，Qujing Normal University，Qujing 655011，China）

As a conceptual structure representation,storage and management model,ontology has raised increasing attention among scholars in various fields of computer,and been widely used in other disciplines such as biology,medicine,pharmaceutics,and geographic information system.In this paper,we have presented a class of ontology learning algorithm based on ranking SVM in which the sample set is consisted of vertex pairs and the loss function is applied with sensitive parameters.The new algorithm is applied to biological gene ontology and humanoid robot ontology.The results have verified that the algorithm has a higher efficiency in calculating the similarity of ontology and constructing ontology mapping.

ontology；similarity measuring；ontology mapping；ranking SVM

TP393.092

A

1672－0687（2016）04－0052－05

責(zé)任編輯：艾淑艷

2015－09－18

國(guó)家自然科學(xué)基金資助項(xiàng)目（11401519）

高煒（1981-），男，浙江紹興人，副教授，博士，研究方向：機(jī)器學(xué)習(xí)，圖論。