摘 要： 針對高維數(shù)據(jù)下貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)精度和效率低的問題，提出一種基于歸一化互信息和近似馬爾可夫毯的特征選擇（feature selection based on normalized mutual information and approximate Markov blanket， FSNMB）算法來獲取目標(biāo)節(jié)點(diǎn)的馬爾可夫毯（Markov blanket，MB），進(jìn)一步結(jié)合MB和Meek規(guī)則實(shí)現(xiàn)基于特征選擇的局部貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)（construct local Bayesian network based on feature selection， FSCLBN）算法，提高局部貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的精度和效率。實(shí)驗(yàn)證明，在高維數(shù)據(jù)中， FSCLBN算法與現(xiàn)存的局部貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法相比更具優(yōu)勢。

關(guān)鍵詞： 貝葉斯網(wǎng)絡(luò); 特征選擇; 互信息; 馬爾可夫毯

中圖分類號： TP 181

文獻(xiàn)標(biāo)志碼： A

DOI：10.12305/j.issn.1001-506X.2024.08.15

Local Bayesian network structure learning for high-dimensional data

WANG Yangyang， GAO Xiaoguang^*， RU Xinxin

（School of Electronic Information， Northwestern Polytechnical University， Xi’an 710129， China）

Abstract： To address the issue of low learning accuracy and efficiency of Bayesian network structure learning under high-dimensional data， a feature selection based on normalized mutual information and approximate Markov blanket （FSNMB） algorithm is proposed to obtain the Markov blanket （MB） of the target node. The MB and Meek’s rule are further combined to implement the algorithm of construct local Bayesian network based on feature selection （FSCLBN）， which improves the accuracy and efficiency of local Bayesian network structure learning. Experiment results show that in high-dimensional data， the FSCLBN algorithm has more advantages than the existing local Bayesian network structure learning algorithms.

Keywords： Bayesian network; feature selection; mutual information; Markov blanket （MB）

0 引 言

貝葉斯網(wǎng)絡(luò)（Bayesian network， BN）是一種結(jié)合概率論和圖論的有向無環(huán)圖（directed acyclic graphical， DAG）模型，是目前處理不確定性知識表達(dá)和因果推理領(lǐng)域最有效的因果模型之一^［1-2］。BN已經(jīng)在軍事威脅評估、生物醫(yī)學(xué)、系統(tǒng)評估等方面得到了廣泛應(yīng)用^［3-4］。BN的研究主要分為3個(gè)方面：結(jié)構(gòu)學(xué)習(xí)、參數(shù)學(xué)習(xí)^［5］和推理，其中結(jié)構(gòu)學(xué)習(xí)是參數(shù)學(xué)習(xí)和推理的基礎(chǔ)。學(xué)習(xí)最優(yōu)的BN結(jié)構(gòu)已經(jīng)被證明是一個(gè)非確定性多項(xiàng)式困難（non-deterministic polynomial hard， NP-hard）問題^［6-7］。

馬爾可夫毯（Markov blanket， MB）是概率圖模型中的一個(gè)重要概念，用于表示一個(gè)節(jié)點(diǎn)在給定其所有鄰居節(jié)點(diǎn)的情況下與其他節(jié)點(diǎn)之間的條件獨(dú)立性關(guān)系。利用MB學(xué)習(xí)BN結(jié)構(gòu)是一種行之有效的方法^［8-9］。具體來說，對于每個(gè)節(jié)點(diǎn)，其MB中包括該節(jié)點(diǎn)的所有父節(jié)點(diǎn)和子節(jié)點(diǎn)以及配偶節(jié)點(diǎn)。Koller等^［10］已經(jīng)證明，在忠實(shí)假設(shè)和存在正確的條件獨(dú)立性測試的情況下，目標(biāo)的MB是唯一的、能夠充分解釋目標(biāo)變量的最小特征集。因此，MB是研究BN建模的重要工具。目前，具有代表性的MB算法有：收縮-增長MB（grow-shrink Markov blanket， GSMB）^［11］，增量關(guān)聯(lián)MB（incremental association Markov blanket， IAMB）^［12］，最大-最小MB（max-min Markov blanket， MMMB）^［13］，HITON-MB^［14］和同步發(fā)現(xiàn)MB（simultaneous Markov blanket， STMB）^［15］等。GSMB算法包含增長和收縮兩個(gè)階段，是第一個(gè)比較完備的MB發(fā)現(xiàn)算法，但其效率不高，無法擴(kuò)展到大規(guī)模節(jié)點(diǎn)。Tsamardinos等^［12］在GSMB算法的基礎(chǔ)上提出IAMB算法，與GS算法相比效率得到有效提升。MMMB算法是首個(gè)利用拓?fù)湫畔⑦M(jìn)行MB學(xué)習(xí)的算法，采用了一種分而治之的方法來進(jìn)行MB求解。MMMB算法對原有算法進(jìn)行改進(jìn)后提出HITON-MB算法，該算法交錯(cuò)地進(jìn)行添加或刪除節(jié)點(diǎn)操作，這樣能夠盡早消除誤選節(jié)點(diǎn)，以減少運(yùn)算復(fù)雜度。Gao等^［15］提出STMB算法以提升MB發(fā)現(xiàn)效率，借用配偶變量來輔助刪除父子（parents and children，PC）集中的誤報(bào)變量。MB的忠實(shí)性假設(shè)認(rèn)為，在給定該節(jié)點(diǎn)的MB的情況下，節(jié)點(diǎn)與其他非鄰居節(jié)點(diǎn)之間不存在條件獨(dú)立性。上述MB算法均是基于忠實(shí)性假設(shè)開發(fā)的。然而，當(dāng)數(shù)據(jù)的維度比較高或樣本量較少時(shí)，忠實(shí)性假設(shè)可能不再成立，同時(shí)原有的MB算法的學(xué)習(xí)效率和精度也會下降。

隨著大數(shù)據(jù)技術(shù)的發(fā)展，數(shù)據(jù)的維數(shù)（數(shù)據(jù)集中變量的個(gè)數(shù)）激增，高維數(shù)據(jù)（一般指維數(shù)大于50的數(shù)據(jù)集）呈現(xiàn)出普遍性，互聯(lián)網(wǎng)、軍事、醫(yī)療等領(lǐng)域已經(jīng)積累了海量的高維數(shù)據(jù)^［16-17］。例如，在生物信息學(xué)領(lǐng)域，人類基因表達(dá)數(shù)據(jù)可以輕松超過1 000維?；诟呔S數(shù)據(jù)學(xué)習(xí)節(jié)點(diǎn)的MB是一個(gè)具有挑戰(zhàn)性的問題^［18］。首先，高維數(shù)據(jù)的“維度災(zāi)難”使得MB的計(jì)算復(fù)雜度呈指數(shù)增長，算法無法在有限的時(shí)間內(nèi)做出響應(yīng);其次，高維數(shù)據(jù)本身具有稀疏性，數(shù)據(jù)中存在許多與標(biāo)簽不相關(guān)或冗余的特征，很難確定節(jié)點(diǎn)之間的依賴關(guān)系，導(dǎo)致原有的基于低維數(shù)據(jù)、表現(xiàn)良好的算法可能無法得到較好的建模精度、造成計(jì)算資源的浪費(fèi);最后，高維數(shù)據(jù)由于維度高、特征多，通常表現(xiàn)出小樣本的特性，無法滿足忠實(shí)性的假設(shè)^［19］，而傳統(tǒng)的BN結(jié)構(gòu)學(xué)習(xí)算法對樣本量要求較高，這也成為高維數(shù)據(jù)BN結(jié)構(gòu)學(xué)習(xí)的難點(diǎn)之一。

當(dāng)僅僅需要考慮目標(biāo)節(jié)點(diǎn)與周圍節(jié)點(diǎn)的因果關(guān)系時(shí)，學(xué)習(xí)目標(biāo)節(jié)點(diǎn)的局部BN能夠提高學(xué)習(xí)效率、節(jié)省計(jì)算開銷。針對高維數(shù)據(jù)本身具有的高維數(shù)和稀疏性的特點(diǎn)，在保證其局部依賴關(guān)系的基礎(chǔ)上對其進(jìn)行降維處理，是基于高維數(shù)據(jù)學(xué)習(xí)局部BN的有效方法。特征選擇是一種主流的數(shù)據(jù)降維方法，其從原始特征中選擇出一些最有效的特征來替代原始數(shù)據(jù)特征，使得系統(tǒng)的特定指標(biāo)最優(yōu)化，從而達(dá)到降低數(shù)據(jù)集維度的目的，進(jìn)而提升模型的效果和性能^［20］。特征選擇得到的特征具有明確的物理含義，方便后續(xù)模型的因果推理。目標(biāo)結(jié)點(diǎn)的MB求解過程的本質(zhì)也是特征選擇的過程^［18］。因此，尋找有效的特征選擇方法來替代傳統(tǒng)的MB求解算法是突破高維數(shù)據(jù)處理壁壘、增加模型可解釋性、建立高質(zhì)量BN模型的關(guān)鍵。

綜上，高維數(shù)據(jù)集的出現(xiàn)給現(xiàn)有的BN結(jié)構(gòu)學(xué)習(xí)算法提出了挑戰(zhàn)。本文的主要工作包括：首先，比較了傳統(tǒng)MB算法與本文提出的MB算法的準(zhǔn)確度和時(shí)間消耗;其次，基于真實(shí)數(shù)據(jù)集比較各個(gè)MB算法得到的特征子集的分類準(zhǔn)確性;最后，比較了本文提出的局部BN算法與其他局部BN構(gòu)建方法的準(zhǔn)確度和運(yùn)行效率。

1 預(yù)備知識

1.1 BN

BN的結(jié)構(gòu)由DAG定義，可以用G（V，E）表示，其中V={V₁，V₂，…，V_n}是網(wǎng)絡(luò)中的節(jié)點(diǎn)集合，E為有向邊的集合，代表兩個(gè)節(jié)點(diǎn)之間的直接依賴關(guān)系。P為節(jié)點(diǎn)的概率分布，表示節(jié)點(diǎn)之間因果影響的強(qiáng)度。當(dāng)存在邊V_i→V_j時(shí)，表示V_i是V_j的父節(jié)點(diǎn)，V_j是V_i的子節(jié)點(diǎn)。

1.2 互信息與歸一化互信息

互信息是信息論中的重要概念，用于衡量兩個(gè)隨機(jī)變量之間相關(guān)性的大小。對于一對離散隨機(jī)變量（X，Y），隨機(jī)變量X和Y的不確定性可以通過熵H（X）和H（Y）來度量。對于x∈X與y∈Y，聯(lián)合分布為p（x，y）=p{X=x，Y=y}，邊際分布為p（x）=p{X=x}，p（y）=p{Y=y}。互信息I（X;Y）定義如下，log可取任意底數(shù)。

I（X;Y）=－∑x，yp（x，y）logp（x，y）p（x）p（y）（1）

隨機(jī)變量X和Y的總的不確定性可以用其聯(lián)合熵H（X，Y）來度量。在給定變量Y的條件下，變量X條件熵為H（X|Y）?；バ畔⒑挽刂g的關(guān)系如圖1所示。

由圖1可知，互信息還可以表示為

I（X;Y）=H（X）+H（Y）－H（X，Y）（2）

互信息越大，說明隨機(jī)變量X和Y之間的相關(guān)性越強(qiáng)。從式（2）可知：

0≤I（X;Y）≤min{H（X），H（Y）}（3）

Yu等^［21］采用對稱不確定性（symmetric uncertainty， SU）作為兩個(gè)變量之間的互信息度量，解決了互信息傾向于選擇取值較大的變量的問題。SU的表達(dá)式如下：

SU（X;Y）=2I（X;Y）H（X）+H（Y）（4）

Estevez等^［22］指出，互信息的上界受限于隨機(jī)變量中最小的熵，不同隨機(jī)變量的熵變化程度較大。將互信息做歸一化處理（將其嚴(yán)格限制在［0，1］內(nèi)）能夠彌補(bǔ)多值特征中互信息的偏差。歸一化互信息（normalized mutual information，NMI）定義如下：

NMI（X;Y）=I（X;Y）min{H（X），H（Y）}（5）

需要指出的是，如果變量并非離散型隨機(jī)變量，那么互信息與NMI并不適用，需要對連續(xù)型變量進(jìn)行離散化。常用的離散化方法有：等間距法、ChiMerge法^［23］、Hartemink法^［24］等。此外，基于最大信息系數(shù)（the maximal information coefficient， MIC）^［25］的度量方法也得到了廣泛應(yīng)用，該方法可以直接計(jì)算兩個(gè)連續(xù)型變量之間的相關(guān)性，但該方法的本質(zhì)依然基于離散化且運(yùn)算復(fù)雜度較高。

1.3 MB

MB是BN中的重要概念，其數(shù)學(xué)定義為：目標(biāo)節(jié)點(diǎn)T的MB為MB（T），則對于所有SíV＼MB（T）＼T，總有S⊥T|MB（T），表示在給定目標(biāo)節(jié)點(diǎn)的MB時(shí)，S與T相互獨(dú)立。其中，數(shù)學(xué)符號“＼”表示集合的差集運(yùn)算，“⊥”表示條件獨(dú)立。圖2顯示了目標(biāo)節(jié)點(diǎn)T的MB（紅色虛線框），包括其父節(jié)點(diǎn)C和D，子節(jié)點(diǎn)F以及配偶節(jié)點(diǎn)G。MB的發(fā)現(xiàn)過程本質(zhì)是一種特征選擇問題。對于特征集F和類變量C，特征子集MìF(xiàn)（f_i?M）為特征f_i的MB的條件為f_i⊥{F＼M＼f_i，C}|M。當(dāng)給定特征變量f_i的MB的M時(shí)，M中包含了關(guān)于f_i對類變量C和其他特征F＼M＼f_i的所有相關(guān)信息。根據(jù)特征與分類節(jié)點(diǎn)之間相關(guān)性，文獻(xiàn)［26］把特征分為4類：強(qiáng)相關(guān)特征、弱相關(guān)非冗余特征、弱相關(guān)且冗余特征和無關(guān)特征，MB應(yīng)當(dāng)包含強(qiáng)相關(guān)特征和弱相關(guān)非冗余特征。當(dāng)特征子集M存在時(shí)，f_i對分類沒有貢獻(xiàn)，被認(rèn)為是冗余特征。由于目標(biāo)結(jié)點(diǎn)的MB求解過程的本質(zhì)也是特征選擇的過程，本文中的特征也可視為BN中的節(jié)點(diǎn)。

1.4 近似MB

對于特征集F中的第i個(gè)特征f_i和第j個(gè)特征f_j，如果滿足：

I（f_i;C）gt;I（f_j;C）

I（f_j;C）lt;I（f_i;f_j）（6）

則稱特征f_i是f_j的近似MB^［21］。

針對高維數(shù)據(jù)下忠實(shí)性假設(shè)可能不再成立的問題，為了提高M(jìn)B的學(xué)習(xí)效率和精度，本文結(jié)合NMI和近似MB來求解目標(biāo)節(jié)點(diǎn)的MB，這在一定程度上可以減少計(jì)算復(fù)雜度，增加模型泛化能力。結(jié)合NMI，將近似MB重新定義，對于特征f_i和f_j，如果滿足：

NMI（f_i;C）gt;NMI（f_j;C）

NMI（f_j;C）lt;NMI（f_i;f_j）（7）

則稱特征f_i是f_j的近似MB。此時(shí)，特征f_j對于特征f_i來說是冗余特征，需要被刪除。

2 MB發(fā)現(xiàn)算法

基于上述定義，本文提出了基于NMI和近似MB的特征選擇（feature selection based on NMI and approximate MB， FSNMB）算法，用于發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)的MB。通過求解近似MB，理論上可以得到目標(biāo)節(jié)點(diǎn)的PC節(jié)點(diǎn)（強(qiáng)相關(guān)性特性），但是無法保證得到的特征子集中包含配偶節(jié)點(diǎn)（弱相關(guān)但非冗余特征）。因此，需要通過繼續(xù)求解目標(biāo)節(jié)點(diǎn)的所有PC節(jié)點(diǎn)的近似MB，來保證得到的特征子集包含目標(biāo)節(jié)點(diǎn)的配偶節(jié)點(diǎn)。

FSNMB算法分為兩步執(zhí)行。

步驟 1 去除不相關(guān)特征和冗余特征。根據(jù)式（5）計(jì)算特征f_i∈F與目標(biāo)分類節(jié)點(diǎn)C之間的NMI（f_i;C）。比較NMI（f_i;C）與給定的閾值ε，如果存在NMI（f_i;C）gt;ε，則認(rèn)為特征f_i與類別C具有強(qiáng)相關(guān)性，應(yīng)當(dāng)被保留。否則，認(rèn)為該f_i是不相關(guān)特征，應(yīng)當(dāng)從F中刪除。將得到的特征子集按照NMI的大小進(jìn)行降序排列。根據(jù)式（7），如果分類節(jié)點(diǎn)C與特征f_i之間的相關(guān)性NMI（f_i;C）大于分類節(jié)點(diǎn)C與特征f_j之間的相關(guān)性NMI（f_j;C），并且f_i與f_j之間的相關(guān)性NMI（f_i;f_j）大于f_j與C之間的相關(guān)性NMI（f_j;C），說明特征f_j對于f_i來說是冗余特征，應(yīng)當(dāng)從F中刪除。此時(shí)F中剩余的特征均為強(qiáng)相關(guān)特征，可視為分類節(jié)點(diǎn)C的PC節(jié)點(diǎn)集，記為PC_C。

步驟 2 查找弱相關(guān)非冗余特征。為了能夠獲得節(jié)點(diǎn)C的配偶節(jié)點(diǎn)，需要繼續(xù)求得節(jié)點(diǎn)temp∈PC_C的PC節(jié)點(diǎn)。對節(jié)點(diǎn)temp重復(fù)步驟1，得到其PC節(jié)點(diǎn)集PC_temp。取A∈PC_temp。需要注意，這時(shí)節(jié)點(diǎn)A可能是節(jié)點(diǎn)C的配偶節(jié)點(diǎn)，需要進(jìn)一步通過條件獨(dú)立性進(jìn)行判斷。具體來說，如果?Y∈PC_C使得A⊥C|Y且使得A⊥C|{Y，temp}不再成立，說明A是C的配偶節(jié)點(diǎn)，記為AíSP_C（temp）。

經(jīng)過上述兩步處理，刪除了不相關(guān)特征和冗余特征，并增加了弱相關(guān)非冗余特征，最終得到MB的最優(yōu)特征子集。將上述兩個(gè)實(shí)現(xiàn)步驟分別實(shí)現(xiàn)為算法1，即基于特征選擇的PC節(jié)點(diǎn)集的查找（feature selection to find parents and children， FSPC）算法和算法2（FSNMB算法）。其中，算法1用于獲取目標(biāo)節(jié)點(diǎn)的PC節(jié)點(diǎn)，算法2基于算法1來查找目標(biāo)節(jié)點(diǎn)的配偶節(jié)點(diǎn)。

3 局部BN學(xué)習(xí)算法

基于分類節(jié)點(diǎn)的MB，可以推斷節(jié)點(diǎn)之間的條件獨(dú)立性關(guān)系，進(jìn)而學(xué)習(xí)局部BN結(jié)構(gòu)。將目標(biāo)分類節(jié)點(diǎn)C對應(yīng)的局部BN結(jié)構(gòu)為G，記有向邊V_i→V_j為G（V_i，V_j）=1且G（V_j，V_i）=0，記無向邊V_i－V_j為G（V_i，V_j）=1且G（V_j，V_i）=1。FSNMB算法為局部BN結(jié)構(gòu)的學(xué)習(xí)提供了便利。首先，對于\"_temp∈PC_C，無法確定節(jié)點(diǎn)C和節(jié)點(diǎn)temp邊的方向，所以其存在無向邊，記為G（C，temp）=1且G（temp，C）=1。其次，對于AíSP_C（temp），由第2節(jié)可知G（A，temp）=1，G（temp，A）=0且G（C，temp）=1，G（temp，C）=0。最后，可以進(jìn)一步結(jié)合Meek規(guī)則^［27］對網(wǎng)絡(luò)結(jié)構(gòu)G進(jìn)行更新。

基于上述討論，本節(jié)提出一種基于特征選擇的局部BN結(jié)構(gòu)（construct local BN based on feature selection， FSCLBN）算法，具體過程如算法3所示。

4 實(shí)驗(yàn)驗(yàn)證

4.1 實(shí)驗(yàn)設(shè)置

表1展示了5個(gè)常見的標(biāo)準(zhǔn)BN的基本信息，包括：節(jié)點(diǎn)數(shù)量、邊數(shù)量、最大出入度等信息。本文從5個(gè)標(biāo)準(zhǔn)網(wǎng)絡(luò)中分別選擇一個(gè)目標(biāo)節(jié)點(diǎn)（5個(gè)節(jié)點(diǎn)信息見表2），用于FSNMB算法和4種MB算法（IAMB、HITON-MB、MMMB和STMB），以及FSCLBN算法和其他3種局部BN學(xué)習(xí)算法（PCD_by_PCD^［28］、CMB（Casual MB）^［29］和MB_by_MB^［30］）的結(jié)果對比。實(shí)驗(yàn)硬件配置為Windows 10操作系統(tǒng)，i5-12400F 2.50 GHz處理器， 32 G內(nèi)存?；谪惾~斯網(wǎng)絡(luò)工具箱（Bayesian network toolbox，BNT）實(shí)現(xiàn)，針對每一個(gè)標(biāo)準(zhǔn)網(wǎng)絡(luò)，采用BNT中的“sample_bnet”函數(shù)生成30個(gè)測試數(shù)據(jù)集（包括50、500、5 000個(gè)樣本的數(shù)據(jù)集各10個(gè)），最終的實(shí)驗(yàn)結(jié)果數(shù)據(jù)以均值±標(biāo)準(zhǔn)差的形式表示。對于MB學(xué)習(xí)算法，其結(jié)果評價(jià)指標(biāo)主要包括F得分（F_score）、準(zhǔn)確率precision、召回率recall和運(yùn)行時(shí)間。采用T檢驗(yàn)用于驗(yàn)證不同算法的F得分之間是否存在顯著性差異。其中，F(xiàn)得分的計(jì)算方法如下所示：

F_score=2precision·recallprecision+recall（8）

對于局部BN結(jié)構(gòu)學(xué)習(xí)算法，分別采用F得分、漢明距離、反向邊數(shù)量、丟失邊數(shù)量、多余邊數(shù)量和運(yùn)行時(shí)間6個(gè)指標(biāo)進(jìn)行算法性能比較。

表3為從一網(wǎng)站^［31］獲取的5個(gè)真實(shí)數(shù)據(jù)集的基本信息，其涵蓋了不同的樣本數(shù)量、特征數(shù)量和類別數(shù)量。對5個(gè)數(shù)據(jù)集進(jìn)行等間距離散化，基于 K最近鄰（K-nearest neighbor， KNN）、支持向量機(jī)（support vector machine， SVM）、隨機(jī)森林（random forest， RF）、決策樹（decision tree， DT）和樸素貝葉斯分類器（naive Bayes classifier， NBC）5種分類器，采用10倍交叉驗(yàn)證法，進(jìn)一步驗(yàn)證FSNMB算法得到的MB在各個(gè)分類器上的分類精度以及平均分類精度。

4.2 實(shí)驗(yàn)結(jié)果

表4～表6分別為FSNMB、IAMB、HITON-MB、MMMB和STMB 5種MB算法基于50、500和5 000個(gè)樣本的F得分、準(zhǔn)確率、召回率和運(yùn)行耗時(shí)結(jié)果。其中，粗體代表該指標(biāo)下對應(yīng)數(shù)據(jù)集的最佳結(jié)果，^*代表所提方法與對比方法相比在T檢驗(yàn)下具有顯著性差異（取plt;0.05）。由表4～表6可知，F(xiàn)SNMB算法在多個(gè)數(shù)據(jù)集上取得了較高的F得分、準(zhǔn)確率和召回率，耗時(shí)較少，在不同的樣本量下綜合性能表現(xiàn)最好。具體來說，F(xiàn)SNMB在50和500個(gè)樣本數(shù)據(jù)集上表現(xiàn)最好，在Alarm、Win95pts和Andes上均取得了最佳F得分，但是當(dāng)樣本量為5 000時(shí)，其表現(xiàn)不如經(jīng)典的MB算法。IAMB在部分?jǐn)?shù)據(jù)集中取得了較高的F得分，運(yùn)行效率高，但當(dāng)樣本量不足時(shí)出現(xiàn)召回率過低的問題。HITON-MB算法在樣本充足時(shí)具有較高的F得分，當(dāng)目標(biāo)節(jié)點(diǎn)的MB規(guī)模較大時(shí)（如Pathfinder），存在計(jì)算效率較低的問題。MMMB和STMB算法具有較高的F得分，但實(shí)時(shí)性較差，不適合對時(shí)間敏感的應(yīng)用場景。綜合來看，F(xiàn)SNMB算法相對于其他4種算法具有一定優(yōu)勢，尤其在高維小樣本數(shù)量下能取得最優(yōu)的運(yùn)行結(jié)果，表現(xiàn)出較好的魯棒性，在F得分、精度、召回率和運(yùn)行耗時(shí)等方面表現(xiàn)出色，具有較高的穩(wěn)定性、準(zhǔn)確性和效率。

表7展示了5種MB算法基于5種分類器的分類精度以及平均分類精度信息。對于Wine數(shù)據(jù)集，F(xiàn)SNMB算法在所有分類器中的平均分類精度為0.94，表現(xiàn)較好，接近于其他算法的最高精度0.95。IAMB的表現(xiàn)與其他4種算法具有較大的差距，僅為0.77。在Breast數(shù)據(jù)集中，F(xiàn)SNMB算法的平均分類精度為0.88，與其他算法表現(xiàn)相當(dāng)，但在NBC上表現(xiàn)略差。其中，IAMB表現(xiàn)最好，尤其是在NBC上表現(xiàn)最佳。對于Ionosphere數(shù)據(jù)集，F(xiàn)SNMB算法的平均分類精度為0.85，僅次于MMMB的0.86。在Splice數(shù)據(jù)集上，F(xiàn)SNMB算法的平均分類精度為0.90，好于其他4種算法，在KNN、SVM、RF和DT這4種分類器上均取得了最佳分類效果。對于較高維的Semeionp數(shù)據(jù)集，F(xiàn)SNMB算法的平均分類精度為0.70，好于IAMB算法的0.39，而HITON-MB、MMMB和STMB算法均未在10 min內(nèi)得到運(yùn)行結(jié)果。綜合來看，F(xiàn)SNMB算法在多個(gè)真實(shí)數(shù)據(jù)上表現(xiàn)出優(yōu)勢，兼顧了更高的平均分類精度以及運(yùn)行效率。然而，在某些特定數(shù)據(jù)集上，其他算法可能具有更好的性能。因此，在選擇算法時(shí)，需要綜合考慮數(shù)據(jù)集特征和任務(wù)要求，確定最佳算法。

表8～表10的數(shù)據(jù)展示了4種局部BN學(xué)習(xí)算法（FSCLBN、PCD_by_PCD、CMB和MB_by_MB）基于5個(gè)標(biāo)準(zhǔn)網(wǎng)絡(luò)的運(yùn)行結(jié)果。從F得分來看，F(xiàn)SCLBN在不同樣本量的Alarm、Hepar2和Win95pts網(wǎng)絡(luò)上均表現(xiàn)出色，但在Andes網(wǎng)絡(luò)上表現(xiàn)一般，丟失邊數(shù)量較多。PCD_by_PCD、CMB和MB_by_MB 3種算法的F得分對樣本量敏感，當(dāng)樣本量充足時(shí)具有較高的F得分，但當(dāng)樣本量不足時(shí)，表現(xiàn)明顯不如FSCLBN。在運(yùn)行時(shí)間方面，F(xiàn)SCLBN的時(shí)間消耗與其他4種算法相比更具優(yōu)勢。此外，4種算法在Pathfinder網(wǎng)絡(luò)上均未在有限時(shí)間內(nèi)（10 min）得到運(yùn)行結(jié)果。整體來看，F(xiàn)SCLBN具有較高的運(yùn)算效率，受樣本量的影響較小，魯棒性好，能夠適應(yīng)小樣本量的高維數(shù)據(jù)的網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)。

5 結(jié)束語

本文提出一種基于NMI度量和近似MB的特征選擇算法，來求解高維數(shù)據(jù)中目標(biāo)節(jié)點(diǎn)的MB，同時(shí)將該算法結(jié)合Meek規(guī)則來求解目標(biāo)節(jié)點(diǎn)的局部BN，這兩種方法為高維數(shù)據(jù)學(xué)習(xí)BN結(jié)構(gòu)提供了新思路。實(shí)驗(yàn)證明，本文所提出的MB算法在大多數(shù)情況下優(yōu)于傳統(tǒng)的MB算法，所提出的局部BN結(jié)構(gòu)學(xué)習(xí)算法綜合性能優(yōu)于現(xiàn)有的結(jié)構(gòu)學(xué)習(xí)算法，在一定程度上解決了傳統(tǒng)BN結(jié)構(gòu)學(xué)習(xí)算法在高維數(shù)據(jù)中建模精度低和效率低下的問題。需要指出的是，并不能保證本文所提算法優(yōu)于所有同類型方法，與最先進(jìn)的方法對比并改進(jìn)現(xiàn)有的算法是本文未來的研究方向。

參考文獻(xiàn)

［1］CHEN S H， POLLINO C A. Good practice in Bayesian network modelling［J］. Environmental Modelling amp; Software， 2012， 37： 134-145.

［2］SCANAGATTA M， SALMERON A， STELLA F. A survey on Bayesian network structure learning from data［J］. Progress in Artificial Intelligence， 2019， 8： 425-439.

［3］ZHANG Y， WENG W G. Bayesian network model for buried gas pipeline failure analysis caused by corrosion and external interference［J］. Reliability Engineering amp; System Safety， 2020， 203： 107089.

［4］WANG Y Y， GAO X G， RU X X， et al. Using feature selection and Bayesian network identify cancer subtypes based on proteomic data［J］. Journal of Proteomics， 2023， 280： 104895.

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

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

［6］WANG X C， REN H J， GUO X X. A novel discrete firefly algorithm for Bayesian network structure learning［J］. Knowledge-Based Systems， 2022， 242： 108426.

［7］CHICKERING M， HECKERMAN D， MEEK C. Large-sample learning of Bayesian networks is NP-hard［J］. Journal of Machine Learning Research， 2004， 5： 1287-1330.

［8］譚翔元， 高曉光， 賀楚超. 基于馬爾可夫毯約束的最優(yōu)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法［J］. 電子學(xué)報(bào)， 2019， 47（9）： 1898-1904.

TAN X Y， GAO X G， HE C C. Learning optimal bayesian network structure constrained with Markov blanket［J］. Acta Electronica Sinica， 2019， 47（9）： 1898-1904.

［9］BUI A T， JUN C H. Learning Bayesian network structure using Markov blanket decomposition［J］. Pattern Recognition Letters， 2012， 33（16）： 2134-2140.

［10］KOLLER D， SAHAMI M. Toward optimal feature selection［J］. Internationa Conference on Machine Learning， 1996， 28（96）： 284-292.

［11］MARGARITIS D， THRUN S. Bayesian network induction via local neighborhoods［J］. Advances in Neural Information Processing Systems， 1999， 12： 505-511.

［12］TSAMARDINOS I， ALIFERIS C F， STATNIKOV A R， et al. Algorithms for large scale Markov blanket discovery［C］∥Proc.of the 16th International FAIRS Conference， 2003： 376-380.

［13］TSAMARDINOS I， BROWN L E， ALIFERIS C F. The max-min hill-climbing Bayesian network structure learning algorithm［J］. Machine Learning， 2006， 65： 31-78.

［14］ALIFERIS C F， TSAMARDINOS I， STATNIKOV A. HITON： a novel Markov blanket algorithm for optimal variable selection［C］∥Proc.of the AMIA Annual Symposium， 2003.

［15］GAO T， JI Q. Efficient Markov blanket discovery and its application［J］. IEEE Trans.on Cybernetics， 2016， 47（5）： 1169-1179.

［16］BOMMERT A， SUN X D， BISCHL B， et al. Benchmark for filter methods for feature selection in high-dimensional classification data［J］. Computational Statistics amp; Data Analysis， 2020， 143： 106839.

［17］JIA W K， SUN M L， LIAN J， et al. Feature dimensionality reduction： a review［J］. Complex amp; Intelligent Systems， 2022， 8（3）： 2663-2693.

［18］YU K， LIU L， LI J Y. A unified view of causal and non-causal feature selection［J］. ACM Transaction on Knowledge Discovery from Data， 2021， 15（4）： 1-46.

［19］SUN L Q， YANG Y L， NING T. A novel feature selection using Markov blanket representative set and particle swarm optimization algorithm［J］. Computational and Applied Mathematics， 2023， 42： 81.

［20］施啟軍， 潘峰， 龍福海， 等. 特征選擇方法研究綜述［J］. 微電子學(xué)與計(jì)算機(jī)， 2022， 39（3）： 1-8.

SHI Q J， PAN F， LONG F H， et al. A review of feature selection methods［J］. Microelectronics amp; Computer， 2022， 39（3）： 1-8.

［21］YU L， LIU H. Efficient feature selection via analysis of relevance and redundancy［J］. The Journal of Machine Learning Research， 2004， 5： 1205-1224.

［22］ESTEVEZ P A， TESMER M， PEREZ C A， et al. Normalized mutual information feature selection［J］. IEEE Trans.on Neural Networks， 2009， 20（2）： 189-201.

［23］KERBER R. Chimerge： discretization of numeric attributes［C］∥Proc.of the 10th National Conference on Artificial Intelligence， 1992： 123-128.

［24］HARTEMINK A J. Principled computational methods for the validation discovery of genetic regulatory networks［D］. Cambridge： Massachusetts Institute of Technology， 2001.

［25］RESHEF D N， RESHEF Y A， FINUCANE H K， et al. Detecting novel associations in large data sets［J］. Science， 2011， 334（6062）： 1518-1524.

［26］LI J D， CHENG K W， WANG S H， et al. Feature selection： a data perspective［J］. ACM Computing Surveys， 2017， 50（6）： 1-45.

［27］GAO T， FADNIS K， CAMPBELL M. Local-to-global Bayesian network structure learning［C］∥Proc.of the 34th International Conference on Machine Learning， 2017： 1193-1202.

［28］YIN J X， ZHOU Y， WANG C Z， et al. Partial orientation and local structural learning of causal networks for prediction［C］∥Proc.of the Workshop on the Causation and Prediction Challenge， 2008： 93-105.

［29］GAO T， JI Q. Local causal discovery of direct causes and effects［C］∥Proc.of the 29th Annual Conference on Neural Information Processing Systems， 2015： 2512-2520.

［30］WANG C Z， ZHOU Y， ZHAO Q， et al. Discovering and orienting the edges connected to a target variable in a DAG via a sequential local learning approach［J］. Computational Statistics amp; Data Analysis， 2014， 77： 252-266.

［31］MARKELLE K， RACHEL L， KOLBY N. The UCI Machine Learning Repository［EB/OL］. ［2023-08-06］. https： archive.ics.uci.edu.

作者簡介

王陽陽（1988—），男，博士研究生，主要研究方向?yàn)樘卣鬟x擇、貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)。

高曉光（1957—），女，教授，博士，主要研究方向?yàn)樨惾~斯網(wǎng)絡(luò)學(xué)習(xí)、航空火力控制、作戰(zhàn)效能分析。

茹鑫鑫（1993—），男，博士研究生，主要研究方向?yàn)樨惾~斯網(wǎng)絡(luò)參數(shù)學(xué)習(xí)。