基于全流程并行遺傳算法的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)

摘 要：

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

關(guān)鍵詞：

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

中圖分類號(hào)：

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)實(shí)問題中的不確定性，其性能受到BN拓?fù)浣Y(jié)構(gòu)影響。隨著結(jié)構(gòu)變量的增多，其搜索空間呈指數(shù)級(jí)增長，搜索最優(yōu)BN結(jié)構(gòu)成為非確定性多項(xiàng)式（non-deterministic polynomially， NP）難問題［2］。為解決此問題，可以通過減少搜索空間和加快搜索效率來開展研究。搜索空間的減少，往往采用約束的方法［3］，即分析變量之間的依賴程度，將條件獨(dú)立的特定結(jié)構(gòu)在搜索空間中篩除，實(shí)現(xiàn)更快的結(jié)構(gòu)學(xué)習(xí)。然而，約束方法依賴于指數(shù)級(jí)的高階條件獨(dú)立性測試計(jì)算復(fù)雜度增加且不可靠。另一種方法是采用評(píng)分搜索的方式加快搜索效率，在搜索過程中確定一個(gè)評(píng)分函數(shù)對(duì)候選的網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行評(píng)分，于是將結(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)搜索空間過大時(shí)，這類方法難以在較短的時(shí)間內(nèi)得出滿意的結(jié)果。

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

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

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

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è)計(jì)突變和鄰居搜索算子提高PSO的搜索能力。Lee等人［13］提出了一種針對(duì)矩陣數(shù)據(jù)的GA來學(xué)習(xí)BN結(jié)構(gòu)，每個(gè)BN個(gè)體都被映射為一個(gè)矩陣染色體。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）算法對(duì)解碼器和局部進(jìn)行了優(yōu)化。

1.2 并行BNSL算法

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

1.3 MI

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

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時(shí)，表示X和Y完全條件獨(dú)立。相反，越高的MI表示兩個(gè)變量的依賴程度越高。

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

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

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

1.4 BIC

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

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

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

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

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

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

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

2.1 MI與BIC評(píng)分的并行設(shè)計(jì)

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

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

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

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

2.2 遺傳算子的并行化

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

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

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

3 實(shí)驗(yàn)結(jié)果與分析

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

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

3.1 并行評(píng)分計(jì)算的有效性

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

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

3.2 并行MI計(jì)算的有效性

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

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

3.3 并行GA的有效性

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

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

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

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

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

3.5 SparkGA-BN的并行性能分析

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

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

為了比較提出的SparkGA-BN算法與其他算法在結(jié)構(gòu)學(xué)習(xí)上的性能，本文將SparkGA-BN算法與5種結(jié)構(gòu)學(xué)習(xí)算法進(jìn)行比較，包括有效的知識(shí)驅(qū)動(dòng)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］和使用本文并行方法實(shí)現(xiàn)的SMIGA［30］（Spark MI-GA）。本文使用了3種不同的樣本量（100 000、300 000和500 000）進(jìn)行訓(xùn)練，對(duì)每一種樣本量均獨(dú)立進(jìn)行10次實(shí)驗(yàn)并統(tǒng)計(jì)平均結(jié)果。

在參數(shù)設(shè)置方面，種群大小為Np=100，CI測試的閾值為tol=0.01，最大父節(jié)點(diǎn)數(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評(píng)價(jià)次數(shù)設(shè)置為Mg=45以保證公平性。對(duì)于并行參數(shù)，啟動(dòng)了4個(gè)虛擬節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)分配4個(gè)CPU核心。另外為了防止算法執(zhí)行時(shí)間過長，本文對(duì)算法的總體執(zhí)行時(shí)間進(jìn)行了限制，當(dāng)超過600 s時(shí)算法將會(huì)被強(qiáng)制終止。

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

F1=2precision·recallprecision+recall（4）

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

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

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

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

4 結(jié) 論

本文基于Spark框架提出了SparkGA-BN，實(shí)現(xiàn)了充分的數(shù)據(jù)復(fù)用和全流程的并行搜索，保證結(jié)構(gòu)學(xué)習(xí)準(zhǔn)確率的同時(shí)大幅提高結(jié)構(gòu)學(xué)習(xí)的效率。算法在約束階段，通過并行計(jì)算MI以高效限制搜索空間，并采用記憶化存儲(chǔ)產(chǎn)生的中間數(shù)據(jù)以復(fù)用。在評(píng)分搜索階段，算法設(shè)計(jì)了一種新的并行演化流程，保證選擇算子能夠在全種群中進(jìn)行選擇的同時(shí)并行執(zhí)行選擇算子。選擇算子和交叉算子的合并實(shí)現(xiàn)了兩算子的并行執(zhí)行以實(shí)現(xiàn)高效演化。通過盡可能復(fù)用存儲(chǔ)的中間數(shù)據(jù)并對(duì)當(dāng)前產(chǎn)生的數(shù)據(jù)進(jìn)行存儲(chǔ)，提高了數(shù)據(jù)復(fù)用率和全局執(zhí)行效率，實(shí)現(xiàn)了BIC評(píng)分流程的并行化。在4個(gè)基準(zhǔn)數(shù)據(jù)集上采用不同規(guī)模樣本的實(shí)驗(yàn)結(jié)果表明，所提算法在計(jì)算效率和學(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］ 李昡熠， 周鋆. 基于頻繁項(xiàng)挖掘的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法BNSL-FIM［J］. 計(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—），男，碩士研究生，主要研究方向?yàn)椴⑿杏?jì)算、貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)。

馬 力（2002—），男，主要研究方向?yàn)樨惾~斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)。

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

方 偉（1980—），男，教授，博士，主要研究方向?yàn)橹悄軆?yōu)化算法。