關聯數據的自然語言查詢方法

肖 錚

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

1 動 機

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

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

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

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

一方面，形式化查詢語言是檢索這類結構化數據的有效方式。另一方面，用戶習慣自然語言(如關鍵字)為基礎的檢索方式。因而如何自動將關鍵詞為基礎的檢索方式轉換成以形式化查詢?yōu)榛A的檢索方式是實現數據網的重要一環(huán)。

例如，自然語言查詢“Who was married to an actor that played in Philadelphia ?”，用戶甚至可能輸入如下關鍵字查詢”Who married to actor Philadelphia”。

則根據本體結構，其有效的SPARQL查詢語句為：

select ?x where {

?y type actor.

?y starring Philadelphia.

?y spouse ?x.}

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

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

(2)術語及術語間關聯的缺失：在形式化邏輯查詢中必須明確概念、實例間的關聯，而在查詢關鍵詞之間并不存在任何關聯。

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

文中的貢獻主要有以下兩點：

引入查詢度量模型，一種主觀查詢滿意度度量方法，貫穿整個分析過程。與精度、召回率等客觀指標相結合，有效刻畫所提方法的有效性與正確性；引入本體自動構建查詢語義圖，既有效消除語義歧義，又降低構造空間的復雜度。

2 查詢度量模型

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

(1)用戶心理模型Ou，即用戶在檢索信息時的期望(結果)模型。雖然該模型與用戶相關，但可以設想成由與當前信息檢索需求相關的實體及其關聯的結構組成。這些實體可能是現實的對象也可能是抽象的概念。用戶在查詢時提供了大多數實體，并稱未提供的實體為“缺失(gaps)”實體。

(2)用戶問題模型Qu，由構造出用戶語言Lu的語言原語Pu的元素組成，即用戶心理模型Qu中的元素轉換成語言原語Pu中的元素的結果集。特別地，問題模型Qu中可以用特定的元素來表示用戶心理模型中的缺失實體。

(3)系統(tǒng)資源模型Os，由構造出系統(tǒng)語言Ls的語言原語Ps的元素組成，與具體的形式化語言無關，這些元素構成了特定本體的實體集。與抽象的用戶心理模型Ou相對，系統(tǒng)資源模型Os中的實體和結構應該明確給出，并可以直接訪問。這些元素構成了系統(tǒng)相應用戶查詢的知識庫。

值得注意的是，模型間的對應關系影響基于本體的信息檢索結果，即用戶心理模型Ou與系統(tǒng)資源模型Os中的實體與結構匹配的越多，則系統(tǒng)使用系統(tǒng)資源模型Os填充缺失項的機會越高，查詢的準確率越高。同樣道理，用戶語言Lu與系統(tǒng)語言Ls的語法結構及語義越相關，則用戶問題模型Ou到系統(tǒng)資源模型Os間的映射越簡單，用戶查詢的解釋越簡單。

3 相關工作

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

直接轉換法指從查詢圖直接獲取對應的SPARQL查詢語句，文獻[1-5]屬于該類方法。

模板法則根據檢索的類型，采用事先確定的、或者自動創(chuàng)建的模板構建SPARQL查詢語句，文獻[6-9]屬于該類方法。

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

4 實現方法

文中的實現方法基于如下的假設：

假設1：被檢索知識庫D中C,I,L,R,τ是已知的，即被檢索數據的背景知識是已知的，但用戶并不關心。

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

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

4.1 例 子

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

第一步，將用戶問題模型中的元素映射成系統(tǒng)資源模型中的本體元素，如下所示：spouse、actor、以及Philadelphia，具體方法見4.2節(jié)?？梢姡@些元素并不能與用戶心理模型中的元素完全對應。而某些缺失的元素也使得構造出滿足用戶需求的查詢較為困難。

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

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

第三步根據第二步所獲取的查詢語義子圖，將圖轉換成最終查詢(該例中，得到如第二節(jié)所示的SPARQL查詢語句)。將其應用在對應的SPARQL查詢終端，即可獲取查詢結果。轉換過程見4.4節(jié)。

圖1 自然語言查詢-SPARQL查詢轉換過程

4.2 術語映射

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

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

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

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

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

則

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

4.3 關聯重構

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

算法：語義查詢圖集的構建。

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í)行過程中，依據獲取的候選集CS，盡可能合并由上述算法搜索到的語義查詢子集，以構造盡可能最大的語義查詢圖。對于不能合并的子圖，依據子圖中CS元素的出現頻次排序，給予取舍(如舍去標識為×的映射)。并對搜索過程中的未知類、實例、屬性使用‘?’表示。

4.4 查詢構建

查詢構建即通過語義查詢圖的分析，使用占位符表示某些實體或關系，自動生成最終的查詢語句。查詢構建步驟如下：①從根節(jié)點開始，對查詢語義圖中的‘?’進行遍歷(如深度或層次遍歷方式)并編號(依次使用x、y、z等未知符號表示)；②遍歷語義查詢樹，收集包含位置變量的三元組，組合成最終的SPARQL查詢語句。

5 實現與評價

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

(1)利用GATE(一個開源的自然語言處理項目，詳細內容及使用方法見其主頁：https://gate.ac.uk/overview.html)提取自然查詢語言中的關鍵字(以關鍵字查詢則忽略該步)。

(2)抽取知識庫本體中的類、實例、屬性，并利用Lucence(一個高性能的，全文本搜索引擎庫)建立術語集索引及關鍵字與術語之間的搜索匹配。

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

精度和召回率的實驗數據以及比較結果如表1所示。

系統(tǒng)總的運行時間如表2所示。

表1 評估QALD-6測試問題(基于DBpedia,總共50個測試問題)

表2 系統(tǒng)能正確回答的問題及其響應時間

續(xù)表2

將該數據與DEANNA數據進行對比，結果如圖2所示。

圖2 系統(tǒng)總的響應時間對比

6 結束語

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

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