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

1.桂林電子科技大學(xué) 廣西可信軟件重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004

2.桂林電子科技大學(xué) 廣西自動檢測技術(shù)與儀器重點(diǎn)實(shí)驗(yàn)室，廣西 桂林 541004

1 引言

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

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

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

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

（2）提出了一種結(jié)合學(xué)習(xí)索引[18]的映射字典，提高映射字典的查詢速度，并利用前綴樹進(jìn)一步減少檢索時(shí)間，實(shí)驗(yàn)證明該方法提高了映射字典檢索效率。

（3）提出了一種商品屬性觀點(diǎn)變量組合策略，該方法基于商品知識圖譜的結(jié)構(gòu)特點(diǎn)，實(shí)驗(yàn)證明該方法有效降低了商品知識檢索的時(shí)間。

2 相關(guān)工作

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

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

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

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

3.1 整體框架概況

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

圖1 商品知識圖譜框架

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

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

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

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

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

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

3.2 商品客觀知識

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

表1 客觀知識類型

當(dāng)表示客觀知識時(shí)，所需用到的屬性如表2所示。

表2 客觀知識屬性

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

圖2 商品客觀知識樣例

3.3 用戶評論主觀知識

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

表3 主觀知識類型

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

表4 主觀知識屬性

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

圖3 商品主觀知識樣例

4 學(xué)習(xí)映射字典

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

4.1 學(xué)習(xí)索引

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

4.2 文本分布

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

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

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

4.3 學(xué)習(xí)映射字典結(jié)構(gòu)

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

圖5 學(xué)習(xí)映射字典結(jié)構(gòu)

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

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

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

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

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

4.4 URI文本壓縮

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

表5 部分類型實(shí)體對應(yīng)的完整URI文本樣例

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

圖7 命名空間壓縮前綴樹

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

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

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

5.1 連接代價(jià)

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

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

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

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

1.設(shè)置新的中間結(jié)果集nIRT為空，即nIRT=φ；

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

3.returnnIRT；

4.forIRT中每條中間結(jié)果記錄rdo

5.設(shè)置臨時(shí)表格tmp為空，即tmp=φ；

6.for中間結(jié)果記錄r中每個元素edo

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

8.continue；

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

10.iftmp為空then

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

12.else

13.list與tmp進(jìn)行交集操作，并將結(jié)果賦予tmp；

14.fortmp中所有的元素edo

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

16.r′添加到nIRT；

17.returnnIRT；

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

5.2 連接順序

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

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

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

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

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

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

查詢1查詢C1分類所有商品及所有觀點(diǎn)特征

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，在選擇連接順序時(shí)優(yōu)先選擇候選集中元素較少的變量節(jié)點(diǎn)進(jìn)行連接，因此在針對該查詢順序?yàn)?f→?r→?p，其每步連接生成的中間結(jié)果集IRT如表8所示。

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

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

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

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

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

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

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

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

5.3 變量組合連接策略

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

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

查詢2查找商品P1相關(guān)商品的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ù)查詢圖進(jìn)行連接，得到中間結(jié)果集，如表10所示。

表10 查詢2的連接中間結(jié)果集

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

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

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

表11 無效的中間結(jié)果列表

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

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

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

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

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

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

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

1.設(shè)置新的中間結(jié)果集nIRT為空，即nIRT=φ；

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

3.returnnIRT；

4.forIRT中每條中間結(jié)果記錄rdo

5.設(shè)置臨時(shí)表格tmp為空，即tmp=φ；

6.設(shè)置臨時(shí)表格tmpv為空，即tmpv=φ；

7.for 中間結(jié)果記錄r中每個元素eledo

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

9.continue；

10.將ele添加到tmpv；

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

12.iftmp為空 then

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

14.else

15.list與tmp進(jìn)行交集操作，并將結(jié)果賦予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 實(shí)驗(yàn)與分析

6.1 實(shí)驗(yàn)環(huán)境

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

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

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

6.2 實(shí)驗(yàn)結(jié)果與分析

6.2.1 學(xué)習(xí)映射字典

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

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

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

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

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

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

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

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

圖14 B-tree階為128時(shí)平均查詢時(shí)間

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

6.2.2 連接策略

實(shí)驗(yàn)針對商品知識圖譜，圍繞商品的主觀與客觀知識，設(shè)計(jì)了常用的商品知識查詢語句，如表14所示。

上述SPARQL查詢對應(yīng)的含義如下：

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

Q2：查詢商品P1所有的用戶觀點(diǎn)和對應(yīng)的商品屬性。

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

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

SPARQL查詢運(yùn)行時(shí)間結(jié)果如表15所示。

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

表14 商品知識查詢

表15 SPARQL查詢運(yùn)行時(shí)間

7 結(jié)束語

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