肖 錚

(四川工商職業(yè)技術(shù)學(xué)院 信息工程系，四川 成都 611830)

1 動(dòng) 機(jī)

以關(guān)聯(lián)數(shù)據(jù)發(fā)布規(guī)律建立知識(shí)庫(kù)的網(wǎng)絡(luò)被稱(chēng)為數(shù)據(jù)萬(wàn)維網(wǎng)(web of data，簡(jiǎn)稱(chēng)為數(shù)據(jù)網(wǎng))。數(shù)據(jù)網(wǎng)以RDF(resource description framework，即資源描述框架)為基礎(chǔ)，連接并整合互聯(lián)網(wǎng)絡(luò)數(shù)據(jù)。近年來(lái)，數(shù)據(jù)網(wǎng)持續(xù)增長(zhǎng)，據(jù)CKAN數(shù)據(jù)統(tǒng)計(jì)，已有超過(guò)100個(gè)公共SPARQL端點(diǎn)(endpoint)，超過(guò)31億的三元組(triples)。一方面，可獲取的結(jié)構(gòu)化數(shù)據(jù)總量顯著提升，另一方面，增加了數(shù)據(jù)檢索的難度。形式化查詢(xún)語(yǔ)言(如SPARQL)是檢索這類(lèi)結(jié)構(gòu)化數(shù)據(jù)的有效語(yǔ)言，但用戶至少需掌握如下兩方面的知識(shí)：①形式化描述邏輯及對(duì)應(yīng)語(yǔ)法規(guī)則；②被檢索數(shù)據(jù)的基本結(jié)構(gòu)(這里特指潛在的本體模式)。本節(jié)首先介紹數(shù)據(jù)網(wǎng)的基本概念，之后分析數(shù)據(jù)網(wǎng)檢索的相關(guān)內(nèi)容。

在數(shù)據(jù)網(wǎng)中，知識(shí)庫(kù)(D)的形式描述為：D:〈C,I,P,τ〉，即知識(shí)庫(kù)D是一個(gè)有向圖GD，其中C是類(lèi)集(class set)，I是實(shí)例集(instance set)，P是屬性集(property set，包括對(duì)象數(shù)據(jù)以及數(shù)據(jù)屬性，字符串L是一種特殊的數(shù)據(jù)屬性值)。τ是一個(gè)函數(shù)，定義知識(shí)庫(kù)D中的所有三元組，其映射關(guān)系可以表示為(C∪I)×(C∪I∪L)→P，即連接關(guān)系(s,p,o)，其中符號(hào)s表示主語(yǔ)，p表示謂語(yǔ)，o表示賓語(yǔ)。為后文敘述的方便，使用符號(hào){e}:{C∪P∪I∪L}表示所有的類(lèi)，關(guān)系，實(shí)例以及字符中的元素。

在知識(shí)庫(kù)檢索方面，關(guān)鍵詞檢索是最易于接受的檢索方式。使用詞袋表示關(guān)鍵詞系列，則關(guān)鍵詞檢索K表示為：K:{k1,k2,…,kn}。

關(guān)鍵詞檢索未能體現(xiàn)數(shù)據(jù)間的關(guān)聯(lián)信息，因而檢索結(jié)果與用戶期望數(shù)據(jù)差異較大。為此，提出了形式化查詢(xún)的思想。形式化查詢(xún)F表示為：F:〈C',I',P',V,τ'〉，即形式化查詢(xún)F是知識(shí)庫(kù)有向圖GD的子圖。其中V是在搜索知識(shí)庫(kù)中本體關(guān)系或節(jié)點(diǎn)過(guò)程中發(fā)現(xiàn)的非關(guān)鍵詞(即查詢(xún)語(yǔ)言中的缺失詞)。

一方面，形式化查詢(xún)語(yǔ)言是檢索這類(lèi)結(jié)構(gòu)化數(shù)據(jù)的有效方式。另一方面，用戶習(xí)慣自然語(yǔ)言(如關(guān)鍵字)為基礎(chǔ)的檢索方式。因而如何自動(dòng)將關(guān)鍵詞為基礎(chǔ)的檢索方式轉(zhuǎn)換成以形式化查詢(xún)?yōu)榛A(chǔ)的檢索方式是實(shí)現(xiàn)數(shù)據(jù)網(wǎng)的重要一環(huán)。

例如，自然語(yǔ)言查詢(xún)“Who was married to an actor that played in Philadelphia ?”，用戶甚至可能輸入如下關(guān)鍵字查詢(xún)”Who married to actor Philadelphia”。

則根據(jù)本體結(jié)構(gòu)，其有效的SPARQL查詢(xún)語(yǔ)句為：

select ?x where {

?y type actor.

?y starring Philadelphia.

?y spouse ?x.}

關(guān)鍵詞檢索固有的模糊性、不明確性與以消除這種模糊、不明確性為宗旨的形式化查詢(xún)語(yǔ)言之間的矛盾使這種轉(zhuǎn)換面臨如下挑戰(zhàn)：

(1)術(shù)語(yǔ)奇異性以及同一性：一方面，用戶不了解本體所使用的術(shù)語(yǔ)(即本體無(wú)關(guān)查詢(xún))，查詢(xún)關(guān)鍵詞與這些術(shù)語(yǔ)之間存在差異。另一方面，不同的術(shù)語(yǔ)可能表達(dá)相同的含義。

(2)術(shù)語(yǔ)及術(shù)語(yǔ)間關(guān)聯(lián)的缺失：在形式化邏輯查詢(xún)中必須明確概念、實(shí)例間的關(guān)聯(lián)，而在查詢(xún)關(guān)鍵詞之間并不存在任何關(guān)聯(lián)。

(3)查詢(xún)排序：由于查詢(xún)關(guān)鍵詞的含糊性，同一關(guān)鍵詞可能生成多種形式化查詢(xún)語(yǔ)句，對(duì)這些查詢(xún)語(yǔ)句的排序成為關(guān)鍵性的因素之一。

文中的貢獻(xiàn)主要有以下兩點(diǎn)：

引入查詢(xún)度量模型，一種主觀查詢(xún)滿意度度量方法，貫穿整個(gè)分析過(guò)程。與精度、召回率等客觀指標(biāo)相結(jié)合，有效刻畫(huà)所提方法的有效性與正確性；引入本體自動(dòng)構(gòu)建查詢(xún)語(yǔ)義圖，既有效消除語(yǔ)義歧義，又降低構(gòu)造空間的復(fù)雜度。

2 查詢(xún)度量模型

為定性度量用戶信息檢索的需求以及形式化解釋查詢(xún)關(guān)鍵詞，文中采用了文獻(xiàn)[1]中提出的四種理論模型：

(1)用戶心理模型Ou，即用戶在檢索信息時(shí)的期望(結(jié)果)模型。雖然該模型與用戶相關(guān)，但可以設(shè)想成由與當(dāng)前信息檢索需求相關(guān)的實(shí)體及其關(guān)聯(lián)的結(jié)構(gòu)組成。這些實(shí)體可能是現(xiàn)實(shí)的對(duì)象也可能是抽象的概念。用戶在查詢(xún)時(shí)提供了大多數(shù)實(shí)體，并稱(chēng)未提供的實(shí)體為“缺失(gaps)”實(shí)體。

(2)用戶問(wèn)題模型Qu，由構(gòu)造出用戶語(yǔ)言Lu的語(yǔ)言原語(yǔ)Pu的元素組成，即用戶心理模型Qu中的元素轉(zhuǎn)換成語(yǔ)言原語(yǔ)Pu中的元素的結(jié)果集。特別地，問(wèn)題模型Qu中可以用特定的元素來(lái)表示用戶心理模型中的缺失實(shí)體。

(3)系統(tǒng)資源模型Os，由構(gòu)造出系統(tǒng)語(yǔ)言Ls的語(yǔ)言原語(yǔ)Ps的元素組成，與具體的形式化語(yǔ)言無(wú)關(guān)，這些元素構(gòu)成了特定本體的實(shí)體集。與抽象的用戶心理模型Ou相對(duì)，系統(tǒng)資源模型Os中的實(shí)體和結(jié)構(gòu)應(yīng)該明確給出，并可以直接訪問(wèn)。這些元素構(gòu)成了系統(tǒng)相應(yīng)用戶查詢(xún)的知識(shí)庫(kù)。

值得注意的是，模型間的對(duì)應(yīng)關(guān)系影響基于本體的信息檢索結(jié)果，即用戶心理模型Ou與系統(tǒng)資源模型Os中的實(shí)體與結(jié)構(gòu)匹配的越多，則系統(tǒng)使用系統(tǒng)資源模型Os填充缺失項(xiàng)的機(jī)會(huì)越高，查詢(xún)的準(zhǔn)確率越高。同樣道理，用戶語(yǔ)言Lu與系統(tǒng)語(yǔ)言Ls的語(yǔ)法結(jié)構(gòu)及語(yǔ)義越相關(guān)，則用戶問(wèn)題模型Ou到系統(tǒng)資源模型Os間的映射越簡(jiǎn)單，用戶查詢(xún)的解釋越簡(jiǎn)單。

3 相關(guān)工作

自然語(yǔ)言查詢(xún)RDF知識(shí)庫(kù)一直是學(xué)術(shù)界、工業(yè)界的研究熱點(diǎn)之一。其基本思想是：以本體為基礎(chǔ)分解自然查詢(xún)語(yǔ)言結(jié)構(gòu)，借助圖模式或機(jī)器學(xué)習(xí)方法生成SPARQL查詢(xún)語(yǔ)句。其過(guò)程描述如下：首先分解自然查詢(xún)語(yǔ)言結(jié)構(gòu)，獲取相應(yīng)的詞匯集，在對(duì)詞匯集處理(如詞根、同義詞識(shí)別等)的基礎(chǔ)上，將詞匯集映射成術(shù)語(yǔ)集(本體中的類(lèi)、屬性、實(shí)例等)；之后，根據(jù)術(shù)語(yǔ)集構(gòu)造查詢(xún)圖，補(bǔ)充缺失的術(shù)語(yǔ)及屬性；最后根據(jù)構(gòu)造的查詢(xún)圖生成SPARQL查詢(xún)語(yǔ)句。查詢(xún)精度和召回率隨各個(gè)階段所采用的技術(shù)而異。依據(jù)SPARQL查詢(xún)語(yǔ)句生成方式的不同，自然語(yǔ)言查詢(xún)轉(zhuǎn)換成SPARQL查詢(xún)大致分為如下三類(lèi)：直接轉(zhuǎn)換法、模板法、機(jī)器學(xué)習(xí)法。

直接轉(zhuǎn)換法指從查詢(xún)圖直接獲取對(duì)應(yīng)的SPARQL查詢(xún)語(yǔ)句，文獻(xiàn)[1-5]屬于該類(lèi)方法。

模板法則根據(jù)檢索的類(lèi)型，采用事先確定的、或者自動(dòng)創(chuàng)建的模板構(gòu)建SPARQL查詢(xún)語(yǔ)句，文獻(xiàn)[6-9]屬于該類(lèi)方法。

機(jī)器學(xué)習(xí)法依據(jù)檢索結(jié)果是否屬于所需資源，將查詢(xún)分為正例和反例，采用機(jī)器學(xué)習(xí)的方法獲得穩(wěn)定的SPARQL查詢(xún)語(yǔ)句，文獻(xiàn)[10-15]采用了該方法。

4 實(shí)現(xiàn)方法

文中的實(shí)現(xiàn)方法基于如下的假設(shè)：

假設(shè)1：被檢索知識(shí)庫(kù)D中C,I,L,R,τ是已知的，即被檢索數(shù)據(jù)的背景知識(shí)是已知的，但用戶并不關(guān)心。

假設(shè)2：存在如下兩種對(duì)應(yīng)關(guān)系，①用戶心理模型中的實(shí)體(thoughtentities)映射到本體實(shí)體集中的實(shí)體(本體實(shí)體集由個(gè)體(I)、概念(C)、數(shù)據(jù)屬性(P)，字符集(L)等組成)；②用戶心理模型中的關(guān)聯(lián)(association)映射成如下的關(guān)聯(lián)類(lèi)型:〈i,C〉,〈i1,P,i2〉及〈i,L,j〉，其中i,i1,i2∈I，j∈P。與描述邏輯語(yǔ)法相對(duì)應(yīng)，這些關(guān)系分別表示i∈C，〈i1,i2〉∈P及〈i,j〉∈L。

假設(shè)3：設(shè)用戶問(wèn)題模型是基于關(guān)鍵詞查詢(xún)的，即Qu=(k1,k2,…,kn)。系統(tǒng)查詢(xún)模型Qs是基于描述邏輯合取式的。文中目標(biāo)是尋找用戶問(wèn)題模型Qu與系統(tǒng)資源模型Qs之間的關(guān)系(f:Qu→Qs)，使系統(tǒng)資源模型Qs與用戶心理模型Qu之間的差異最小。

4.1 例 子

先通過(guò)簡(jiǎn)單的例子解釋該方法的原理及步驟。如圖1所示，用戶想要檢索“Who was married to an actor that played in Philadelphia ?”(對(duì)應(yīng)用戶的心理模型)，用戶可能發(fā)布如下查詢(xún)內(nèi)容(即用戶的問(wèn)題模型)：=“Whomarried to actor Philadelphia”。SPARQL自動(dòng)轉(zhuǎn)換過(guò)程分析如下：

第一步，將用戶問(wèn)題模型中的元素映射成系統(tǒng)資源模型中的本體元素，如下所示：spouse、actor、以及Philadelphia，具體方法見(jiàn)4.2節(jié)。可見(jiàn)，這些元素并不能與用戶心理模型中的元素完全對(duì)應(yīng)。而某些缺失的元素也使得構(gòu)造出滿足用戶需求的查詢(xún)較為困難。

所謂缺失元素是指在用戶心理模型中存在，但在用戶問(wèn)題模型中并未明確指出的元素，如上例中的Antonio_Banderas與actor之間的“type”屬性、Antonio_Banderas與Philadelphia的“starring”屬性等。這些缺失的元素需要在構(gòu)造正式查詢(xún)語(yǔ)句之前明確補(bǔ)充完整。

在第二步中，假設(shè)搜索深度為2，利用用戶問(wèn)題模型中的元素在知識(shí)庫(kù)中依次搜索，獲取對(duì)應(yīng)的關(guān)系以及元素。如上例所示，從married to(映射到語(yǔ)義本體中的spouse)開(kāi)始搜索，得到元素“Antonio_Banderas”及“Melanie_Griffith”。從actor開(kāi)始搜索，得到關(guān)系“type”以及元素Antonio_Banderas。從Philadelphia開(kāi)始搜索，得到關(guān)系“starring”以及元素“Antonio_Banderas”。這樣，得到查詢(xún)語(yǔ)義子圖，如圖1中的System Query Model所示，搜索算法見(jiàn)4.3節(jié)。

第三步根據(jù)第二步所獲取的查詢(xún)語(yǔ)義子圖，將圖轉(zhuǎn)換成最終查詢(xún)(該例中，得到如第二節(jié)所示的SPARQL查詢(xún)語(yǔ)句)。將其應(yīng)用在對(duì)應(yīng)的SPARQL查詢(xún)終端，即可獲取查詢(xún)結(jié)果。轉(zhuǎn)換過(guò)程見(jiàn)4.4節(jié)。

圖1 自然語(yǔ)言查詢(xún)-SPARQL查詢(xún)轉(zhuǎn)換過(guò)程

4.2 術(shù)語(yǔ)映射

術(shù)語(yǔ)映射，即將用戶問(wèn)題模型Qu中的元素映射到系統(tǒng)資源模型Os中的本體元素。該過(guò)程具體分為如下兩步：

(1)將關(guān)鍵詞映射成IRI集，即獲取與用戶提供的關(guān)鍵詞匹配的實(shí)體集(如類(lèi)，屬性和實(shí)例)，且對(duì)于每個(gè)關(guān)鍵詞，都獲取到其對(duì)應(yīng)的候選IRI集。如對(duì)于關(guān)鍵詞marriedTo，可能獲取到的候選集為：{‘married’,‘spouse’,‘wife’}。字符串匹配及編輯距離是常用的匹配算法及度量指標(biāo)。

如前所述，用戶關(guān)鍵詞Qu=(k1,k2,…,kn)，則映射函數(shù)M:Qu→2C∪I∪P，對(duì)于每個(gè)關(guān)鍵詞ki，其候選集為CSki?C∪I∪P，其中C,I,P分別代表在知識(shí)庫(kù)中與關(guān)鍵詞ki相同或?yàn)殛P(guān)鍵詞ki子串的類(lèi)，實(shí)例及屬性。

(2)排序及選擇最終的候選集，即去除候選集CSki中與關(guān)鍵詞ki的任何解釋都不相關(guān)的元素，從而降低候選搜索空間大小。候選集排序由串相似度得分σ(ulable,Ki)及連接度CD(u)(u∈CSki)的乘積S(u)來(lái)確定，其中串相似度得分σ(ulable,Ki)的計(jì)算式為：

連接度CD(u)表示u在知識(shí)庫(kù)三元組中的發(fā)生頻次。

則

S(u)=σ(ulable,Ki)×log(CD(u))

4.3 關(guān)聯(lián)重構(gòu)

根據(jù)假設(shè)2，只搜索如下的三種關(guān)聯(lián)關(guān)系，即〈i,C〉,〈i1,P,i2〉與〈i,L,j〉。對(duì)搜索深度d分兩種情況進(jìn)行處理：①在預(yù)設(shè)搜索深度沒(méi)有匹配項(xiàng)，則停止搜索；②超過(guò)預(yù)設(shè)深度仍有匹配項(xiàng)，則繼續(xù)搜索，直至沒(méi)有匹配項(xiàng)為止。具體如下所示：

算法：語(yǔ)義查詢(xún)圖集的構(gòu)建。

SQG Construct(CS,d)

1 INPUT candidate set CS(the set of CSki)and the search depthd

2 OUTPUT the Semantic Query Graph, single or set

3 Initialize new empty graphg

4 fore∈CS

5 ifeis a concept

6 then for allibeing instance ofe

7 do I-P-I Construct(e,d,g)

8 else ifeis an object property

9 then for alli,jwith ∈CS

10 do I-P-I Construct(i,d,g)

11 do I-P-I Construct(j,d,g)

12 else ifeis a data property

13 then for alli,jwith ∈CS

14 do J-P-I Construct(j,d,g)

15 else ifeis a individual

16 then I-P-I Construct(e,d,g)

17 else ifeis a data value

18 then J-P-I Construct(e,d,g)

19 returng

在算法的執(zhí)行過(guò)程中，依據(jù)獲取的候選集CS，盡可能合并由上述算法搜索到的語(yǔ)義查詢(xún)子集，以構(gòu)造盡可能最大的語(yǔ)義查詢(xún)圖。對(duì)于不能合并的子圖，依據(jù)子圖中CS元素的出現(xiàn)頻次排序，給予取舍(如舍去標(biāo)識(shí)為×的映射)。并對(duì)搜索過(guò)程中的未知類(lèi)、實(shí)例、屬性使用‘?’表示。

4.4 查詢(xún)構(gòu)建

查詢(xún)構(gòu)建即通過(guò)語(yǔ)義查詢(xún)圖的分析，使用占位符表示某些實(shí)體或關(guān)系，自動(dòng)生成最終的查詢(xún)語(yǔ)句。查詢(xún)構(gòu)建步驟如下：①?gòu)母?jié)點(diǎn)開(kāi)始，對(duì)查詢(xún)語(yǔ)義圖中的‘?’進(jìn)行遍歷(如深度或?qū)哟伪闅v方式)并編號(hào)(依次使用x、y、z等未知符號(hào)表示)；②遍歷語(yǔ)義查詢(xún)樹(shù)，收集包含位置變量的三元組，組合成最終的SPARQL查詢(xún)語(yǔ)句。

5 實(shí)現(xiàn)與評(píng)價(jià)

為評(píng)估文中提出方法的性能，利用Java開(kāi)發(fā)核心算法，并借用相關(guān)工具輔助相關(guān)模塊的實(shí)現(xiàn)。系統(tǒng)采用了DBpedia數(shù)據(jù)集(數(shù)據(jù)集事先下載到本體)，自然語(yǔ)言問(wèn)題集采用QALD-6(http://qald.sebastianwalter.org/6/data/qald-6-test-datacube.json)問(wèn)題集，并將實(shí)驗(yàn)數(shù)據(jù)與DEANNA[10-12]系統(tǒng)進(jìn)行比較。實(shí)驗(yàn)過(guò)程及結(jié)果如下所示:

(1)利用GATE(一個(gè)開(kāi)源的自然語(yǔ)言處理項(xiàng)目，詳細(xì)內(nèi)容及使用方法見(jiàn)其主頁(yè)：https://gate.ac.uk/overview.html)提取自然查詢(xún)語(yǔ)言中的關(guān)鍵字(以關(guān)鍵字查詢(xún)則忽略該步)。

(2)抽取知識(shí)庫(kù)本體中的類(lèi)、實(shí)例、屬性，并利用Lucence(一個(gè)高性能的，全文本搜索引擎庫(kù))建立術(shù)語(yǔ)集索引及關(guān)鍵字與術(shù)語(yǔ)之間的搜索匹配。

主要從三個(gè)方面評(píng)價(jià)系統(tǒng)的性能，即精度(precision(q))、召回率(recall(q))及響應(yīng)時(shí)間(overtime)。其中精度和召回率定義如下：

精度和召回率的實(shí)驗(yàn)數(shù)據(jù)以及比較結(jié)果如表1所示。

系統(tǒng)總的運(yùn)行時(shí)間如表2所示。

表1 評(píng)估QALD-6測(cè)試問(wèn)題(基于DBpedia,總共50個(gè)測(cè)試問(wèn)題)

表2 系統(tǒng)能正確回答的問(wèn)題及其響應(yīng)時(shí)間

續(xù)表2

將該數(shù)據(jù)與DEANNA數(shù)據(jù)進(jìn)行對(duì)比，結(jié)果如圖2所示。

圖2 系統(tǒng)總的響應(yīng)時(shí)間對(duì)比

6 結(jié)束語(yǔ)

通過(guò)對(duì)自然語(yǔ)言查詢(xún)與SPARQL查詢(xún)轉(zhuǎn)換模型空間及轉(zhuǎn)換過(guò)程的建模及形式化描述，提出了以語(yǔ)義查詢(xún)圖為基礎(chǔ)的轉(zhuǎn)換方法。該方法將自然語(yǔ)言查詢(xún)(或關(guān)鍵字查詢(xún))轉(zhuǎn)換為SPARQL查詢(xún)形式[13-15]，從而實(shí)現(xiàn)基于語(yǔ)義的搜索。而且方法提出根據(jù)語(yǔ)義查詢(xún)圖所包含語(yǔ)義元素(關(guān)鍵詞對(duì)應(yīng)到本體中的元素)的多少進(jìn)行查詢(xún)排序以及取舍，在性能未降低的情況下，降低了系統(tǒng)資源的消耗。

下一步主要從三個(gè)方面增強(qiáng)系統(tǒng)的性能：進(jìn)一步完善語(yǔ)義查詢(xún)圖理論及其構(gòu)造性能，提高語(yǔ)義查詢(xún)圖的合并算法，并驗(yàn)證排序算法的合理性；集成系統(tǒng)各個(gè)功能模塊，提供統(tǒng)一的Web接口；增強(qiáng)SPARQL查詢(xún)的結(jié)構(gòu)化表達(dá)能力，如支持NOT、OR等組合查詢(xún)方式。