黄 涛，曹子宁,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系统中的输入输出轨迹进行处理，并应用于规范挖掘、模型验证之中，利用机器学习的技术挖掘混成自动机，模拟系统的行为，提高了系统的运行效率，用自动机模拟系统，减少了实际生产的资源浪费。

对于未来的工作，计划对相关技术进行进一步研究，如更好地进行分段预处理、使聚类更加精确高效、进一步改进算法，提高搜索效率等。此外，还会针对一些更加复杂的嵌入式系统进行研究，在更加复杂的系统中输入信号的复杂谓词可能会触发不同的动作，可以考虑在这一领域继续深入探讨。最后，希望将规范挖掘中混成自动机的挖掘框架进一步完善，提出更加方便高效的方法。