基于混合簡化粒子群算法的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學習研究

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

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

1 引 言

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

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

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

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

本文提出的混合簡化粒子群算法優(yōu)化貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學習算法(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)的時間,提高了搜索效率。由于粒子群算法常用于解決連續(xù)性問題,為了更好地用于解決本文BNSL離散型問題,根據(jù)文獻[24]提出的不含速度項的簡化粒子群算法公式,然后結(jié)合GA算法的交叉和變異策略,生成了新的改進粒子群算法迭代公式,由此可實現(xiàn)BNSL的優(yōu)化。在更新過程中,本文自定義變異和交叉概率,從而避免迭代過程的冗余;增加副粒子增緩策略優(yōu)化未迭代更新的粒子進而增加種群多樣性,避免算法陷入局部最優(yōu)。因此最終搜索到含有更多正確邊的BN結(jié)構(gòu)并增強了算法的學習效率。

2 BNs-HsPSO算法研究

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

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

(1)

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

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

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

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

(2)

(3)

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

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

(4)

(5)

(6)

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

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

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

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

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

(7)

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

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

(8)

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

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

(9)

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

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

(10)

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

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

2.3 副粒子增緩策略

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

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

(11)

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

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

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

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

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

2.5 BNs-HsPSO算法流程圖

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

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

3 實驗分析

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

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

不同閾值參數(shù)的設(shè)置影響迭代的效率和準確性,副粒子中閾值的設(shè)置影響評分值的大小、收斂速度和正確邊及多邊的個數(shù)。由于在ASIA、CAR網(wǎng)絡(luò)中取不同閾值時評分值及收斂速度相差不大,所以在CHILD和ALARM中做閾值對評分值及收斂速度的對比實驗。圖2是在不同閾值下,CHILD、ALARM網(wǎng)絡(luò)所達到的最高評分值所需迭代次數(shù)。圖3是在不同閾值下,ASIA、CAR、CHILD、ALARM網(wǎng)絡(luò)與標準網(wǎng)絡(luò)相比正確邊及多邊的個數(shù)。此兩組實驗分別是在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可知,當閾值為0.08時評分值的絕對值最大,且迭代次數(shù)最小,并在之后一直維持最大評分值的絕對值。由圖3可知,在ASIA、CAR、CHILD中,當閾值為0.08時,正確邊數(shù)是最大的且多邊數(shù)是最小的。而在ALARM網(wǎng)絡(luò)中,將閾值設(shè)為0.08并無優(yōu)勢,但是結(jié)合4個網(wǎng)絡(luò)中正確邊數(shù)的數(shù)量及評分值等指標,最終副粒子增緩策略中的閾值設(shè)置為0.08。

3.2 與其他算法的對比實驗

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

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

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

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

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

BIC評分用來評價學習到的網(wǎng)絡(luò)和真實網(wǎng)絡(luò)的匹配程度。

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

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

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

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

表5 評價算法性能指標Tab.5 Evaluate algorithm performance indicators

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

HD=FP+FN

(12)

(13)

通過表5所示,本實驗選用TP、HD、ACC指標作為實驗對比項,各個算法的對比結(jié)果如圖4到圖6所示。

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

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

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

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

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

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

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

由圖6可知,在ASIA網(wǎng)絡(luò)中,本文的BNs-HsPSO算法相比于其他算法有較高的ACC值,而在數(shù)據(jù)量增大時,BNs-HsPSO算法的ACC值也在提高。這是由于數(shù)據(jù)量增大時,所選擇的數(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é)點,而最大支撐樹算法只是保留最大互信息相連的邊,此時會出現(xiàn)少邊的情況。同時在搜索過程中的副粒子增緩策略會增加邊,但由于增加了錯誤邊時式(13)的分母變大,從而導致ACC值偏低。在GS算法和MMHC算法中充分搜索到了最多的正確邊數(shù),這兩個算法的ACC值在CHILD網(wǎng)絡(luò)中則較高。在ALARM網(wǎng)絡(luò)中,隨著數(shù)據(jù)量的增加,對比算法中大多數(shù)算法的正確率都會逐步提高,但在GS算法中,當數(shù)據(jù)量增加時,不可避免地陷入局部最優(yōu),會導致搜索過程中搜索到的錯誤邊更多,最終ACC值反而下降了?？梢钥闯?本文BNs-HsPSO算法的ACC值最高。

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

4 結(jié) 論

本文提出混合粒子群優(yōu)化貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的學習算法BNs-HsPSO,該算法首先通過互信息確定2節(jié)點的依賴強度,然后構(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)化了粒子群位置變化,同時提出的副粒子策略針對未優(yōu)化粒子進行更新,最終搜索到最優(yōu)的網(wǎng)絡(luò)結(jié)構(gòu)。實驗結(jié)果表明,BNs-HsPSO算法能夠?qū)W習到更好的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)模型。不同網(wǎng)絡(luò)下的學習結(jié)果表明,本文算法在評分結(jié)果和學習到的正確邊數(shù)等評價指標中優(yōu)于其他算法,且在小型網(wǎng)絡(luò)中具有更高的準確率。