基于地理位置信息的知識(shí)圖譜查詢方法

李怡霈，王宇翔

(杭州電子科技大學(xué) 計(jì)算機(jī)學(xué)院，浙江 杭州 310018)

知識(shí)圖譜是一種以圖的形式描述客觀事實(shí)的數(shù)據(jù)存儲(chǔ)管理技術(shù)，常作為智能問答、推薦系統(tǒng)等上層應(yīng)用的底層數(shù)據(jù)支撐，受到廣泛的關(guān)注。利用知識(shí)圖譜來高效地獲取大數(shù)據(jù)中有價(jià)值的知識(shí)信息已成為研究熱點(diǎn)[1]。目前，知識(shí)圖譜中的查詢大多針對(duì)事實(shí)類查詢開展，根據(jù)特定的業(yè)務(wù)場景，可衍生出一類基于地理位置信息的查詢。

針對(duì)事實(shí)類查詢的研究工作相對(duì)成熟，研究人員已在該領(lǐng)域取得了豐富的研究成果。文獻(xiàn)[2]提出了分布式SPARQL(SPARQL Protocol and RDF Query Language)查詢方法，使其能適用于大規(guī)模RDF(Resource Description Framework)數(shù)據(jù)的查詢。但這類查詢需具備專業(yè)知識(shí)，因此不適用于普通用戶。文獻(xiàn)[3]提出了一種關(guān)鍵字與查詢圖之間的轉(zhuǎn)換算法，但該算法只支持單跳關(guān)系的轉(zhuǎn)換。為方便用戶，文獻(xiàn)[4]通過將自然語言問題轉(zhuǎn)換為相應(yīng)查詢圖的方式，實(shí)現(xiàn)了基于知識(shí)圖譜的自然語言問答系統(tǒng)。文獻(xiàn)[5]為了降低查詢模板的構(gòu)建成本，提出了一種查詢模板自動(dòng)生成算法。文獻(xiàn)[6]提出了端到端的知識(shí)圖譜查詢方法，將查詢問題等價(jià)于利用知識(shí)圖譜嵌入模型實(shí)現(xiàn)頭、尾實(shí)體預(yù)測的問題。與此同時(shí)，文獻(xiàn)[7]基于h-鄰域向量化的思想提出一種快速圖搜索算法，對(duì)每個(gè)頂點(diǎn)h-跳鄰域的拓?fù)涮卣鬟M(jìn)行編碼，然后將查詢頂點(diǎn)和其匹配頂點(diǎn)的鄰域向量進(jìn)行比較以獲取子圖模式之間的相似性。文獻(xiàn)[8]提出了一個(gè)基于路徑長度的相似度模型，首次提出基于錨節(jié)點(diǎn)的免索引近似圖查詢算法。文獻(xiàn)[9]提出了基于圖模擬的圖模式匹配算法，以此提高子圖近似匹配的適用性。文獻(xiàn)[10]提出了集合相似度子圖匹配算法，該方法建立了頻繁查詢模式的節(jié)點(diǎn)索引，并通過兩步剪枝策略減少了搜索空間。文獻(xiàn)[11]提出一種范例查詢算法，能根據(jù)用戶提供的查詢描述來構(gòu)建用戶樣例以匹配查詢目標(biāo)。文獻(xiàn)[12]提出在最小圖編輯距離約束下查找相似子圖的方法。文獻(xiàn)[13]提出了一個(gè)語義相似度搜索模型。該模型基于先驗(yàn)知識(shí)與字符串編輯距離實(shí)現(xiàn)，但只適用于弱語義近似的圖查詢。文獻(xiàn)[14]采用重寫查詢文本的方法解決了詞匯不匹配問題，提高了查詢效率。

上述工作多關(guān)注于知識(shí)圖譜中實(shí)體間的謂詞語義關(guān)系，無法支持基于地理位置信息的知識(shí)圖譜查詢，例如“在日月山水小區(qū)周邊的家政公司工作的鐘點(diǎn)工”，該查詢問題中不僅包含實(shí)體間關(guān)系約束“工作”，同時(shí)也包含地理位置信息約束“周邊的”。于是，研究人員開始嘗試構(gòu)建基于地理位置信息的知識(shí)圖譜，例如文獻(xiàn)[15]構(gòu)建了LinkedGeoData數(shù)據(jù)集，從OpenStreetMap中獲取地理數(shù)據(jù)，通過分析數(shù)據(jù)源構(gòu)建三元組數(shù)據(jù)模型，將地理數(shù)據(jù)轉(zhuǎn)換為RDF格式，并在數(shù)據(jù)層面與DBpedia等數(shù)據(jù)源建立鏈接，以形成最終的結(jié)構(gòu)化地理數(shù)據(jù)源[16]。文獻(xiàn)[17]人構(gòu)建了一個(gè)眾包地理知識(shí)圖譜CrowdGeoKG，從OpenStreetMap中獲取不同類型的地理實(shí)體，并通過與維基百科中的地理實(shí)體做實(shí)體鏈接工作，豐富了地理實(shí)體的屬性內(nèi)容。

上述知識(shí)圖譜主要針對(duì)具有地理位置信息的地理實(shí)體構(gòu)建，缺失了大量與地理實(shí)體關(guān)聯(lián)的普通百科實(shí)體及相應(yīng)的關(guān)聯(lián)關(guān)系，無法支持本文討論的基于地理位置信息的知識(shí)圖譜查詢問題。因此，本文基于向百科知識(shí)圖譜中融合地理位置信息構(gòu)建而成的混合知識(shí)圖譜，通過抽取三元組，并構(gòu)建查詢圖以理解自然語言查詢問題。此外，本文結(jié)合實(shí)驗(yàn)室已有的事實(shí)類語義查詢方法，將基于地理位置信息的查詢問題分為6類，并分別研究了相應(yīng)的知識(shí)圖譜查詢方法。

1 先導(dǎo)知識(shí)

1.1 融合地理知識(shí)的混合知識(shí)圖譜

為本文研究提供數(shù)據(jù)支持的混合知識(shí)圖譜Gf的具體實(shí)例如圖1所示。本文共定義了5種地理實(shí)體的距離關(guān)系、8種地理實(shí)體的方位關(guān)系以及55種地理實(shí)體的類型，并融合了百科知識(shí)圖譜中的237種數(shù)據(jù)屬性。圖譜中的位置關(guān)系如表1所示。

表1 混合知識(shí)圖譜中的位置關(guān)系詳情

1.2 查詢問題中三元組的抽取

將本文涉及的基于地理位置信息的查詢分為實(shí)體查詢和屬性查詢，并根據(jù)地理位置信息約束的不同形式進(jìn)一步劃分為6類查詢問題，具體分類情況如表2所示。本文將基于Bert-NER(Bidirectional Encoder Representation from Transformers-Named Entity Recognition)的信息抽取系統(tǒng)中的實(shí)現(xiàn)邏輯引入LTP(Language Technology Platform)平臺(tái)，完成了對(duì)查詢問題中多個(gè)三元組的抽取。具體抽取結(jié)果示例如表3所示。

表2 基于地理位置信息的查詢問題的詳細(xì)分類

表3 三元組抽取結(jié)果示例

1.3 查詢圖的構(gòu)建

在完成對(duì)查詢問題中的三元組的抽取之后，分別為幾類問題構(gòu)建了相應(yīng)的查詢圖。

定義1查詢圖。定義查詢圖GQ=(VQ，EQ，PQ)，其中VQ是查詢結(jié)點(diǎn)的集合，EQ為邊的集合，PQ存儲(chǔ)節(jié)點(diǎn)的屬性。對(duì)于一個(gè)查詢問題VQ={vs，vg}，其中vs為某一特定結(jié)點(diǎn)，vg為查詢的目標(biāo)結(jié)點(diǎn)。vs的結(jié)點(diǎn)名稱和結(jié)點(diǎn)類型及vg的結(jié)點(diǎn)類型。已知EQ中包含邊e=。查詢圖構(gòu)建示例如圖2所示。

(a)

2 基于地理位置信息的實(shí)體查詢方法

基于地理位置信息的實(shí)體查詢的最終查詢目標(biāo)為知識(shí)圖譜中的一組實(shí)體。其主要查詢過程描述如下：首先，根據(jù)表1中的中文位置關(guān)系，將從查詢問題中抽取出的兩個(gè)三元組里的謂詞劃分為位置關(guān)系謂詞和百科關(guān)系謂詞，并相應(yīng)地將查詢問題分解為包含位置關(guān)系謂詞的位置查詢qw和包含百科關(guān)系謂詞的事實(shí)類查詢qb。其中，本文討論的基于地理位置信息的實(shí)體查詢問題的兩個(gè)子查詢問題間可能含有隱含信息，因此考慮隱含信息，分別完成qb和qw的查詢?？筛鶕?jù)已有研究[18]中提出的方法實(shí)現(xiàn)對(duì)qb的語義化查詢；然后，整合兩個(gè)子查詢，得到最終基于地理位置信息的實(shí)體查詢結(jié)果。根據(jù)查詢問題中不同的地理位置約束形式，可以繼續(xù)劃分為下文所述的5類實(shí)體查詢。

2.1 基于方位關(guān)系的實(shí)體查詢

基于方位關(guān)系的實(shí)體查詢問題，例如“在嘉里中心北邊的醫(yī)院上班的牙科醫(yī)生”，最終的查詢目標(biāo)為類型是“醫(yī)生”的一組未知實(shí)體?？蓮纳鲜霾樵儐栴}中抽取得到以下三元組：(嘉里中心，北邊的，醫(yī)院)和(醫(yī)院，牙科醫(yī)生，？)，并將其轉(zhuǎn)換為基于方位關(guān)系的位置子查詢qwf“嘉里中心北邊的醫(yī)院”和事實(shí)類子查詢qb“在醫(yī)院上班的牙科醫(yī)生”。其中，子查詢問題qb依據(jù)文獻(xiàn)[18]中的語義化圖查詢方法獲取查詢目標(biāo)。而子查詢問題qwf的主要查詢流程為：

步驟1獲取表1中的中文方位位置關(guān)系，通過TransE翻譯模型[19]得到中文方位位置關(guān)系對(duì)應(yīng)的詞向量，并創(chuàng)建一個(gè)列表listR用于存放上述關(guān)系向量X=(x1，x2，x3，…，xn)；

步驟2當(dāng)?shù)玫綇牟樵儐栴}中抽取出的三元組后，通過TransE翻譯模型獲取謂詞對(duì)應(yīng)的詞向量Y=(y1，y2，y3，…，yn)；

步驟3將詞向量Y依次與listR中存放的關(guān)系向量X進(jìn)行語義相似度計(jì)算，并創(chuàng)建一個(gè)大頂堆CS用于存放相似度大于閾值τ且排名位于top-k的關(guān)系。當(dāng)遍歷到語義相似度為1的關(guān)系時(shí)，停止遍歷，返回當(dāng)前關(guān)系。其中，語義相似度通過向量間的余弦相似度計(jì)算，具體如式(1)所示；

(1)

步驟4在得到與查詢問題中謂詞向量語義相似度排名位于top-k的位置關(guān)系后，根據(jù)相應(yīng)的查詢圖GQ1和GQ2分別定位到混合知識(shí)圖譜Gf中的對(duì)應(yīng)關(guān)系；

步驟5創(chuàng)建并初始化一個(gè)集合Sw用于存放最后返回的查詢結(jié)果；

步驟6在Gf中找到起始實(shí)體vn，根據(jù)得到的查詢圖GQ1中的方位位置關(guān)系，通過廣度優(yōu)先算法在Gf中向外遍歷vn的鄰居實(shí)體vm，并判斷當(dāng)前鄰居vm的類型是否與GQ1中的目標(biāo)類型相同。若相同，則將vm加入Sw，并記錄下Sw當(dāng)前的實(shí)體個(gè)數(shù)m；若不同，繼續(xù)遍歷下一個(gè)鄰居；

步驟7根據(jù)查詢圖GQ2中的方位位置關(guān)系，重復(fù)步驟6，直到m大于默認(rèn)返回結(jié)果數(shù)n，則結(jié)束查詢，返回Sw中的查詢結(jié)果。

得到基于方位關(guān)系的位置子查詢問題qwf的查詢結(jié)果集Sw后，將查詢結(jié)果代入事實(shí)類子查詢問題qb進(jìn)行語義化圖查詢。然后，新建一個(gè)集合R用于存放qb的查詢結(jié)果，也就是基于方位關(guān)系的實(shí)體查詢的最終結(jié)果。最后，返回結(jié)果集R中的值，完成查詢。

2.2 基于距離關(guān)系的實(shí)體查詢

基于距離關(guān)系的實(shí)體查詢問題，例如“在春波南苑附近的裝修公司工作的水電師傅”，最終的查詢目標(biāo)為類型是“水電師傅”的一組未知實(shí)體，其可被分解為基于距離關(guān)系的位置子查詢qwj和事實(shí)類子查詢qb。子查詢問題qb依據(jù)事實(shí)類查詢問題的語義化圖查詢方法獲取查詢目標(biāo)。子查詢問題qwj的具體實(shí)現(xiàn)步驟闡述如下：

步驟1獲取表1中的中文距離位置關(guān)系，通過TransE翻譯模型得到中文距離位置關(guān)系對(duì)應(yīng)的低維詞向量，并創(chuàng)建一個(gè)列表listR用于存放上述關(guān)系向量X=(x1，x2，x3，…，xn)；

步驟2～步驟3與基于方位關(guān)系的位置子查詢一致，不再贅述；

步驟4在得到與查詢問題中謂詞向量語義相似度排名位于top-k的位置關(guān)系后，根據(jù)相應(yīng)的查詢圖GQ定位到混合知識(shí)圖譜Gf中的對(duì)應(yīng)關(guān)系；

步驟5創(chuàng)建并初始化一個(gè)集合Sw用于存放最后返回的查詢結(jié)果；

步驟6在Gf中找到起始實(shí)體vn，根據(jù)得到的查詢圖GQ中的距離位置關(guān)系，通過廣度優(yōu)先算法在Gf中向外遍歷vn的鄰居實(shí)體vm，并判斷當(dāng)前鄰居vm的類型是否與GQ中的目標(biāo)類型相同。若相同，則將vm加入Sw，并記錄下Sw當(dāng)前的實(shí)體個(gè)數(shù)m；若不同，繼續(xù)遍歷下一個(gè)鄰居，直到m大于默認(rèn)返回結(jié)果數(shù)n，結(jié)束查詢，返回Sw中的查詢結(jié)果。

得到子查詢問題qwj的查詢結(jié)果集Sw后，將查詢結(jié)果代入qb進(jìn)行語義化圖查詢。然后，新建一個(gè)集合R用于存放qb的查詢結(jié)果，同時(shí)也是基于距離關(guān)系的實(shí)體查詢的最終結(jié)果。最后，返回結(jié)果集R中的值，完成查詢。

2.3 直接范圍約束下的實(shí)體查詢

直接范圍約束下的實(shí)體查詢，例如“住在海創(chuàng)基地1 000 m范圍內(nèi)的沈思齊的校友”，最終的查詢目標(biāo)為類型是“人”的一組未知實(shí)體，可轉(zhuǎn)換為直接范圍約束下的位置子查詢qwd和事實(shí)類子查詢qb。子查詢問題qb依據(jù)事實(shí)類查詢問題的語義化圖查詢方法獲取查詢目標(biāo)。子查詢問題qwd可根據(jù)K近鄰搜索思想，以圓形范圍作為搜索空間。因此，可以將查詢問題約束信息中的距離范圍建模為圓形搜索范圍的半徑r?；旌现R(shí)圖譜Gf中定義的距離關(guān)系邊隱含距離范圍信息，故可獲取距離關(guān)系的上界對(duì)查詢算法做剪枝操作。具體獲取規(guī)則如式(2)所示。

(2)

按照以下邏輯執(zhí)行直接范圍約束下的位置查詢：

步驟1首先構(gòu)建并初始化一個(gè)候選集S、一個(gè)小頂堆Sw和一個(gè)訪問列表C，分別用于存放候選的鄰居實(shí)體、查詢結(jié)果和訪問過的鄰居實(shí)體；

步驟2在混合知識(shí)圖譜Gf中找到起始實(shí)體vn。選取候選集中與vn之間的距離d取值最小的鄰居實(shí)體s。若最小距離大于r，則查詢結(jié)束，在約束范圍r內(nèi)沒有符合查詢條件的目標(biāo)實(shí)體；否則初始化一個(gè)集合M，用于存放vn的相鄰邊指向的鄰居實(shí)體s；

步驟3根據(jù)式(2)獲取當(dāng)前相鄰邊e的上界，并與r做比較。若上界不超過r，則將當(dāng)前相鄰邊e指向的鄰居實(shí)體s并加入M；

步驟4依次判斷M中鄰居實(shí)體en的類型是否符合查詢目標(biāo)實(shí)體給定的類型。若符合，則將當(dāng)前鄰居實(shí)體en從M中移除，加入結(jié)果集Sw，并記錄當(dāng)前M中的實(shí)體數(shù)|M|和Sw中的實(shí)體數(shù)|Sw|，直到M為空結(jié)束遍歷；

步驟5若當(dāng)前|Sw|尚未滿足目標(biāo)個(gè)數(shù)n，則不斷向外遍歷步驟3～步驟4，直到|Sw|大于給定的返回目標(biāo)個(gè)數(shù)n或達(dá)到迭代終止條件sp，結(jié)束查詢，將結(jié)果集Sw中的實(shí)體作為查詢結(jié)果返回。

得到直接范圍約束下的位置子查詢問題qwd的查詢結(jié)果集Sw后，創(chuàng)建一個(gè)集合Sb，用于存放事實(shí)類子查詢qb的查詢結(jié)果。然后根據(jù)查詢問題中實(shí)體間的隱含信息“住址”篩選出滿足隱含約束條件的查詢結(jié)果存入新建的集合Sbn中。接著，對(duì)集合Sw和集合Sbn執(zhí)行取交集的操作，得到直接范圍下的實(shí)體查詢的最終結(jié)果，并存入新建的集合R中。最后返回結(jié)果集R中的值，完成查詢。

如圖3(a)所示為查詢過程中存在一種特殊情況。目標(biāo)實(shí)體v4到起始實(shí)體vn的實(shí)際距離大于4 000 m，不在距離關(guān)系的定義范圍內(nèi)，故v4與vn之間不存在距離關(guān)系邊。起始實(shí)體vn迭代2次后的鄰居實(shí)體v3落在約束范圍r以外，按照算法將不再由實(shí)體v3繼續(xù)往下查找。但v3的某一個(gè)鄰居實(shí)體v4卻恰好是符合查詢要求的目標(biāo)實(shí)體。

為了解決上述問題，本文提出了優(yōu)化方案：本文為范圍約束r添加了給定容差ε，將范圍約束擴(kuò)展至(1+ε)r，具體如圖3(b)所示。通過將上述執(zhí)行步驟中的范圍約束r替換為(1+ε)r來實(shí)現(xiàn)上述優(yōu)化方案。

(a)

2.4 間接范圍約束下的實(shí)體查詢

間接范圍約束下的實(shí)體查詢問題可被看作為直接范圍約束下的實(shí)體查詢問題的擴(kuò)展。對(duì)查詢問題中的間接范圍約束進(jìn)行處理，將其轉(zhuǎn)換為直接范圍約束下的實(shí)體查詢。

例如“步行15分鐘內(nèi)能從學(xué)校到杭州大劇院的邵楠的熟人”是間接范圍約束下的查詢問題，其最終的查詢目標(biāo)為類型是“人”的一組未知實(shí)體。其可被分解為間接范圍約束下的位置子查詢qwi和事實(shí)類子查詢qb。子查詢問題qb依據(jù)事實(shí)類查詢問題的語義化圖查詢方法獲取查詢目標(biāo)。間接范圍約束下的位置子查詢問題qwi可通過向直接范圍約束下的位置子查詢qwd轉(zhuǎn)換以實(shí)現(xiàn)查詢。具體地，子查詢問題qwi中的地理位置約束“步行15分鐘內(nèi)”雖然不是直接的范圍約束條件，但可以通過簡單的速度換算來轉(zhuǎn)換間接的范圍約束條件。本文主要討論步行、騎行和乘車3種出行方式與范圍約束條件間的對(duì)應(yīng)關(guān)系，分別將其平均速度取值為5 km·h-1、20 km·h-1和70 km·h-1。具體轉(zhuǎn)換規(guī)則如下

(3)

(4)

(5)

式中，t表示出行時(shí)間；Lw、Lr和Ld分別表示步行的距離范圍、騎行的距離范圍和乘車的距離范圍，以m為單位。根據(jù)上述位置子查詢問題qwi“步行15分鐘內(nèi)能到杭州大劇院的學(xué)?！逼渲械姆秶s束條件“步行15分鐘內(nèi)”，選擇式(3)進(jìn)行換算，將其轉(zhuǎn)換成“杭州大劇院1 250 m范圍內(nèi)的學(xué)?！?。完成轉(zhuǎn)換后，間接范圍約束下的實(shí)體查詢策略與直接范圍約束下的實(shí)體查詢策略相同，此處不再贅述。

2.5 最值范圍約束下的實(shí)體查詢

實(shí)體查詢還涉及最值范圍約束形式，例如查詢問題“公司距離太子灣公園最近的呂樂寅的同學(xué)”，最終查詢目標(biāo)為類型是“人”的一組未知實(shí)體。其中，“最近的”為查詢問題中的最值范圍約束?？蓪⒃搯栴}分解為兩個(gè)子查詢問題：最值范圍約束下的位置子查詢qwe和事實(shí)類子查詢qb。子查詢問題qb依據(jù)事實(shí)類查詢問題的語義化圖查詢方法獲取查詢目標(biāo)。最值范圍約束下的位置子查詢問題qwe的查詢方案如下文所述。

由地理知識(shí)模型為地理實(shí)體添加的距離關(guān)系的定義可知，5種不同的距離關(guān)系隱含著相應(yīng)的距離范圍信息，距離關(guān)系nextTo、nearBy、notFarFrom、notAround和littleFarFrom對(duì)應(yīng)的距離范圍依次遞增。根據(jù)這些關(guān)系的隱含信息，可以將子查詢qwe轉(zhuǎn)換為基于距離關(guān)系的位置子查詢qwj的最值匹配問題。詳細(xì)的實(shí)現(xiàn)策略如下：

步驟1構(gòu)建并初始化候選集S和小頂堆Sw，分別用于存放候選鄰居實(shí)體和查詢結(jié)果；

步驟2在混合知識(shí)圖譜Gf中找到起始實(shí)體vn，通過廣度優(yōu)先算法在Gf中向外遍歷vn的相鄰邊e，判斷當(dāng)前相鄰邊e是否為nextTo關(guān)系。若是，獲取通過當(dāng)前e連接的鄰居實(shí)體vm，并將其加入到候選集S中；

步驟3判斷當(dāng)前vm類型是否為目標(biāo)類型。若是，將vm加入Sw，并計(jì)算vm與vn間的實(shí)際距離d。循環(huán)遍歷S中的鄰居實(shí)體，直到遍歷結(jié)束，返回堆頂實(shí)體vd作為查詢結(jié)果；

步驟4若相鄰邊未匹配到nextTo關(guān)系或遍歷結(jié)束尚未查詢到結(jié)果，則按上述步驟2～步驟3依次遍歷nearBy、notFarFrom、notAround和littleFarFrom關(guān)系。直到查詢到至少一個(gè)符合條件的目標(biāo)實(shí)體或遍歷完所有距離位置關(guān)系，查詢結(jié)束。

上述查詢方法存在缺陷，當(dāng)符合查詢條件的目標(biāo)實(shí)體vd與起始實(shí)體vn間的實(shí)際距離d超過距離關(guān)系定義的最大上界4 000 m時(shí)，該方法不再適用，但仍可按照直接范圍約束下的位置子查詢邏輯解決。將直接范圍約束下的實(shí)體查詢方法中的約束范圍r賦值為5 000 m，若查詢到目標(biāo)實(shí)體，則將堆頂實(shí)體作為查詢結(jié)果返回；若仍未查詢到目標(biāo)實(shí)體，則將約束范圍r等差增加賦值為6 000 m，重復(fù)上述操作，直至查詢到至少一個(gè)符合條件的目標(biāo)實(shí)體或遞增到設(shè)定的最大約束范圍時(shí)，終止查詢。

得到子查詢結(jié)果集Sw后，創(chuàng)建集合Sb用于存放事實(shí)類子查詢qb的查詢結(jié)果。然后根據(jù)查詢問題中實(shí)體間的隱含信息“工作單位”篩選出滿足隱含約束條件的查詢結(jié)果存入新建的集合Sbn中。接著，對(duì)集合Sw和集合Sbn執(zhí)行取交集的操作，得到直接范圍下的實(shí)體查詢的最終結(jié)果，并存入新建的集合R中。最后返回結(jié)果集R中的值，完成查詢。

3 基于地理位置信息的屬性查詢

基于地理位置信息的查詢中還包括一類基于地理位置信息的屬性查詢，同樣也由包含位置關(guān)系謂詞的位置查詢和包含百科關(guān)系謂詞的事實(shí)類查詢構(gòu)成，其最終的查詢目標(biāo)為事實(shí)類子查詢問題中所查找的實(shí)體的屬性值，例如“嘉柯寵物診所隔壁的打印店的營業(yè)時(shí)間”的最終的查詢目標(biāo)為屬性“營業(yè)時(shí)間”的值。結(jié)合前文所述的位置子查詢問題的實(shí)現(xiàn)邏輯與事實(shí)類子查詢問題的語義化圖查詢算法，完成基于地理位置信息的屬性查詢。具體查詢按照以下步驟實(shí)現(xiàn)：

步驟1判斷抽取出的三元組謂詞是否為范圍約束，若是，將其劃分為位置關(guān)系并標(biāo)記為范圍約束；若不是，將抽取的三元組中的謂詞與表1中的位置關(guān)系做對(duì)比，判斷謂詞屬于百科關(guān)系或位置關(guān)系，并據(jù)此將基于地理位置信息的屬性查詢問題分解為事實(shí)類子查詢問題qb和位置子查詢問題qw；

步驟2創(chuàng)建一個(gè)集合Sw用來存放qw的查詢結(jié)果。根據(jù)謂詞形式相應(yīng)調(diào)用直接范圍約束下的位置子查詢方法、間接范圍約束下的位置子查詢方法或最值范圍約束下的位置子查詢方法完成qw中帶范圍約束標(biāo)簽的位置子查詢，調(diào)用基于方位關(guān)系的實(shí)體查詢方法或基于距離關(guān)系的實(shí)體查詢完成qw中的其余查詢，并將查詢結(jié)果存入Sw；

步驟3將位置子查詢問題qw的查詢結(jié)果代入qb中，同時(shí)創(chuàng)建一個(gè)集合R用來存放qb的查詢結(jié)果。調(diào)用事實(shí)類查詢的語義化圖查詢方法完成對(duì)qb中屬性值的查詢，并將查詢結(jié)果存入R。返回最后R中的值，作為基于地理位置信息的屬性查詢的結(jié)果。

前文給出的屬性查詢問題“嘉柯寵物診所隔壁的打印店的營業(yè)時(shí)間”中的“隔壁的”為位置關(guān)系謂詞，“營業(yè)時(shí)間”是實(shí)體的百科屬性關(guān)系，可據(jù)此將上述基于地理位置信息的屬性查詢問題分解為位置子查詢qw和事實(shí)類子查詢qb。對(duì)于上述屬性查詢問題，抽取出的第1個(gè)三元組中的“打印店”是子查詢問題qw中查詢目標(biāo)的類型；抽取出的第2個(gè)三元組中缺失的屬性值為qb和最終基于地理位置信息的屬性查詢問題共同的查詢目標(biāo)。

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

本文進(jìn)行了大量實(shí)驗(yàn)來驗(yàn)證基于地理位置信息的知識(shí)圖譜查詢方法的查詢效果。

4.1 實(shí)驗(yàn)設(shè)置

4.1.1 數(shù)據(jù)集

本文實(shí)驗(yàn)使用自建的查詢測試集，構(gòu)建過程如下：首先，根據(jù)查詢問題模板，通過填充混合知識(shí)圖譜中的實(shí)體名稱以及定義好的地理實(shí)體類型、目標(biāo)實(shí)體類型，半自動(dòng)化地構(gòu)建每種查詢問題。例如模板“在<實(shí)體>附近的<地理實(shí)體類型>工作的<目標(biāo)實(shí)體類型>”，通過填充可構(gòu)建得到其中一個(gè)查詢問題為“在西湖音樂噴泉附近的商場工作的售貨員”。然后，將混合知識(shí)圖譜文件轉(zhuǎn)換為csv格式，根據(jù)構(gòu)建的查詢問題相應(yīng)的篩選出全部正確答案添加進(jìn)測試集中。最后，為6種查詢問題分別構(gòu)建了350個(gè)查詢問題，得到共含2 100個(gè)查詢問題的測試集T。為了對(duì)每種查詢問題的查詢效果做橫向?qū)Ρ?，本文繼續(xù)為6種查詢問題相應(yīng)的擴(kuò)展了不同結(jié)構(gòu)的查詢形式，并獲得了共包含4 200個(gè)查詢問題的基準(zhǔn)測試集Textend。擴(kuò)展的查詢形式為：Q1擴(kuò)展的查詢形式為“有哪些牙科醫(yī)生在嘉里中心北邊的醫(yī)院上班”；Q2擴(kuò)展的查詢形式為“有哪些水電師傅在春波南苑附近的裝修公司工作”；Q3擴(kuò)展的查詢形式為“沈思齊的哪些校友的住址離海創(chuàng)基地不超過1 000 m”；Q4擴(kuò)展的查詢形式為“邵楠的熟人里有誰從學(xué)校騎行10分鐘能到杭州大劇院”；Q5擴(kuò)展的查詢形式為“呂樂的哪些同學(xué)在離太子灣公園最近的公司上班”；Q6擴(kuò)展的查詢形式為“嘉柯寵物診所隔壁的打印店什么時(shí)間營業(yè)”。

4.1.2 查詢配置

設(shè)定返回結(jié)果個(gè)數(shù)n=10；設(shè)定基于方位關(guān)系的實(shí)體查詢和基于距離關(guān)系的實(shí)體查詢中的相似度閾值τ=0.95。

實(shí)驗(yàn)分析了給定容差ε和迭代次數(shù)sp對(duì)范圍約束下實(shí)體查詢效果的影響。由圖4和圖5可知，當(dāng)其他條件相同時(shí)，將給定容差ε設(shè)置為0.1或迭代次數(shù)設(shè)置為20時(shí)，可在查詢響應(yīng)時(shí)間和查詢效果間實(shí)現(xiàn)較好的平衡。因此，本文下述實(shí)驗(yàn)中設(shè)定ε=0.1，sp=20。

圖4 給定容差ε對(duì)查詢效果的影響

圖5 迭代次數(shù)sp對(duì)查詢效果的影響

4.1.3 評(píng)價(jià)標(biāo)準(zhǔn)

本文采用精確率P(Precision)、召回率R(Recall)和F1值3個(gè)評(píng)價(jià)標(biāo)準(zhǔn)來衡量查詢的效果。設(shè)正確的查詢結(jié)果數(shù)記為t，返回的查詢結(jié)果總數(shù)為w，測試集中正確答案的總數(shù)為k，則準(zhǔn)確率P、召回率R和F1的計(jì)算方法如式(6)所示。

(6)

4.2 實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)1本文據(jù)P、R和F1指標(biāo)，對(duì)6種不同的基于地理位置信息的知識(shí)圖譜查詢問題的查詢效果進(jìn)行了比較。實(shí)驗(yàn)結(jié)果為每種問題下所有問題查詢效果的平均值，具體如圖6所示。

圖6 各種查詢問題的平均查詢效果

由圖6可以看出，Q3(直接范圍約束下的實(shí)體查詢)和Q4(間接范圍約束下的實(shí)體查詢)的表現(xiàn)基本相當(dāng)，其精確率和召回率相對(duì)較優(yōu)。Q1(基于方位關(guān)系的實(shí)體查詢)和Q2(基于距離關(guān)系的實(shí)體查詢)表現(xiàn)基本相當(dāng)，其中Q1在召回率上的表現(xiàn)稍遜色于Q2，這是因?yàn)樵跇?gòu)建混合知識(shí)圖譜時(shí)，并沒有在兩兩實(shí)體間都添加方位關(guān)系，使得部分符合查詢要求的目標(biāo)實(shí)體無法通過實(shí)體間的關(guān)聯(lián)邊被查找。Q5(最值范圍約束下的位置查詢)和Q6(基于地理位置信息的屬性查詢)在精確率上的表現(xiàn)明顯優(yōu)于在召回率上的表現(xiàn)，這是因?yàn)镼5的目標(biāo)實(shí)體只有一個(gè)，且由于查詢方法中對(duì)于查詢范圍有限制，使得查找的目標(biāo)實(shí)體個(gè)數(shù)只存在0和1兩種可能；又由于查找到唯一一個(gè)實(shí)體時(shí)，不是正例就是負(fù)例，所以Q5的精準(zhǔn)率較高，召回率較低。同樣的，由于Q6的查詢目標(biāo)為屬性值，返回的查詢結(jié)果也大多具有唯一性，故其也表現(xiàn)出較高的精確率和較低的召回率。

實(shí)驗(yàn)2對(duì)每種問題不同查詢形式下的查詢效果進(jìn)行對(duì)比實(shí)驗(yàn)，結(jié)果如圖7所示。

由圖7(a)和圖7(b)可知，Q1和Q2在不同查詢形式下的查詢效果相差不大。這是因?yàn)樵诓樵儐栴}語義理解的過程中，從不同查詢形式下的問題中抽取出的三元組是幾乎一致的。由圖7(c)和圖7(d)可知，在擴(kuò)展的查詢形式下，Q3和Q4的精確率和召回率同時(shí)出現(xiàn)小幅度下滑，但整體穩(wěn)定。這是因?yàn)樵跀U(kuò)展的查詢形式下，有一部分查詢問題無法根據(jù)定義的規(guī)則抽取出完全正確的三元組，導(dǎo)致整體查詢的平均效果受到了輕微影響。如圖7(e)和圖7(f)所示，Q5和Q6在不同查詢形式下的查詢效果差異較明顯。其精確率明顯下降是由于在查詢問題語義理解的過程中，不同查詢形式下三元組的抽取結(jié)果產(chǎn)生不同程度的誤差。由于Q5的查詢目標(biāo)為最值，因此返回的查詢結(jié)果具有唯一性。Q6的查詢目標(biāo)為屬性值，因此返回的查詢結(jié)果也大多具有唯一性，所以對(duì)于Q5和Q6的召回率影響不大。由圖7可知，本文提出的基于地理位置信息的知識(shí)圖譜查詢方法，在處理不同查詢模式下的最值范圍約束下的實(shí)體查詢問題和基于地理位置信息的屬性查詢問題時(shí)，適應(yīng)性表現(xiàn)相對(duì)欠佳；在處理直接范圍約束下的實(shí)體查詢問題和間接范圍約束下的實(shí)體查詢問題時(shí)，詢效果相對(duì)較優(yōu)，但因查詢問題理解的誤差，影響了對(duì)不同查詢模式的適應(yīng)性；在處理基于方位關(guān)系的實(shí)體查詢問題、基于距離關(guān)系的實(shí)體查詢問題時(shí)，查詢效果相對(duì)較優(yōu)且對(duì)不同查詢模式具有較好的適應(yīng)性。

(a)

5 結(jié)束語

本文提出了一種基于地理位置信息的知識(shí)圖譜查詢方法，并將基于地理位置信息的查詢問題分為6類分別解決?；诜轿魂P(guān)系和基于距離關(guān)系的實(shí)體查詢通過向量化表示位置關(guān)系謂詞，計(jì)算謂詞語義相似度并根據(jù)查詢圖做廣度優(yōu)先搜索以獲取查詢結(jié)果。直接范圍約束下的實(shí)體查詢按照k近鄰搜索思想，基于混合知識(shí)圖譜中位置關(guān)系的隱含信息展開查詢。在此基礎(chǔ)上，將直接范圍約束下的實(shí)體查詢方法擴(kuò)展至適用于間接范圍約束下的實(shí)體查詢，并根據(jù)最值范圍約束下的查詢問題的自身特性，為其中一部分特殊范圍約束下的實(shí)體查詢問題，提供了基于距離關(guān)系邊的查詢方法。然后，本文結(jié)合位置查詢邏輯和事實(shí)類問題的屬性查詢方法，提出了基于地理位置信息的屬性查詢方案。最后，本文對(duì)比了各種查詢問題的平均查詢效果，以及每種查詢問題在不同查詢形式下的平均查詢效果。實(shí)驗(yàn)結(jié)果表明，本文提出的方法具有一定的應(yīng)用價(jià)值。