改進進化算法的貝葉斯網(wǎng)絡結(jié)構(gòu)學習及其應用

郭文強，毛玲玲，黃梓軒，肖秦琨，郭志高

(1.陜西科技大學 電子信息與人工智能學院，陜西 西安 710021;2.西安工業(yè)大學 電子信息工程學院，陜西 西安 710021;3.倫敦瑪麗女王大學 電子工程與計算機科學學院，倫敦 E1 4NS)

0 引言

貝葉斯網(wǎng)絡(Bayesian network，BN)是概率圖模型的重要研究方向，主要用于表征和解決不確定性問題[1]，并在故障溯源、醫(yī)療診斷和金融學習等領域得到了廣泛的應用[2]。BN研究主要由結(jié)構(gòu)學習、參數(shù)學習和推理3部分組成[3]，其中，結(jié)構(gòu)學習是BN構(gòu)建與應用的基礎與核心[4]。文獻[5]提出了最大最小爬山(max-min hill-climbing,MMHC)算法，通過條件獨立性構(gòu)建初始結(jié)構(gòu)，并結(jié)合爬山法學習貝葉斯網(wǎng)絡結(jié)構(gòu)，但算法存在學習耗時過長，且容易陷入局部最優(yōu)的問題。進化算法(evolutionary algorithms,EA)使用啟發(fā)式搜索策略能夠在一定程度上避免算法陷入局部最優(yōu)，主要通過種群中個體的選擇、重組和變異等基本操作實現(xiàn)優(yōu)化問題的求解。文獻[6]基于最大信息系數(shù)和微生物遺傳算法提出了一種新的貝葉斯網(wǎng)絡結(jié)構(gòu)學習，但耗時長，初始種群數(shù)目等先驗參數(shù)的確定缺乏客觀依據(jù)，存在一定的進化搜索盲目性等問題。

為解決上述問題，本文基于最大支撐樹(most weight supported tree，MWST)[7]和EA,提出了一種新的貝葉斯網(wǎng)絡結(jié)構(gòu)學習算法MWST-EA。該算法將結(jié)構(gòu)學習轉(zhuǎn)化為進化問題后，先建立最大支撐樹來得到種群中節(jié)點的父節(jié)點數(shù)目上限，采用本文設計的種群數(shù)目計算函數(shù)可以計算出種群數(shù)目；同時，采用條件獨立性測試獲得初始結(jié)構(gòu)來限制搜索空間。其次，采用設計的變異函數(shù)來控制基因突變，可以提高算法的局部搜索能力，防止陷入局部最優(yōu)。最終，通過種群的迭代操作學習出BN結(jié)構(gòu)。

糖尿病是一種不可治愈的慢性疾病，據(jù)國際糖尿病聯(lián)盟統(tǒng)計，截至2020年，全球糖尿病患病率約為9.3%[8]。目前糖尿病的發(fā)病機制尚未完全明確，多數(shù)學者認為在糖尿病病程發(fā)展的過程中，有多種因素對其產(chǎn)生作用，具有極大的不確定性。僅僅依靠醫(yī)生個人經(jīng)驗的診斷方式，容易出現(xiàn)病情診斷不及時的情況。將糖尿病與機器學習相結(jié)合來輔助醫(yī)生診斷，將在很大程度上提高診斷的智能性和實時性。文獻[9]運用正余弦優(yōu)化算法和神經(jīng)網(wǎng)絡相結(jié)合，為糖尿病的自動化診斷提供了一種智能方法。文獻[10]提出了一種遺傳算法模型用于糖尿病風險預測，輔助醫(yī)生進行早期干預。文獻[11]使用樸素貝葉斯(naive Bayes，NB)和支持向量機(support vector machine, SVM)等分類技術(shù)對糖尿病進行了預測。

本文將MWST-EA應用于加利福尼亞大學歐文學院分校David Aha博士搭建的UCI數(shù)據(jù)庫中的糖尿病數(shù)據(jù)集[12]上，建立貝葉斯網(wǎng)絡結(jié)構(gòu)分類模型，取得了較好的結(jié)果。

1 貝葉斯網(wǎng)絡結(jié)構(gòu)學習改進算法MWST-EA

在貝葉斯網(wǎng)絡結(jié)構(gòu)中，事件節(jié)點容易確定，但節(jié)點間的關(guān)系錯綜復雜難以確定，并且從數(shù)據(jù)中學習貝葉斯網(wǎng)絡結(jié)構(gòu)是一個難題。因此，本文提出了一種改進型進化算法MWST-EA，來確定貝葉斯網(wǎng)絡節(jié)點和節(jié)點間的依賴關(guān)系。

1.1 初始種群建立及個體父節(jié)點上限確定

進化算法的種群難以確定，且會影響算法的執(zhí)行效率和穩(wěn)定性。本文結(jié)合BN結(jié)構(gòu)特點設計了一種確定進化算法種群數(shù)目下限的函數(shù)，如式(1)所示：

(1)

其中：A為所需的種群數(shù)量；λ為變量概率分布的偏度，本文取1；d為BN模型中節(jié)點最大父節(jié)點個數(shù)；ζ為節(jié)點的最大狀態(tài)數(shù)；σ為BN模型的Kullback-Leibler(KL)距離，常取0.1；ζ為置信度，常取0.05。

設計的MWST-EA算法從完全無向圖開始，為縮小BN結(jié)構(gòu)的搜索空間，將條件獨立性測試應用于所有的節(jié)點之間。當兩個節(jié)點之間相互獨立，移除節(jié)點之間的邊，并據(jù)此得到初始結(jié)構(gòu)BN0。采用式(1)中的A作為初始種群大小。然后，對初始結(jié)構(gòu)中邊連接的兩個節(jié)點，隨機選擇邊狀態(tài)，以生成初始種群，并采用GR算法[13]對初始種群個體中產(chǎn)生的環(huán)即非法結(jié)構(gòu)進行修正，從而得到結(jié)構(gòu)BN1。

個體在交叉、變異的過程中，一個節(jié)點可能會存在多個父節(jié)點，顯然，初始父節(jié)點的個數(shù)影響著算法的收斂速度。本文利用互信息構(gòu)建MWST確定可能的個體父節(jié)點上限(individual parent node upper limit, IPI)數(shù)目，實現(xiàn)對種群中節(jié)點的父節(jié)點數(shù)量的限制，從而提高學習算法的效率?；バ畔14]表示兩個變量間的相互依賴關(guān)系，以任意兩個變量X、Y為例，互信息I(X，Y)為：

(2)

其中:p(X,Y)為變量X和Y的聯(lián)合概率;p(X)為變量X的概率;p(Y)為變量Y的概率。

MWST算法首先根據(jù)節(jié)點數(shù)據(jù)計算所有節(jié)點之間的互信息，通過把所有節(jié)點間的互信息從大到小進行排列，不斷選取互信息最大的邊加入最大生成樹，并且遍歷所有的節(jié)點，來完成MWST的建立。本文依據(jù)MWST中最大節(jié)點度，選擇具有最大節(jié)點度的節(jié)點作為算法中的個體父節(jié)點上限數(shù)目。圖1為個體父節(jié)點上限確定。以圖1a所示的經(jīng)典貝葉斯網(wǎng)絡中的ASIA網(wǎng)絡模型為例，根據(jù)MWST算法得出最大支撐樹(見圖1b)，可看出節(jié)點6具有最大節(jié)點度(見圖1c)，因此該網(wǎng)絡的IPI由節(jié)點6決定，其值為3。

(a) ASIA網(wǎng)絡模型 (b) 圖1a的MWST (c) 最大節(jié)點度圖1 個體父節(jié)點上限確定

1.2 MWST-EA新個體的產(chǎn)生及種群更新

1.2.1 評分函數(shù)及個體的選擇、交叉

本文采用BDeu評分函數(shù)對個體評分，以評分最高的個體作為精英個體x*。設X={X1,X2,…,Xn}是一組變量集合，D={D1,D2,…,Dn}是關(guān)于變量的樣本集合，G是關(guān)于變量集的BN結(jié)構(gòu)。假設數(shù)據(jù)集滿足獨立同分布條件假設，則BDeu評分如式(3)所示[15]：

(3)

為提高種群的局部尋優(yōu)能力，挑選評分高的一半個體進行交叉操作。均勻交叉算子的性能較為優(yōu)越[16]，利用均勻交叉算子組合生成新的個體，在搜索空間進行有效搜索，同時降低對種群有效模式的破壞概率。

1.2.2 精英集構(gòu)建及候選父節(jié)點數(shù)目限制

建立精英集e，以精英集中的每個個體作為種群的領導者，可以保證算法的尋優(yōu)能力。

(4)

其中：精英資格閾值β∈[0.5,1]；f(xk)為每個個體的評分；fbest為精英個體的評分。為了保持精英集的多樣性，以增加進化算法的搜索能力，β在每次種群更新時的變化依據(jù)DiG-SiRG算法[17]。

MWST-EA將個體具有可變狀態(tài)的邊定義為位點，位點中每組有值的組成部分被定義為等位基因。構(gòu)建邊頻次權(quán)重EFW=(wi,j)，wi,j對應于等位基因i∈{b,←,→}，即“無邊”、“反向邊”、“正向邊”出現(xiàn)的概率，j∈{1,2,…,L}(L為個體長度)。wi,j是精英集合中位置j處等位基因i出現(xiàn)的概率。

其中：當個體xk在位點j的等位基因等于i時，δ函數(shù)δ(xk,j=1)等于1。

有效地限制候選父節(jié)點數(shù)目，能加快BN結(jié)構(gòu)尋優(yōu)速度。采用父節(jié)點重復權(quán)重來選擇要刪除的邊以限制父節(jié)點數(shù)量。父節(jié)點重復權(quán)重是為每個節(jié)點定義的鍵值向量，其中鍵值由其父集中節(jié)點的索引給出，代表整個精英集中邊(父節(jié)點→節(jié)點)出現(xiàn)的概率，由個體的評分決定。為每個節(jié)點Xt填充與邊相關(guān)的概率(父(Xt)→Xt)，通過隨機排序為每個節(jié)點Xt構(gòu)建父節(jié)點重復權(quán)重，刪除出現(xiàn)概率最小的邊。ASIA網(wǎng)絡父節(jié)點限制如圖2所示。

圖2 ASIA網(wǎng)絡父節(jié)點限制

以圖1a的ASIA網(wǎng)絡模型為例，個體父節(jié)點上限設置為3，精英集由圖2中的3個精英集個體組成，對其他非精英個體的6節(jié)點進行父節(jié)點數(shù)目限制。要刪除的邊是在精英集中頻率出現(xiàn)最低的邊。個體1要刪除節(jié)點2至節(jié)點6的有向邊；個體2要刪除節(jié)點1至節(jié)點6的有向邊和節(jié)點5到節(jié)點6的有向邊；個體3滿足父節(jié)點數(shù)量為3的要求，所以不需要刪除節(jié)點。通過上述操作來保證每個個體中節(jié)點6參與進化、尋優(yōu)的父節(jié)點初始數(shù)目不超過3。

1.2.3 個體變異率函數(shù)

為避免算法陷入局部最優(yōu)，本文提出了一種新的變異函數(shù)來更新種群。通過上述EFW和精英集為種群中的每個個體xk的每個點j∈{1,2,…,L}計算個體變異率υi,j，如式(6)所示：

(6)

其中：wi,j為EFW的第(i,j)個元素；f(xk)為當前個體的評分；fbest為精英個體的評分；ε為一個極小正數(shù)，避免零概率。每個突變率都是基于邊在精英群體中的分布以及個體的評分函數(shù)來衡量的。

1.3 MWST-EA結(jié)構(gòu)學習算法步驟

本文提出的MWST-EA結(jié)構(gòu)學習算法步驟如下：

步驟1 設置算法最大迭代次數(shù)Iter，利用互信息建立最大支撐樹MWST，由最大節(jié)點度得到個體父節(jié)點上限數(shù)目IPI；采用式(1)計算種群數(shù)目。

步驟2 采用條件獨立性測試獲得初始結(jié)構(gòu)，生成初始種群P0，利用GR算法[13]修正種群中個體產(chǎn)生的非法結(jié)構(gòu)。

步驟3 依據(jù)式(3)對每個個體進行評分，挑選評分高的一半個體作為新種群P1進行均勻交叉操作，得到種群P2。

步驟4 對種群P2評分得到精英個體，將個體評分與P2代入式(4)構(gòu)建精英集e。

步驟5 依據(jù)個體評分函數(shù)和將精英集e代入式(5)構(gòu)建邊頻次權(quán)重。

步驟6 構(gòu)建父節(jié)點重復權(quán)重對種群P2中個體的父節(jié)點個數(shù)進行限制，得到種群P3。

步驟7 利用式(6)計算個體的突變率，對種群P3進行變異操作增加種群的多樣性，得到新種群P。

步驟8 若當本次迭代達到迭代次數(shù)Iter, 則輸出精英個體對應的BN結(jié)構(gòu)模型；否則轉(zhuǎn)至步驟3, 進行迭代計算。

2 MWST-EA結(jié)構(gòu)學習算法仿真實驗

實驗采用的編程環(huán)境為Windows10系統(tǒng)，處理器為Intel 酷睿i7 4712MQ(2.3 GHz)，8 G內(nèi)存，開發(fā)語言為MATLAB R2016b。為驗證MWST-EA的BN結(jié)構(gòu)學習性能，基于經(jīng)典BN模型-Alarm網(wǎng)[2]進行仿真實驗，Alarm網(wǎng)包含37個節(jié)點和46條邊。為體現(xiàn)本文算法的優(yōu)越性，在相同實驗條件下，與MMHC算法、傳統(tǒng)EA進行實驗對比及結(jié)果分析。

實驗中以Alarm網(wǎng)絡作為基礎，隨機生成數(shù)據(jù)容量分別為500、1 000、3 000和5 000的訓練數(shù)據(jù)樣本集，利用MWST-EA進行10次仿真實驗，結(jié)果取平均值以減少隨機性影響。實驗中設置種群迭代次數(shù)Iter為100，模型置信度ζ取0.05，精英資格閾值α為0.9。由式(1)計算得到種群數(shù)目為101。

表1為不同數(shù)據(jù)量下各算法學習Alarm網(wǎng)的BDeu平均評分對比，表2不同數(shù)量下為各算法學習Alarm網(wǎng)的平均運行時間。

由表1可知：MWST-EA在不同數(shù)據(jù)量的情況下，得到的BDeu評分優(yōu)于MMHC和傳統(tǒng)EA等算法。

表1 不同數(shù)據(jù)量下各算法學習Alarm網(wǎng)的BDeu平均評分

原因是MMHC算法搜索能力有限，而傳統(tǒng)EA啟發(fā)函數(shù)容易陷入局部最優(yōu)。本文提出了改進的變異函數(shù)來更新種群，可以有效防止進化過程陷入局部最優(yōu)，從而學出更好的BN模型。

由表2可知：MWST-EA運行時間明顯小于MMHC算法耗時，同時也優(yōu)于傳統(tǒng)EA。原因是MWST-EA采用了有效的種群數(shù)目和節(jié)點的個體父節(jié)點數(shù)目限定策略，縮小了算法的搜索空間，因此算法的執(zhí)行效率較高。

表2 不同數(shù)據(jù)量下各算法學習Alarm網(wǎng)的平均運行時間 s

將本文算法學習得到的網(wǎng)絡結(jié)構(gòu)與Alarm網(wǎng)原模型進行對比，計算得到網(wǎng)絡與標準網(wǎng)中相同邊的數(shù)量(samesides，SS)、增加邊的數(shù)量(added sides，AS)和丟失邊的數(shù)量(missing sides，MS)。Alarm學習得到的相同邊、增加邊和丟失邊數(shù)量統(tǒng)計如圖3所示。

圖3 Alarm網(wǎng)絡仿真對比

通過圖3對比可知：在Alarm網(wǎng)絡中，MWST-EA的相同邊個數(shù),在不同數(shù)據(jù)量下，均大于MMHC算法和傳統(tǒng)EA；MWST-EA的丟失邊、增加邊個數(shù)也小于其他算法。這是由于算法生成了較好的初始種群，用改進的變異函數(shù)來更新種群，提高了算法尋優(yōu)的能力。

綜上所述，MWST-EA結(jié)構(gòu)學習算法速度快于MMHC算法和傳統(tǒng)EA，且結(jié)構(gòu)尋優(yōu)能力更強。

3 MWST-EA在糖尿病診斷中的應用

3.1 實驗設置

本節(jié)實驗條件與上節(jié)實驗的設置相同，所采用的UCI數(shù)據(jù)庫中糖尿病數(shù)據(jù)集[12]包含520個實例信息，每個實例中包含17條屬性，對數(shù)據(jù)庫中的屬性做屬性標簽，其中，節(jié)點1設置年齡段19～35歲為狀態(tài)1，36～59歲為狀態(tài)2，60歲及以上為狀態(tài)3；節(jié)點2設置性別Male為狀態(tài)1,Female為狀態(tài)2；節(jié)點3～16中，Yes為狀態(tài)1，No為狀態(tài)2；節(jié)點17設置Positive為狀態(tài)1，Negetive為狀態(tài)2。數(shù)據(jù)集描述如表3所示。

表3 數(shù)據(jù)集描述

為了驗證本文提出的基于MWST-EA結(jié)構(gòu)學習算法的糖尿病診斷方法的有效性，采用十折交叉驗證法，將糖尿病數(shù)據(jù)庫中的468組數(shù)據(jù)用來訓練，52組數(shù)據(jù)用來測試。對10次實驗結(jié)果取平均值進行性能評價。

3.2 基于MWST-EA的糖尿病分類模型

采用MWST-EA，首先依據(jù)樣本中各節(jié)點的數(shù)據(jù)來計算互信息。圖4為糖尿病數(shù)據(jù)模型構(gòu)建。將互信息從大到小排序，遍歷所有的節(jié)點來確定糖尿病數(shù)據(jù)構(gòu)成的最大支撐樹模型，以此確定種群中每個個體的各節(jié)點的父節(jié)點數(shù)量上限數(shù)目，如圖4a所示；接下來，對所有節(jié)點之間進行獨立性測試，據(jù)此得到初始結(jié)構(gòu)用來構(gòu)建種群，其初始結(jié)構(gòu)如圖4b所示；依據(jù)3.1節(jié)參數(shù)設置，由式(1)計算得到種群數(shù)量為108，初始化種群之后，采用MWST-EA對種群進行多次迭代得到最優(yōu)的貝葉斯網(wǎng)絡結(jié)構(gòu)圖，如圖4c所示。

(a) 最大支撐樹模型 (b) 初始結(jié)構(gòu) (c) 糖尿病分類模型的BN結(jié)構(gòu)

由文獻[12，18]可知，糖尿病與性別、多尿、多飲、體質(zhì)量突然減輕、煩躁、肌肉僵硬、脫發(fā)等有關(guān)。由圖4可直觀地看到：糖尿病與節(jié)點2、3、4、5、11、14、15有直接依賴關(guān)系。由此可見，MWST-EA學到的模型與專家經(jīng)驗相吻合，具有較強可解釋性。

3.3 實驗分析

貝葉斯網(wǎng)絡結(jié)構(gòu)學習完成后，用最大期望(expectation maximization，EM)算法[19]對糖尿病分類模型進行參數(shù)學習。設置EM算法實驗迭代次數(shù)為5 000次，以得到BN模型的參數(shù)。在BN結(jié)構(gòu)和參數(shù)確定之后，利用BN對是否有糖尿病進行診斷。本文采用聯(lián)合樹精確推理算法[20]來進行BN推理。將推理結(jié)果與MMHC、傳統(tǒng)EA、NB[11]和SVM[11]等算法進行對比，實驗結(jié)果如表4所示。

由表4可以看出：SVM算法是目前4種算法中識別率最高的，但MWST-EA與SVM算法相比平均識別率提升了1.54%；與MMHC算法相比，MWST-EA性能提升了11.15%。本文的MWST-EA算法構(gòu)建出的BN模型結(jié)構(gòu)進行糖尿病診斷識別率有明顯提高。

表4 不同建模方法的實驗結(jié)果對比

為進一步驗證本文算法的性能，實驗對不同方法在十折交叉驗證情況下的時間進行對比，結(jié)果如圖5所示。從圖5中可以看出：本文算法的推理耗時與傳統(tǒng)EA和MMHC算法基本相同，相比NB算法和SVM算法的耗時則明顯降低。這表明MWST-EA算法構(gòu)建出的BN模型在推理速度方面性能優(yōu)良。

圖5 不同建模算法推理耗時對比

4 結(jié)束語

針對傳統(tǒng)進化算法學習貝葉斯網(wǎng)絡結(jié)構(gòu)存在收斂速度慢、局部搜索能力差以及種群數(shù)目確定缺乏依據(jù)的問題，本文提出了一種改進進化算法的BN結(jié)構(gòu)學習算法MWST-EA。該算法利用條件獨立性構(gòu)建初始結(jié)構(gòu)和設計的個體父節(jié)點上限數(shù)目函數(shù)共同作用，減少了搜索的盲目性，縮減了BN結(jié)構(gòu)的搜索空間，提升了算法的尋優(yōu)效率和收斂速度。采用改進的變異函數(shù)可避免算法陷入局部最優(yōu)。對比實驗結(jié)果表明了本文算法在BN結(jié)構(gòu)學習性能的優(yōu)越性，為智能系統(tǒng)的建模提供了一條新途徑。未來工作將考慮把進化算法與其他算法相結(jié)合，學習得到更優(yōu)的貝葉斯網(wǎng)絡結(jié)構(gòu)。