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

李曉晴，于海征

(新疆大學(xué)數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院，烏魯木齊 830046)

貝葉斯網(wǎng)絡(luò)是概率論與圖論相結(jié)合的產(chǎn)物，能夠在復(fù)雜領(lǐng)域進(jìn)行不確定性推理和數(shù)據(jù)分析[1]。近年來(lái)，貝葉斯網(wǎng)絡(luò)已被應(yīng)用于故障監(jiān)測(cè)[2-4]、風(fēng)險(xiǎn)分析[5-7]、決策支持[8-9]、醫(yī)學(xué)診斷[10]和信息檢索[11]等不同的復(fù)雜領(lǐng)域。

貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)是通過(guò)學(xué)習(xí)給定樣本，從大量結(jié)構(gòu)中輸出適應(yīng)度最高的網(wǎng)絡(luò)結(jié)構(gòu)。傳統(tǒng)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法大致分為三類：基于依賴分析的方法、基于評(píng)分搜索的方法和基于混合搜索的方法。其中，基于依賴分析的方法：通過(guò)條件獨(dú)立性假設(shè)或?qū)＜蚁闰?yàn)知識(shí)得到節(jié)點(diǎn)間的相關(guān)性，從而構(gòu)建對(duì)應(yīng)的網(wǎng)絡(luò)結(jié)構(gòu)。該方法常采用卡方檢驗(yàn)或互信息衡量節(jié)點(diǎn)間的相關(guān)性，缺點(diǎn)是無(wú)法判斷因果關(guān)系的方向?；谠u(píng)分搜索的方法：給定評(píng)分函數(shù)，利用搜索算法取評(píng)分最優(yōu)的網(wǎng)絡(luò)結(jié)構(gòu)。評(píng)分函數(shù)主要包括BD(Bayesian dirichlet)評(píng)分、BIC(Bayesian information criterion)評(píng)分和MDL(minimum description length)評(píng)分等；搜索算法主要包括GS(greedy search)算法、HC(hill-climbing)算法和K2算法等；該方法的缺點(diǎn)是復(fù)雜度較高且易陷入局部最優(yōu)。基于混合搜索的方法：利用條件獨(dú)立性檢驗(yàn)縮小搜索空間，結(jié)合評(píng)分搜索方法得到最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu)。典型算法有：MMHC(max-min hill-climbing,MMHC)算法、稀疏候選算法等；由于結(jié)合了前兩種方法的優(yōu)勢(shì)，因此能夠有效搜索解空間內(nèi)最有潛力的區(qū)域，進(jìn)而提高網(wǎng)絡(luò)學(xué)習(xí)的精度和效率。

K2算法作為一種經(jīng)典結(jié)構(gòu)學(xué)習(xí)算法，已得到了廣泛應(yīng)用，該算法將節(jié)點(diǎn)序作為重要參數(shù)輸入，而節(jié)點(diǎn)序的選取強(qiáng)烈影響K2算法的學(xué)習(xí)效果。文獻(xiàn)[12]總結(jié)了6種學(xué)習(xí)節(jié)點(diǎn)序的方法：SORDER(sequential ordering)算法、因子分析、熵、互信息、條件熵和評(píng)分方法，將得到的節(jié)點(diǎn)序作用于K2算法進(jìn)行結(jié)構(gòu)學(xué)習(xí)，分析得到的網(wǎng)絡(luò)結(jié)構(gòu)，從而對(duì)比學(xué)習(xí)節(jié)點(diǎn)序方法的優(yōu)劣。因此如何尋找高質(zhì)量的節(jié)點(diǎn)序具有重要研究?jī)r(jià)值。

近年來(lái)，涌現(xiàn)出許多針對(duì)節(jié)點(diǎn)序的研究方法，根據(jù)節(jié)點(diǎn)序的獲取方式可以分為先驗(yàn)節(jié)點(diǎn)序和學(xué)習(xí)節(jié)點(diǎn)序。

先驗(yàn)節(jié)點(diǎn)序的方法：需要專家提供節(jié)點(diǎn)的相關(guān)知識(shí)作為結(jié)構(gòu)調(diào)整。文獻(xiàn)[7]通過(guò)相關(guān)性分析得到節(jié)點(diǎn)序，結(jié)合K2算法得到初始網(wǎng)絡(luò)結(jié)構(gòu)，最后根據(jù)專家先驗(yàn)知識(shí)修正初始結(jié)構(gòu)得到最優(yōu)結(jié)果。文獻(xiàn)[13]提出分組并行化學(xué)習(xí)，同時(shí)基于先驗(yàn)節(jié)點(diǎn)序，避免執(zhí)行環(huán)檢測(cè)；文獻(xiàn)[14]運(yùn)用相關(guān)性分析和先驗(yàn)知識(shí)得到先驗(yàn)節(jié)點(diǎn)序，再結(jié)合K2算法進(jìn)行結(jié)構(gòu)學(xué)習(xí)；文獻(xiàn)[15]利用重構(gòu)先驗(yàn)信息構(gòu)建初始網(wǎng)絡(luò)結(jié)構(gòu)，改進(jìn)模擬退火算法的鄰域求解方法，以求得網(wǎng)絡(luò)的最優(yōu)結(jié)構(gòu)。這類方法降低了計(jì)算復(fù)雜度，但要求高質(zhì)量的先驗(yàn)節(jié)點(diǎn)序，很多情況下，尤其是高維變量很難獲得精確的先驗(yàn)節(jié)點(diǎn)序。

學(xué)習(xí)節(jié)點(diǎn)序的方法：需要從數(shù)據(jù)中自動(dòng)學(xué)習(xí)優(yōu)質(zhì)節(jié)點(diǎn)序，結(jié)合結(jié)構(gòu)學(xué)習(xí)算法構(gòu)建最優(yōu)模型。通過(guò)搜索最大生成樹(maximum weight spanning tree,MWST)得到不同的節(jié)點(diǎn)序：文獻(xiàn)[16]的變量排序算法，將入度為0的節(jié)點(diǎn)添加到拓?fù)渑判虮砟┪玻瞥嚓P(guān)的邊；重復(fù)上述過(guò)程，直至所有節(jié)點(diǎn)都被添加到排序表中；文獻(xiàn)[17]采用蟻群優(yōu)化(ant colony optimization，ACO)搜索最大生成樹，獲得了節(jié)點(diǎn)序；文獻(xiàn)[18]通過(guò)帶環(huán)監(jiān)測(cè)的深度優(yōu)先搜索算法得到節(jié)點(diǎn)序；文獻(xiàn)[19]構(gòu)建定量評(píng)價(jià)節(jié)點(diǎn)序的適應(yīng)度函數(shù)，通過(guò)提出混合交叉策略和孤立節(jié)點(diǎn)處理機(jī)制，同時(shí)利用動(dòng)態(tài)學(xué)習(xí)因子和倒置變異策略，提升了遺傳算法節(jié)點(diǎn)序?qū)?yōu)的性能，從而得到了高質(zhì)量的節(jié)點(diǎn)序。

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

現(xiàn)基于節(jié)點(diǎn)序的研究，提出一種新的混合結(jié)構(gòu)學(xué)習(xí)算法——雙重K2算法，首先將節(jié)點(diǎn)信息作為初始節(jié)點(diǎn)序，通過(guò)K2算法的評(píng)分搜索策略找到每個(gè)節(jié)點(diǎn)最優(yōu)的父節(jié)點(diǎn)，從而構(gòu)建鄰接矩陣作為初始結(jié)構(gòu)；之后，在初始網(wǎng)絡(luò)結(jié)構(gòu)上利用拓?fù)渑判虻玫叫拚蟮墓?jié)點(diǎn)序；最后K2算法通過(guò)修正后的節(jié)點(diǎn)序?qū)W習(xí)得到最優(yōu)的網(wǎng)絡(luò)結(jié)構(gòu)。由雙重K2算法得到的網(wǎng)絡(luò)結(jié)構(gòu)與標(biāo)準(zhǔn)的網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行對(duì)比，分析結(jié)構(gòu)中的多邊、少邊和反轉(zhuǎn)邊；同樣，對(duì)比其他基于節(jié)點(diǎn)序的K2算法進(jìn)行結(jié)構(gòu)學(xué)習(xí)。

1 基礎(chǔ)知識(shí)

1.1 貝葉斯網(wǎng)絡(luò)模型

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

網(wǎng)絡(luò)參數(shù)P={p[Xi|pa(Xi)]}為一個(gè)條件概率表。給定Xi的父節(jié)點(diǎn)集pa(Xi)時(shí)，Xi的條件概率分布為p[Xi|pa(Xi)]。貝葉斯網(wǎng)絡(luò)滿足馬爾可夫條件：節(jié)點(diǎn)Xi在給定其父節(jié)點(diǎn)pa(Xi)的條件下獨(dú)立于它的所有非后代節(jié)點(diǎn)。那么，對(duì)于貝葉斯網(wǎng)絡(luò)所有節(jié)點(diǎn)的聯(lián)合概率就可表示為各節(jié)點(diǎn)概率的乘積，即

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

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

(1)

式(1)中：n為節(jié)點(diǎn)總個(gè)數(shù)；Xi為第i個(gè)節(jié)點(diǎn)；pa(Xi)為節(jié)點(diǎn)Xi的父節(jié)點(diǎn)。

貝葉斯網(wǎng)絡(luò)實(shí)質(zhì)上就是一個(gè)聯(lián)合概率分布p(X1,X2,…,Xn)所有條件獨(dú)立性的圖形化表示。采用圖的鄰接矩陣dag= (Aij)表示網(wǎng)絡(luò)結(jié)構(gòu)，Aij=1表示有向邊由節(jié)點(diǎn)Xi指向節(jié)點(diǎn)Xj，Aij=0表示節(jié)點(diǎn)Xi和節(jié)點(diǎn)Xj之間沒(méi)有邊連接，每一個(gè)鄰接矩陣就代表一個(gè)網(wǎng)絡(luò)結(jié)構(gòu)。

1.2 K2算法

K2算法是最早、也是最經(jīng)典的基于評(píng)分搜索的結(jié)構(gòu)學(xué)習(xí)算法，因其在效率和精度上的良好性能，受到諸多學(xué)者關(guān)注。K2算法的思想是基于給定的先驗(yàn)節(jié)點(diǎn)序，使用貪婪搜索策略尋找評(píng)分最大的網(wǎng)絡(luò)結(jié)構(gòu)?？紤]到計(jì)算效率問(wèn)題，該算法并非是要搜索出評(píng)分最高的結(jié)構(gòu)，而是要搜索在給定條件下的最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu)。但K2算法的精度依賴于節(jié)點(diǎn)序的優(yōu)劣，K2算法對(duì)節(jié)點(diǎn)序的高要求制約了它的適用性，卻極大提高了算法的效率[26]。K2算法中節(jié)點(diǎn)序的作用：分辨節(jié)點(diǎn)Xi的父節(jié)點(diǎn)是否位于節(jié)點(diǎn)Xi前，Pred(Xi)為節(jié)點(diǎn)Xi前的節(jié)點(diǎn)，則定義為[15]

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

(2)

K2算法具體步驟為[27]：①?gòu)囊粋€(gè)包含所有節(jié)點(diǎn)的空?qǐng)D開(kāi)始，在搜索過(guò)程中按照給定節(jié)點(diǎn)序，對(duì)每個(gè)節(jié)點(diǎn)Xi，將排列在節(jié)點(diǎn)Xi之前的i-1個(gè)節(jié)點(diǎn)作為節(jié)點(diǎn)Xi的候選父節(jié)點(diǎn)，計(jì)算該節(jié)點(diǎn)與每一個(gè)候選父節(jié)點(diǎn)構(gòu)成局部網(wǎng)絡(luò)結(jié)構(gòu)的貝葉斯信息準(zhǔn)則(Bayesian information criterion，BIC)評(píng)分；②將加入之后評(píng)分最高的父節(jié)點(diǎn)同該父節(jié)點(diǎn)未加入之前進(jìn)行比較：若加入之后的BIC評(píng)分高，則將該父節(jié)點(diǎn)加入節(jié)點(diǎn)Xi的父節(jié)點(diǎn)集中，添加該父節(jié)點(diǎn)指向節(jié)點(diǎn)Xi的邊；若加入之后的BIC評(píng)分低，則將該父節(jié)點(diǎn)舍棄；③這樣依次循壞，直到加入父節(jié)點(diǎn)后得分score[Xi,pa(Xi)]不再增加或者達(dá)到了指定的節(jié)點(diǎn)入度。

評(píng)分函數(shù)公式為

(3)

(4)

式中：G為含有n個(gè)節(jié)點(diǎn)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)；D為樣本數(shù)據(jù)集；ri為節(jié)點(diǎn)Xi的取值狀態(tài)；qi為節(jié)點(diǎn)Xi的父節(jié)點(diǎn)pa(Xi)的取值狀態(tài)；mijk為節(jié)點(diǎn)Xi的父節(jié)點(diǎn)pa(Xi)取第j(j=1,2,…,qi)個(gè)節(jié)點(diǎn)時(shí)，Xi處于第k種狀態(tài)時(shí)的樣本個(gè)數(shù)；BS為網(wǎng)絡(luò)結(jié)構(gòu)。

由評(píng)分函數(shù)可以看出，K2算法具有可分解性，它是對(duì)所有節(jié)點(diǎn)進(jìn)行逐一打分，最后得到整個(gè)網(wǎng)絡(luò)的評(píng)分值[26]。在給定節(jié)點(diǎn)序的條件下，K2算法可以有效縮減搜索空間，降低計(jì)算復(fù)雜度。實(shí)際研究中，節(jié)點(diǎn)序并不容易事先得到，而且K2算法中節(jié)點(diǎn)序的容錯(cuò)性較差，一旦輸入的節(jié)點(diǎn)序有違真實(shí)結(jié)構(gòu)，那么K2算法的精度就會(huì)大大降低[15]。因此，為K2算法提供高質(zhì)量的節(jié)點(diǎn)序具有重要的研究?jī)r(jià)值。

2 雙重K2算法

2.1 雙重K2算法原理

文獻(xiàn)[27]首先利用MMPC(max-min parents-children)算法確定每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)集和子節(jié)點(diǎn)集，從而構(gòu)建出網(wǎng)絡(luò)結(jié)構(gòu)的框架，再利用廣度優(yōu)先搜索得到節(jié)點(diǎn)序，利用節(jié)點(diǎn)序進(jìn)行K2算法結(jié)構(gòu)學(xué)習(xí)，其中MMPC算法首先測(cè)試給定Z時(shí)節(jié)點(diǎn)X和Y的條件獨(dú)立性，最后衡量給定Z時(shí)節(jié)點(diǎn)X和Y的關(guān)聯(lián)強(qiáng)度。

K2算法的中心思想是：將排列在節(jié)點(diǎn)Xi之前的i-1個(gè)節(jié)點(diǎn)作為節(jié)點(diǎn)Xi的候選父節(jié)點(diǎn)，使得該節(jié)點(diǎn)和其父節(jié)點(diǎn)構(gòu)成的局部網(wǎng)絡(luò)結(jié)構(gòu)的BIC評(píng)分不斷增加，得到每個(gè)節(jié)點(diǎn)的最佳父節(jié)點(diǎn)，從而在空?qǐng)D中添加從父節(jié)點(diǎn)指向子節(jié)點(diǎn)的邊，得到網(wǎng)絡(luò)結(jié)構(gòu)。與MMPC算法相比，K2算法效率更快。

拓?fù)渑判騕18]是為DAG所有節(jié)點(diǎn)生成一個(gè)線性序列的過(guò)程，它使圖中的任一對(duì)節(jié)點(diǎn)Xi和Xj，若邊∈E，那么節(jié)點(diǎn)Xi在線性排序中位于節(jié)點(diǎn)Xj之前。拓?fù)渑判驖M足以下條件：每個(gè)節(jié)點(diǎn)都出現(xiàn)并只出現(xiàn)一次。

基于節(jié)點(diǎn)序研究，提出一種新的混合結(jié)構(gòu)學(xué)習(xí)算法——雙重K2算法。雙重K2算法思想是：①將節(jié)點(diǎn)信息作為初始節(jié)點(diǎn)序，利用K2算法的評(píng)分搜索策略找到每個(gè)節(jié)點(diǎn)的最優(yōu)父集，從而構(gòu)建鄰接矩陣dag作為初始結(jié)構(gòu)；②由于dag中的元素特性(Aij=1表示有向邊由節(jié)點(diǎn)Xi指向節(jié)點(diǎn)Xj)，在dag中調(diào)用拓?fù)渑判虻玫揭粋€(gè)父節(jié)點(diǎn)在子節(jié)點(diǎn)前的線性排列，則將其作為修正后的節(jié)點(diǎn)序；③K2算法的搜索策略是將節(jié)點(diǎn)序中節(jié)點(diǎn)Xi之前的i-1個(gè)節(jié)點(diǎn)作為節(jié)點(diǎn)Xi的候選父集從而計(jì)算BIC評(píng)分最優(yōu)，則由步驟②得到的修正節(jié)點(diǎn)序符合該搜索思想，最終K2算法通過(guò)該修正節(jié)點(diǎn)序?qū)W習(xí)得到最優(yōu)的網(wǎng)絡(luò)結(jié)構(gòu)。

在3種不同規(guī)模的網(wǎng)絡(luò)中進(jìn)行實(shí)驗(yàn)，結(jié)果證明：由雙重K2算法得到的修正節(jié)點(diǎn)序優(yōu)于其他節(jié)點(diǎn)序?qū)W習(xí)算法，且對(duì)于后續(xù)K2算法的結(jié)構(gòu)學(xué)習(xí)起到積極作用；在精度和效率上，雙重K2算法的學(xué)習(xí)效果也優(yōu)于其他對(duì)比算法。

2.2 雙重K2算法流程

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

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

2.3 雙重K2算法偽代碼

雙重K2算法偽代碼如下。

Step1 構(gòu)造初始網(wǎng)絡(luò)結(jié)構(gòu)。輸入:節(jié)點(diǎn)集nodes;節(jié)點(diǎn)個(gè)數(shù)n;節(jié)點(diǎn)入度max_in;數(shù)據(jù)集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 拓?fù)渑判虻玫焦?jié)點(diǎn)序。輸入:初始網(wǎng)絡(luò)結(jié)構(gòu)dag輸出:修正后的節(jié)點(diǎn)序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算法結(jié)構(gòu)學(xué)習(xí)。輸入:經(jīng)典網(wǎng)絡(luò)數(shù)據(jù)集data;節(jié)點(diǎn)取值范圍ns;節(jié)點(diǎn)序order;節(jié)點(diǎn)入度max_in輸出:最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu)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 實(shí)驗(yàn)

3.1 實(shí)驗(yàn)設(shè)置

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

為了評(píng)價(jià)算法的學(xué)習(xí)性能，選擇經(jīng)典的Asia網(wǎng)絡(luò)、Insurance網(wǎng)絡(luò)和Alarm網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)，其網(wǎng)絡(luò)信息如表1所示，標(biāo)準(zhǔn)網(wǎng)絡(luò)結(jié)構(gòu)如圖2所示。圖2(a)所示的Asia網(wǎng)絡(luò)中，各節(jié)點(diǎn)為Smoking=1，Bronchitis=2，LungCancer=3，VisitToAsia=4，TB=5，TBorCancer=6，Dys=7，Xray=8；圖2(b)所示的Insurance網(wǎng)絡(luò)中，各節(jié)點(diǎn)為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網(wǎng)絡(luò)中，各節(jié)點(diǎn)為L(zhǎng)VFAILURE=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，F(xiàn)IO2=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。在仿真實(shí)驗(yàn)中，各網(wǎng)絡(luò)的樣本量N= 1 000、3 000、5 000。

表1 標(biāo)準(zhǔn)貝葉斯網(wǎng)絡(luò)信息Table 1 Standard Bayesian network information

圖2 標(biāo)準(zhǔn)網(wǎng)絡(luò)結(jié)構(gòu)Fig.2 Standard network structure

實(shí)驗(yàn)對(duì)比算法為：①HC算法：通過(guò)加邊、減邊、轉(zhuǎn)邊修改初始網(wǎng)絡(luò)結(jié)構(gòu)，得到一系列候選網(wǎng)絡(luò)結(jié)構(gòu)并計(jì)算其評(píng)分，最后輸出評(píng)分最優(yōu)的網(wǎng)絡(luò)結(jié)構(gòu)；②最大生成樹+拓?fù)渌阉?topologie search,TS)+K2算法：拓?fù)渌阉髟谧畲笊蓸渖系玫焦?jié)點(diǎn)序，結(jié)合K2算法得到最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu)；③最大生成樹+深度優(yōu)先搜索(depth first search,DFS)+K2算法：深度優(yōu)先搜索在最大生成樹上得到節(jié)點(diǎn)序，結(jié)合K2算法得到最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu)；④最大生成樹+廣度優(yōu)先搜索(breadth first search,BFS)+K2算法：廣度優(yōu)先搜索在最大生成樹上得到節(jié)點(diǎn)序，結(jié)合K2算法得到最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu)；⑤雙重K2(double K2)算法。

學(xué)習(xí)效果的衡量指標(biāo)為：①錯(cuò)誤邊，實(shí)驗(yàn)算法學(xué)得的網(wǎng)絡(luò)結(jié)構(gòu)與標(biāo)準(zhǔn)網(wǎng)絡(luò)結(jié)構(gòu)中不一致的邊數(shù)，包括缺失邊(missed edge，ME)、多余邊(increased edges,IE)和反轉(zhuǎn)邊(reversal edges,RE)；②正確邊(correct edges,CE)，實(shí)驗(yàn)算法學(xué)得的網(wǎng)絡(luò)結(jié)構(gòu)與標(biāo)準(zhǔn)網(wǎng)絡(luò)結(jié)構(gòu)中一致的邊數(shù)；③準(zhǔn)確率，正確邊CE與標(biāo)準(zhǔn)網(wǎng)絡(luò)總邊數(shù)的比值；④運(yùn)行時(shí)間，實(shí)驗(yàn)算法學(xué)習(xí)得到最終網(wǎng)絡(luò)結(jié)構(gòu)所需時(shí)間，單位為s。

比較不同規(guī)模和樣本量下，實(shí)驗(yàn)算法學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)的效果，驗(yàn)證雙重K2算法的學(xué)習(xí)優(yōu)勢(shì)。為避免產(chǎn)生隨機(jī)效應(yīng)，實(shí)驗(yàn)過(guò)程中每種樣本量隨機(jī)生成10次，取結(jié)果的平均值進(jìn)行衡量。

3.2 實(shí)驗(yàn)結(jié)果與分析

由節(jié)點(diǎn)信息作為初始節(jié)點(diǎn)序，利用K2算法的搜索策略構(gòu)建初始網(wǎng)絡(luò)結(jié)構(gòu)。針對(duì)初始網(wǎng)絡(luò)結(jié)構(gòu)，在1 000組樣本數(shù)據(jù)的情況下，各網(wǎng)絡(luò)利用拓?fù)渑判虻玫叫拚蟮墓?jié)點(diǎn)序如表2所示。

表2 修正后的節(jié)點(diǎn)序Table 2 Modified node order

雙重K2算法利用修正后的節(jié)點(diǎn)序進(jìn)行結(jié)構(gòu)學(xué)習(xí)。5種實(shí)驗(yàn)算法的學(xué)習(xí)結(jié)果如圖3、表3所示。

由圖3可知，錯(cuò)誤邊ME、IE和RE的數(shù)值越小越能證明實(shí)驗(yàn)算法的學(xué)習(xí)結(jié)果接近標(biāo)準(zhǔn)網(wǎng)絡(luò)結(jié)構(gòu)。

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

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

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

圖3 網(wǎng)絡(luò)的錯(cuò)誤邊Fig.3 Wrong edges of network

由表3可知，正確邊CE和準(zhǔn)確率的值越大越能證明實(shí)驗(yàn)算法的學(xué)習(xí)結(jié)果接近標(biāo)準(zhǔn)網(wǎng)絡(luò)結(jié)構(gòu)。Asia網(wǎng)絡(luò)學(xué)習(xí)的正確邊CE和準(zhǔn)確率：3種樣本量下結(jié)果最優(yōu)的為Double K2算法，其CE=7，準(zhǔn)確率=0.875 0；樣本量為1 000時(shí)，結(jié)果最差的為HC算法，其CE=4，準(zhǔn)確率=0.500 0；樣本量為3 000時(shí)，結(jié)果最差的為MWST+TS+K2算法，其CE=3，準(zhǔn)確率=0.375 0；樣本量為5 000時(shí)，結(jié)果最差的為HC算法，其CE=3，準(zhǔn)確率=0.375 0。

表3 網(wǎng)絡(luò)學(xué)習(xí)結(jié)果對(duì)比Table 3 Comparison of networks learning results

Insurance網(wǎng)絡(luò)學(xué)習(xí)的正確邊CE和準(zhǔn)確率：3種樣本量下結(jié)果最優(yōu)的為Double K2算法，其CE=39，準(zhǔn)確率=0.750 0；CE=44，準(zhǔn)確率為0.846 2；CE=43，準(zhǔn)確率為0.826 9。樣本量為1 000時(shí)，結(jié)果最差的為MWST+BFS+K2算法，其CE=23，準(zhǔn)確率=0.442 3；樣本量為3 000時(shí)，結(jié)果最差的為MWST+DFS+K2算法，其CE=26，準(zhǔn)確率=0.500 0；樣本量為5 000時(shí)，結(jié)果最差的為MWST+DFS+K2算法，其CE=25，準(zhǔn)確率=0.480 8。

Alarm網(wǎng)絡(luò)學(xué)習(xí)的正確邊CE和準(zhǔn)確率：3種樣本量下結(jié)果最優(yōu)的為Double K2算法，其CE=45，準(zhǔn)確率=0.978 3。樣本量為1 000時(shí)，結(jié)果最差的為HC算法，其CE=19，準(zhǔn)確率=0.413 0；樣本量為3 000時(shí)，結(jié)果最差的為HC算法，其CE=18，準(zhǔn)確率=0.391 3；樣本量為5 000時(shí)，結(jié)果最差的為MWST+DFS+K2算法，其CE=22，準(zhǔn)確率=0.478 3。

由表3可知，運(yùn)行時(shí)間的值越小越能證明實(shí)驗(yàn)算法的學(xué)習(xí)結(jié)果耗費(fèi)時(shí)間少。Asia網(wǎng)絡(luò)學(xué)習(xí)的運(yùn)行時(shí)間：樣本量為1 000時(shí)，結(jié)果最優(yōu)的為MWST+DFS+K2算法，其值為7.256 0；樣本量為300 0時(shí)，結(jié)果最優(yōu)的為MWST+TS+K2算法，其值為13.502 0；樣本量為5 000時(shí)，結(jié)果最優(yōu)的為MWST+DFS+K2算法，其值為20.450 0。

Insurance網(wǎng)絡(luò)學(xué)習(xí)的運(yùn)行時(shí)間：樣本量為1 000時(shí)，結(jié)果最優(yōu)的為MWST+DFS+K2算法，其值為31.301 0；樣本量為3 000時(shí)，結(jié)果最優(yōu)的為MWST+BFS+K2算法，其值為59.049 0；樣本量為5 000時(shí)，結(jié)果最優(yōu)的為MWST+TS+K2算法，其值為88.885 0。

Alarm網(wǎng)絡(luò)學(xué)習(xí)的運(yùn)行時(shí)間：樣本量為1 000時(shí)，結(jié)果最優(yōu)的為MWST+BFS+K2算法，其值為49.904 0；樣本量為3 000時(shí)，結(jié)果最優(yōu)的為MWST+TS+K2算法，其值為88.258 0；樣本量為5 000時(shí)，結(jié)果最優(yōu)的為MWST+TS+K2算法，其值為136.512 0。

通過(guò)以上實(shí)驗(yàn)可以看出，①對(duì)于HC算法，其學(xué)習(xí)效果不如基于節(jié)點(diǎn)序的K2算法，且耗費(fèi)時(shí)間長(zhǎng)，準(zhǔn)確率低；②MWST+TS+K2算法、MWST+DFS+K2算法、MWST+BFS+K2算法和雙重K2算法均為基于不同節(jié)點(diǎn)序進(jìn)行結(jié)構(gòu)學(xué)習(xí)的K2算法，可以對(duì)比發(fā)現(xiàn)不同節(jié)點(diǎn)序?qū)τ诮Y(jié)構(gòu)學(xué)習(xí)效果的影響；③經(jīng)過(guò)結(jié)果分析，在準(zhǔn)確度和效率上，雙重K2算法效果優(yōu)于其他對(duì)比算法。

綜上所述，K2算法的精度取決于節(jié)點(diǎn)序的優(yōu)劣。通過(guò)大量實(shí)驗(yàn)表明，與其他算法相比，雙重K2算法具有更強(qiáng)的學(xué)習(xí)性能，并且該算法得到的修正節(jié)點(diǎn)序非常接近于真實(shí)節(jié)點(diǎn)序，使得學(xué)習(xí)效果遠(yuǎn)遠(yuǎn)優(yōu)于其他節(jié)點(diǎn)序的K2算法，實(shí)驗(yàn)證明了雙重K2算法在貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方面的有效性。

4 結(jié)論

(1)傳統(tǒng)基于評(píng)分搜索的算法通過(guò)降低收斂速度來(lái)提高精度，或者通過(guò)降低精度來(lái)提高收斂速度，難以同時(shí)優(yōu)化收斂速度和精度。K2算法作為結(jié)構(gòu)學(xué)習(xí)的經(jīng)典算法之一，一方面，由于缺少先驗(yàn)信息很難確定節(jié)點(diǎn)序，導(dǎo)致該算法在應(yīng)用上的局限性；另一方面，由于貪婪搜索策略導(dǎo)致該算法容易陷入局部最優(yōu)。但在給定節(jié)點(diǎn)序的前提下進(jìn)行結(jié)構(gòu)學(xué)習(xí)，就會(huì)減少此類問(wèn)題產(chǎn)生。學(xué)習(xí)K2算法的節(jié)點(diǎn)序相當(dāng)于將貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的搜索空間縮減為節(jié)點(diǎn)序搜索空間，且節(jié)點(diǎn)序搜索避免了環(huán)結(jié)構(gòu)的產(chǎn)生，所以在節(jié)點(diǎn)序空間上進(jìn)行結(jié)構(gòu)學(xué)習(xí)可以有效降低運(yùn)算成本。

(2)所提出的雙重K2算法不僅解決先驗(yàn)節(jié)點(diǎn)序的問(wèn)題，而且保證算法的準(zhǔn)確性。在3種規(guī)模不同的網(wǎng)絡(luò)實(shí)驗(yàn)中，與HC算法和其他基于節(jié)點(diǎn)序的K2算法相比，雙重K2算法的優(yōu)勢(shì)更加突出。

(3)未來(lái)的研究工作包括：結(jié)構(gòu)學(xué)習(xí)中對(duì)于孤立節(jié)點(diǎn)的處理，以及在大型網(wǎng)絡(luò)中對(duì)于節(jié)點(diǎn)序的優(yōu)化學(xué)習(xí)。