蘭美輝,高煒

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

1 引 言

本體是一種廣泛應(yīng)用的數(shù)據(jù)結(jié)構(gòu)化儲(chǔ)存和管理模型，具有強(qiáng)大的語義查詢和擴(kuò)展檢索功能，是用一個(gè)圖G=(V,E)來表示概念集合以及集合中成員的關(guān)系.本體算法的核心問題是尋找概念之間的相互聯(lián)系和內(nèi)在關(guān)聯(lián),即在本體上的相似度計(jì)算是各種本體工程應(yīng)用算法的本質(zhì)所在.一類本體學(xué)習(xí)方法是通過本體樣本的學(xué)習(xí)得到本體函數(shù)f：V→，該函數(shù)給本體圖上每個(gè)頂點(diǎn)(對(duì)應(yīng)一個(gè)概念)分配一個(gè)分值，從而將高維幾何空間上相似度計(jì)算轉(zhuǎn)化為一維數(shù)軸上的直接距離計(jì)算.近年來，出于本體的優(yōu)越性，本體的應(yīng)用領(lǐng)域涵蓋了整個(gè)自然科學(xué)與工程學(xué)科中，被越來越多的專家所關(guān)注并作為重點(diǎn)研究課題.目前，本體已成為信息檢索、數(shù)據(jù)庫、知識(shí)工程和管理學(xué)的核心內(nèi)容[1-7].

在化學(xué)、生物、制藥和材料工程相關(guān)的本體中，由于涉及基因或者復(fù)雜的分子結(jié)構(gòu)，使得這些本體所要表達(dá)的信息量非常的龐大.在此類應(yīng)用背景下，對(duì)本體算法的設(shè)計(jì)提出了更高的要求.為了降低計(jì)算復(fù)雜度，快速而高效地得到相似度計(jì)算結(jié)果，稀疏算法被引入到本體相似度計(jì)算和本體映射中.針對(duì)特定的應(yīng)用背景和本體圖特殊的結(jié)構(gòu)，設(shè)計(jì)適合本體應(yīng)用的本體稀疏向量學(xué)習(xí)算法，并由此得到本體概念之間的相似度，是未來本體學(xué)習(xí)算法研究的趨勢(shì).

本文利用核函數(shù)計(jì)算，給出一類本體稀疏向量衰減迭代方法，并將所得本體算法應(yīng)用于兩個(gè)特定的工程領(lǐng)域來分別驗(yàn)證其對(duì)本體概念相似度計(jì)算和不同本體之間映射構(gòu)建的有效性.

2 新算法描述

為了構(gòu)建數(shù)學(xué)模型的需要，將本體圖中每個(gè)頂點(diǎn)對(duì)應(yīng)概念的全部信息用一個(gè)p維向量進(jìn)行封裝.設(shè)v={v1,…,vp} 是頂點(diǎn)v對(duì)應(yīng)的向量.在不引起混淆的前提下，標(biāo)記v可同時(shí)表示本體圖中的頂點(diǎn)、該頂點(diǎn)對(duì)應(yīng)的概念或它所對(duì)應(yīng)的向量.

引入本體稀疏向量后，本體函數(shù)可表示為

(1)

其中β=(β1,…,βp) 表示稀疏向量，其特點(diǎn)是大部分分量的值為0或者非常小，小到可以忽略的程度； 附加項(xiàng)β0是一個(gè)偏移量，可用來表示噪聲或者誤差糾正項(xiàng).本體稀疏向量學(xué)習(xí)模型可歸納為

(2)

其中l(wèi)(β)為虧損項(xiàng)，Q(β)為平衡項(xiàng)，用來調(diào)節(jié)本體稀疏向量β的稀疏程度.

(3)

其中β=(β1,…,βn) 表示新本體稀疏向量.可見，同樣是通過本體稀疏向量將頂點(diǎn)映射成實(shí)數(shù)，表達(dá)式(1)和表達(dá)式(3)有著本質(zhì)的不同：在忽略偏移量β0的前提下，公式(1)是將頂點(diǎn)對(duì)應(yīng)向量和稀疏向量作內(nèi)積得到函數(shù)值；而公式(3)是將頂點(diǎn)對(duì)應(yīng)向量和樣本點(diǎn)作核運(yùn)算后與對(duì)應(yīng)稀疏向量的分量相乘后再求和.前者稀疏的每個(gè)頂點(diǎn)對(duì)應(yīng)向量的分量，其實(shí)質(zhì)是強(qiáng)化本體信息中最重要的特征；后者是稀疏樣本集中的樣本信息，其實(shí)質(zhì)是強(qiáng)化樣本信息的重要性，所得本體函數(shù)fβ對(duì)樣本的依賴性較強(qiáng).因此，后者較前者更加符合機(jī)器學(xué)習(xí)的本質(zhì)，能充分挖掘所給樣本集合的潛力.

(4)

(5)

(6)

(7)

由于Lp關(guān)于β+和β-都是可導(dǎo)的，因此(6)的優(yōu)化條件為

(8)

(9)

從而有

(10)

(11)

從如上條件(8)、(9)、(10)和(11)可知，在核函數(shù)參數(shù)γ固定的情況下，其最優(yōu)解有如下性質(zhì)：

(ⅰ)若λ>0，則

且

(12)

i?A?|gi|<λ

(13)

(14)

(15)

(16)

(17)

(18)

(19)

可知(18)和(19)構(gòu)成了m+1個(gè)線性方程.定義如下變量：

從而上面的m+1個(gè)線性方程可以寫成如下矩陣的形式：

ΩΔ=Ψ

(20)

若Ω是滿秩矩陣，則Ω-1存在且

(21)

隨著γ的變化，算法需要對(duì)稠密點(diǎn)集合A的變化進(jìn)行如下監(jiān)控：

?其中一個(gè)βA(i)(i=1,…,m)達(dá)到0；

?有一個(gè)標(biāo)記i?A加入A，即|gi|=λ發(fā)生.

通過監(jiān)控，計(jì)算在事件發(fā)生的情況下使得γ<γl成立的最大γ.這個(gè)γ值是一個(gè)斷點(diǎn)并記為γl+1，然后更新稠密點(diǎn)集合A并繼續(xù)算法直到整個(gè)算法結(jié)束.下面給出整個(gè)算法的過程.

算法A.本體稀疏向量衰減迭代計(jì)算算法

A3:whileγ>γmin

A4:設(shè)r=θ;

A5:whiler<1-ε

A6:γ=γtr;

A7:通過公式(21)計(jì)算(β(γ),β0(γ));

A9:end while

A10:更新集合A;

A11:end while

A12:輸出滿足γmin<γ<γ0的解序列(β(γ),β0(γ)).

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

在下面兩個(gè)實(shí)驗(yàn)中，將分別驗(yàn)證新本體稀疏向量學(xué)習(xí)算法對(duì)特定應(yīng)用領(lǐng)域本體相似度計(jì)算和構(gòu)建本體映射的可行性.在得到最優(yōu)稀疏向量后，再通過該向量把本體頂點(diǎn)映射成實(shí)數(shù)值，最后本體概念之間的相似度關(guān)系通過它們對(duì)應(yīng)實(shí)數(shù)之間的一維距離來判斷：距離越大，則相似度越??；距離越小，則相似度越大.

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

第一個(gè)實(shí)驗(yàn)驗(yàn)證本文本體稀疏向量衰減迭代算法是否可應(yīng)用于植物學(xué)領(lǐng)域，采用的數(shù)據(jù)來自http://www.plantontology.org網(wǎng)站構(gòu)建的植物學(xué)PO本體O1(其基本結(jié)構(gòu)可參考圖1).該本體其實(shí)是一個(gè)植物學(xué)數(shù)據(jù)庫，或者可理解為一本植物學(xué)字典.用戶可利用網(wǎng)站的搜索功能進(jìn)行概念查找，并由此知道對(duì)應(yīng)的含義和與其他概念的關(guān)聯(lián).將以下三類經(jīng)典本體學(xué)習(xí)算法也同時(shí)作用于植物學(xué)PO本體：基于一般排序?qū)W習(xí)方法的本體算法[8]、基于快速排序?qū)W習(xí)的本體算法[9]和基于NDCG測(cè)度計(jì)算的本體算法[10].使用傳統(tǒng)的P@N[11]平均準(zhǔn)確率來衡量四種算法的有效性，并取N為3、5和10，將四類準(zhǔn)確率進(jìn)行對(duì)比，結(jié)果如表1所示.

圖1 PO本體O1Fig.1 PO ontology O1

表1 實(shí)驗(yàn)1部分?jǐn)?shù)據(jù)Table 1 Part of the data in experiment 1

通過表1對(duì)比分析可知，當(dāng)N的取值為3、5和10時(shí)，本文本體稀疏向量衰減迭代學(xué)習(xí)算法得到的P@N準(zhǔn)確率要明顯高于其他三類算法，即新本體算法對(duì)于植物學(xué)PO本體上進(jìn)行相似度計(jì)算是可行的，并且是高效的.

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

第二個(gè)實(shí)驗(yàn)對(duì)象的是仿生學(xué)領(lǐng)域中構(gòu)造的兩個(gè)“仿生機(jī)器人”本體O2和O3，其目的是在它們之間構(gòu)造本體映射，從而來了解它們各自概念之間的相互關(guān)聯(lián).構(gòu)造這兩個(gè)本體的依據(jù)是機(jī)器人的各個(gè)部件的連接和它們之間的相互關(guān)聯(lián).為了進(jìn)行實(shí)驗(yàn)數(shù)據(jù)對(duì)比，將基于k-部排序的本體學(xué)習(xí)算法[12]、基于NDCG測(cè)度計(jì)算的本體學(xué)習(xí)算法[10]和基于超圖調(diào)和分析的本體學(xué)習(xí)算法[13]也應(yīng)用于“仿生機(jī)器人”本體O2和O3，并根據(jù)得到的相似度構(gòu)建本體映射策略.實(shí)驗(yàn)結(jié)果同樣采用傳統(tǒng)的P@N準(zhǔn)確率來進(jìn)行對(duì)比，當(dāng)N的取值為1、3和5時(shí)數(shù)據(jù)對(duì)比可參考表2.

圖2 “仿生機(jī)器人”本體O2 圖3 “仿生機(jī)器人”本體O3Fig.2 Biomimetic robot ontology O2 Fig.3 Biomimetic robot ontology O3

表2 實(shí)驗(yàn)2部分?jǐn)?shù)據(jù)Table 2 Part of the data in experiment 2

由表2數(shù)據(jù)可知，本文本體稀疏向量衰減迭代算法對(duì)于在“仿生機(jī)器人”本體O2和O3間建立基于相似度的本體映射而言，其效率要明顯高于其他三類傳統(tǒng)本體學(xué)習(xí)算法.當(dāng)N的取值為1、3和5時(shí)，P@N準(zhǔn)確率數(shù)據(jù)對(duì)比說明了本文提出的本體學(xué)習(xí)新算法的高效性和有效性.

4 結(jié)束語

本體已廣泛應(yīng)用于教育學(xué)、心理學(xué)、測(cè)量學(xué)、地理信息系統(tǒng)、化學(xué)、制藥學(xué)和材料科學(xué)等諸多領(lǐng)域，且作為核心內(nèi)容的本體概念相似度計(jì)算受到各個(gè)學(xué)科的廣泛關(guān)注.本文從學(xué)習(xí)算法的角度給出一類學(xué)習(xí)本體稀疏向量的衰減迭代策略，并由此間接計(jì)算本體概念之間的相似度.通過兩個(gè)具體工程應(yīng)用實(shí)例，說明新算法對(duì)于特定領(lǐng)域的本體工程應(yīng)用是有效的，有廣泛的應(yīng)用前景.