劉浩然, 李 晟, 崔少鵬, 王念太, 蔡炎濱, 時(shí)倩蕊, 張力悅

(1.燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島 066004；2.河北省特種光纖與光纖傳感重點(diǎn)實(shí)驗(yàn)室，河北 秦皇島 066004)

1 引 言

貝葉斯網(wǎng)絡(luò)(Bayesian network, BN)是表示隨機(jī)變量之間相互依賴或獨(dú)立關(guān)系的概率圖模型。網(wǎng)絡(luò)結(jié)構(gòu)表示為有向無環(huán)圖,用來定性地表示變量之間的依賴關(guān)系[1],參數(shù)為節(jié)點(diǎn)間條件概率分布,用來定量地描述變量之間的依賴程度[2]。由于BN結(jié)構(gòu)在表示和推理方面的強(qiáng)大能力[3],使其在生物醫(yī)學(xué)[4]、故障診斷[5]、狀態(tài)監(jiān)測[6]等領(lǐng)域得到了廣泛的應(yīng)用。

BN學(xué)習(xí)可以分為結(jié)構(gòu)學(xué)習(xí)和參數(shù)學(xué)習(xí)[7],參數(shù)學(xué)習(xí)需要在結(jié)構(gòu)已知的基礎(chǔ)上進(jìn)行,所以貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)(BN structure learning,BNSL)是基礎(chǔ)。BNSL可分為精確學(xué)習(xí)算法[8]和近似學(xué)習(xí)算法[9]。精確學(xué)習(xí)算法是遍歷整個(gè)搜索空間,然后找到全局最優(yōu)解,但是通常算法效率不高,大型網(wǎng)絡(luò)結(jié)構(gòu)甚至不可實(shí)現(xiàn);近似學(xué)習(xí)算法通常采用啟發(fā)式策略對結(jié)構(gòu)空間搜索以獲得最優(yōu)解,其計(jì)算效率較高,所以近似學(xué)習(xí)算法得到廣泛研究和應(yīng)用。

近似學(xué)習(xí)算法一般分為3類:基于約束[10]、基于評(píng)分搜索[11]和基于混合搜索[12]。除以上方法外,結(jié)合仿生學(xué)算法的BNSL發(fā)展迅速,許多優(yōu)質(zhì)算法被提出,如遺傳算法(genetic algorithm, GA)[13]、狼群算法[14]、蟻群算法[15]、鯨魚群算法[16]、粒子群優(yōu)化(particle swarm optimization, PSO)[17]等。

PSO算法因?yàn)槠渚幋a方式簡單、全局搜索能力強(qiáng)、收斂速度快而被廣泛地應(yīng)用到BNSL中。文獻(xiàn)[18]提出一種基于二進(jìn)制粒子群算法的貝葉斯網(wǎng)絡(luò)學(xué)習(xí)算法;文獻(xiàn)[19]運(yùn)用混沌粒子群算法得到最優(yōu)位置,即最優(yōu)初始網(wǎng)絡(luò)結(jié)構(gòu),以此獲得節(jié)點(diǎn)排序,并帶入K2算法,從而獲得最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu);文獻(xiàn)[20]將PSO算法和GA算法相結(jié)合,利用GA的交叉和變異重新定義粒子的更新規(guī)則,并利用馬爾科夫鏈定理證明了該算法的全局收斂性。以上3個(gè)算法都是對PSO算法進(jìn)行了改進(jìn),但是其初始結(jié)構(gòu)都是隨機(jī)生成的,這導(dǎo)致算法的隨機(jī)性過大,結(jié)果和效率都不太好。文獻(xiàn)[21]提出了一種基于進(jìn)化策略的BNSL算法,并設(shè)計(jì)了一種新的初始結(jié)構(gòu)編碼方法,以避免生成非法結(jié)構(gòu)循環(huán)圖。然而,由于編碼相對復(fù)雜,后續(xù)計(jì)算需要較高的計(jì)算機(jī)性能,并且不容易實(shí)現(xiàn)。文獻(xiàn)[22]提出PC算法構(gòu)建初始結(jié)構(gòu),用帶有突變算子的雙速度離散粒子群優(yōu)化BN結(jié)構(gòu),該文的優(yōu)化策略是利用突變算子更新粒子的位置,從而使粒子向最優(yōu)解的位置不斷搜索,但是生成的初始解太隨機(jī)化并且雙速度離散化過程太發(fā)散,所以最終尋找到的最優(yōu)粒子并不好。文獻(xiàn)[23]首先用PC算法構(gòu)建出定向網(wǎng)絡(luò)結(jié)構(gòu),將結(jié)構(gòu)轉(zhuǎn)化為一個(gè)基因組,然后利用隨機(jī)數(shù)控制基因組的每一個(gè)基因進(jìn)行均勻變異和均勻交叉操作。實(shí)驗(yàn)證明,在相同數(shù)據(jù)集的小網(wǎng)絡(luò)中,能夠?qū)W習(xí)到評(píng)分較高的網(wǎng)絡(luò)并具有較好的收斂性,但其更新規(guī)則中的交叉和變異概率的選擇過于隨機(jī),失去了GA算法的優(yōu)勢。

本文提出的混合簡化粒子群算法優(yōu)化貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法(hybrid simplified particle swarm algorithm-Bayesian network structure learning,BNs-HsPSO)通過最大支撐樹策略生成無向結(jié)構(gòu),然后利用V-結(jié)構(gòu)和條件相對平均熵(conditional relative average entropy,CRAE)共同確定初始結(jié)構(gòu)的方向,此方式有效減少了后期多次循環(huán)迭代尋優(yōu)的時(shí)間,提高了搜索效率。由于粒子群算法常用于解決連續(xù)性問題,為了更好地用于解決本文BNSL離散型問題,根據(jù)文獻(xiàn)[24]提出的不含速度項(xiàng)的簡化粒子群算法公式,然后結(jié)合GA算法的交叉和變異策略,生成了新的改進(jìn)粒子群算法迭代公式,由此可實(shí)現(xiàn)BNSL的優(yōu)化。在更新過程中,本文自定義變異和交叉概率,從而避免迭代過程的冗余;增加副粒子增緩策略優(yōu)化未迭代更新的粒子進(jìn)而增加種群多樣性,避免算法陷入局部最優(yōu)。因此最終搜索到含有更多正確邊的BN結(jié)構(gòu)并增強(qiáng)了算法的學(xué)習(xí)效率。

2 BNs-HsPSO算法研究

2.1 BNs-HsPSO算法初始種群構(gòu)建

設(shè)節(jié)點(diǎn)集合為X={x1,x2,…,xn},利用互信息公式(1)計(jì)算任意兩節(jié)點(diǎn)xi和xj的互信息I(xi,xj),并對集合X中所有的節(jié)點(diǎn)關(guān)系進(jìn)行計(jì)算,最后得到X的互信息矩陣XI={I(xi,xj)}n×n。

(1)

式中:P(xi,xj)表示xi和xj的聯(lián)合概率;P(xi)表示xi的邊緣概率;P(xj)表示xj的邊緣概率?；バ畔⒕哂蟹秦?fù)對稱性,即I(xi,xj)=I(xj,xi)。I(xi,xj)>0說明兩節(jié)點(diǎn)xi和xj之間存在相互影響,I(xi,xj)=0表示兩節(jié)點(diǎn)是相互獨(dú)立的。

令T=XI,從集合X中選擇任意節(jié)點(diǎn)xi作為起始點(diǎn),并令集合V={xi},同時(shí)從集合X-V中尋找另一個(gè)節(jié)點(diǎn)xj,使得互信息值在XI中為最大,同時(shí)用無向邊連接xj,xp。并將節(jié)點(diǎn)xj也加入到集合V中;重復(fù)以上步驟,直到V=X時(shí),此時(shí),便可得到最大支撐樹結(jié)構(gòu)矩陣T。

此時(shí)T中兩節(jié)點(diǎn)間只有無向邊,本篇采用V-結(jié)構(gòu)[25]和CRAE[2]共同確定無向邊的方向,具體過程如下。

V-結(jié)構(gòu):對于無遮擋元組,若滿足xi和xk相連,xj和xk相連,同時(shí)xi和xj不相連的三節(jié)點(diǎn)連接關(guān)系,如果有xi→xk且xj→xk,即可形成xi→xk←xj的V-結(jié)構(gòu)。通過公式(2)和(3)確定無遮擋三元組是否形成V-結(jié)構(gòu),當(dāng)I>0可確定xi→xk←xj;而當(dāng)I≤0時(shí),則不形成V結(jié)構(gòu),不對節(jié)點(diǎn)進(jìn)行定向。

(2)

(3)

式中:PXi,Xj,Xk(xi,xj,xk)表示節(jié)點(diǎn)xi,xj,xk的聯(lián)合概率;PXi,Xk(xi,xk)表示節(jié)點(diǎn)xi,xk的聯(lián)合概率。PXk(xk)表示xk的先驗(yàn)概率。

通過V-結(jié)構(gòu)確定了部分無向邊的方向,對于剩余的無向邊通過CRAE策略來確定方向。CRAE策略簡潔且高效,具體計(jì)算公式如下:

(4)

(5)

(6)

式中:|xi|為變量xi的取值個(gè)數(shù);H(xi)為離散隨機(jī)變量xi的熵;H(xi|xj)是離散變量xi在已知xj條件下的不確定性。如果CRAE(xi→xj)≥CRAE(xj→xi),則兩節(jié)點(diǎn)方向?yàn)閤i→xj,否則兩節(jié)點(diǎn)方向?yàn)閤j→xi。

經(jīng)過對初始結(jié)構(gòu)定向,表示無向圖的矩陣XM轉(zhuǎn)化為表示有向圖的矩陣XG。在XG矩陣中,若XG(xi,xj)=1表示在網(wǎng)絡(luò)結(jié)構(gòu)中的指定方向?yàn)閤i→xj,即表明xi是xj的父節(jié)點(diǎn)。以矩陣XG為原始矩陣,對XG隨機(jī)的增加一條邊或者反轉(zhuǎn)一條邊,從而形成一個(gè)新的矩陣,重復(fù)生成多個(gè)這樣的新矩陣,直到加邊或轉(zhuǎn)邊不會(huì)生成新的矩陣為止。存儲(chǔ)這些矩陣的集合為G,G={XG1,XG2,…,XGm},m為矩陣個(gè)數(shù)。

2.2 BNs-HsPSO算法尋優(yōu)

將G中的m個(gè)結(jié)構(gòu)看作m個(gè)粒子的位置,m為初始的粒子群中個(gè)體數(shù)目,個(gè)體最優(yōu)粒子的位置即為當(dāng)前待優(yōu)化的結(jié)構(gòu)矩陣,全局最優(yōu)粒子的位置是評(píng)分值最大的結(jié)構(gòu)矩陣。變異操作的目的是避免陷入局部最優(yōu),當(dāng)需更新粒子的評(píng)分值和整個(gè)粒子群的平均評(píng)分值差異性在閾值范圍內(nèi)時(shí)變異;交叉操作是增加種群多樣性,此時(shí)交叉操作是優(yōu)化粒子的當(dāng)前位置。G中第i個(gè)粒子的位置更新過程如式(7)所示:

XGi(t+1)=(((XGi(t)⊕w)?c1)?c2)

(7)

式中:⊕為變異操作;w為變異概率;?代表與個(gè)體最優(yōu)粒子或全局最優(yōu)粒子交叉操作;c1、c2為交叉概率;i=1,2,…,m。

XGi(t)→XGi(t+1)的實(shí)現(xiàn)分為3個(gè)步驟,即變異操作、與個(gè)體最優(yōu)粒子交叉操作、與全局最優(yōu)粒子交叉操作等步驟。變異操作的具體過程如式(8):

(8)

式中:A表示條件變異操作;t表示當(dāng)前的第t次迭代;M表示在當(dāng)前條件下變異;|w-1|代表變異條件(a=0.05);w=score(i)/favg,score(i)表示當(dāng)前結(jié)構(gòu)XGi(t)的BIC評(píng)分值,favg表示所有參與迭代粒子的平均評(píng)分值。

與個(gè)體最優(yōu)粒子交叉操作如式(9)所示:

(9)

式中:B表示與個(gè)體最優(yōu)粒子的條件交叉操作;S表示當(dāng)前條件下與全局最優(yōu)粒子交叉;c1=score(i)/fpbest表示與個(gè)體最優(yōu)粒子的交叉概率;fpbest表示個(gè)體最優(yōu)粒子的評(píng)分值。

與全局最優(yōu)粒子交叉操作如式(10)所示:

(10)

式中:XGi(t+1)表示與全局最優(yōu)粒子的條件交叉操作;S表示當(dāng)前條件下與個(gè)體最優(yōu)粒子交叉;c2=score(i)/fgbest表示與全局最優(yōu)粒子交叉概率;fgbest表示全局最優(yōu)粒子的評(píng)分值。

當(dāng)?shù)Ｗ油瓿勺儺惒僮骱?利用BIC評(píng)分判斷此結(jié)構(gòu)的優(yōu)劣,未優(yōu)化的粒子選擇副粒子增緩策略(見2.3節(jié))來增強(qiáng)優(yōu)化效果。在迭代過程中可能會(huì)出現(xiàn)環(huán)狀結(jié)構(gòu),增加去環(huán)操作(見2.4節(jié))去除環(huán)狀粒子,提高粒子的準(zhǔn)確性。

2.3 副粒子增緩策略

由于迭代后期粒子位置趨于集中化且評(píng)分值不再增加,此時(shí)整體粒子群的優(yōu)化極易陷入局部最優(yōu)。為增強(qiáng)種群多樣性,避免陷入局部最優(yōu),從而提出副粒子增緩策略。

副粒子的選擇:同第2.1節(jié)所示得到互信息矩陣XI={I(xi,xj)}n×n,并且確定閾值大小,當(dāng)I(xi,xj)值大于閾值時(shí),將XI中對應(yīng)的(xi,xj)元素坐標(biāo)i、j保留在L空數(shù)組中。由于XI是對稱矩陣,則僅保留對稱矩陣中上三角或下三角的元素對應(yīng)坐標(biāo)值。并將L排列成二維稀疏矩陣,按互信息I(xa,xb)>I(xc,xd)>…>I(xl,xo)(a,b,c,l,o∈{1,2,…,n})的順序排列,最終形成l×2維的L,l的大小等于在閾值設(shè)定下,篩選出的最大矩陣元素個(gè)數(shù)。副粒子如式(11)所示:

(11)

增緩策略:在2.2節(jié)的算法尋優(yōu)過程之后,因?yàn)樵u(píng)分值不增加而無迭代尋優(yōu)的粒子選擇在副粒子的作用下優(yōu)化,即尋得新的粒子位置,避免全部粒子向局部最優(yōu)粒子的位置移動(dòng)。未優(yōu)化的粒子的改變主要在于增加邊的操作,未優(yōu)化的粒子群為G′(G′∈G),G′={XG′1,XG′2,……,XG′n},n為未優(yōu)化粒子群個(gè)數(shù)。當(dāng)選擇副粒子中某一維的元素(a,b)時(shí),判斷XG′i中對應(yīng)位置XG′i(a,b)的元素值,若XG′i(a,b)=0時(shí),對XG′i粒子加邊操作,即XG′i(a,b)=1,否則不變。

副粒子增緩策略后的粒子通過適應(yīng)度函數(shù)值判斷粒子的優(yōu)化程度,并和原粒子群合并; 然后進(jìn)行去除環(huán)狀操作,以確保最終的網(wǎng)絡(luò)結(jié)構(gòu)無異常環(huán)狀。

2.4 去除環(huán)狀操作

在變異操作和交叉操作中可能會(huì)產(chǎn)生非法環(huán)狀結(jié)構(gòu),因此為了保證變異后的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)不含有異常的環(huán)狀結(jié)構(gòu),需要對貝葉斯網(wǎng)絡(luò)進(jìn)行修正。修正方法如下:

重復(fù)第1步至第4步的操作,直到最終并無任何環(huán)狀結(jié)構(gòu)。

2.5 BNs-HsPSO算法流程圖

BNs-HsPSO算法流程圖如圖1所示。

圖1 算法整體流程圖Fig.1 Overall algorithm flowchart

3 實(shí)驗(yàn)分析

實(shí)驗(yàn)運(yùn)行環(huán)境:Inter(R)Core(TM)i5-8250U CPU,主頻1.60 GHz,內(nèi)存4 GB,Windows10 64bit操作系統(tǒng)。在MATLAB2020a平臺(tái)中基于bnt-master工具箱進(jìn)行實(shí)驗(yàn)。為了驗(yàn)證本文算法的性能優(yōu)勢,使用常用的且具有代表性的貝葉斯網(wǎng)絡(luò)中的ASIA、CAR、CHILD、ALARM網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)對比。其中ASIA網(wǎng)絡(luò)包含8個(gè)節(jié)點(diǎn)、8條邊;CAR網(wǎng)絡(luò)包括12個(gè)節(jié)點(diǎn)、9條邊;CHILD網(wǎng)絡(luò)包括20個(gè)節(jié)點(diǎn)、25條邊;ALARM網(wǎng)絡(luò)包括37個(gè)節(jié)點(diǎn)、46條邊。在如上個(gè)網(wǎng)絡(luò)中隨機(jī)生成訓(xùn)練數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù),其中4個(gè)網(wǎng)絡(luò)分別隨機(jī)生成了1 000、2 000、3 000、5 000組數(shù)據(jù)。

3.1 參數(shù)設(shè)置

不同閾值參數(shù)的設(shè)置影響迭代的效率和準(zhǔn)確性,副粒子中閾值的設(shè)置影響評(píng)分值的大小、收斂速度和正確邊及多邊的個(gè)數(shù)。由于在ASIA、CAR網(wǎng)絡(luò)中取不同閾值時(shí)評(píng)分值及收斂速度相差不大,所以在CHILD和ALARM中做閾值對評(píng)分值及收斂速度的對比實(shí)驗(yàn)。圖2是在不同閾值下,CHILD、ALARM網(wǎng)絡(luò)所達(dá)到的最高評(píng)分值所需迭代次數(shù)。圖3是在不同閾值下,ASIA、CAR、CHILD、ALARM網(wǎng)絡(luò)與標(biāo)準(zhǔn)網(wǎng)絡(luò)相比正確邊及多邊的個(gè)數(shù)。此兩組實(shí)驗(yàn)分別是在5 000組數(shù)據(jù)且20次迭代結(jié)果所得的平均值。

圖2 不同網(wǎng)絡(luò)下的迭代過程Fig.2 Iterative processes under different networks

圖3 不同網(wǎng)絡(luò)下的邊數(shù)對比結(jié)果Fig.3 Comparison results of the number of edges under different networks

由圖2可知,當(dāng)閾值為0.08時(shí)評(píng)分值的絕對值最大,且迭代次數(shù)最小,并在之后一直維持最大評(píng)分值的絕對值。由圖3可知,在ASIA、CAR、CHILD中,當(dāng)閾值為0.08時(shí),正確邊數(shù)是最大的且多邊數(shù)是最小的。而在ALARM網(wǎng)絡(luò)中,將閾值設(shè)為0.08并無優(yōu)勢,但是結(jié)合4個(gè)網(wǎng)絡(luò)中正確邊數(shù)的數(shù)量及評(píng)分值等指標(biāo),最終副粒子增緩策略中的閾值設(shè)置為0.08。

3.2 與其他算法的對比實(shí)驗(yàn)

為了驗(yàn)證所提算法的有效性,將本文的算法與BNC-PSO[20]和PC-PSO[23]以及常用的經(jīng)典的BN結(jié)構(gòu)學(xué)習(xí)算法MMHC[26]算法和貪婪算法[27](Greedy Search, GS)進(jìn)行對比實(shí)驗(yàn)。實(shí)驗(yàn)次數(shù)為50次,并在標(biāo)準(zhǔn)網(wǎng)絡(luò)隨機(jī)生成的相同數(shù)據(jù)樣本中對比了以上算法在各網(wǎng)絡(luò)中取得的最佳BIC評(píng)分平均值如表1到表4所示。

表1 ASIA網(wǎng)絡(luò)中平均BIC評(píng)分的對比Tab.1 Comparison of average BIC scores in ASIA networks

表2 CAR網(wǎng)絡(luò)中平均BIC評(píng)分的對比Tab.2 Comparison of average BIC scores in CAR networks

表3 CHILD網(wǎng)絡(luò)中平均BIC評(píng)分的對比Tab.3 Comparison of average BIC scores in CHILD networks

表4 ALARM網(wǎng)絡(luò)中平均BIC評(píng)分的對比Tab.4 Comparison of average BIC scores in ALARM networks

BIC評(píng)分用來評(píng)價(jià)學(xué)習(xí)到的網(wǎng)絡(luò)和真實(shí)網(wǎng)絡(luò)的匹配程度。

由表1～表4數(shù)據(jù)結(jié)果可知,在1 000、2 000、3 000、5 000組數(shù)據(jù)下,平均評(píng)分值的對比結(jié)果:在ASIA網(wǎng)絡(luò)中,本文算法的評(píng)分值比MMHC算法增長5.8%,比GS算法增長6.4%,比BNC-PSO增長5.4%,比PC-PSO算法增長5.5%;在CAR網(wǎng)絡(luò)的數(shù)據(jù)結(jié)果顯示,本文算法的評(píng)分值比MMHC增長9.3%,比GS算法增長9.6%,比BNC-PSO增長3.2%,比PC-PSO算法增長1.1%;在CHILD網(wǎng)絡(luò)中,本文算法的評(píng)分值比MMHC算法增長0.4%,比GS算法增長0.3%,比BNC-PSO增長1.1%,比PC-PSO算法增長0.1%;在ALARM網(wǎng)絡(luò)中,本文算法評(píng)分值比MMHC算法增長2.2%,比GS算法增長2.5%,比BNC-PSO算法增長3.3%,比PC-PSO算法增長3.0%。

上述評(píng)分值對比結(jié)果表明,在相同數(shù)據(jù)量下,本文的算法在評(píng)分值上比其他算法均有優(yōu)勢。GS在某種意義上容易陷入局部最優(yōu)解,這是由于GS算法不考慮各種可能的情況,總是在尋找當(dāng)前狀態(tài)下最優(yōu)的解,所以本文算法評(píng)分值大于GS算法。MMHC算法在進(jìn)行評(píng)分禁忌搜索后仍有陷入局部最優(yōu)的趨勢,所以本算法比MMHC算法增長率較高。BNC-PSO算法它的初始結(jié)構(gòu)是隨機(jī)生成的,后期迭代過程可以增加部分評(píng)分值,但其評(píng)分值和本文算法評(píng)分值仍有差距。

PC-PSO算法在初始結(jié)構(gòu)構(gòu)建中使用了PC算法確定初始結(jié)構(gòu),但PC算法無法在不完整數(shù)據(jù)下找到完整數(shù)據(jù)的因果關(guān)系,即無法尋找到更多的正確邊數(shù),從而降低了一定的評(píng)分值。但從4個(gè)網(wǎng)絡(luò)的評(píng)分對比值中發(fā)現(xiàn),在CHILD網(wǎng)絡(luò)中,本文算法比其他算法的評(píng)分值增長率并不明顯,這是由于本文算法在CHILD網(wǎng)尋優(yōu)過程中會(huì)出現(xiàn)比其他網(wǎng)絡(luò)更多的多邊,這些邊是標(biāo)準(zhǔn)網(wǎng)絡(luò)中所沒有的邊,即副粒子增緩策略閾值的約束在CHILD網(wǎng)絡(luò)中略差。

為了對本文算法學(xué)習(xí)到的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)準(zhǔn)確性有更深入的檢測,本文選取了評(píng)價(jià)算法性能中常用具有代表性的指標(biāo)[28]來驗(yàn)證該算法的性能,部分指標(biāo)的物理意義如表5所示。

表5 評(píng)價(jià)算法性能指標(biāo)Tab.5 Evaluate algorithm performance indicators

其中,HD、ACC值的計(jì)算公式如式(12)和(13)所示:

HD=FP+FN

(12)

(13)

通過表5所示,本實(shí)驗(yàn)選用TP、HD、ACC指標(biāo)作為實(shí)驗(yàn)對比項(xiàng),各個(gè)算法的對比結(jié)果如圖4到圖6所示。

圖4 4個(gè)網(wǎng)絡(luò)中不同算法的TP值Fig.4 TP values for different algorithms in four networks

圖4為4個(gè)網(wǎng)絡(luò)中不同的算法TP值的對比結(jié)果。

由圖4可知,在CHILD網(wǎng)絡(luò)中,本文的BNs-HsPSO算法的TP值差于GS算法和MMHC算法,但在ASIA、CAR、ALARM網(wǎng)絡(luò)TP值具有明顯優(yōu)勢。因?yàn)楸疚腂Ns-HsPSO算法在初始結(jié)構(gòu)中使用最大支撐樹搜索策略構(gòu)建初始結(jié)構(gòu),所以在CHILD網(wǎng)絡(luò)中存在少邊情況,而副粒子增緩策略會(huì)增加部分多邊,所以在CHILD網(wǎng)絡(luò)中本文BNs-HsPSO算法與GS和MMHC算法相比略差。同時(shí),本文算法與PC-PSO算法相比的優(yōu)勢在于副粒子增緩策略的約束使得本算法的TP值比PC-PSO算法在ASIA和CAR網(wǎng)絡(luò)中更高。

圖5為4個(gè)網(wǎng)絡(luò)中不同的算法HD值的對比結(jié)果。當(dāng)HD值越小時(shí),整體算法的學(xué)習(xí)效果更好。同時(shí)在ASIA、CAR、ALARM網(wǎng)絡(luò)中,本文BNs-HsPSO算法的HD值明顯較小,而在CHILD網(wǎng)絡(luò)中,本文算法的HD值略差,這是由于本算法的閾值約束不得當(dāng)造成的多邊情況。BNs-HsPSO算法增加了初始結(jié)構(gòu)的約束及迭代過程的優(yōu)化,其搜索性能較強(qiáng),所以無論數(shù)據(jù)量的大小,其HD值均會(huì)增大。但整體來看,本文算法的HD值更低,與標(biāo)準(zhǔn)網(wǎng)絡(luò)更接近。

圖5 4個(gè)網(wǎng)絡(luò)中不同算法的HD值Fig.5 HD values for different algorithms in four network

圖6為4個(gè)網(wǎng)絡(luò)中不同的算法ACC值的對比結(jié)果。

圖6 4個(gè)網(wǎng)絡(luò)中不同算法的ACC值Fig.6 ACC values for different algorithms in four networks

由圖6可知,在ASIA網(wǎng)絡(luò)中,本文的BNs-HsPSO算法相比于其他算法有較高的ACC值,而在數(shù)據(jù)量增大時(shí),BNs-HsPSO算法的ACC值也在提高。這是由于數(shù)據(jù)量增大時(shí),所選擇的數(shù)據(jù)范圍較廣,所以得到的網(wǎng)絡(luò)結(jié)構(gòu)更趨近于正確的網(wǎng)絡(luò)結(jié)構(gòu),ACC值就有所提高。

在CHILD網(wǎng)絡(luò)中,BNs-HsPSO算法與GS、MMHC算法相比不具有優(yōu)勢。由于BNs-HsPSO算法的初始結(jié)構(gòu)中使用最大支撐樹來連接兩節(jié)點(diǎn),而最大支撐樹算法只是保留最大互信息相連的邊,此時(shí)會(huì)出現(xiàn)少邊的情況。同時(shí)在搜索過程中的副粒子增緩策略會(huì)增加邊,但由于增加了錯(cuò)誤邊時(shí)式(13)的分母變大,從而導(dǎo)致ACC值偏低。在GS算法和MMHC算法中充分搜索到了最多的正確邊數(shù),這兩個(gè)算法的ACC值在CHILD網(wǎng)絡(luò)中則較高。在ALARM網(wǎng)絡(luò)中,隨著數(shù)據(jù)量的增加,對比算法中大多數(shù)算法的正確率都會(huì)逐步提高,但在GS算法中,當(dāng)數(shù)據(jù)量增加時(shí),不可避免地陷入局部最優(yōu),會(huì)導(dǎo)致搜索過程中搜索到的錯(cuò)誤邊更多,最終ACC值反而下降了?？梢钥闯?本文BNs-HsPSO算法的ACC值最高。

綜上,結(jié)合BIC評(píng)分值和部分指標(biāo)的對比,可以明顯地看出本文BNs-HsPSO算法的學(xué)習(xí)效果優(yōu)于其他算法,這是由于在初始結(jié)構(gòu)構(gòu)建的時(shí)候增加了V-結(jié)構(gòu)和CRAE的定向策略,后期迭代過程引入自定義迭代概率和副粒子增緩策略,使得算法學(xué)習(xí)過程能搜索到更多的正確邊并能獲得更優(yōu)的評(píng)分值,減少了隨機(jī)搜索和隨機(jī)迭代概率導(dǎo)致的陷入局部最優(yōu)的可能性。

4 結(jié) 論

本文提出混合粒子群優(yōu)化貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的學(xué)習(xí)算法BNs-HsPSO,該算法首先通過互信息確定2節(jié)點(diǎn)的依賴強(qiáng)度,然后構(gòu)建非定向最大支撐樹結(jié)構(gòu),利用V-結(jié)構(gòu)、CRAE確定結(jié)構(gòu)方向,即可得到初始網(wǎng)絡(luò)結(jié)構(gòu);以此結(jié)構(gòu)為基礎(chǔ)并利用爬山算法產(chǎn)生眾多的結(jié)構(gòu)模型,在粒子群中表現(xiàn)為較優(yōu)的初代種群。交叉、變異條件概率策略的提出優(yōu)化了粒子群位置變化,同時(shí)提出的副粒子策略針對未優(yōu)化粒子進(jìn)行更新,最終搜索到最優(yōu)的網(wǎng)絡(luò)結(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明,BNs-HsPSO算法能夠?qū)W習(xí)到更好的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)模型。不同網(wǎng)絡(luò)下的學(xué)習(xí)結(jié)果表明,本文算法在評(píng)分結(jié)果和學(xué)習(xí)到的正確邊數(shù)等評(píng)價(jià)指標(biāo)中優(yōu)于其他算法,且在小型網(wǎng)絡(luò)中具有更高的準(zhǔn)確率。