摘 要：

為解決海量數(shù)據(jù)情況下學(xué)習(xí)貝葉斯網(wǎng)絡(luò)（Bayesian network， BN）結(jié)構(gòu)的算法性能急劇降低問題，基于Spark框架設(shè)計了一種全流程并行遺傳算法用于BN結(jié)構(gòu)學(xué)習(xí)（簡稱為SparkGA-BN）。SparkGA-BN包含互信息計算并行化、遺傳算子并行化和適應(yīng)度評分并行化3個部分。互信息并行計算可以高效減少搜索空間;在演化前增加對種群信息與選擇信息的廣播來對全種群執(zhí)行選擇操作。選擇與交叉算子共用選擇信息以并行執(zhí)行，從而高效演化并減少數(shù)據(jù)落盤時間。對約束和評分兩階段產(chǎn)生的中間數(shù)據(jù)作記憶化存儲，提升數(shù)據(jù)復(fù)用率和全局執(zhí)行效率。實驗結(jié)果表明，所提算法在執(zhí)行效率和學(xué)習(xí)準(zhǔn)確率方面均優(yōu)于對比算法。

關(guān)鍵詞：

貝葉斯網(wǎng)絡(luò); 結(jié)構(gòu)學(xué)習(xí); 遺傳算法; 并行結(jié)構(gòu)學(xué)習(xí); Spark

中圖分類號：

TP 181

文獻(xiàn)標(biāo)志碼： A""" DOI：10.12305/j.issn.1001-506X.2024.05.23

Full process parallel genetic algorithm for Bayesian network structure learning

CAI Yiming， MA Li， LU Hengyang， FANG Wie*

（School of Artificial Intelligence and Computer Science， Jiangnan University， Wuxi 214122， China）

Abstract：

To solve the problem of algorithm performance degradation in Bayesian network （BN） structure learning in case of massive data， a full process parallel genetic algorithm （GA） for BN structure learning is proposed based on the Spark framework （SparkGA-BN）. SparkGA-BN includes three parts： parallel calculation of mutual information， parallelization of genetic operators， and parallelization of fitness evaluation. Parallel computation of mutual information is employed to reduce the search space. Broadcasting is used to perform selection operation on the entire population by propagating population information and selection information before evolution. Selection and crossover operators share selection information to evolve efficiently and reduce disk write time. Intermediate data generated during the constraint and scoring stages are stored in memory to improve data reuse and overall execution efficiency. Experimental results show that the proposed algorithm outperforms the comparison algorithms in terms of execution efficiency and learning accuracy.

Keywords：

Bayesian network （BN）; structure learning; genetic algorithm （GA）; parallel structure learning; Spark

0 引 言

貝葉斯網(wǎng)絡(luò)（Bayesian network， BN）［1］由有向無環(huán)圖和條件概率表組成，廣泛用于表達(dá)現(xiàn)實問題中的不確定性，其性能受到BN拓?fù)浣Y(jié)構(gòu)影響。隨著結(jié)構(gòu)變量的增多，其搜索空間呈指數(shù)級增長，搜索最優(yōu)BN結(jié)構(gòu)成為非確定性多項式（non-deterministic polynomially， NP）難問題［2］。為解決此問題，可以通過減少搜索空間和加快搜索效率來開展研究。搜索空間的減少，往往采用約束的方法［3］，即分析變量之間的依賴程度，將條件獨立的特定結(jié)構(gòu)在搜索空間中篩除，實現(xiàn)更快的結(jié)構(gòu)學(xué)習(xí)。然而，約束方法依賴于指數(shù)級的高階條件獨立性測試計算復(fù)雜度增加且不可靠。另一種方法是采用評分搜索的方式加快搜索效率，在搜索過程中確定一個評分函數(shù)對候選的網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行評分，于是將結(jié)構(gòu)學(xué)習(xí)問題轉(zhuǎn)化為組合優(yōu)化問題，再通過貪心算法或元啟發(fā)式算法進(jìn)行搜索，例如模擬退火（simulated annealing， SA）算法［4］、蟻群優(yōu)化（ant colony optimization， ACO）算法［5］、遺傳算法（genetic algorithm， GA）［6］、粒子群優(yōu)化（particle swarm optimization， PSO）算法［7］等。然而，當(dāng)搜索空間過大時，這類方法難以在較短的時間內(nèi)得出滿意的結(jié)果。

為了同時優(yōu)化搜索空間和計算效率，研究者們提出了將基于約束和評分搜索的兩種方法進(jìn)行結(jié)合的混合方法。通過約束的方法構(gòu)建網(wǎng)絡(luò)結(jié)構(gòu)的骨架，再通過評分搜索的方式得到高評分的BN結(jié)構(gòu)，這已成為當(dāng)前BN結(jié)構(gòu)學(xué)習(xí)（BN structure learning， BNSL）的主流方法［8］。然而，在海量數(shù)據(jù)情況下，串行的混合搜索算法難以在有限時間內(nèi)得到搜索結(jié)果，需要采用并行的方法加速搜索效率，如采用MapReduce［9］、Spark［10］等技術(shù)對原搜索算法進(jìn)行并行化設(shè)計以提高計算效率。Spark是一種快速且通用的分布式內(nèi)存計算方法，而GA是一種CPU密集型的算法且天然適合并行。為此，本文提出了一種基于Spark的GA算法來優(yōu)化求解BNSL問題（簡稱為SparkGA-BN）。首先，為了減少搜索空間，使用互信息（mutual information， MI）對搜索空間進(jìn)行約束并構(gòu)建超結(jié)構(gòu)（super structure， SS）。然后，采用GA在搜索空間中進(jìn)行搜索。本文基于Spark實現(xiàn)了全流程的并行化設(shè)計，包括并行計算MI、并行適應(yīng)度評估和遺傳操作并行化。此外，為了對數(shù)據(jù)實現(xiàn)充分的利用，將約束和評分流程中產(chǎn)生的中間數(shù)據(jù)存儲在內(nèi)存中，在采用貝葉斯信息準(zhǔn)則（Bayesian information criterion， BIC）評分計算時加以復(fù)用數(shù)據(jù)，以避免并行搜索中不必要的重復(fù)計算。其次，合并選擇和交叉算子，共享選擇信息和種群信息，以減少數(shù)據(jù)落盤時間。

本文首先介紹了相關(guān)工作與預(yù)備知識，然后描述了所提出的SparkGA-BN算法，最后介紹實驗結(jié)果，測試算法的并行性能和有效性。

1 相關(guān)工作與預(yù)備知識

1.1 基于演化算法的BNSL

為了解決大規(guī)模數(shù)據(jù)下BN結(jié)構(gòu)搜索空間龐大的問題，研究者們采用了GA、ACO、SA、PSO等演化算法開展研究。Adabor等人［4］提出了結(jié)合SA和貪心算法的混合算法，通過兩階段搜索來廣泛探索搜索空間。Khanteymoori等人［11］提出將GA和PSO結(jié)合，性能有了較好的提升。Wang等人［12］設(shè)計突變和鄰居搜索算子提高PSO的搜索能力。Lee等人［13］提出了一種針對矩陣數(shù)據(jù)的GA來學(xué)習(xí)BN結(jié)構(gòu)，每個BN個體都被映射為一個矩陣染色體。Vafaee等人［14］提出一種基于GA的BN結(jié)構(gòu)混合算法，采用MI約束搜索空間和GA在搜索空間中進(jìn)行搜索。Liu等人［15］提出約束階段引入局部信息以提高前期網(wǎng)絡(luò)的精度，采用離散二進(jìn)制PSO來搜索網(wǎng)絡(luò)結(jié)構(gòu)，降低算法復(fù)雜度。Sun等人［16］提出一種將PC（Peter-Clark）算法、GA和PSO相結(jié)合的混合算法。文獻(xiàn)［17］中又引入了一種有偏見的隨機(jī)密鑰GA來解決BNSL問題，通過跡指數(shù)和結(jié)構(gòu)學(xué)習(xí)的增廣拉格朗日進(jìn)行非組合優(yōu)化（non-combinatorial optimization via trace exponential and augmented Lagrangian for structure learning， NOTEARS）算法對解碼器和局部進(jìn)行了優(yōu)化。

1.2 并行BNSL算法

為了解決BNSL算法執(zhí)行效率低下的問題，研究者們在BNSL領(lǐng)域提出了許多并行的解決方案。Madsen等人［18］提出了經(jīng)典約束算法PC的并行化版本，通過控制線程在共享內(nèi)存的大型數(shù)據(jù)集上并行計算以學(xué)習(xí)BN結(jié)構(gòu)，但在高維數(shù)據(jù)集中約束算法需要大量的條件獨立性（conditional independence， CI）測試且精度不高。Lee等人［19］提出了結(jié)合貪心和SA的并行算法（parallel SA with a greedy algorithm， PSAGA），采用多線程的方法，每一個線程獨立執(zhí)行一個SA-GA實例，并通過記憶化存儲和復(fù)用不同線程得到的解以加速搜索過程，然而采用多線程技術(shù)需要考慮線程間的負(fù)載均衡和大量原子操作的開銷。Li等人［20］將BNSL混合算法遷移到Mapreduce平臺實現(xiàn)并行計算，約束階段采用三階段依賴性分析（three-phase dependency analysis， TPDA）算法，在評分搜索階段采用爬山算法并復(fù)用約束階段的數(shù)據(jù)，然而僅是對MI和評分函數(shù)的并行化，沒有實現(xiàn)對全流程的并行。由以上文獻(xiàn)可以看出，BNSL的并行算法主要通過多線程或Mapreduce的方法實現(xiàn)。至今為止很少有文獻(xiàn)通過Spark來實現(xiàn)并行BNSL，由于Spark基于內(nèi)存計算相比于傳統(tǒng)的Mapreduce計算將大幅提高計算效率，并且設(shè)計全流程的并行方案可以提高搜索效率，因此本文研究了基于Spark平臺設(shè)計一種全流程的并行方案來提高BN結(jié)構(gòu)搜索的效率。

1.3 MI

MI是度量兩個隨機(jī)變量之間相互依賴關(guān)系的一種方法，計算方法如下：

I（X;Y）=∑y∈Y∑x∈Xp（x，y）lnp（x，y）p（x）p（y）（1）

式中：p（x）和p（y）分別表示變量X和Y的邊際概率密度函數(shù);p（x，y）表示X和Y的聯(lián)合概率密度函數(shù)。當(dāng)I（X;Y）=0時，表示X和Y完全條件獨立。相反，越高的MI表示兩個變量的依賴程度越高。

為在BNSL問題上使用MI以約束搜索空間，Chen等人［21］提出一種判斷兩個變量間相互獨立的方法，給定一個介于0到1的閾值α，當(dāng)滿足：

I（X;Y）≥min（MMI（X），MMI（Y））·α（2）

可以認(rèn)為兩個變量間有較高的相關(guān)性，即兩個節(jié)點間應(yīng)當(dāng)存在一條相連接的邊。其中，MMI（X）表示了變量X和其余所有變量的MI最大值，MMI（Y）同理。

1.4 BIC

在BNSL的評分搜索階段，需要一個評分函數(shù)來判斷得到的網(wǎng)絡(luò)與樣本數(shù)據(jù)的匹配程度。常用的評分函數(shù)有：K2［22］、BDeu［23］、MDL［24］、BIC［25］等。其中，K2和BDeu函數(shù)均需要結(jié)構(gòu)先驗信息，而本文旨在無先驗知識情況下學(xué)習(xí)BN結(jié)構(gòu)。MDL函數(shù)在樣本量較大時，結(jié)構(gòu)精度不高。BIC函數(shù)采用對數(shù)似然度來度量結(jié)構(gòu)與樣本數(shù)據(jù)的擬合程度，不需要結(jié)構(gòu)的先驗知識且適用于海量數(shù)據(jù)，因此采用BIC作為本文算法的評分函數(shù)，對于樣本量為m且節(jié)點數(shù)為n的數(shù)據(jù)集，BIC的計算方法如下：

BICscore=∑ni=1∑qij=1∑rik=1mijklnmijkmij－∑ni=1qi（ri－1）2ln m（3）

從式（3）中可以看出，BIC由兩部分組成，前者為結(jié)構(gòu)的對數(shù)似然函數(shù)，后者是對結(jié)構(gòu)復(fù)雜度的懲罰項。其中，對于每一個節(jié)點i有ri種不同的取值狀態(tài)，其父節(jié)點有qi種可能的取值。mij表示節(jié)點i的父節(jié)點取值狀態(tài)為j的樣本數(shù)量，mijk表示節(jié)點i取值狀態(tài)為k的同時父節(jié)點取值狀態(tài)為j時的樣本數(shù)量。

2 基于Spark全流程并行GA的混合BNSL算法

本文的研究目的在于提供一種并行BNSL混合算法，將充分的數(shù)據(jù)復(fù)用和全流程的并行搜索相結(jié)合，以提高BNSL算法的求解性能。所提算法由3個主要階段組成，分別為并行計算MI、并行計算BIC評分和并行執(zhí)行演化算子。

GA并行化難點在于選擇和交叉操作的并行化，由于均需要其他的個體信息，并行設(shè)計較為困難。最直接的并行方案是將種群分成多個子種群，每個子種群進(jìn)行獨立演化，但這樣的選擇操作并不是對整體種群進(jìn)行選擇，實際的選擇概率將發(fā)生變化，造成選擇語義的錯誤。另外由于Spark本身的特性，不同的并行節(jié)點之間是封裝的，無法實現(xiàn)節(jié)點間的信息通信和信息共享，因此無法在局部演化的過程中獲取其余的個體信息，如果不重新設(shè)計其并行流程就很難在并行化的同時保證正確的演化語義。

SparkGA-BN算法的偽代碼如算法1所示，描述了整個約束和搜索過程，包括MI計算、BIC評分和演化算子的并行化設(shè)計及實現(xiàn)。算法首先讀取樣本數(shù)據(jù)集并初始化全局變量（第1行）。然后通過并行計算MI的方式對搜索空間進(jìn)行約束，并以此初始化分布式種群（第2～4行）。為了避免數(shù)據(jù)的冗余計算而導(dǎo)致效率低下，使用管道復(fù)用技術(shù)計算評分，同時存儲局部計算產(chǎn)生的中間數(shù)據(jù)以在后續(xù)迭代中復(fù)用（第5行）。在執(zhí)行混合算法的搜索階段，將局部搜索需要的信息廣播。為了提高演化效率，將選擇和交叉算子進(jìn)行合并以同時執(zhí)行，減少Shuffle時間（第6～14行）。最后，在種群中選擇BIC評分最高的個體進(jìn)行輸出，作為搜索到的最優(yōu)BN結(jié)構(gòu)。

2.1 MI與BIC評分的并行設(shè)計

為了解決在海量數(shù)據(jù)情況下搜索空間過大的問題，本文在約束階段采用MI構(gòu)造SS以減少搜索空間。由于計算MI和BIC評分需要很高的計算代價，所以本文基于Spark對其流程進(jìn)行并行化設(shè)計。現(xiàn)有并行方式在局部搜索過程中往往是對所有數(shù)據(jù)進(jìn)行遍歷，對于計算產(chǎn)生的中間數(shù)據(jù)應(yīng)用不充分，因此本文將中間數(shù)據(jù)存儲于內(nèi)存中以盡可能的實現(xiàn)復(fù)用。

MI是由一系列變量的邊際概率和聯(lián)合概率組成，為了在不同節(jié)點之間同時計算MI，算法首先需要構(gòu)造一個用于計算概率的變量集合Smi并將其廣播，以在不同節(jié)點間同時計算。假設(shè)對一個有3個節(jié)點A、B、C的樣本數(shù)據(jù)集構(gòu)造Smi，其集合為Smi={A，B，C，lt;A，Bgt;，lt;A，Cgt;，lt;B，Cgt;}，包括了節(jié)點及其組合，這是計算MI必需的信息。接下來，算法將在分布式數(shù)據(jù)集的所有分區(qū)上搜索Smi集合，將搜索到的任何變量或變量組的取值情況及其在樣本中的出現(xiàn)次數(shù)以鍵值對的方式存儲在內(nèi)存中，以備后續(xù)復(fù)用。在并行搜索完成后，計算每對變量的MI值。最后，返回MI矩陣用于后續(xù)步驟對搜索空間進(jìn)行約束。

BIC評分函數(shù)由一系列變量或變量對的取值條件在樣本中出現(xiàn)的次數(shù)和一些全局變量組成。為了實現(xiàn)對BIC評分函數(shù)的并行計算，即并行地統(tǒng)計每種取值條件在樣本中出現(xiàn)的次數(shù)，需提前將待計算的條件進(jìn)行構(gòu)造。假設(shè)某個BN個體包含兩個節(jié)點A和B，每個節(jié)點分別有兩種取值條件，即a1、a2、b1、b2，且節(jié)點B為節(jié)點A的父節(jié)點，則可以構(gòu)建一個條件集合Sbic，其中包含了需要計算的條件，如下所示：Sbic={B=b1，B=b2，lt;A=a1，B=b1gt;，lt;A=a1，B=b2gt;，lt;A=a2，B=b1gt;，lt;A=a2，B=b2gt;}。

在對整個樣本進(jìn)行搜索之前，首先對內(nèi)存中的數(shù)據(jù)進(jìn)行搜索，以復(fù)用計算MI或以往迭代中存儲的數(shù)據(jù)，提高數(shù)據(jù)復(fù)用率。然后，篩選出仍然需要搜索的條件集合并對其廣播，以便所有節(jié)點在并行搜索的過程中可快速匹配條件。并行搜索的方法與搜索MI相同，對分布式樣本數(shù)據(jù)集的每個分區(qū)并行搜索Sbic集合，將搜索到的條件記錄并對相同的條件進(jìn)行聚合，以獲取條件出現(xiàn)的次數(shù)。然后，將聚合后的數(shù)據(jù)通過管道存儲在內(nèi)存中，以在后續(xù)迭代中復(fù)用。為了對整個種群中所有的個體并行地計算BIC，將種群分布在不同節(jié)點上以提供并行性，然后對種群中的所有個體同時計算BIC評分。

2.2 遺傳算子的并行化

為了解決Spark平臺上針對GA的選擇和交叉算子的并行設(shè)計存在的問題，本文提出了一種并行演化流程，以提高算法執(zhí)行效率。

圖1給出了SparkGA-BN的并行演化流程。首先通過廣播方式將整個種群的信息傳遞到每個節(jié)點，這確保了每個節(jié)點能夠獨立地快速訪問整個種群中的個體信息。每個節(jié)點都具備并行處理的能力，并有效地防止前文提到的子種群演化中可能出現(xiàn)的選擇概率變化問題。由于錦標(biāo)賽選擇需要每次從整個種群中隨機(jī)選擇兩個個體，為了實現(xiàn)并行，首先構(gòu)造一個錦標(biāo)賽選擇信息列表（list of tournament selection information， LSI）。若種群規(guī)模為Np，列表包含Np組錦標(biāo)賽選擇信息（tournament selection information， SI），每個SI為兩個范圍在［0，2Np）的隨機(jī)數(shù)組成的數(shù)組。接著將選擇信息數(shù)組廣播（broadcast selection information， BSI）并構(gòu)造分布式選擇信息（distributed selection information， DSI），使得每個分區(qū)上均有一條SI。在每個分區(qū)節(jié)點并行執(zhí)行錦標(biāo)賽選擇算法，即對于每一條SI通過廣播的種群數(shù)組查詢到對應(yīng)的兩個個體，進(jìn)行評分比較，將評分最高的個體輸出。因此，整個并行錦標(biāo)賽選擇算法結(jié)束后，將會得到Np個下一代個體。

對于交叉操作也進(jìn)行了并行化設(shè)計。為了進(jìn)一步提高效率，本文設(shè)計了一種并行執(zhí)行選擇與交叉算子的計算流程。由于交叉操作需要在種群中隨機(jī)選擇兩個個體作為父代個體，可以復(fù)用DSI以減少冗余的構(gòu)造開銷并提高效率。在每一個演化分區(qū)中提前收集選擇與交叉算子需要的SI以便后續(xù)并行執(zhí)行選擇與交叉算子。在DSI的每個分區(qū)中，額外從BSI中選擇兩條SI加入，即每個分區(qū)均包含3條SI（s0，s1，s2）。隨后所有分區(qū)的3條SI通過廣播的種群數(shù)組查詢到對應(yīng)的兩個個體，進(jìn)行評分比較，將評分較高的個體輸出。其中，s0輸出的個體G0直接作為下一代個體輸出，s1和s2輸出的個體進(jìn)行均勻交叉操作。由于查詢個體、評分比較、交叉需要的信息以通過廣播快速獲取且可獨立執(zhí)行，因此均為并行執(zhí)行。最后，將演化得到的種群作為下一代種群輸出。

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

本文使用4個不同的基準(zhǔn)數(shù)據(jù)集（Asia、Cancer、Earthquake和Survey）來評估所提算法的性能，表1列出了數(shù)據(jù)集的具體信息。

實驗平臺為一臺裝有Centos7.6系統(tǒng)、兩顆10核（2.40 GHz）處理器和32 GB RAM內(nèi)存的服務(wù)器，部署了基于Spark的分布式集群。使用Scala2.11實現(xiàn)基于Spark的算法。此外，本文通過高性能存儲系統(tǒng)Redis來存儲產(chǎn)生的中間數(shù)據(jù)并實現(xiàn)數(shù)據(jù)復(fù)用。

3.1 并行評分計算的有效性

為了評估提出的并行評分計算的執(zhí)行效率，本文以串行GA作為基準(zhǔn)，將串行評分計算方法替換為基于Spark的并行評分計算方法進(jìn)行實驗測試。與串行GA保持一致，本文將并行評分算法僅運行在一個節(jié)點上，該節(jié)點擁有4個虛擬CPU核。對于每個數(shù)據(jù)集，隨機(jī)生成100 000、300 000和500 000個樣本。

本文在每個數(shù)據(jù)集上獨立進(jìn)行10次實驗以計算平均評分時間，該評分時間包括計算BIC評分時間、存儲和復(fù)用中間數(shù)據(jù)的時間以及節(jié)點間通信的時間。實驗在單一服務(wù)器上進(jìn)行，因此不涉及網(wǎng)絡(luò)通信時間。對比實驗設(shè)置相同的BIC評價次數(shù)和種群數(shù)量，串行和并行評分得到的BIC結(jié)果相同。圖2分別給出了在4種數(shù)據(jù)集上不同數(shù)據(jù)量情況下的平均評分時間，可以看出在4個數(shù)據(jù)集上通過Spark并行加速均有顯著提升。其中，在Asia數(shù)據(jù)集上樣本規(guī)模在50×104時串行評分的時間達(dá)到了接近600 s，而經(jīng)過并行加速后評分時間僅需要不到150 s，獲得了77%左右的加速效果。在10×104規(guī)模時并行加速效果為68%，在30×104時為71%。隨著數(shù)據(jù)規(guī)模的增加，加速效果也相應(yīng)增加，這是由于在分布式計算過程中會產(chǎn)生大量的通信開銷，因此在小數(shù)據(jù)量時提升效果不夠明顯，而隨著規(guī)模的增加，通信開銷占總耗時的比例下降，加速效果變得明顯。

3.2 并行MI計算的有效性

為了評估提出的MI并行計算的有效性，本文將串行的MI計算方法作為基準(zhǔn)，以基于Spark的并行MI計算方法作為對比進(jìn)行實驗。為了與串行MI計算算法保持一致，將并行MI計算算法僅運行在一個節(jié)點上。

在每個數(shù)據(jù)集上獨立進(jìn)行10次實驗以統(tǒng)計MI計算平均時間，該時間包含了MI計算時間、存儲中間數(shù)據(jù)以及節(jié)點間通信的時間。圖3顯示了在4種數(shù)據(jù)集上不同數(shù)據(jù)量情況下的MI計算平均時間，可以看出提出的并行MI計算方法相比于串行方法在4個數(shù)據(jù)集上計算效率均獲得了85%左右的加速效果。以Asia數(shù)據(jù)集為例，采樣規(guī)模在10×104時，串行計算的時間在10.5 s左右，而并行加速后僅需1.5 s左右，加速效果為85%。隨著數(shù)據(jù)量的增大，提升幅度也隨之增加。采樣規(guī)模在50×104時，加速效果達(dá)到了93.3%。

3.3 并行GA的有效性

為了評估GA并行化的效果，本文將基于Spark的并行GA與串行GA進(jìn)行對比。BIC評價次數(shù)設(shè)置為250次，數(shù)據(jù)集規(guī)模從10×104增加到100×104以對比串并行的演化時間。為公平比較，串行GA和并行GA的適應(yīng)度評價算子均執(zhí)行本文提出的基于Spark的并行BIC評分算法，算法均運行在4個節(jié)點上。

在每個數(shù)據(jù)集上獨立進(jìn)行10次實驗以統(tǒng)計平均演化時間，由于GA算子的執(zhí)行時間較短，為了對比結(jié)果更加明顯，將 GA的選擇、交叉、變異算子以及BIC評分時間作為總演化時間進(jìn)行統(tǒng)計并比較。圖4顯示了在4種數(shù)據(jù)集上不同數(shù)據(jù)量情況下的平均演化時間，可以看出隨著數(shù)據(jù)量的增加，串行GA的平均演化時間呈增長趨勢，而并行GA的平均執(zhí)行時間較穩(wěn)定。從加速效果來看，隨著采樣規(guī)模和模型規(guī)模增大，并行加速效果越好。在Asia數(shù)據(jù)集上效果最為明顯，采樣規(guī)模在100×104時并行GA相比串行可帶來40%的加速效果。由于演化時集群節(jié)點間的數(shù)據(jù)通信會產(chǎn)生時間開銷，當(dāng)樣本規(guī)模較小時并行帶來的效果占總時間的比重較小，因此在Earthquake數(shù)據(jù)集上加速效果不夠明顯?？傮w來看，本文提出的GA并行化有效提高了計算性能。

3.4 存儲和復(fù)用中間數(shù)據(jù)的有效性

為了驗證采用記憶化存儲技術(shù)的有效性，本文設(shè)置了兩個實驗，第1個實驗是在流程中不采用記憶化技術(shù)，第2個實驗是在計算MI時存儲產(chǎn)生的中間數(shù)據(jù)，演化搜索階段在每一輪中存儲和復(fù)用中間數(shù)據(jù)。另外，兩個實驗用的MI計算方法和演化搜索方法均為本文提出的并行方法，在7個節(jié)點上并行執(zhí)行。本文選取Asia和Cancer數(shù)據(jù)集，隨機(jī)生成100 000、500 000和1 000 000個樣本，種群數(shù)量設(shè)置為100，在每個數(shù)據(jù)集獨立進(jìn)行10次實驗并統(tǒng)計平均的總評分時間，圖5展示了實驗結(jié)果。

由圖5可以看出，如果不采用記憶化技術(shù)，隨著數(shù)據(jù)量的增加，總評分時間將大幅提升。例如Asia數(shù)據(jù)集中，3種數(shù)據(jù)規(guī)模的耗時分別為100 s、500 s、900 s左右，接近于數(shù)據(jù)規(guī)模增長的幅度。而存儲和復(fù)用中間數(shù)據(jù)后，此階段的耗時將大量減少。在規(guī)模為100×104時僅需要35 s左右的時間，帶來了96%的加速效果。另外，經(jīng)過計算，樣本規(guī)模每增加10×104，不采用記憶化技術(shù)的耗時將增加一倍左右，而記憶化技術(shù)后耗時僅增加15%左右，體現(xiàn)出較好的擴(kuò)展性。因此，記憶化技術(shù)為評分階段帶來了明顯的性能提升。

3.5 SparkGA-BN的并行性能分析

為了評估所提出的并行框架的性能，本文在不同并行規(guī)模下對所提出的SparkGA-BN的執(zhí)行效率進(jìn)行分析。圖6展示了在100×104樣本規(guī)模下的Asia數(shù)據(jù)集上的算法總體執(zhí)行時間，包括MI計算、BIC評分計算和GA進(jìn)化算子的時間。所選取的并行規(guī)模分別為1、4、8、12、16，其中規(guī)模為1表示串行情況，16為啟動4個虛擬節(jié)點，每個節(jié)點分配到4個CPU核。從圖6可以看出，隨著線程數(shù)量的增加，平均運行時間減少。其中，串行耗時約300 s，并行數(shù)為16時可提速到40 s左右，因此所提出的并行搜索通過使用足夠多的線程最高可以實現(xiàn)將近八倍的處理速度。值得注意的是，當(dāng)使用的線程數(shù)超過 12 時，性能并沒有顯著提高。結(jié)果表明，所提出的并行方法比串行方法顯著提高了計算時間性能。

3.6 不同結(jié)構(gòu)學(xué)習(xí)算法的性能比較

為了比較提出的SparkGA-BN算法與其他算法在結(jié)構(gòu)學(xué)習(xí)上的性能，本文將SparkGA-BN算法與5種結(jié)構(gòu)學(xué)習(xí)算法進(jìn)行比較，包括有效的知識驅(qū)動GA（effective know-ledge-driven GA for BNSL，EKGA-BN）［26］、基于GA的自適應(yīng)精英結(jié)構(gòu)學(xué)習(xí)（adaptive elite-based structure learner using GA，AESL-GA）算法［27］、父集交叉（parent set crossover，PSX）算法［28］、Hybrid-SLA［29］和使用本文并行方法實現(xiàn)的SMIGA［30］（Spark MI-GA）。本文使用了3種不同的樣本量（100 000、300 000和500 000）進(jìn)行訓(xùn)練，對每一種樣本量均獨立進(jìn)行10次實驗并統(tǒng)計平均結(jié)果。

在參數(shù)設(shè)置方面，種群大小為Np=100，CI測試的閾值為tol=0.01，最大父節(jié)點數(shù)量為Mp=4。與文獻(xiàn)中參數(shù)一致，EKGA-BN的精英資格閾值為0.5以及AESL-GA的為0.9。SparkGA-BN和SMIGA的錦標(biāo)賽選擇規(guī)模tour=2，EKGA-BN的tour=4。最大BIC評價次數(shù)設(shè)置為Mg=45以保證公平性。對于并行參數(shù)，啟動了4個虛擬節(jié)點，每個節(jié)點分配4個CPU核心。另外為了防止算法執(zhí)行時間過長，本文對算法的總體執(zhí)行時間進(jìn)行了限制，當(dāng)超過600 s時算法將會被強(qiáng)制終止。

本文將學(xué)習(xí)到的網(wǎng)絡(luò)結(jié)構(gòu)與真實網(wǎng)絡(luò)在5個評價指標(biāo)上進(jìn)行對比，分別為F1評分、精度precision、召回率recall、結(jié)構(gòu)漢明距離（structural Hamming distance， SHD）、執(zhí)行時間。其中，F(xiàn)1評分為精度和召回率的調(diào)和平均值，計算方法如下所示：

F1=2precision·recallprecision+recall（4）

該值介于0到1之間，越高的F1意味著該網(wǎng)絡(luò)結(jié)構(gòu)的準(zhǔn)確率越高。結(jié)構(gòu)漢明距離為結(jié)構(gòu)中增加邊、缺少邊和錯誤邊的總和，其中錯誤邊為方向相反的邊，對其設(shè)置懲罰值為0.5，其他增加或缺少的邊設(shè)置懲罰值為1。

表2給出了不同算法的總體執(zhí)行時間對比結(jié)果。圖7～圖10展示了算法得到的最優(yōu)結(jié)構(gòu)在準(zhǔn)確率方面的結(jié)果。

從表2可以看出，與其他算法相比，本文所提并行方法在執(zhí)行時間上具有明顯的優(yōu)勢。以樣本量50×104為例，非并行方法需要超過350 s的執(zhí)行時間，而并行方法只需20 s，獲得了超過94%的加速效果。對于兩個基于并行方法的算法，當(dāng)樣本規(guī)模較小時，由于SMIGA具有較強(qiáng)的MI指導(dǎo)，因此更快地收斂。然而，隨著樣本規(guī)模的增加，這種優(yōu)勢逐漸減小，在50×104規(guī)模時，SparkGA-BN表現(xiàn)更出色。這是因為均勻交叉帶來了更高的種群多樣性，使得最優(yōu)BN更早得到。

從圖7～圖9可以看出，SparkGA-BN算法搜索得到的最優(yōu)結(jié)構(gòu)在F1評分、精度、召回率上均明顯優(yōu)于其他5種算法，說明本文所提算法在相同迭代次數(shù)內(nèi)學(xué)習(xí)得到的最優(yōu)網(wǎng)絡(luò)結(jié)構(gòu)相較于對比算法可以獲得最高的準(zhǔn)確率。隨著樣本量的增加，SparkGA-BN算法的求解準(zhǔn)確率表現(xiàn)出線性上升的趨勢，而對比算法并未表現(xiàn)出這一特點，說明所提出算法更適用于處理大規(guī)模數(shù)據(jù)。此外，從圖10可見，通過SparkGA-BN算法得到的SHD值低于0.5，在所有算法中最低，表明SparkGA-BN算法搜索的BN結(jié)構(gòu)幾乎不包含增加或缺少的邊，主要是方向相反的邊。值得注意的是，BIC分?jǐn)?shù)通常不會受到單個邊的方向變化的影響，因此基于BIC評分的啟發(fā)式算法得到SHD值低于0.5可以被視為最佳結(jié)果，這進(jìn)一步驗證了所提算法的優(yōu)勢。

4 結(jié) 論

本文基于Spark框架提出了SparkGA-BN，實現(xiàn)了充分的數(shù)據(jù)復(fù)用和全流程的并行搜索，保證結(jié)構(gòu)學(xué)習(xí)準(zhǔn)確率的同時大幅提高結(jié)構(gòu)學(xué)習(xí)的效率。算法在約束階段，通過并行計算MI以高效限制搜索空間，并采用記憶化存儲產(chǎn)生的中間數(shù)據(jù)以復(fù)用。在評分搜索階段，算法設(shè)計了一種新的并行演化流程，保證選擇算子能夠在全種群中進(jìn)行選擇的同時并行執(zhí)行選擇算子。選擇算子和交叉算子的合并實現(xiàn)了兩算子的并行執(zhí)行以實現(xiàn)高效演化。通過盡可能復(fù)用存儲的中間數(shù)據(jù)并對當(dāng)前產(chǎn)生的數(shù)據(jù)進(jìn)行存儲，提高了數(shù)據(jù)復(fù)用率和全局執(zhí)行效率，實現(xiàn)了BIC評分流程的并行化。在4個基準(zhǔn)數(shù)據(jù)集上采用不同規(guī)模樣本的實驗結(jié)果表明，所提算法在計算效率和學(xué)習(xí)準(zhǔn)確率上均表現(xiàn)出優(yōu)越的性能。

參考文獻(xiàn)

［1］ 茹鑫鑫， 高曉光， 王陽陽. 基于模糊約束的貝葉斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí)［J］. 系統(tǒng)工程與電子技術(shù)， 2023， 45（2）： 444-452.

RU X X， GAO S G， WANG Y Y. Bayesian network parameter learning based on fuzzy constraints［J］. Systems Engineering and Electronics， 2023， 45（2）： 444-452.

［2］ SOLOVIEV V P， BIELZA C， LARRANAGA P. Quantum approximate optimization algorithm for Bayesian network structure learning［J］. Quantum Information Processing， 2022， 22（1）： 19-47.

［3］ MARELLA D， VICARD P. Bayesian network structural learning from complex survey data： a resampling based approach［J］. Statistical Methods amp; Applications， 2022， 31（4）： 981-1013.

［4］ ADABOR E S， ACQUAAH-MENSAH G K， ODURO F T. SAGA： a hybrid search algorithm for Bayesian Network structure learning of transcriptional regulatory networks［J］. Journal of Biomedical Informatics， 2015， 54（1）： 27-35.

［5］ ZHANG X Y， XUE Y Y， LU X Y， et al.Differential-evolution-based coevolution ant colony optimization algorithm for Bayesian network structure learning［J］. Algorithms， 2018， 11（11）： 188-204.

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

WANG C F， ZHANG Y H. Bayesian network structure learning based on unconstrained optimization and genetic algorithm［J］. Control and Decisioin， 2013， 28（4）： 618-622.

［7］ 邸若海， 高曉光. 基于限制型粒子群優(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.

［8］ 李明， 張韌， 洪梅， 等. 基于信息流改進(jìn)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法［J］. 系統(tǒng)工程與電子技術(shù)， 2018， 40（6）： 1385-1390.

LI M， ZHANG R， HONG M， et al. Improved structure learning algorithm of Bayesian network based on information flow［J］. Systems Engineering and Electronics， 2018， 40（6）： 1385-1390.

［9］ HU L， YANG S C， LUO X， et al. A distributed framework for large-scale protein-protein interaction data analysis and prediction using mapreduce［J］. IEEE/CAA Journal of Automatica Sinica， 2021， 9（1）： 160-172.

［10］ CHAUDHURY M， KARAMI A， GHAZANFAR M A. Large-scale music genre analysis and classification using machine learning with apache spark［J］. Electronics， 2022， 11（16）： 2567-2598.

［11］ KHANTEYMOORI A R， OLYAEE M H， ABBASZ-ADEH O， et al. A novel method for Bayesian networks structure learning based on breeding swarm algorithm［J］. Soft Computing， 2018， 22（9）： 3049-3060.

［12］ WANG J Y， LIU S Y. A novel discrete particle swarm optimization algorithm for solving Bayesian network structures learning problem［J］. International Journal of Computer Mathematics， 2019， 96（12）： 2423-2440.

［13］ LEE J H， CHUNG W Y， KIM E T， et al. A new genetic approach for structure learning of Bayesian networks： matrix genetic algorithm［J］. International Journal of Control， Automation and Systems， 2010， 8（2）： 398-407.

［14］ VAFAEE F. Learning the structure of large-scale Bayesian networks using genetic algorithm［C］∥Proc.of the Annual Conference on Genetic and Evolutionary Computation， 2014： 855-862.

［15］ LIU K， CUI Y， REN J， et al. An improved particle swarm optimization algorithm for Bayesian network structure learning via local information constraint［J］. IEEE Access， 2021， 9： 40963-40971.

［16］ SUN B， ZHOU Y， WANG J J， et al. A new PC-PSO algorithm for Bayesian network structure learning with structure priors［J］. Expert Systems with Applications， 2021， 184： 115237.

［17］ SUN B D， ZHOU Y. Bayesian network structure learning with improved genetic algorithm［J］. International Journal of Intelligent Systems， 2022， 37（9）： 6023-6047.

［18］ MADSEN A L， JENSEN F， SALMERON A， et al. A parallel algorithm for Bayesian network structure learning from large data sets［J］. Knowledge-Based Systems， 2017， 117： 46-55.

［19］ LEE S， KIM S B. Parallel simulated annealing with a greedy algorithm for Bayesian network structure learning［J］. IEEE Trans.on Knowledge and Data Engineering， 2019， 32（6）： 1157-1166.

［20］ LI S， WANG B. Hybrid parrallel Bayesian network structure learning from massive data using MapReduce［J］. Journal of Signal Processing Systems， 2018， 90（8/9）： 1115-1121.

［21］ CHEN X W， ANANTHA G， LIN X T. Improving Bayesian network structure learning with mutual information-based node ordering in the K2 algorithm［J］. IEEE Trans.on Knowledge and Data Engineering， 2008， 20（5）： 628-640.

［22］ XIE X L， XIE B Q， XIONG D， et al. New theoretical ISM-K2 Bayesian network model for evaluating vaccination effectiveness［J］. Journal of Ambient Intelligence and Humanized Computing， 2023， 14（9）： 12789-12805.

［23］ 李昡熠， 周鋆. 基于頻繁項挖掘的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法BNSL-FIM［J］. 計算機(jī)應(yīng)用， 2021， 41（12）： 3475-3479.

LI X Y， ZHOU Y. BNSL-FIM： Bayesian network structure learning algorithm based" on frequent item mining［J］. Journal of Computer Applications， 2021， 41（12）： 3475-3479.

［24］ PROENA H M， GRUNWALD P， BACK T， et al. Robust subgroup discovery： discovering subgroup lists using MDL［J］. Data Miningand Knowledge Discovery， 2022， 36（5）： 1885-1970.

［25］ LIAO T F， FASANG A E. Comparing groups of life-course sequences using the Bayesian information criterion and the likelihood-ratio test［J］. Sociological Methodology， 2021， 51（1）： 44-85.

［26］ ZHANG W J， FANG W， SUN J， et al. Learning Bayesian networks structures with an effective knowledge-driven GA［C］∥Proc.of the IEEE Congress on Evolutionary Computation， 2020.

［27］ CONTALDI C， VAFAEE F， NELSON P C. Bayesian network hybrid learning using an elite-guided genetic algorithm［J］. Artificial Intelligence Review， 2019， 52（1）： 245-272.

［28］ CONTALDI C， VAFAEE F， NELSON P C. The role of crossover operator in Bayesian network structure learning performance： a comprehensive comparative study and new insights［C］∥Proc.of the Genetic and Evolutionary Computation Conference， 2017： 769-776.

［29］ JOSE S， LIU S， LOUIS S， et al. Towards a hybrid approach for evolving Bayesian networks using genetic algorithms［C］∥Proc.of the IEEE 31st International Conference on Tools with Artificial Intelligence， 2019： 705-712.

［30］ YAN K F， FANG W， LU H Y， et al. Mutual information-guided GA for Bayesian network structure learning［J］. IEEE Trans.on Knowledge and Data Engineering， 2022， 35（8）： 8282-8299.

作者簡介

蔡一鳴（1998—），男，碩士研究生，主要研究方向為并行計算、貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)。

馬 力（2002—），男，主要研究方向為貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)。

陸恒楊（1991—），男，副教授，博士，主要研究方向為機(jī)器學(xué)習(xí)。

方 偉（1980—），男，教授，博士，主要研究方向為智能優(yōu)化算法。