牛艷飛，馬 潔

(北京信息科技大學(xué)自動化學(xué)院，北京 100192)

1 引言

貝葉斯網(wǎng)絡(luò)(Bayesian Network，BN)經(jīng)常用于處理涉及不確定知識的問題，是一種綜合了圖論和概率論的圖模型，既可以定性地表示節(jié)點之間的因果關(guān)系，又可以定量地描述變量間的聯(lián)合概率分布。在數(shù)據(jù)挖掘領(lǐng)域，貝葉斯網(wǎng)絡(luò)一直是眾多學(xué)者的研究重點，并且在各領(lǐng)域均有重要的應(yīng)用，如故障溯源[1]、醫(yī)療診斷[2]、金融分析[3]等。

貝葉斯網(wǎng)絡(luò)的構(gòu)建主要由結(jié)構(gòu)學(xué)習(xí)和參數(shù)學(xué)習(xí)兩部分組成，其中結(jié)構(gòu)學(xué)習(xí)因其對先驗知識的依賴而成為貝葉斯網(wǎng)絡(luò)構(gòu)建的一大難點[4]。本文針對貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)，提出一種混合部分互信息量和改進差分進化算法的PMI-DE算法，該算法首先基于變量之間的部分互信息描述網(wǎng)絡(luò)節(jié)點的關(guān)聯(lián)度并構(gòu)建初始種群，再通過引入動態(tài)因子改進差分進化算法的交叉策略，平衡算法的全局收斂和局部搜索能力，從而得到最優(yōu)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)。最后在仿真中將該算法與遺傳算法和爬山算法進行對比，分析該算法的優(yōu)劣。

2 貝葉斯網(wǎng)絡(luò)

2.1 貝葉斯網(wǎng)絡(luò)的概念

貝葉斯網(wǎng)絡(luò)[5-6]由變量之間的有向邊和節(jié)點概率表構(gòu)成，其數(shù)學(xué)描述可以用BN=來表示。

其中G=是一個二進制矩陣，用來表示貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)。X={x1，x2，…，xn}決定矩陣的大小，代表貝葉斯網(wǎng)絡(luò)中的各個節(jié)點變量，E={a11…aij…ann}(aij=0or1)決定矩陣中的元素，反映了網(wǎng)絡(luò)節(jié)點xi和xj之間的因果關(guān)系。圖1為一個貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的矩陣表達。

圖1 貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)示意圖

P是貝葉斯網(wǎng)絡(luò)中各個節(jié)點xi∈X的聯(lián)合概率分布P(xi|Pa(xi))，用來定量描述各個節(jié)點之間的依賴關(guān)系，其中Pa(xi)為xi在網(wǎng)絡(luò)結(jié)構(gòu)G中的父節(jié)點集合。貝葉斯網(wǎng)絡(luò)全節(jié)點之間的聯(lián)合概率分布如式(1)

(1)

2.2 貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)

從數(shù)據(jù)集D={d1，d2，d3…dn}中尋找一個與變量關(guān)系匹配度最高的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)是結(jié)構(gòu)學(xué)習(xí)的主要目標，但是該過程的計算復(fù)雜度會隨著節(jié)點的個數(shù)增多而成為一個無法進行精確求解的NP-hard問題[7]。式(2)展示了變量節(jié)點個數(shù)與貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)個數(shù)之間的關(guān)系

(2)

可見想要通過遍歷的方式對貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)進行精確查找是不可行的，對此，國內(nèi)外已經(jīng)有很多貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)尋優(yōu)方法，比較主流的方法是通過合理的結(jié)構(gòu)評價函數(shù)和啟發(fā)式搜索算法對網(wǎng)絡(luò)結(jié)構(gòu)進行尋優(yōu)，最終得到準確的網(wǎng)絡(luò)結(jié)構(gòu)。Cooper等人[8]提出的K2算法利用節(jié)點序縮小了搜索空間并且可以避免產(chǎn)生非法結(jié)構(gòu)，但是K2算法嚴重依賴于節(jié)點序的正確性；Tsamardinos等人[9]提出了最大最小爬山算法(Max-Min Hill-Climbing，MMHC)，先通過獨立性測試縮小搜索空間，再利用爬山算法進行遍歷確定貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)，該方法得到了比較廣泛的應(yīng)用；Saoussen[10]等提出PSO-K2算法，通過粒子群算法對節(jié)點的順序進行尋優(yōu)，再將最優(yōu)結(jié)果與K2算法結(jié)合得到貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)；劉浩然等[11]提出MAK(MWST-ACO-K2)算法，該算法融合最大支撐樹和蟻群算法搜索節(jié)點序，在處理小型網(wǎng)絡(luò)時可取得較理想的結(jié)果；魏中強等[12]提出了CMI-PK2算法，其先通過條件互信息得到節(jié)點序，再將K2算法的搜索策略進行改進來提高學(xué)習(xí)的速度，得到了較好的學(xué)習(xí)效果。

本文提出了一種基于部分互信息和差分進化算法的混合算法(PMI-DE算法)，該算法首先利用部分互信息度量網(wǎng)絡(luò)節(jié)點之間的相關(guān)性，并在此基礎(chǔ)上產(chǎn)生初始種群，然后利用差分進化算法對貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)進行尋優(yōu)，通過引入動態(tài)交叉因子來改進交叉策略，使得算法能夠自適應(yīng)地選擇交叉對象，最終得到最優(yōu)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)。

3 PMI-DE算法研究

3.1 部分互信息

互信息是信息論中的一個重要概念，經(jīng)常被用來度量隨機變量之間的相關(guān)性，若已知兩個隨機變量X={x1，x2，x3…xn}Y={y1，y2，y3…ym}，則X和Y之間的互信息如式(3)

(3)

式中，p(x)表示X的先驗概率，p(x，y)為X和Y的聯(lián)合概率。

條件互信息用來衡量隨機變量X和Y在條件Z下的相關(guān)關(guān)系。定義如式(4)所示

(4)

式中，p(x|z)p(y|z)分別為X、Y在條件Z下的先驗概率，p(x，y|z)為X和Y在條件Z下的聯(lián)合概率，p(x，y，z)為X、Y、Z的聯(lián)合概率。

雖然互信息和條件互信息都能夠度量變量之間的相關(guān)性，但是互信息往往會過高的估計兩個隨機變量之間的相關(guān)性，以此為依據(jù)構(gòu)建的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)會產(chǎn)生過多的冗余邊，而條件互信息則會過低的估計兩個隨機變量之間的相關(guān)性，這將導(dǎo)致貝葉斯網(wǎng)絡(luò)出現(xiàn)嚴重的邊缺失現(xiàn)象，為了平衡互信息和條件互信息的這種缺陷，Zhao等人[13]提出了使用部分互信息(part mutual information，PMI)來度量隨機變量之間的相關(guān)性。

已知隨機變量X和Y在條件Z下獨立表示為式(5)

p(x|z)p(y|z)=p(x，y|z)

(5)

則X和Y在條件Z下的部分獨立性定義如式(6)

p*(x|z)p*(y|z)=p(x，y|z)

(6)

PMI(X，Y|Z)由式(7)所示的部分獨立性和KL距離(Kullback-Leibler divergence)[14]得出，定義如下

PMI(X，Y|Z)=

D(p(x，y，z)||p*(x|z)p*(y|z)p(z))

(7)

式中p(x，y，z)為X、Y、Z的聯(lián)合概率，D(p(x，y，z)||p*(x|z)p*(y|z)p(z))表示p(x，y，z)到p*(x|z)p*(y|z)p(z)的KL距離。PMI(X，Y|Z)也可以寫成式(8)的形式

(8)

3.2 差分進化算法改進

差分進化算法(Differential Evolution，DE)是由Storn等人[15]于1997年提出的，其主要包含變異、交叉、選擇三大部分。與遺傳算法的不同之處在于其變異操作是從種群中隨機挑選兩個個體，將差作為第三個個體的變化來源進行變異。該算法主要用于解決連續(xù)變量的全局尋優(yōu)問題，但是貝葉斯網(wǎng)絡(luò)由離散的二進制矩陣表示，為了將差分進化算法應(yīng)用于結(jié)構(gòu)學(xué)習(xí)，將算法的變異和交叉算子進行了相應(yīng)的修改。

3.2.1 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)是演化算法的導(dǎo)向，用來衡量當(dāng)前的迭代過程中最優(yōu)的網(wǎng)絡(luò)結(jié)構(gòu)是否滿足設(shè)定要求。評價貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的函數(shù)根據(jù)原理可以劃分為兩類，一是基于貝葉斯統(tǒng)計的評分函數(shù)，如K2評分、BDeu評分；二是基于信息論的評分函數(shù)，如MIT評分[16]。本文采用可分解的BIC評分函數(shù)[17]度量網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)劣程度，其定義如式(9)

(9)

BIC((xi，pa(xi))|D)

(10)

則有

(11)

由式(10)和式(11)可見，BIC評分是可分解的，但是BIC評分一般為負值，為了便于比較和盡可能保留最終結(jié)果的有效數(shù)字，本文定義適應(yīng)度函數(shù)如式(12)

(12)

3.2.2 初始種群的構(gòu)建

初始種群的確定是算法的重要組成部分，為了挑選優(yōu)秀的初始種群，本文首先通過對n個節(jié)點利用部分互信息進行打分，得到節(jié)點相關(guān)關(guān)系權(quán)重矩陣W={w11，w12，w13…wij…wnn}，其中wij的計算如式(13)

(13)

其中x∈xi，y∈xj表示節(jié)點xi和xj的類別，Z表示類別向量

Gi={g11，g12，g13…gij…gnn}

(14)

該過程首先利用節(jié)點之間的相關(guān)關(guān)系權(quán)重矩陣，限制了初始種群中冗余邊和缺失邊的數(shù)量，同時概率矩陣保證了初始種群的多樣性，為后續(xù)的變異和交叉操作提供了可靠的搜索基礎(chǔ)。

3.2.3 變異算子

與連續(xù)變量的尋優(yōu)不同，在貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的尋優(yōu)中，個體是二進制矩陣，傳統(tǒng)的變異算子無法直接應(yīng)用，故設(shè)計了針對于二進制矩陣的變異算子。

首先從初始種群中隨機選擇一個個體Gj={g11，g12，g13…gij…gnn}，j=1，…，N，將Gj變化成為當(dāng)代種群的最優(yōu)結(jié)構(gòu)Gbest需要進行的操作用轉(zhuǎn)移矩陣Mov來表示

Mov=Gbest-Gj={m11，m12，m13…mij…mnn}

(15)

其中mij代表了轉(zhuǎn)移過程的三種操作

(16)

將待變異的個體按照轉(zhuǎn)移矩陣進行變異，并由變異概率cp進行控制：

(17)

變異過程中網(wǎng)絡(luò)結(jié)構(gòu)中會產(chǎn)生無意義的gij=-1元素，其代表了該結(jié)構(gòu)變異之前此處無邊，故不需要進行轉(zhuǎn)移矩陣中的刪除邊操作，將其置零，最終得到變異之后的個體Ui，i=1，…，N

3.2.4 交叉算子

交叉操作的目的是在個體的鄰域進行局部搜索，傳統(tǒng)差分進化算法的交叉操作全程由一個固定的交叉概率控制，在算法中期極易陷入局部最優(yōu)，為了平衡算法的全局尋優(yōu)和局部搜索能力，本文引入了自適應(yīng)的動態(tài)交叉因子，其控制待交叉?zhèn)€體的交叉對象來源Hi。動態(tài)因子計算如下

a=t/Tmax

(18)

式中t為當(dāng)前迭代次數(shù)，Tmax為最大迭代次數(shù)，每個個體的交叉對象選擇由a來控制

(19)

交叉過程采用兩點交叉方式，即從交叉對象中隨機選取兩個元素，與待交叉?zhèn)€體進行元素互換，得到交叉后的個體Vi，i=1，…，N。

(20)

3.3 非法結(jié)構(gòu)修復(fù)

算法的變異和交叉操作可能給網(wǎng)絡(luò)結(jié)構(gòu)帶來部分非法結(jié)構(gòu)，例如雙向邊以及環(huán)狀結(jié)構(gòu)。為了保證迭代過程中個體的正確性，必須在變異和交叉操作后對個體進行非法結(jié)構(gòu)判斷和修復(fù)[18]，修正的步驟如圖所示：

圖2 網(wǎng)絡(luò)結(jié)構(gòu)修復(fù)流程圖

3.4 算法偽代碼

PMI-DE算法的偽代碼如下：

PMI-DE Algorithm

Input：Data set、N、cp、hp、Tmax

Output：Gbest

Step1：Initialization

1)constructs the partial mutual information weight matrix W by Formula (13)

2)construct the edge existence probability matrix P

3)for i=1：N

4) Generate individuals Gi

5) calculate F(Gi)

6) end

7) Find the best individual Gbest(0)，(F(Gbest)=Max(F(Gi)))

8) Pbest=G(0)

Step2：evolution

9) While t < Tmax

10) for i=1：N

11) if rand

12) Mov=Gbest(t)-Gi(t)

13) Ui(t)=Gi(t)+Mov

14) illegal structure restoration

15) end

16) Calculate the dynamic factoraand Select crossover Hi(t) by Formula (18) and (19)

17) Two points cross to produce Vi(t) by Formula (20)

18) illegal structure restoration

Step3：update

19) if F(Vi(t))

20) Gi(t+1)=Vi(t)

21) else

22) Gi(t+1)=Gi(t)

23) end

26) end

27)end

4 仿真研究

為了驗證PMI-DE算法的有效性，本節(jié)以小型Asia網(wǎng)絡(luò)和中型Car網(wǎng)絡(luò)為模型，分別生成樣本數(shù)為500、1000、2000的數(shù)據(jù)集，與遺傳算法(GS)、爬山算法(HC)進行比較，分析PMI-DE算法的優(yōu)缺點。

為了評價不同的算法在相同的數(shù)據(jù)集中所得到的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)劣程度，本文采用海明距離來度量算法所得的網(wǎng)絡(luò)結(jié)構(gòu)與真實結(jié)構(gòu)的差異程度，海明距離的計算如式(21)

H(G)=A(G)+D(G)+R(G)

(21)

式中，A(G)表示冗余邊，D(G)表示缺失邊，R(G)表示反向邊。網(wǎng)絡(luò)結(jié)構(gòu)的海明距離越小，說明該結(jié)構(gòu)與真實的網(wǎng)絡(luò)結(jié)構(gòu)相似度越高，進而說明了算法能夠更加準確地從數(shù)據(jù)集中學(xué)習(xí)到貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)。

實驗采用Matlab軟件平臺，運行環(huán)境：操作系統(tǒng)Windows 10，處理器為Intel(R) Core(TM) i7-8750H，主頻2.20GHz，內(nèi)存8GB。PMI-DE算法的相關(guān)參數(shù)初始化設(shè)置如下：種群規(guī)模：50，變異概率為0.5，交叉概率為0.5，最大迭代次數(shù)為30次。為了保證算法結(jié)果的有效性，分別將三種算法獨立運行10次，并取平均值記錄，結(jié)果如下。

表1 Asia網(wǎng)絡(luò)樣本錯誤邊對比

表2 Car網(wǎng)絡(luò)樣本錯誤邊對比

圖3 Asia網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)漢明距離對比

圖4 Car網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)漢明距離對比

可見，在訓(xùn)練數(shù)據(jù)相同的情況下，PMI-DE算法所得的網(wǎng)絡(luò)結(jié)構(gòu)漢明距離最小，即得到的網(wǎng)絡(luò)結(jié)構(gòu)最優(yōu)，說明了PMI-DE算法在對網(wǎng)絡(luò)結(jié)構(gòu)進行尋優(yōu)時具有比較高的精度。

為了測試PMI-DE算法的學(xué)習(xí)性能，選擇Asia網(wǎng)絡(luò)樣本數(shù)量為500、1000、2000的數(shù)據(jù)集，三種算法分別運行10次取平均值，將PMI-DE算法的迭代速度和最佳評分值與其它兩種算法進行對比。結(jié)果見表3和圖4。

表3 樣本數(shù)為1000的數(shù)據(jù)集中學(xué)習(xí)性能比較

圖5 三種算法運行效率對比

由表3和圖5可以看出，當(dāng)樣本數(shù)較小時，三種算法的計算速度相當(dāng)，但是當(dāng)樣本數(shù)較大時，遺傳算法的計算速度表現(xiàn)出明顯的不足，這是因為遺傳算法在迭代的過程中容易陷入局部最優(yōu)，導(dǎo)致在要求精度的前提下需要更多的迭代次數(shù)，PMI-DE算法和爬山算法的計算時間相當(dāng)，但是由最優(yōu)評分值可以看出在精度上PMI-DE算法要更加精確。

5 結(jié)論

從數(shù)據(jù)中學(xué)習(xí)貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)是一個棘手的問題，本文提出一種結(jié)合部分互信息和差分進化算法的混合學(xué)習(xí)方法，該算法以節(jié)點之間的部分互信息為基礎(chǔ)構(gòu)建初始種群，縮小了搜索空間，提升了算法的執(zhí)行效率，再通過引入動態(tài)因子改進傳統(tǒng)差分進化算法的交叉算子，使算法能夠自適應(yīng)地平衡全局尋優(yōu)和局部搜索，防止算法陷入局部最優(yōu)。在標準的貝葉斯網(wǎng)絡(luò)中進行仿真，結(jié)果表明該算法有良好的尋優(yōu)效果和運行效率，為貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)提供了新的混合方法。