岳 昆,闞伊戎,王鈺杰,錢文華

(云南大學 信息學院,云南 昆明 650500)

0 引言

知識圖譜(Knowledge Graph, KG)是結構化的語義知識庫，其以符號形式描述物理世界中的概念和相互關系，以“實體-關系-實體”三元組作為基本組成單位，為海量數(shù)據(jù)和領域知識提供了一種有效的組織方式，例如Apple Siri的Wolfram Alpha[1]、YAGO的YAGO KB[2]和DBpedia的DBpediaKB[3]等。在電子商務應用中，基于商品之間關聯(lián)關系構成的KG(即電子商務領域知識體系)，可有效支持商品管理、跨領域搜索、導購和交互，并體現(xiàn)用戶需求的個性化服務。近年來，國際上主流的互聯(lián)網(wǎng)公司或研究機構均加入KG的研究中，并在KG或知識庫的構建[4-5]、知識表示與學習[6-7]、關聯(lián)查詢[8-10]等方面開展了大量研究。

針對給定的KG結構或節(jié)點，找到KG中與其關聯(lián)的部分，是KG關聯(lián)查詢的基本任務，查找KG中具有關聯(lián)關系的實體是實現(xiàn)這一基本任務的關鍵[10]，也是海量數(shù)據(jù)背景下信息檢索與服務的重要基礎。從海量數(shù)據(jù)和實際應用中實體間相互關聯(lián)的特點看，實體間的關聯(lián)關系往往具有不確定性，其反映了關聯(lián)關系的強度，可以用來定量描述實體間的依賴關系，例如“安全座椅”與“汽車”以95%的概率相關聯(lián)。在KG關聯(lián)查詢中考慮該特點，計算任意實體間直接或間接的關聯(lián)關系及其相應的不確定性，能夠以更細的粒度回答查詢，使結果與實際情形更加吻合。因此，關聯(lián)關系的表示及其不確定性計算，是KG關聯(lián)查詢處理中應該解決的核心問題。

從關聯(lián)關系表示的角度看，KG本身包含了對特定領域中實體間關聯(lián)關系的描述，然而由于Web 2.0、電子商務應用和社交網(wǎng)絡的普及與廣泛應用，快速產(chǎn)生了基于多種媒介的用戶行為記錄(如商品購買或評價、消息評論或轉(zhuǎn)發(fā)等)，即使對于同一實體集，用戶行為中體現(xiàn)出的實體間的關聯(lián)關系，仍然可能與KG中的描述不同。也就是說，KG和用戶行為記錄分別從領域知識體系和歷史數(shù)據(jù)集兩個方面描述了實體間的關聯(lián)關系，從用戶行為記錄產(chǎn)生和KG構建的角度看，急劇增長的數(shù)據(jù)中所蘊含的知識也是KG所描述領域知識的有益補充。因此，將KG中描述的知識與用戶行為記錄中蘊含的知識進行有效融合，構建完整、全面的關聯(lián)關系知識模型，是KG關聯(lián)查詢處理結果有效性的重要保證。

面向電子商務應用，為了對所涉及商品和用戶的KG進行關聯(lián)查詢處理，將用戶的購買或評價記錄中反映出來的商品之間的潛在關聯(lián)關系作為KG中商品之間關聯(lián)關系的補充，并將兩方面知識進行有效融合，得到具有關聯(lián)關系的商品，是商品分類、用戶定向、銷量預測和個性化推薦等電子商務典型應用的重要基礎和支撐技術。例如，通過涉及安全座椅、行車記錄儀、坐墊和野餐墊等實體的用戶行為記錄，以及KG中描述這些商品之間的關聯(lián)信息，得到安全座椅分別以20%，45%，30%的強度與行車記錄儀、坐墊和野餐墊存在關聯(lián)關系，進而對汽車配件或母嬰主題的相關商品進行細粒度、有針對性地管理和營銷。從關聯(lián)關系強度定量計算的角度看，特定商品對應的用戶行為記錄，是對商品間關聯(lián)關系的不確定性進行統(tǒng)計計算的基礎。針對實際中的大規(guī)模KG和海量的用戶行為記錄，需要設計海量數(shù)據(jù)處理算法，從而實現(xiàn)關聯(lián)關系表示和不確定性的高效計算。

因此，給定涉及商品和用戶信息的KG，針對特定查詢處理任務，如何從KG和用戶行為記錄中獲取相關商品之間的關聯(lián)關系及其不確定性，支持任意實體間直接或間接的不確定性關聯(lián)關系的有效計算，進而有效地回答關聯(lián)查詢，是本文研究的關鍵。

近年來，國內(nèi)外研究人員提出不同的KG關聯(lián)查詢處理方法。Metzger等[8]和Yan等[9]基于結構特征提出實體間相似性的建模方法，根據(jù)查詢結果推測用戶興趣，自動提取實體的全部特征來判斷用戶偏好；Jayaram等[10]提出基于實體元組的查詢方法，在KG中查找與給定元組相似的元組集合；Fan等[11]提出圖結構的函數(shù)依賴，討論了圖的查詢、清理和挖掘問題；Yuan等[12]提出基于圖結構的查詢處理方法，該方法可從KG中查找與給定圖結構相似的子圖集合；Zhang等[13]將結構與語義相似性結合，基于語義編輯距離回答SPARQL(simple protocol and RDF query language)查詢。然而，這些方法僅以KG作為知識來源，在電子商務應用的實際情形中，用戶行為記錄中可能蘊含著當前已經(jīng)顯現(xiàn)出來、但KG中尚未包含的實體或尚未描述的關聯(lián)關系，因此知識未必全面和實時；另外，這些方法也未考慮關聯(lián)關系的不確定性或強度的定量計算，使關聯(lián)關系的粒度較粗，甚至與實際情形不吻合。

基于數(shù)據(jù)分析回答商品的關聯(lián)查詢是一類具有代表性的方法，Zhou等[14-15]提出基于文本或關系數(shù)據(jù)發(fā)現(xiàn)商品間關聯(lián)關系的方法。然而在實際中，海量的商品、用戶和用戶行為記錄對其組織形式和模型的計算效率提出了更高的要求。

貝葉斯網(wǎng)(Bayesian Network, BN)是一個由隨機變量構成的有向無環(huán)圖(Directed Acyclic Graph, DAG)，每個節(jié)點(即變量)有一張定量描述節(jié)點間依賴關系的條件概率表(Conditional Probability Table, CPT)?；贐N可實現(xiàn)不確定性知識的定性和定量計算，作為一種重要的概率圖模型，BN被廣泛應用于不確定性知識的表示和推理[16-17]。鑒于BN在表示變量間的依賴關系及其不確定性以及推理方面的顯著優(yōu)勢，本文采用BN的圖模型表示KG中商品(即節(jié)點)間的關聯(lián)關系，采用BN的推理算法定量計算關聯(lián)關系的強度，從而解決上述關聯(lián)查詢的核心問題。因此，本文將BN作為基本知識框架和模型基礎，首先構建用以描述商品間關聯(lián)關系及其不確定性的BN，進而基于BN的概率推理算法回答KG的關聯(lián)查詢

對于KG之上的關聯(lián)查詢處理任務，如“與‘安全座椅’有關的實體”，本文首先抽取KG中與查詢目標相關的實體構成的子圖結構，作為最終所要構建BN的初始DAG結構，來反映相關實體在電子商務領域知識體系層面的關聯(lián)關系。在此基礎上分析用戶行為記錄，從用戶行為層面以增量的方式完善初始DAG結構，并計算各節(jié)點的CPT，從而構建相應的BN，將KG中描述的領域知識與用戶行為記錄中蘊含的知識有機融合，作為KG知識表示框架的補充和擴展，為實現(xiàn)KG關聯(lián)查詢處理奠定基礎。

與表示為關聯(lián)規(guī)則[17]的關聯(lián)關系不同，BN能夠以DAG的方式描述任意形式、非線性的關聯(lián)關系，KG中的圖結構和數(shù)據(jù)的相關性反映了商品之間的關聯(lián)關系?；贐N的概率推理算法不僅無需根據(jù)查詢處理任務構造概率計算式，還可以通過計算實體間的關聯(lián)關系反映實體間潛在的相互依賴關系，因此更具通用性和可擴展性。

本文的主要研究工作包括：

(1)為了描述給定KG關聯(lián)查詢?nèi)蝿罩猩婕暗南嚓P商品間的關聯(lián)關系及其不確定性，首先對KG中的領域知識進行分析，針對大規(guī)模KG提出基于Spark[18]的并行算法，從KG抽取商品間的關聯(lián)關系，得到BN的初始DAG模型。

(2)借鑒數(shù)據(jù)密集型BN學習算法[19]，以(1)中得到的圖模型為BN初始結構，給出基于Spark的并行算法，從海量用戶行為記錄中提取所蘊含的知識來構建DAG并計算各節(jié)點的CPT，然后對KG中的領域知識與用戶行為記錄中所蘊含的知識進行有效融合，得到描述關聯(lián)查詢處理任務時涉及的商品間關聯(lián)關系及其不確定性的BN。

(3)Gibbs采樣是應用最廣泛的Markov鏈蒙特卡洛(Markov Chain Monte Carlo, MCMC)概率算法，可有效地獲取一系列近似等于指定多維概率分布的觀察樣本[20]。本文基于Gibbs采樣算法進行BN概率推理，以通用算法計算任意商品或商品集合之間直接或間接的關聯(lián)關系，從而高效地計算關聯(lián)關系的強度。

通過淘寶網(wǎng)真實數(shù)據(jù)[21]和Spark計算引擎進行實驗，測試了本文方法的有效性和高效性。

1 相關定義和問題陳述

以電子商務應用為背景，KG的基本組成單位是“用戶-購買-商品”三元組，用戶和商品間通過購買關系相互聯(lián)接構成網(wǎng)狀結構。假設用戶購買了多個商品(如圖1)，例如用戶u0購買商品p1，p2，p3，則存在有向邊(u0,p1)，(u0,p2)，(u0,p3)。在面向電子商務應用的KG(E-Commerce KG, EKG)中，商品和用戶構成節(jié)點集，商品和用戶之間的關系構成有向邊，將EKG表示為GE=(V,E)；P={p1,p2,…,pn}和U={u1,u2,…,um}分別表示商品節(jié)點集和用戶節(jié)點集，V=P∪U;E={(ui,pj)}表示商品和用戶之間的關系，ui∈U(1≤i≤n)，pj∈P(1≤j≤m)。

EKG上的關聯(lián)查詢描述為：給定商品集合Q，在EKG中得到與Q中商品相關的前k個商品,關聯(lián)度對，記為R，R={pj,prj|j={1,2,…,k},pj∈P,prj∈[0,1]}，其中：pj為與商品集合Q關聯(lián)的節(jié)點，prj為節(jié)點pj與Q中商品關聯(lián)的強度。

定義1[16]BN是描述節(jié)點及節(jié)點間依賴關系的DAG，用節(jié)點表示隨機變量，有向邊表示節(jié)點間的依賴關系，每個節(jié)點的CPT用來量化父節(jié)點的影響(獨立于除父節(jié)點的其他節(jié)點)，節(jié)點X的父節(jié)點指所有存在一條直接指向X邊的節(jié)點。

定義2關聯(lián)查詢貝葉斯網(wǎng)(Correlation Query BN, CQBN)是表示商品間關聯(lián)關系的DAGG=(V,E,Pr)，其中：V為商品節(jié)點集，E為商品節(jié)點間關聯(lián)關系的集合，Pr表示各節(jié)點CPT的集合。

GraphX[18]實質(zhì)上是分布式有向多重圖，而且節(jié)點和邊都可以有屬性，本文基于GraphX來存儲CQBN，以支持CQBN上的概率推理和關聯(lián)查詢處理。GraphX中的邊表示CQBN中商品間的依賴關系，點表示CQBN中的節(jié)點，而且每個節(jié)點的CPT以嵌套二元組的形式作為點的屬性。例如，Pr311=Pr(X3=1|X1=1,X2=1)的存儲格式為((((X1,1),(X2,1)),1),Pr311)。CQBN中的商品節(jié)點集V包括給定商品節(jié)點集Q和候選節(jié)點集Q′，反映商品間關聯(lián)關系的邊集依賴于EKG中描述的領域知識體系和用戶行為記錄中蘊含的知識。

2 關聯(lián)查詢模型的構建

本章首先根據(jù)給定的關聯(lián)查詢抽取EKG中的關聯(lián)關系，然后從用戶行為記錄中發(fā)現(xiàn)相關實體之間可能存在的其他關聯(lián)關系，并計算其強度。為了便于討論，用戶行為記錄表示為該記錄所涉及商品的集合。

2.1 抽取EKG中商品間的關聯(lián)關系

若將EKG中的所有商品作為節(jié)點構建CQBN，則需很大的時間代價，不但不符合實際要求，而且對于KG的關聯(lián)查詢處理也沒有必要。對此，本文只考慮與關聯(lián)查詢中給定商品節(jié)點集Q具有較高相關度的商品節(jié)點集Q′，Q∪Q′即為CQBN中的節(jié)點集V。具體地，給定商品節(jié)點集Q，首先對Q的1步用戶鄰居節(jié)點集(記為U1)進行廣度優(yōu)先搜索，再對U1的1步商品節(jié)點集(記為Q1)進行廣度優(yōu)先搜索，再對Q1的鄰居節(jié)點集進行搜索，……，直到達到指定步數(shù)為止，從而找到與Q可能關聯(lián)的商品節(jié)點集Q′。例如，對于圖1中的EKG，考慮1步鄰居，用戶u0的購物記錄為Q={p1,p2,p3}，Q的可能關聯(lián)節(jié)點集為Q′={p4,p5,p6}。

給定EKG，對于任意兩個商品節(jié)點p1和p2，假設購買商品p1的用戶集合為|U1|，購買商品p2的用戶集合為|U2|，同時購買商品p1和p2的用戶集合為|U1∩U2|，給出關聯(lián)度C(p1,p2)來判斷兩種商品之間是否存在關聯(lián)，并判斷邊的方向，從而得到CQBN的初始DAG結構。具體地，若C(p1,p2)≥θ，則商品節(jié)點p1到節(jié)點p2存在關聯(lián)關系，否則商品節(jié)點p1與節(jié)點p2不存在關聯(lián)關系。

(1)

式中|U1∪U2|表示購買商品p1或p2的用戶的集合。

針對EKG中的節(jié)點和邊，本文以Spark為計算引擎，判斷兩個商品節(jié)點之間的關聯(lián)關系。確定每對商品p1和p2之間的關聯(lián)關系時，對|U1|，|U2|，|U1∩U2|進行統(tǒng)計計算的時間開銷較大，因此采用GraphX存儲EKG中的節(jié)點和邊，設計并行算法。第一階段并行算法以Q∪Q′為輸入，通過Map函數(shù)得到每個用戶購買商品的情況，通過Reduce函數(shù)統(tǒng)計所有用戶購買商品的情況，結果以key,value對形式表示，key為用戶節(jié)點，value為用戶購買商品的列表，得到U1，U2，U1∪U2；第二階段并行算法通過Map函數(shù)和Reduce函數(shù)得到|U1|，|U2|，|U1∪U2|，從而判斷商品之間的依賴關系。上述方法的思想如算法1所示。

算法1

輸入：給定的EKGG、G中的用戶節(jié)點集U、查詢商品節(jié)點的k步鄰居商品節(jié)點集N。

輸出：每對商品的購買情況list，即|U1|，|U2|，|U1∩U2|。

1.val outDegree←G.graph.collectNeighborIds(EdgeDirection.Out) /*計算G中各節(jié)點的出度*/

2.val user←U

3.var resultEmit /*存儲對商品的處理結果*/

4.resultEmit←user.map{x=>

5.tmp←outDegree.filter()/*查找用戶指向的商品*/

6.var keyValue /*存儲中間結果*/

7.FOR piin tmp DO

8. keyValue←keyValue.union((x,pi))

9.END FOR

10.keyValue /*將值傳遞給resultEmit*/

11.}.reduce /*統(tǒng)計每個用戶節(jié)點指向的商品節(jié)點*/

13.list←resultEmit.map{x=>

15. IF piIN x AND pjIN x THEN

17. ElSE IF piIN x THEN /*若用戶只購買pi*/

18. (pi,1)

19. ELSE IF pjIN x THEN /*若用戶只購買pj*/

20. (pj,1)

21. END IF

22.END FOR

23.}.reduce

24.RETURN lis

不難看出，算法1的執(zhí)行代價主要為將同一個用戶購買的不同商品組合在一起的時間開銷。若EKG中包含m個用戶和n種商品，則算法1在最壞情況下的時間復雜度為O(nm)。針對實際中規(guī)模較大的KG，將通過實驗測試算法的有效性。

2.2 發(fā)現(xiàn)用戶行為記錄中的關聯(lián)關系

評分搜索(scoring & search)算法是BN結構學習的經(jīng)典方法[19]，算法從一個無邊的圖開始，通過對當前圖進行加邊、減邊、反轉(zhuǎn)邊等操作產(chǎn)生一系列候選模型，然后根據(jù)評分函數(shù)對候選模型進行評分，從中找到最優(yōu)結構模型。將從EKG中抽取的商品節(jié)點構成的子圖記為G0，以G0為初始結構，利用BN的結構學習算法對其中無有向邊連接的節(jié)點對(即未包含關聯(lián)關系)進行加邊、減邊和反轉(zhuǎn)邊測試，使用最小描述長度(Minimum Description Length, MDL)作為評分標準，對候選結構模型進行評分[18]，選取分值最高的模型作為最終的關聯(lián)關系圖，得到CQBN的DAG。其中，MDL評分標準為

(2)

以上方法具體如算法2所示。

算法2

輸入：商品節(jié)點集V、用戶行為記錄集D、從EKG中抽取的關聯(lián)關系圖G0。

輸出：CQBN的DAGG。

1.G←G0; oldScore←F(G0|D)/*最小描述長度*/

2.WHILE true DO

3. G*←null; newScore←∞

4. FOREACH G0中無邊相連的節(jié)點對 DO

5. 進行加邊、減邊和反轉(zhuǎn)邊操作

6. tempScore←F(G′|D)

/*基于文獻[19]中的算法，對D中的每一條記錄ti計算邊緣概率或聯(lián)合概率，進而計算MDL分值*/

7. IFtempScore

8. G*←G′; newScore←tempScore

9. END IF

10. END FOR

11. IF newScore

12. G←G*; oldScore←newScore

13. ELSE

14. RETURNG

15. END IF

16.END WHILE

算法2的執(zhí)行代價主要是計算以G0中各子集所對應子圖的MDL分值，最壞的情況是計算所有邊的MDL分值，其中F(G′|D)的計算時間隨D中的記錄數(shù)線性增長[19]。因此，若G0中有l(wèi)個節(jié)點，且D中包括k條用戶行為記錄，則算法2在最壞情況下的時間復雜度為O(l2k)。

2.3 CPT計算

基于算法2得到的DAG，本節(jié)采用最大似然估計法[16,19]從用戶行為記錄計算CQBN中各節(jié)點的CPT?？紤]一個由X1,X2,…,Xn組成的CQBN，若Xi共有ri個取值，其父節(jié)點π(Xi)共有qi個取值組合(若Xi無父節(jié)點，則令qi=1)，則Xi的參數(shù)為

θijk=Pr(Xi=k|π(Xi)=j)。

(3)

式中i∈[1,n]。對于特定的i,j∈[1,qi]，k∈[1,ri]，用θ表示所有θijk組成的向量，有

(4)

根據(jù)條件概率計算公式，Pr(X=k|(X)=j)=Pr(X=k,(X)=j)/Pr((X=j))，因此計算Pr(X=k|(X)=j)可歸結為對Pr(X=k,(X)=j)和Pr((X=j))的計算。本文給出基于Spark的CPT計算方法，算法中的Map階段記錄每條用戶的行為，若包括節(jié)點(X)，則輸出(X),1和(X).union(X),1；Reduce階段對Map結果聚集后再進行處理，分別計算Pr(X=k,(X)=j)和P((X=j))值，得到每個節(jié)點的CPT。以上方法具體如算法3所示。

算法3

輸入：CQBN的DAGG、用戶行為記錄集D。

輸出：CQBN的CPTresult。

1.val data←D

2.val countOfSubsetOfNodes←data.map{x=>

3. FOR XiIN G DO

4. (π(X),1)

6. END FOR

7.}.reduce

8.var result←null /*存儲表示CPT的二元組(key, value)*/

9.FOR XIN G DO

11.END FOR

12.RETURN result

算法3的算法時間復雜度取決于Map函數(shù)，其中包含的FOR循環(huán)對CQBN中的每個節(jié)點進行處理，因此算法的時間復雜度為O(kn)，其中k為用戶行為記錄數(shù)，n為CQBN中節(jié)點的個數(shù)。

3 關聯(lián)查詢處理

為了以統(tǒng)一的計算方法高效地計算商品間的間接關聯(lián)關系及其強度，本文以查詢節(jié)點集Q作為證據(jù)，采用Gibbs采樣進行CQBN的近似推理，從而計算候選節(jié)點集Q′的概率值，作為Q′中節(jié)點與Q中節(jié)點之間相互關聯(lián)的強度，即為關聯(lián)查詢的結果。為了簡化計算，在采樣過程中僅考慮其Markov覆蓋(Markov blanket)(X的Markov覆蓋包括X的直接孩子節(jié)點、直接父節(jié)點，以及直接孩子的其他父節(jié)點，記為MB(X))[13,19]。CQBN包括特定關聯(lián)查詢中涉及的商品(節(jié)點)，其規(guī)模遠小于原EKG，基于Gibbs采樣的CQBN推理方法如算法4所示。

算法4

輸入：G=(V,E,Pr)，為第3章構建的CQBN；給定商品(證據(jù)變量)集合Q；Q的取值e；V中Q之外的節(jié)點(非證據(jù)變量)集Q′；采樣次數(shù)s。

輸出：給定Q時G中其他商品的條件概率Pr(X|e),XQ′。

1.隨機為Q′中每個變量Xi賦值：v0←e∪Xi;N[Xi]←0/*N[Xi]為Xi取1的個數(shù)*/

2.FOR k←1 TO s DO/*產(chǎn)生樣本序列*/

3. FOR XiIN Q′ DO

4. B←Pr(Xi=0|vMB(Xi))+Pr(Xi=1|vMB(Xi))

5. 產(chǎn)生隨機數(shù)rk∈[0,B]，確定Xi的值：

6. END FOR

7.END FOR

8.FOR k←1 TO s DO

9. IF Xi=x1THEN

10. N[Xi]←N[Xi]+1/*N[Xi]表示Xi取值的個數(shù)*/

11. END IF

12.END FOR

13.Pr(X|e)←N[xi]/s/*計算Q′中各變量的概率*/

14.RETURN Pr(X|e)

通過算法2得到與Q中商品存在關聯(lián)關系的商品及其相應的關聯(lián)強度，并按照關聯(lián)強度排序，得到相關的前k個商品,關聯(lián)強度對。Gibbs采樣算法的收斂性(已在文獻[20]中進行了分析)從理論上保證了算法4的有效性。

4 實驗結果

為了測試本文所提方法的有效性，采用淘寶網(wǎng)2015年11月18日～12月18日的用戶行為記錄數(shù)據(jù)作為實驗數(shù)據(jù)集，包括20 000個用戶、620 918件商品和23 291 027條用戶行為記錄[21]，基于現(xiàn)有的KG構建方法構建EKG。Spark計算平臺的實驗環(huán)境如下：1臺主頻為3.3 GHz的32核CPU、內(nèi)存為32 GB的計算機作為Master節(jié)點，10臺主頻為3.3 GHz的8核CPU、內(nèi)存為16 GB的計算機作為Worker節(jié)點。

4.1 有效性測試

通過測試電子商務應用中兩種相互關聯(lián)的商品銷售情況來測試模型構建算法的有效性。若兩種商品相互關聯(lián)，則在相同時間段內(nèi)兩種商品銷量的變化趨勢一致。實驗統(tǒng)計商品在5個時間段(每6天為一個時間段)的銷售情況，計算某種商品在這5個時間段的最高、最低和居中銷量，考察與其關聯(lián)的前3種商品的銷量是否具有一致性。執(zhí)行3次關聯(lián)查詢，關聯(lián)商品銷量的趨勢分別如圖2～圖4所示?？梢?，在任一時間段內(nèi)，關聯(lián)商品銷售情況呈現(xiàn)相同的變化趨勢，由于幾種商品相互關聯(lián)，顧客會以較高的概率同時購買(或同時不購買)。因此，基于算法4得到的KG關聯(lián)查詢處理結果是合理的。

同時，以文獻[8]中KG的相似實體搜索結果為標準，進一步測試本文所提KG關聯(lián)查詢方法的有效性。準確率(precision)定義為關聯(lián)查詢處理結果中的相似實體比率，召回率(recall)定義為關聯(lián)查詢處理結果中相似實體占所有相似實體的比率。在KG中包括100，200，400，600個節(jié)點的情形下(用|GE|表示KG中包含的節(jié)點數(shù))，記錄關聯(lián)查詢Q中包含的商品數(shù)分別為5，10，15，20，25時的準確率和召回率，分別如圖5和圖6所示。

可以看出，基于本文提出的KG關聯(lián)查詢處理方法，準確率和召回率均隨KG中所包含節(jié)點數(shù)量的增多、Q中所包含商品數(shù)量的增多而下降，但下降趨勢較為平緩；本文關聯(lián)查詢結果的準確率均高于40%，召回率均高于87%。本文方法可以發(fā)現(xiàn)在KG中未反映出來、但在實際用戶行為記錄中蘊含在的商品間的關聯(lián)關系，因此在查詢時，即使KG規(guī)模較大、給定商品較多，也能保證較高的召回率。正是由于這一原因，用本文方法得到的關聯(lián)查詢結果中，一些商品之間的關聯(lián)關系用文獻[8]方法未必能發(fā)現(xiàn)，因此將用戶行為記錄中的關聯(lián)商品與基于文獻[8]得到的關聯(lián)商品匯集起來，作為準確率和新穎性測試的標準對方法的有效性進行進一步測試，這是筆者正在開展的工作。

進一步，在包括100個節(jié)點的KG和相應用戶行為記錄上，對于基于CQBN和基于關聯(lián)規(guī)則(記為AR)得到的關聯(lián)商品，分別以概率推理結果和置信度作為商品關聯(lián)強度?？紤]置信度閾值為0.1和0.2的情形，比較兩種方法在關聯(lián)查詢Q中包含的商品數(shù)分別為5，10，15，20，25時所得結果的準確率和召回率，如圖7和圖8所示。可以看出，本文CQBN得到的關聯(lián)商品的準確率和召回率均高于關聯(lián)規(guī)則得到的結果，說明本文方法適用于稀疏用戶行為記錄分析；隨著Q中商品數(shù)的增加，CQBN查詢結果的準確率和召回率下降得都不明顯，因為CQBN的概率推理計算比關聯(lián)規(guī)則更多地考慮了商品之間的間接相關性，這也說明了本文提出的KG關聯(lián)查詢處理方法的有效性。

4.2 效率測試

為了測試EKG中商品關聯(lián)關系抽取算法(算法1)的效率，在KG規(guī)模分別為1.1 GB(1 GB數(shù)據(jù)約包括2 300萬條邊)，2.2 GB，3.3 GB，4.4 GB，5.5GB，Worker數(shù)量為10的情況下，測試算法的執(zhí)行時間，以及不同節(jié)點下算法的加速比和并行效率。圖9所示為10個Worker時，不同KG規(guī)模下算法1的執(zhí)行時間。可見隨著KG規(guī)模的增大，鄰居步數(shù)越大，執(zhí)行時間越長，而且算法1的執(zhí)行時間隨著KG規(guī)模和鄰居步數(shù)的增大線性增長，說明算法1能夠有效處理大規(guī)模KG。

以6步鄰居節(jié)點作為關聯(lián)查詢候選節(jié)點，測試不同數(shù)據(jù)量和不同節(jié)點數(shù)下的加速比。圖10所示為隨著KG規(guī)模的增大，Worker數(shù)不同時算法1的加速比；圖11所示為隨著Worker數(shù)的增加，不同KG規(guī)模下算法1的加速比。可以看出，隨著KG規(guī)模的增大，Worker數(shù)量越多，加速比增加越快。

圖12所示為Worker數(shù)不同時，不同KG規(guī)模下的并行效率，可見隨著KG規(guī)模的增大，不同Worker節(jié)點的并行效率均逐漸增加。圖13所示為KG規(guī)模不同時，不同Worker數(shù)量下的并行效率，可見隨著Worker數(shù)量的增加，不同KG規(guī)模的并行效率均逐漸下降，而且Worker數(shù)量相同時的KG規(guī)模越大，并行效率越高，說明算法1對于大規(guī)模KG具有較好的可擴展性。

算法2和算法3通過用戶行為記錄構建CQBN，測試用戶行為記錄數(shù)據(jù)規(guī)模分別為1.1 GB，2.2 GB，3.2 GB，4.4 GB，5.5 GB時，不同計算節(jié)點下CQBN構建方法的執(zhí)行時間、加速比和并行效率。圖14所示為隨著用戶行為記錄數(shù)據(jù)規(guī)模的增大，不同Worker數(shù)量下CQBN構建方法的執(zhí)行時間?？梢姡S著用戶行為記錄數(shù)據(jù)規(guī)模的增大，Worker數(shù)量越多，CQBN構建方法的執(zhí)行時間越短，而且隨用戶行為記錄數(shù)據(jù)規(guī)模的增大線性增長，說明本文方法能夠很好地處理海量數(shù)據(jù)。

圖15所示為不同用戶行為記錄規(guī)模下，Worker數(shù)量不同時CQBN構建方法的加速比。圖16所示為不同Worker數(shù)量下，用戶行為記錄規(guī)模與加速比的關系，可見隨著Worker節(jié)點數(shù)的增加，用戶行為記錄數(shù)據(jù)規(guī)模增大，加速比也逐漸增大。圖17所示為不同用戶行為記錄規(guī)模下，Worker數(shù)量不同時的并行效率，可見隨著用戶行為記錄規(guī)模的增大，不同Worker節(jié)點下CQBN構建方法的并行效率均逐漸增加。圖18所示為不同Worker數(shù)下，用戶行為記錄規(guī)模不同時的并行效率，可見隨著Worker數(shù)的增加，不同用戶行為記錄規(guī)模的并行效率均趨于平穩(wěn)，而且Worker數(shù)相同時，用戶行為記錄數(shù)越多，并行效率越高，說明本文提出的CQBN構建方法對于處理海量用戶行為記錄具有較好的可擴展性。

5 結束語

本文面向電子商務應用，提出將KG中描述的知識和用戶行為記錄中蘊含的知識進行融合，并基于BN的概率推理定量計算商品間關聯(lián)強度的方法，而且基于Spark設計了CQBN模型構建算法，通過實驗測試了方法的有效性、高效性和良好的可擴展性。

本文所提方法為KG的關聯(lián)查詢提供了一種思路，但是仍為對KG關聯(lián)查詢的初步探索，還需進一步通過實驗對關聯(lián)查詢結果進行測試；另外，針對商品屬性更細的粒度，進步一研究用戶偏好對商品間關聯(lián)關系的影響，也是需要開展的工作。