王永恒，高 慧，陳炫伶

湖南大學(xué) 信息科學(xué)與工程學(xué)院，長沙 410082

采用變結(jié)構(gòu)動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)的交通流量預(yù)測*

王永恒+，高 慧，陳炫伶

湖南大學(xué) 信息科學(xué)與工程學(xué)院，長沙 410082

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

智能交通系統(tǒng)；交通流量預(yù)測；復(fù)雜事件處理；變結(jié)構(gòu)動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)

1 引言

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

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

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

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

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

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

2 相關(guān)研究

2.1 復(fù)雜事件處理

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

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

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

2.2 交通流量預(yù)測

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

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

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

3 系統(tǒng)結(jié)構(gòu)

3.1 總體框架

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

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

3.2 復(fù)雜事件處理和上下文

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

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

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

Fig.2 Apart of traffic domain ontology圖2 交通領(lǐng)域本體的一部分

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

4 基本貝葉斯網(wǎng)絡(luò)預(yù)測

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

Fig.3 Bayesian network structure fortraffic flow prediction圖3 用于交通流量預(yù)測的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)

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

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

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

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

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

5 變結(jié)構(gòu)動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)預(yù)測

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

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

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

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

此聚類方法的關(guān)鍵是計(jì)算樣本之間的距離，也就是事件切片之間的距離。本文基于事件上下文來計(jì)算樣本間的距離。先考慮單個(gè)上下文屬性間的距離。表示事件上下文的模糊本體是一個(gè)層次化的結(jié)構(gòu)。兩個(gè)事件屬性結(jié)點(diǎn)ni和nj間的距離定義如下：

其中，μi()為結(jié)點(diǎn)ni上的模糊集隸屬函數(shù)；s(ni,nj)表示結(jié)點(diǎn)ni和nj在同一個(gè)進(jìn)行了模糊劃分的結(jié)點(diǎn)上（如劃分為“慢”、“中”、“快”）；K表示結(jié)點(diǎn)上模糊劃分的數(shù)量；pi表示上下文屬性對(duì)應(yīng)的結(jié)點(diǎn)ni上模糊劃分的序號(hào)（如“中”對(duì)應(yīng)的序號(hào)為2）；Lij表示模糊本體層次結(jié)構(gòu)上結(jié)點(diǎn)ni和nj之間的路徑長度。

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

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

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

對(duì)于切片間距離的計(jì)算，把切片看作事件的集合，也采用上述方法計(jì)算集合間的距離。在確定了聚簇的中心點(diǎn)以后，其他樣本點(diǎn)劃分到其附近的聚簇。由于事件上下文的復(fù)雜性，允許在劃分聚簇時(shí)把樣本點(diǎn)劃入多個(gè)聚簇，也就是找到k個(gè)距離最近的中心點(diǎn)，然后把樣本劃分到相關(guān)的聚簇。為了使樣本在聚簇間的分布更為合理，以便貝葉斯網(wǎng)絡(luò)的學(xué)習(xí)，對(duì)于劃分到多個(gè)聚簇中的樣本，基于如下圖書館準(zhǔn)則進(jìn)行劃分的調(diào)整。

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

圖書館準(zhǔn)則2（均勻性）圖書應(yīng)該盡量均勻地分布在多個(gè)書架上。

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

假設(shè)在初始劃分時(shí)cei被劃分到了k個(gè)聚簇，計(jì)算歸一化熵如下：

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

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

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

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

最終歸一化熵定義為：

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

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

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

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

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

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

6 實(shí)驗(yàn)研究

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

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

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

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

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

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

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

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

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

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

3種方法在SUMO仿真系統(tǒng)上的誤差百分比如圖8所示?？梢钥闯?，和PEMS的數(shù)據(jù)相比，總體上3種方法的誤差都有所增大。原因是SUMO仿真系統(tǒng)的數(shù)據(jù)有更多的上下文變化，從而加大了預(yù)測的難度。同時(shí)可以看出，SVDBN和其他兩種方法的誤差進(jìn)一步拉開了差距，體現(xiàn)出更明顯的優(yōu)勢。原因是SVDBN的適應(yīng)變化能力更好地體現(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種方法針對(duì)不同時(shí)間間隔進(jìn)行預(yù)測的平均準(zhǔn)確度對(duì)比情況如圖9所示。圖中可以明確體現(xiàn)出，無論在PEMS數(shù)據(jù)還是在SUMO仿真數(shù)據(jù)上，SVDBN的平均準(zhǔn)確度均明顯高于BN和DBN兩種方法。DBN的平均準(zhǔn)確度略高于BN，但并無明顯差異。當(dāng)預(yù)測時(shí)間間隔加大時(shí)，每種方法的平均準(zhǔn)確度都下降。原因是時(shí)間間隔加長會(huì)增加更多的未觀測數(shù)據(jù)，從而難以實(shí)現(xiàn)準(zhǔn)確預(yù)測。

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

7 結(jié)論與下一步工作

Fig.9 Accuracy of 3 methods for different time spans圖9 3種方法預(yù)測不同時(shí)間范圍時(shí)的準(zhǔn)確度

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

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

[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.

附中文參考文獻(xiàn)：

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

[20]史建國,高曉光.變結(jié)構(gòu)離散動(dòng)態(tài)貝葉斯網(wǎng)絡(luò)的快速推理算法[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年于國防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)獲得博士學(xué)位，現(xiàn)為湖南大學(xué)信息科學(xué)與工程學(xué)院副教授，CCF會(huì)員，主要研究領(lǐng)域?yàn)榇髷?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—），女，湖南張家界人，湖南大學(xué)信息科學(xué)與工程學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)閿?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—），女，山西運(yùn)城人，湖南大學(xué)信息科學(xué)與工程學(xué)院碩士研究生，主要研究領(lǐng)域?yàn)閿?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(國家自然科學(xué)基金).

Received 2016-07,Accepted 2016-09.

CNKI網(wǎng)絡(luò)優(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.