蘭美輝， 徐堅(jiān)， 高煒

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

1 引 言

作為一種表示、存儲(chǔ)和管理信息的工具，本體被廣泛應(yīng)用于生物制藥[1]、教育科學(xué)[2]等各個(gè)領(lǐng)域.本體映射的本質(zhì)是尋找不同本體間相似程度大的概念，從而在不同的本體間建立聯(lián)系[3].近年來,排序?qū)W習(xí)算法被廣泛應(yīng)用于本體映射，其本質(zhì)是得到排序函數(shù)，通過該函數(shù)將實(shí)例映射成實(shí)數(shù)，再通過比較實(shí)數(shù)間的差值來判定兩概念的相似程度.相關(guān)內(nèi)容可參考文獻(xiàn)[4-9].

設(shè)圖G1、G2、…、Gk分別對(duì)應(yīng)本體O1、O2、…、Ok，令G=G1+G2+…+Gk.本文利用primal RankRLS算法得到本體映射算法.文章的結(jié)構(gòu)組織如下：首先簡單介紹RankRLS算法[10]；其次，在第三節(jié)中針對(duì)多本體圖的結(jié)構(gòu)特征將primal RankRLS算法融入本體概念相似度計(jì)算，進(jìn)而得到本體映射；最后，通過一個(gè)具體實(shí)驗(yàn)驗(yàn)證新算法的有效性.

2 RankRLS簡介

設(shè)X為輸入空間.排序函數(shù)f：X→可以看成一個(gè)得分函數(shù)，它將X中每個(gè)數(shù)據(jù)映射成一個(gè)實(shí)數(shù)，數(shù)據(jù)之間的排名通過比較實(shí)數(shù)間的大小來確定，實(shí)數(shù)值越大，排名越高.排序?qū)W習(xí)算法的目標(biāo)即是找到最優(yōu)的排序函數(shù).

設(shè)RX為從輸入空間X到實(shí)數(shù)R的所有函數(shù)的集合.H?RX為假設(shè)空間(即排序函數(shù)f∈H).對(duì)任意映射Φ：X→F，內(nèi)積k(x,x')≤Φ(x)、Φ(x')稱為核函數(shù)，其中x、x'∈X.n×n對(duì)稱核矩陣K如下：

由輸入空間X和核函數(shù)k:X×X→決定的再生核希爾伯特空間(RKHS)記為Hk,X.RankRLS算法A可形式化表示為

(1)

其中

(2)

λ表示正則化常數(shù),c(f(S),G)為代價(jià)函數(shù).根據(jù)表示理論，使(1)達(dá)到最小的f∈Hk,X可表示為

(3)

這里ai∈R.令

(4)

其中實(shí)值參數(shù)wi、zi>0.則

(5)

設(shè)A∈Rn是最小化(5)的解，則

A=(MMTK+λI)-1MN

(6)

3 新算法描述

對(duì)于單本體圖的概念相似度計(jì)算，將RankRLS算法融入本體映射算法，由于zi一般取與邊標(biāo)記yi相關(guān)的數(shù)(例如：直接取zi=yi)，因此只需根據(jù)本體自身的結(jié)構(gòu)設(shè)計(jì)邊權(quán)值函數(shù)w即可.但在多本體映射中，還需處理另外一個(gè)問題，即在多本體圖中，頂點(diǎn)的數(shù)量會(huì)非常龐大，此時(shí)選取樣本點(diǎn)的數(shù)量也會(huì)非常大，遠(yuǎn)遠(yuǎn)超過數(shù)據(jù)本身的維數(shù)，導(dǎo)致算法的計(jì)算量會(huì)非常大.因此，需要將學(xué)習(xí)理論中降維的思想運(yùn)用于排序?qū)W習(xí)算法.具體的做法是運(yùn)用改進(jìn)的RankRLS算法-primal RankRLS算法融入本體相似度計(jì)算.

3.1 運(yùn)用primal RankRLS算法

對(duì)于樣本S=(x1,…,xn)，取特征空間為Rl.令矩陣

H=(Φ(x1),…,Φ(xn)).

則最優(yōu)化(1)得到的函數(shù)(3)的具體形式可表示為

f(x)= Φ(x)THA=Φ(x)TW，

這里，W=HA表示RankRLS算法在特征空間的解所對(duì)應(yīng)的超平面的賦范向量，其維數(shù)等于特征空間的維數(shù)l，而與n無關(guān)；A是式(3)中由ai∈R決定的向量.此類方法稱為primal RankRLS, 它能大大降低計(jì)算復(fù)雜度，使其由特征空間的維數(shù)l決定，而與n無關(guān).

式(1)可寫為

這里，J(W,G)=(N-MTHTW)T(N-MTHTW)+λWTW.

對(duì)J(W,G)關(guān)于W求導(dǎo)可得：

令導(dǎo)數(shù)的值為0，則可得關(guān)于W的解為：

W=(HMMTHT+λI)-1HMN.

(7)

該解對(duì)應(yīng)原來RankRLS算法的解(6).

通過解最優(yōu)化模型(6)得到排序函數(shù)f.對(duì)任意v∈V(Gi)，其中1≤i≤k.選擇閾值M，返回集合{u∈V(G-Gi)，|f(u)-f(v)|≤M}作為頂點(diǎn)v的映射.

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

實(shí)驗(yàn)構(gòu)建了兩個(gè)“Computer”本體O1、O2,其結(jié)構(gòu)如圖1、圖2所示.采用P@N[11]準(zhǔn)確率來評(píng)價(jià)實(shí)驗(yàn)，對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行分析，P@1平均準(zhǔn)確率達(dá)62.50%，P@3平均準(zhǔn)確率達(dá)70.83%，P@5平均準(zhǔn)確率達(dá)79.17%，所以該算法是有效的.

圖1 “Computer”本體O1結(jié)構(gòu)圖

圖2 “Computer”本體O2結(jié)構(gòu)圖

5 結(jié)束語

本文運(yùn)用primal RankRLS學(xué)習(xí)算法對(duì)所有多本體圖的所有頂點(diǎn)給出了一個(gè)序列，并根據(jù)兩概念對(duì)應(yīng)頂點(diǎn)對(duì)應(yīng)實(shí)數(shù)的差值來判斷它們的相似程度，由此得到本體映射.算法適用于多本體圖頂點(diǎn)數(shù)量龐大的情況，支持大規(guī)模運(yùn)算，具有廣闊的應(yīng)用前景.

參 考 文 獻(xiàn):

[1] HE X,WANG Y,GAO W.Ontology similarity measure algorithm based on KPCA and application in biology science[J].Journal of Chemical and Pharmaceutical Research，2013,5(12):196-200.

[2] BOUZEGHOUB A,ELBYED A.Ontology mapping for web-based educational systems interoperability[J].Interoperability in Business Information Systems,2006,1(1):73-84.

[3] SU X,GULLA J A.Semantic enrichment for ontology mapping[C].Natural Language Processing and Information Systems:9th International Conference on Applications of Natural Languages to Information Systems,Salford,UK,2004,Proceedings.Springer,2006,3136:217-228.

[4] JOACHIMS T.Optimizing search engines using clickthrough data[C].Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining,Washington,DC,USA,2002,133-142.

[5] CHUA T S,NEO S Y,GOH H K.Trecvid 2005 by nus pris[R].NIST TRECVID,2005.

[6] CORTES C,MOHRI M,RASTOGI A.Magnitude-preserving ranking algorithms[C].Proceedings of the 24th International Conference on Machine Learning,Corvallis,USA,2007,169-176.

[7] COSSOCK D,ZHANG T.Subset Ranking Using Regression[C].Proceedings of the 19th annual conference on Learning Theory,Pittsburgh,USA,2006,Springer-Verlag,2006,605-619.

[8] YAN R,HAUPTMANN A G.Efficient margin-based rank learning algorithms for information retrieval[C].Image and Video Retrieval:5th International Conference,Tempe,USA,2006,Proceedings Springer,2006,4071,113-122.

[9] RUDIN C.Ranking with a P-Norm Push[C].Proceedings of the 19th annual conference on Learning Theory,Pittsburgh,USA,2006,Springer-Verlag,2006,589-604.

[10]PAHIKKALA T,TSIVTSIVADZE E,AIROLA A, et al.An efficient algorithm for learning to rank from preference graphs[J].Mach Learn,2009,75(1):129-165.

[11]CRASWELL N,HAWKING D.Overview of the TREC 2003 web track[C].Proceedings of the 12th Text Retrieval Conference,Gaithersburg,USA,2003,NIST Special Publication,2003:78-92.