貝葉斯網(wǎng)絡(luò)推理算法及其在交通量預(yù)測(cè)中的應(yīng)用

貝葉斯網(wǎng)絡(luò)推理算法及其在交通量預(yù)測(cè)中的應(yīng)用

1貝葉斯網(wǎng)絡(luò)的結(jié)構(gòu)貝葉斯網(wǎng)絡(luò)也稱為新網(wǎng)絡(luò)，是在復(fù)雜統(tǒng)計(jì)分析技術(shù)中基于貝葉斯決策方法的統(tǒng)計(jì)推斷方法發(fā)展而來的。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)之間的條件概率組成的條件概率分布Θ。近年來,貝葉斯網(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ò)。宗芳等(2010)建立了停車行為分析的貝葉斯網(wǎng)絡(luò),并進(jìn)行了停車收費(fèi)等管理政策評(píng)價(jià)。宗芳等(2011)運(yùn)用相關(guān)性分析方法和K2算法建立了交通事故致因分析的貝葉斯網(wǎng)絡(luò)。梁俊秀(2010)基于貝葉斯網(wǎng)絡(luò)的人的可靠性分析模型,對(duì)軌道交通系統(tǒng)司機(jī)的人因可靠性進(jìn)行了定量分析,提出了基于Gibbs采樣的交通貝葉斯網(wǎng)絡(luò)近似概率推理算法,并進(jìn)行交通流量的短時(shí)預(yù)測(cè)。Janssens等(2006)結(jié)合應(yīng)用決策樹和貝葉斯網(wǎng)絡(luò)描述人們的出行行為。Hinsbergen等(2009)應(yīng)用貝葉斯網(wǎng)絡(luò)和神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)出行時(shí)間。但目前的研究主要注重貝葉斯網(wǎng)絡(luò)參數(shù)估計(jì)和結(jié)構(gòu)學(xué)習(xí)方法,對(duì)推理算法還沒有足夠重視。本文將研究貝葉斯網(wǎng)絡(luò)的推理算法,并以停車行為分析的貝葉斯網(wǎng)絡(luò)推理為例進(jìn)行實(shí)例分析。2貝葉斯網(wǎng)絡(luò)推理貝葉斯網(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)的概率分布?，F(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)樹傳播算法是最常用的一種精確推理算法,其推理結(jié)果精確,計(jì)算效率較高。其主要思想是將貝葉斯網(wǎng)絡(luò)轉(zhuǎn)化為團(tuán)樹,然后通過定義在團(tuán)樹上的消息傳遞過程來進(jìn)行概率計(jì)算,完成對(duì)網(wǎng)絡(luò)的推理計(jì)算。其推理過程為:①確立推理函數(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)樹傳播算法可以在Matlab通過engine=jtree_inf_engine(bnet)函數(shù),調(diào)用聯(lián)合樹推理引擎來實(shí)現(xiàn),并可以進(jìn)行停車行為分析的貝葉斯網(wǎng)絡(luò)的推理學(xué)習(xí)?；趫F(tuán)樹傳播算法的貝葉斯推理計(jì)算流程如圖1所示。以下將以文獻(xiàn)《基于貝葉斯網(wǎng)絡(luò)的停車行為分析》所建的貝葉斯網(wǎng)絡(luò)為例,詳細(xì)說明團(tuán)樹傳播算法的實(shí)現(xiàn)過程。圖2為停車行為分析的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)圖,表1為圖中各變量的取值。(1)打開原始地圖將貝葉斯結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)的不同父結(jié)點(diǎn)結(jié)合,即在它們之間加一條邊,然后去掉所有邊的方向,所得到的無向圖稱為端正圖。(2)以開發(fā)數(shù)據(jù)為前提的編碼過程應(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)?lt;sc,jf,f,j,l,s,g,m,k>,確定消元順序后的端正圖如圖3。(3)法的基本思想構(gòu)造團(tuán)樹的方法主要有圖消元算法和BuildCT算法。其中,BuildCT(ξ,ρ)算法的基本思想是:從貝葉斯網(wǎng)G的端正圖ξ出發(fā),按一定順序在ξ中進(jìn)行變量消元;在消去變量X之前,先構(gòu)造一個(gè)由X以及所有與X相鄰的變量組成的團(tuán);在消元過程結(jié)束后,把所產(chǎn)生的團(tuán)以適當(dāng)方式進(jìn)行組織,得到一棵覆蓋G的團(tuán)樹ζ。應(yīng)用BuildCT算法,所得團(tuán)樹如圖4所示。(4)基于團(tuán)樹傳播算法的多查詢變量推理首先要確定推理中的證據(jù)變量,取值e。其后,設(shè)置推理中的查詢變量,其集合為Q。根據(jù)查詢變量的多少,推理過程可分為單查詢變量推理和多查詢變量推理,前者的查詢變量?jī)H有一個(gè),而后者是在前者的基礎(chǔ)上,利用團(tuán)樹的共享推理機(jī)制,簡(jiǎn)化計(jì)算過程后,推理得到多個(gè)查詢變量的結(jié)果。推理過程即為計(jì)算在證據(jù)變量的影響下查詢變量的值的過程,即求解P(Q|E=e)?；镜挠?jì)算公式為,P(Q|E=e)=P(Q,E=e)P(E=e)(1)停車場(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),團(tuán)樹傳播算法(簡(jiǎn)記為CTP)的推理計(jì)算過程為:CTP(G,ζ,E,e,Q)輸入:G-一個(gè)貝葉斯網(wǎng);ζ-一棵覆蓋G的團(tuán)樹;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:endfor7:把上一步獲得的函數(shù)以及儲(chǔ)存在CQ處的函數(shù)相乘,得到C′Q的一個(gè)函數(shù)h(C′Q),這里C′Q=CQ＼E;8:return∑C′Q\{Q}h(C′Q)/∑C′Qh(C′Q)則P(Q|E=e)=∑C′Q\{Q}h(C′Q)/∑C′Qh(C′Q)即為所求的查詢結(jié)果?；趫F(tuán)樹傳播算法的多查詢變量的貝葉斯推理算法將在調(diào)用子程序CollectMessage的基礎(chǔ)上,引入另外兩個(gè)子程序SaveMessage和RetrieveMessage,進(jìn)行團(tuán)樹共享計(jì)算。對(duì)于停車行為分析的貝葉斯網(wǎng)絡(luò)推理,最終將通過單查詢變量推理和多查詢變量推理,計(jì)算并輸出[l][sc]兩個(gè)查詢變量的值。3停車行為的推理分析應(yīng)用Matlab軟件的jtree_inf_engine模塊,停車行為分析的貝葉斯網(wǎng)絡(luò)的推理結(jié)果介紹如下。3.1停車場(chǎng)類型的選擇假設(shè)已知某人因工作于非高峰時(shí)段開公車出行,想知道此人所選擇停車場(chǎng)類型。證據(jù)為:evidence=[出行目的m=1][公車/私車g=1][停車開始時(shí)間k=2]應(yīng)用已建貝葉斯網(wǎng)絡(luò)推理,得此人選擇9個(gè)類型停車場(chǎng)的概率如表2所示。分析表2中數(shù)據(jù)可知,此人選擇居住小區(qū)停車場(chǎng)的可能性最大,其次是單位大院停車場(chǎng)?？梢哉J(rèn)為,如選擇居住小區(qū)停車場(chǎng),則此人的出行目的為工作出行中的回家;而如果選擇單位大院停車場(chǎng),則出行目的為工作出行中的上班或上學(xué)。3.2基于未建貝葉斯網(wǎng)絡(luò)推理的出行目的分布假設(shè)已知某人選擇在2元/小時(shí)的停車場(chǎng)停放車輛5小時(shí),想知道停車場(chǎng)類型和此人的出行目的。根據(jù)已建貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)分析已知和待求各變量之間的推理順序,知此問題為診斷推理方式。證據(jù)為:evidence=[停車費(fèi)率f=3][停車時(shí)長(zhǎng)sc=2]應(yīng)用已建貝葉斯網(wǎng)絡(luò)推理,此人的出行目的分布如表3所示。分析表3中結(jié)果可知,此人的出行目的為生活出行的可能性大。應(yīng)用已建貝葉斯網(wǎng)絡(luò)推理,此人選擇9個(gè)類型停車場(chǎng)的概率如表4所示。分析表4中結(jié)果可知,此人選擇公建配建停車場(chǎng)的可能性最大,其次是路外停車場(chǎng),這與停車時(shí)間和出行目的也比較相符。3.3停車場(chǎng)類型與停車率的相關(guā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ù)為:evidence=[停車時(shí)長(zhǎng)sc=1]。所得結(jié)果見表5?？梢?停車場(chǎng)類型與停車費(fèi)率之間的相關(guān)性較大。具體來說,占道停車(劃線)、公建配建停車場(chǎng)收費(fèi)較高,其次是立交橋下停車場(chǎng)、路外停車場(chǎng)、居住小區(qū)停車場(chǎng),免費(fèi)的停車場(chǎng)類型主要有臨時(shí)路邊、占道停車(未劃線)、單位大院停車場(chǎng)和其他。這些推理分析結(jié)果與目前的停車管理現(xiàn)狀吻合。3.4停車場(chǎng)的選擇假設(shè)已知某人開車購(gòu)物,選擇在2元/小時(shí)的停車場(chǎng)停放車輛5小時(shí),則想知道此人開的車是公車還是私車,選擇何種停車場(chǎng)。證據(jù)為:evidence=[出行目的m=2][停車費(fèi)率f=3][停車時(shí)長(zhǎng)sc=2]。應(yīng)用已建貝葉斯網(wǎng)絡(luò)推理,得公車/私車的比例為0.1311:0.8689。可知,此人開私家車的概率大。停車場(chǎng)類型分布如表6所示。分析結(jié)果可知,此人選擇公建配建停車場(chǎng)的可能性最大,其次是路外停車場(chǎng)。與診斷推理案例相比,此例在新增出行目的為購(gòu)物這樣的證據(jù)下,選擇公建配建停車場(chǎng)和路外停車場(chǎng)的概率有所增加。4巖相系統(tǒng)的應(yīng)用本文以貝葉斯網(wǎng)絡(luò)的推理方法為主要研究?jī)?nèi)容,重點(diǎn)闡述了團(tuán)樹推理方法的基本過程和算法,以Matlab軟件的en