基于Shapelet的混成自動機規范挖掘技術

黃 濤，曹子寧,2,3，李 晴

(1.南京航空航天大學 計算機科學與技術學院，江蘇 南京 211106；2.光電控制技術重點實驗室，河南 洛陽 471023；3.軟件新技術與產業化協同創新中心，江蘇 南京 210023)

0 引 言

信息物理融合系統(Cyber-Physics System，CPS)[1-2]作為一種集成的動態系統，由硬件和軟件組成，是能夠獨立運作的構件。隨著對CPS的深入研究，學習系統的行為變得日益重要。系統的行為可以由不同的組件來表示，例如自動機或形式化語言。在實際應用過程中，常用的是自動機。自動機的規范對于指定復雜嵌入式控制系統的行為描述非常有幫助，可以對復雜的系統進行更加詳盡的描述，將行為規范化，找出一套自動機規范，相似的系統可以利用這套規范來描述，提高系統的適用性。

在信息物理融合系統的背景下，基于系統的不規范性以及較弱的可移植性和解釋性，對系統的輸入輸出軌跡進行相關處理，最后整合成混成自動機，模擬系統的行為。基于上述思路，提出了一種基于EHATSS算法從輸入輸出軌跡挖掘混成自動機的技術。該算法將系統的輸入輸出時間序列軌跡進行預處理，找出最優分割點和候選Shapelet，對所有的時間序軌跡進行分段操作，將分段完成之后的片段進行相似性標準標記，使得各分段進行分類，標記符號相同的片段分類到同一狀態集合中，然后應用EHATSS算法對這些分類過后的狀態集進行聚類操作，挖掘出離散狀態序列和變遷關系以及挖掘組成混成自動機的離散的跳躍條件和連續的流條件。將上述挖掘出的離散狀態序列、變遷關系和變遷條件整合成自動機，模擬系統的行為。為證明算法的準確性，用發動機正時系統和汽車懸掛系統兩個案列來進行解釋說明。

該文主要創新點如下：

(1)在原有技術的基礎上對相似性探測方法進行了改進—相似性標準，用來對狀態進行歸類標記，為后續聚類工作提供有效的方法。

(2)將機器學習相關方法應用于CPS系統的驗證，在聚類方法上進行了創新，結合Shapelet技術提出了EHATSS算法，可以對相關嵌入式系統進行規范挖掘，挖掘出混成自動機來模擬系統的行為，找出系統的行為規范。

1 相關工作

術語規范挖掘是由Ammons等人在文獻[3]中提出的，他們提出規范挖掘是一個推斷模型或屬性的過程。Lo和Khoo[4]提出了一種基于自動機的規范挖掘的新架構。它通過對錯誤軌跡過濾、聚類、學習和自動機合并四個功能組件的流程方法處理來實現規范挖掘。Alur等人[5]則提出了一種從應用程序編程接口(API)代碼中推理自動機的方法。Mariani和Pezz’e[6]提出了一種專門適用于程序執行的語法推理引擎k-behavior。Acharya等人[7]提出了一種從系統中挖掘有限狀態機的靜態分析方法。

作為規范挖掘中的一個分支，對系統的行為進行模擬，用混成自動機的方式為系統提出相應的行為規范，正逐步填滿傳統形式化方法難以對復雜系統進行建模的空缺。文獻[8]提出了一種從嵌入式控制系統的輸入輸出執行軌跡中挖掘基于自動機的模型的方法。它提出了一種框架，該框架分別通過識別分割、聚類、事件軌跡生成和自動機推理等步驟來分析多個輸入輸出軌跡。而且這個框架可以在技術和方法方面進行替換，有利于后續進行深入研究。文獻[9]提出了一種利用非線性網絡物理系統的輸入輸出軌跡來合成混成自動機的新方法，它利用動態時間扭曲技術和提出的算法，來合成混成自動機。它是在文獻[8]的基礎上做了進一步的實現工作，在聚類和自動機挖掘算法方面進行創新，并利用數理統計的方法挖掘出了變遷條件，用實際案例證實了提出算法的準確性。

2 預備知識

2.1 輸入輸出軌跡

信號軌跡是一個關于時間戳和值的有窮序列對：(t1,v1)(t2,v2)…(tk,vk)，輸入輸出軌跡ωi,o是一個三元組序列對，如下所示：

ωi,o=(t1,μ1,υ1)…(tn,μn,νn)，其中：

(1)ti是時間戳，?i∈[1,p]:ti∈R≥0；

(2)μi是輸入信號在時間ti時的值；

(3)νi是輸出信號在時間ti時的值。

2.2 輸入輸出軌跡分段與信息增益

(1)

其中，(tk,μk,νk)…(tl,μl,νl)表示在時間(tk,tl)內的軌跡片段。

(2)

Gain(sp)=I(D)-f(D1)I(D1)+f(D2)I(D2)

(3)

2.3 時間序列之間的距離

圖1 最佳匹配位置說明

2.4 最優分割點與時間序列Shapelet

最優分割點(Optimal Split Point，OSP)[10]，時間序列數據集D由兩個類A,B組成，對于一個Shapelet候選S，加入閾值dth(最優分割點就是一個距離閾值)，并且將D數據集 分割成兩個數據子集D1與D2，使得在D1中，對于每個時間序列對象T1,i有SubsequenceDist(T1,i，S)

(4)

Shapelet[10]，某一類別時間序列中最具有辨識性特征的一段或多段，可以很好地解釋分類結果，某種程度上，Shapelet可以比較確切地代表一個類。給定一個由A和B兩個類組成的時間序列數據集D，Shapelet(D)是一個具有最優分割點的子序列，定義如下：

Gain(Shapelet(D),dOSP(D,Shapelet(D)))

≥Gain(S,dOSP(D,S))

(5)

對于任何其他子序列S均成立。

2.5 準確性評估函數

為了形式化地定義挖掘混成自動機的問題，給出了一個評估函數，如下所示：給定兩個已經被預處理的分段軌跡集合：一個訓練軌跡集合φr={ωr1,ωr2,…,ωrn}，一個測試軌跡集合φt={ωr1,ωt2,…,ωtn}。目標是構造一個混成自動機HA，通過訓練軌跡集合φr，模擬系統在運行過程展示的離散狀態變化、連續變量的變化及系統行為，然后將測試軌跡集合φr輸入構造出的自動機，進行行為模擬，觀察實際輸出與測試輸出的差異，用如下評估函數來表示：

(6)

3 EHATSS算法及分析

在這個部分，基于時間序列Shapelet技術，提出了挖掘混成自動機[11-13]的算法EHATSS(Extracting Hybrid Automata based on Time Series Shapelet)。挖掘混成自動機的步驟由時間序列軌跡預處理、信號分段、相似性標準探測、分類[14]、聚類[15]、離散狀態序列和變遷關系挖掘以及跳躍條件、流條件挖掘組成，主要分為四大步驟：信號處理、挖掘離散狀態序列和變遷關系、挖掘離散的跳躍變遷、挖掘連續的流變遷。

3.1 EHATSS算法

算法1展現了挖掘混成自動機的程序算法。對每一個未處理的輸入輸出軌跡ω進行分段，經過分段之后得到分段集合φω，作為該算法的輸入部分。其他的輸入包括，距離閾值dth、作為聚類對比的參考類Shapelet以及組成混成自動機的states和transitions，算法將返回更新過后的字典樹trie_tree和變遷表tran_table。

Algorithm1：Extracting Hybrid Automata based on Time Series Shapelet。

1: Input: segmented_traces_sets(φω),

distance_threshold(dth),Shapelet, states, transitions

2:Output: trie_tree, tran_table

3: states←initialState()

4: tran_table←initialTransition()

5: trie_tree← null

6: trie_tree_head←null

7:for each segment inφωdo

8:Shapelet ← GenerateCandidates(seg)

9:if states is empty then

10:current_I←Gain(Shapelet,ωrest)

11:new_state←create_new_state()

12: trie_tree_head.next1← new_state

13: trie_tree_head next1.value ← current_I

14:update_ trie_tree_head.next1.I()

15:else

16:candidate_state←null

17:candidate_I←0

18:for each state in trie_tree do

19:if Dist(Shapelet(seg), state(seg))

20: state exist in trie_tree_head.nextithen

21: candidate_state←state

22: candidate_I←Gain(Shapelet,state)

23:if candidate_I≥states[i]_I then

24: trie_tree_head.nexti← candidate_state

25: update_ trie_tree_head.nexti.I()

26:end if

27: current_state←candidate_state

28:trie_tree_head.nexti←current_state

29:current_I←candidate_I

30:trie_tree_head.nexti.I←current_I

31:tran_table ← tran(current_state, state)

32:else

33: candidate_I←Gain(Shapelet,ωrest)

34: new_state←create_new_state()

35: trie_tree_head.nexti←new_state

36: tran_table←tran(new_state,

trie_tree_head.nexti)

37: update_ trie_tree_head.nexti.I()

38:end if

39:end for

40:end if

41:end for

42: for each state in state[i] do

43:Max_Difference(I_(state[i].j, state[i].k),

I_(state[i].m, state[i].n))

44: end for

45: for each transition in tran_table do

46: update_jump(transition, tran(current_state,

state)，tran(new_state, trie_tree_head.nexti))

47: end for

48: for each state in trie_tree do

49:update_flow(transition, state, current_state)

50: end for

在算法的第3～6行，初始化兩個集合，將狀態用字典樹存儲，變遷關系用變遷表來存儲，將當前的trie_tree和tran_table均置為空，字典樹的頭節點不存放任何狀態。算法的第7行是遍歷分割好的φ中的所有分段，進行狀態和變遷的挖掘。第8行，為每一個分段生成Shapelet，將Shapelet作為一個狀態類，可以看作一個分類標準，方便后面的分段歸類。在第9～14行，如果狀態集是空的，首先，計算當前的分段狀態與Shapelet之間的信息增益，ωrest為除去分段之后剩下的軌跡；然后，創造一個新的狀態，更新狀態集合，將新的狀態插入字典樹，并且更新該類狀態的信息增益的值。在這一塊引入信息增益，它表示的是軌跡的分割程度，信息增益的值越大表示分段的效果越好，越能代表這一分段的狀態，反之亦然。

第16～17行，先初始化候選狀態，然后再將候選狀態的信息增益的值置為0。第18行，遍歷字典樹中的所有狀態。后面程序的本質是將每個分段對應相應的狀態，若是狀態存在于原字典樹中，則進行細分，比較信息增益的值；若是不存在原字典樹中，則生成新的狀態，并插入字典樹中，記錄不同狀態之間的遷移，且更新遷移表以及信息增益。下面，對這個過程進行詳細的描述。第19～22行，首先計算狀態集中的每個state與該分段產生的Shapelet之間的距離Dist()，若小于規定的距離閾值且該狀態存在于字典樹中，則將該狀態置為候選狀態。計算分段產生的Shapelet與狀態之間信息增益值，并將它賦值給candidate_I。

第23～26行，是相似狀態之間的進一步比較，如果candidate_I的值大于或等于當前狀態的I值trie_tree_head.nexti.I，則用候選狀態替換狀態集合中的狀態，并且更新該狀態在狀態集中的I值。第27～31行，通過上述條件語句比較之后，將候選狀態置為當前狀態，candidate_I賦值為current_I，記錄在state與current_state之間產生的新的遷移，將新的狀態插入字典樹中，將新產生的變遷記錄在變遷表中，然后更新當前的狀態的信息增益值。第32～41行，如果該狀態不存在原始的字典樹中，則生成新的狀態并插入字典樹，且記錄新的變遷關系，更新變遷表和當前狀態的信息增益。第42～44行，是將分類狀態進行聚類，將相似狀態集合中的所有狀態進行信息增益計算，找出最適合的狀態，表示這個相似狀態集合。

3.2 時間序列分段和分類

(1)信號分段是一種時間序列分析方法，它將輸入輸出時間序列分割為一系列離散段，以揭示其源的潛在屬性。挖掘混成自動機對信號進行預處理，將每個輸入輸出軌跡分為多段，找到相鄰軌跡之間的最優分割點。在最優分割點的搜索過程中，使用滑動窗口技術對序列軌跡進行分割。首先，利用距離函數計算時間序列軌跡中每個時間序列與Shapelet之間的距離；然后，根據計算的距離大小將時間序列進行整理排序，得到新的數據序列集合，該序列集合中的距離是有序的，將相鄰的兩個時間序列之間的點作為分割點，如圖2所示，分別計算這兩個分割點的信息增益，根據分割點的信息增益來進行判別，信息增益最大的分割點就是序列集合中所有前后相近序列之間的最優分割點；最后，根據OSP將軌跡進行分割段。Eq.7利用滑動窗口技術，將輸入輸出軌跡ω進行分段，返回一個最優分割點的集合，用SPω表示。

SPω=sliding_window_algorithm(ω)

(7)

圖2 最優分割點注釋圖

3.3 挖掘離散狀態序列與變遷關系

為進行離散狀態序列和變遷關系的挖掘，算法中給出挖掘步驟如下：首先，運用文獻[10]提出算法中的公式(8)搜尋Shapelet，找出所有候選Shapelet的集合；然后，利用算法CheckCandidate(dataset D, Shapelet candidate S)檢查單個候選Shapelet的實用性，利用公式(9)計算信息增益I，信息增益的值越 大，代表分割的效果越好。基于公式(8)和(9)，通過計算比較找出了Shapelet集合，至此分段集合φω與Shapelet集合搜索完成。(1)將φω中的每一個分段與Shapelet中的Shapelet進行距離計算，結果為dω,s，當距離dω,s≤d時，將該段聚類成一種狀態，d表示距離閾值，為該分段的最優分割點；(2)當距離dω,S>d時，尋找下一個Shapelet，計算它們之間的距離，如果滿足條件則回到步驟(1)，如不滿足則繼續尋找符合的Shapelet，若均不滿足，則劃分為新的狀態，循環重復以上兩個步驟，直到所有片段歸類完成。當同一種狀態集中有多個狀態存在時，分別計算分段與該分段聚類使用的Shapelet之間的信息熵，分段與Shapelet分別作為數據集的兩類，任意選擇兩個分段，計算它們之間的信息增益，做減法處理，差值若為正值則選取減數，反之亦然。重復上述操作，直到找出信息增益的最大值，此時減數代表的狀態分段，即當前狀態集的狀態代表。至此，當前狀態集合中的狀態聚類完成。剩下狀態集合重復上述聚類操作，直到將所有狀態集合聚類完成。

Shapelets=GenerateCandidates(dataset D,

MAXLEN, MINLEN)

(8)

I=CalculateInformationGain

(distance histogram obj_hist )

(9)

3.4 挖掘離散的跳躍變遷

在算法1的第45～47行，將自動機中的變遷進行了整合，其中包括分段之后的狀態的變遷以及分段之后相似歸類的狀態之間的變遷。狀態之間的跳躍，可能是由于輸入信號的行為導致的，所以對輸入事件進行檢測，找出潛在的原因。通過比較發現，產生這種行為的原因大體上分為兩種：

(1)輸入事件的動作，即輸入事件在輸入過程中發出的動作，可能會對輸出造成影響；

(2)時間條件，系統在某一時間段內一直處于某種狀態，度過這一時間段，進入到下一狀態。輸出條件指的是，改變狀態之間的變遷關系的條件，使得當前狀態到達下一狀態，在4.1節案例中將對跳躍變遷做出具體分析。

3.5 挖掘連續的流變遷

在算法1的第48～50行，將自動機中的變遷進行了整合。流變遷是混合自動機中與狀態相關的函數，描述了當系統處于該狀態時連續變量的變化情況。流變遷表示的是，狀態在連續變化滿足某一函數表示的條件時，跳轉到另一狀態的觸發條件。推斷流變遷的目的是，按照訓練集產生函數，給定輸入值返回精確的輸出值。應用線性回歸方法來評估非線性自動機中每一個狀態分段的流變遷中方程的參數，如公式(10)所示。

y=β0+β1x1+β2x2+…+βkxk+ε

(10)

在4.1節案例中將對流變遷做出具體分析。

4 案例分析

該文將用兩個案例評估所提算法對不同系統的適用性。雖然選取的這些系統不能代表整個混成系統，但是這些系統具有一定的代表性，可以一定程度上說明算法的有效性、準確性，未來的研究可以在此基礎上進行擴展，深度挖掘。第一個案例研究是發動機正時系統，該案例基于Simulink中的內置sldemo_engine系統模型。另一個案例研究是汽車懸掛系統模型，基于Simulink的sldemo_suspn系統模型。這兩個案例運行軌跡已經應用了窗口滑動技術和Shapelet來進行最優分割點探測和信號分段。

4.1 發動機正時系統

發動機正時系統是基于Simulink的內置模型sldemo_engine，此示例介紹有關創建發動機模型的概念和詳細信息。基本模型使用Simulink的增強功能來高保真地捕獲基于時間的事件。

如圖3所示，它來源于發動機正時控制系統[8]，最上層是輸入節氣門，中間層是輸入轉矩，最下層是發動機的輸出速度。為了測試提出的方法，該案例在Simulink中收集了八條軌跡，這八條軌跡大致包含了基本的狀態和輸入動作。將這些軌跡全部輸入算法，最終整合的自動機如圖4所示。用UCR時間序列分類存檔數據集，進行分類測試，然后對這些軌跡進行分段，此時就擁有了一系列的訓練數據集。接下來對這些已經預處理過的數據進行相似性標準標記，將相同的標記歸類為同一個狀態集，接著運用提出的算法進行狀態歸類，挖掘離散狀態序列、變遷關系、跳躍條件、流條件。

圖3 運行示例軌跡

圖4所示為發動機正時系統形成的混成自動機，圖中狀態4到狀態5為外界時間輸入負載轉矩的改變引起的狀態之間的變遷，在變遷表中記錄下該變遷的條件，存儲記錄，方便其他的軌跡生成的狀態之間發生的變遷關系，具備整合的可能。如圖所示，狀態5到狀態8，改變的外部輸入條件為輸入節流，當該數值緩緩增加時，系統的速度會發生變化，隨著時間的增加，輸入節氣門趨于穩定，輸出速度漸漸穩定。

圖4 發動機正時系統生成的自動機

圖4中參數throttle，torque，time分別表示節氣門輸入、轉矩和時間。狀態0通過條件[torque:0.00→0.01,throttle:0.98→0.00]跳轉到狀態1。狀態4通過[torque:0.45→0.48]跳轉到狀態5，再通過[throttle:0.00→0.98]跳轉到狀態8；狀態4還可以通過條件[throttle: 0.00→0.98]跳轉到狀態6，再通過條件[torque:0.48→0.50,time:0.012’]跳轉到狀態8；狀態4還可以通過條件[throttle:0.00→0.98, torque:0.45→0.48]跳轉到狀態7，再通過條件[torque:0.50→0.51]跳轉到狀態8。

如圖5所示，這是通過從運行的例子中得到的自動機子集。圖中th表示輸入節氣門變化，to表示輸入轉矩，ti表示時間，圖中變量表示狀態變遷過程中，因為輸入變量的變化導致的狀態變遷。圖6表示為當狀態的連續變量在滿足流條件時發生變化的情況，其中狀態5、6的流條件分別為y5=ax5+b，y6=cx6+d，y5與y6表示輸出，x5與x6表示輸入，a、b、c、d表示相關系數。

圖5 運行軌跡中的自動機子集

圖6 更新流條件的自動機子集

為了評估生成的自動機，將一組測試軌跡輸入生成的自動機中，比較自動機的輸入和測試軌跡生成的輸出。用Eq.6的等式來計算測試軌跡輸出的代價值等于“0.022 6”。預測的輸出與實際的輸出對比如圖7所示，這張圖展示了生成的自動機的準確性。

圖7 實際輸出與測試輸出的比較

4.2 汽車懸掛系統

汽車懸掛系統是基于Simulink的內置模型sldemo_suspn，此示例說明如何對包括獨立前后垂直懸掛系統的簡化半車模型進行建模。懸掛系統模型有兩個輸入。第一個輸入是路面高度。這里的階躍輸入對應于在高度呈階躍變化的道路表面行駛的車輛。第二個輸入是由于制動或加速動作而通過車輪中心施加的水平力。此輸入僅顯示為俯仰軸的力矩，因未對縱向車體運動進行建模。

圖8 汽車懸掛系統運行軌跡

如圖9所示，通過輸入輸出運行軌跡，生成了基于汽車懸掛系統的混成自動機模型。每個狀態之間的轉換標簽表示的是跳轉條件。圖中參數h、Facc、Fdec分別表示路面高度、車身前懸掛向上增加的力、車身前懸掛向上減少的力。圖9中從狀態3轉換到狀態4，是因為發生了條件變遷，此時路面高度改變了，即(h:0->10)；狀態4跳轉到狀態5，是因為此時車身前懸掛向上減少的力發生了變化，即[Fdec:6 800->6 200]；狀態4跳轉到狀態6，是因為此時車身前懸掛向上增加的力在0.2秒之內發生了變化，即[Facc:6 800->7 000; time:0.2’]；狀態7跳轉到狀態8是因為此時車身前懸掛向上增加的力在0.15秒之內發生了變化，即[Fdec:6 700->6 750; time:0.15’]。圖9所示的基于汽車懸掛系統組合成的混成自動機，很好地模擬出了系統的行為動作。

圖9 汽車懸掛系統自動機

為了進一步解釋算法的準確性，利用公式1的評估函數來評價此次模擬出的系統的性能，對于每組輸出信號，使用EHATSS算法進行自動機學習。運用Simulink的內置模型生成了8個輸入輸出軌跡，將這些輸入輸出軌跡輸入到EHATSS的算法中，來學習系統懸掛的行為，通過計算得出，代價值為“0.116”，顯示出了算法的準確性。

5 結束語

該文提出了一種從輸入輸出軌跡中挖掘混成自動機的算法，引入了相似性標準sim_criteria，再利用文中提出的EHATSS算法進行聚類分析，挖掘出離散狀態空間和變遷條件，最后構造出混成自動機。較之文獻[9]，該算法區分于文獻中聚類全局特征的提取，選取的是局部特征，這樣的特征更具有局部代表性，使得分類更加精確。文獻[16]介紹了關于Shapelet的一元以及多元時間序列分類方法，文獻[17]將Shapelet與深度學習相結合，提出了兩種新型模型。該文利用Shapelet技術對CPS系統中的輸入輸出軌跡進行處理，并應用于規范挖掘、模型驗證之中，利用機器學習的技術挖掘混成自動機，模擬系統的行為，提高了系統的運行效率，用自動機模擬系統，減少了實際生產的資源浪費。

對于未來的工作，計劃對相關技術進行進一步研究，如更好地進行分段預處理、使聚類更加精確高效、進一步改進算法，提高搜索效率等。此外，還會針對一些更加復雜的嵌入式系統進行研究，在更加復雜的系統中輸入信號的復雜謂詞可能會觸發不同的動作，可以考慮在這一領域繼續深入探討。最后，希望將規范挖掘中混成自動機的挖掘框架進一步完善，提出更加方便高效的方法。