一種具有結(jié)構(gòu)先驗(yàn)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法

仝兆景,李金香,喬征瑞

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

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

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

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

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

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

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

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

(1)

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

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

(2)

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

(3)

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

(4)

以某節(jié)點(diǎn)為例,通過(guò)其父節(jié)點(diǎn)信息,在BN體系中根據(jù)式(4)可知,如果某節(jié)點(diǎn)其父節(jié)點(diǎn)的狀態(tài)信息可知,那么該節(jié)點(diǎn)的條件完全獨(dú)立于由其父節(jié)點(diǎn)中給定的任何非子節(jié)點(diǎn)所組成的集合體。以節(jié)點(diǎn)的獨(dú)立性為前提,對(duì)提出的問(wèn)題進(jìn)行分析,選取特征變量后對(duì)數(shù)據(jù)進(jìn)行預(yù)處理,再進(jìn)行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í)方法一般采用條件獨(dú)立性檢驗(yàn)或互信息檢查確定變量間的相互依賴性或獨(dú)立性關(guān)系。該方法的性能主要取決于CI測(cè)試的數(shù)量和約束集的大小。由于約束集和高階CI測(cè)試數(shù)量增加,基于約束的方法精度將降低,因此本文選用CI確定變量間的依賴關(guān)系。PC算法便是利用CI測(cè)試來(lái)確定變量間依賴關(guān)系的典型算法之一,其通過(guò)檢測(cè)兩個(gè)最鄰近節(jié)點(diǎn)子集的有向分離(D-separation)來(lái)減少搜索空間與時(shí)間復(fù)雜度。本文通過(guò)PC算法選擇初始網(wǎng)絡(luò),對(duì)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行修改。

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

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

D-separation可將無(wú)向圖擴(kuò)展為DAG。節(jié)點(diǎn)集合O能D分隔節(jié)點(diǎn)i和節(jié)點(diǎn)j,當(dāng)且僅當(dāng)給定O時(shí),i與j不存在有效路徑,即i和j在O條件下獨(dú)立,記作i⊥j∣O。已知有向無(wú)環(huán)圖G以及節(jié)點(diǎn)X、Y和點(diǎn)集O,當(dāng)X和Y之間的路徑滿足以下任意一條結(jié)論時(shí),該路徑堵塞,那么X、Y關(guān)于O條件獨(dú)立:1)若節(jié)點(diǎn)Z屬于圖2的a、b、c3種情況,且Z包含在點(diǎn)集O中;2)若節(jié)點(diǎn)Z屬于圖2中的d情況,且Z不包含在點(diǎn)集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 基于分?jǐn)?shù)的結(jié)構(gòu)學(xué)習(xí)

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

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

(5)

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

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

2 麻雀搜索算法

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

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

(6)

(7)

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

(8)

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

追隨者的位置更新計(jì)算式為

(9)

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

警戒者的位置更新計(jì)算式為

(10)

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

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

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

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

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

(11)

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

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

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

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

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

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

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

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

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

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

4 標(biāo)準(zhǔn)貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)學(xué)習(xí)測(cè)試

為驗(yàn)證本文所提算法的尋優(yōu)性能,選取CANCER網(wǎng)絡(luò)(圖6)、ASIA網(wǎng)絡(luò)(圖8)和INSURANCE網(wǎng)絡(luò)(圖9)3個(gè)標(biāo)準(zhǔn)BN測(cè)試BIC評(píng)分。這3個(gè)網(wǎng)絡(luò)的節(jié)點(diǎn)和有向邊的數(shù)量遞增,復(fù)雜程度也逐漸增高,能有效測(cè)試算法在簡(jiǎn)單網(wǎng)絡(luò)和復(fù)雜網(wǎng)絡(luò)的尋優(yōu)能力。其中,CANCER網(wǎng)絡(luò)包含5個(gè)節(jié)點(diǎn)和4條有向邊,ASIA網(wǎng)絡(luò)包含8個(gè)節(jié)點(diǎn)和8條有向邊,INSURANCE包含27個(gè)節(jié)點(diǎn)和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個(gè)網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)驗(yàn)證,實(shí)驗(yàn)結(jié)果如表1所示。

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

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

(a)

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

表2 不同算法在標(biāo)準(zhǔn)貝葉斯網(wǎng)絡(luò)上的實(shí)驗(yàn)結(jié)果

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

5 結(jié)束語(yǔ)

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