基于v-結(jié)構(gòu)和鄰居集的 啟發(fā)式貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法

摘 要： ""針對K2算法存在的序依賴性問題，提出了能夠從給定數(shù)據(jù)集中有效學(xué)習(xí)變量序的啟發(fā)式算法（H-vnK2）。具體而言，基于PC算法學(xué)習(xí)的v-結(jié)構(gòu)知識以節(jié)點(diǎn)塊的形式快速準(zhǔn)確修正部分父子節(jié)點(diǎn)順序，獲得部分節(jié)點(diǎn)的最優(yōu)序；基于PC算法學(xué)習(xí)的鄰居集知識以距離閾值啟發(fā)式策略進(jìn)一步從全局最優(yōu)角度修正父子節(jié)點(diǎn)順序， 獲得所有節(jié)點(diǎn)的最佳序。實(shí)驗(yàn)表明，在標(biāo)準(zhǔn)數(shù)據(jù)集Asia、Alarm網(wǎng)絡(luò)上，所提算法顯著優(yōu)于對比算法，其中與性能最好的基于因果效應(yīng)的方法相比，準(zhǔn)確率平均提升了7%，增量最高能達(dá)到33.3%，可以學(xué)習(xí)到更準(zhǔn)確的網(wǎng)絡(luò)結(jié)構(gòu)。

關(guān)鍵詞： "變量序； K2算法； v-結(jié)構(gòu)； 鄰居集

中圖分類號： "TP181 """文獻(xiàn)標(biāo)志碼： A

文章編號： "1001-3695（2022）02-020-0442-05

doi：10.19734/j.issn.1001-3695.2021.07.0273

Heuristic Bayesian network structure learning method "based on v-structure and neighbor set

Xu Miao， Wang Huiling， Liang Yi， Qi Xiaolong

（School of Cybersecurity amp; Information Technology， Yili Normal University， Yining Xinjiang 835000， China）

Abstract： "Aiming at the order dependency problem of the K2 algorithm，this paper proposed a heuristic algorithm（H-vnK2） to learn the node order effectively from a given data set.Specifically，based on the v-structure knowledge learned by the PC algorithm，it corrected the order of some parent-child nodes in the form of node blocks quickly and accurately，and then obtained the optimal order of some nodes.Based on the neighbor set knowledge learned by the PC algorithm，with the distance threshold heuristic strategy，it further modified the order of the parent-child nodes from the global optimal point of view，and then obtained the best order of all nodes.Experiments show that the proposed algorithm is significantly better than the comparison algorithm on the Asia and Alarm standard data set.Among them，compared with the best-performing method based on causal effects，the proposed algorithm improves the accuracy rate by 7% on average，and the increment can reach up to 33.3%.It can learn a more accurate network structure.

Key words： "variable order； K2 algorithm； v-structure； neighbor set

0 引言

貝葉斯網(wǎng)絡(luò)［1］起源自人工智能的研究，是概率統(tǒng)計(jì)和數(shù)據(jù)分析的有力工具。通過概率論和圖論的結(jié)合，既能直觀展現(xiàn)問題的結(jié)構(gòu)，又能有效降低概率推理的復(fù)雜度，在處理不確定性問題上具備顯著的優(yōu)勢，因此深受眾多學(xué)者們的關(guān)注。隨著時(shí)代的發(fā)展，貝葉斯網(wǎng)絡(luò)已被應(yīng)用在臨床醫(yī)學(xué)、視覺識別、信息檢索、自然語言處理和故障診斷等不同的復(fù)雜領(lǐng)域之中［2～5］。

在一定條件下，專家可以根據(jù)相應(yīng)的領(lǐng)域知識和經(jīng)驗(yàn)構(gòu)建出貝葉斯網(wǎng)絡(luò)，但這是非常復(fù)雜和容易出錯(cuò)的工作，大多數(shù)情況下無法得到可靠的網(wǎng)絡(luò)結(jié)構(gòu)。隨著機(jī)器學(xué)習(xí)技術(shù)的發(fā)展，研究者們開始關(guān)注從觀測數(shù)據(jù)中自動學(xué)習(xí)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)，研究證明該類方法是NP-hard［6］。為了更高效地獲得優(yōu)質(zhì)網(wǎng)絡(luò)結(jié)構(gòu)，研究者們提出了基于約束的算法［7，8］、基于評分—搜索的算法［9，10］和混合學(xué)習(xí)算法［11，12］三類主要學(xué)習(xí)算法。

基于約束的算法是對變量進(jìn)行一系列的獨(dú)立性檢測，查詢找到最優(yōu)的網(wǎng)絡(luò)模型，如SGS算法［7］和PC-stable算法［8］等。它們具有很好的學(xué)習(xí)性能且易于實(shí)現(xiàn)，但是在復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)下，這類算法的可靠性會下降。基于評分搜索的算法是用評分函數(shù)評價(jià)數(shù)據(jù)與候選結(jié)構(gòu)的擬合度，在候選結(jié)構(gòu)組成的空間里搜索最優(yōu)評分的結(jié)構(gòu)模型，如爬山法、粒子群算法［10］等，可以學(xué)習(xí)到較為準(zhǔn)確的網(wǎng)絡(luò)結(jié)構(gòu)，但是隨著變量數(shù)的增加，搜索空間會呈現(xiàn)出指數(shù)級增長的現(xiàn)象，降低學(xué)習(xí)效率?；旌蠈W(xué)習(xí)算法是將前兩種算法相融合，利用各自的優(yōu)點(diǎn)學(xué)習(xí)最佳結(jié)構(gòu)模型，例如MMHC算法［12］，通過MMPC算法產(chǎn)生候選父節(jié)點(diǎn)，然后利用貪婪算法確定邊的方向。這類算法學(xué)習(xí)效果較好，已經(jīng)成為目前貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的主要算法［13］。

K2算法［14］在已知特定節(jié)點(diǎn)序列的前提下可以學(xué)習(xí)到最佳的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)，并且有效避免似然等價(jià)的情況，在效率和精度上都優(yōu)于大多數(shù)經(jīng)典算法，但需要注意的是，節(jié)點(diǎn)順序的優(yōu)劣對K2算法的精度起著決定性作用。

針對評分—搜索空間復(fù)雜度高問題，受到K2算法的啟發(fā)，提出了一種基于v-結(jié)構(gòu)和鄰居集搜索最佳變量序的混合學(xué)習(xí)算法。主要?jiǎng)?chuàng)新點(diǎn)如下：首次將基于約束算法學(xué)習(xí)的v-結(jié)構(gòu)應(yīng)用到變量序搜索中，確定部分節(jié)點(diǎn)的位置，減少序搜索空間?；趯W(xué)習(xí)的鄰居集，使用提議的距離度量算法進(jìn)一步修正節(jié)點(diǎn)序。實(shí)驗(yàn)表明，與經(jīng)典算法相比，該算法的精度性能顯著提升。

1 相關(guān)工作

K2算法是一類經(jīng)典的基于評分—搜索算法，因其在復(fù)雜度和精密度上表現(xiàn)出了良好的性能，且能夠有效處理似然等價(jià)的情況，受到了眾多學(xué)者的關(guān)注。但其依賴于變量序，即不同的變量序會產(chǎn)生不同的結(jié)構(gòu)，使得如何獲取高質(zhì)量變量序列以學(xué)習(xí)最優(yōu)模型成為一個(gè)不斷研究探討的題目。

近年來涌現(xiàn)出了許多相關(guān)研究方法，根據(jù)先驗(yàn)序列的獲取方式，可以分為基于先驗(yàn)序列和學(xué)習(xí)先驗(yàn)序列兩類?；谙闰?yàn)序列方法需要領(lǐng)域?qū)＜翌A(yù)先提供先驗(yàn)序列知識，結(jié)合K2算法的改進(jìn)來提升方法的學(xué)習(xí)精度和速度，如CE-GP［15］和分組并行化學(xué)習(xí)［16］。這類方法降低了時(shí)空復(fù)雜度，但要求正確的先驗(yàn)序列，很多情況下，尤其是高維場景很難獲得領(lǐng)域的先驗(yàn)序列；學(xué)習(xí)先驗(yàn)序列方法需要從數(shù)據(jù)中自動學(xué)習(xí)優(yōu)質(zhì)變量序列，結(jié)合K2算法構(gòu)建最優(yōu)模型，如基于互信息的MWST+T-K2［17］、NOK2［18］和因果效應(yīng)方法［19］，基于約束的混合結(jié)構(gòu)學(xué)習(xí)方法［20］和優(yōu)先級排序方法［21］，基于領(lǐng)域知識的皮爾森相關(guān)系數(shù)方法［22］以及基于強(qiáng)連通圖劃分的K2改進(jìn)算法［23］，這類算法實(shí)用性可觀且易于實(shí)現(xiàn)，但都存在些許不足?；诨バ畔⒌姆椒ǜm用于小規(guī)模網(wǎng)絡(luò)，基于約束的方法仍然受到基于約束方法步的限制，基于領(lǐng)域知識的方法需要有完備的領(lǐng)域知識作為基礎(chǔ)，基于強(qiáng)連通圖劃分的方法受到變量最佳父集的制約。

2 啟發(fā)式貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法

提出的H-vnK2算法主要有三部分組成：a）初始化的節(jié)點(diǎn)優(yōu)先序列；利用改進(jìn)的因果效應(yīng)方法學(xué)習(xí)每個(gè)節(jié)點(diǎn)的優(yōu)先度，根據(jù)優(yōu)先度降序排列獲得節(jié)點(diǎn)優(yōu)先序列；b）基于v-結(jié)構(gòu)知識首次調(diào)整，通過PC算法學(xué)習(xí)節(jié)點(diǎn)的v-結(jié)構(gòu)和鄰居集，根據(jù)v-結(jié)構(gòu)進(jìn)一步調(diào)整節(jié)點(diǎn)順序；c）基于鄰居集的順序再調(diào)整，結(jié)合節(jié)點(diǎn)的鄰居集通過距離閾值算法，完成節(jié)點(diǎn)序的進(jìn)一步修正得到最終節(jié)點(diǎn)序，將其作為K2算法的先驗(yàn)順序，學(xué)習(xí)到最優(yōu)網(wǎng)絡(luò)模型。

2.1 節(jié)點(diǎn)優(yōu)先序列

節(jié)點(diǎn)優(yōu)先序列使用改進(jìn)版因果效應(yīng)來學(xué)習(xí)，算法分為二值狀態(tài)網(wǎng)絡(luò)和多值狀態(tài)網(wǎng)絡(luò)。根據(jù)網(wǎng)絡(luò)中變量的值狀態(tài)數(shù)量，分別從兩個(gè)算法出發(fā)，計(jì)算得到每個(gè)節(jié)點(diǎn)的優(yōu)先度，再進(jìn)行降序排列獲得節(jié)點(diǎn)優(yōu)先序列。對于二值狀態(tài)網(wǎng)絡(luò)，改進(jìn)版因果效應(yīng)［19］在不考慮“do-操作”的情況下對Pearl的因果效應(yīng)進(jìn)行了擴(kuò)展，考慮了 X i→X j 在 X j=1 和 X j=0 兩處的因果效應(yīng)。對于數(shù)據(jù)集中任意兩個(gè)節(jié)點(diǎn) X i、X j 之間的因果效應(yīng) CE X i→X j 如下：

CE X i→X j= N（X j=1） N ×［P（X j=1|X i=1）-P（X j=1|X i=0）］-

N（X j=0） N ×［P（X j=0|X i=1）-P（X j=0|X i=0）］ ""（1）

其中： N 表示總樣本數(shù)量； N（X j=1） 表示 X j=1 的樣本數(shù)量， N（X j=0） 表示 X j=0 的樣本數(shù)量。

對于多值狀態(tài)網(wǎng)絡(luò)，找出每個(gè)節(jié)點(diǎn)最多的兩個(gè)狀態(tài)值，通過相對應(yīng)的狀態(tài)值遍歷任意兩個(gè)節(jié)點(diǎn)間的因果效應(yīng)，學(xué)習(xí)得到節(jié)點(diǎn)優(yōu)先度。如果 X i 的最多狀態(tài)值為 a 和 b ， X j 的最多狀態(tài)值為 c 和 d ，那么就要考慮 X i→X j 在 X j=c 和 X j=d 兩處的因果效應(yīng)。對于數(shù)據(jù)集中任意兩個(gè)節(jié)點(diǎn) X i、X j 之間的因果效應(yīng) CE X i→X j 如下：

CE X i→X j= N（X j=c） N ×［P（X j=c|X i=a）-P（X j=c|X i=b）］-

N（X j=d） N ×［P（X j=d|X i=a）-P（X j=d|X i=b）］ ""（2）

其中： N 表示總樣本數(shù)量； N（X j=c） 表示 X j=c 的樣本數(shù)量， N（X j=d） 表示 X j=d 的樣本數(shù)量。

兩個(gè)算法都從第一個(gè)節(jié)點(diǎn)開始，分別利用式（1）（2）計(jì)算每兩個(gè)節(jié)點(diǎn)間的因果效應(yīng)，如果 CE X i→X jgt;CE X j→X i ，那么 X i 的優(yōu)先度加1；如果 CE X i→X jlt;CE X j→X i ，那么 X j 的優(yōu)先度加1。完成所有節(jié)點(diǎn)遍歷，降序排列學(xué)習(xí)到的節(jié)點(diǎn)優(yōu)先度，獲得節(jié)點(diǎn)優(yōu)先序列。

2.2 基于PC算法的v-結(jié)構(gòu)和鄰居集更新策略

2.2.1 PC算法

PC算法［24］是一種基于條件獨(dú)立測試的算法，較SGS算法有更低的時(shí)間復(fù)雜度。算法的核心點(diǎn)是從一個(gè)完全無向圖開始，學(xué)習(xí)自0階集合的條件獨(dú)立性到 n 階集合的條件獨(dú)立性。在測試過程中，變量對的條件集由變量的鄰居集決定，該鄰居集會隨著算法的迭代進(jìn)行動態(tài)變化。文獻(xiàn)［25］中的定理3.3給出PC算法能夠輸出表示有向無圈圖 G 的CPDAG，也就是說，PC算法能夠輸出正確的v-結(jié)構(gòu)。為了減少序空間搜索規(guī)模，準(zhǔn)確確定序的正確性，H-vnK2算法使用PC算法輸出的v-結(jié)構(gòu)和鄰居集進(jìn)行最優(yōu)節(jié)點(diǎn)序列的搜索。

2.2.2 v-結(jié)構(gòu)和鄰居集距離閾值更新策略

因果效應(yīng)得出的節(jié)點(diǎn)序列與真實(shí)序列存在一定偏差。為了減少搜索空間，提高正確序的識別，提出了基于v-結(jié)構(gòu)集的塊調(diào)整和變量鄰居集的距離閾值序搜索策略。對于無遮擋元組〈 X i，X j，X k 〉，如果有 X i→X j且X k→X j，X i和X k 都存在指向 X j 的有向邊，形成 X i→X j←X k 的結(jié)構(gòu)，那么就稱之為v-結(jié)構(gòu)?？梢钥闯?，v-結(jié)構(gòu)指明 X i和X k 都是 X j 的父節(jié)點(diǎn)。也就是說，在變量序中， X i和X k 的順序必然要排在 X j 的前面。

基于這一點(diǎn)，將PC算法獲得v-結(jié)構(gòu)信息應(yīng)用到序調(diào)整中，對學(xué)習(xí)到的節(jié)點(diǎn)優(yōu)先序列進(jìn)行進(jìn)一步更新。對于任意v-結(jié)構(gòu) X i→X j←X k ，在節(jié)點(diǎn)優(yōu)先序列中檢驗(yàn) X i 和 X k 是否在 X j 的前面，如不滿足，則將 X i 和 X k 以塊的形式插到 X j 之前，達(dá)到修正錯(cuò)誤序列的目的，如圖1所示。

v-結(jié)構(gòu)的使用使得部分節(jié)點(diǎn)的順序是最佳的，為了在合理的時(shí)間內(nèi)搜索到全局最佳的節(jié)點(diǎn)序，H-vnK2算法進(jìn)一步提出了基于鄰居集的啟發(fā)式策略。

定義1 "鄰居。如果 X 和 Y 之間存在一條邊，則變量 X 是變量 Y 的鄰居，反之亦然，記做Adj （X）={Y} 。

定義2 "鄰居距離。變量序 O 中，如果變量 X 是變量 Y 的鄰居，則兩者在序中位置的差值稱之為鄰居距離，記做Dis （X，Y）=|X index-Y index| 。其中： X index 指示了變量 X 在序 O 中的位置。

基于PC算法提供的鄰居集信息提出一種基于鄰居集距離的啟發(fā)式變量序調(diào)整策略檢測子節(jié)點(diǎn)和父節(jié)點(diǎn)的位置是否符合標(biāo)準(zhǔn)。該策略背后的想法是在真實(shí)結(jié)構(gòu)中如果兩個(gè)變量滿足鄰居關(guān)系，那么它們之間的路徑上不會有其他變量，否則與鄰居關(guān)系矛盾?；谶@一點(diǎn)，H-vnK2算法實(shí)現(xiàn)了跨多節(jié)點(diǎn)的快速位置調(diào)整策略。

具體而言，如果鄰居之間的距離超過了設(shè)定的距離閾值，Dis （X，Y）gt;γ ，那么調(diào)整處在序 O 中后方鄰居節(jié)點(diǎn) X 或 Y 的位置。不失一般性，假設(shè)在序 O 中節(jié)點(diǎn) Y 在后，節(jié)點(diǎn) X 在前。分為三種情況：a） 將節(jié)點(diǎn) Y 移動到節(jié)點(diǎn) X 前，確保節(jié)點(diǎn) Y 作為節(jié)點(diǎn) X 的父節(jié)點(diǎn)的情況被檢測；b）將節(jié)點(diǎn) Y 移動到節(jié)點(diǎn) X 后，確保節(jié)點(diǎn) Y 作為節(jié)點(diǎn) X 和 Y 之間節(jié)點(diǎn)的父節(jié)點(diǎn)的情況被檢測；c） 節(jié)點(diǎn) Y 保持不動。執(zhí)行過程如圖2所示。分別對這三種情況進(jìn)行BD評分［29］判定，選擇評分最優(yōu)的序列。其中，BD評分函數(shù)如下：

score （G|D）= log "P（G）+∑ n i=1 ∑ q i j=1 ［ log "Γ（a ij*） Γ（a ij*+m ij*） + ∑ r i k=1 "log "Γ（a ijk+m ijk） Γ（a ijk） ］ ""（3）

其中： a ijk 是狄利克雷分布中的超參數(shù)， a ij*=∑ r i k=1 a ijk ; "m ijk 表示變量 X i 的狀態(tài)為 k 時(shí)，其父節(jié)點(diǎn)取第 j 個(gè)值的樣本數(shù)量， m ij*=∑ r i k=1 m ijk 。

注意，從實(shí)驗(yàn)中觀察到距離閾值的設(shè)定對鄰居集調(diào)整策略至關(guān)重要，如果閾值過小，節(jié)點(diǎn)序列會陷入局部最優(yōu)，如果閾值過大，節(jié)點(diǎn)更新次數(shù)較少，極易丟失最佳節(jié)點(diǎn)序。到目前，已經(jīng)有了一個(gè)能夠使用K2算法學(xué)習(xí)貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)的顯著節(jié)點(diǎn)序。所提H-vnK2算法整體流程如算法1所示。

算法1 H-vnK2算法

輸入：節(jié)點(diǎn)集 N ；數(shù)據(jù)集 D ；距離閾值 γ ；父節(jié)點(diǎn)上限數(shù) u 。

輸出：一個(gè)貝葉斯網(wǎng)絡(luò)。

for "i=1 ： n

for "j=1 ： n

按照式（1）（2）計(jì)算每兩條邊的因果效應(yīng)

if "CE X i→X jgt;CE X j→X i

d X i=d X i+1

else "d X j=d X j+1

end if

end for

end for

將每個(gè)節(jié)點(diǎn)按照優(yōu)先度降序排序，獲得初始序列order

使用PC算法得到v結(jié)構(gòu) -v和各個(gè)節(jié)點(diǎn)的鄰居集-b；

while "X i，X j，X k∈v

if "X i→X j←X k=1

將 X i ， X k 移動到 X j 前面

while distance （X i，X l）gt;γ∈b

計(jì)算貝葉斯評分分?jǐn)?shù)，調(diào)整位置

end while

end if

end while

返回order

將order作為K2算法的節(jié)點(diǎn)順序

for "i=1 ： n

π i=

計(jì)算出節(jié)點(diǎn) X i 的評分 P old

令OKTOProceed為真

while OKTOProceed and "|π i|lt;u "do

找出排在 X i 前面的變量 X j ，得到最大新評分 P new

if "P newgt;P old "then

P old=P new

π i=π i∪{j};

else OKTOProceed為假

end if

end while

end for

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

實(shí)驗(yàn)在MATLAB R2016a環(huán)境下運(yùn)行，平臺為Windows 7，CPU為i5-4210M，內(nèi)存8 GB。選擇使用FullBNT-1.0.7工具箱中的Asia［26］和Alarm［27］兩個(gè)通用標(biāo)準(zhǔn)貝葉斯網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)，其信息如表1所示。與基于因果效應(yīng)的方法［19］、爬山法［1］、MMHC算法［12］和MCMC算法［28］進(jìn)行比較，分別從正確邊、反向邊、冗余邊、缺失邊的平均值與標(biāo)準(zhǔn)差方面驗(yàn)證H-vnK2算法對于貝葉斯網(wǎng)絡(luò)學(xué)習(xí)的優(yōu)質(zhì)性能。

1）Asia網(wǎng)絡(luò) Asia網(wǎng)絡(luò)是一個(gè)小型網(wǎng)絡(luò)，主要用于呼吸系統(tǒng)疾病診斷。分別取2 000、4 000、6 000、8 000、10 000、12 000、14 000、16 000、18 000、20 000十組樣本量數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，選用式（1）學(xué)習(xí)節(jié)點(diǎn)優(yōu)先序列，距離閾值取4，實(shí)驗(yàn)結(jié)果如表2和圖3～6所示。

由表2可知，H-vnK2算法學(xué)習(xí)的Asia網(wǎng)絡(luò)正確邊數(shù)目達(dá)到平均7.7條，較基于因果效應(yīng)的方法提高了10%，較MMHC算法的正確邊數(shù)目提高了22%，除了缺失邊平均值略高于基于因果效應(yīng)的方法0.1以外，在反向邊和冗余邊方面的性能均優(yōu)于對比算法。

v-結(jié)構(gòu)集調(diào)整與鄰居集距離更新策略相結(jié)合，使用基于v-結(jié)構(gòu)的正確父子順序信息和基于鄰居集的距離信息，全面檢測錯(cuò)誤父子順序并進(jìn)行修正，有效減少了錯(cuò)誤邊的產(chǎn)生。

圖3給出了不同樣本量下各個(gè)算法的正確邊數(shù)目，H-vnK2算法在2 000個(gè)樣本時(shí)較MCMC算法少一條正確邊，原因在于K2算法本身的局限性，即當(dāng)樣本量較少時(shí)，即使在正確的變量序下，K2算法的精度也會受到影響。當(dāng)樣本量大于等于10 000時(shí)，正確邊數(shù)目達(dá)到穩(wěn)定，均能學(xué)習(xí)到正確網(wǎng)絡(luò)。

在對比算法中，基于因果效應(yīng)的方法是最為優(yōu)越的。圖4給出了H-vnK2算法對基于因果效應(yīng)方法的正確邊增量對比?；谝蚬?yīng)的方法通過刪除邊和反向調(diào)節(jié)策略修正非法結(jié)構(gòu)，存在陷入局部最優(yōu)的可能，H-vnK2算法直接更新節(jié)點(diǎn)序列更為靈活，從源頭上避免非法結(jié)構(gòu)，結(jié)果表明了算法的有效性，增量最高可以達(dá)到33.3%。

圖5給出了不同算法學(xué)習(xí)Asia網(wǎng)絡(luò)的標(biāo)準(zhǔn)差對比，由于Asia網(wǎng)絡(luò)為小型網(wǎng)絡(luò)，僅有8條邊，學(xué)習(xí)難度不高，所以正確邊標(biāo)準(zhǔn)差差距不大，但仍然可以看出H-vnK2算法的數(shù)據(jù)波動最為穩(wěn)定。圖6展示了不同算法學(xué)習(xí)Asia網(wǎng)絡(luò)的正確率對比，H-vnK2算法的正確率達(dá)到了96%，優(yōu)于對比算法。

實(shí)驗(yàn)表明，對于Asia網(wǎng)絡(luò)，提議的H-vnK2算法比基于因果效應(yīng)方法的性能更優(yōu)異，在十組實(shí)驗(yàn)中，有七組數(shù)據(jù)學(xué)習(xí)到了正確的網(wǎng)絡(luò)結(jié)構(gòu)，而基于因果效應(yīng)的方法只有四組數(shù)據(jù)能學(xué)到真實(shí)的結(jié)構(gòu)。究其原因，H-vnK2算法產(chǎn)生反向邊和冗余邊情況的概率遠(yuǎn)低于基于因果效應(yīng)的方法。

2）Alarm網(wǎng)絡(luò) Alarm網(wǎng)絡(luò)是一個(gè)復(fù)雜網(wǎng)絡(luò)，主要用于醫(yī)療診斷監(jiān)控。在實(shí)驗(yàn)中分別生成2 000、4 000、6 000、8 000、10 000不同樣本量的五組數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，選用式（2）學(xué)習(xí)節(jié)點(diǎn)優(yōu)先序列，距離閾值取14，實(shí)驗(yàn)結(jié)果如表3和圖7～10所示。

由表3可知，在Alarm網(wǎng)絡(luò)中，H-vnK2算法在平均正確邊數(shù)目上達(dá)到了42.8條，而基于因果效應(yīng)的方法平均正確邊數(shù)目只達(dá)到41.2條，MMHC算法的正確邊數(shù)目平均只有34.1條，H-vnK2算法較基于因果效應(yīng)的方法準(zhǔn)確率提高了3.9%，較MMHC算法準(zhǔn)確率提高了25.5%。

H-vnK2算法雖然在缺失邊性能上不及基于因果效應(yīng)的方法，但在總體性能錯(cuò)誤邊上，本文H-vnK2算法優(yōu)于對比算法，原因是在學(xué)習(xí)節(jié)點(diǎn)序列過程中，該算法可以有效避免反向邊的產(chǎn)生。

圖7展示了各個(gè)算法的正確邊數(shù)目對比，H-vnK2算法明顯優(yōu)于對比算法，樣本量2 000時(shí)能得到40條正確邊，樣本量8 000時(shí)可以學(xué)習(xí)到45條正確邊，在五組數(shù)據(jù)中有四組數(shù)據(jù)都優(yōu)于基于因果效應(yīng)的方法。其原因是H-vnK2算法能夠獲得一個(gè)質(zhì)量較好的節(jié)點(diǎn)序列。

圖8展示了H-vnK2算法與對比算法中表現(xiàn)最優(yōu)的基于因果效應(yīng)方法的正確邊增量對比，在相同樣本量下，比較基于因果效應(yīng)方法的BDe評分調(diào)邊策略，H-vnK2算法應(yīng)用的策略可以學(xué)習(xí)到更多的正確邊，樣本量4 000和6 000時(shí)增量達(dá)到最高。

圖9展示了不同算法正確邊的標(biāo)準(zhǔn)差對比，由于Alarm網(wǎng)絡(luò)中邊數(shù)多，父子節(jié)點(diǎn)數(shù)多，增加了算法陷入局部最優(yōu)情況的可能性，所以正確邊標(biāo)準(zhǔn)差差距較大。相比而言，H-vnK2算法正確邊標(biāo)準(zhǔn)差性能最好。圖10展示了Alarm網(wǎng)絡(luò)中不同算法學(xué)習(xí)的正確率對比，H-vnK2算法的正確率達(dá)到了93%。

實(shí)驗(yàn)表明，在Alarm網(wǎng)絡(luò)數(shù)據(jù)集上，H-vnK2算法的準(zhǔn)確性和穩(wěn)定性都優(yōu)于基于因果效應(yīng)的方法、MMHC算法、爬山法和MCMC算法，有更好的學(xué)習(xí)性能，可以獲得更高質(zhì)量的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)。

4 結(jié)束語

針對K2算法需要優(yōu)質(zhì)先驗(yàn)序的問題，提出了一種基于v-結(jié)構(gòu)和鄰居集的啟發(fā)式貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法。該算法通過因果效應(yīng)構(gòu)建初始節(jié)點(diǎn)序列，利用PC算法學(xué)習(xí)的v-結(jié)構(gòu)和鄰居集對初始節(jié)點(diǎn)序進(jìn)行父子關(guān)系修正操作?；趘-結(jié)構(gòu)的塊調(diào)整策略不僅提高了序搜索效率而且保證了序的質(zhì)量；基于鄰居集的啟發(fā)式策略有效避免了局部最優(yōu)的場景。最后通過K2算法得到最佳網(wǎng)絡(luò)模型。相較于對比算法，該算法在準(zhǔn)確性和穩(wěn)定性上都具有明顯優(yōu)勢，可以學(xué)習(xí)到優(yōu)質(zhì)的網(wǎng)絡(luò)結(jié)構(gòu)，進(jìn)一步解決了K2算法對準(zhǔn)確先驗(yàn)節(jié)點(diǎn)序的需求，為貝葉斯網(wǎng)絡(luò)的學(xué)習(xí)提供了新的思路。

參考文獻(xiàn)：

［1］ "張連文，郭海鵬.貝葉斯網(wǎng)引論［M］.北京：科學(xué)出版社，2006. （Zhang Lianwen，Guo Haipeng.Introduction to Bayesian nets［M］.Beijing：Science Press，2006.）

［2］ Lou Chuyue，Li Xiangshun，Atoui M A.Bayesian network based on an adaptive threshold scheme for fault detection and classification［J］. Industrial and Engineering Chemistry Research ，2020， 59 （34）：15155-15164.

［3］ Taghi-Molla A，Rabbani M，Gavareshki M， et al .Safety improvement in a gas refinery based on resilience engineering and macro-ergonomics indicators：a Bayesian network-artificial neural network approach［J］. International Journal of System Assurance Engineering and Management ，2020， 11 （3）：641-654.

［4］ "黃詩雯，劉朝暉，羅凌云，等.融合行為和遺忘因素的貝葉斯知識追蹤模型研究［J］.計(jì)算機(jī)應(yīng)用研究，2021， 38 （7）：1993-1997. （Huang Shiwen，Liu Zhaohui，Luo Lingyun， et al .Research on Bayesian knowledge tracking model integrating behavior and forgetting factors［J］. Application Research of Computers ，2021， 38 （7）：1993-1997.）

［5］ 臧艷輝，趙雪章，席運(yùn)江.Spark框架下利用分布式NBC的大數(shù)據(jù)文本分類方法［J］.計(jì)算機(jī)應(yīng)用研究，2019， 36 （12）：3705-3708，3712. （Zang Yanhui，Zhao Xuezhang，Xi Yunjiang.Big data text classification method using distributed NBC under Spark framework［J］. Application Research of Computers ，2019， 36 （12）：3705-3708，3712.）

［6］ Chickering D M.Learning Bayesian networks is NP-complete［J］. Networks ，1996， 112 （2）：121-130.

［7］ Spirtes P，Glymour C，Scheines R.Causality from probability［M］.Berlin：Springer，1989.

［8］ Colombo D，Maathuis M H.Order-independent constraint-based causal structure learning［J］. The Journal of Machine Learning Research ，2014， 15 （1）：3741-3782.

［9］ Lam W，Bacchus F.Learning Bayesian belief networks：an approach based on the MDL principle［J］. Computational Intelligence ，1994， 10 （3）：269-293.

［10］ Liu Xuqing，Liu Xinsheng.Structure learning of Bayesian networks by continuous particle swarm optimization algorithms［J］. Journal of Statistical Computation and Simulation ，2018， 88 （9）：1-29.

［11］ Chen Xuewen，Anantha G，Lin Xiaotong.Improving Bayesian network structure learning with mutual information-based node ordering in the K2 algorithm［J］. IEEE Trans on Knowledge amp; Data Enginee-ring ，2008， 20 （5）：628-640.

［12］ Tsamardinos I，Brown L E，Aliferis C F.The max-min hill-climbing Bayesian network structure learning algorithm［J］. Machine Lear-ning ，2006， 65 （1）：31-78.

［13］ 周慕宇，劉以安，肖穎.K2算法在貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)中的改進(jìn)研究［J］.南京理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2020， 44 （3）：320-324. （Zhou Muyu，Liu Yian，Xiao Ying.Research on the improvement of K2 algorithm in Bayesian network structure learning［J］. Journal of Nanjing University of Science and Technology：Natural Science Edition ，2020， 44 （3）：320-324.）

［14］ Cooper G F，Herskovits E.A Bayesian method for the induction of probabilistic networks from data［J］. Machine Learning ，1992， 9 （4）：309-347.

［15］ 洪宇.基于信息論的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法研究［D］.上海：東華大學(xué)，2017. （Hong Yu.Research on Bayesian network structure learning algorithm based on information theory［D］.Shanghai：Donghua University，2017.）

［16］ "Qi Xiaolong，Shi Yinhuan，Wang Hao， et al .Grouping parallel Bayesian network structure learning algorithm based on variable ordering［C］//Proc of International Conference on Intelligent Data Engineering and Automated Learning.Cham：Springer，2016：405-415.

［17］ "趙高長，王欣，張仲華，等.基于MWST+T-K2結(jié)構(gòu)學(xué)習(xí)算法的貝葉斯分類器［J］.復(fù)旦學(xué)報(bào)：自然科學(xué)版，2017， 56 （1）：48-56. （Zhao Gaochang，Wang Xin，Zhang Zhonghua， et al .Bayesian classifier based on MWST+T-K2 structure learning algorithm［J］. Journal of Fudan University：Natural Science Edition ，2017， 56 （1）：48-56.）

［18］ "劉彬，王海羽，孫美婷，等.一種通過節(jié)點(diǎn)序?qū)?yōu)進(jìn)行貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)的算法［J］.電子與信息學(xué)報(bào)，2018， 40 （5）：1234-1241. （Liu Bin，Wang Haiyu，Sun Meiting， et al .An algorithm for Bayesian network structure learning through node order optimization［J］. Journal of Electronics amp; Information Technology ，2018， 40 （5）：1234-1241.）

［19］ 安寧，滕越，楊矯云，等.基于因果效應(yīng)的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)方法［J］.計(jì)算機(jī)應(yīng)用研究，2018， 35 （12）：3609-3613. （An Ning，Teng Yue，Yang Jiaoyun， et al .Bayesian network structure learning method based on causal effects［J］. Application Research of Computers ，2018， 35 （12）：3609-3613.）

［20］ 姚潔，朱響斌，宋新方，等.基于節(jié)點(diǎn)排序的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法［J］.計(jì)算機(jī)工程，2017， 43 （5）：317-321. （Yao Jie，Zhu Xiangbin，Song Xinfang， et al .Bayesian network structure learning algorithm based on node ordering［J］. Computer Engineering ，2017， 43 （5）：317-321.）

［21］ Gao Fan，Huang Da.A node sorting method for K2 algorithm in Bayesian network structure learning［C］//Proc of IEEE International Conference on Artificial Intelligence and Computer Applications.Piscataway，NJ：IEEE Press，2020：106-110.

［22］ 劉艷杰，李霞.基于貝葉斯網(wǎng)絡(luò)的學(xué)生成績預(yù)測［J］.山東理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2019， 33 （5）：75-78. （Liu Yanjie，Li Xia.Student performance prediction based on Bayesian network［J］. Journal of Shandong University of Technology：Natural Science Edition ，2019， 33 （5）：75-78.）

［23］ Behjati S，Beigy H.Improved K2 algorithm for Bayesian network structure learning［J］. Engineering Applications of Artificial Intelligence ，2020， 91 （5）：1-12.

［24］ Spirtes P，Glymour C.An algorithm for fast recovery of sparse causal graphs［J］. Social Science Computer Review ，1991， 9 （1）：62-72.

［25］ Yu Kui，Li Jiuyong，Liu Lin.A review on algorithms for constraint-based causal discovery［EB/OL］.（2016-11-24）.https：//arxiv.org/abs/1611.03977.

［26］ Lauritzen S L，Spiegelhalter D J.Local computations with probabilities on graphical structures and their application to expert systems［J］. Journal of the Royal Statistical Society：Series B ，1988， 50 （2）：157-194.

［27］ Beinlich I A，Suermondt H J，Chavez R M， et al. The ALARM monitoring system：a case study with two probabilistic inference techniques for belief networks［J］. Lecture Notes in Medical Informatics ，1989， 38 （1）：247-256.

［28］ Andrieu C，F(xiàn)reitas N D，Doucet A， et al. An introduction to MCMC for machine learning［J］. Machine Learning ，2003， 50 （1）：5-43.