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

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

西安工程大學(xué) 電子信息學(xué)院，西安710048

1 引言

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

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

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

2.1 基本思想

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

2.2 算法描述

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

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

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

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

（1）初始化

（2）迭代計(jì)算

在式（2）濾波基礎(chǔ)上，利用轉(zhuǎn)移概率的校正，對(duì)第t+1 個(gè)時(shí)間片的隱變量進(jìn)行預(yù)測，即

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

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

圖2 第t+1 個(gè)時(shí)間片簡化的貝葉斯網(wǎng)絡(luò)圖

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

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

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

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

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

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

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

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

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

3 應(yīng)用仿真

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

本文仿真的模型如圖4 所示，其隱變量都有4 個(gè)狀態(tài)a、b、c、d，前7 個(gè)時(shí)間片中每個(gè)都有5 個(gè)觀測變量，其中，觀測變量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 個(gè)時(shí)間片中每個(gè)都有4 個(gè)觀測變量，其中，觀測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 的先驗(yàn)概率為P(X=a,b,c,d)=(0.3,0.3,0.3,0.1)，前7 個(gè)時(shí)間片的條件概率表如表1所示，后7個(gè)時(shí)間片的條件概率表如表2所示，狀態(tài)轉(zhuǎn)移概率如表3所示。

圖4 變結(jié)構(gòu)離散動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)

表1 前7個(gè)時(shí)間片條件概率表

表2 后7個(gè)時(shí)間片條件概率表

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

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

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

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

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