采用變結構動態(tài)貝葉斯網絡的交通流量預測*

王永恒，高 慧，陳炫伶

湖南大學 信息科學與工程學院，長沙 410082

采用變結構動態(tài)貝葉斯網絡的交通流量預測*

王永恒+，高 慧，陳炫伶

湖南大學 信息科學與工程學院，長沙 410082

物聯(lián)網和大數(shù)據(jù)流式計算的快速發(fā)展為智能交通系統(tǒng)的研究帶來新的機遇。交通流量預測一直是智能交通系統(tǒng)的關鍵問題。針對交通流量預測中一個固定模型無法適應多種環(huán)境的問題，以及面向數(shù)據(jù)流的模型更新問題，提出了一種基于變結構動態(tài)貝葉斯網絡的交通流量預測方法。該方法以復雜事件處理和事件上下文為基礎，通過上下文聚類進行歷史數(shù)據(jù)的劃分，并通過事件流在線聚類支持聚簇的更新。面向不同聚簇的數(shù)據(jù)，采取搜索-打分的方法學習對應的貝葉斯網絡結構，基于高斯混合模型實現(xiàn)貝葉斯網絡的近似推斷。在線預測時根據(jù)當前上下文選擇合適的模型或模型組合進行預測。真實和仿真數(shù)據(jù)上的實驗結果表明，該方法能夠獲得比當前常用方法更好的預測效果。

智能交通系統(tǒng)；交通流量預測；復雜事件處理；變結構動態(tài)貝葉斯網絡

1 引言

近年來，隨著物聯(lián)網（Internet of things,IoT）和移動計算技術的迅速發(fā)展，人們加速跨進大數(shù)據(jù)的時代。很多應用快速產生多種多樣的數(shù)據(jù)，對這些數(shù)據(jù)進行實時高效的處理能夠獲取更大的價值。對數(shù)據(jù)流的實時處理是大數(shù)據(jù)研究的一個關鍵，大數(shù)據(jù)特性中的快速性（velocity）和多樣性（variety）正是對這種情況的刻畫。

作為物聯(lián)網中間件的核心及大數(shù)據(jù)流式處理的關鍵技術，復雜事件處理（complex event processing，CEP）正在受到廣泛的關注。復雜事件處理是對數(shù)據(jù)流中的原始事件進行解釋和組合，從而識別出更高層的復雜事件（也稱復合事件）的過程[1]。復雜事件處理技術在很多領域得到了廣泛應用，如基于無線傳感網的環(huán)境監(jiān)測、股票走勢的連續(xù)分析等。近期大數(shù)據(jù)的流式計算技術也得到了快速發(fā)展，如Apache的Storm、Spark Streaming及Flink等項目，這些項目強調高效處理大規(guī)模分布式數(shù)據(jù)流，但并不直接支持復雜的操作。把這些技術和復雜事件處理配合起來使用，能夠更好地支持分布式數(shù)據(jù)流的高效和智能處理。

物聯(lián)網和大數(shù)據(jù)流式處理技術的發(fā)展，為智能交通系統(tǒng)（intelligent transportation system，ITS）帶來了新的發(fā)展機遇。借助物聯(lián)網技術，可以對交通信息進行全方位的感知和數(shù)據(jù)傳輸。機遇大數(shù)據(jù)流式處理技術，可以對產生的大量數(shù)據(jù)進行實時和智能的處理。交通流量預測作為很多交通智能決策的依據(jù)，在智能交通系統(tǒng)中占據(jù)重要的位置。

人們對交通流量預測問題進行了大量研究，開發(fā)了多種預測模型和方法。近年來比較成功的有基于支持向量機的方法[2-3]、基于深度學習的方法[4-5]、基于貝葉斯網絡（Bayesian network，BN）的方法[6-8]和基于混合模型的方法[9]等?；谪惾~斯統(tǒng)計技術，貝葉斯網絡能夠很好地把領域知識和數(shù)據(jù)融合起來，支持不完整數(shù)據(jù)的處理及因果分析，并能夠較好地解決過擬合的問題。這些特點使得貝葉斯網絡在預測模型中占據(jù)重要位置，并在交流流量預測中獲得廣泛應用。

當前的交通流量預測方法還存在以下問題：（1）當環(huán)境變化時，一個固定的模型無法在不同的環(huán)境下都具備良好的預測能力[9]?；诨旌夏Ｐ偷姆椒軌蛟谝欢ǔ潭壬峡朔@個問題，避免在環(huán)境變化時出現(xiàn)很糟糕的預測結果。但模型組合方法無法保證在每種環(huán)境下能夠得到最好的結果。（2）現(xiàn)有的方法基本都是從大量歷史數(shù)據(jù)中訓練模型，然后把模型用于實時的預測，而很少考慮隨著新數(shù)據(jù)的產生，模型也可能需要發(fā)生相應的變化。（3）隨著物聯(lián)網和移動計算的發(fā)展，人們能夠實時獲取多種環(huán)境信息，如路況、天氣等?，F(xiàn)有的交通預測方法往往還是根據(jù)有限的信息進行預測，而沒有綜合利用各種實時的環(huán)境信息。

針對上述問題，本文提出了一種基于變結構貝葉斯網絡（structure varying dynamic Bayesian network，SVDBN）的交通流量預測方法。本文方法以復雜事件處理和事件上下文為基礎，通過上下文聚類對數(shù)據(jù)進行劃分，針對不同的數(shù)據(jù)學習對應的貝葉斯網絡模型，并在對事件流預測的過程中實時更新模型。在預測時針對當前上下文選擇合適的模型或模型組合進行預測。貝葉斯模型的結構學習基于搜索-打分的方式實現(xiàn)，近似推斷通過高斯混合模型（Gau-ssian mixture model，GMM）來實現(xiàn)。真實和仿真數(shù)據(jù)上的實驗結果表明，本文方法能夠獲得比當前常用方法更好的預測效果。

2 相關研究

2.1 復雜事件處理

復雜事件處理技術通過對原始事件流的持續(xù)監(jiān)視獲取高層的復雜事件。Luckham和Etzion等人介紹了復雜事件處理的基本概念和處理結構[1,10]。復雜事件處理的核心是復雜事件處理網絡（event processing network，EPN），它通過事件通道把多個復雜事件處理代理（event processing agent，EPA）、事件產生者、事件消費者等連接起來。

與本文相關的一個研究方向是上下文敏感復雜事件處理。針對上下文的表示人們研究了多種模型，一般認為本體是表示上下文的最佳模型。為了表示不確定知識，近期有人采用模糊本體來表示上下文。Zhang等人提出了一種基于模糊集的領域本體構建方法，在本體概念屬性集上引入了模糊集隸屬函數(shù)[11]。Cai等人在其著作中闡述了模糊本體的隸屬度和典型性問題，并研究了模糊本體模型在上下文表示和推理中的應用[12]。

另一個重要的相關研究是預測式復雜事件處理（predictive complex event processing），也就是預測將來某個事件的發(fā)生。Etzion等人在其著作中指出，預測式復雜事件處理的目標主要是為了防止或減緩某個事件的發(fā)生[10]。Fül?p等人提出了一個預測式復雜事件處理框架[13]，實際上是在復雜事件處理網絡中增加預測分析模塊。在這個框架下，很多已有的預測分析技術可以直接應用于預測式復雜事件處理，但這些方法如何適應大規(guī)模的分布式數(shù)據(jù)流，以及如何調整模型適應數(shù)據(jù)的變化，仍然是待解決的問題。

2.2 交通流量預測

交通流量預測的相關模型和方法非常多，Eleni等人對短時交通流量預測技術進行了詳細的綜述[14]，對常見的模型和方法進行了分類對比，并提出了短時交通流量預測的10項挑戰(zhàn)及對應的研究工作。

最近隨著深度學習熱潮的興起，涌現(xiàn)出了一些基于深度學習的交通流量預測工作。Huang等人提出了一種基于深度信念網絡（deep belief networks，DBN）進行交通流量預測的方法。該方法下層采用深度信念網絡，最上層采用回歸模型進行最終的預測[4]。同時其最上層的回歸模型支持多任務學習（multitask learning）。Lv等人在其基于深度學習的交通流量預測中使用了自編碼器（autoencoder）來學習交通流量的一般特征，并采用貪婪逐層融合的方式進行訓練[5]。深度學習的方法能夠取得較好的預測效果，但模型訓練比較復雜，也容易出現(xiàn)過擬合的問題。

與本文直接相關的是貝葉斯網絡方面的研究工作。Sun等人采用貝葉斯網絡模型進行交通流量預測，在建模事實數(shù)據(jù)和待預測數(shù)據(jù)結點的聯(lián)合分布時采用了高斯混合模型[6]。其中高斯混合模型的參數(shù)通過競爭性EM算法（competitive expectation maximization，CEM）實現(xiàn)。Castilloa等人使用貝葉斯網絡進行起點-終點及鏈路的交通預測，采用高斯模型進行聯(lián)合分布建模[7]。同時在給定起點-終點流量的情況下，采用了隨機用戶平衡（stochastic user equilibrium，SUE）的方式進行鏈路流量處理。Zhu等人也是把SUE融合到貝葉斯網絡模型，把鏈路流量作為起點-終點流量的父結點[8]。根據(jù)先驗路段流量確定所有變量的先驗分布，然后通過更新一些觀測的路段流量，給出后驗分布，從而實現(xiàn)最終預測。和本文相比，這些研究都沒有考慮交通數(shù)據(jù)發(fā)生大的變化時，模型無法適應的問題。同時也沒有考慮面向數(shù)據(jù)流的模型更新問題。

3 系統(tǒng)結構

3.1 總體框架

系統(tǒng)總體框架如圖1所示。首先定義復雜事件處理網絡中的各概率事件處理代理（probability event processing agent，PEPA）的事件模式、相互連接及事件上下文的獲取規(guī)則。來自傳感器網絡或其他系統(tǒng)的原始事件，經復雜事件處理網絡處理后形成復雜事件流，并保存在歷史數(shù)據(jù)庫中。模型訓練時首先對歷史數(shù)據(jù)按時間片進行劃分，然后以時間片為單位，根據(jù)事件上下文進行離線聚類，對每個獲得的聚簇分別學習對應的貝葉斯網絡結構和參數(shù)。在線預測時，對在線復雜事件流進行基于上下文的在線聚類，根據(jù)聚類的結果選擇一個貝葉斯模型或多個貝葉斯模型的組合來進行預測。同時，在線聚類的結果能夠實時更新聚簇的數(shù)據(jù)，在此基礎上進行貝葉斯模型結構和參數(shù)的實時更新。

Fig.1 System architecture圖1 系統(tǒng)總體框架

3.2 復雜事件處理和上下文

原始事件是指某個時刻某個事情的一次發(fā)生，例如傳感器的一次數(shù)據(jù)讀取產生一個原始事件。原始事件表示為＜A,T>，其中A為事件屬性的集合，T為事件發(fā)生的時標。如果為不確定事件，則表示為＜A, T,P>，P為事件的概率。復雜事件是由原始事件或者復雜事件按照一定的運算規(guī)則形成的事件，表示為＜E,R>，其中E是復雜事件的組成元素，R為事件合成規(guī)則。如果是不確定事件也加上概率。具有相同特征的一類事件為一個事件類型。復雜事件有多種模式，如ALL、ANY、COUNT、SEQ等，這些在文獻[10]中有詳細的定義和說明。例如在交通領域可以使用COUNT模式獲取一定范圍內的車輛總數(shù)，用SEQ獲取車輛行駛路線等。這些模式可以進一步組合和嵌套形成更復雜的模式。作為本文的基礎，作者前期開發(fā)了一個分布式概率復雜事件處理系統(tǒng)（distributed probabilisticcomplexeventprocessingmethod，DPCEP）[15]。

事件上下文定義為一些特殊的條件，根據(jù)這些條件可以對事件實例進行劃分，從而使被劃分的事件能夠關聯(lián)在一起來處理[10]。上下文有很多類型，如“汽車旅館M1周圍2公里范圍”是一個距離上下文，“公路交通狀態(tài)是緩慢行駛”是一個狀態(tài)上下文。通常上下文的獲取有兩種情況：一種是簡單情況，直接通過事件的屬性獲取上下文，例如車輛的行駛速度。另外一種是復雜情況，需要通過定義復雜事件來幫助獲取上下文。例如道路擁堵上下文的獲取可以通過道路流量計數(shù)、車輛行駛速度和等待時間等多個因素結合起來進行判斷。

定義2（模糊本體）在特定領域D上的模糊本體O表示為OD=(C,R,P,I)。其中C為模糊概念的集合，P為概念的模糊屬性的集合，I是概念實例的集合，R是模糊角色（也就是對象及概念間的關聯(lián)）的集合。

Fig.2 Apart of traffic domain ontology圖2 交通領域本體的一部分

例如“紅色轎車”是一個模糊概念，它是另外一個概念“轎車”的子集?！皬埲浅Ｏ矚g跑車”是一個模糊角色的實例，關聯(lián)程度是“非常高”。模糊屬性“駕駛速度”的值可以表示為{“S(慢)”，“M（中）”，“F（快）”}。本文采取手工方法建立了一個交通領域模糊本體，其中的一部分如圖2所示。本體的表示基于Fuzzy OWL 2（http://gaia.isti.cnr.it/～straccia/software/ FuzzyOWL/）。關于上下文敏感復雜事件處理的詳細資料參閱文獻[16]。

4 基本貝葉斯網絡預測

應用在交通流量預測領域，貝葉斯網絡的結構如圖3所示。圖中有兩個維度：位置（橫坐標）和時間（縱坐標）。假定車輛在N個路口（或路段）中行駛，圖中某個結點(i,t)的擁堵狀態(tài)s(i,t)依賴于t之前的若干個結點（貝葉斯網絡中稱其為父結點，表示為pa(i,t)），在圖3中通過有向邊連接到結點(i,t)的是其父結點。pa(i,t)的狀態(tài)可表示為Spa(i,t)={sj,s|(j,s)∈pa(i,t)}。根據(jù)貝葉斯理論，此貝葉斯網絡結點狀態(tài)的聯(lián)合分布可表示為：

Fig.3 Bayesian network structure fortraffic flow prediction圖3 用于交通流量預測的貝葉斯網絡結構

其中，條件概率 p(si,t|Spa(i,t))可根據(jù)下式計算：

本文使用高斯混合模型[17]來近似聯(lián)合分布 p(si,t, Spa(i,t))：

其中，M為高斯模型的數(shù)量；gm(·|μm,Σm)是第m個高斯模型的分布；μm為均值向量；Σm為協(xié)方差矩陣；αm為第m個高斯模型的系數(shù)且。采用EM算法[18]可以從樣本數(shù)據(jù)中學習參數(shù)。根據(jù)獲取的參數(shù)可以計算分布 p(si,t,Spa(i,t))，從而計算p(si,t|Spa(i,t))。

為了學習貝葉斯網絡的結構，本文采用搜索-打分的方法，思想是最大化打分函數(shù)，從而實現(xiàn)貝葉斯網絡結構和樣本數(shù)據(jù)的最優(yōu)擬合。采用的BIC（Bayesian information criterion）[19]打分函數(shù)為：

其中，D為樣本數(shù)據(jù)集；G為貝葉斯網絡結構；Θ?為D的極大似然分布參數(shù)；d為邊的數(shù)量；m為樣本大小。學習過程分為擴張和收縮兩個階段。在擴張階段，所有能夠最大化打分函數(shù)增長的邊被加入網絡結構。在收縮階段，對于那些移去以后不導致打分函數(shù)值下降的邊從網絡結構上移除。

5 變結構動態(tài)貝葉斯網絡預測

定義4（變結構動態(tài)貝葉斯網絡）變結構動態(tài)貝葉斯網絡表示為，其中G(t)和Θ(t)分別表示t時刻貝葉斯網絡的結構和參數(shù)，Ce(t)?CE為t時刻的上下文類別，CE為上下文類別的集合，F(xiàn)為G(t)和Θ(t)到Ce(t)的映射。

盡管已經有一些動態(tài)和變結構貝葉斯網絡學習和推理的研究[17,20]，但是這些方法過于復雜而難以應用到較大規(guī)模的交通流量預測中。前期的實驗結果表明[21]，在交通預測領域不同的環(huán)境對應不同的貝葉斯模型。本文提出了一種基于復雜事件上下文來近似處理SVDBN的方法。由于在貝葉斯網絡中結點的當前狀態(tài)和一段時間內的歷史狀態(tài)相關，按照一個時間跨度參數(shù)δ對事件流進行劃分，劃分出來的每一段稱為一個切片。根據(jù)事件上下文對切片數(shù)據(jù)進行聚類，并針對聚類結果的每一聚簇學習其貝葉斯網絡的結構和參數(shù)。

對歷史數(shù)據(jù)的聚類，本文采用減法聚類方法[22]。在聚類時使用樣本數(shù)據(jù)作為候選的中心點（聚簇中心），而不是采用虛擬的中心點。對于每個數(shù)據(jù)點，基于以下公式計算其潛在值（密度）：

其中，pi(zi)為數(shù)據(jù)點zi的潛在值；N為數(shù)據(jù)點的總數(shù)；ra是一個正的常量。其原理是把某個數(shù)據(jù)點的潛在值定義為其到所有其他數(shù)據(jù)點距離的函數(shù)。選擇具有最高潛在值的數(shù)據(jù)點作為第一個類的中心。然后每個數(shù)據(jù)點的潛在值都減去一個正比于其到數(shù)據(jù)中心距離的值。選擇剩余潛在值最大的數(shù)據(jù)點作為下一個聚簇的中心點，以此類推。

此聚類方法的關鍵是計算樣本之間的距離，也就是事件切片之間的距離。本文基于事件上下文來計算樣本間的距離。先考慮單個上下文屬性間的距離。表示事件上下文的模糊本體是一個層次化的結構。兩個事件屬性結點ni和nj間的距離定義如下：

其中，μi()為結點ni上的模糊集隸屬函數(shù)；s(ni,nj)表示結點ni和nj在同一個進行了模糊劃分的結點上（如劃分為“慢”、“中”、“快”）；K表示結點上模糊劃分的數(shù)量；pi表示上下文屬性對應的結點ni上模糊劃分的序號（如“中”對應的序號為2）；Lij表示模糊本體層次結構上結點ni和nj之間的路徑長度。

由于一個事件可能有多個上下文，為了定義上下文集合間的距離，把事件a和b對應的上下文集合分別表示為Ca=(ca1,ca2…,cam)和Cb=(cb1,cb2,…,cbn)。對于每個cai?Ca，查找cbj滿足mincbj(dis(cai,cbj))，則定義Ca到Cb的距離為：

其中，函數(shù)β為距離的權重。同樣定義Cb到Ca的距離為：

最終Ca和Cb之間的距離為：

對于切片間距離的計算，把切片看作事件的集合，也采用上述方法計算集合間的距離。在確定了聚簇的中心點以后，其他樣本點劃分到其附近的聚簇。由于事件上下文的復雜性，允許在劃分聚簇時把樣本點劃入多個聚簇，也就是找到k個距離最近的中心點，然后把樣本劃分到相關的聚簇。為了使樣本在聚簇間的分布更為合理，以便貝葉斯網絡的學習，對于劃分到多個聚簇中的樣本，基于如下圖書館準則進行劃分的調整。

圖書館準則1（緊湊性）同一本書可以放在不同的書架上，但放置的方法要滿足圖書數(shù)量需求最小的原則。

圖書館準則2（均勻性）圖書應該盡量均勻地分布在多個書架上。

對于緊湊性，首先基于式（10）計算事件上下文cei屬于聚簇Ch的概率分布：

假設在初始劃分時cei被劃分到了k個聚簇，計算歸一化熵如下：

根據(jù)緊湊性的原則，歸一化熵Hnorm(cei)應該越接近0越好。在實現(xiàn)時對每個cei加總Hnorm(cei)的值，然后找到使其最小的劃分。

對于均勻性，根據(jù)貝葉斯理論計算p(cei|Ch)：

設p(cei)=1/N，則：

則p(Ch)可按下式計算：

最終歸一化熵定義為：

對于每個劃分，對所有Hnorm(Ch)計算平均值，平均值越大的劃分越合理。

上述方法為離線數(shù)據(jù)的聚類。在面向數(shù)據(jù)流的預測中，為了保持時效性，對離線聚類方法進行擴展以支持在線聚類。把潛在值定義為：

其中，pk(zk)為時刻k的數(shù)據(jù)點zk的潛在值。當數(shù)據(jù)增加時，可以一直使用上述公式更新潛在值，然后進行聚簇的更新。在線聚類并不從頭開始運行，直接使用離線聚類中已經獲得的中心點和聚簇劃分，根據(jù)新的數(shù)據(jù)進行更新。

如果在線聚類產生了新的類，并且新類的樣本達到一定規(guī)模，則學習新類對應的貝葉斯網絡結構并應用到實時預測中。在實時預測時，如果當前上下文和已有多個聚簇的聚類比較接近（其差異小于某個閾值δ），并不選擇其中聚類最小的聚簇來匹配模型，而是選擇所有符合條件的聚簇，把對應的模型通過貝葉斯組合方法（Bayesian combination method，BCM）[9]進行模型組合來預測。

為了對貝葉斯網絡的結構進行實時更新，假設聚簇中新增加的樣本為DΔ。根據(jù)DΔ的來源確定可能受影響的結點集合VΔ和邊集合EΔ。對于VΔ中的所有結點，逐個連接其所有候選父結點，如果新邊的加入最大化了BIC打分函數(shù)值，則保留新加入的邊，并將其合并入集合EΔ。然后對EΔ中的所有邊進行判斷，如果去除該邊后BIC打分函數(shù)值并不下降，則去除該邊。

在使用EM算法進行高斯混合模型的參數(shù)學習時，在內存中保留參數(shù)的最終值和各中間結果。為了對高斯混合模型的參數(shù)進行更新，使用當前的αm、μm、Σm參數(shù)，針對變化后的樣本計算隱藏變量的分布，然后基于隱藏變量的分布根據(jù)極大似然法計算新的αm、μm、Σm參數(shù)。如果參數(shù)無明顯變化或對數(shù)似然收斂，則無需更新在線參數(shù)。否則反復重復上述步驟直至收斂，并更新在線模型的參數(shù)。

6 實驗研究

實驗系統(tǒng)的結構如圖4所示。系統(tǒng)采用Apache Kafka作為數(shù)據(jù)總線。使用了兩類實驗數(shù)據(jù)：真實數(shù)據(jù)和交通仿真系統(tǒng)產生的數(shù)據(jù)。真實數(shù)據(jù)來源于PEMS交通監(jiān)測系統(tǒng)（https://pems.eecs.berkeley.edu/），監(jiān)測的是洛杉磯市101號高速公路的數(shù)據(jù)。數(shù)據(jù)以文件的形式存儲，系統(tǒng)運行時通過一個播放器把文件中的數(shù)據(jù)發(fā)送到Kafka系統(tǒng)中。交通仿真系統(tǒng)采用了開源項目SUMO[23]。SUMO中支持“感應線圈”獲取流量數(shù)據(jù)，也可以獲取每個車輛的實時位置信息（模擬為GPS）。同時擴展SUMO系統(tǒng)以支持其他類型的傳感器，如溫度、濕度、風力等?；赟UMO提供的TraCI（traffic control interface）調用接口，本實驗系統(tǒng)實現(xiàn)了從SUMO中實時獲取傳感器的數(shù)據(jù)，并發(fā)送到Kafka形成原始事件流。

仿真系統(tǒng)中設置了15×15交叉路口的路網，每條路雙向4車道?？偣餐斗?0萬輛車，車輛的投放模擬了周五和周六兩天的車流量情況，仿真系統(tǒng)一分鐘代表實際時間的一小時。為了使仿真更接近真實的系統(tǒng)，制定了一些規(guī)則。公交車在固定的路線上行駛，為每輛私家車設置一個家位置和一個辦公室位置。車輛以一定的概率在家和辦公室之間行駛，同時以某個小的概率到其他地方，如醫(yī)院或超市。在運行交通仿真時，控制系統(tǒng)上下文按時間段發(fā)生變化。實驗使用了3臺配置至強E3和16 GB內存的服務器，一臺用于運行交通仿真和播放PEMS數(shù)據(jù)，一臺用于實時交通流量預測，另外一臺用于實時模型學習和更新。

實驗中選擇常規(guī)的貝葉斯網絡方法[6]和深度信念網絡方法[4]作為對比方法。對算法的衡量基于平均絕對百分比誤差（mean absolute percentage error，MAPE），其計算方法如下：

其中，yi為實際數(shù)據(jù)值；yi′為預測值。而平均準確度（mean accuracy，MA）可以用1-MAPE來計算。

實驗中發(fā)現(xiàn)聚類的粒度和GMM中的模型數(shù)M對結果有一定的影響。粒度過小會造成每個聚簇的樣本數(shù)不足，影響學習效果，同時也容易出現(xiàn)過擬合的問題。粒度太大則不能充分體現(xiàn)SVDBN的優(yōu)勢。在系統(tǒng)實現(xiàn)時通過多個不同粒度的聚類實驗對結果進行驗證，選擇了最好的粒度參數(shù)進行后繼的實驗。在進行減法聚類時，每個數(shù)據(jù)點的潛在值都減去一個正比于其到數(shù)據(jù)中心距離的值，通過調整這個值可以調整聚類的粒度。GMM中的模型數(shù)M的選取也面臨類似的情況。通過實驗確定M的取值在25～30之間效果比較好。

對于PEMS數(shù)據(jù)，分別以15 min、30 min、45 min、60 min為間隔，采用3種方法進行預測。對于SUMO仿真數(shù)據(jù)，首先多次運行系統(tǒng)，盡量使系統(tǒng)出現(xiàn)各種類型的上下文，保存歷史數(shù)據(jù)并離線訓練模型。在線預測時分別以1 min、2 min、3 min、4 min為間隔進行預測。3種方法的預測流量值與實際值的對照曲線如圖5和圖6所示。從這兩個圖中能夠看到實際數(shù)據(jù)的走勢以及不同預測方法的大致擬合程度。

Fig.4 System implementation framework圖4 系統(tǒng)實現(xiàn)框架

Fig.5 Prediction flow for PEMS data圖5PEMS數(shù)據(jù)的預測流量

Fig.6 Prediction flow for simulated data圖6 仿真數(shù)據(jù)的預測流量

3種方法在PEMS數(shù)據(jù)上進行預測時，不同時間點上的誤差如圖7所示。從圖7中可以看出，總體上DBN的誤差略低于BN，而SVDBN的誤差是最小的。原因是SVDBN能夠更好地適應數(shù)據(jù)的變化。此處最重要的上下文變化是“暢通”和“擁堵”間的變化。開始階段各種方法的誤差都比較大，原因是起始階段車輛比較少，分布比較稀疏，歷史狀態(tài)也比較少，不利于做出預測。

3種方法在SUMO仿真系統(tǒng)上的誤差百分比如圖8所示?？梢钥闯?，和PEMS的數(shù)據(jù)相比，總體上3種方法的誤差都有所增大。原因是SUMO仿真系統(tǒng)的數(shù)據(jù)有更多的上下文變化，從而加大了預測的難度。同時可以看出，SVDBN和其他兩種方法的誤差進一步拉開了差距，體現(xiàn)出更明顯的優(yōu)勢。原因是SVDBN的適應變化能力更好地體現(xiàn)出來。

Fig.7 Error of 3 methods on PEMS data圖7 PEMS數(shù)據(jù)上3種方法的誤差

Fig.8 Error of 3 methods on simulated data圖8 仿真數(shù)據(jù)上3種方法的誤差

3種方法針對不同時間間隔進行預測的平均準確度對比情況如圖9所示。圖中可以明確體現(xiàn)出，無論在PEMS數(shù)據(jù)還是在SUMO仿真數(shù)據(jù)上，SVDBN的平均準確度均明顯高于BN和DBN兩種方法。DBN的平均準確度略高于BN，但并無明顯差異。當預測時間間隔加大時，每種方法的平均準確度都下降。原因是時間間隔加長會增加更多的未觀測數(shù)據(jù)，從而難以實現(xiàn)準確預測。

綜上所述，SVDBN在預測中取得了比常用方法更好的準確度。當數(shù)據(jù)結構隨時間變化得比較頻繁和劇烈時，SVDBN的優(yōu)越性能夠更好地體現(xiàn)出來。

7 結論與下一步工作

Fig.9 Accuracy of 3 methods for different time spans圖9 3種方法預測不同時間范圍時的準確度

本文提出了一種基于變結構動態(tài)貝葉斯網絡的交通流量預測方法。該方法在復雜事件處理技術的基礎上，通過上下文聚類進行訓練數(shù)據(jù)的劃分，針對不同的聚簇訓練對應的貝葉斯網絡模型和參數(shù)。通過在線聚類方法支持聚簇面向數(shù)據(jù)流的實時更新，從而進一步支持模型和參數(shù)的更新?；镜呢惾~斯網絡結構通過BIC搜索打分的方式學習。貝葉斯網絡的推理通過高斯混合模型進行近似計算。在線預測時，通過把當前上下文和已有聚簇進行匹配來選擇一個或多個合適的貝葉斯網絡模型。在實際數(shù)據(jù)和仿真數(shù)據(jù)上的實驗結果表明，本文方法的預測準確度超過了當前常用的交通流量預測方法，并且當數(shù)據(jù)結構隨時間變化得比較頻繁和劇烈時，其優(yōu)越性能夠更好地體現(xiàn)出來。

本文還有一些不足之處：首先，上下文聚類的粒度和高斯混合模型中模型數(shù)量的確定，尚需要多次實驗探索，缺乏一種有效的手段進行自動學習。其次，對于大規(guī)模分布式數(shù)據(jù)流下的高性能并行與分布式預測處理，還沒有考慮。下一步研究將重點解決這些問題。

[1]Luckham D.Event processing for business:organizing the real-time enterprise[M].Hoboken,USA:John Wiley&Sons, 2011.

[2]Weichiang H,Dong Yucheng,Zheng Feifeng,et al.Forecasting urban traffic flow by SVR with continuous ACO[J].Applied Mathematical Modelling,2011,35(3):1282-1291.

[3]Yang Yanni,Lu Huapu.Short-term traffic flow combined forecasting model based on SVM[C]//Proceedings of the 2010 International Conference on Computational and Information Sciences,Chengdu,China,Dec 17-19,2010.Piscataway,USA:IEEE,2010:262-265.

[4]Huang Wenhao,Song Guojie,Hong Haikun,et al.Deep architecture for traffic flow prediction-deep belief networks with multitask learning[J].IEEE Transactions on Intelligent Transportation Systems,2014,15(5):2191-2201.

[5]Lv Yisheng,Duan Yanjie,Kang Wenwen,et al.Traffic flow prediction with big data:a deep learning approach[J].IEEE Transactions on Intelligent Transportation Systems,2015, 16(2):865-873.

[6]Sun Shiliang,Zhang Changshui,Yu Guoqiang.A Bayesian network approach to traffic flow forecasting[J].IEEE Transactions on Intelligent Transportation Systems,2006,7(1): 124-132.

[7]Castilloa E,Menéndezb J,Sánchez-Cambronerob S.Predicting traffic flow using Bayesian networks[J].Transportation Research:Part B Methodological,2008,42(5):482-509.

[8]Zhu Senlai,Chen Lin,Chu Zhaoming.Bayesian network model for traffic flow estimation using prior link flows[J]. Journal of Southeast University,2013,29(3):322-327.

[9]Wang Jian,Deng Wei,Guo Yuntao.New Bayesian combination method for short-term traffic flow forecasting[J].Transportation Research:Part C Emerging Technologies,2014, 43(1):79-94.

[10]Etzion O,Niblett P.Event processing in action[M].Greenwich,USA:Manning Publications Co,2010.

[11]Zhang Huawei,Chen Kerui.Building social relationship ontology model based on fuzzy sets[J].International Journal of Digital Content Technology&Its Applications,2012,6 (15):459-466.

[12]Cai Yi,Yeung C A,Leung H.Fuzzy computional ontologies in contexts[M].Beijing:Higher Education Press,2012.

[13]Fül?p L J,árpád B,Tóth G,et al.Predictive complex event processing—a conceptual framework for combining complex event processing and predictive analytics[C]//Proceedings of the 5th Balkan Conference in Informatics,Novi Sad,Serbia,Sep 16-20,2012.New York:ACM,2012:26-31.

[14]Eleni I V,Matthew G K,John C G.Short-term traffic forecasting:where we are and where we're going[J].Transportation Research Part C:Emerging Technologies,2014,43(1): 3-19.

[15]Wang Yongheng,Cao Kening,Zhang Xiaoming.Complex event processing over distributed probabilistic event streams [J].Computers and Mathematics with Applications,2013, 66(10):1808-1821.

[16]Cao Kening,Wang Yongheng,Li Renfa,et al.A distributed context-aware complex event processing method for Internet of things[J].Journal of Computer Research and Development,2013,50(6):1163-1176.

[17]Wang Zhaowen,Kuruog?lu E E,Yang Xiaokang,et al.Time varying dynamic Bayesian network for nonstationary events modeling and online inference[J].IEEE Transactions on Signal Processing,2011,59(4):1553-1568.

[18]Verbeek J J,Vlassis N,Krose B.Efficient greedy learning of Gaussian mixture models[J].Neural Computation,2003, 15(2):469-485.

[19]Samaranayake S,Blandin S,Bayen A.Learning the dependency structure of highway networks for traffic forecast[C]// Proceedings of the 50th IEEE Conference on Decision and Control and European Control Conference,Orlando,USA, Dec 12-15,2011.Piscataway,USA:IEEE，2011:5983-5988.

[20]Shi Jianguo,Gao Xiaoguang.To speed up the inference for the structure varied discreat dynamic Bayesian networks[J]. Fire Control&Command Control,2012,37(9):71-74.

[21]Pascale,Nicoli M.Adaptive Bayesian network for traffic flow prediction[C]//Proceedings of the 2011 Statistical Signal Processing Workshop,Nice,France,Jun 28-30,2011. Piscataway,USA:IEEE,2011:177-180.

[22]Chiu S L.Fuzzy model identification based on cluster estimation[J].Journal of Intelligent&Fuzzy Systems:Applications in Engineering and Technology,1994,2(3):267-278.

[23]Behrisch M,Bieker L,Erdmann J,et al.SUMO-simulation of urban mobility:an overview[C]//Proceedings of the 3rd International Conference on Advances in System Simulation,Barcelona,Spain,Oct 23-29，2011.Wilmington,USA: IARIAXPS Press,2011:63-68.

附中文參考文獻：

[16]曹科寧,王永恒,李仁發(fā),等.面向物聯(lián)網的分布式上下文敏感復雜事件處理方法[J].計算機研究與發(fā)展,2013,50(6): 1163-1176.

[20]史建國,高曉光.變結構離散動態(tài)貝葉斯網絡的快速推理算法[J].火力與指揮控制,2012,37(9):71-74.

WANG Yongheng was born in 1973.He received the Ph.D.degree in computer science and technology from National University of Defense Technology in 2006.Now he is an associate professor at Hunan University,and the member of CCF.His research interests include big data,stream processing and artificial intelligence.

王永恒（1973—），男，河北霸州人，2006年于國防科學技術大學計算機科學與技術專業(yè)獲得博士學位，現(xiàn)為湖南大學信息科學與工程學院副教授，CCF會員，主要研究領域為大數(shù)據(jù)，數(shù)據(jù)流處理，人工智能。

GAO Hui was born in 1993.She is an M.S.candidate at Hunan University.Her research interests include data mining and stream processing.

高慧（1993—），女，湖南張家界人，湖南大學信息科學與工程學院碩士研究生，主要研究領域為數(shù)據(jù)挖掘，數(shù)據(jù)流處理。

CHEN Xuanling was born in 1991.She is an M.S.candidate at Hunan University.Her research interests include data mining and stream processing.

陳炫伶（1991—），女，山西運城人，湖南大學信息科學與工程學院碩士研究生，主要研究領域為數(shù)據(jù)挖掘，數(shù)據(jù)流處理。

Traffic Prediction Method Using Structure Varying Dynamic Bayesian Networks*

WANG Yongheng+,GAO Hui,CHEN Xuanling
College of Information Science and Engineering,Hunan University,Changsha 410082,China
+Corresponding author:E-mail:wyh@hnu.edu.cn

The rapid development of Internet of things(IoT)and in-stream big data processing technology brings new opportunity to intelligent transportation system(ITS).Traffic flow prediction is the key issue of ITS.In traffic flow prediction,one fixed model cannot get excellent performance under different environments.Predicting models should also be updated according to data stream.In order to resolve these problems,this paper proposes a traffic prediction method based on structure varying dynamic Bayesian network.Based on complex event processing,this method uses context clustering to partition historical data and uses online clustering to support the update of clusters.A search-score method is used to learn the structure of Bayesian network and Gaussian mixture model is used for approximate inference of Bayesian network.When predicting at run time,appropriate model or model composition are selected based on current context.The experiments on both real and simulation data show that the proposed method has better performance than popular methods currently used.

intelligent transportation system;traffic flow prediction;complex event processing;structure varying dynamic Bayesian network

10.3778/j.issn.1673-9418.1608043

A

TP391

*The National Natural Science Foundation of China under Grant No.61371116(國家自然科學基金).

Received 2016-07,Accepted 2016-09.

CNKI網絡優(yōu)先出版:2016-09-08,http://www.cnki.net/kcms/detail/11.5602.TP.20160908.1047.024.html

WANG Yongheng,GAO Hui,CHEN Xuanling.Traffic prediction method using structure varying dynamic Bayesian networks.Journal of Frontiers of Computer Science and Technology,2017,11(4)：528-538.