仝兆景,李金香,喬征瑞

(河南理工大學(xué) 電氣工程與自動化學(xué)院,河南 焦作 454003)

貝葉斯網(wǎng)絡(luò)(BN)結(jié)合概率論和圖論的知識,能解決概率事件的不確定性問題,是目前不確定知識表達和推理領(lǐng)域較有效的理論模型之一。BN具備多元知識圖解可視化的能力,能通過有限不完整的知識推理并融合多源信息,被應(yīng)用于設(shè)備故障診斷[1]、醫(yī)學(xué)診斷[2]、圖像處理[3]、可靠性分析與風(fēng)險分析[4]等多領(lǐng)域。BN還具有處理變量不確定性與不完整性的能力,可被用于變壓器[5]、電網(wǎng)[6]和輸電線路[7]等多種故障診斷領(lǐng)域[8-10]。但是基于傳統(tǒng)的BN具有節(jié)點多和網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜等缺點,影響了其在實際使用中的性能。元啟發(fā)式搜索策略被廣泛應(yīng)用于BN結(jié)構(gòu)學(xué)習(xí),對識別分類算法具有良好的改進效果[11-12]。文獻[13]通過交叉變異策略對BN節(jié)點序?qū)?yōu),在小樣本學(xué)習(xí)下的BN結(jié)構(gòu)較優(yōu),但其在大樣本學(xué)習(xí)下的結(jié)構(gòu)較差。文獻[14]采用獨立性測試和爬山算法的最大-最小爬山算法優(yōu)化BN結(jié)構(gòu),降低了搜索空間復(fù)雜度。目前有研究人員利用改進鯨魚算法對BN結(jié)構(gòu)尋優(yōu),但復(fù)雜度較高[15]。文獻[16]將PC算法與改進的粒子群算法結(jié)合來優(yōu)化BN結(jié)構(gòu),獲得了較好的學(xué)習(xí)效果,但該方法的參數(shù)設(shè)置較多,在標準貝葉斯網(wǎng)絡(luò)的測試中不穩(wěn)定。

BN由表示隨機變量和機率分配的拓撲構(gòu)造與基本參數(shù)構(gòu)成,故BN的學(xué)習(xí)包括結(jié)構(gòu)學(xué)習(xí)和參數(shù)學(xué)習(xí)。結(jié)構(gòu)學(xué)習(xí)分為3種:基于約束的學(xué)習(xí)方法、基于分數(shù)的學(xué)習(xí)方法和混合學(xué)習(xí)方法。將基于約束的方法通過條件獨立測試(Conditional Independence,CI)來學(xué)習(xí)BN結(jié)構(gòu)[17]。基于分數(shù)的學(xué)習(xí)方法應(yīng)用較廣泛,它可將專家知識作為結(jié)構(gòu)先驗靈活地引入到學(xué)習(xí)過程中。K2和粒子群算法[18]等群智能算法都是基于分數(shù)的方法?；旌戏椒▽⒍呓Y(jié)合起來,通過條件獨立測試減少搜索空間,并采用基于分數(shù)的方法進行結(jié)構(gòu)學(xué)習(xí)。

基于上述分析,本文提出一種基于PC-SSA(Sparrow Search Algorithm)的BN混合結(jié)構(gòu)學(xué)習(xí)方法。將通過PC算法生成的初始網(wǎng)絡(luò)圖作為結(jié)構(gòu)先驗,并基于它們生成初始解。采用麻雀搜索算法作為BN的分數(shù)學(xué)習(xí)算法,提高網(wǎng)絡(luò)結(jié)構(gòu)的尋優(yōu)性能。本文所提算法參數(shù)設(shè)置少,在標準網(wǎng)絡(luò)上的測試分數(shù)更接近標準分數(shù)。

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

1.1 貝葉斯網(wǎng)絡(luò)理論

貝葉斯網(wǎng)絡(luò)的數(shù)學(xué)形式用B(G,P)表示,其中G為有向無環(huán)圖(Directed Acyclic Graph,DAG),包含節(jié)點、弧線以及箭頭3個元素。節(jié)點一般為離散型隨機變量,通過直線連接。箭頭用于描述節(jié)點之間的關(guān)聯(lián)關(guān)系,由父節(jié)點指向子節(jié)點。P為條件概率,用來說明有向線連接的兩個目標節(jié)點或者條件節(jié)點之間變量的概率關(guān)系。貝葉斯網(wǎng)絡(luò)通過其節(jié)點間的父子關(guān)系和概率論的知識對不確定問題進行概率推理。

貝葉斯網(wǎng)絡(luò)中的全概率的定義如下

(1)

當貝葉斯網(wǎng)絡(luò)節(jié)點數(shù)量較多時,以N=(G,Θ)代替上述計算式,其中G=〈V,E〉,V={V1,V2,…,Vn}代表貝葉斯網(wǎng)絡(luò)的所有節(jié)點集合體,E代表有向無環(huán)圖中全部有向邊的集合,Θ={Θ1,Θ2,…,Θn}表示每個節(jié)點Vi在已知其父節(jié)點pa(vi)時的條件概率表。

假設(shè)節(jié)點Vi=(vi),其父節(jié)點集合為pa(vi),則其聯(lián)合概率分布為

(2)

對于節(jié)點Vi=(vi)中的任一隨機變量X,其聯(lián)合概率分布如下所示。

(3)

根據(jù)隨機變量的聯(lián)合概率分布計算式,進一步將其表示為以下形式。

(4)

以某節(jié)點為例,通過其父節(jié)點信息,在BN體系中根據(jù)式(4)可知,如果某節(jié)點其父節(jié)點的狀態(tài)信息可知,那么該節(jié)點的條件完全獨立于由其父節(jié)點中給定的任何非子節(jié)點所組成的集合體。以節(jié)點的獨立性為前提,對提出的問題進行分析,選取特征變量后對數(shù)據(jù)進行預(yù)處理,再進行BN學(xué)習(xí)。本文構(gòu)建貝葉斯網(wǎng)絡(luò)的流程如圖1所示。

圖1 貝葉斯網(wǎng)絡(luò)決策流程Figure 1.Flow of Bayesian network decision

1.2 基于約束的結(jié)構(gòu)學(xué)習(xí)

基于約束的學(xué)習(xí)方法一般采用條件獨立性檢驗或互信息檢查確定變量間的相互依賴性或獨立性關(guān)系。該方法的性能主要取決于CI測試的數(shù)量和約束集的大小。由于約束集和高階CI測試數(shù)量增加,基于約束的方法精度將降低,因此本文選用CI確定變量間的依賴關(guān)系。PC算法便是利用CI測試來確定變量間依賴關(guān)系的典型算法之一,其通過檢測兩個最鄰近節(jié)點子集的有向分離(D-separation)來減少搜索空間與時間復(fù)雜度。本文通過PC算法選擇初始網(wǎng)絡(luò),對網(wǎng)絡(luò)結(jié)構(gòu)進行修改。

根據(jù)D-separation思想確立網(wǎng)絡(luò)結(jié)構(gòu)中節(jié)點間的依賴關(guān)系,對任意3個以有效依賴關(guān)系邊相連的節(jié)點X-Z-Y,其依賴關(guān)系為圖2所示的類型之一。

圖2 貝葉斯網(wǎng)絡(luò)中的4種依賴關(guān)系Figure 2. Four kinds of dependencies in Bayesian network

D-separation可將無向圖擴展為DAG。節(jié)點集合O能D分隔節(jié)點i和節(jié)點j,當且僅當給定O時,i與j不存在有效路徑,即i和j在O條件下獨立,記作i⊥j∣O。已知有向無環(huán)圖G以及節(jié)點X、Y和點集O,當X和Y之間的路徑滿足以下任意一條結(jié)論時,該路徑堵塞,那么X、Y關(guān)于O條件獨立:1)若節(jié)點Z屬于圖2的a、b、c3種情況,且Z包含在點集O中;2)若節(jié)點Z屬于圖2中的d情況,且Z不包含在點集O中。

D-separation可將判斷BN邊的方向規(guī)則分為3條:

規(guī)則1如圖3所示,如果X→Y-Z,則將Y-Z變?yōu)閅→Z;

圖3 方向判斷規(guī)則1Figure 3. Direction judgment rule 1

規(guī)則2如圖4所示,如果X→Z→Y,則將X-Y變?yōu)閄→Y;

圖4 方向判斷規(guī)則2Figure 4. Direction judgment rule 2

規(guī)則3如圖5所示,如果X-Z1→Y,X-Z2→Y,且Z1,Z2不相鄰,則將X-Y變?yōu)閄→Y。

圖5 方向判斷規(guī)則3Figure 5. Direction judgment rule 3

1.3 基于分數(shù)的結(jié)構(gòu)學(xué)習(xí)

基于分數(shù)的學(xué)習(xí)方法主要思想是遍歷所有可行結(jié)構(gòu),根據(jù)評分函數(shù)尋最優(yōu)結(jié)構(gòu)。常用的評分函數(shù)有貝葉斯狄利克雷等價(Bayesian Dirichlet Equivalent,BDE)、最小描述長度(Minimum Description Length,MDL)和貝葉斯信息準則(Bayesian Information Criterion,BIC)。與BDE相比,基于MDL或BIC的BN結(jié)構(gòu)學(xué)習(xí)更容易,BDE則需考慮參數(shù)的先驗分布。由于學(xué)習(xí)結(jié)構(gòu)的復(fù)雜性,BDE傾向于選擇更復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu),而MDL和BIC傾向于選擇更簡單的網(wǎng)絡(luò)結(jié)構(gòu)。在實際應(yīng)用中,MDL和BIC的計算結(jié)果比較簡單。BIC評分函數(shù)較簡單,可以更好地均衡計算的精準度和網(wǎng)絡(luò)結(jié)構(gòu)的復(fù)雜性,在確保獲得最優(yōu)貝葉斯網(wǎng)絡(luò)的同時提升了BN的學(xué)習(xí)效率。

根據(jù)以上分析,本文以BIC評估學(xué)習(xí)過程中的DAG。假設(shè)一個BN含有n個節(jié)點,其BIC定義為

(5)

式中,ri表示節(jié)點xi可能取值的種數(shù);qi表示節(jié)點xi的父節(jié)點可能取值的種數(shù)。計算式的前半部分為BN的似然對數(shù),表示BN與樣本集間的匹配程度,后半部分表示BN的復(fù)雜度。

BIC評分函數(shù)可判斷搜索流程中的可行結(jié)構(gòu)以及數(shù)據(jù)的匹配度,其評價值越高,函數(shù)的適應(yīng)度值越高,樣本集與網(wǎng)絡(luò)結(jié)構(gòu)的匹配度越高,網(wǎng)絡(luò)結(jié)構(gòu)越優(yōu)。搜索算法用來計算由各種可能構(gòu)造形成的空間上搜索分數(shù)最高的結(jié)構(gòu)。其中,啟發(fā)式算法被普遍用于搜索可行解,本文通過群智能算法尋找BN空間,從而優(yōu)化其結(jié)構(gòu)。

2 麻雀搜索算法

麻雀搜索算法[19](Sparrow Search Algorithm,SSA)改善了優(yōu)化搜索空間的探索和利用方式,促進了優(yōu)化搜尋空間技術(shù)的研究與使用。該方法在搜尋準確性、收斂速率、穩(wěn)定性以及避免局部最優(yōu)值問題等方面都優(yōu)于現(xiàn)有方法,故本文在基于分數(shù)學(xué)習(xí)的BN結(jié)構(gòu)優(yōu)化中采用SSA來進一步提升算法性能。

假設(shè)d維空間中有n只麻雀,則麻雀組成的種群X以及每只麻雀對應(yīng)的適應(yīng)度函數(shù)F表示為

(6)

(7)

探索者的位置在t次迭代中更新為

(8)

其中,j為維值,且j=1,2,…,d;α∈(0,1];itermax為最大迭代次數(shù);R2為報警值,且R2∈[0,1];ST為安全閾值;Q代表所有滿足于正態(tài)分布的隨機數(shù),L為1×dim的全1矩陣。當R2

追隨者的位置更新計算式為

(9)

其中,Xworst為當前迭代中全局最差的麻雀位置;XP為當前迭代全局最優(yōu)的麻雀位置;A為1×dim隨機數(shù)為1或-1矩陣。當i>n/2時,當前追隨者的位置較差,找不到食物,需要飛往其他地區(qū)覓食;反之則表示當前追隨者的位置較好,將會跟隨離自己最近的適應(yīng)度值高的探索者覓食。

警戒者的位置更新計算式為

(10)

其中,Xbest代表當前迭代中全局最佳的麻雀位置;β代表一個服從平均數(shù)為0、方差為1的正態(tài)分布的隨機數(shù);K代表下一個隨機數(shù),取值范圍為[-1,1];ε表示最小的隨機常數(shù);fi表示當前迭代麻雀的適應(yīng)度值;fg和fw分別表示最優(yōu)和最差的適應(yīng)度值。當fi>fg時,當前麻雀的位置處于易被捕食者發(fā)現(xiàn)的種群邊緣,此時麻雀需要尋找更優(yōu)的位置覓食;當fi=fg時,當前麻雀處于種群中間的位置,此時麻雀會靠近距離自己較近的同伴,以此來縮減它們的危險區(qū)域。

3 基于PC-SSA的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)

3.1 貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的編碼設(shè)計

本文采用SSA搜索DAGs空間。與其他啟發(fā)式算法相比,麻雀搜索算法不需要學(xué)習(xí)較多參數(shù),適用于各種搜索空間,能夠快速找到最優(yōu)解。本文結(jié)合BN知識,將尋找最優(yōu)BN結(jié)構(gòu)的過程等價為最優(yōu)麻雀位置的過程?；赑C-SSA算法的結(jié)構(gòu)學(xué)習(xí),便是將數(shù)據(jù)集中學(xué)習(xí)BN結(jié)構(gòu)的過程等價為麻雀尋找最優(yōu)位置的過程。

對于有n個隨機變量的固定域S={0,1},其BN用n×n鄰接矩陣a表示,aij的元素定義如下所示。

(11)

以癌癥網(wǎng)絡(luò)為例,其BN以及編碼如圖6所示,網(wǎng)絡(luò)結(jié)構(gòu)包含5個節(jié)點和4個弧。根據(jù)圖6可知,污染和吸煙會導(dǎo)致癌癥,癌癥會導(dǎo)致患者X-射線檢測結(jié)果呈陽性并出現(xiàn)呼吸困難的癥狀。

圖6 癌癥網(wǎng)絡(luò)及其鄰接矩陣Figure 6. Cancer network and its adjacency matrix

3.2 貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)實現(xiàn)過程

首先采用PC算法生成具有結(jié)構(gòu)先驗的初始網(wǎng)絡(luò),然后利用SSA算法對最優(yōu)DAG結(jié)構(gòu)進行搜尋。本文的貝葉斯網(wǎng)絡(luò)采用n個節(jié)點,m個種群個體,即(n,m)維的搜索空間。第i個個體的位置為Xi={X11,…,X1n,X21,…,X2n,…,Xn1,…,Xnn}。在搜索最優(yōu)結(jié)構(gòu)的過程中,每只麻雀的位置都代表一種有效的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu),以BIC評分函數(shù)作為算法尋優(yōu)過程的適應(yīng)度函數(shù),通過測試的樣本集對當前DAG評分。在麻雀的位置更新過程中,對當前DAG不斷進行添加弧、刪減弧和修正非法網(wǎng)絡(luò)等操作,具體過程如下所示:

步驟1初始化網(wǎng)絡(luò)結(jié)構(gòu)的參數(shù)。麻雀種群規(guī)模為n,最大迭代次數(shù)為max_iteration,BN搜索空間維度為dim以及上下界,預(yù)警值ST=0.6,探索者比例PD=0.7,意識到有危險的麻雀比例為SD=0.2。按照比例劃分訓(xùn)練集和測試集,將訓(xùn)練數(shù)據(jù)集D作為輸入。

步驟2根據(jù)PC算法生成初始網(wǎng)絡(luò),通過CI測試進行加減邊并測試節(jié)點的獨立性,再根據(jù)方向判斷規(guī)則生成完全部分DAG。最后,結(jié)合專家經(jīng)驗生成初始麻雀種群,對網(wǎng)絡(luò)結(jié)構(gòu)進行修復(fù)。

步驟3根據(jù)式(5)計算當前麻雀個體的BIC函數(shù)評分值并排序記錄最優(yōu)DAG結(jié)構(gòu)。

步驟4判斷算法是否達到最大迭代次數(shù),若達到終止條件,則算法結(jié)束并返回全局最優(yōu)DAG;反之則返回步驟3。

基于PC-SSA的BN流程如圖7所示。

圖7 基于PC-SSA算法的BN流程Figure 7. Flow of BN based on PC-SSA algorithm

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

為驗證本文所提算法的尋優(yōu)性能,選取CANCER網(wǎng)絡(luò)(圖6)、ASIA網(wǎng)絡(luò)(圖8)和INSURANCE網(wǎng)絡(luò)(圖9)3個標準BN測試BIC評分。這3個網(wǎng)絡(luò)的節(jié)點和有向邊的數(shù)量遞增,復(fù)雜程度也逐漸增高,能有效測試算法在簡單網(wǎng)絡(luò)和復(fù)雜網(wǎng)絡(luò)的尋優(yōu)能力。其中,CANCER網(wǎng)絡(luò)包含5個節(jié)點和4條有向邊,ASIA網(wǎng)絡(luò)包含8個節(jié)點和8條有向邊,INSURANCE包含27個節(jié)點和52條有向邊。

圖8 ASIA網(wǎng)絡(luò)Figure 8. ASIA network

圖9 INSURANCE網(wǎng)絡(luò)Figure 9. INSURANCE network

將數(shù)據(jù)集劃分為500、1 000、1 500和2 000,分別在上述3個網(wǎng)絡(luò)進行實驗驗證,實驗結(jié)果如表1所示。

由表1可知,本文提出的PC-SSA可得到接近真實網(wǎng)絡(luò)的BIC分數(shù)。在ASIA網(wǎng)絡(luò)的1 000個樣本的測試中,標準BIC分數(shù)為-2 246.94,本文算法得到的BIC分數(shù)為-2 247.82,表明通過PC-SSA獲得的網(wǎng)絡(luò)是一個合理的亞洲網(wǎng)絡(luò)結(jié)構(gòu),并且在尋優(yōu)過程中獲得的分數(shù)接近標準分數(shù)。隨著網(wǎng)絡(luò)復(fù)雜度的增高,該算法在測試網(wǎng)絡(luò)上的BIC分數(shù)與標準分數(shù)誤差增大。PC-SSA在ASIA網(wǎng)絡(luò)上的平均測試結(jié)果最優(yōu),在2 000樣本的測試中,最小誤差為0.2。PC-SSA在網(wǎng)絡(luò)復(fù)雜的INSURANCE網(wǎng)絡(luò)上的測試結(jié)果最差,在2 000樣本的測試中,其最大誤差達557.5。

將本文算法與粒子群優(yōu)化 (Particle Swarm Optimization, PSO) 算法以及未加先驗結(jié)構(gòu)的SSA進行比較,樣本容量為500,分別在CANCER、ASIA和INSURANCE網(wǎng)絡(luò)上進行對比實驗,結(jié)果如圖10所示。

(a)

由圖10可知,采用SSA的評分高于PSO;相比于PSO和SSA,PC-SSA初始評分更高,表明采用PC生成的先驗結(jié)構(gòu)提高了算法的初始評分;SSA提高了整體的BIC分數(shù),本文算法的初始值和最終評分都高于其他算法。該結(jié)果證明了本文采用的PC算法可以有效地提高BN結(jié)構(gòu)學(xué)習(xí)問題的初始解。在初始解最優(yōu)的情況下,SSA實現(xiàn)了更好的搜索過程,得到更好的最終解。隨著迭代次數(shù)的增加,BIC分數(shù)趨于不變,表明本文方法可以收斂到BN結(jié)構(gòu)學(xué)習(xí)問題的固定解,且本文算法比其他算法能夠更快地搜索到最優(yōu)解。將圖10收斂的BIC分數(shù)和在達到最佳BIC分數(shù)時的迭代次數(shù)進行比較,結(jié)果如表2所示。

表2 不同算法在標準貝葉斯網(wǎng)絡(luò)上的實驗結(jié)果

由表2可知,本文算法比其他算法的迭代次數(shù)少,BIC評分更接近標準分數(shù)整體,性能更優(yōu),說明PC-SSA更易實現(xiàn),收斂速度更快,整體評分高,性能更優(yōu)良。

5 結(jié)束語

本文提出了一種基于PC-SSA的混合方法優(yōu)化貝葉斯網(wǎng)絡(luò)結(jié)構(gòu),并通過CANCER網(wǎng)絡(luò)、ASIA網(wǎng)絡(luò)和INSURANCE網(wǎng)絡(luò)進行了測試。實驗結(jié)果證明了基于PC-SSA學(xué)習(xí)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的評分更高,收斂速度更快,能在最短時間內(nèi)尋出最優(yōu)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu),獲得與標準評分誤差最小的BIC評分。本文采用的PC算法對網(wǎng)絡(luò)初始解的優(yōu)化也說明了結(jié)構(gòu)先驗在BN結(jié)構(gòu)學(xué)習(xí)中的重要性。