貝葉斯網絡推理分析的團樹傳播算法——以停車行為分析為例

李志瑤，宗 芳 ，張屹山b

(1.長春大學 機械工程學院，長春 130022;2.吉林大學 a.交通學院;b.商學院，長春 130021)

1 介紹

貝葉斯網絡(Bayesian network)又稱信度網絡，是在多元統(tǒng)計分析技術中的貝葉斯決策方法的基礎上發(fā)展起來的一種統(tǒng)計推斷方法，于1988年由Pearl首次提出。它將概率論與圖論相結合，能夠系統(tǒng)地描述隨機變量之間復雜的相關關系。貝葉斯網絡一般由三部分組成:①結點集X和結點間的有向連接集A;②由結點集和有向連接集組成的有向連接圖G;③每一個結點與其各父結點之間的條件概率組成的條件概率分布Θ。

近年來，貝葉斯網絡以其獨特的不確定性知識表達形式、豐富的概率表達能力、綜合先驗知識的增量學習特性，被廣泛應用于輔助智能決策、模式識別、醫(yī)療診斷等領域。在交通領域，主要應用于交通行為分析、交通事故研究、短時交通量預測等方面。例如，鮮于建川、雋志才等(2011)應用改進的K2算法和貝葉斯參數估計方法構造通勤出行方式和出行鏈模式選擇的局部貝葉斯網絡［1］。宗芳等(2010)建立了停車行為分析的貝葉斯網絡，并進行了停車收費等管理政策評價［2］。宗芳等(2011)運用相關性分析方法和K2算法建立了交通事故致因分析的貝葉斯網絡［3］。梁俊秀(2010)基于貝葉斯網絡的人的可靠性分析模型，對軌道交通系統(tǒng)司機的人因可靠性進行了定量分析，提出了基于Gibbs采樣的交通貝葉斯網絡近似概率推理算法，并進行交通流量的短時預測［4］。Janssens等(2006)結合應用決策樹和貝葉斯網絡描述人們的出行行為［5］。Hinsbergen等(2009)應用貝葉斯網絡和神經網絡預測出行時間［6］。但目前的研究主要注重貝葉斯網絡參數估計和結構學習方法，對推理算法還沒有足夠重視。本文將研究貝葉斯網絡的推理算法，并以停車行為分析的貝葉斯網絡推理為例進行實例分析。

2 團樹傳播算法

貝葉斯網絡推理是在給定一個貝葉斯網絡模型的情況下，根據已知條件，利用貝葉斯概率中的條件概率計算方法，計算出所感興趣的查詢結點發(fā)生的概率。應用貝葉斯網絡，可以根據網絡中任意一個或多個結點的值推斷其他結點的值。

貝葉斯網絡推理有4種模式:①預測推理，由原因推(預測)結論，即已知一定的原因(證據)，用貝葉斯網絡的推理計算，求出在該原因情況下結果發(fā)生的概率;②診斷推理，由結論推知原因，即已知結果，根據貝葉斯網絡推理，找到造成該結果發(fā)生的原因和計算原因發(fā)生的概率;③原因關聯推理，推理學習產生同一結果的不同原因之間的關系;④混合推理，上述幾種推理模式的結合。該推理方法可用于求解網絡中所有結點的概率分布。

現有的貝葉斯網絡推理算法可分為精確推理算法和近似推理算法。精確推理算法適用于結構簡單、網絡規(guī)模小的貝葉斯網絡推理。近似推理算法在不改變計算結果正確性的前提下降低了計算精度，從而簡化計算復雜性，主要用于網絡結構復雜、規(guī)模較大的貝葉斯網絡推理。

團樹傳播算法是最常用的一種精確推理算法，其推理結果精確，計算效率較高。其主要思想是將貝葉斯網絡轉化為團樹，然后通過定義在團樹上的消息傳遞過程來進行概率計算，完成對網絡的推理計算。其推理過程為:①確立推理函數;②在函數中添加證據函數;③向證據函數中輸入證據結點的值，即添加證據;④輸入想推理的結點編號或名稱;⑤運行推理函數，得到在父結點影響下待分析結點的概率分布情況。

團樹傳播算法可以在Matlab通過engine=jtree_inf_engine(bnet)函數，調用聯合樹推理引擎來實現，并可以進行停車行為分析的貝葉斯網絡的推理學習?；趫F樹傳播算法的貝葉斯推理計算流程如圖1所示。

圖1 基于團樹傳播算法的貝葉斯推理計算流程

以下將以文獻《基于貝葉斯網絡的停車行為分析》所建的貝葉斯網絡為例，詳細說明團樹傳播算法的實現過程。圖2為停車行為分析的貝葉斯網絡結構圖，表1為圖中各變量的取值。

圖2 停車行為分析的貝葉斯網絡及其端正圖

(1)構造端正圖。將貝葉斯結構中每個結點的不同父結點結合，即在它們之間加一條邊，然后去掉所有邊的方向，所得到的無向圖稱為端正圖。

表1 各影響變量的含義

(2)確定變量消元順序。應用最大勢搜索法確定變量消元順序。設ξ是一個包含n個結點的端正圖。最大勢搜索對ξ中所有結點按如下規(guī)則從大到小進行編號:在第i步中，選擇擁有最多已編號相鄰結點的未編號結點，將其編號為n－i+1。如果這樣的結點有多個，則任選其一。在所有的結點均被編號以后，按編號由小到大將結點排序，即得一個變量消元順序。應用最大勢搜索法確定停車行為分析的貝葉斯網絡的變量消元順序為 ＜sc，jf，f，j，l，s，g，m，k＞，確定消元順序后的端正圖如圖3。

圖3 應用最大勢搜索法確定消元順序后的端正圖

(3)構造團樹。構造團樹的方法主要有圖消元算法和BuildCT算法。其中，BuildCT(ξ，ρ)算法的基本思想是:從貝葉斯網G的端正圖ξ出發(fā)，按一定順序在ξ中進行變量消元;在消去變量X之前，先構造一個由X以及所有與X相鄰的變量組成的團;在消元過程結束后，把所產生的團以適當方式進行組織，得到一棵覆蓋G的團樹ζ。應用BuildCT算法，所得團樹如圖4所示。

圖4 停車行為分析的貝葉斯網絡的團樹

(4)設置推理證據。首先要確定推理中的證據變量，取值e。其后，設置推理中的查詢變量，其集合為Q。根據查詢變量的多少，推理過程可分為單查詢變量推理和多查詢變量推理，前者的查詢變量僅有一個，而后者是在前者的基礎上，利用團樹的共享推理機制，簡化計算過程后，推理得到多個查詢變量的結果。

推理過程即為計算在證據變量的影響下查詢變量的值的過程，即求解P(Q|E=e)。基本的計算公式為，

停車場類型和停車時長是兩項重要的停車決策，將其設置為貝葉斯網絡的查詢變量，則所對應的推理為多查詢變量推理。停車行為分析的貝葉斯網絡的結點序列為［m］［g］［k］［s］［j］［l］［jf］［f］［sc］。其中，查詢變量的集合Q=［l］［sc］，證據變量的集合evidence=［m］［g］［k］［s］［j］［jf］［f］。

根據文獻［7］，團樹傳播算法(簡記為CTP)的推理計算過程為:

輸入:G－一個貝葉斯網;ζ－一棵覆蓋G的團樹;

E－證據變量;e－證據變量的取值;Q－一個查詢變量。

輸出:P(Q|E=e)

1:利用G將ζ初始化，即將G中的概率分布函數存儲于ζ中的各結點處;

2:在ζ中的函數中，將證據變量E設置為其取值e;

3:在ζ中找出一個包含Q的團CQ作為樞紐;

4:for(每個與CQ相鄰的結點C)

5:調用子程序CollectMessage1(ζ，CQ，C)獲得一個函數;

6:end for

7:把上一步獲得的函數以及儲存在CQ處的函數相乘，得到C′Q的一個函數h(C′Q)，這里C′Q=CQE;

基于團樹傳播算法的多查詢變量的貝葉斯推理算法將在調用子程序CollectMessage的基礎上，引入另外兩個子程序SaveMessage和RetrieveMessage，進行團樹共享計算［7］。對于停車行為分析的貝葉斯網絡推理，最終將通過單查詢變量推理和多查詢變量推理，計算并輸出［l］［sc］兩個查詢變量的值。

3 停車行為推理分析

應用Matlab軟件的jtree_inf_engine模塊，停車行為分析的貝葉斯網絡的推理結果介紹如下。

3.1 預測推理

假設已知某人因工作于非高峰時段開公車出行，想知道此人所選擇停車場類型。證據為:

應用已建貝葉斯網絡推理，得此人選擇9個類型停車場的概率如表2所示。

表2 預測推理中某人選擇各類型停車場的概率

分析表2中數據可知，此人選擇居住小區(qū)停車場的可能性最大，其次是單位大院停車場?？梢哉J為，如選擇居住小區(qū)停車場，則此人的出行目的為工作出行中的回家;而如果選擇單位大院停車場，則出行目的為工作出行中的上班或上學。

3.2 診斷推理

假設已知某人選擇在2元/小時的停車場停放車輛5小時，想知道停車場類型和此人的出行目的。根據已建貝葉斯網絡結構分析已知和待求各變量之間的推理順序，知此問題為診斷推理方式。證據為:

應用已建貝葉斯網絡推理，此人的出行目的分布如表3所示。

表3 診斷推理中某人的出行目的分布

分析表3中結果可知，此人的出行目的為生活出行的可能性大。應用已建貝葉斯網絡推理，此人選擇9個類型停車場的概率如表4所示。

表4 診斷推理中某人選擇各類型停車場的概率

分析表4中結果可知，此人選擇公建配建停車場的可能性最大，其次是路外停車場，這與停車時間和出行目的也比較相符。

3.3 原因關聯推理

例如，在停車行為分析的貝葉斯網絡中，停車場類型和停車費率是產生停車時長的直接原因。下面應用原因關聯推理方法推理學習當停車時長為3小時及以下的短時停車時，停車場類型和停車費率之間的相互影響關系。證據為停車時長sc=1］。所得結果見表5。

表5 停車場類型與停車費率之間的關系

可見，停車場類型與停車費率之間的相關性較大。具體來說，占道停車(劃線)、公建配建停車場收費較高，其次是立交橋下停車場、路外停車場、居住小區(qū)停車場，免費的停車場類型主要有臨時路邊、占道停車(未劃線)、單位大院停車場和其他。這些推理分析結果與目前的停車管理現狀吻合。

3.4 混合推理

假設已知某人開車購物，選擇在2元/小時的停車場停放車輛5小時，則想知道此人開的車是公車還是私車，選擇何種停車場。證據為:evidence==3］［停車時長sc=2］。

應用已建貝葉斯網絡推理，得公車/私車的比例為0.1311:0.8689。可知，此人開私家車的概率大。停車場類型分布如表6所示。

表6 混合推理中某人選擇各類型停車場的概率

分析結果可知，此人選擇公建配建停車場的可能性最大，其次是路外停車場。與診斷推理案例相比，此例在新增出行目的為購物這樣的證據下，選擇公建配建停車場和路外停車場的概率有所增加。

4 結論

本文以貝葉斯網絡的推理方法為主要研究內容，重點闡述了團樹推理方法的基本過程和算法，以Matlab軟件的engine=jtree_inf_engine(bnet)模塊為主要工具，以停車行為分析的貝葉斯網絡為例，進行了包括預測、診斷、原因關聯和混合的全模式推理，并根據推理結果分析總結了居民的停車行為特征。研究結果表明，貝葉斯網絡及團樹推理方法可以應用于分析停車決策與停車者的個人屬性、出行屬性、停車屬性等因素間的因果作用關系，以利于理解居民的停車決策特征。在此基礎上還可以進一步診斷城市停車問題，提出和評價路內停車收費等管理政策的實施效果。

［1］鮮于建川，雋志才，朱泰英.基于貝葉斯網絡的出行選擇行為分析［J］.交通運輸系統(tǒng)工程與信息，2011，11(5):167－172.

［2］宗芳，張慧永，雋志才.基于貝葉斯網絡的停車行為分析［J］.系統(tǒng)工程理論實踐，2010，30(5):948－954.

［3］許洪國，張慧永，宗芳.交通事故致因分析的貝葉斯網絡建模［J］.吉林大學學報:工學版，2011，41(增刊1):89－94.

［4］梁俊秀.基于貝葉斯網絡的軌道交通系統(tǒng)人因可靠性定量分析方法研究［D］.北京:北京交通大學，2010.

［5］Janssens D.，Wets G.，Brijs T.，Vanhoof K.，Arentze T.，Timmermans H.Integrating Bayesian networks and decision trees in a sequential rule-based transportation model［J］.European Journal of Operational Research，2006(175):16－34.

［6］Hinsbergen C.P.IJ.van，Lint J.W.C.van，Zuylen H.J.van.Bayesian committee of neural networks to predict travel times with confidence intervals［J］.Transportation Research Part C，2009(17):498－509.

［7］張連文，郭海鵬.貝葉斯網引論［M］.北京:科學出版社，2006.