面向電子商務(wù)應(yīng)用的知識圖譜關(guān)聯(lián)查詢處理

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 相關(guān)定義和問題陳述

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

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

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

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

GraphX[18]實質(zhì)上是分布式有向多重圖，而且節(jié)點和邊都可以有屬性，本文基于GraphX來存儲CQBN，以支持CQBN上的概率推理和關(guān)聯(lián)查詢處理。GraphX中的邊表示CQBN中商品間的依賴關(guān)系，點表示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′，反映商品間關(guān)聯(lián)關(guān)系的邊集依賴于EKG中描述的領(lǐng)域知識體系和用戶行為記錄中蘊含的知識。

2 關(guān)聯(lián)查詢模型的構(gòu)建

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

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

若將EKG中的所有商品作為節(jié)點構(gòu)建CQBN，則需很大的時間代價，不但不符合實際要求，而且對于KG的關(guān)聯(lián)查詢處理也沒有必要。對此，本文只考慮與關(guān)聯(lián)查詢中給定商品節(jié)點集Q具有較高相關(guān)度的商品節(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可能關(guān)聯(lián)的商品節(jié)點集Q′。例如，對于圖1中的EKG，考慮1步鄰居，用戶u0的購物記錄為Q={p1,p2,p3}，Q的可能關(guān)聯(lián)節(jié)點集為Q′={p4,p5,p6}。

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

(1)

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

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

4.resultEmit←user.map{x=>

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

6.var keyValue /*存儲中間結(jié)果*/

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在最壞情況下的時間復(fù)雜度為O(nm)。針對實際中規(guī)模較大的KG，將通過實驗測試算法的有效性。

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

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

(2)

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

算法2

輸入：商品節(jié)點集V、用戶行為記錄集D、從EKG中抽取的關(guān)聯(lián)關(guā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中各子集所對應(yīng)子圖的MDL分值，最壞的情況是計算所有邊的MDL分值，其中F(G′|D)的計算時間隨D中的記錄數(shù)線性增長[19]。因此，若G0中有l(wèi)個節(jié)點，且D中包括k條用戶行為記錄，則算法2在最壞情況下的時間復(fù)雜度為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)可歸結(jié)為對Pr(X=k,(X)=j)和Pr((X=j))的計算。本文給出基于Spark的CPT計算方法，算法中的Map階段記錄每條用戶的行為，若包括節(jié)點(X)，則輸出(X),1和(X).union(X),1；Reduce階段對Map結(jié)果聚集后再進行處理，分別計算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的算法時間復(fù)雜度取決于Map函數(shù)，其中包含的FOR循環(huán)對CQBN中的每個節(jié)點進行處理，因此算法的時間復(fù)雜度為O(kn)，其中k為用戶行為記錄數(shù)，n為CQBN中節(jié)點的個數(shù)。

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

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

算法4

輸入：G=(V,E,Pr)，為第3章構(gòu)建的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中商品存在關(guān)聯(lián)關(guān)系的商品及其相應(yīng)的關(guān)聯(lián)強度，并按照關(guān)聯(lián)強度排序，得到相關(guān)的前k個商品,關(guān)聯(lián)強度對。Gibbs采樣算法的收斂性(已在文獻[20]中進行了分析)從理論上保證了算法4的有效性。

4 實驗結(jié)果

為了測試本文所提方法的有效性，采用淘寶網(wǎng)2015年11月18日～12月18日的用戶行為記錄數(shù)據(jù)作為實驗數(shù)據(jù)集，包括20 000個用戶、620 918件商品和23 291 027條用戶行為記錄[21]，基于現(xiàn)有的KG構(gòu)建方法構(gòu)建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 有效性測試

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

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

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

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

4.2 效率測試

為了測試EKG中商品關(guān)聯(lián)關(guā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í)行時間?？梢婋S著KG規(guī)模的增大，鄰居步數(shù)越大，執(zhí)行時間越長，而且算法1的執(zhí)行時間隨著KG規(guī)模和鄰居步數(shù)的增大線性增長，說明算法1能夠有效處理大規(guī)模KG。

以6步鄰居節(jié)點作為關(guān)聯(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通過用戶行為記錄構(gòu)建CQBN，測試用戶行為記錄數(shù)據(jù)規(guī)模分別為1.1 GB，2.2 GB，3.2 GB，4.4 GB，5.5 GB時，不同計算節(jié)點下CQBN構(gòu)建方法的執(zhí)行時間、加速比和并行效率。圖14所示為隨著用戶行為記錄數(shù)據(jù)規(guī)模的增大，不同Worker數(shù)量下CQBN構(gòu)建方法的執(zhí)行時間?？梢?，隨著用戶行為記錄數(shù)據(jù)規(guī)模的增大，Worker數(shù)量越多，CQBN構(gòu)建方法的執(zhí)行時間越短，而且隨用戶行為記錄數(shù)據(jù)規(guī)模的增大線性增長，說明本文方法能夠很好地處理海量數(shù)據(jù)。

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

5 結(jié)束語

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

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