基于結構繼承的貝葉斯網結構學習優化設計

曾杰鵬，廖 芹，谷志元

（1.華南理工大學 理學院，廣東 廣州510640；2.廣州鐵路職業技術學院 應用數學教研室，廣東 廣州510430）

0 引 言

貝葉斯網絡結構學習是貝葉斯網絡研究的一個重要方向，尤其在沒有先驗網絡結構的情況下，結構學習算法在建網上的作用尤為突出。貝葉斯結構學習主要有基于評分的啟發式算法以及基于互信息等規則［1］的建網方法。其中，基于評分的啟發式算法在當前的研究中最為活躍，主要包括爬山算法［2］，蟻群算法［3］，遺傳算法［4］，模擬退火算法［5］等。同時，通過對上述算法的優化組合，也生成了各種有效的組合算法，如遺傳算法與模擬退火算法的組合算法［6］，遺傳算法與蟻群算法的組合算法［7］等。

遺傳算法搜索范圍大，尋優效率高，在貝葉斯網絡結構學習中具有普遍的應用。然而由于傳統的個體編碼主要采用貝葉斯網絡的鄰接矩陣，導致種群初始化的過程中，可行解的生成概率較低，需要重復生成新個體，以保證其通過無環性檢驗［8］。其次，在種群的進化過程中，個體的可行性可能受到破壞。因此，對于新生成的個體，往往又需要重新進行無環性檢驗，進而將非法結構修正為有向無環圖［9］，或者為非法結構設置較低的適應度，從而降低了尋優的效率［10－11］。另外，之前的研究在計算新個體的結構得分時，往往需要計算整個新貝葉斯網絡的得分。然而事實上，在遺傳進化過程中，貝葉斯網絡通常存在局部不變性。因此可以結合結構得分的可分解性與結構局部穩定性［12］，從而進一步優化結構學習的效率。

本文針對上述問題，提出一種新的個體編碼方式，同時結合遺傳進化過程中，個體的家族得分具有可繼承性，從而設計相應的改進算法。最后通過對比實驗表明，相比于傳統的遺傳算法，本文改進的算法在結構學習的精度與效率上都得到明顯的提升。

1 貝葉斯網絡結構編碼的改進

1.1 傳統編碼的問題

貝葉斯網絡結構的傳統編碼，一般以0－1向量表示。具體如下：若貝葉斯網絡有n個節點，其鄰接矩陣為（cij）nxn。若節點i指向節點j，則cij＝1，表示節點i為節點j的父節點，否則cij＝0。把上述鄰接矩陣改寫為0－1向量 （c11，c12，…，c1n，c21，c22，…，c2n，…，cn1，cn2，…cnn），即可將其作為貝葉斯網絡結構的個體編碼。

然而在該編碼下，得到有向無環圖的可能性不高。因為對于節點數為n的貝葉斯網絡，所有可能結構的個數f（n）滿足［13］

而以隨機生成的鄰接矩陣為例，所有n階0－1矩陣的個數F（n）＝2nxn。于是，隨機生成的鄰接矩陣滿足無環性的概率。

以n＝1，2，……，5為例，計算r（n），見表1。

表1 滿足無環性的概率

可見，隨著節點數的增大，隨機生成的鄰接矩陣滿足無環性的概率迅速減小。

1.2 個體編碼改進

考慮到傳統個體編碼的低效性，本文基于每個貝葉斯網絡都可以至少對應到一個節點順序的事實［14］，提出一種新的個體編碼方式。該編碼包括兩個部分：節點順序與給定節點順序下的連邊情況。

具體設計如下：若節點數為n，個體編碼為 （i1，i2，…，in，c12，c13，c23，c14，c24，c34，…，c1n，c2n，…，cn－1，n）。其中i1，i2，…，in為1至n的一個排列，表示節點順序。為了保證無環性，這里規定只允許排序在前的節點指向排序在后的節點。c12，c13，c23，c14，c24，c34，…，c1n，c2n，…，cn－1，n表示在給定節點順序下的連邊情況。若節點ij指向節點ik（j＜k），則cjk＝1，否則cjk＝0。

例如，當n＝4，若編碼為 （2，4，3，1，1，1，0，0，1，1）。那么，其中2，4，3，1表示節點順序，分別對應于變量X2，X4，X3，X1。1，1，0，0，1，1表示給定節點順序下的連邊情況。X2排在第一位，因此沒有父節點；X4連邊情況的相關編碼為1，表示X2為其父節點；X3連邊情況的相關編碼為1，0，表示X2為其父節點；X1連邊情況的相關編碼為0，1，1，表示X4，X3為其父節點。于是，該編碼對應的貝葉斯網絡如圖1所示。

圖1 編碼對應結構

可以證明，該設計下的個體編碼，唯一對應到一個有向無環圖，即唯一對應到一個貝葉斯網絡；而任意一個貝葉斯網絡，都至少可以找到一個該設計下的個體編碼與之對應。

該編碼設計的好處還在于可以有效減少編碼長度。對n個節點的貝葉斯網絡，若采用傳統方式的編碼，其編碼長度L（n）＝n2，而采用本文設計的編碼，計算得知其編碼長度L’（n）＝n（n＋1）/2。可以證明：

由此說明，本文設計的個體編碼可以有效減少編碼長度，降低存儲開銷。而且當節點數增大時，本文編碼的優勢更加明顯，可以將編碼長度減少到將近傳統編碼的一半。

2 基于家族繼承的評分算法改進

2.1 評分函數的改進

關于貝葉斯網絡結構的優劣存在多種評價標準，當前以BIC得分最為常用。BIC得分的計算方式如下［15］

式中：n——節 點 數，qi——節 點i的 父 節 點 取 值 數，ri——節點i的取值數，mijk——學習樣本中，父節點為第j種取值下，節點i為第k種取值的樣本數。。N表示樣本數。

在傳統的遺傳算法中，由舊種群生成的新種群，其中新個體的結構得分往往整個重新計算。然而分析發現，這個過程可能存在重復運算的問題。例如對于節點數為4的貝葉斯網絡，遺傳前后可能存在網絡結構分別如圖2所示。

那么，傳統方法計算該新結構的得分，需要先分別計算X1，X2，X3，X4的家族得分。然而觀察發現，在新結構中X1和X3的父節點，與舊結構的中一致，因此它們的家族得分可以直接從舊結構中繼承。于是只有X2和X4的家族得分需要重新計算，從而大大簡化了結構得分的計算。

圖2 新舊個體對應結構

2.2 改進算法實現

本文采用矩陣AllPa和AllFamS，分別對上一代所有個體中各節點對應的父節點及家族得分進行存儲。AllPa＝（Paij）mxn，其中m表示種群大小，n表示網絡節點數，Paij表示個體i中節點j的父節點的集合。若個體i的節點j無父節點，則記Paij＝ ｛0｝。AllFamS＝ （FamSij）mxn，其中FamSij表示個體i中節點j的家族得分。因此，計算個體i的結構得分只需對AllFamS第i行求和。

對于遺傳過程中生成的新個體，計算其結構得分時，需要累積其各節點的家族得分。例如計算節點i的家族得分，則首先對比該節點i與父代中個體的節點i，確定其父節點集合是否存在一致，如果存在，則直接從上一代的該個體繼承節點i的家族得分，如果不存在，則需通過重新掃描樣本集計算。

AllPa和AllFamS的更新算法具體如下：

Update//更新算法

輸入：AllPa，AllfamS，Population//種群，data//數據集

輸出：NewAllPa，NewAllfamS

//獲取各個體的各父節點

fori＝1：m//m為種群個體數

//針對某一個體，獲取其各節點的父節點

forj＝1：n//n為節點數

Pa＝GetPa（Population，i，j）//GetPa （Population，i，j）返回種群Population的個體i中節點j的父節點集合

ifPa＝Γ

NewAllPa｛i，j｝＝0；

else

NewAllPa｛i，j｝＝Pa；

end

end

end

//計算各個體的各家族得分

fori＝1：m

//針對某一個體，計算其各節點的家族得分

forj＝1：n

Exist＝false；//Exist為能否家族繼承的標志

//掃描上一個種群的AllPa，確定能否家族繼承

fork＝1：m

ifNewAllPa｛i，j｝＝＝AllPa｛k，j｝

NewAllfamS（i，j）＝AllfamS（k，j）；

Exist＝true；

break；

end

end

//如果無法家族繼承，家族得分則需重新掃描data計算

ifExist＝false；

NewAllfamS（i，j）＝GetfamS （data，j，Pa）；//GetfamS（data，j，Pa）返回根據數據集data計算得到的節點j在父節點Pa下的家族得分

end

end

end

3 結構學習遺傳算法的改進

基于上文的個體編碼設計與家族繼承方法，下面設計與之相應的結構學習遺傳算法。該算法設計的難點在于交叉與變異過程中對個體無環性的保證。具體如下：

3.1 種群初始化

設種群大小為m，按照上文的個體編碼方式，生成m個個體。個體生成的具體步驟如下：

步驟1 隨機生成1至n的一個排列i1，i2，…，in，表示節點的順序；

步驟2 生成一個 （n－1）＊n/2維的零向量，表示給定節點順序下的連邊情況；

步驟3 將步驟1中的n維向量與步驟2中的 （n－1）＊n/2維向量連接，則形成n＊ （n＋1）/2維的個體編碼。

該種群初始化的設計表明，所有個體的初始狀態均無連邊，初始個體之間的差異在于節點順序的不同。

3.2 適值函數

個體的適值是通過對其BIC得分進行0－1壓縮得到的，即個體i對應的適值f（i）為

式中：si——個體i的BIC得分。

3.3 選擇算子

本文的選擇算子主要采取μ＋λ策略，具體設計如下：

步驟1 保存上一代的所有個體及其適值；

步驟2 采用輪盤賭算法從上一代的所有個體中挑選m個形成新種群；

步驟3 合并上一代個體與交叉變異后的新種群個體，從中選擇適值最高的前m個。

因此本文選擇算子的設計，引入了父代與子代的競爭，在個體選擇方面，還采用了以適值排序與輪盤賭概率相結合的方式。

3.4 交叉算子

交叉算子采用單點交叉。假如交叉的位置出現在表示連邊情況的0－1編碼部分，則直接將從該位置起的后半段相互交換。如果交叉的位置出現在表示節點順序的編碼部分，則首先將表示連邊情況的整段0－1編碼相互交換，再進行表示節點順序的編碼的交叉。

節點順序編碼的交叉方式如下：假設節點順序S1＝（i1，i2，…，in），S2＝ （j1，j2，……，jn）。若交叉位置為p，則首先將兩節點順序轉化為S1＝ （i1，i2，……，ip－1，jp，jp＋1， ……，jn，ip，ip＋1， ……，in），S2＝ （j1，j2，……，jp－1，ip，ip＋1，……，in，jp，jp＋1，……，jn），接著按從左到右的順序，掃描S1和S2中的每個節點，如果該節點在其左邊的子串中已經出現，則將其刪去，直至S1和S2最終形成兩個新的節點順序。

例如對于節點數為5的兩個節點順序S1＝ （2，3，1，4，5），S2＝ （5，3，4，1，2）。若交叉位置為3，則首先將S1和S2轉化為S1＝ （2，3，4，1，2，1，4，5），S2＝（5，3，1，4，5，4，1，2），再按照上述規則進行刪減，得到S1＝ （2，3，4，1，5），S2＝ （5，3，1，4，2）。

于是，通過該交叉算子的設計，保證了交叉運算后新個體的可行性。

3.5 變異算子

變異算子采用單點變異。假如交叉的位置出現在表示連邊情況的0－1編碼部分，則直接將該位置的編碼0變1或1變0。如果交叉的位置出現在表示節點順序的編碼部分，則隨機選擇另一節點，將兩節點的位置互換。

因此，對于個體編碼 （i1，i2，…，in，c12，c13，c23，c14，c24，c34，…，c1n，c2n，…，cn－1，n），該變異算子包括如下3種變換：

變換1：若進行變異的編碼為cij，且cij＝0，則變異表示添加節點i指向節點j的邊；

變換2：若進行變異的編碼為cij，且cij＝1，則變異表示刪除節點i指向節點j的邊；

變換3：若進行變異的編碼為ij，且選中的與之交換的編碼為ik，則變異表示在貝葉斯網絡結構中，直接互換節點ij與節點ik，而不改變其它連邊情況。

例如，個體編碼 （2，4，3，1，1，1，0，0，1，1）對應的結構如圖3（a）所示。若互換節點2與節點3的位置，則得到新個體編碼 （3，4，2，1，1，1，0，0，1，1），其對應的結構如圖3（b）所示。

可見，在編碼中互換節點2與節點3的位置，就相當于在貝葉斯網絡結構中直接互換節點2與節點3。

于是，通過該變異算子的設計，保證了變異運算后新個體的可行性。

圖3 新舊編碼對應結構

4 實驗結果

下面對原始遺傳算法 （OldGA）與本文改進的遺傳算法 （NewGA）進行對比試驗。

數據集來自Aisa網絡。該網絡的節點數為8，邊數為8。

令種群大小為10，交叉概率為0.9，變異概率為0.1。遺傳算法的終止條件為運行時間達到事先給定的算法耗時上限。

為了減少遺傳算法單次運行隨機性的影響，對于每個隨機試驗，OldGA與NewGA都重復進行10次，最終取這10次中各指標的平均值，作為OldGA與NewGA該試驗的結果。

取定樣本量為1000，在給定不同的算法耗時上限的情況下，對比新舊算法的建網效果。

4.1 最優得分與算法耗時

最優得分是指進化過程中最優個體的得分，它與算法耗時的關系如圖4所示。

圖4 最優得分與算法耗時

可見一開始，NewGA的最優得分低于OldGA，然而NewGA具有較高的進化效率，因此其最優得分在隨后就迅速超過了OldGA。

4.2 邊誤差與算法耗時

邊誤差是指在標準網絡中存在，而算法生成的網絡中不存在或者標準網絡中不存在，而算法生成的網絡中存在的連邊數目總和，它與算法耗時的關系如圖5所示。

可見，OldGA和NewGA的邊誤差總體上均隨算法耗時呈下降趨勢，而且相比發現，NewGA的邊誤差明顯小于OldGA，而且其下降的速度也更快。

圖5 邊誤差與算法耗時

5 結束語

本文針對貝葉斯網絡結構學習中，傳統遺傳算法的個體編碼需要反復驗證無環性的問題，提出了一種新的個體編碼方式，將網絡節點排序與基于給定排序的節點間連邊情況分別編碼，從而提高了個體編碼在遺傳過程中的可行性。同時，考慮到進化過程中，結構得分的可分解性以及父代家族得分的可繼承性，提出了基于家族繼承的結構評分算法改進，在此基礎上設計了相應的改進遺傳算法。通過實驗表明，本文算法在建網的精度與效率上都得到了明顯的提升。

［1］GOU Kui－xiang，GONG Xiu－jun，ZHAO Zheng.Learning Bayesian network structure from distributed homogeneous data［C］.Eighth ACIS International Conference on Software Engineering，Artificial Intelligence，Networking，and Parallel/Distributed Computing.Qingdao：IEEE，2007：250－254.

［2］JIN Xiaobo，HOU Xinwen，LIU Cheng－lin.A hybrid generative－discriminative learning algorithm for Bayesian network structure［C］.Proceedings of the International Conference on Wavelet Analysis and Pattern Recognition.Beijing：IEEE，2007：618－623.

［3］WANG Fengshan，ZHU Wanhong.A Bayesian network structure learning method based on ant colony algorithm ［C］.International Conference on Management and Service Science.Wuhan：IEEE，2010：1－4.

［4］ZHOU Benda，TIAN Xu.An algorithm for Bayesian networks structure learning based on genetic algorithms and reinforcement learning ［J］.Microcomputer ＆ Its Applications，2007，6（S1）：2257－2259 （in Chinese）.［周本達，田旭.基于遺傳算法和強化學習的貝葉斯網絡結構學習算法 ［J］.微型機與應用，2007，6 （S1）：2257－2259.］

［5］GUO Peng，LI Naixiang.An EM－MCMC algorithm for Bayesian structure learning ［C］.2nd IEEE International Conference on Computer Science and Information Technology.Beijing：IEEE，2009：158－162.

［6］CAO Weidong，FANG Xiangnong.An improved method for Bayesian network structure learning ［C］.Sixth International Conference on Natural Computation.Yantai：IEEE，2010：3133－3137.

［7］LI Xi－jun.Learning structure of Bayesian network using ant colony algorithm assisted by genetic algorithm ［C］.Intelligent Systems and Applications.Wuhan：IEEE，2009：1－4.

［8］CHEN Wangyu，QIN Liao.Research on Bayesian network adaptive knowledge construction and inference based on genetic algorithm ［C］.Fourth International Conference on Natural Computation.Jinan：IEEE，2008：315－319.

［9］LI Xian－jie，ZHANG You－sheng，LI Jianfei.Algorithm of BN structural learning based on quantum genetic ［J］.Application Research of Com－puters，2008，25 （4）：996－1002 （in Chinese）.［李顯杰，張佑生，李劍飛.基于量子遺傳算法的貝葉斯網絡結構學習 ［J］.計算機應用研究，2008，25 （4）：996－1002.］

［10］HUANG Hao，SONG Hantao，LU Yuchang.Research on structure learning algorithm of Bayesian networks based on niche genetic algorithm ［J］.Application Research of Computers，2007，24 （4）：100－103 （in Chinese）.［黃浩，宋瀚濤，陸玉昌.基于小生境遺傳算法的貝葉斯網絡結構學習算法研究 ［J］.計算機應用研究，2007，24 （4）：100－103.］

［11］LI Weiwei，WANG Jiandong，FANG Liming，et al.Edgeoriented approach of Bayesian networks based on tabu genetic algorithm ［J］.Computer Engineering，2009，35 （12）：178－180（in Chinese）. ［李瑋瑋，王建東，方黎明，等.基于遺傳禁忌算法的貝葉斯網邊定向方法 ［J］.計算機工程，2009，35 （12）：178－180.］

［12］Valentin Ziegler.Approximation algorithms for restricted Bayesian network structures ［J］.Information Processing Letters，2008，108 （2）：60－63.

［13］Lobna Bouchaala，Afif Masmoudi，Faiez Gargouri，et al.Improving algorithms for structure learning in Bayesian networks using a new implicit score ［J］.Expert Systems with Applications，2010，37 （7）：5470－5475.

［14］CHENG Zekai，QIN Feng，YANG Bo.Improving Bayesian network structure learning with mutual information－based node ordering in the k2algorithm ［C］.Proceedings of the 6th World Congress on Intelligent Control and Automation.Dalian：IEEE，2006：6010－6014.

［15］LIU Guixia，FENG Wei，WANG Han，et al.Reconstruction of gene regulatory networks based on two－stage Bayesian network structure learning algorithm ［J］.Journal of Bionic Engineering，2009，6 （1）：86－92.