基于差分進(jìn)化策略的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法

牛艷飛，馬 潔

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

1 引言

貝葉斯網(wǎng)絡(luò)(Bayesian Network，BN)經(jīng)常用于處理涉及不確定知識(shí)的問(wèn)題，是一種綜合了圖論和概率論的圖模型，既可以定性地表示節(jié)點(diǎn)之間的因果關(guān)系，又可以定量地描述變量間的聯(lián)合概率分布。在數(shù)據(jù)挖掘領(lǐng)域，貝葉斯網(wǎng)絡(luò)一直是眾多學(xué)者的研究重點(diǎn)，并且在各領(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í)因其對(duì)先驗(yàn)知識(shí)的依賴而成為貝葉斯網(wǎng)絡(luò)構(gòu)建的一大難點(diǎn)[4]。本文針對(duì)貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)，提出一種混合部分互信息量和改進(jìn)差分進(jìn)化算法的PMI-DE算法，該算法首先基于變量之間的部分互信息描述網(wǎng)絡(luò)節(jié)點(diǎn)的關(guān)聯(lián)度并構(gòu)建初始種群，再通過(guò)引入動(dòng)態(tài)因子改進(jìn)差分進(jìn)化算法的交叉策略，平衡算法的全局收斂和局部搜索能力，從而得到最優(yōu)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)。最后在仿真中將該算法與遺傳算法和爬山算法進(jìn)行對(duì)比，分析該算法的優(yōu)劣。

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

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

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

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

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

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

(1)

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

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

(2)

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

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

3 PMI-DE算法研究

3.1 部分互信息

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

(3)

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

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

(4)

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

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

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

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

(5)

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

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

(6)

PMI(X，Y|Z)由式(7)所示的部分獨(dú)立性和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)也可以寫(xiě)成式(8)的形式

(8)

3.2 差分進(jìn)化算法改進(jìn)

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

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

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

(9)

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

(10)

則有

(11)

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

(12)

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

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

(13)

其中x∈xi，y∈xj表示節(jié)點(diǎn)xi和xj的類(lèi)別，Z表示類(lèi)別向量

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

(14)

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

3.2.3 變異算子

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

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

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

(15)

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

(16)

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

(17)

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

3.2.4 交叉算子

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

a=t/Tmax

(18)

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

(19)

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

(20)

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

算法的變異和交叉操作可能給網(wǎng)絡(luò)結(jié)構(gòu)帶來(lái)部分非法結(jié)構(gòu)，例如雙向邊以及環(huán)狀結(jié)構(gòu)。為了保證迭代過(guò)程中個(gè)體的正確性，必須在變異和交叉操作后對(duì)個(gè)體進(jìn)行非法結(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 仿真研究

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

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

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

(21)

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

實(shí)驗(yàn)采用Matlab軟件平臺(tái)，運(yùn)行環(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é)果的有效性，分別將三種算法獨(dú)立運(yùn)行10次，并取平均值記錄，結(jié)果如下。

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

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

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

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

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

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

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

圖5 三種算法運(yùn)行效率對(duì)比

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

5 結(jié)論

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