一步預測的SVDDBN缺失數(shù)據(jù)插補算法

陳海洋，劉喜慶，環(huán)曉敏

西安工程大學 電子信息學院，西安710048

1 引言

貝葉斯網(wǎng)絡是用于描述變量間依賴關系的圖論模型，具有很強的處理不確定性問題的能力，被廣泛應用于各大領域，如決策支持[1-2]、風險評估[3-4]、故障診斷[5]等。傳統(tǒng)的動態(tài)貝葉斯網(wǎng)絡只用于解決穩(wěn)態(tài)過程中的不確定性問題，為了解決非穩(wěn)態(tài)過程中的不確定性問題，文獻[6]提出了變結構動態(tài)貝葉斯網(wǎng)絡（Structure-Variable Dynamic Bayesian Networks，SVDBN）的概念，從廣義的角度上看，傳統(tǒng)的動態(tài)貝葉斯網(wǎng)絡是變結構動態(tài)貝葉斯網(wǎng)絡的一個特例，即適用于變結構動態(tài)貝葉斯網(wǎng)絡的算法同樣適用于傳統(tǒng)的動態(tài)貝葉斯網(wǎng)絡，反之則不然，因此變結構動態(tài)貝葉斯網(wǎng)絡更具普適性。而在實際應用中，傳感器不能一直持續(xù)獲取目標特征信息，從而使得不同時間片上觀測節(jié)點的證據(jù)信息可能發(fā)生隨機缺失，這些缺失數(shù)據(jù)把不確定性引入到網(wǎng)絡中，影響了網(wǎng)絡推理的可靠性，降低了網(wǎng)絡推理結果的置信度，因此必須對觀測節(jié)點的缺失數(shù)據(jù)進行正確、有效的處理。

常見的數(shù)據(jù)缺失處理法可分為兩大類：刪除法[7-8]和數(shù)據(jù)插補法[9-14]。刪除法就是直接刪去缺失的變量或者樣本，將剩余樣本看作“完整”的數(shù)據(jù)集；數(shù)據(jù)插補法就是借助統(tǒng)計學知識，利用與缺失數(shù)據(jù)相關的信息為缺失值匹配合適的預測值，再用預測值替換缺失值。刪除法會造成有用信息或隱含信息的損失，不利于網(wǎng)絡推理，因此本文采用數(shù)據(jù)插補法。常見的數(shù)據(jù)插補法有均值插補[9]、EM 迭代[10-11]、回歸插補[12-13]、貝葉斯估計法[14]等。其中，均值插補法就是利用變量中的非缺失數(shù)據(jù)均值來代替缺失數(shù)據(jù)，此方法易低估數(shù)據(jù)變異程度；EM迭代法又被稱為期望值最大化法，E步用來尋找期望值代替缺失值，M 步通過最大化對數(shù)似然函數(shù)來計算參數(shù)的值，兩步輪流迭代直至收斂，此方法收斂較慢且計算復雜度高；回歸插補法是利用數(shù)學方法建立因變量（缺失變量）與自變量（非缺失變量）之間的函數(shù)關系式，用因變量的估計值代替缺失值，此方法易錯估隨機誤差與標準差；貝葉斯估計法是一種基于完善的貝葉斯理論，將先驗分布與似然函數(shù)相結合對缺失數(shù)據(jù)進行預測的方法，所需的積分運算往往比較困難。本文為了克服變結構離散動態(tài)貝葉斯網(wǎng)絡在結構、參數(shù)已知，部分觀測數(shù)據(jù)缺失導致推理精度低的缺陷，提出了一步預測的SVDDBN缺失數(shù)據(jù)插補算法。該算法以貝葉斯理論為基礎，結合信息前向傳播規(guī)律，對缺失數(shù)據(jù)進行插補，并與經(jīng)典的均值插補法、EM算法以及回歸插補法進行了比較，仿真實驗驗證了所提出算法的有效性。

2 一步預測缺失數(shù)據(jù)插補算法

2.1 基本思想

假設變結構離散動態(tài)貝葉斯網(wǎng)絡有T 個時間片，第t(t=1,2,…,T)個時間片的貝葉斯網(wǎng)絡結構為BNt，包含一個隱藏節(jié)點Xt和kt個觀測節(jié)點，由于放寬了傳統(tǒng)動態(tài)貝葉斯網(wǎng)絡的齊次性假設，所以不同的時間片BNt也可能會不同，即各觀測節(jié)點間的依賴關系可能會不同，因此適用于傳統(tǒng)靜態(tài)貝葉斯網(wǎng)絡的貝葉斯估計方法不能直接應用于變結構離散動態(tài)貝葉斯網(wǎng)絡的缺失數(shù)據(jù)處理，需要綜合考慮多個時間片之間的關系和可變的節(jié)點依賴關系。雖然變結構離散動態(tài)貝葉斯網(wǎng)絡數(shù)據(jù)結構比較復雜，但其依然遵從信息傳播規(guī)律，即信息可以沿貝葉斯網(wǎng)絡時間軸向后傳播，前面時間片的證據(jù)信息會影響到后面的時間片[15]，以此思想為基礎，利用前t 個時間片的證據(jù)信息對第t+1 個時間片缺失的數(shù)據(jù)信息進行一步預測，預測值用來替換缺失數(shù)據(jù)，最終得到完整的數(shù)據(jù)集。算法插補過程如圖1所示，其推導過程主要分為三步：第一步，推導出第t 個時間片的濾波公式。假定前t 個時間片的觀測數(shù)據(jù)已經(jīng)完備，即缺失數(shù)據(jù)已經(jīng)得到插補（插補過的數(shù)據(jù)節(jié)點用虛線灰底表示，如Y21），利用直接觀測到的數(shù)據(jù)（用實線白底表示）和插補數(shù)據(jù)組合成的“混合”證據(jù)信息推導出隱變量Xt的后驗概率，即對當前時間片的隱變量狀態(tài)進行估計，此步被稱為濾波。第二步，對第t+1 個時間片隱變量的狀態(tài)進行預測。通過第一步求得的濾波公式和轉移概率的校正，可以估計出第t+1 個時間片隱變量狀態(tài)的估計值。第三步，對觀測節(jié)點的缺失數(shù)據(jù)進行一步預測。若第t+1 個時間片的觀測數(shù)據(jù)存在缺失（缺失數(shù)據(jù)節(jié)點用虛線表示，如Ynt+1），將此缺失數(shù)據(jù)的觀測節(jié)點看作查詢變量，求得此觀測節(jié)點的后驗概率，即一步預測值，用此預測值作為缺失數(shù)據(jù)插補值，這樣就得到了第t+1個時間片上完整的證據(jù)信息。在這三步中，轉移概率將不同時間片的貝葉斯網(wǎng)絡關聯(lián)起來，得到了濾波信息和含有缺失數(shù)據(jù)時間片的隱藏變量的狀態(tài)估計值，然后通過將相關節(jié)點按照與所求觀測變量的依賴關系劃分成不同集合的方法，處理了各節(jié)點間復雜多變的依賴關系，最后利用變量消元法給出具有一般性的一步預測公式。

2.2 算法描述

圖1 一步預測缺失數(shù)據(jù)插補算法的插補過程示意圖

初始化變結構離散動態(tài)貝葉斯網(wǎng)絡各個參數(shù)值，即先驗信息值、條件概率表和狀態(tài)轉移表。假設隱變量Xt有mt個狀態(tài)，即{1,2,…,mt}，觀測變量(n=1,2,…,kt)表示第t 個時間片的第n 個觀測變量，觀測值為。下面按照時間序列t 對各貝葉斯網(wǎng)絡進行缺失數(shù)據(jù)插補，具體算法描述如下：

先檢查第一個時間片的觀測數(shù)據(jù)是否發(fā)生缺失，若缺失，則用缺失變量的狀態(tài)數(shù)倒數(shù)值進行插補。例如，當變量有兩個狀態(tài)時，每個狀態(tài)的預測值為0.5。第一個時間片插補完成后，檢查下一個時間片是否發(fā)生數(shù)據(jù)缺失，若缺失，可由式（6）給出一步預測值。具體推到過程如式（1）至（6）所示。

定義αt(i)為第t(t ≥2)個時間片的濾波，表示當前所有的觀測證據(jù)信息對當前時刻的隱藏變量狀態(tài)的估計，則t=1,2,…,T，其中表示第t 個時間片上所有的觀測數(shù)據(jù)。利用已知的參數(shù)信息，通過初始化和迭代計算可以得到αt(i)的遞推公式。

（1）初始化

（2）迭代計算

在式（2）濾波基礎上，利用轉移概率的校正，對第t+1 個時間片的隱變量進行預測，即

在式（3）的狀態(tài)估計的基礎上，將此估計轉換為對該時間片上的第n 個觀測變量缺失數(shù)據(jù)的預測。為了便于推導第t+1 個時間片觀測節(jié)點的缺失值，需將第t+1個時間片的觀測節(jié)點重新編號，這里表示為，其中表示的是與缺失節(jié)點有依賴關系的觀測節(jié)點集，表示的是與觀測節(jié)點及相互獨立的觀測節(jié)點集。根據(jù)圖2 所示的簡化貝葉斯網(wǎng)絡圖，列寫出概率分布函數(shù)集合，利用變量消元法得出缺失變量的預測值，由于觀測節(jié)點集在推導的預測值時不含有證據(jù)信息，所以不會對其推導產生影響，故可省去。由于變量之間的依賴關系不明確，概率分布函數(shù)集合一般寫為：

再消去變量Xt+1，最終得到變量的后驗概率，即所求的一步預測值，其公式表示為：

圖2 第t+1 個時間片簡化的貝葉斯網(wǎng)絡圖

從數(shù)據(jù)處理的方式來看，本文提出的算法是一種在線數(shù)據(jù)插補算法，即每獲得一個新的含有缺失值的時間片，就對其進行數(shù)據(jù)插補。從利用證據(jù)的情況上來看，它既利用了直接觀測到的證據(jù)信息，也利用了插補的證據(jù)信息，即是一種利用“混合”證據(jù)信息對缺失數(shù)據(jù)進行插補的方法。相比于傳統(tǒng)插補算法，本文算法結合了貝葉斯理論知識，利用了貝葉斯網(wǎng)絡結構和網(wǎng)絡節(jié)點參數(shù)，增強了已知信息的利用率，計算量也相對較少，并且能夠解決穩(wěn)態(tài)與非穩(wěn)態(tài)條件下的動態(tài)貝葉斯網(wǎng)絡數(shù)據(jù)缺失問題，具有一般性。

下面給出一步預測缺失數(shù)據(jù)插補算法的實現(xiàn)步驟：

步驟1 給定變結構離散動態(tài)貝葉斯網(wǎng)絡的初始狀態(tài)概率、條件概率和轉移概率，設定其時間片數(shù)為T。第t 個時間片有kt個觀測節(jié)點，令n=1，t=1。

步驟2 若第一個時間片上的第n 個觀測變量Y n1含有缺失數(shù)據(jù)，則用觀測變量Y n1 的狀態(tài)數(shù)倒值對缺失數(shù)據(jù)進行插補；若不含有缺失數(shù)據(jù)，則轉入步驟3。

步驟3 n=n+1，若n ≤kt轉入步驟2；否則，取n=1，t=t+1，轉入步驟4。

步驟4 若第t 個時間片的第n個觀測變量Y nt 含有缺失數(shù)據(jù)，則轉入步驟5；若不含有缺失數(shù)據(jù)，則轉入步驟6。

步驟5 由式（1）到式（5）得到式（6），對缺失數(shù)據(jù)進行插補，插補完成后，轉入步驟6。

步驟6 n=n+1，如果n ≤kt轉入步驟4；否則，取n=1，t=t+1，若t ≤T，則轉入步驟4；否則結束。

一步預測缺失數(shù)據(jù)插補算法的流程圖如圖3所示。

3 應用仿真

圖3 一步預測缺失數(shù)據(jù)插補算法流程圖

本文仿真的模型如圖4 所示，其隱變量都有4 個狀態(tài)a、b、c、d，前7 個時間片中每個都有5 個觀測變量，其中，觀測變量Y1有3種狀態(tài)：e、f、g，觀測變量Y2有2種狀態(tài)：h、i，觀測變量Y3有3種狀態(tài)：j、k、l，觀測變量Y4有3種狀態(tài)：m、n、o，觀測變量Y5有2種狀態(tài)：p、q；后7 個時間片中每個都有4 個觀測變量，其中，觀測h、i，觀測變量Y3有3種狀態(tài)：j、k、l，觀測變量Y4有3變量Y1有3種狀態(tài)：e、f、g，觀測變量Y2有2種狀態(tài)：種狀態(tài)：m、n、o。隱變量X 的先驗概率為P(X=a,b,c,d)=(0.3,0.3,0.3,0.1)，前7 個時間片的條件概率表如表1所示，后7個時間片的條件概率表如表2所示，狀態(tài)轉移概率如表3所示。

圖4 變結構離散動態(tài)貝葉斯網(wǎng)絡

表1 前7個時間片條件概率表

表2 后7個時間片條件概率表

表3 狀態(tài)轉移概率

表4～8為圖4仿真模型的觀測數(shù)據(jù)隨機缺失9.5%、20.6%、30.2%、39.7%、46.0%時的數(shù)據(jù)，利用一步預測缺失數(shù)據(jù)插補算法、均值插補法、EM算法以及回歸插補法對缺失數(shù)據(jù)插補得到完整數(shù)據(jù)后，用文獻[16]提出的變結構離散動態(tài)貝葉斯網(wǎng)絡推理算法進行推理，得到前7個時間片的隱變量a 狀態(tài)概率最高，后7個時間片隱變量b 狀態(tài)概率最高。圖5（a）、（b）、（c）、（d）、（e）分別是不同數(shù)據(jù)缺失率下各插補方法插補后，推理得到隱變量狀態(tài)的最高概率。

從圖5各分圖對比可以看出，隨著數(shù)據(jù)缺失率的增加，各時間片隱變量的狀態(tài)最高概率整體呈下降趨勢，即貝葉斯網(wǎng)絡推理結果的置信度會隨著缺失數(shù)據(jù)的增加而降低，貝葉斯網(wǎng)絡的不確定性也會隨之增大。此外，各插補方法各時間片的狀態(tài)最高概率大多大于未插補的狀態(tài)最高概率，即本文算法和其他經(jīng)典插補方法都能降低缺失數(shù)據(jù)帶來的影響。在缺失率為9.5%時，數(shù)據(jù)缺失影響較小，各插補方法的狀態(tài)最高概率相近；在缺失率為20.6%、30.2%時，本文算法、EM算法和回歸插補法的狀態(tài)最高概率相近且大多高于均值算法，即本文算法、EM算法和回歸法的插補效果較優(yōu)，均值法的插補效果較差；在缺失率為39.7%、46.0%時，本文算法有65%時間片的狀態(tài)最高概率高于EM 算法，68%時間片的狀態(tài)最高概率高于回歸插補法，93%時間片的狀態(tài)最高概率高于均值插補法，即在缺失率較高時，EM算法和回歸法的可利用的信息少于本文算法，使得其部分插補值逐漸偏離標準值，造成部分隱變量的狀態(tài)最高概率偏差較大，而本文算法則較為穩(wěn)定，其優(yōu)越性得到充分體現(xiàn)。

表4 觀測數(shù)據(jù)缺失9.5%

表5 觀測數(shù)據(jù)缺失20.6%

表6 觀測數(shù)據(jù)缺失30.2%

表7 觀測數(shù)據(jù)缺失39.7%

表8 觀測數(shù)據(jù)缺失46.0%

4 總結

圖5 前7個時間片狀態(tài)a 的概率，后7個時間片狀態(tài)b 的概率

本文針對變結構離散動態(tài)貝葉斯網(wǎng)絡發(fā)生觀測數(shù)據(jù)缺失導致其推理結果的精確度和可靠性差的問題，提出了一步預測的SVDDBN缺失數(shù)據(jù)插補算法。通過不同缺失率下與經(jīng)典插補方法的比較，得出本文算法主要有以下特點：（1）只利用部分證據(jù)信息對缺失信息進行預測，計算量較?。唬?）缺失數(shù)據(jù)的插補值相對準確有效，提高了推理算法的精確性，達到了數(shù)據(jù)插補的目的；（3）在觀測數(shù)據(jù)難以獲得、樣本數(shù)據(jù)缺失較多的情況，如臨床醫(yī)療、作戰(zhàn)指揮等，本文算法的優(yōu)越性更能得到充分體現(xiàn)。同時本文算法也存在缺陷，需要依賴初始先驗概率、條件概率等數(shù)據(jù)信息。