貝葉斯網(wǎng)絡(luò)推理分析的團(tuán)樹(shù)傳播算法——以停車行為分析為例

李志瑤，宗 芳 ，張屹山b

(1.長(zhǎng)春大學(xué) 機(jī)械工程學(xué)院，長(zhǎng)春 130022;2.吉林大學(xué) a.交通學(xué)院;b.商學(xué)院，長(zhǎng)春 130021)

1 介紹

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

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

2 團(tuán)樹(shù)傳播算法

貝葉斯網(wǎng)絡(luò)推理是在給定一個(gè)貝葉斯網(wǎng)絡(luò)模型的情況下，根據(jù)已知條件，利用貝葉斯概率中的條件概率計(jì)算方法，計(jì)算出所感興趣的查詢結(jié)點(diǎn)發(fā)生的概率。應(yīng)用貝葉斯網(wǎng)絡(luò)，可以根據(jù)網(wǎng)絡(luò)中任意一個(gè)或多個(gè)結(jié)點(diǎn)的值推斷其他結(jié)點(diǎn)的值。

貝葉斯網(wǎng)絡(luò)推理有4種模式:①預(yù)測(cè)推理，由原因推(預(yù)測(cè))結(jié)論，即已知一定的原因(證據(jù))，用貝葉斯網(wǎng)絡(luò)的推理計(jì)算，求出在該原因情況下結(jié)果發(fā)生的概率;②診斷推理，由結(jié)論推知原因，即已知結(jié)果，根據(jù)貝葉斯網(wǎng)絡(luò)推理，找到造成該結(jié)果發(fā)生的原因和計(jì)算原因發(fā)生的概率;③原因關(guān)聯(lián)推理，推理學(xué)習(xí)產(chǎn)生同一結(jié)果的不同原因之間的關(guān)系;④混合推理，上述幾種推理模式的結(jié)合。該推理方法可用于求解網(wǎng)絡(luò)中所有結(jié)點(diǎn)的概率分布。

現(xiàn)有的貝葉斯網(wǎng)絡(luò)推理算法可分為精確推理算法和近似推理算法。精確推理算法適用于結(jié)構(gòu)簡(jiǎn)單、網(wǎng)絡(luò)規(guī)模小的貝葉斯網(wǎng)絡(luò)推理。近似推理算法在不改變計(jì)算結(jié)果正確性的前提下降低了計(jì)算精度，從而簡(jiǎn)化計(jì)算復(fù)雜性，主要用于網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜、規(guī)模較大的貝葉斯網(wǎng)絡(luò)推理。

團(tuán)樹(shù)傳播算法是最常用的一種精確推理算法，其推理結(jié)果精確，計(jì)算效率較高。其主要思想是將貝葉斯網(wǎng)絡(luò)轉(zhuǎn)化為團(tuán)樹(shù)，然后通過(guò)定義在團(tuán)樹(shù)上的消息傳遞過(guò)程來(lái)進(jìn)行概率計(jì)算，完成對(duì)網(wǎng)絡(luò)的推理計(jì)算。其推理過(guò)程為:①確立推理函數(shù);②在函數(shù)中添加證據(jù)函數(shù);③向證據(jù)函數(shù)中輸入證據(jù)結(jié)點(diǎn)的值，即添加證據(jù);④輸入想推理的結(jié)點(diǎn)編號(hào)或名稱;⑤運(yùn)行推理函數(shù)，得到在父結(jié)點(diǎn)影響下待分析結(jié)點(diǎn)的概率分布情況。

團(tuán)樹(shù)傳播算法可以在Matlab通過(guò)engine=jtree_inf_engine(bnet)函數(shù)，調(diào)用聯(lián)合樹(shù)推理引擎來(lái)實(shí)現(xiàn)，并可以進(jìn)行停車行為分析的貝葉斯網(wǎng)絡(luò)的推理學(xué)習(xí)?；趫F(tuán)樹(shù)傳播算法的貝葉斯推理計(jì)算流程如圖1所示。

圖1 基于團(tuán)樹(shù)傳播算法的貝葉斯推理計(jì)算流程

以下將以文獻(xiàn)《基于貝葉斯網(wǎng)絡(luò)的停車行為分析》所建的貝葉斯網(wǎng)絡(luò)為例，詳細(xì)說(shuō)明團(tuán)樹(shù)傳播算法的實(shí)現(xiàn)過(guò)程。圖2為停車行為分析的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)圖，表1為圖中各變量的取值。

圖2 停車行為分析的貝葉斯網(wǎng)絡(luò)及其端正圖

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

表1 各影響變量的含義

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

圖3 應(yīng)用最大勢(shì)搜索法確定消元順序后的端正圖

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

圖4 停車行為分析的貝葉斯網(wǎng)絡(luò)的團(tuán)樹(shù)

(4)設(shè)置推理證據(jù)。首先要確定推理中的證據(jù)變量，取值e。其后，設(shè)置推理中的查詢變量，其集合為Q。根據(jù)查詢變量的多少，推理過(guò)程可分為單查詢變量推理和多查詢變量推理，前者的查詢變量?jī)H有一個(gè)，而后者是在前者的基礎(chǔ)上，利用團(tuán)樹(shù)的共享推理機(jī)制，簡(jiǎn)化計(jì)算過(guò)程后，推理得到多個(gè)查詢變量的結(jié)果。

推理過(guò)程即為計(jì)算在證據(jù)變量的影響下查詢變量的值的過(guò)程，即求解P(Q|E=e)?；镜挠?jì)算公式為，

停車場(chǎng)類型和停車時(shí)長(zhǎng)是兩項(xiàng)重要的停車決策，將其設(shè)置為貝葉斯網(wǎng)絡(luò)的查詢變量，則所對(duì)應(yīng)的推理為多查詢變量推理。停車行為分析的貝葉斯網(wǎng)絡(luò)的結(jié)點(diǎn)序列為［m］［g］［k］［s］［j］［l］［jf］［f］［sc］。其中，查詢變量的集合Q=［l］［sc］，證據(jù)變量的集合evidence=［m］［g］［k］［s］［j］［jf］［f］。

根據(jù)文獻(xiàn)［7］，團(tuán)樹(shù)傳播算法(簡(jiǎn)記為CTP)的推理計(jì)算過(guò)程為:

輸入:G－一個(gè)貝葉斯網(wǎng);ζ－一棵覆蓋G的團(tuán)樹(shù);

E－證據(jù)變量;e－證據(jù)變量的取值;Q－一個(gè)查詢變量。

輸出:P(Q|E=e)

1:利用G將ζ初始化，即將G中的概率分布函數(shù)存儲(chǔ)于ζ中的各結(jié)點(diǎn)處;

2:在ζ中的函數(shù)中，將證據(jù)變量E設(shè)置為其取值e;

3:在ζ中找出一個(gè)包含Q的團(tuán)CQ作為樞紐;

4:for(每個(gè)與CQ相鄰的結(jié)點(diǎn)C)

5:調(diào)用子程序CollectMessage1(ζ，CQ，C)獲得一個(gè)函數(shù);

6:end for

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

基于團(tuán)樹(shù)傳播算法的多查詢變量的貝葉斯推理算法將在調(diào)用子程序CollectMessage的基礎(chǔ)上，引入另外兩個(gè)子程序SaveMessage和RetrieveMessage，進(jìn)行團(tuán)樹(shù)共享計(jì)算［7］。對(duì)于停車行為分析的貝葉斯網(wǎng)絡(luò)推理，最終將通過(guò)單查詢變量推理和多查詢變量推理，計(jì)算并輸出［l］［sc］兩個(gè)查詢變量的值。

3 停車行為推理分析

應(yīng)用Matlab軟件的jtree_inf_engine模塊，停車行為分析的貝葉斯網(wǎng)絡(luò)的推理結(jié)果介紹如下。

3.1 預(yù)測(cè)推理

假設(shè)已知某人因工作于非高峰時(shí)段開(kāi)公車出行，想知道此人所選擇停車場(chǎng)類型。證據(jù)為:

應(yīng)用已建貝葉斯網(wǎng)絡(luò)推理，得此人選擇9個(gè)類型停車場(chǎng)的概率如表2所示。

表2 預(yù)測(cè)推理中某人選擇各類型停車場(chǎng)的概率

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

3.2 診斷推理

假設(shè)已知某人選擇在2元/小時(shí)的停車場(chǎng)停放車輛5小時(shí)，想知道停車場(chǎng)類型和此人的出行目的。根據(jù)已建貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)分析已知和待求各變量之間的推理順序，知此問(wèn)題為診斷推理方式。證據(jù)為:

應(yīng)用已建貝葉斯網(wǎng)絡(luò)推理，此人的出行目的分布如表3所示。

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

分析表3中結(jié)果可知，此人的出行目的為生活出行的可能性大。應(yīng)用已建貝葉斯網(wǎng)絡(luò)推理，此人選擇9個(gè)類型停車場(chǎng)的概率如表4所示。

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

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

3.3 原因關(guān)聯(lián)推理

例如，在停車行為分析的貝葉斯網(wǎng)絡(luò)中，停車場(chǎng)類型和停車費(fèi)率是產(chǎn)生停車時(shí)長(zhǎng)的直接原因。下面應(yīng)用原因關(guān)聯(lián)推理方法推理學(xué)習(xí)當(dāng)停車時(shí)長(zhǎng)為3小時(shí)及以下的短時(shí)停車時(shí)，停車場(chǎng)類型和停車費(fèi)率之間的相互影響關(guān)系。證據(jù)為停車時(shí)長(zhǎng)sc=1］。所得結(jié)果見(jiàn)表5。

表5 停車場(chǎng)類型與停車費(fèi)率之間的關(guān)系

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

3.4 混合推理

假設(shè)已知某人開(kāi)車購(gòu)物，選擇在2元/小時(shí)的停車場(chǎng)停放車輛5小時(shí)，則想知道此人開(kāi)的車是公車還是私車，選擇何種停車場(chǎng)。證據(jù)為:evidence==3］［停車時(shí)長(zhǎng)sc=2］。

應(yīng)用已建貝葉斯網(wǎng)絡(luò)推理，得公車/私車的比例為0.1311:0.8689?？芍巳碎_(kāi)私家車的概率大。停車場(chǎng)類型分布如表6所示。

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

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

4 結(jié)論

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

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

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

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

［4］梁俊秀.基于貝葉斯網(wǎng)絡(luò)的軌道交通系統(tǒng)人因可靠性定量分析方法研究［D］.北京:北京交通大學(xué)，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］張連文，郭海鵬.貝葉斯網(wǎng)引論［M］.北京:科學(xué)出版社，2006.