基于Seq2Seq 模型的SparQL 查詢預測?

楊東華,鄒開發,王宏志,王金寶

1(哈爾濱工業大學 分析測試與計算中心,黑龍江 哈爾濱 150001)

2(哈爾濱工業大學 計算學部,黑龍江 哈爾濱 150001)

近年來,支撐人工智能的數據管理和分析技術已成為當前大數據與人工智能領域的研究熱點,在圖數據庫領域也是如此.利用圖數據庫中的數據管理與分析技術,可以有效促進人工智能領域的發展.例如:在類似于微信或者Facebook 這樣的社交網絡中,存在著大量用戶與用戶之間的關系,適合用圖數據模型進行存儲.在商業領域,公司控股關系、法人關系等也構成了一個龐大的網絡,這些數據更適合使用圖數據庫進行存儲,并借助人工智能,利用數據管理與分析技術為用戶、公司等提供更多的幫助.

查詢預測是圖數據庫領域支撐人工智能的技術之一,結合各種人工智能方法,利用已有的查詢對用戶未來的查詢進行預測,然后進行數據預加載,從而提高圖數據庫的響應效率.這些方法對人工智能本身的發展起到了推動作用.

以SparQL 查詢為例,目前已有一些研究人員提出了SparQL 查詢預測的算法.這些算法往往分為兩類.

? 一類方法如文獻[1?3],從圖數據庫讀取數據源的信息,然后根據這些信息來對用戶可能的查詢進行預測.這樣的方法能夠結合數據信息,但也使得算法不具有跨數據移植性.當更換了其他數據源之后,可能會因為某些信息的缺失而使算法無法正確工作;

? 另一類方法則通常從圖數據庫的工作日志中獲取用戶的歷史查詢的信息,并計算這些歷史查詢間的相似度來預測下一個可能的相似的SparQL 查詢.雖然具有了跨數據移植性,但仍然具有局限性.文獻[4,5]中使用圖模式匹配的算法要求歷史查詢必須存在重復性,才可以匹配到連續相似的查詢以創建模板;文獻[6,7]中使用相似度的算法,由于獨立計算三元組的相似度導致三元組之間的聯系沒有被考慮到,影響了預測的準確率.

使用圖模式匹配的方法僅僅考慮相似的查詢,而不考慮查詢間的聯系;而利用三元組的相似度進行計算,則將查詢本身進行細化了,沒有考慮到同一個查詢內三元組間的影響.因此,本文將查詢轉化為序列,不同的查詢序列進行連接,將查詢內部三元組的聯系以及查詢間的聯系信息存儲于序列之中,進而本文使用Seq2Seq 模型處理這些序列數據,提出了一種基于Seq2Seq 模型的SparQL 查詢預測算法.本文的主要研究重點在于如何將用戶的查詢轉化為可計算的特征向量,合適的特征向量能夠提高Seq2Seq 模型的學習效果,以及如何對模型的結構進行優化也是需要解決的問題.

本文第1 節主要回顧目前圖數據庫以及SparQL 查詢預測的研究成果.第2 節給出本文所需的背景知識.第3 節介紹預測算法的具體流程.第4 節則是利用USEWOD 數據集對算法進行測試,并進行結果分析和討論.第5 節總結本文的主要工作和對未來工作的展望.

1 相關工作

1.1 圖數據庫

近些年,圖數據庫的發展迅速,一方面,Neo4j,OriendDB,ArangoDB 等數據庫仍然廣泛使用;另一方面,研究者們也提出了一些新的圖數據庫,如TigerGraph[8],SeQuery[9],GraphSE2[10],Graphflow[11]等,它們往往采用了不同的解決方案,從而解決不同的實際應用問題.文獻[12]分析了 Neo4j,AllegroGraph,ArangoDB,InfiniteGraph,OrientDB 等流行圖數據庫的特點,從存儲結構、易用性、性能等方面對各個數據庫做了介紹,并指出了對于圖數據庫最重要的幾個特性(靈活的結構、支持的查詢語言、分片、備份、多模型、多架構、可擴展性、云讀取),并從這幾個維度為上述圖數據庫進行了評分.文獻[13]則是比較了同一數據模型在關系數據庫和圖數據庫上的存儲,證明了圖數據庫在圖查詢和可視化上的優勢.

圖數據庫的應用也變得越來越廣泛.文獻[14]基于圖數據庫實現了一種位置圖模型,用于根據場所描述信息對其進行建模,在這個基礎上,實現了地理位置匹配、推理與查詢功能.文獻[15]則基于Neo4j 圖數據庫構建了煤礦領域的知識圖譜,同時,設計并開發了煤礦監測監控原型系統,體現了圖數據庫在知識圖譜領域的應用.文獻[16]則是以Neo4j 作為后端實現了一個圖查詢系統,并比較了Cypher,Gremlin,Java 作為查詢語言的方案,比較了幾種方案的優缺點.

1.2 SparQL查詢預測

SparQL 查詢預測指利用已有的信息對用戶接下來可能發出的SparQL 查詢進行預測,目前主要有兩種方法.(1)根據RDF 數據中的信息對SparQL 查詢進行預測;(2)根據用戶的歷史SparQL 查詢進行預測.

第1 類方法相對傳統,文獻[1]使用本體元數據的信息進行下一步的查詢預測.相比之下,文獻[2]則提出了一種新的方法,該方法使用一張預先計算好的屬性值相似表進行查詢預測.文獻[3]則利用從知識圖譜構建出的語言模型來實現查詢預測.這些方法通常預先進行信息計算,然后進行查詢預測.但是其共同點是需要從數據中獲取信息,這意味著它們構建出的方法/模型不是跨數據源可用的.因為不同的數據源信息不同,也可能存在缺失,因此這些方法存在很大的局限性.

另一類方法則是利用圖數據庫的歷史查詢日志來做查詢預測,這樣的方法具有較強的數據移植性,因為它們通常是通過分析查詢而不是數據本身.文獻[4]檢測歷史查詢中所存在的重復模式,然后使用一種自下而上的圖模式匹配算法進行查詢模板的創建,從而實現查詢預測.文獻[5]則是在此基礎上將這些查詢模板與不同的策略相結合,來進一步擴展可能的查詢,但是并沒有得到結論性的結果.一些方法使用相似性來進行查詢預測,如文獻[6]使用圖編輯距離來計算不同的SparQL 查詢之間的相似性,從而使用相似的查詢構建新的查詢;文獻[7]則利用SparQL 的三元組的主語、謂語和賓語間的相似性得到三元組的相似性,進而計算查詢的相似性,從而進行查詢預測.

第2 種方法雖然具有較好的數據移植性,但是無論是基于模板的方法還是基于相似性的方法,都只能使用歷史查詢中的相似查詢,如果查詢呈現周期性的波動,則很難進行預測.另一方面,SparQL 查詢的長度是不確定的,而這樣的方法導致新的查詢的長度必然等于這些相似的歷史查詢,因此這一問題也需要解決.

2 背景知識

本文旨在根據圖數據庫所存儲的數據以及其歷史工作負載等信息,對工作負載、數據特征等進行有效的統計,并設計合理的方案提取出相關特征;根據這些特征,進行對用戶可能的查詢的預測,從而可以對用戶需要的數據進行預加載以及進行合適的查詢優化.

為了較為方便地提取工作負載以及進行預測,本文主要研究的數據對象為關聯數據.關聯數據是語義網的主題之一,描述了通過可鏈接的URI 方式來發布、分析、連接Web 中各類資源的方法.關聯數據通常以資源描述框架(resource description framework,簡稱RDF)的形式進行描述,而查詢RDF 使用的語言是SparQL(SPARQL protocol and RDF query language).

定義1(SparQL 圖模式).一個SparQL 查詢通常可以被表示為一個圖結構,定義符號B為空白節點,I表示國際化資源標識符(internationalized resource identifier,簡稱IRI),L表示字面量,V則表示變量,那么一個SparQL圖的圖模式通常可以如下遞歸定義[17].

(1)一個有效的三元組T∈(IVB)×(IV)×(IVLB)是一個基本的圖模式(basic graph pattern,簡稱BGP),三個元素分別被稱之為主語、謂語和賓語;

(2)對于基本的圖模式BGPi和BGPj,其連接(BGPiandBGPj)也是一個BGP;

(3)如果Pi和Pj是圖模式,那么(PiandPj),(PiunionPj)以及(PioptionalPj)也是圖模式;

(4)如果Pi是一個圖模式,而Ri是一個SparQL 的內建表達式(如lang(?name)=“en”表示限定name變量的語言是英語),那么表達式(PifilterRi)是一個圖模式.

可以從數據庫中獲取用戶的若干個歷史SparQL 查詢,進而對用戶接下來的查詢進行預測.據此,給出SparQL 查詢預測問題的定義.

定義2(SparQL 查詢預測問題).符號N表示用戶查詢的個數,Q1,Q2,…,Qn表示用戶最新發出的N個連續的SparQL 查詢,Q表示用戶接下來的SparQL 查詢,則SparQL 查詢預測問題即在給定Q1,Q2,…,Qn的情況下,對Q進行預測.

此外,本文在研究中使用到了Seq2Seq 模型以及注意力機制和集束搜索,在此給出介紹.

2.1 Seq2Seq模型

本研究中將 SparQL 查詢轉化為序列,因此將問題變成了一個序列到序列的問題.而文獻[18]提出的Seq2Seq 模型通常被用以處理序列到序列的任務,Seq2Seq 模型使用兩個循環神經網絡(recurrent neural networks,簡稱RNN)[19]對序列進行處理和輸出,RNN 是一種隱藏層互相連接的神經網絡,被廣泛應用于處理序列數據,其計算流程見公式(1)、公式(2).

σh與σy分別表示隱藏層與輸出層的激活函數,W,U和b均為對應的參數,ht表示t 時刻的隱藏層狀態,yt表示t時刻的輸出.

Seq2Seq 模型則使用了兩個RNN 進行處理,分別稱之為編碼器Encoder 與解碼器Decoder.Encoder 讀取輸入信息,將學習到的信息存儲于公式(1)中計算出的隱藏層狀態ht中;Decoder 則讀取最終時刻的Encoder 的隱藏層狀態作為自己的初始隱藏層狀態,并不斷進行迭代產生輸出序列,從而完成從序列到序列的任務.

2.2 注意力機制

注意力機制希望模型對輸入具有“注意力”[20].具體地,解碼器應當在輸出的不同時間步都對編碼器的每個狀態(對應輸入序列的每個時間步)給予不同的權重,于是在每個輸出時刻,都可以通過這些不同的權重對編碼器的隱藏層信息進行加權,從而得到一個隨著時間步變化的上下文信息,該上下文信息相當于模型在當前時間步進行輸出時,關注不同的輸入而得到了不同的信息.將這些上下文信息作為對應時間步的輸入之一,增強解碼器輸出時的判斷能力.這些權重采取隨機初始化的方式,在Seq2Seq 模型訓練時不停調整,以獲取更豐富的信息.

2.3 集束搜索

集束搜索(beam search)是一種動態規劃算法[21].集束搜索只應用于Seq2Seq 模型的預測時:在當前時間步進行輸出時,不再選擇概率最高的結果進行輸出,而是保留概率最高的K個;而在下一個時間步進行輸出時,在計算概率時不再單純計算輸出某個元素的概率,而是計算從第1 個時間步到當前時間步的所有輸出形成的輸出序列的聯合概率,從而可以根據聯合概率對當前時間步的輸出進行排序,同樣地,再次保留概率最高的K個作為當前時間步的輸出給予下一個時間步使用.

使用集束搜索機制,一方面可以降低單個時間步預測出錯時所帶來的誤差,因此可能在下一個時間步正確的輸出會獲得更高的概率;另一方面,在每個時間步都計算整體的輸出序列的概率而不是單個時間步的輸出元素的概率,更好地考慮了序列元素之間的相關性.

3 SparQL 查詢預測算法

本研究從圖數據庫的工作日志中提取出用戶的SparQL 查詢信息,然后進行查詢預測.這樣做的優點是具有跨數據的移植性,即使更換了數據源仍然適用.已有的這類研究通常使用圖匹配或者相似度的方法,這意味著用戶過去的歷史查詢需要保持相似,當其發生周期性的變化時,無論是圖匹配還是相似度,都無法找到這種周期性的規律;另一方面,基于相似度的方法通常利用歷史查詢中相似的三元組構建預測查詢中的三元組,而沒有利用到三元組之間的信息.

本文提出的基于Seq2Seq 模型的SparQL 查詢預測算法將定義1 中的圖模式轉化為序列,利用Seq2Seq 模型挖掘序列內部元素的關聯性,保證利用了三元組之間的信息;同時,將若干個歷史查詢連接為同一個序列,從而使得模型可以學習到查詢間的規律性,降低了對于查詢連續相似的依賴.

想要從序列中學習到豐富的信息,那么就需要將文本形式的SparQL 查詢轉化為可計算的特征向量,這部分將在第3.1 節中介紹;在得到特征向量之后,如何利用Seq2Seq 模型進行查詢預測以及如何進行模型優化將在第3.2 節中介紹.

3.1 特征轉化

3.1.1 特征轉化的要求

從查詢轉化到的特征向量將用于查詢預測任務,因此對特征向量的要求較高,也是本文著重解決的問題,具體地,特征轉化的要求主要有如下幾點.

(1)信息完備性

所得到的特征應當盡可能地囊括原始數據,也就是SparQL 圖模式中所蘊含的信息,要能夠恰好地表達出三元組所包含的信息的同時,也要能夠表達三元組間的聯系,不可以將三元組獨立拆分,這也是現有的大多數方法所不具備的.

(2)還原性

一些提取SparQL 特征向量的工作,如文獻[22],將SparQL 查詢轉化為語法樹的形式,然后通過將其中的一些關鍵信息(如UNION 操作的個數等)進行記錄,然后轉化為特征向量.但這樣所得到的特征向量并不具備還原性,即無法從特征向量還原到SparQL 查詢或者圖模式,那么就無法進行查詢的相關預測.因此,對特征轉化的要求包括需要能夠從特征向量轉化為SparQL 圖模式,從而判斷查詢預測的準確性等.

(3)泛化能力

查詢預測是根據用戶的歷史查詢去預測用戶下一步的查詢,而事實上,用戶下一步的查詢中可能會出現歷史查詢中所沒有出現過的變量或其他信息,因此在提取特征時,便不能過度依賴于三元組字段的內容本身,否則當用戶發出新的陌生的SparQL 查詢時將無法轉化,故泛化能力是指需要能夠預測訓練時歷史查詢中所不包含的三元組或變量等信息.

3.1.2 特征轉化的設計思想

基于第3.1.1 節中所列出的3 點要求,本文將通過如下的設計思想進行特征轉化方案的設計.

(1)將三元組視為整體,查詢視為一個序列

三元組包括由主語、謂語和賓語構成,而這三者之間往往存在一定聯系,如果將三元組的信息拆分進行表示,那么將會破壞其整體性,無法較好地表達其三元組本身的信息,因此需要將三元組視為一個整體進行對待.其次則是將查詢整體視為序列,從而包含三元組之間的關聯.如果以符號T表示三元組,那么一個SaprQL 查詢的圖模式部分的例子通常類似于:“{{T1T2T3} UNION {{T4T5} AND {T6}} OPTIONAL {T7}}”.從這個例子中可以看到:除了三元組之外,圖模式中還包括了UNION,AND 和OPTIONAL 這類SparQL 操作符以及括號等符號.事實上,無論是三元組還是這些操作符,都在圖模式中表達著SparQL 的語義信息,甚至于左右大括號這類符號也傳遞著嵌套信息等語義信息.因此,若想要完整的表示SparQL 圖模式,就必須將所有的這些語義信息進行盡可能地充分的表達.因此,本文借鑒了自然語言處理領域對于類似信息的處理方式,將SparQL 圖模式視為一個符號序列,無論是三元組還是操作符,抑或是括號等其他符號,均視為該符號序列中的一部分進行單獨表示,從而將整個序列的語義信息進行充分的表達,也能使三元組之間的聯系信息存儲在序列之中.

(2)以位置信息表達三元組

本研究使用一組查詢中“第N個三元組”的形式定義三元組的編號,即:其在序列中的位置決定了其編號,而不是使用內容信息.如果以三元組本身的內容進行信息表達,那么對于未知內容的三元組,則無法提前了解其信息,也就無法進行表達了,故而這種方法將不再具有泛化能力.本文的這種形式判斷三元組在這一組查詢中所出現的次序,以此進行三元組的編號,在已經使用序列表達整個SparQL 圖模式的情況下,對于相似的序列模式,其所包含的三元組的位置信息也是相似的,即使在用戶的新查詢中包含了訓練時未曾出現過的三元組,但是其位置信息往往已經出現過,從而可以以位置信息匹配曾經出現過的模式.

另一方面,這樣做帶來的更大好處是可以避免產生內容偏好,即不同用戶所發出的SparQL 查詢在內容上是不同的,而內容上的不同并不能稱之為一個有用的信息,因為往往不同用戶所發出的查詢可能形式是相同的,但是內容完全不同,使用內容表達會減少所能學習到的信息,而使用位置信息表達則可以很好地解決這一問題.

(3)對三元組使用等價類劃分

以三元組“?sub rdf:person_name“kaily”@en”和“?sub rdf:person_name“jack”@en”為例,這兩個三元組均是為了查詢特定姓名的實體,其差異僅僅在于謂語不同.事實上,在大量觀察數據記錄后,可以發現這樣的情況占據大多數,有時不同的SparQL 圖模式的差異僅僅在于這類三元組的差異,而字面量的變化對于模型或者算法的意義是不大的,這并不能成為有效的信息.因此,本文對三元組進行等價類的劃分以解決該問題,這里給出等價三元組的定義.

定義3(三元組等價類).對于三元組A與三元組B,若A與B的主語和謂語字段均相同,而A與B的賓語字段不同,且A與B的賓語字段均為字面量(以字符串表達的值),則稱A與B是等價的三元組.

一方面,等價的三元組可以查詢到所有這一類三元組的信息,從而減少模型或者算法所需要學習的冗余信息;另一方面,這樣的處理方式同樣可以降低訓練時未出現的三元組所帶來的影響,因為它們通常也可以被歸納為某個等價類三元組.

3.1.3 特征轉化的具體流程

基于第3.1.1 節中的要求以及第3.1.2 節中特征轉化的設計思想,現給出特征轉化的具體流程.

對于一個SparQL 查詢的圖模式,將其視為一個序列,序列中的每個元素均使用One-Hot(即對于一個D維向量,使用第K維為1 且其他維均為0 的方式表示數字K)的形式進行表示,因此需要定義該向量的長度.

使用符號HIS_LEN表示預測時使用的歷史查詢的個數,則HIS_LEN+1 個查詢為一組數據(最后一個為要預測的查詢),并定義在一組SparQL 查詢的圖模式中最多可能出現的三元組的數量為MAX_TRIPLE,而除了三元組之外,還需要被轉化的符號和操作符總共有7 個,分別為AND、UNION、OPTIONAL、{、}、起始符號Start和結束符號End,其中,Start 和End 分別用于表示一個序列的起始和結束,從而方便算法或者模型進行預測.

由此,序列中的每個元素所對應的是一個(MAX_TRIPLE+7)維的One-Hot 形式的向量,以上7 個符號分別定義為0～6,三元組則按照這組查詢中的“第N個三元組”的形式以數字N+7 所對應的One-Hot 向量進行表示.算法1 為單個元素轉化的具體流程偽代碼.

算法1.特征轉化的流程.

輸入:queries查詢的數組;

輸出:vectors查詢數組對應的向量數組.

算法使用querySet數組控制等價的三元組,第10 行～第16 行中,對于每個三元組,算法首先尋找是否已經存在相同的或者等價的三元組,如果有則使用其索引,否則才創建新的索引;第6 行～第8 行中,對于一般符號的處理,則是直接使用查表法尋找對應的索引,將One-Hot 向量的對應位置置1.假設查詢序列的平均長度為m,總共有n個查詢,算法對于每個查詢僅遍歷其序列一次,因此算法的時間復雜度為O(nm).

對于一個SparQL 圖模式對應的序列中的所有元素,均采取上面的方式進行轉化,最終可以得到一個長度不定的One-Hot 向量序列,作為特征提取階段的最終產出.

3.2 查詢預測

查詢預測階段使用Seq2Seq 模型對第3.1 節中所提取到的特征向量進行學習,但直接將One-Hot 向量序列輸入進模型的方法并不合理,因為One-Hot 向量只能簡單地表達類別信息,其維度較低,而低維語義空間所蘊含的語義信息顯然不如高維空間豐富.如果能夠將這一低維度的One-Hot 向量映射為一個高維向量,那么特征向量可以借助高維的語義空間向Seq2Seq 模型提供更加豐富的語義信息.

具體地,定義新的維度為D,D通常要比MAX_TRIPLE大很多,如1 024,太大的數字可能會導致內存等資源不足,因此需要權衡.在初始化Seq2Seq 模型時,設置一個映射函數,將所有MAX_TRIPLE+7 種向量映射為一個D維的高維向量.對于這些高維向量的設定,采取類似于編碼器隱藏層初始狀態的處理方式,即對其進行隨機初始化,因為人為地指定這樣的維度的內容是近似于不可能的,因此這些向量設定為可訓練的.在Seq2Seq 模型的訓練過程中,不斷地根據反向傳播調整這些向量,這樣也可以使得那些表示三元組的向量更具位置上的語義性.

通過特征向量升維,可以大幅提升Seq2Seq 模型能夠從輸入中學習到的信息,從而提高模型的預測能力.

另一方面,在預測用戶的下一步可能發出的查詢時,通常要使用到不止一個歷史查詢,而單個SparQL 圖模式轉化得到的序列長度通常在30～50 左右,這意味著輸入的序列的長度是較高的.另一方面,輸出時模型也不應當考慮到輸入序列的所有內容,譬如在輸出某個三元組時,模型在這一時刻應當關注于輸入序列中同樣是三元組的那些信息而不是操作符等符號,因為輸入序列中的三元組更能在輸出三元組時表達更多的信息.因此,本文為Seq2Seq 模型引入了第2.2 節中的注意力機制,強調不同的輸出時刻對輸入給予不同的權重.

此外,為了降低單個時間步預測出錯的影響,利用整體序列的概率替代單個預測的概率.本文在此基礎之上再引入了第2.3 節中的集束搜索機制,對Seq2Seq 模型進行優化.

以簡單SparQL 查詢的圖模式“{T1UNIONT2}”為樣例輸入(即只使用一個歷史查詢),假定輸出為“{T3UNIONT4}”,圖1 表示了該模型的工作流程,其中,〈start〉和〈eos〉分別表示起始符號Start 與結束符號End 對應的One-Hot 向量在使用特征升維后對應的向量.

Fig.1 Process of query prediction using Seq2Seq model圖1 使用Seq2Seq 模型進行查詢預測的流程

編碼器接受不定長的輸入,并維護編碼器狀態.編碼器狀態即保存了輸入序列中的信息,當輸入處理完畢之后,此時編碼器的狀態作為解碼器的初始狀態,解碼器讀取狀態中的信息,并開始產生預測序列.

現有的基于歷史查詢進行預測的算法通常對歷史查詢的要求較高,如果歷史查詢并不連續相似,則無法匹配到相應的圖模式,也無法利用查詢間的相似度進行判斷.而實際上,真實的數據中有些用戶的查詢是呈現周期性波動的.本文使用Seq2Seq 模型不僅利用到了查詢內三元組間的信息,還利用到了不同查詢間的信息,即使歷史查詢并不相似,也可以捕獲到查詢間的聯系,從而提升了預測任務的準確率;另一方面,模型可以判斷輸出的停止時間,因此可以輸出不定長度的序列.

4 實驗結果與分析

4.1 USEWOD數據集

本文使用了USEWOD2016 數據集,該數據集存儲了DBPedia 等知識庫的SparQL 查詢日志,其中記錄了用戶在DBPedia 的SparQL 查詢接口中所發出的SparQL 查詢以及用戶ID 和發出查詢的時間.

圖2 為USEWOD2016 數據集中的內容示例,圖中共3 項數據記錄,每一行的第1 個字段為用戶的ID,可以看到,這3 條查詢請求均來自于同一用戶;第2 個字段則是時間字段,表明用戶發出該查詢的具體時間;時間字段之后則是用戶通過Web 客戶端所發出的SparQL 查詢的HTTP 請求格式,記錄了用戶所發出的SparQL 查詢的相關信息.

Fig.2 Example of USEWOD2016 dataset圖2 USEWOD2016 數據集示例

4.2 評價指標

為了更加全面地評價算法的預測效果,本文定義3 個指標對預測結果進行評價.

(1)完全預測準確率

該指標作為最嚴格的評價指標,即當且僅當算法所做出的預測與用戶所發出的真實預測完全相同(序列長度相同且內容相同)時,視為模型的預測是完全正確的,完全預測準確率則等于完全預測正確的數據量與所有數據量的比例.

(2)完全緩存命中率

本文進行查詢預測的目的是為了提前對數據進行預加載,即做預緩存,那么數據的緩存命中率也是重要的評價指標.因此,本文定義:若用戶的查詢中的三元組均被算法預測的查詢所覆蓋,則視為完全命中緩存,完全緩存命中率則等于完全命中緩存的數據量與所有數據量的比例.

(3)平均緩存百分比

即使沒有完全命中緩存,對其中一部分數據進行預加載也能夠提高數據庫對于用戶所發出查詢請求的響應速度,因此,該評價指標計算用戶的查詢中的三元組被算法預測的查詢所覆蓋的比例,并在所有數據中計算該比例的平均值.

使用以上3 個指標,可以更全面地評價算法的預測效果.

4.3 實驗設計

首先給定本文在實驗中設定的一些參數,MAX_TRIPLE值設定為32,因此One-Hot 向量的維度為39,特征向量升維后的維度D為1 024,循環神經網絡的隱藏狀態層的維度為1 024,集束搜索的搜索個數K為5.除此之外,在一些方面設計了對比實驗,具體如下:

(1)歷史查詢個數,觀察使用的歷史查詢個數對算法結果的影響;

(2)注意力機制,觀察注意力機制的是否使用對算法結果的影響;

(3)集束搜索,觀察集束搜索的是否使用對算法結果的影響.

4.4 實驗結果與分析

(1)關于歷史查詢個數的實驗

在關于歷史查詢個數的對比實驗中,HIS_LEN參數分別被設定為1～5,訓練數據設定為60 822 組,注意力機制被使用,不使用集束搜索方法,測試數據設定為3 000 組,圖3 表明了歷史查詢個數對實驗結果的影響,其中,橫軸為HIS_LEN參數,縱軸為3 個評價指標的數值,實線、虛線、點狀線分別對應第5.2 節中的評價指標(1)～(3).

Fig.3 Impact of the number of historical queries on results圖3 歷史查詢個數對實驗結果的影響

可以看到:3 個評價指標的變化趨勢是基本相同的;并且指標的評價標準越嚴格的情況下,其數值則越低.值得注意的是:當歷史查詢個數的值為3 個的時候,準確率(這里準確率指代所有指標)達到極值;并且當歷史查詢個數由2 變為3 時,準確率的提升小于由1 變為2 時的提升;而當歷史查詢個數變得更多時,準確率開始下降.這是因為雖然循環神經網絡主要是用以處理不定長的序列數據,但是其處理長期依賴的能力也是有限的,較長的輸入序列仍然會使得循環神經網絡的記憶能力降低.當歷史查詢個數為3 時,Seq2Seq 模型所處理的輸入序列的總長度可以達到150,這幾乎已經快超出了循環神經網絡的處理能力,因此當歷史查詢個數再次增加,輸入序列的總長度再次增加時,Seq2Seq 模型陷入了欠擬合的狀態,因此準確率開始下降.而當歷史查詢個數較低時,特別是當歷史查詢個數只有一個時,對于模型來說,此時其是無法從歷史查詢中判斷該段序列中所存在的模式與規律的,輸入序列所帶來的信息太少,因此準確率要比歷史查詢個數較多時更低一些.因此在本文的實驗中,歷史查詢個數為3 是最為合適的值.

(2)關于注意力機制的實驗

在關于注意力機制的對比實驗中,HIS_LEN參數分別被設定為1～5,訓練數據設定為60 822 組,不使用集束搜索方法,測試數據設定為3 000 組,圖4 表明了注意力機制對實驗結果的影響,其中,橫軸為HIS_LEN參數,縱軸為3 個評價指標的數值,圖4(a)～圖4(c)分別對應第5.2 節中的評價指標(1)～(3),實線為使用注意力機制,虛線為未使用注意力機制.

Fig.4 Impact of attention mechanism on results圖4 注意力機制對結果的影響

可以看到,3 組曲線的變化趨勢與對比基本是相同的.在不使用注意力機制的情況下,3 種評價指標均有不同幅度的下降,表明注意力機制能夠提升模型的預測效果.此外,當歷史查詢個數較低,尤其是只有一個的時候,注意力機制對于準確率的提升并不大.這是因為此時輸入中只有一個歷史查詢,輸入信息較少,注意力機制并不能發揮其效果,在不同時刻關注不同的輸入,因此對于模型沒有太多的提升;而在歷史查詢個數較多的時候,模型準確率的下降也得到了一定的改善,因為注意力機制可以使得模型從較多的查詢序列中關注其中更有價值的信息,從而提升預測的效果.

(3)關于集束搜索的實驗

在關于集束搜索的對比實驗中,HIS_LEN參數分別被設定為1～5,訓練數據設定為60 822 組,注意力機制被使用,測試數據設定為3 000 組.圖5 表明了歷史查詢個數對實驗結果的影響,其中,橫軸為HIS_LEN參數,縱軸為3 個評價指標的數值,圖5(a)～圖5(c)分別對應第5.2 節中的評價指標(1)～(3),實線為使用集束搜索,虛線為未使用集束搜索.

相比注意力機制,集束搜索對于模型準確率的提升更為明顯一些.當歷史查詢個數增大到3 以上時,準確率的下降明顯變緩.因為即使某個時刻的預測是出錯的,正確的輸出也可能屬于概率較高的輸出之一而被集束搜索所保留,并在下一時刻通過整體的序列的概率再次利用到正確的輸出進行判斷.這使得即使模型因為序列長度的提升降低了記憶能力,但仍然通過這種機制羅列出模型學習到的各種序列模式,并挑選出概率最高的序列進行輸出.因此,集束搜索能夠較好地提升歷史查詢個數較多時候的效果.但歷史查詢個數較少時,整體序列的特點并未被模型所過多地學習,因此集束搜索機制也無法使得這種情況下的正確率變得較高.

Fig.5 Impact of beam search on results圖5 集束搜索對結果的影響

綜合以上3 組實驗可以發現:在已有的實驗參數下,最合適的歷史查詢個數為3.注意力機制與集束搜索均被使用,本文測定了此設定下的指標,完全預測準確率達到77.3%,完全緩存命中率達到80.1%,平均緩存百分比達到82.5%,總體達到了較為不錯的水平.

5 結 論

本文從RDF 圖數據庫的查詢日志中提取出SparQL 查詢,并進一步將SparQL 查詢提取為SparQL 圖模式,進行可還原的特征轉化,得到了蘊含豐富信息的特征向量.為了能夠從特征向量里充分挖掘序列之間的關聯性,本文使用了Seq2Seq 模型進行SparQL 圖模式的預測,Seq2Seq 模型可以處理不定長的輸入與輸出.在此基礎上,利用注意力機制與集束搜索對模型進行優化,使得模型的完全預測準確率達到77.3%,完全緩存命中率達到80.1%,平均緩存百分比達到82.5%.

本文所使用的方法一方面避免了收集數據源的信息,從而使得方法具有跨數據移植性,并且利用位置信息代替內容信息之后,也使得該方法不會因為查詢的數據不同而失效,因此具有良好的跨數據移植性;另一方面,使用Seq2Seq 模型充分挖掘了數據間的關聯性與規律,因此即使用戶的SparQL 查詢呈現周期性變化,也可以進行預測,此外也利用了循環神經網絡的特性,較好地解決了SparQL 查詢長度不確定的問題.

本文現有的工作中,所進行特征轉化的主要是SparQL 圖模式中的三元組以及UNION,AND 和OPTIONAL操作符.實際上,SparQL 查詢中還存在FILTER,LIMIT 等操作符,這些操作符是對數據的進一步過濾,與UNION,AND 等操作符的語義信息不同,且這些操作符以及其攜帶的表達式信息在轉化時很難保持還原性.因此,未來的工作將重點研究如何對這些操作符進行特征轉化;另一方面,由于將SparQL 圖模式視為了一個序列,那么序列中括號等操作符所表達的嵌套信息就必須被正確呈現,這也是未來研究工作中的重點.

此外,除了用于查詢圖數據庫的SparQL,查詢傳統關系數據庫的SQL 語言也具有與SparQL 類似的特征,如果同樣以位置信息記錄SQL 中的字段信息,同時將SQL 中的AND,HAVING 等操作符進行特征轉化,那么本文提到的方法也可以適用于SQL 語言,這也是未來會進行的工作.