黃濤貽，李 優(yōu)，宋 浩，林煜明

1.桂林電子科技大學 廣西可信軟件重點實驗室，廣西 桂林 541004

2.桂林電子科技大學 廣西自動檢測技術與儀器重點實驗室，廣西 桂林 541004

1 引言

隨著Web技術的不斷發(fā)展，互聯(lián)網(wǎng)正由以人與人互聯(lián)為主要特征的Web2.0 時代邁向基于知識互聯(lián)的Web3.0時代[1]，其目標是實現(xiàn)人和機器都可以理解的互聯(lián)網(wǎng)，使網(wǎng)絡更加智能化。在這種背景下，如何將Web上的海量數(shù)據(jù)知識化并進行高效的管理，使之為用戶提供更高質量的信息服務，這已經(jīng)成為學術界和工業(yè)界共同關注的熱點問題。2012 年谷歌率先推出知識圖譜，并以此作為增強其搜索功能的輔助知識庫，構建下一代智能化的搜索引擎。隨后，各種類型的知識圖譜陸續(xù)推出，例如基于維基百科的YAGO[2-4]、DBpedia[5]和Freebase[6]等。

與此同時，網(wǎng)絡上商品相關的數(shù)據(jù)也在急劇增長，而上層應用/用戶對商品信息準確獲取的需求卻難以滿足。這兩者間的矛盾不但沒有得到緩解，而且存在日趨嚴重的態(tài)勢。造成該矛盾的主要原因一方面是絕大部分承載商品信息的數(shù)據(jù)均以無結構的形式存在，嚴重地限制了它們自動化和智能化的應用；另一方面，這些大規(guī)模的信息缺少高效的數(shù)據(jù)管理機制，導致用戶直接面對碎片化和高冗余的信息，進一步加劇了信息過載的問題。對Web 上包含商品信息的海量數(shù)據(jù)進行知識化和結構化處理，并實現(xiàn)統(tǒng)一、高效的管理不僅能有效地解決該矛盾，而且能向用戶提供更全面和更準確的信息服務[7-8]。如何高效地檢索大規(guī)模商品知識成為一個重要的問題。已有許多知識檢索系統(tǒng)支持大規(guī)模知識圖譜，如 SW-store[9-10]、RDF-3x[11-13]、Hexastore[14]和 gStore[15-17]等。它們在存儲數(shù)據(jù)時，通過映射字典將知識圖譜中URI（Uniform Resource Identifier，統(tǒng)一資源標識符）文本轉換為ID 值，從而降低數(shù)據(jù)存儲和查詢的代價。基于圖模型的知識檢索系統(tǒng)，如gStore，能夠利用知識圖譜的圖結構特性處理知識檢索，具有較高的查詢效率。

當處理大規(guī)模查詢時，大量文本需要轉換成對應的ID值，這導致頻繁地訪問映射字典，此時映射字典的時間代價不能忽略。另外基于圖模型的檢索系統(tǒng)在處理商品知識查詢時，無法充分利用商品知識圖譜的結構特征，導致在進行商品觀點知識查詢時性能低，無法滿足商品知識檢索性能的要求。本文圍繞上述問題展開研究，主要貢獻如下：

（1）提出了一種融合客觀與主觀知識的商品知識圖譜框架，實現(xiàn)對商品客觀信息與用戶觀點信息統(tǒng)一組織。

（2）提出了一種結合學習索引[18]的映射字典，提高映射字典的查詢速度，并利用前綴樹進一步減少檢索時間，實驗證明該方法提高了映射字典檢索效率。

（3）提出了一種商品屬性觀點變量組合策略，該方法基于商品知識圖譜的結構特點，實驗證明該方法有效降低了商品知識檢索的時間。

2 相關工作

已有基于單機的RDF 數(shù)據(jù)存儲與查詢可以分為2大類，分別為基于關系模型和基于圖模型?；陉P系模型的方式是利用成熟的關系型數(shù)據(jù)庫進行管理，從而實現(xiàn)知識存儲與查詢的功能。例如三列表構建具有3 個列屬性的表，并將RDF三元組數(shù)據(jù)直接插入到表中，雖然這種方式實現(xiàn)簡單，但處理復雜查詢時包含大量自連接操作。水平表將RDF數(shù)據(jù)中所有的屬性都作為表的列屬性，避免了自連接操作，但導致存在大量的空值。屬性表[19]通過對屬性聚類從而減少空值的產(chǎn)生，但是聚類是需要交給數(shù)據(jù)專家進行，當數(shù)據(jù)更新時，可能需要重新聚類，造成巨大的表的維護代價。垂直切分[9-10]為每個屬性構建一張兩列表，分別存儲主語與賓語，RDF三元組按照屬性歸類，并存儲在對應的表中，具有良好的性能，但當屬性為變量時，需要遍歷所有的表，導致性能急劇下降。全排列索引[11-14]是對RDF 三元組中元素進行全排列組合并構建索引，解決了垂直劃分查詢屬性效率低的問題，但存儲空間代價較高。

基于圖模型的方式是利用RDF數(shù)據(jù)轉換成的數(shù)據(jù)圖，與基于關系模型的方式不同，其能夠保留原有的圖結構。知識查詢將轉換為子圖匹配問題[15]。圖劃分[20-21]將圖劃分成若干子圖，對每個子圖包含的節(jié)點構建了布隆過濾器（bloom filter）。GRIN[22]用節(jié)點之間的距離采用聚類的方法對圖進行劃分，然后根據(jù)每個聚類的中心節(jié)點和半徑構建樹狀索引。gStore 中對每個實體節(jié)點進行簽名（Signature）編碼，構建基于二進制的簽名圖（Signature Graph），并在此基礎上建立VS-tree 索引，減少搜索空間。

總的來說，基于關系模式的方式破壞了RDF 數(shù)據(jù)原有的圖結構，導致額外的存儲或查詢代價。而基于圖模型的方法能有效保存RDF 數(shù)據(jù)的圖結構，提供較好的查詢性能，但依賴數(shù)據(jù)的圖結構，現(xiàn)有方法檢索商品知識時性能較低。

3 大規(guī)模商品知識的組織

3.1 整體框架概況

商品知識圖譜輔助用戶提供基于知識的檢索功能，因此該框架應該與在線購物平臺數(shù)據(jù)結構保持一致，其概要結構如圖1所示。

圖1 商品知識圖譜框架

商品知識圖譜總共分為5層，其中最上面兩層為客觀知識，剩下的三層為主觀知識，每層包含的知識分別如下：

（1）商品分類層。在線商城通過對商品進行分類并構建分類樹實現(xiàn)對大規(guī)模商品的管理，潛在消費者則可以通過商品分類進行目錄式檢索商品。

（2）商品實例層。這一層主要包含商品實例，以及在線購物平臺提供的客觀信息，例如商品名稱、品牌、價格以及網(wǎng)站提供的商品屬性等。

（3）商品屬性層。這一層主要包括商品的屬性，這里的屬性不是平臺提供的屬性，而是用戶評論中觀點描述的屬性。

（4）觀點層。觀點層主要包含了用戶發(fā)表的觀點信息，包括對商品或商品屬性的觀點。

（5）用戶層。用戶層包含了平臺的注冊用戶，是在平臺上進行消費和發(fā)表觀點的主體。

3.2 商品客觀知識

商品客觀知識主要是網(wǎng)站提供的客觀信息，包括商品分類信息和商品信息。首先，針對客觀知識定義如表1所示的類型。

表1 客觀知識類型

當表示客觀知識時，所需用到的屬性如表2所示。

表2 客觀知識屬性

例如在亞馬遜購物平臺中，亞馬遜網(wǎng)站擁有一個electronics（電子產(chǎn)品）商品分類，headphones（耳機）也是一個商品分類，是electronics 的子分類，商品編號為B0753GRNQZ 的商品屬于headphones 商品分類，對應RDF數(shù)據(jù)圖如圖2所示。

圖2 商品客觀知識樣例

3.3 用戶評論主觀知識

用戶評論主觀知識主要為用戶對商品的屬性表達的觀點，即從評論中抽取的商品屬性-用戶觀點詞對。用戶評論主觀知識是一種多元關系，涉及到用戶、商品和商品屬性，然而RDF 三元組不能直接表示多元關系。解決該問題的方法是引入中介節(jié)點，通過中介節(jié)點從而表達多元關系。由于用戶的觀點是包含于用戶所撰寫的評論中，因此將用戶評論作為中介節(jié)點，從而實現(xiàn)表示用戶評論主觀知識。表示主觀知識將引入如下的類型，其定義如表3所示。

表3 主觀知識類型

表示主觀知識時，所需要的屬性如表4所示。

表4 主觀知識屬性

例如用戶A001307232 認為商品B0753GRNQZ 的尺寸好，利用RDF數(shù)據(jù)圖表示如圖3所示。其中用戶發(fā)表的觀點都作為opinion的子屬性，例子中用戶觀點good（好）可以通過三元組表示成。

圖3 商品主觀知識樣例

4 學習映射字典

當同時處理大規(guī)模查詢時，大量URI文本需要通過映射字典轉換為對應的ID值。傳統(tǒng)的映射字典使用B-tree，但隨著映射字典規(guī)模的增大，其查詢效率逐漸降低。學習映射字典結合學習索引技術，基于數(shù)據(jù)的分布利用機器學習模型對數(shù)據(jù)分片，從而提升查詢效率。

4.1 學習索引

學習索引是將傳統(tǒng)索引結合機器學習技術，通過對數(shù)據(jù)的分布進行訓練，得到符合數(shù)據(jù)分布的模型，從而將傳統(tǒng)索引對數(shù)據(jù)的查詢轉換為模型對數(shù)據(jù)位置的預測，而查詢時間也轉換成機器學習模型的執(zhí)行時間。同時隨著GPU、TPU和FPGA等高性能計算硬件的發(fā)展和廣泛應用于復雜計算中，同時在機器學習領域也被用于提升模型的執(zhí)行效率，從而有效降低檢索的時間成本。

4.2 文本分布

構建URI文本的學習映射字典，首先需要明確文本的分布。文本是一種復合數(shù)據(jù)類型，是由多個字符組合構成，可以通過ASCII 編碼轉換成一個一維整形數(shù)組，如圖4所示。

圖4 文本通過ASCII編碼轉換成數(shù)組

商品知識圖譜中所有URI 文本排序構成一個有序集合U={u1,u2,…,uM}，每個 URI 文本ui通過 ASCII編碼轉換成數(shù)組xi。數(shù)組xi取前N個元素，對于數(shù)組長度n＜N的，設置=0(j＞n)，最終得到數(shù)組集合XN={x1,x2,…,xm} 。對URI文本集合U轉換的XN，構建累積分布函數(shù)如式（1）所示：

4.3 學習映射字典結構

學習映射字典分為兩個層，第一層包含機器學習模型，第二層包含了B-tree，URI文本集合通過第一層機器學習模型將數(shù)據(jù)分片，每一個數(shù)據(jù)分片使用B-tree 保存，其結構如圖5所示。

圖5 學習映射字典結構

第一層是機器學習模型。首先將URI文本集U通過ASCII編碼轉換成數(shù)組集合XN，使用神經(jīng)網(wǎng)絡對文本分布進行訓練，最終得到學習模型P(x)，該模型實現(xiàn)預測URI文本ui在數(shù)據(jù)集U中的位置p。為了降低神經(jīng)網(wǎng)絡在查詢時執(zhí)行的時間代價，這里采用單隱層全連接神經(jīng)網(wǎng)絡，如圖6所示，其輸入層神經(jīng)單元數(shù)量為N，輸出值為p。

圖6 單隱層全連接神經(jīng)網(wǎng)絡

URI 文本ui在數(shù)據(jù)集U中的位置不可能為負數(shù)，同時取值跨度廣，因此，需要激活函數(shù)具有較廣的輸出范圍并且避免預測值p≤0 ，所以神經(jīng)網(wǎng)絡模型采用ReLu函數(shù)作為激活函數(shù)，如式（2）所示：

訓練模型時，利用URI 文本ui在數(shù)據(jù)集U中真實位置y與模型預測位置p之間的誤差值，采用方差作為損失函數(shù)，如式（3）所示：

第二層包含多棵B-tree。理想狀態(tài)下，第一層的模型能正確預測ui在文本集中的位置，但數(shù)據(jù)的復雜性導致預測位置與真實的位置仍存在較大的誤差，因此基于第一層預測位置，設置閾值s，將數(shù)據(jù)切分，即當(h-1) ?s≤P(xi)＜h?s時，將ui保存到第h個數(shù)據(jù)分片，每個分片分別使用B-tree保存。

4.4 URI文本壓縮

商品知識圖譜中完整的URI文本較長，如表5展示了商品知識圖譜中部分類型實體對應的完整URI 文本。其中，商品類型實體的URI文本包含了41個字符，前面30個字符用于表示命名空間。當神經(jīng)網(wǎng)絡輸入層的神經(jīng)單元數(shù)量N≤30 時，對于神經(jīng)網(wǎng)絡模型，所有商品類型的URI將會是一樣的，所以輸入層的神經(jīng)單元的數(shù)量至少需要N＞30。在商品知識圖譜中，命名空間作為完整URI 的前綴，其種類較少并且固定，但文本長度普遍較長，導致神經(jīng)網(wǎng)絡模型需要更多的輸入節(jié)點，這造成神經(jīng)網(wǎng)絡模型的執(zhí)行效率降低。

表5 部分類型實體對應的完整URI文本樣例

為了提高機器學習模型的執(zhí)行效率，利用前綴樹對URI文本中冗余的前綴進行壓縮，減少神經(jīng)網(wǎng)絡模型輸入層的神經(jīng)單元的數(shù)量N。URI文本的前綴為命名空間，其通常使用斜杠（/）符號表示命名空間的目錄或分類層級，因此利用斜杠符號對URI 命名空間分割，然后構建前綴樹，圖7 展示了命名空間壓縮前綴樹的結構。該結構中，圓形表示前綴樹的節(jié)點，內(nèi)部的數(shù)字為節(jié)點對應的編號，邊的標簽對應命名空間分割后得到的文本子串。

圖7 命名空間壓縮前綴樹

通過前綴樹壓縮后，表5中完整的URI文本將轉換成如表6 所示，相比完整的URI 文本，壓縮后的URI 文本長度較短，減少了神經(jīng)網(wǎng)絡輸入層神經(jīng)單元數(shù)量N，這有效降低了學習映射字典第一層神經(jīng)網(wǎng)絡模型的執(zhí)行時間代價。

表6 部分類型實體壓縮后的URI文本樣例

5 商品知識查詢優(yōu)化

5.1 連接代價

每個變量在獲得候選值集合后，需要根據(jù)查詢圖的結構對變量進行連接操作。連接一個變量的過程在算法1 中給出，其中IRT表示中間結果集，即已連接變量所構成的子圖的結果集合。

算法1連接一個變量節(jié)點算法

輸入：SPARQL查詢圖Q，當前中間結果表IRT，需要連接的變量節(jié)點v；

輸出：連接變量節(jié)點v后的中間結果表nIRT；

1.設置新的中間結果集nIRT為空，即nIRT=φ；

2.if變量節(jié)點v的候選集為空then

3.returnnIRT；

4.forIRT中每條中間結果記錄rdo

5.設置臨時表格tmp為空，即tmp=φ；

6.for中間結果記錄r中每個元素edo

7.ife對應Q中變量節(jié)點v′與v之間沒有邊相連then

8.continue；

9.通過e獲取v的另一個候選集list；

10.iftmp為空then

11.list與v的候選集進行交集操作，并賦予tmp；

12.else

13.list與tmp進行交集操作，并將結果賦予tmp；

14.fortmp中所有的元素edo

15.創(chuàng)建r副本r′，將e添加到r′；

16.r′添加到nIRT；

17.returnnIRT；

連接操作的時間代價主要由兩部分組成：交集操作代價和I/O 代價。其中交集操作受到列表的大小影響，在執(zhí)行前難以預測其代價。I/O 代價是訪問磁盤操作造成的，由于磁盤的訪問速度比內(nèi)存慢幾個數(shù)量級，當頻繁訪問磁盤時會造成巨大的I/O 代價。這導致I/O代價成為連接操作代價的絕大部分，因此連接代價基本可以由I/O 代價決定。在算法中連接一個變量所造成的I/O代價由中間結果集IRT的大小決定，因此查詢圖連接的總代價可以由每一步連接操作時中間結果集IRT的大小共同決定。對查詢圖包含節(jié)點集合V={v1,v2,…,vn}和邊集合E={e1,e2,…,em}，假設每次只連接一條邊，其連接的總代價cost如式（4）所示，其中Si表示進行第i步連接時中間結果集IRT的大小和第i步的代價。

5.2 連接順序

第i步連接的代價Si是第i-1 步連接完成所得到，每步連接操作的代價都是由其前序連接操作得到，因此不同的連接順序會造成得到不同的連接代價，這里針對表7所示的商品知識數(shù)據(jù)進行分析。

表7 商品知識圖譜RDF三元組樣例

表7 展示了商品知識圖譜RDF 數(shù)據(jù)樣例。為了簡潔表示，所有的URI 都使用簡寫表示，并用URI 縮寫的第一個字母表示該元素的類型，如P 開頭的URI 為商品，C 開頭的 URI 為商品分類，R 開頭的 URI 為評論，O開頭的URI 為觀點，F(xiàn) 開頭的URI 為商品屬性。該數(shù)據(jù)假設有兩個商品分類C1和C2，其中C1分類下有3個商品，C2分類下有1 個商品，有兩個用戶分別發(fā)表了3 條評論，且每條評論分別都包含了對特征F1和F2的觀點。圖8展示的是該樣例對應的RDF數(shù)據(jù)圖，其中省略了邊的標簽。

圖8 商品知識圖譜樣例RDF數(shù)據(jù)圖

查詢1假設查詢C1分類所有商品及所有觀點特征的知識，該查詢對應的查詢圖如圖9 所示，同樣省略了邊的標簽，但保留變量邊的標簽。圖中每個變量的對應候選值集合均標在變量節(jié)點右側。

圖9 SPARQL查詢圖及變量候選節(jié)點

查詢1查詢C1分類所有商品及所有觀點特征

SELECT ?p ?f ?o where {

?p rdf:type Product.

?p productOf C1.

?r rdf:type Review.

?r reviewOn ?p.

?f rdf:type Feature.

?r ?o ?f.

};

從圖中可知，變量?f候選值集合的大小為2，變量?r的候選值集合大小為6，變量?p候選值集合的大小為3。目前最新的圖模型查詢系統(tǒng)，例如gStore，在選擇連接順序時優(yōu)先選擇候選集中元素較少的變量節(jié)點進行連接，因此在針對該查詢順序為?f→?r→?p，其每步連接生成的中間結果集IRT如表8所示。

對于表8中的操作，首先選擇變量?r作為連接操作的起始節(jié)點，將候選值集合中的元素依次加入到IRT中，此時|IRT|=|C(?f)|=2；然后與變量?r進行連接操作，此時S1=2，連接操作結束后|IRT|=12；最后與變量?p進行連接操作，此時S2=12，完成連后|IRT|=10。最后對根據(jù)IRT中每條記錄變量獲取?o的值，此時S3=10。因此總代價為S1+S2+S3=24。

在商品知識圖譜中，用戶評論唯一關聯(lián)一個商品，但通常會包含多個觀點。根據(jù)這個數(shù)據(jù)特征，將選擇變量?p作為連接操作的起始節(jié)點，此時連接順序為?p→?r→?f。其每步連接生成的中間結果集IRT如表9所示。

首先將變量?p的候選值集合中的元素依次加入到IRT中，此時|IRT|=|C(?p)|=3，然后與變量?r進行連接操作，此時S1=3，連接完成后|IRT|=5，然后再與變量?f連接，此時S2=5，連接操作完成后|IRT|=10。最后根據(jù)IRT中每條記錄變量獲取?o的值，此時S3=10。該連接順序的總代價為S1+S2+S3=18。不同的連接順序，雖然最終產(chǎn)生的結果不變，但每步生成的中間結果集不同。

在商品知識圖譜中，每一條用戶評論Ri由一個用戶Uj撰寫，并且描述一件商品Pk連接。但評論中會對多個商品屬性表達觀點，如圖10所示。

在商品知識圖譜中，商品、用戶的數(shù)量規(guī)模龐大，而商品屬性的規(guī)模相對較小，導致連接操作時，優(yōu)先將商品屬性與用戶評論進行連接。然而用戶評論唯一關聯(lián)一個商品，但通常會包含多個觀點。因此在商品知識圖譜中，商品屬性和評論進行連接時，中間結果集會擴大，所以連接過程中在進行評論與商品屬性連接的操作應放在最后進行。

表8 連接過程中每步MRT 的數(shù)據(jù)

表9 連接過程中每步中間結果集IRT 的數(shù)據(jù)

圖10 一條商品評論的數(shù)據(jù)圖

5.3 變量組合連接策略

現(xiàn)有基于圖模型的查詢系統(tǒng)主要針對查詢圖中邊標簽均為常量的查詢。在處理邊標簽為變量的查詢時，其連接過程首先將節(jié)點變量連接起來，然后獲取變量邊的值，這種連接策略導致查詢性能較低。

但是在商品知識圖譜中，用戶觀點作為一種重要的知識，存在許多圍繞用戶觀點的查詢，查詢1 展示了一種簡單的用戶觀點查詢。但圍繞用戶觀點往往存在更加復雜的查詢，例如查詢與商品P1相關的商品，這些商品與P1擁有共同的買家，并且買家對該商品的某些屬性具有相同的觀點，該SPARQL如查詢2所示。

查詢2查找商品P1相關商品的SPARQL

SELECT ?p ?f ?o where

{

?r1rdf:type Review.

?r1reviewOn P1.

?r2rdf:type Review.

?p rdf:type Product.

?p productOf C1.

?r2reviewOn ?p.

?f rdf:type Feature.

?r1?o ?f.

?r2?o ?f.

?u rdf:type User.

?u write ?r1.

?u write ?r2.

}

針對該查詢，首先排除變量?o與?f，并將其他變量根據(jù)查詢圖進行連接，得到中間結果集，如表10所示。

表10 查詢2的連接中間結果集

這里針對中間結果集第二條結果進行討論，當R1和R2對商品屬性F1和F2分別發(fā)表了不同的用戶觀點，其RDF數(shù)據(jù)圖如圖11所示。

圖11 兩個用戶評論的觀點都不相同的數(shù)據(jù)圖

按照原有連接策略，將對變量?f進行連接操作，將產(chǎn)生如表11所示的結果。

表11 無效的中間結果列表

最后獲取變量?o的結果時，表11 的所有中間結果均是無效的，然后被刪除。在考慮中間結果是否需要連接變量?f時，需要變量?r1和?r2對應的值都有相同的邊才需要連接，因此，當變量?r1和?r2對應的值沒有相同邊時，該中間結果可以直接刪除，而不需要進行下一步操作。

當兩個評論R1和R2存在相同的觀點，但是針對不同的商品屬性，僅考慮是否存在相同的邊標簽，同樣也會導致無效的中間結果的產(chǎn)生，如圖12所示。

圖12 兩個評論存在相同觀點但不是同一個屬性的數(shù)據(jù)圖

上面的連接方式都是將商品屬性和用戶觀點分開單獨進行查詢，但在商品知識圖譜中，商品屬性和用戶觀點是組合并成對出現(xiàn)。因此利用這個特性，本節(jié)提出了一種商品屬性觀點變量組合（product Aspect and Opinion Combination，AOC）的連接策略，即將變量邊?o與變量節(jié)點?f組合成一個整體變量，首先對變量?f和?o以外的變量節(jié)點進行連接，然后對變量組合進行連接操作。連接組合變量的過程如算法2所示。

算法2連接一個組合變量算法

輸入：當前中間結果表IRT，需要連接的組合變量(e,v)；

輸出：連接變量節(jié)點v后的中間結果表nIRT；

1.設置新的中間結果集nIRT為空，即nIRT=φ；

2.if 變量節(jié)點v的候選集為空then

3.returnnIRT；

4.forIRT中每條中間結果記錄rdo

5.設置臨時表格tmp為空，即tmp=φ；

6.設置臨時表格tmpv為空，即tmpv=φ；

7.for 中間結果記錄r中每個元素eledo

8.ifele與v之間不是通過邊edo

9.continue；

10.將ele添加到tmpv；

11.通過ele獲取v的另一個候選值集合list；

12.iftmp為空 then

13.list與v的候選集進行交集操作，并賦予tmp；

14.else

15.list與tmp進行交集操作，并將結果賦予tmp；

16.iftmp為空 then

17.continue

18.fortmp中每個元素elethen

19.獲取ele邊候選值集合tmpe；

20.for 元素tmpe中每個元素edgethen

21.通過ele和edge獲取候選列表list

22.iftmpv?listthen

23.創(chuàng)建r副本r′，將(edge,ele)添加到r′；

24.r′添加到nIRT；

25.returnnIRT；

6 實驗與分析

6.1 實驗環(huán)境

本實驗硬件環(huán)境為單臺Intel?Core?i5-6500 @3.20 GHz四核處理器的計算機，擁有16 GB DDR3內(nèi)存和1 TB 機械硬盤。為了保證實驗運行的公平性，沒有采用GPU、TPU或FPGA等硬件加速。操作系統(tǒng)為64位Ubuntu 16.04操作系統(tǒng)。

實驗數(shù)據(jù)將通過本文設計的商品知識圖譜框架組織，其中知識圖譜的數(shù)據(jù)為真實數(shù)據(jù)與仿真數(shù)據(jù)相結合，數(shù)據(jù)集的總體概況如表12 所示。其中商品分類、商品信息、用戶知識為真實數(shù)據(jù)，來自于亞馬遜平臺，其中包含商品實體總數(shù)為478 626，用戶實體總數(shù)為1 000 000。用戶評論、觀點知識為仿真數(shù)據(jù)，每個用戶隨機挑選商品并發(fā)表評論，評論中包含隨機數(shù)量的觀點知識。

表12 數(shù)據(jù)集的一些統(tǒng)計信息

6.2 實驗結果與分析

6.2.1 學習映射字典

實驗從存儲空間和響應時間兩個方面進行分析。由于學習映射字典與傳統(tǒng)映射字典都采用了B-tree 結構，為了減少實驗環(huán)境的差異性，實驗中兩者采用相同的B-tree。此外B-tree的階數(shù)對數(shù)據(jù)存儲空間和查詢響應時間存在影響，將針對B-tree的階數(shù)進行討論。兩種映射字典存儲所占用的空間如表13所示。

表13 數(shù)據(jù)對應映射詞典所消耗的存儲空間 MB

根據(jù)結果顯示，隨著B-tree 階數(shù)的增加，兩種映射字典在存儲空間上都呈現(xiàn)減少的趨勢。當兩個映射字典采用相同階數(shù)時，學習映射字典的存儲空間比傳統(tǒng)的映射字典占用的空間少。學習映射字典中第一層只需要保存機器學習模型的參數(shù)，其占用的存儲空間遠小于整體存儲空間，本實驗中，模型存儲空間占用約1 KB。在學習映射字典第二層中，第一層學習模型將數(shù)據(jù)切分成多個小規(guī)模的數(shù)據(jù)分片，每個數(shù)據(jù)分片對應的B-tree的高度均不高于傳統(tǒng)映射字典中B-tree，同時其所有B-tree 內(nèi)部節(jié)點包含鍵的總數(shù)也比傳統(tǒng)映射字典中B-tree少。由于內(nèi)部節(jié)點鍵的數(shù)量占用了絕大部分存儲空間，所以學習映射字典相比傳統(tǒng)映射字典的所占用的存儲空間小。

接下來進一步驗證學習映射字典的查詢效率。首先討論B-tree的階數(shù)對響應時間的影響，這里隨機查詢URI 文本100 000 次，然后統(tǒng)計平均單次查詢URI 文本的響應時間，如圖13所示。

圖13 不同階數(shù)B-tree的平均響應時間

實驗結果顯示，當B-tree 采用不同階數(shù)時，學習映射字典的平均響應時間比傳統(tǒng)映射字典的平均響應時間更短。此外，隨著B-tree 階數(shù)的增加，學習映射字典查詢效率提升更加明顯。

然后針對隨機查詢URI文本的次數(shù)進行比較，這里采用128 階B-tree，統(tǒng)計平均單次查詢URI 文本的響應時間，結果如圖14所示。

實驗結果表明，在處理不同隨機訪問次數(shù)時，學習映射字典的平均響應時間比傳統(tǒng)映射字典的平均響應時間更短。

圖14 B-tree階為128時平均查詢時間

學習映射字典利用機器學習模型將大規(guī)模URI 文本集分割成多個小規(guī)模URI文本集分片，當查詢URI文本時，只需要對其中一個URI 文本集分片進行查詢，相比傳統(tǒng)映射字典，學習映射字典減少了查詢過程中比較操作的次數(shù)。同時第一層的機器學習模型采用單隱層全連接神經(jīng)網(wǎng)絡模型，其模型復雜度較低，執(zhí)行效率較高，使用CPU處理器執(zhí)行此模型，平均單次執(zhí)行時間小于100 ns，小于整體查詢時間。

6.2.2 連接策略

實驗針對商品知識圖譜，圍繞商品的主觀與客觀知識，設計了常用的商品知識查詢語句，如表14所示。

上述SPARQL查詢對應的含義如下：

Q1：在商品分類C1下，查找商品屬性F1具有O1觀點的商品。

Q2：查詢商品P1所有的用戶觀點和對應的商品屬性。

Q3：查詢一個商品分類C1下所有商品，用戶更加關心哪些屬性。通過查詢所有該商品分類下所有商品以及對應的用戶觀點和特征，并將數(shù)據(jù)通過商品屬性進行聚合操作，然后統(tǒng)計數(shù)量。

Q4：查詢與用戶U1愛好相同的用戶，這些用戶不僅與用戶U1購買過相同的商品，并且他們對該商品的某一商品屬性發(fā)表過相同的觀點。

SPARQL查詢運行時間結果如表15所示。

實驗結果顯示，在查詢Q1的查詢性能相似，由于查詢中不包含對商品屬性和用戶觀點的查詢，優(yōu)化策略沒有起到作用。而針對查詢Q2、Q3 和Q4，這些查詢中都包含商品屬性和用戶觀點的查詢，此時優(yōu)化的查詢策略發(fā)揮作用，采用AOC 策略的系統(tǒng)比gStore 具有更高的查詢效率。其中查詢Q2 語句較為簡單，不存在復雜的關系，并且查詢針對一個商品，相關的信息量較少，采用AOC 連接策略的系統(tǒng)相比gStore 性能提升了2 倍。查詢Q3 語句同樣較為簡單，但查詢涉及一個商品分類所有商品的數(shù)據(jù)，相關的數(shù)據(jù)量較大，gStore查詢超過1個小時未獲得結果，而采用AOC 策略的系統(tǒng)在較短時間內(nèi)完成查詢，通過減少中間結果的產(chǎn)生，提高了查詢的效率。查詢Q4的語言的復雜度比查詢Q2，Q3大，gStore同樣無法在1 h內(nèi)完成該查詢，采用AOC策略的系統(tǒng)在較短時間內(nèi)完成查詢，由于避免了生成無效的中間結果，從而提高了查詢效率。

表14 商品知識查詢

表15 SPARQL查詢運行時間

7 結束語

首先，為了統(tǒng)一管理商品客觀信息與用戶觀點主觀信息，本文設計了一種融合商品客觀與主觀知識的商品知識圖譜框架。然后，為了提升查詢效率，降低URI 文本轉換成對應ID值的代價，結合學習索引，提高查詢效率，并利用前綴樹對URI 文本中冗余的前綴進行壓縮，進一步提高查詢效率。接著，為了提高商品知識查詢的效率，設計了商品屬性觀點變量組合的連接策略，具有較高的商品知識查詢效率。最后在商品知識圖譜數(shù)據(jù)上驗證了本文提出的方法具有性能上的提升。在之后的工作中，將會考慮利用GPU構建異構計算平臺，進一步提升商品知識檢索的效率。