基于案例推理的應急決策貝葉斯網建模方法

, ,

(哈爾濱工業大學 管理學院, 哈爾濱 150001)

0 引 言

突發事件尤其是突發自然災害事件的發生往往對人類社會造成巨大的危害.突發災害事件發生后第一時間的應對決策將直接影響事件的走向,然而,目前突發事件的應急決策主要是依靠人來完成,而且通常是面對繁雜無序的信息,具有極強的不確定性,應對效率不高.因此,突發事件的應急決策需要一種能夠融合各種信息、表征各種不確定性、效率較高的輔助決策工具.

由于貝葉斯網絡具有豐富的概率表達能力、不確定性問題的處理能力以及多源信息的融合能力[1-2],因此,將貝葉斯網絡技術應用于突發事件的應急決策,有利于輔助突發事件的應對決策,提高決策效率.Jensen[1]將貝葉斯網絡定義為一種可以表達一組隨機變量之間概率關系的概率圖模型.貝葉斯網絡的特點對突發事件應急決策具有如下優勢:

(1) 貝葉斯網絡能夠表示和融合多源信息;

(2) 貝葉斯網絡可以表達不確定性因果關系,這符合突發事件的不確定性的特點,有利于在不確定情況下做出決策;

(3) 貝葉斯網絡具有全局更新能力,可以隨著突發事件的發展而不斷更新各種信息;

(4) 貝葉斯網絡具有直觀的圖像表達能力,易于相關決策人員的使用.

(1) 基于領域專家的建模方法[3],即由領域專家確定貝葉斯網絡的結構和參數;

(2) 基于數據學習的建模方法[4],即使用一定的算法從數據中自動學習并生成貝葉斯網絡結構和參數;

(3) 基于知識庫的建模方法[5],即使用推理技術基于知識生成貝葉斯網絡的結構和參數.

突發事件的應急決策問題本身是一個復雜系統,各種系統變量相互影響,關系錯綜復雜,由此提高了貝葉斯網絡建模的難度.通常一個貝葉斯網絡模型只能解決一個或者幾個同類的問題,對于突發事件應急決策而言,由于突發事件本身的不確定性,事前不可能估計到所有不同類型的事件,因此針對每種事件都建立各自的貝葉斯網絡模型顯然不具有可行性.此外,突發事件應急決策往往具有較高的時間敏感性,因此,要求能夠盡可能縮短貝葉斯網絡的建模時間,而從無到有的傳統貝葉斯網絡建模方法的效率顯然無法較好地滿足突發事件應急決策這類復雜系統的要求.

針對以上問題,本文作者提出基于案例推理的應急決策貝葉斯網絡建模方法.該方法將歷史貝葉斯網絡模型作為案例存儲到案例庫中,當面臨新的突發事件應急決策問題時,利用相似度和偏離度兩個指標進行案例匹配,從而得到相同或者相似的案例,然后通過案例的融合、剪枝、修正等方法得到最終的貝葉斯網絡模型.本方法可以達到復用貝葉斯網絡模型的目的,從而提高了貝葉斯網絡的建模效率.

1 基于案例推理的建模流程

圖1 基于案例推理的應急決策貝葉斯網絡建模方法流程

案例推理是計算機人工智能領域發展比較成熟的一個技術分支.該方法的核心思想是:為了解決一個新問題,首先在案例庫中搜索相似的案例,從歷史相似問題中找尋新問題的解,得到初始解之后,通過一定的修改獲得新問題的最終解.基于該思想的應急決策貝葉斯網絡建模方法流程如圖1所示.

2 案例表示方法

案例表示通常包含案例整體情況的描述以及案例求解的描述.具體到本文中的應急決策貝葉斯網絡,案例表示應該包含貝葉斯網絡的結構和參數的描述.以圖2所示貝葉斯網絡模型為例,采用分層框架表示法,網絡框架為貝葉斯網絡模型的整體描述,節點框架為節點情況的描述.

lngdpit=β0+β1lngdpit-1+β2lntraffit+β3lntongit+β4lndianit+β5lnfdiit+β6lnfdiit×lntraffit×I(thr r)+β8lnfdiit×lntongit×I(thr r)+β10lnfdiit×lndianit×I(thr r)+β12rkit+β13cxit+β14lnexit+β15flit+μi+εit

圖2 貝葉斯網絡示例

網絡框架包含網絡名稱、問題描述、節點數目、邊數目等信息,節點框架包含節點名稱、節點描述、值域、父節點、子節點等信息.使用分層框架法表示圖2示例的結果如圖3所示.

3 案例匹配方法

案例匹配的思想是通過一定的算法,計算新案例和歷史案例的相似程度,以相似程度最大的案例作為匹配結果.由于貝葉斯網絡是通過變量之間的相互關系表示的,因此,對于同一領域的模型來說,案例之間的相似程度可以近似地通過計算相同節點的數目得到,即節點相似程度高的兩個模型具有相似的貝葉斯網絡結構.假設Cnew為新案例,Cold為歷史案例,引入相似度(S)和偏離度(D)兩個函數,即

圖3 示例的分層框架表示

(1)

其中,ns是兩個案例相同查詢節點的數目,n是新案例中查詢節點的數目,ms是兩個案例相同證據節點的數目,m是新案例中證據節點的數目,ωq為查詢節點的權重系數,ωe為證據節點的權重系數,且ωq+ωe=1.若歷史案例包含了新案例中所有的節點,則S(Cold,Cnew)=1;若歷史案例沒有包含新案例中的任何節點,則S(Cold,Cnew)=0.

圖4 貝葉斯網絡模型案例匹配流程

(2)

其中,R是歷史案例中的節點數目,Rd是存在于歷史案例中但不存在于新案例中的節點數目,且Rd=R-ns-ms.

貝葉斯網絡模型案例匹配的流程如圖4所示.

4 案例調整方法

4.1 網絡合并方法

進行案例匹配后,往往得到多個候選案例,此時需要將各個候選案例的貝葉斯網絡合并成為一個貝葉斯網絡.貝葉斯網絡的合并包括拓撲結構的合并以及節點條件概率分布的合并.

假設候選案例分別為C1和C2,將C2的貝葉斯網絡加入到C1中.則其拓撲結構合并的算法如下:

(1) 若案例C1和C2的貝葉斯網絡沒有相同節點,則無法合并;

(2) 若案例C1和C2的貝葉斯網絡有相同的節點,則遍歷C2的所有節點,從第一個與C1不同的節點開始,向上和向下搜索節點,直到搜索到一個與C1相同的節點,然后將兩個相同節點之間的路徑復制到C1中;

(3) 若合并后產生環路,則進行人工修正,否則完成合并.

貝葉斯網絡各節點條件概率分布的合并使用Noisy-or門近似計算[6].令節點X的父節點為Y={Y1,Y2,…,Yn},假設若Yi為Y中唯一取真值的變量,則X取真值的概率為:

(3)

其中,qi為事件Yi阻礙X為真的阻礙因子,所有父節點的阻礙作用是相互獨立的.當Y取值為y={y1,y2,…,yi},yi∈{0,1}時,令Ty={i:Yi=yes}表示Y取真值的元素的子集.則X的概率分布為:

(4)

4.2 網絡剪枝方法

設有貝葉斯網絡G,X、Y是其節點,現有查詢P(X|Y=y0),Y=y0代表證據,針對該查詢,基于文獻[7]的研究,提出確定冗余節點的方法.

圖5 貝葉斯網絡剪枝示意圖

定義節點集合X∪Y中包含以下元素:(1)X與Y之間所有有向路徑上的全部節點;(2)若X與Y之間沒有有向路徑,則從X與Y節點分別向上回溯,直到第一個共同祖先節點Z為止,路徑Y→Z→X上的所有節點.設An(X∪Y)為X∪Y中的節點及其祖先節點的集合.由此,得到兩個貝葉斯網絡剪枝規則:

規則1:若某節點不屬于任何一個An(X∪Yi),則可以刪除;

規則2:若某節點被Y節點d-分離于X節點,則可以刪除.

圖5為貝葉斯網絡剪枝示意圖,根據以上剪枝規則,給定圖5中(1)所示貝葉斯網絡,求P(E|B=b0)時,對(1)進行規則1剪枝得到(2),對(2)進行規則2剪枝得到(3).

5 案例仿真

突發事件應急決策時常常需要判斷是否能夠及時救援,即行動的及時性.假設案例庫中有4個有關救援行動及時性的歷史案例,如圖6所示.

現基于本研究所述方法建立新的貝葉斯網絡模型.假設當前突發事件應急決策已知證據包含:交通事故、物資充足、道路中斷、空運能力,需要判斷獲得及時救援的概率.令ωQ=0.60,ωE=0.40,閥值設為0.5,計算當前應急決策問題與圖6所示4個歷史案例的相似性,結果如表1所示.第一輪案例匹配后,候選案例為案例(4);案例(4)中缺少“交通事故”節點,因此再進行第二輪匹配,此時相似度公式中的n被重置為0,即不需要再考慮查詢節點,只需考慮證據節點,因此重置權重系數ωE=1,第二輪匹配后得到候選案例為案例(l).最終得到候選案例集為:{案例(4), 案例(1)}.

圖6 案例庫中歷史案例模型示意圖

歷史案例第一輪相似度偏離度第一輪相似度偏離度(1)0.200.601.000.80(2)0.800.5001.00(3)0.800.4001.00(4)0.900.33——

得到候選案例集后,對案例進行調整以提高其針對性和效率.首先對候選案例(1)和案例(4)進行案例合并,即將案例(1)加入到案例(4)中.合并后的貝葉斯網絡如圖7所示,其中加粗節點為證據節點,虛線節點為查詢節點.

案例合并后,對得到的貝葉斯網絡進行案例剪枝.根據剪枝規則1,案例(1)中的“人員傷亡”節點不屬于任何一個An(X∪Yi),因此該節點可以刪除;根據剪枝規則2,節點集合{交通事故、道路破壞、大車流量},被“道路中斷”節點d-分離于“及時救援”節點,因此該節點集合中的節點都可以刪除.經過剪枝后最終的貝葉斯網絡如圖8所示.

圖7 案例合并后的貝葉斯網絡

圖8 案例剪枝后的貝葉斯網絡

6 結 論

本文作者對應急決策貝葉斯網絡建模方法進行了研究,提出了基于案例推理的應急決策貝葉斯網絡建模方法.該方法基于歷史案例庫,通過相似度和偏離度兩個指標對歷史案例進行匹配并得到候選案例,最后通過案例合并和案例剪枝等方法對候選案例進行調整,得到最終的案例模型.文末的案例仿真結果表明：作者提出的基于案例推理的應急決策貝葉斯網絡建模方法沒有龐大的搜索空間,也不需要樣本數據,只需要提前收集歷史案例模型,與傳統貝葉斯網絡建模方法相比,本方法能夠復用歷史模型,提高了建模的效率.由于突發事件應急決策對時間非常敏感,通常要求迅速做出反應,因此,文中所提出的方法可以作為應急決策貝葉斯網絡建模的一個重要輔助方法,為突發事件應急決策爭取到寶貴的時間.

參考文獻:

[1] JENSEN F,NIELSEN T.Bayesian Networks and Decision Graphs [M].2nd Edition.New York: Springer Science Business Media,2007.

[2] BOZORGNIA,BERTERO.Earthquake Engineering-from Engineering Seismology to Performance-Based Engineering[J].Earthquake Spectra,2005,21(2):609-611.

[3] PARK H,CHO S.A modular design of Bayesian networks using expert knowledge: Context-aware home service robot[J].Expert Systems with Applications,2012,39(3):2629-2642.

[4] PLANT N,HOLLAND T.Prediction and assimilation of surf-zone processes using a Bayesian network.Part II: Inverse models[J].Coastal Engineering,2011,58(3):256-266.

[5] OUKHELLOU L,COME E,BOUILLAUT L,et al.Combined use of sensor data and structural knowledge processed by Bayesian network: Application to a railway diagnosis aid scheme[J].Transportation Research Part C: Emerging Technologies,2008,16(6):755-767.

[6] PEARL J.Probabilistic reasoning in intelligent systems: networks of plausible inference[M].San Mateo,CA:Morgan Kaufmann,Inc,1988.

[7] ZHANG N L,POOLE D.A simple approach to Bayesian network computations[C].Proceedings of the Tenth Biennial Canadian Artificial Intelligence Conference,Banff,1994: 171-178.