貝葉斯網絡結構學習的雙重K2算法

李曉晴，于海征

(新疆大學數學與系統科學學院，烏魯木齊 830046)

貝葉斯網絡是概率論與圖論相結合的產物，能夠在復雜領域進行不確定性推理和數據分析[1]。近年來，貝葉斯網絡已被應用于故障監測[2-4]、風險分析[5-7]、決策支持[8-9]、醫學診斷[10]和信息檢索[11]等不同的復雜領域。

貝葉斯網絡結構學習是通過學習給定樣本，從大量結構中輸出適應度最高的網絡結構。傳統的貝葉斯網絡結構學習方法大致分為三類：基于依賴分析的方法、基于評分搜索的方法和基于混合搜索的方法。其中，基于依賴分析的方法：通過條件獨立性假設或專家先驗知識得到節點間的相關性，從而構建對應的網絡結構。該方法常采用卡方檢驗或互信息衡量節點間的相關性，缺點是無法判斷因果關系的方向。基于評分搜索的方法：給定評分函數，利用搜索算法取評分最優的網絡結構。評分函數主要包括BD(Bayesian dirichlet)評分、BIC(Bayesian information criterion)評分和MDL(minimum description length)評分等；搜索算法主要包括GS(greedy search)算法、HC(hill-climbing)算法和K2算法等；該方法的缺點是復雜度較高且易陷入局部最優。基于混合搜索的方法：利用條件獨立性檢驗縮小搜索空間，結合評分搜索方法得到最優網絡結構。典型算法有：MMHC(max-min hill-climbing,MMHC)算法、稀疏候選算法等；由于結合了前兩種方法的優勢，因此能夠有效搜索解空間內最有潛力的區域，進而提高網絡學習的精度和效率。

K2算法作為一種經典結構學習算法，已得到了廣泛應用，該算法將節點序作為重要參數輸入，而節點序的選取強烈影響K2算法的學習效果。文獻[12]總結了6種學習節點序的方法：SORDER(sequential ordering)算法、因子分析、熵、互信息、條件熵和評分方法，將得到的節點序作用于K2算法進行結構學習，分析得到的網絡結構，從而對比學習節點序方法的優劣。因此如何尋找高質量的節點序具有重要研究價值。

近年來，涌現出許多針對節點序的研究方法，根據節點序的獲取方式可以分為先驗節點序和學習節點序。

先驗節點序的方法：需要專家提供節點的相關知識作為結構調整。文獻[7]通過相關性分析得到節點序，結合K2算法得到初始網絡結構，最后根據專家先驗知識修正初始結構得到最優結果。文獻[13]提出分組并行化學習，同時基于先驗節點序，避免執行環檢測；文獻[14]運用相關性分析和先驗知識得到先驗節點序，再結合K2算法進行結構學習；文獻[15]利用重構先驗信息構建初始網絡結構，改進模擬退火算法的鄰域求解方法，以求得網絡的最優結構。這類方法降低了計算復雜度，但要求高質量的先驗節點序，很多情況下，尤其是高維變量很難獲得精確的先驗節點序。

學習節點序的方法：需要從數據中自動學習優質節點序，結合結構學習算法構建最優模型。通過搜索最大生成樹(maximum weight spanning tree,MWST)得到不同的節點序：文獻[16]的變量排序算法，將入度為0的節點添加到拓撲排序表末尾，移除相關的邊；重復上述過程，直至所有節點都被添加到排序表中；文獻[17]采用蟻群優化(ant colony optimization，ACO)搜索最大生成樹，獲得了節點序；文獻[18]通過帶環監測的深度優先搜索算法得到節點序；文獻[19]構建定量評價節點序的適應度函數，通過提出混合交叉策略和孤立節點處理機制，同時利用動態學習因子和倒置變異策略，提升了遺傳算法節點序尋優的性能，從而得到了高質量的節點序。

基于構造的初始網絡結構學習節點序，文獻[20]在強連通分量圖中采用精確搜索方法得到最佳節點序；文獻[21]提出了CMI-PK2(conditional mutual information and probability jumping)算法中利用條件互信息得到初始節點序；文獻[22]提出了基于節點影響度的變量序調整方法；文獻[23]在文獻[19]的基礎上結合混合交叉策略和種群規?？s減機制對節點序列進行搜索，得到最優節點序；文獻[24]利用改進的Pearl因果效應和BDEU(Bayesian dirichlet equivalent uniform)評分，學習網絡得到節點序；文獻[25]提出了一種基于節點優先級的排序算法，該方法利用MCMC(Monte Carlo simulation and Markov chain)算法生成一些能夠充分擬合觀測值的貝葉斯網絡結構，基于選擇出的結構，使用定義的層級擬合度加權節點排序評分函數獲得所有節點的合理排序，最終得到節點序。這類方法實用性可觀且易于實現，但都存在些許不足。

現基于節點序的研究，提出一種新的混合結構學習算法——雙重K2算法，首先將節點信息作為初始節點序，通過K2算法的評分搜索策略找到每個節點最優的父節點，從而構建鄰接矩陣作為初始結構；之后，在初始網絡結構上利用拓撲排序得到修正后的節點序；最后K2算法通過修正后的節點序學習得到最優的網絡結構。由雙重K2算法得到的網絡結構與標準的網絡結構進行對比，分析結構中的多邊、少邊和反轉邊；同樣，對比其他基于節點序的K2算法進行結構學習。

1 基礎知識

1.1 貝葉斯網絡模型

貝葉斯網絡由網絡結構G和網絡參數P兩部分組成。網絡結構G=(V,E)為有向無環圖(direct acyclic graph,DAG)。其中，節點集合V={X1,X2,…,Xn}，節點Xi為第i個變量，i=1,2,…,n；E={|Xi≠Xj;Xi,Xj∈V}為有向邊集合，邊表示節點Xi和Xj之間具有Xi→Xj的依賴關系。

網絡參數P={p[Xi|pa(Xi)]}為一個條件概率表。給定Xi的父節點集pa(Xi)時，Xi的條件概率分布為p[Xi|pa(Xi)]。貝葉斯網絡滿足馬爾可夫條件：節點Xi在給定其父節點pa(Xi)的條件下獨立于它的所有非后代節點。那么，對于貝葉斯網絡所有節點的聯合概率就可表示為各節點概率的乘積，即

P(X1,X2,…,Xn)=P(X1)P(X2|X1)…

P(Xn|X1,X2,…,Xn-1)

(1)

式(1)中：n為節點總個數；Xi為第i個節點；pa(Xi)為節點Xi的父節點。

貝葉斯網絡實質上就是一個聯合概率分布p(X1,X2,…,Xn)所有條件獨立性的圖形化表示。采用圖的鄰接矩陣dag= (Aij)表示網絡結構，Aij=1表示有向邊由節點Xi指向節點Xj，Aij=0表示節點Xi和節點Xj之間沒有邊連接，每一個鄰接矩陣就代表一個網絡結構。

1.2 K2算法

K2算法是最早、也是最經典的基于評分搜索的結構學習算法，因其在效率和精度上的良好性能，受到諸多學者關注。K2算法的思想是基于給定的先驗節點序，使用貪婪搜索策略尋找評分最大的網絡結構。考慮到計算效率問題，該算法并非是要搜索出評分最高的結構，而是要搜索在給定條件下的最優網絡結構。但K2算法的精度依賴于節點序的優劣，K2算法對節點序的高要求制約了它的適用性，卻極大提高了算法的效率[26]。K2算法中節點序的作用：分辨節點Xi的父節點是否位于節點Xi前，Pred(Xi)為節點Xi前的節點，則定義為[15]

Pred(Xi)=Xj=pa(Xi),j=1,2,…,i-1

(2)

K2算法具體步驟為[27]：①從一個包含所有節點的空圖開始，在搜索過程中按照給定節點序，對每個節點Xi，將排列在節點Xi之前的i-1個節點作為節點Xi的候選父節點，計算該節點與每一個候選父節點構成局部網絡結構的貝葉斯信息準則(Bayesian information criterion，BIC)評分；②將加入之后評分最高的父節點同該父節點未加入之前進行比較：若加入之后的BIC評分高，則將該父節點加入節點Xi的父節點集中，添加該父節點指向節點Xi的邊；若加入之后的BIC評分低，則將該父節點舍棄；③這樣依次循壞，直到加入父節點后得分score[Xi,pa(Xi)]不再增加或者達到了指定的節點入度。

評分函數公式為

(3)

(4)

式中：G為含有n個節點的貝葉斯網絡結構；D為樣本數據集；ri為節點Xi的取值狀態；qi為節點Xi的父節點pa(Xi)的取值狀態；mijk為節點Xi的父節點pa(Xi)取第j(j=1,2,…,qi)個節點時，Xi處于第k種狀態時的樣本個數；BS為網絡結構。

由評分函數可以看出，K2算法具有可分解性，它是對所有節點進行逐一打分，最后得到整個網絡的評分值[26]。在給定節點序的條件下，K2算法可以有效縮減搜索空間，降低計算復雜度。實際研究中，節點序并不容易事先得到，而且K2算法中節點序的容錯性較差，一旦輸入的節點序有違真實結構，那么K2算法的精度就會大大降低[15]。因此，為K2算法提供高質量的節點序具有重要的研究價值。

2 雙重K2算法

2.1 雙重K2算法原理

文獻[27]首先利用MMPC(max-min parents-children)算法確定每個節點的父節點集和子節點集，從而構建出網絡結構的框架，再利用廣度優先搜索得到節點序，利用節點序進行K2算法結構學習，其中MMPC算法首先測試給定Z時節點X和Y的條件獨立性，最后衡量給定Z時節點X和Y的關聯強度。

K2算法的中心思想是：將排列在節點Xi之前的i-1個節點作為節點Xi的候選父節點，使得該節點和其父節點構成的局部網絡結構的BIC評分不斷增加，得到每個節點的最佳父節點，從而在空圖中添加從父節點指向子節點的邊，得到網絡結構。與MMPC算法相比，K2算法效率更快。

拓撲排序[18]是為DAG所有節點生成一個線性序列的過程，它使圖中的任一對節點Xi和Xj，若邊∈E，那么節點Xi在線性排序中位于節點Xj之前。拓撲排序滿足以下條件：每個節點都出現并只出現一次。

基于節點序研究，提出一種新的混合結構學習算法——雙重K2算法。雙重K2算法思想是：①將節點信息作為初始節點序，利用K2算法的評分搜索策略找到每個節點的最優父集，從而構建鄰接矩陣dag作為初始結構；②由于dag中的元素特性(Aij=1表示有向邊由節點Xi指向節點Xj)，在dag中調用拓撲排序得到一個父節點在子節點前的線性排列，則將其作為修正后的節點序；③K2算法的搜索策略是將節點序中節點Xi之前的i-1個節點作為節點Xi的候選父集從而計算BIC評分最優，則由步驟②得到的修正節點序符合該搜索思想，最終K2算法通過該修正節點序學習得到最優的網絡結構。

在3種不同規模的網絡中進行實驗，結果證明：由雙重K2算法得到的修正節點序優于其他節點序學習算法，且對于后續K2算法的結構學習起到積極作用；在精度和效率上，雙重K2算法的學習效果也優于其他對比算法。

2.2 雙重K2算法流程

雙重K2算法流程如圖1所示。

圖1 雙重K2算法流程Fig.1 Double K2 algorithm flow

2.3 雙重K2算法偽代碼

雙重K2算法偽代碼如下。

Step1 構造初始網絡結構。輸入:節點集nodes;節點個數n;節點入度max_in;數據集data輸出:鄰接矩陣dag dag←zeros(n,n); FORiin[1,n]DO ps←[]; j←nodes(i); u←find(clamped(j,:)==0); score←BIC(j,ps,max_in,data(:,u)); WHILElength(ps)≤max_inDO pps←mysetdiff(nodes(1:i-1),ps); nps←length(pps); pscore←zeros(1,nps); FORpiin[1:nps]DO p←pps(pi); pscore←BIC(j,[psp],max_in,data(:,u)); ENDFOR [best_pscore,best_p]←max(pscore); best_p←pps(best_p); IFbest_pscore>scoreDO score←best_pscore; ps←[psbest_p]; ENDIF ENDWHILE IFps≠NULLDO dag(ps,j)←1; ENDIF ENDFOR RETURNdag Step2 拓撲排序得到節點序。輸入:初始網絡結構dag輸出:修正后的節點序order indeg←zeros(1,n); zero_indeg←[]; FORiin[1,n]DO indeg(i)←length(parents(dag,i)); IFindeg(i)==0DO zero_indeg←[izero_indeg]; ENDIF ENDFOR t←1; order←zeros(1,n); WHILEzero_indeg≠NULLDO v←zero_indeg(1); zero_indeg←zero_indeg(2:end); order(t)←v; t←t+1; cs←children(dag,v); FORjin[1:length(cs)]DO c←cs(j); indeg(c)←indeg(c)-1; IFindeg(c)==0DO zero_indeg←[czero_indeg]; ENDIF ENDFOR ENDWHILE RETURNorder

Step3 K2算法結構學習。輸入:經典網絡數據集data;節點取值范圍ns;節點序order;節點入度max_in輸出:最優網絡結構dagK2 dag←zeros(n,n); FORiin[1,n]DO ps←[]; j←order(i); u←find(clamped(j,:)==0); score←BIC(j,ps,max_in,data(:,u)); WHILElength(ps)≤max_inDO pps←mysetdiff(order(1:i-1),ps); nps←length(pps); pscore←zeros(1,nps); FORpiin[1:nps]DO p←pps(pi); pscore←BIC(j,[psp],max_in,data(:,u)); ENDFOR [best_pscore,best_p]←max(pscore); best_p←pps(best_p); IFbest_pscore>scoreDO score←best_pscore; ps←[psbest_p]; ENDIFENDWHILE IFps≠NULLDO dag(ps,j)←1; ENDIF ENDFOR RETURNdagK2

3 實驗

3.1 實驗設置

實驗平臺的基本配置：操作系統Windows10，處理器Intel(R)Core(TM)i5-4210U，主頻2.40 GHz，內存8.00 GB。實驗環境：MATLAB R2019a，使用FullBNT-1.0.7工具箱。

為了評價算法的學習性能，選擇經典的Asia網絡、Insurance網絡和Alarm網絡進行實驗，其網絡信息如表1所示，標準網絡結構如圖2所示。圖2(a)所示的Asia網絡中，各節點為Smoking=1，Bronchitis=2，LungCancer=3，VisitToAsia=4，TB=5，TBorCancer=6，Dys=7，Xray=8；圖2(b)所示的Insurance網絡中，各節點為Age=1，SocioEcon=2，GoodStudent=3，RiskAversion=4，VehicleYear=5，MakeModel=6，Antilock=7，Mileage=8，SeniorTrain=9，DrivingSkill=10，DrivQuality=11，Accident=12，RuggedAuto=13，ThisCarDam=14，CarValue=15，AntiTheft=16，HomeBase=17，Theft=18，ThisCarCost=19，OtherCarCost=20，PropCost=21，OtherCar=22，Airbag=23，Cushioning=24，MedCost=25，ILiCost=26，DrivHist=27；圖2(c)所示的Alarm網絡中，各節點為LVFAILURE=1，HISTORY=2，HYPOVOLEMIA=3，LVEDVOLUME=4，CVP=5，PCWP=6，STROKEVOLUME=7，ERRLOWOUTPUT=8，INTUBATION=9，KINKEDTUBE=10，DISCONNECT=11，MINVOLSET=12，VENTMACH=13，VENTTUBE=14，VENTLUNG=15，VENTALV=16，ARTCO2=17，INSUFFANESTH=18，FIO2=19，PVSAT=20，PULMEMBOLUS=21，SHUNT=22，SAO2=23，ANAPHYLAXIS=24，TPR=25，CATECHOL=26，HR=27，HRBP=28，ERRCAUTER=29，HREKG=30，HRSAT=31，EXPCO2=32，MINVOL=33，PAP=34，PRESS=35，CO=36，BP=37。在仿真實驗中，各網絡的樣本量N= 1 000、3 000、5 000。

表1 標準貝葉斯網絡信息Table 1 Standard Bayesian network information

圖2 標準網絡結構Fig.2 Standard network structure

實驗對比算法為：①HC算法：通過加邊、減邊、轉邊修改初始網絡結構，得到一系列候選網絡結構并計算其評分，最后輸出評分最優的網絡結構；②最大生成樹+拓撲搜索(topologie search,TS)+K2算法：拓撲搜索在最大生成樹上得到節點序，結合K2算法得到最優網絡結構；③最大生成樹+深度優先搜索(depth first search,DFS)+K2算法：深度優先搜索在最大生成樹上得到節點序，結合K2算法得到最優網絡結構；④最大生成樹+廣度優先搜索(breadth first search,BFS)+K2算法：廣度優先搜索在最大生成樹上得到節點序，結合K2算法得到最優網絡結構；⑤雙重K2(double K2)算法。

學習效果的衡量指標為：①錯誤邊，實驗算法學得的網絡結構與標準網絡結構中不一致的邊數，包括缺失邊(missed edge，ME)、多余邊(increased edges,IE)和反轉邊(reversal edges,RE)；②正確邊(correct edges,CE)，實驗算法學得的網絡結構與標準網絡結構中一致的邊數；③準確率，正確邊CE與標準網絡總邊數的比值；④運行時間，實驗算法學習得到最終網絡結構所需時間，單位為s。

比較不同規模和樣本量下，實驗算法學習網絡結構的效果，驗證雙重K2算法的學習優勢。為避免產生隨機效應，實驗過程中每種樣本量隨機生成10次，取結果的平均值進行衡量。

3.2 實驗結果與分析

由節點信息作為初始節點序，利用K2算法的搜索策略構建初始網絡結構。針對初始網絡結構，在1 000組樣本數據的情況下，各網絡利用拓撲排序得到修正后的節點序如表2所示。

表2 修正后的節點序Table 2 Modified node order

雙重K2算法利用修正后的節點序進行結構學習。5種實驗算法的學習結果如圖3、表3所示。

由圖3可知，錯誤邊ME、IE和RE的數值越小越能證明實驗算法的學習結果接近標準網絡結構。

由圖3(a)中Asia網絡的錯誤邊可知：3種樣本量下結果最優的為Double K2算法，其錯誤邊均為ME=1，IE=0，RE=0；樣本量為1 000時，結果最差的為HC算法，其錯誤邊ME=4，IE=4，RE=3和MWST+DFS+K2算法，其錯誤邊ME=3，IE=6，RE=2。樣本量為300 0時，結果最差的為MWST+TS+K2算法，其錯誤邊ME=5，IE=7，RE=3。樣本量為500 0時，結果最差的為HC算法，其錯誤邊ME=5，IE=7，RE=3。

由圖3(b)中Insurance網絡的錯誤邊可知：3種樣本量下結果最優的為Double K2算法，其錯誤邊分別為ME=13，IE=2，RE=0；ME=8，IE=1，RE=0；ME=9，IE=0，RE=0。樣本量為1 000時，結果最差的為MWST+BFS+K2算法，其錯誤邊ME=29，IE=21，RE=10。樣本量為3 000時，結果最差的為MWST+DFS+K2算法，其錯誤邊ME=26，IE=24，RE=12。樣本量為5 000時，結果最差的為MWST+DFS+K2算法，其錯誤邊ME=27，IE=26，RE=12。

由圖3(c)中Alarm網絡的錯誤邊可知：3種樣本量下結果最優的為Double K2算法，其錯誤邊ME=1，IE=6，RE=0；ME=1，IE=2，RE=0；ME=1，IE=2，RE=0。樣本量為1 000時，結果最差的為MWST+DFS+K2算法，其錯誤邊ME=25，IE=38，RE=21。樣本量為3 000時，結果最差的為HC算法，其錯誤邊ME=28，IE=39，RE=26。樣本量為5 000時，結果最差的為MWST+DFS+K2算法，其錯誤邊ME=24，IE=41，RE=22。

圖3 網絡的錯誤邊Fig.3 Wrong edges of network

由表3可知，正確邊CE和準確率的值越大越能證明實驗算法的學習結果接近標準網絡結構。Asia網絡學習的正確邊CE和準確率：3種樣本量下結果最優的為Double K2算法，其CE=7，準確率=0.875 0；樣本量為1 000時，結果最差的為HC算法，其CE=4，準確率=0.500 0；樣本量為3 000時，結果最差的為MWST+TS+K2算法，其CE=3，準確率=0.375 0；樣本量為5 000時，結果最差的為HC算法，其CE=3，準確率=0.375 0。

表3 網絡學習結果對比Table 3 Comparison of networks learning results

Insurance網絡學習的正確邊CE和準確率：3種樣本量下結果最優的為Double K2算法，其CE=39，準確率=0.750 0；CE=44，準確率為0.846 2；CE=43，準確率為0.826 9。樣本量為1 000時，結果最差的為MWST+BFS+K2算法，其CE=23，準確率=0.442 3；樣本量為3 000時，結果最差的為MWST+DFS+K2算法，其CE=26，準確率=0.500 0；樣本量為5 000時，結果最差的為MWST+DFS+K2算法，其CE=25，準確率=0.480 8。

Alarm網絡學習的正確邊CE和準確率：3種樣本量下結果最優的為Double K2算法，其CE=45，準確率=0.978 3。樣本量為1 000時，結果最差的為HC算法，其CE=19，準確率=0.413 0；樣本量為3 000時，結果最差的為HC算法，其CE=18，準確率=0.391 3；樣本量為5 000時，結果最差的為MWST+DFS+K2算法，其CE=22，準確率=0.478 3。

由表3可知，運行時間的值越小越能證明實驗算法的學習結果耗費時間少。Asia網絡學習的運行時間：樣本量為1 000時，結果最優的為MWST+DFS+K2算法，其值為7.256 0；樣本量為300 0時，結果最優的為MWST+TS+K2算法，其值為13.502 0；樣本量為5 000時，結果最優的為MWST+DFS+K2算法，其值為20.450 0。

Insurance網絡學習的運行時間：樣本量為1 000時，結果最優的為MWST+DFS+K2算法，其值為31.301 0；樣本量為3 000時，結果最優的為MWST+BFS+K2算法，其值為59.049 0；樣本量為5 000時，結果最優的為MWST+TS+K2算法，其值為88.885 0。

Alarm網絡學習的運行時間：樣本量為1 000時，結果最優的為MWST+BFS+K2算法，其值為49.904 0；樣本量為3 000時，結果最優的為MWST+TS+K2算法，其值為88.258 0；樣本量為5 000時，結果最優的為MWST+TS+K2算法，其值為136.512 0。

通過以上實驗可以看出，①對于HC算法，其學習效果不如基于節點序的K2算法，且耗費時間長，準確率低；②MWST+TS+K2算法、MWST+DFS+K2算法、MWST+BFS+K2算法和雙重K2算法均為基于不同節點序進行結構學習的K2算法，可以對比發現不同節點序對于結構學習效果的影響；③經過結果分析，在準確度和效率上，雙重K2算法效果優于其他對比算法。

綜上所述，K2算法的精度取決于節點序的優劣。通過大量實驗表明，與其他算法相比，雙重K2算法具有更強的學習性能，并且該算法得到的修正節點序非常接近于真實節點序，使得學習效果遠遠優于其他節點序的K2算法，實驗證明了雙重K2算法在貝葉斯網絡結構學習方面的有效性。

4 結論

(1)傳統基于評分搜索的算法通過降低收斂速度來提高精度，或者通過降低精度來提高收斂速度，難以同時優化收斂速度和精度。K2算法作為結構學習的經典算法之一，一方面，由于缺少先驗信息很難確定節點序，導致該算法在應用上的局限性；另一方面，由于貪婪搜索策略導致該算法容易陷入局部最優。但在給定節點序的前提下進行結構學習，就會減少此類問題產生。學習K2算法的節點序相當于將貝葉斯網絡結構的搜索空間縮減為節點序搜索空間，且節點序搜索避免了環結構的產生，所以在節點序空間上進行結構學習可以有效降低運算成本。

(2)所提出的雙重K2算法不僅解決先驗節點序的問題，而且保證算法的準確性。在3種規模不同的網絡實驗中，與HC算法和其他基于節點序的K2算法相比，雙重K2算法的優勢更加突出。

(3)未來的研究工作包括：結構學習中對于孤立節點的處理，以及在大型網絡中對于節點序的優化學習。