李 明, 張 韌, 洪 梅, 白成祖

(國防科技大學(xué)氣象海洋學(xué)院, 江蘇 南京 211101)

0 引 言

大數(shù)據(jù)環(huán)境下,分析和挖掘海量數(shù)據(jù)以獲取科學(xué)評價和決策信息,需要有效的知識表達(dá)和分析推理,其中以不確定知識的表達(dá)推理最為重要,而貝葉斯網(wǎng)絡(luò)是對不確定問題模擬和推理的有效工具。從數(shù)據(jù)樣本集中構(gòu)建貝葉斯網(wǎng)絡(luò),包括結(jié)構(gòu)學(xué)習(xí)和參數(shù)學(xué)習(xí),其中結(jié)構(gòu)學(xué)習(xí)是基礎(chǔ)和核心。結(jié)構(gòu)學(xué)習(xí)是指利用訓(xùn)練數(shù)據(jù)集,盡可能結(jié)合先驗知識,構(gòu)建與客觀數(shù)據(jù)最吻合的有向網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu),目前貝葉斯網(wǎng)絡(luò)的研究熱點之一就是如何從客觀數(shù)據(jù)中自動學(xué)習(xí)和優(yōu)化網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)。

貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的關(guān)鍵在于如何確定網(wǎng)絡(luò)節(jié)點間的弧和弧方向,常用的結(jié)構(gòu)學(xué)習(xí)算法可以分為基于統(tǒng)計檢測方法和基于搜索評分方法兩類?；诮y(tǒng)計檢測方法關(guān)鍵是選取合適的測度函數(shù)進(jìn)行節(jié)點間的依賴程度測試,尤其是條件獨立性測試,完成網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)。基于搜索評分方法通常作為最優(yōu)化問題來處理,即在一個網(wǎng)絡(luò)結(jié)構(gòu)空間中由評分函數(shù)引導(dǎo)搜索最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu)。由于從大規(guī)模數(shù)據(jù)庫中進(jìn)行結(jié)構(gòu)學(xué)習(xí)是一個非確定性多項式(non-deterministic polynomial,NP)難題,所以對于節(jié)點較多情況時大都采用搜索評分方法:文獻(xiàn)[1]提出基于K2評分的爬山算法;文獻(xiàn)[2]提出基于最小描述長度(minimum description length,MDL)評分函數(shù)的K3算法;文獻(xiàn)[3-4]先后將模擬退火算法和貪婪搜索算法用于網(wǎng)絡(luò)結(jié)構(gòu)的搜索學(xué)習(xí);近些年,文獻(xiàn)[5-7]將遺傳算法、蟻群優(yōu)化算法和粒子群算法用于結(jié)構(gòu)學(xué)習(xí)。但搜索評分方法的效率通常較低,且易于陷入局部最優(yōu),為克服此方法計算和搜索的困難,許多學(xué)者進(jìn)行了大量研究工作:文獻(xiàn)[8]結(jié)合經(jīng)典的K2和馬爾可夫鏈蒙特卡羅(Markov chain Monte Carlo,MCMC)算法提出改進(jìn)的結(jié)構(gòu)學(xué)習(xí)思路;文獻(xiàn)[9]基于互信息和混沌映射來改進(jìn)遺傳算法用于網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí);文獻(xiàn)[10]基于無約束優(yōu)化和遺傳算法提出學(xué)習(xí)結(jié)構(gòu)的限制型遺傳算法;文獻(xiàn)[11]基于卡方測試來改進(jìn)貪婪搜索結(jié)構(gòu)學(xué)習(xí)算法。上述改進(jìn)算法優(yōu)化了結(jié)構(gòu)搜索空間,提高了搜索收斂速度,但仍然容易陷入局部最優(yōu)解,最主要的缺陷是弧和弧方向的確定要分步進(jìn)行,學(xué)習(xí)效率較低,并且弧方向的確定具有較大的不確定性。

貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)實際上是因果分析的過程,信息流[12]是一種新興的因果分析方法,本文首次將信息流引入結(jié)構(gòu)學(xué)習(xí),基于信息流構(gòu)造無約束0/1優(yōu)化問題,提出一種結(jié)構(gòu)學(xué)習(xí)的改進(jìn)型搜索評分算法——改進(jìn)型貪婪搜索(advanced greedy search,AGS)算法。該方法由2個階段組成:第1階段,基于信息流進(jìn)行因果分析,對初始網(wǎng)絡(luò)進(jìn)行全局性處理,構(gòu)造0/1優(yōu)化問題并求解,獲得初始網(wǎng)絡(luò)結(jié)構(gòu),為第2階段隨機(jī)搜索提供一個較優(yōu)的結(jié)構(gòu)空間;第2階段,在初始網(wǎng)絡(luò)結(jié)構(gòu)基礎(chǔ)上進(jìn)行加弧、減弧操作,進(jìn)行結(jié)構(gòu)弧的搜索學(xué)習(xí),同時根據(jù)信息流確定弧方向,最終完成最優(yōu)結(jié)構(gòu)學(xué)習(xí)。由于在第2階段中,待搜索結(jié)構(gòu)是以信息流全局優(yōu)化的初始結(jié)構(gòu)中的弧作為候選弧,并且弧和弧方向同步確定,不需進(jìn)行傳統(tǒng)的轉(zhuǎn)弧操作,較傳統(tǒng)的搜索算法更能夠得到近似全局最優(yōu)結(jié)構(gòu),提高了結(jié)構(gòu)學(xué)習(xí)的準(zhǔn)確性和時間效率。具體改進(jìn)算法流程,如圖1所示。

圖1 貝葉斯網(wǎng)絡(luò)AGS算法流程Fig.1 AGS algorithm of Bayesian network

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

貝葉斯網(wǎng)絡(luò),又稱貝葉斯信度網(wǎng)絡(luò)[13],是圖論與概率論的結(jié)合。貝葉斯網(wǎng)絡(luò)是變量間概率關(guān)系的圖形化描述,提供了一種將知識直觀的圖解可視化的方法；同時又是一種概率推理技術(shù),使用概率理論來處理在描述不同變量之間因條件相關(guān)而產(chǎn)生的不確定性。貝葉斯網(wǎng)絡(luò)直觀地表示為一個復(fù)雜的賦值因果關(guān)系圖,完整的貝葉斯網(wǎng)絡(luò)是一個二元組B=〈G,θ〉,其中:

(1)G=(V(G),E(G)),是一個有向無環(huán)圖,V(G)是節(jié)點集合,節(jié)點表示所研究問題域中的變量(或事件);E(G)為弧集合,有向弧定性表示節(jié)點之間的概率依賴關(guān)系。

(2) 網(wǎng)絡(luò)參數(shù)θ構(gòu)成的條件概率表表達(dá)了節(jié)點之間的因果依賴程度,體現(xiàn)了知識域定量方面的特征。

貝葉斯網(wǎng)絡(luò)的數(shù)學(xué)基礎(chǔ)是貝葉斯公式,基于先驗概率,根據(jù)相關(guān)條件可推導(dǎo)后驗概率;并且網(wǎng)絡(luò)蘊(yùn)含了條件獨立性假設(shè),如果給定根節(jié)點的先驗概率分布和非根節(jié)點的條件概率分布,則可以通過推理得到包含所有節(jié)點的聯(lián)合概率分布,即

(1)

式中,Vi為網(wǎng)絡(luò)節(jié)點;Pa(Vi)為節(jié)點Vi的父節(jié)點。

貝葉斯網(wǎng)絡(luò)的構(gòu)建主要包括結(jié)構(gòu)學(xué)習(xí)和參數(shù)學(xué)習(xí),其中結(jié)構(gòu)學(xué)習(xí)的目標(biāo)是將給定數(shù)據(jù)中的因果依賴關(guān)系,用一個圖形化的模型表達(dá)出來,找到一個與樣本數(shù)據(jù)擬合程度最好的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)?；谒阉髟u分的結(jié)構(gòu)學(xué)習(xí)有兩個重要的組成部分:度量機(jī)制和搜索過程。度量機(jī)制即結(jié)構(gòu)評分函數(shù),是評價網(wǎng)絡(luò)好壞的一種標(biāo)準(zhǔn),常用度量機(jī)制包括χ2度量、信息熵度量、貝葉斯度量以及MDL度量等,本文采用貝葉斯信息準(zhǔn)則(Bayesian information criterion,BIC)評分函數(shù);搜索過程用來搜索網(wǎng)絡(luò)空間,以找到一個度量值最高的網(wǎng)絡(luò),即

best_G=argmax_score[f(Gi:D)],i=1,2…

(2)

式中,f(Gi:D)是依據(jù)數(shù)據(jù)集D而給出的網(wǎng)絡(luò)結(jié)構(gòu)Gi的度量評分。本文采用貪婪搜索算法進(jìn)行最優(yōu)搜索。

n個節(jié)點構(gòu)成的所有有向無環(huán)圖都可能作為貝葉斯網(wǎng)絡(luò)的搜索空間,Robinson給出了n個節(jié)點構(gòu)成貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)空間函數(shù)為

(3)

由式(3)可知,隨著網(wǎng)絡(luò)節(jié)點數(shù)的增加,網(wǎng)絡(luò)結(jié)構(gòu)空間呈指數(shù)級增加,當(dāng)n=10時,搜索空間結(jié)構(gòu)個數(shù)達(dá)到約4.2×1018,搜索空間巨大,采用傳統(tǒng)的搜索算法,必然導(dǎo)致結(jié)構(gòu)學(xué)習(xí)效率低下。鑒于從大規(guī)模數(shù)據(jù)庫中學(xué)習(xí)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)是一個NP問題,本文首先基于信息流構(gòu)建無約束0/1優(yōu)化問題,對初始網(wǎng)絡(luò)進(jìn)行全局處理,優(yōu)化結(jié)構(gòu)搜索空間;然后利用貪婪算法搜索結(jié)構(gòu)弧,同時根據(jù)信息流確定弧方向,完成網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)。由于初始搜索空間性能較好,并且弧和弧方向同步確定,本文提出的AGS算法可以高效、準(zhǔn)確地進(jìn)行最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)。

2 基于信息流的AGS算法

貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)實際上就是確定節(jié)點之間的因果關(guān)系,在眾多關(guān)于因果關(guān)系描述中,確定因果關(guān)系一般基于如下3個條件:

(1) 變量之間具有密切聯(lián)系,具有較強(qiáng)的因果依賴關(guān)系;

(2) 變量之間具有不對稱性,由原因得到結(jié)果的可能性大于由結(jié)果得到原因的可能性;

(3) 不存在隱藏變量和數(shù)據(jù)偏差。

梁湘三提出的信息流[12]能夠較優(yōu)地計算兩者之間的因果關(guān)系,因此可將其用于貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)。本節(jié)首先介紹基于信息流理論的全局因果分析和無約束0/1優(yōu)化問題的構(gòu)造,然后提出改進(jìn)型貪婪搜索算法。

2.1 信息流基本理論

信息流是梁湘三在轉(zhuǎn)移熵和Granger因果檢驗的基礎(chǔ)上,改進(jìn)的以一種定量方式來表征變量(或事件)之間因果關(guān)系的物理量,通過一個變量序列到另一個變量序列的信息時間速率來衡量因果關(guān)系,并且這種因果關(guān)系是單向的。兩個變量之間的信息交換量不僅說明了因果關(guān)系的大小,而且指明了方向。通過信息流或信息傳遞來衡量變量之間的因果關(guān)系,能夠?qū)崿F(xiàn)因果分析的公式化和定量化。

根據(jù)原始信息流形式,考慮一個維隨機(jī)系統(tǒng),則

dX=F(X;θ)dt+B(X;θ)dW

(4)

式中,F為漂移系數(shù)向量;θ為參數(shù);B=(bij)為擴(kuò)散系數(shù)矩陣;W為標(biāo)準(zhǔn)的Wiener過程向量。如果系統(tǒng)是二維,則變量X2到X1的信息流為

(5)

式中,ρ1是X1的邊緣概率密度;E是數(shù)學(xué)期望。從X2到X1的信息流;等于X1的邊際熵變化率與系統(tǒng)排除X2后的邊際熵變化率之差。

梁湘三在此基礎(chǔ)上提出基于信息流的因果分析,推導(dǎo)了變量序列間因果分析的定量公式,對于X1和X2序列,從后者到前者的信息流(單位:單位時間的轉(zhuǎn)移量)為

(6)

為了能夠進(jìn)行因果關(guān)系的強(qiáng)弱比較,本文采用標(biāo)準(zhǔn)化信息流公式[14],即

(7)

通過式(7)計算的標(biāo)準(zhǔn)化信息流τ2→1可以為零或非零。如果τ2→1=0,表示X2不會導(dǎo)致X1發(fā)生;如果τ2→1≠0,則兩者存在因果關(guān)系。此時,可以根據(jù)信息流的符號細(xì)分為兩種情況:τ2→1>0,表示X2導(dǎo)致X1趨向不確定,即X2是X1的原因;τ2→1<0,表示X2導(dǎo)致X1趨向穩(wěn)定,即X2不能作為X1的原因。特別指出,在顯著性水平為0.1時,τ2→1>1%可判斷因果關(guān)系是顯著的。

經(jīng)過上述分析可以看出,信息流非常適用于貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí),信息流的大小反映了網(wǎng)絡(luò)中節(jié)點之間依賴關(guān)系的強(qiáng)弱,即結(jié)構(gòu)弧的存在問題;信息流的正負(fù)則表征了結(jié)構(gòu)弧的方向,基于信息流能夠?qū)崿F(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)的整體化學(xué)習(xí)。

2.2 無約束0/1優(yōu)化問題的構(gòu)建

一個貝葉斯網(wǎng)絡(luò)可以進(jìn)行矩陣編碼,采用鄰接矩陣X=(xij)的形式表示,n個節(jié)點的網(wǎng)絡(luò)可以表示為

定義1基于鄰接矩陣X=(xij)和信息流τij構(gòu)造一個度量網(wǎng)絡(luò)全局因果程度的量,貝葉斯網(wǎng)絡(luò)全局因果度量為

全局因果度量C(X,α)取值越大,表明網(wǎng)絡(luò)的因果關(guān)系越顯著。在定義1的基礎(chǔ)上,可構(gòu)造無約束0/1優(yōu)化問題,即

(8)

基于信息流構(gòu)建的網(wǎng)絡(luò)全局因果度量,通過上述0/1優(yōu)化問題求解的最優(yōu)鄰接矩陣,對應(yīng)一有向拓?fù)浣Y(jié)構(gòu),即初始網(wǎng)絡(luò)結(jié)構(gòu)。根據(jù)信息流性質(zhì)可知,網(wǎng)絡(luò)結(jié)構(gòu)中所保留的有向弧是最優(yōu)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的候選弧,基于初始網(wǎng)絡(luò)結(jié)構(gòu)可生成因果關(guān)系最顯著的結(jié)構(gòu)搜索空間。

2.3 BIC評分函數(shù)與貪婪搜索算法描述

接下來,基于搜索評分方法進(jìn)行網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí),度量機(jī)制采用BIC評分函數(shù),搜索機(jī)制采用貪婪搜索(greedy search,GS)算法。BIC評分函數(shù)將貝葉斯網(wǎng)絡(luò)的復(fù)雜度和匹配程度綜合考慮[15],函數(shù)表達(dá)式為

(9)

式中,Dim(G)表示貝葉斯網(wǎng)絡(luò)維度;G表示貝葉斯網(wǎng)絡(luò)結(jié)構(gòu);D表示數(shù)據(jù)集。

GS算法的基本思想是從一個隨機(jī)生成的網(wǎng)絡(luò)模型出發(fā),對初始網(wǎng)絡(luò)進(jìn)行加弧、減弧和轉(zhuǎn)弧操作然后進(jìn)行評分。若評分增加則保留操作,該過程不斷迭代,直到網(wǎng)絡(luò)評分達(dá)到最優(yōu)則停止。需要指出,本文的GS算法不再進(jìn)行轉(zhuǎn)弧操作,弧的方向由信息流同步確定。GS算法具體流程描述如下。

GS搜索算法輸入 V為一組變量集,D關(guān)于V的完整數(shù)據(jù)集,初始貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)G0輸出 一個貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)G步驟 1 對初始網(wǎng)絡(luò)結(jié)構(gòu)評分G0→oldscore;步驟 2 依次對初始網(wǎng)絡(luò)進(jìn)行加弧、減弧操作并由信息流確定方向,結(jié)構(gòu)評分G'→tempscore;if (tempscore>oldscore) newscore≡tempscore并保留相應(yīng)弧操作;else newscore≡oldscore并舍棄相應(yīng)弧操作;end if步驟 3 if newscore→maxreturn G≡G'

2.4 基于信息流的AGS算法描述

貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)包括弧和弧方向的確定,但結(jié)構(gòu)學(xué)習(xí)中的搜索算法,如爬山算法、貪婪算法等,對于結(jié)構(gòu)弧方向的確定具有較大不確定性;弧方向的準(zhǔn)確判斷需要另外采用其他算法如條件相對平均熵、最大權(quán)重樹等,兩者只能分步進(jìn)行,不能進(jìn)行結(jié)構(gòu)的高效學(xué)習(xí)。

通過求解上述基于信息流構(gòu)建的0/1優(yōu)化問題,獲得一個初始網(wǎng)絡(luò)結(jié)構(gòu),以此初始結(jié)構(gòu)為基礎(chǔ)網(wǎng)絡(luò)生成結(jié)構(gòu)搜索空間,即搜索空間中的結(jié)構(gòu)弧只能在初始網(wǎng)絡(luò)的弧中隨機(jī)生成,而初始網(wǎng)絡(luò)結(jié)構(gòu)的弧是基于信息流確定的,是最優(yōu)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的候選弧,從而實現(xiàn)了對網(wǎng)絡(luò)搜索空間的優(yōu)化處理;并且搜索算法不再進(jìn)行轉(zhuǎn)弧操作,確定弧的同時由信息流判斷方向,即同步確定弧及弧方向。較原始的貪婪搜索方法更能獲得近似全局最優(yōu)結(jié)構(gòu),簡化了搜索程序,提高了搜索精度。AGS算法具體流程描述如下。

AGS算法輸入 V為一組變量集和一組關(guān)于V的完整數(shù)據(jù)集D輸出 最優(yōu)貝葉斯網(wǎng)絡(luò)G步驟 1 初始化: 設(shè)定0/1優(yōu)化和信息流分析中的顯著性水平;步驟 2 信息流分析: 計算每一對節(jié)點(Vi,Vj)的信息流,并進(jìn)行顯著性分析和因果分析;步驟 3 初始結(jié)構(gòu)確定: 構(gòu)造無約束0/1優(yōu)化問題并求解,確定弧和弧方向,得到初始結(jié)構(gòu)G0;步驟 4 GS算法搜索: 在G0的基礎(chǔ)上,用GS算法并結(jié)合信息流學(xué)習(xí)到最優(yōu)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)G。

3 仿真實驗

3.1 實驗環(huán)境與數(shù)據(jù)

本文采用經(jīng)典的Asia網(wǎng)(8個節(jié)點,8條有向邊)和Alarm網(wǎng)(37個變量,46條有向邊)檢驗所提出算法的有效性。以Matlab為平臺,根據(jù)給出的結(jié)構(gòu)和概率參數(shù)表,對上述網(wǎng)絡(luò)進(jìn)行采樣,分別獲得800組和3 200組樣本數(shù)據(jù),進(jìn)行仿真實驗。實驗所需相應(yīng)庫函數(shù)來自Murphy K P編寫的BNT工具箱。

由于搜索算法的隨機(jī)性,每個實驗均做10次求取平均值。為了表明結(jié)構(gòu)學(xué)習(xí)的準(zhǔn)確性,以正確弧(C)、丟失弧(L)、多余弧(E)和反向弧(R)的個數(shù)為評價指標(biāo),引入漢明距離[11]定量地評價學(xué)習(xí)到結(jié)構(gòu)的優(yōu)劣。

漢明距離=L+E+R

漢明距離越小,說明學(xué)習(xí)到的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)越準(zhǔn)確;當(dāng)漢明距離為0時,說明學(xué)習(xí)到的結(jié)構(gòu)為最優(yōu)結(jié)構(gòu)。

3.2 實驗結(jié)果與分析

首先,計算標(biāo)準(zhǔn)化信息流矩陣。以Asia網(wǎng)為例,不同樣本量的結(jié)果如表1、表2所示。

表1 800組樣本的信息流矩陣

表2 樣本量3 200組的信息流矩陣

需要指出:上述信息流矩陣中,信息流方向是由行變量指向列變量。舉例分析表中信息流含義,表1中如τSmoking→Bronchitis=0.010 6>0,τBronchitis→Smoking=-0.013 6<0,且兩者都大于1%,故可以判斷“Smoking”是“Bronchitis”的原因,即在貝葉斯網(wǎng)絡(luò)中可能存在弧“Smoking→Bronchitis”;再如τSmoking→Lunecancer=0.015 5>0,τLunecancer→Smoking=0.007 6>0,兩者雖然都大于0,但后者小于1%,因果關(guān)系不顯著,則可以判斷“Smoking”是“Lunecancer”的原因。表2中信息流矩陣與表1大體一致,表明采用信息流描述因果關(guān)系具有一定的穩(wěn)定性,但隨著樣本量的增加,因果關(guān)系會更為顯著,如τSmoking→Bronchitis=0.018 3,τBronchitis→Smoking=-0.016 7,與表1相比,“Smoking”作為“Bronchitis”的原因更加顯著。

然后,基于信息流構(gòu)造全局因果度量,求解無約束0/1優(yōu)化問題,并結(jié)合信息流進(jìn)行顯著性篩選和弧方向確定,獲得最優(yōu)初始網(wǎng)絡(luò)結(jié)構(gòu)。以Asia網(wǎng)為例,鄰接矩陣如圖2(a)所示,對應(yīng)初始網(wǎng)絡(luò)結(jié)構(gòu)如圖2(b)所示。

圖2 Asia網(wǎng)絡(luò)0/1優(yōu)化求解結(jié)果Fig.2 0/1 optimization solution of Asia network

最后,以此初始網(wǎng)絡(luò)結(jié)構(gòu)為基礎(chǔ)產(chǎn)生搜索空間,采用GS算法進(jìn)行搜索學(xué)習(xí)。以Asia網(wǎng)為例,迭代收斂曲線如圖3所示,不同樣本量學(xué)習(xí)到的結(jié)構(gòu)如圖4所示,在3 200組樣本時,本文算法學(xué)習(xí)到的網(wǎng)絡(luò)結(jié)構(gòu)與標(biāo)準(zhǔn)Asia網(wǎng)一致。

圖3 Asia網(wǎng)絡(luò)的收斂曲線Fig.3 Convergence curve of Asia network

為了說明本文提出的AGS算法進(jìn)行網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的有效性,將其與傳統(tǒng)GS算法、爬山算法和文獻(xiàn)[10]提出的改進(jìn)型遺傳算法(genetic algorithm,GA)學(xué)習(xí)網(wǎng)絡(luò)結(jié)構(gòu)的精度和時間進(jìn)行比較,將4種算法分別運(yùn)行10次,取平均值作為實驗結(jié)果,Asia網(wǎng)和Alarm網(wǎng)的結(jié)果如表3、表4所示。

圖4 不同樣本量的Asia網(wǎng)絡(luò)學(xué)習(xí)結(jié)構(gòu)Fig.4 Learning structure of Asia network at different sample sizes

樣本容量算法CLER漢明距離搜索時間/s800組本文AGS8.001.40.21.62.67改進(jìn)GA7.80.70.91.63.23.59GS3.64.81.92.18.89.09爬山2.75.31.33.810.437.693 200組本文AGS8.000.100.15.61改進(jìn)GA7.90.60.41.12.17.89GS5.22.71.21.95.820.91爬山4.53.11.22.97.2106.29

表4 Alarm網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)結(jié)果

從表3的實驗結(jié)果可得,對于節(jié)點較少的Asia網(wǎng),在800、3 200組樣本時,本文提出的AGS算法均能學(xué)習(xí)到較優(yōu)的結(jié)構(gòu),隨著樣本量的增加,學(xué)習(xí)的網(wǎng)絡(luò)結(jié)構(gòu)更優(yōu)。從表4的實驗結(jié)果可得,Alarm網(wǎng)在800組樣本時,所列4種算法的學(xué)習(xí)精度均較差,可見,對于37個節(jié)點的Alarm網(wǎng),800組樣本相對于網(wǎng)絡(luò)復(fù)雜度而言樣本集規(guī)模太小,故數(shù)據(jù)與結(jié)構(gòu)不能正確擬合。在3 200組樣本時,本文算法能夠?qū)W習(xí)到較優(yōu)結(jié)構(gòu)且在準(zhǔn)確性和學(xué)習(xí)效率上較其他算法優(yōu)勢明顯。

分析表3、表4可得,針對Asia網(wǎng)和Alarm網(wǎng)的結(jié)構(gòu)學(xué)習(xí),與傳統(tǒng)GS和爬山算法相比,本文提出的AGS算法在貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的準(zhǔn)確性和時間效率上都有顯著提升;與文獻(xiàn)[10]中的改進(jìn)型GA算法相比,兩者在搜索時間上差別不大,但在結(jié)構(gòu)準(zhǔn)確性上AGS算法有一定優(yōu)勢,尤其是在反向弧R一項中,反向弧個數(shù)顯著降低,即本文算法在弧方向確定上優(yōu)勢明顯。以Alarm網(wǎng)為例,繪制4種算法學(xué)習(xí)迭代曲線，如圖5所示。

圖5 不同算法迭代收斂曲線Fig.5 Iterative convergence curves of different algorithms

由圖5可得,本文基于信息流的全局因果分析所構(gòu)建的初始結(jié)構(gòu)搜索空間,明顯優(yōu)于其他3種算法,初始搜索空間的優(yōu)化避免了隨機(jī)搜索算法對網(wǎng)絡(luò)進(jìn)行過多的搜索,使得結(jié)構(gòu)學(xué)習(xí)的精度和時間效率得到顯著提高,實驗結(jié)果驗證了AGS算法的有效性。

4 結(jié) 論

從大規(guī)模數(shù)據(jù)集中進(jìn)行貝葉斯網(wǎng)絡(luò)自動建模,是貝葉斯網(wǎng)絡(luò)建模研究的難點之一。為有效進(jìn)行貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí),本文基于信息流的全局因果分析和0/1優(yōu)化提出一種AGS算法。首先基于信息流引入全局因果度量,構(gòu)造0/1優(yōu)化問題,得到最優(yōu)初始網(wǎng)絡(luò)結(jié)構(gòu);隨后以此結(jié)構(gòu)為基礎(chǔ)產(chǎn)生結(jié)構(gòu)搜索空間,通過貪婪算法搜索結(jié)構(gòu)弧,同時根據(jù)信息流確定弧方向,實現(xiàn)結(jié)構(gòu)的一體化學(xué)習(xí),得到最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu)。實驗表明,AGS算法與經(jīng)典算法相比能夠更優(yōu)近似全局最優(yōu)結(jié)構(gòu),信息流的引入實現(xiàn)了弧和弧方向的同步確定,簡化了搜索程序,使得算法在準(zhǔn)確性和時間性能上更高效。下一步研究的重點是信息流矩陣異常值的檢驗以及樣本量較小時如何獲得質(zhì)量較高的結(jié)構(gòu)。

參考文獻(xiàn)：

[1] COOPER G F, HERSKOVITS E. A Bayesian method for the induction of probabilistic networks from data[J]. Machine Learning, 1992, 9(4):309-347.

[2] BOUCKAERT R R. A stratified simulation scheme for inference in Bayesian belief networks[C]∥Proc.of the 10th International Conference on Uncertainty in Artificial Intelligence, 1994:110-117.

[3] CHICKERING D M, GEIGER D, HECKERMAN D. Learning Bayesian networks: search methods and experimental results[J]. General Information, 1995, 35(3):214-236.

[4] CHICKERING D M. Optimal structure identification with greedy search[J].Journal of Machine Learning Research,2003,3(3):507-554.

[5] LIU D Y, WANG F, LU Y N, et al. Research on learning Bayesian network structure based on genetic algorithms[J]. Chinese Journal of Electronics, 2001, 38(8):572-589.

[6] PINTO P C, NAGELE A, DEJORI M, et al. Using a local discovery ant algorithm for Bayesian network structure learning[J]. IEEE Trans.on Evolutionary Computation, 2009, 13(4):767-779.

[7] WANG T, YANG J. A heuristic method for learning Bayesian networks using discrete particle swarm optimization[J]. Knowledge and Information Systems, 2010, 24(2):269-281.

[8] 范敏, 黃席樾, 石為人,等. 一種改進(jìn)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法[J]. 系統(tǒng)仿真學(xué)報, 2008, 20(17):4613-4617.

FAN M, HUNG X Y, SHI W R, et al. Improved Bayesian network structure learning algorithm[J]. Journal of System Simulation, 2008, 20 (17): 4613-4617.

[9] 劉寶寧, 章衛(wèi)國, 李廣文,等. 一種改進(jìn)遺傳算法的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)[J]. 西北工業(yè)大學(xué)學(xué)報, 2013, 31(5):716-721.

LIU B N, ZHANG W G, LI G W, et al. A Bayesian network structure learning for improved genetic algorithm[J]. Journal of Northwestern Polytechnical University,2013,31(5):716-721.

[10] 汪春峰, 張永紅. 基于無約束優(yōu)化和遺傳算法的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法[J]. 控制與決策, 2013(4):618-622.

WANG C F, ZHANG Y H. Research on Bayesian network structure learning method based on unconstrained optimization and genetic algorithm[J].Control and Decision,2013(4):618-622.

[11] 劉向南. 因果貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)研究[D]. 合肥:合肥工業(yè)大學(xué), 2012.

LIU X N. Study on Bayesian network structure learning[D]. Hefei: Journal of Hefei University of Technology, 2012.

[12] LIANG X S. Unraveling the cause-effect relation between time series[J]. Physical Review E Statistical， Nonlinear & Soft Matter Physics, 2014, 90(5/1):052150.

[13] 史志富. 貝葉斯網(wǎng)絡(luò)理論及其在軍事系統(tǒng)中的應(yīng)用[M]. 北京:國防工業(yè)出版社, 2012.

SHI Z F. Bayesian network theory and its application in military system[M]. Beijing: Defense Industry Press, 2012.

[14] LIANG X S. Normalizing the causality between time series[J]. Physical Review E Statistical, Nonlinear & Soft Matter Physics, 2015, 92(2):022126.

[15] 邸若海, 高曉光. 基于限制型粒子群優(yōu)化的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)[J]. 系統(tǒng)工程與電子技術(shù), 2011, 33(11):2423-2427.

DI R H, GAO X G. Bayesian Network structure learning based on restricted particle swarm optimization[J]. Systems Engineering and Electronics, 2011, 33 (11): 2423-2427.