耿少峰,王永恒,李仁發(fā),張 佳,宋秉華 ,郭曉曦

1(湖南大學 信息科學與工程學院,長沙 410082) 2(集美大學 計算機工程學院,福建 廈門 361021) 3(湖南大學 工商管理學院,長沙 410082) E-mail:sfgeng@163.com

1 引 言

近年來,隨著信息物理融合系統(tǒng)(Cyber Physical System,CPS)的廣泛應用,如何有效的實時處理CPS應用中所產(chǎn)生的大量且種類不同的數(shù)據(jù)是人們當前面對的主要問題.復雜事件處理(Complex Events Processing,CEP)[1-3]是大數(shù)據(jù)流實時處理中的一種重要技術(shù).在CPS應用中,由各種各樣的設備直接生成的數(shù)據(jù)稱為原始事件.一般情況下原始事件中的語義信息非常有限,并不能直接交由高層系統(tǒng)來處理.CEP可以根據(jù)一些模型(如有限自動機模型、有向圖模型、Petri網(wǎng)模型和匹配樹模型等)實時的將這些數(shù)量巨大的簡單原始事件進行解釋和結(jié)合,從中得到有價值的高層次復雜事件.

基于復雜事件數(shù)據(jù)的預測分析(Predictive Analytics,PA)能夠?qū)Λ@取的復雜事件建立預測模型,然后根據(jù)歷史事件數(shù)據(jù)對被觀測系統(tǒng)的某些屬性進行預測,對CPS應用有著非常重要的意義.近年來貝葉斯網(wǎng)絡[8-10]和神經(jīng)網(wǎng)絡(特別是深度神經(jīng)網(wǎng)絡)在預測模型中占據(jù)重要位置.其中貝葉斯網(wǎng)絡及其變種能夠很好的融合領域知識和數(shù)據(jù),支持不完整數(shù)據(jù)的處理及因果分析.

目前復雜事件處理和預測分析的融合還面臨著一些挑戰(zhàn).首先傳統(tǒng)的分析預測方法大多是應用在數(shù)據(jù)庫領域,這意味著所有的數(shù)據(jù)在任何時刻都是可用的.但在CEP中,系統(tǒng)只能處理單次傳遞的數(shù)據(jù),無法控制隨時間到達的樣本的順序.其次,一個固定的模型無法在不同的環(huán)境下都具備良好的預測性能[4].混合模型方法在一定程度上能夠避免在環(huán)境變化時出現(xiàn)糟糕的預測結(jié)果.但模型組合方法無法確保在各種環(huán)境下能夠得到最好的結(jié)果.另外隨著CPS和移動計算技術(shù)的發(fā)展,多種環(huán)境的上下文信息都能夠?qū)崟r獲取.但現(xiàn)有的預測方法往往只能根據(jù)有限的信息進行預測,并沒有綜合考慮各種實時的上下文信息.

針對上述問題,本文提出了一種以面向CPS不確定性事件流的復雜事件處理技術(shù)[13]為基礎的上下文敏感預測方法(Context-aware Prediction Method for Complex Event,CPMCE).該方法將經(jīng)過復雜事件處理后的數(shù)據(jù)通過上下文聚類進行劃分,針對不同的數(shù)據(jù)學習對應的貝葉斯網(wǎng)絡模型,可實現(xiàn)根據(jù)上下文來選擇合適的模型或模型組合進行預測.

2 系統(tǒng)架構(gòu)

2.1 總體結(jié)構(gòu)

系統(tǒng)總體結(jié)構(gòu)如圖1所示.原始數(shù)據(jù)流經(jīng)過概率復雜事件處理引擎的處理,從而得到有意義的高層復雜事件[13].其中PEPA(Probabilistic Event Processing Agent)為概率事件處理器[16],它負責處理由底層設備產(chǎn)生的原始數(shù)據(jù)流,然后生成概率復雜事件并把他們保存在歷史數(shù)據(jù)庫中.模型學習時首先對歷史數(shù)據(jù)按時間片進行劃分,然后以時間片為單位,根據(jù)事件上下文進行聚類,對每個獲得的聚簇分別學習對應的貝葉斯網(wǎng)絡結(jié)構(gòu)和參數(shù).在實時預測時,根據(jù)當前上下文適應性選取貝葉斯網(wǎng)絡模型或模型組合進行預測.

2.2 復雜事件處理和事件上下文

CEP中的事件類型由一組具有相同語義和結(jié)構(gòu)的事件規(guī)則構(gòu)成.每個事件對象都是一個事件類型的實例.一個事件類型可以表示為原始事件或復雜事件.原始事件可以用三元組表示,其中A為事件屬性的集合,T為事件發(fā)生的時標,Pr為事件的概率.復雜事件是由原始事件或者復雜事件按照一定的運算歸則形成的事件,表示為,其中E是復雜事件的組成元素,R為事件合成規(guī)則.主要的復雜事件規(guī)則包括ALL、ANY、COUNT和SEQ[3].

圖1 系統(tǒng)架構(gòu)Fig.1 System architecture

在事件處理領域,上下文可以定義為一些特殊的條件,根據(jù)這些條件對事件實例進行劃分,并進行關(guān)聯(lián)處理.事件上下文有多種類型,例如“車輛A周圍1公里范圍發(fā)生的事件”是一個距離上下文,“1號公路上車輛的行駛狀態(tài)為緩慢”是一個狀態(tài)上下文.上下文的獲取一般有兩種形式.一種是簡單上下文,可以直接通過事件的屬性來獲取,另外一種是復雜上下文,需要通過定義復雜事件來獲取.現(xiàn)實世界中上下文的表示往往是模糊的.例如“一輛行駛速度很快的藍色的轎車”,其中“速度很快”、“藍色”和“轎車”都是模糊的概念.本文采用模糊本體的方法對上下文建模[5].

3 狀態(tài)預測

3.1 事件上下文聚類

對于同種類型的事件數(shù)據(jù),當系統(tǒng)處于不同上下文狀態(tài)時,數(shù)據(jù)可能符合不同的模型.上下文的聚類方法可以對事件進行劃分,為不同的事件匹配合適的模型.傳統(tǒng)的FCM算法要求事先確定聚類類別數(shù),然而在某些應用環(huán)境中(例如道路交通領域),事先很難確定上下文聚類的種類個數(shù),如果類別數(shù)目給定不準確,則算法會產(chǎn)生誤導,也就破壞了算法的無監(jiān)督性和自適應性.本文采用改進的FCM算法:首先由快速搜索查找密度峰值聚類算法(Clutering by fast search and find of density peaks,CSFDP)[6]確定聚類中心,然后結(jié)合FCM對歷史數(shù)據(jù)進行上下文聚類.

待聚類的上下文數(shù)據(jù)集S={x1,x2,…,xn},對于S中的任何一個數(shù)據(jù)點xi,可以為其定義兩個量:局部密度ρi和距離δi.

1)局部密度ρi:包括截斷內(nèi)核(Cut-off kernel)和高斯內(nèi)核(Gaussian kernel)兩種計算方式.

?截斷內(nèi)核:

(1)

其中,x(x)定義為:

(2)

dij表示數(shù)據(jù)點xi和xj之間的距離,dc為截斷距離,需要事先指定.由公式(1)可知,ρi表示的是S中與xi間距離小于dc的數(shù)據(jù)點的個數(shù).上下文表示的模糊本體是一個層次結(jié)構(gòu),數(shù)據(jù)點間的距離基于他們在層次結(jié)構(gòu)中的距離進行定義:

(3)

其中αi和αj分別是兩個上下文Ci和Cj的權(quán)值,Oij是兩者之間在本體層次結(jié)構(gòu)中的距離.一個事件可以對應多個上下文,為了對事件上下文集合進行距離比較,設事件x的上下文為Cx=(cx1,…,cxm),事件y的上下文為Cy=(cy1,…,cym),首先對每個cxi∈Cx,找到cyj滿足minCyi(D(Cxi,Cyj)).然后Cx到Cy的距離可定義為:

(4)

其中r函數(shù)為距離的權(quán)值,同樣Cy到Cx的距離為:

(5)

最后可以得到Cx到Cy的距離:

(6)

?高斯內(nèi)核:

(7)

高斯內(nèi)核是類似于譜聚類中的高斯核函數(shù)的形式,在譜聚類中,高斯核函數(shù)一般用來計算兩個點之間的相似度.高斯內(nèi)核的引入,很顯然考慮到了1個數(shù)據(jù)點與所有數(shù)據(jù)點之間的關(guān)系來決定其密度.相對于截斷內(nèi)核,高斯內(nèi)核產(chǎn)生沖突(即不同的數(shù)據(jù)點具有相同的局部密度值)的概率更小,這樣提高了整個聚類的魯棒性.

2) 最小距離δi:

設{q1,q2,…,qn}是表示{ρ1,ρ2,…,ρn}的一個降序排列下標序,則距離可定義為:

(8)

由公式(8)可知,當點xi具有最大局部密度時,δi表示S中和xi距離最大的數(shù)據(jù)點與xi間的距離;否則,δi表示在所有局部密度大于xi的數(shù)據(jù)點中,與xi距離最小的那個數(shù)據(jù)點與xi間的距離.其中那些密度和距離相對比較大的數(shù)據(jù)點被其它點圍繞著.

對于S中的每一個數(shù)據(jù)點計算出其(ρi,δi)的值,然后按照ρ為橫軸,δ為縱軸的方式將所有的數(shù)據(jù)點標識在一張二維決策圖上.找出其中具有較大密度值和距離值的數(shù)據(jù)點作為S的初始聚類中心.由此確定的初始聚類中心采用的是定性分析,且具有主觀因素,所以未必是最優(yōu)結(jié)果.接下來根據(jù)初始聚類中心和歷史數(shù)據(jù),通過迭代過程修正聚類中心,尋找使以下目標函數(shù)取得最小值的結(jié)果:

(9)

其中V=[V1,…,Vc]為聚類中心,uij表示了第j個數(shù)據(jù)對第i類的隸屬度,m是一個取值范圍為[1,+)的模糊加權(quán)指數(shù),用來控制隸屬度矩陣U=[μij]c×n的模糊程度.表示第i個聚類中心與第j個數(shù)據(jù)點之間的距離.

用拉格朗日乘法求解公式(9),構(gòu)造目標函數(shù):

(10)

λj(j=1,2,…,n)是n個約束式的拉格朗日乘子,對輸入?yún)⒘壳髮?使公式(9)達到最小的必要條件為:

(11)

(12)

根據(jù)公式(11)和公式(12)對每一次迭代后的聚類中心以及隸屬矩陣進行適當?shù)恼{(diào)整,當相鄰兩次的聚類中心之間的變化小于預先設定的閾值ε時,則可判定該算法收斂,即得到了最佳的聚類中心和隸屬矩陣.

3.2 基本預測方法

CPS應用中,不同傳感器產(chǎn)生的事件可能適合不同的模型,甚至同類型的事件在上下文不同時也可能適用不同的模型.針對這個問題,在獲得上下文聚類相關(guān)情況的基礎上,CPMCE采用一種適應性貝葉斯網(wǎng)絡模型(Appropriate Bayesian Network,ABN)來提高預測的準確度.

ABN模型實例如圖2所示.其中包括一個狀態(tài)平面和一系列位置平面.每個平面是一個包括時間和空間兩維貝葉斯網(wǎng)絡.在狀態(tài)平面中,結(jié)點代表不同時間和空間的對象位置聚集或流量的狀態(tài)(例如某個路口車輛的擁堵狀態(tài)),邊代表狀態(tài)之間的條件概率.針對CPS應用中貝葉斯網(wǎng)絡結(jié)構(gòu)經(jīng)常變化的情況,引入適應性貝葉斯網(wǎng)絡,其中的“適應性”是指貝葉斯網(wǎng)絡的實際結(jié)構(gòu)可通過學習歷史數(shù)據(jù)得到,并可在數(shù)據(jù)變化時進行調(diào)整.每個對象位置平面代表對象在不同時間的位置及位置轉(zhuǎn)換的概率.在某個時間段內(nèi)物體移動的位置鏈就構(gòu)成了物體的移動路徑.

圖2 適應性貝葉斯網(wǎng)絡模型Fig.2 Appropriate Bayesian network model

本文將交通網(wǎng)絡視為貝葉斯網(wǎng)絡來分析預測其各個節(jié)點的流狀態(tài)(擁堵程度).圖2中節(jié)點總數(shù)為N(NT+1).其中節(jié)點(i,t)的狀態(tài)受t時刻之前多個父節(jié)點影響.設fi,t表示節(jié)點i在t時刻的流狀態(tài),pn(i,t)表示貝葉斯網(wǎng)絡中節(jié)點(i,t)的父節(jié)點的集合,NP表示pn(i,t)中節(jié)點的數(shù)量,pn(i,t)的狀態(tài)集為Fpn (i,t)={fj,s:(j,s)pn(i,t)}.根據(jù)貝葉斯網(wǎng)絡理論,網(wǎng)絡中所有節(jié)點的聯(lián)合分布可以表示為:

(13)

其中條件概率p(fi,t|Fpn(i,t))可以按照下面的公式計算:

p(fi,t∣Fpn(i,t))=p(fi,t∣Fpn(i,t))/p(Fpn(i,t))

(14)

將聯(lián)合分布p(fi,t,Fpn(i,t))使用高斯混合模型來建模[12]:

(15)

3.3 適應性貝葉斯網(wǎng)絡學習方法

本文采用一種混合型的方法來學習及更新貝葉斯網(wǎng)絡的結(jié)構(gòu).學習方法分兩步,先用基于約束的方法,根據(jù)對數(shù)據(jù)依賴的分析構(gòu)建候選集,然后用打分-搜索的方法最終確定網(wǎng)絡結(jié)構(gòu).針對圖2所示的模型特征,首先采取從位置平面數(shù)據(jù)構(gòu)建狀態(tài)平面結(jié)構(gòu)的方法.其依據(jù)是位置平面記錄了物體位置極其移動的詳細信息,而這些信息決定了系統(tǒng)總體狀態(tài)平面的結(jié)構(gòu).尋找一個節(jié)點對應的候選集的初步算法如下:

算法1.獲取結(jié)點對應的候選集

輸入:O為位置平面的對象集合,i為目標結(jié)點

輸出:Ni為結(jié)點i對應的候選集

方法:

begin

Pi←{P|P∈O^i∈Dest(P)}

foreachp∈P

fork=1 to |p|

I[p(k)]+=α|p-k|/count(p(k))

end

end

Ni←{n|n∈N^I(n)>θ}

returnNi

end

算法描述中忽略了結(jié)點路徑中的概率部分,其中Dest(P)獲取平面P中所有路徑的目標結(jié)點.I是一個影響因子數(shù)組,保存了每個其它結(jié)點到結(jié)點(i,t)的影響因子(通過條件概率表CPT計算).Count(n)函數(shù)獲取通過結(jié)點n的的所有路徑,α是一個衰減因子,θ是一個閾值.此算法在面對大量位置平面時可采用并行的方式處理數(shù)據(jù).

接下來進行搜索-打分,其基本思路是使BIC(Bayesian Information Criterion)打分函數(shù)最大化:

(16)

3.4 多貝葉斯模型組合

由于本文之前對上下文的劃分采用的是模糊聚類的方式,考慮到事件上下文的復雜性,所以允許將一個樣本劃分到多個聚簇中.在實時預測時,如果當前事件上下文和已有多個聚類比較接近,那么選擇所有符合條件的聚簇模型,通過多貝葉斯模型組合的方法進行預測[2].這是提高預測準確度的一條有效途徑.

假設有K個可能的預測模型,模型Mk有一個有mk個參數(shù)構(gòu)成的參數(shù)向量Θk=(θ1k,θ2k,…,θmk),D為數(shù)據(jù)集合.根據(jù)貝葉斯公式有:

(17)

其中p(D|Mk)為模型證據(jù),可以通過式(18)計算:

(18)

每個模型的后驗概率如下計算:

(19)

其中p(Mk)代表模型Mk的先驗分布,在對模型沒有偏好的情況下,假設每個模型具有相同的先驗概率.而p(D)與模型無關(guān),所以不同模型的質(zhì)量主要取決于p(D|Mk).公式(19)可轉(zhuǎn)化為:

(20)

這是每個模型的權(quán)值.使用交叉檢驗分布,可以對公式(18)中的p(D|Mk)進行有效評估:

(21)

其中p(yi|Mk)為:

(22)

在模型比較復雜的情況下,可以采用馬爾可夫鏈蒙特卡洛(Markov Chain Monte Carlo,MCMC)方法來近似計算.通過抽樣從θk的分布p(θk|Mk)獲得θk的一系列獨立樣本θk(t):t=1,…,T,則公式(22)可以用下式來近似:

(23)

MCMC方法的關(guān)鍵是找到獨立的樣本序列.采用馬爾可夫鏈θ0,θ1,…,θn,序列的每個值只依賴于它前面的值.當滿足一定的條件時,無論序列的初始值取什么,在迭代m次之后序列都將收斂于目標靜態(tài)分布p().那么隨后的迭代生成的樣本θ(t):t=m+1,…,n就可以作為MCMC的獨立樣本.

4 實驗結(jié)果與分析

本文實驗選取了兩種事件源:真實應用數(shù)據(jù)和交通模擬系統(tǒng).真實應用數(shù)據(jù)來自洛杉磯101公路的PeMS交通監(jiān)視網(wǎng)絡,它可以采集各種不同時間間隔的實時交通流數(shù)據(jù),主要包括交通流量(flow)、速度(speed)和占有率(Occupancy)等[15].這些真實應用數(shù)據(jù)中的交通網(wǎng)絡和事件的上下文比較簡單,因此本文還采用了開源的交通模擬系統(tǒng)SUMO[11].實驗的框架如圖3所示,用JADE(Java Agent Development Framework)框架對SUMO進行擴展來支持多Agent系統(tǒng),同時使用SUMO的TraCI接口來獲得車輛的實時位置信息,用它們來模擬GPS閱讀器.地圖中設置了15×15個路口和8萬輛汽車.為了更接近真實情景,定義了一組規(guī)則:每輛車都設置了家的位置和辦公室位置.車輛Vi在家庭和辦公室之間運行的概率是pi.這些車輛還有一定概率去其他地點.實驗使用了3臺至強E3處理器和16GB內(nèi)存的服務器當作數(shù)據(jù)處理服務器.

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

實驗中FCM的參數(shù)m取2,閾值ε取0.001,GMM中模型數(shù)M取25至30之間效果比較理想.真實應用數(shù)據(jù)選取了PeMS中I-405道路上一個觀測站在2016年3月7日至2016年3月13日的交通流數(shù)據(jù)作為模型訓練樣本.實驗選取交通狀態(tài)為事件上下文,流量、速度和占有率3個參數(shù)作為交通狀態(tài)評判的輸入變量.對于SUMO仿真數(shù)據(jù),首先多次運行系統(tǒng),盡量使系統(tǒng)出現(xiàn)各種類型的上下文,保存歷史數(shù)據(jù)并離線訓練模型.

在得到真實數(shù)據(jù)和模擬數(shù)據(jù)事件上下文后,本文將CPMCE與Pascal等人采用的貝葉斯網(wǎng)絡(BN)[9]和Huang等人采用的深度置信網(wǎng)絡(DBN)[14]進行了對比.真實數(shù)據(jù)以30分鐘為間隔進行預測,結(jié)果如圖4所示.從結(jié)果中可以看出在大部分時間內(nèi),CPMCE相比其他方法有更好的準確性,但是相差不大.原因在于車流量大約在6.5小時后相對穩(wěn)定,事件的上下文并沒有很大改變,這使得CPMCE的優(yōu)勢沒有完全發(fā)揮.模擬數(shù)據(jù)以1分鐘為間隔進行預測,結(jié)果如圖5所示.相對于真實數(shù)據(jù),模擬數(shù)據(jù)的車流量更大,而且變化更加劇烈,此處最重要的上下文變化是自由流、同步流和阻塞流間的變化.三種方法的準確度都有所下降.但是CPMCE方法相對于BN和DBN得到了更好的結(jié)果,這是因為CPMCE針對不同的事件上下文而采用了多貝葉斯網(wǎng)絡模型組合的方法.

圖4 PeMS數(shù)據(jù)預測結(jié)果Fig.4 Prediction result for PEMS data

圖5 SUMO數(shù)據(jù)預測結(jié)果Fig.5 Prediction result for SUMO data

5 結(jié)束語

本文提出了一種以復雜事件處理技術(shù)為基礎的上下文敏感預測方法.該方法以復雜事件處理為基礎,采用模糊本體對歷史事件上下文進行建模,然后通過上下文聚類來實現(xiàn)數(shù)據(jù)的劃分.針對不同的數(shù)據(jù)學習對應的貝葉斯網(wǎng)絡模型,能夠根據(jù)當前事件上下文選擇合適的模型或模型組合進行預測分析.實驗評估表明,本方法能有效的處理事件數(shù)據(jù)流,并具有良好的預測性能.本文還有一些不足之處,首先,上下文聚類中心的選擇采用的是定性分析,缺乏一種有效的自動學習方式.其次,沒有考慮并行與分布式預測處理.研究如何解決上述問題是今后工作的重點.