上下文敏感的復雜事件預測方法研究

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

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

1 引 言

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

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

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

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

2 系統架構

2.1 總體結構

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

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

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

圖1 系統架構Fig.1 System architecture

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

3 狀態預測

3.1 事件上下文聚類

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

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

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

?截斷內核:

(1)

其中,x(x)定義為:

(2)

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

(3)

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

(4)

其中r函數為距離的權值,同樣Cy到Cx的距離為:

(5)

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

(6)

?高斯內核:

(7)

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

2) 最小距離δi:

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

(8)

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

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

(9)

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

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

(10)

λj(j=1,2,…,n)是n個約束式的拉格朗日乘子,對輸入參量求導,使公式(9)達到最小的必要條件為:

(11)

(12)

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

3.2 基本預測方法

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

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

圖2 適應性貝葉斯網絡模型Fig.2 Appropriate Bayesian network model

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

(13)

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

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

(14)

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

(15)

3.3 適應性貝葉斯網絡學習方法

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

算法1.獲取結點對應的候選集

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

輸出:Ni為結點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

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

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

(16)

3.4 多貝葉斯模型組合

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

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

(17)

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

(18)

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

(19)

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

(20)

這是每個模型的權值.使用交叉檢驗分布,可以對公式(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方法的關鍵是找到獨立的樣本序列.采用馬爾可夫鏈θ0,θ1,…,θn,序列的每個值只依賴于它前面的值.當滿足一定的條件時,無論序列的初始值取什么,在迭代m次之后序列都將收斂于目標靜態分布p().那么隨后的迭代生成的樣本θ(t):t=m+1,…,n就可以作為MCMC的獨立樣本.

4 實驗結果與分析

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

圖3 系統實現框架Fig.3 System implementation framework

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

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

圖4 PeMS數據預測結果Fig.4 Prediction result for PEMS data

圖5 SUMO數據預測結果Fig.5 Prediction result for SUMO data

5 結束語

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