1、简介

近年来，随着工业化和现代化进程的推进，在流程型工业场景中，通过对生产运行状态和运行环境的实时记录和感知，积累并产生了大量的工业时序数据，这些数据往往存在量级大、测点多、时滞大等特点。通过对多维时间序列数据的分析和预测，能够对系统的运行状态实现控制、分析和优化。

流程工业系统往往涉及一系列设备和工序步骤，工业时序数据之间，各测点相互影响，并且事件有先后之分，这给时间序列预测任务增加了相当大的难度，因此在进行时间预测任务之前，需要先对时间序列之间的相关性进行度量，发现他们之间相似的规律和特征，选择相似度较高的特征和序列进行研究，进而有效提高时间序列预测的精度和效率。

时间序列相关性的定义由 Agrawal等在1993年提出, 描述如下：

假设给定两时间序列 S1、S2，和一个相关性度量函数 Dist(S1, S2)。如果序列 S1 和 S2 满足Dist(S1, S2)<ε, 则称时间序列 S1 和 S2 是相关的。其中ε是时间序列相关的阈值. Dist(S1, S2) 表示 S1 与S2 的某种距离, 通过这种距离来度量两者之间的相关性。

本文主要介绍了两种时序数据相关性分析的方法：DTW和coFlux

2、动态时间规整Dynamic Time Warping（DTW）

DTW利用动态规划DP（dynamic programming）的方法来计算两个时间序列的相似度，通过对时间序列在时间轴上自动warping扭曲，进行延伸和缩短，使得两个序列的形态尽可能一致，从而计算得到最大可能的相似度。直观地来看，如图1所示，时间序列上的点不再是一一对应（左图），而是会出现“一对多”、“多对一”的情况（右图）。

图1 欧几里得距离(左)与DTW距离(右)的对应方式[5]

图1右图中的绿色和蓝色线条表示两个不同的时间序列，红色线条连接两个序列之间相似的点。DTW使用所有这些相似点之间的距离的和，称之为归整路径距离(Warp Path Distance)来衡量两个时间序列之间的相似性。

假设有两个时间序列A（绿色序列）、B（蓝色序列），他们的长度分别是n和m，用一个n×m矩阵来对比两个序列，warping路径P={p_1,…,p_s,…,p_S } 会穿越这个矩阵，warping路径的第s个元素表示为p_s=(i_s,j_s )，i、j分别代表的是两个序列对应的点。

图2 DTW算法求解路径[5]

DTW算法的目标则是找到一条最优的warping路径P，其本质是一个优化问题，可以用数学语言表达为：

$DTW(A,B)=min\sqrt{\sum_{s-1}^{S}(p_s)}$

为了求解上述优化问题，需要满足三个约束条件：

边界条件： $p_1=(1,1)$和 $p_{S}=(n,m)$，表示两条序列首尾必须匹配，路径从左下方开始到右上方结束，确保序列整体都被考虑。

连续性： 如果 $p_s=(a,b)$且 $p_{(s-1)}=(a',b')$，则必须满足 $a-a'≤1$且 $b-b'≤1$，这条约束表示在匹配过程中多对一和一对多的情况只能匹配周围一个时间步的情况，也就是说不可能跨过某个点去匹配，只能和自己相邻的点对齐。这样可以保证wraping路径没有“跳跃”，A和B中的每个坐标都在wraping路径中出现。

单调性： 如果 $p_s=(a,b)$且 $p_{(s-1)}=(a',b')$，则必须满足 $a-a'≥0$且 $b-b'≥0$，表示warping路径不走“回头路”，确保每个坐标不会在路径中重复，warping路径一定是随时间单调递增的。

warping路径P的单调性和连续性，意味着P只有三条路可走：向右一格、向上一格、向右上一格。再加上P的边界条件，最优P的求解则变成了一个动态规划（Dynamic Programming）问题。记这个动态规划问题为γ，则有：

$γ(i,j)=d(a_i,b_j )+min{γ(i-1,j-1),γ(i-1,j),γ(i,j-1)}$

由此，DTW 算法得到了两个时间序列A、B的相似度。

3、时间序列的波动关联关系CoFlux: Robustly Correlating KPIs by Fluctuations for Service Troubleshooting

CoFlux认为，对于时间序列的预测任务，时间序列中的正常数据是比较容易预测出来的，而异常波动则由于样本量少、无规律性等因素，很难被预测。因此，时间序列的预测误差则可以被用来表示时间序列的波动特征。如图3所示，K1和K2、K3波动相关，但是与K4波动无关；K1的波动先于K2和K3发生，且波动方向相反；K2和K3的波动同时发生，且波动方向相同。

图3 (a) 6条KPI(时间序列数据)曲线、(b) KPI对应的波动特征曲线[2]

如图4所示，CoFlux的输入是两条时间序列数据KPI1、KPI2，输出是时间序列之间的波动关联关系。CoFlux直接从时间序列的历史数据出发，判断两条时间序列之间的相关性，如果相关，则进一步的分析波动发生的先后顺序以及波动方向；如果不相关，则不需要判断波动发生的先后顺序以及波动方向。

图4 CoFlux结构[2]

CoFlux的整体算法主要包括两部分：特征工程Feature Engineering和相关性测量Correlation Measurement。

特征工程Feature Engineering主要包括两个步骤：特征提取和特征放大。

特征提取主要包含了论文中选取的不同时间序列预测模型及其参数（论文中共选取7个模型，根据不同参数共构造了86个detector，因此对于一条时间序列KPI，可以得到86个波动特征），如果两条时间序列X和Y是波动相关的，那么X的波动特征序列和Y的波动特征序列也是相关的，两条波动特征可以对齐到同一个detector，也可以不做对齐，前者时间复杂度低，后者时间复杂度高。

同时为了削弱噪声的影响，论文中使用改进版的激励函数，放大时间序列的波动特征，这样就使得时间序列的波动特征更具有区别度，对波动的相关性判断也更有帮助。

相关性测量Correlation Measurement： 对两条时间序列的波动特征进行相关性判断时，需要考虑到波动特征的轻微形变以及相位差。论文中利用Cross-Correlation来解决时间序列中存在时间前后的漂移问题，对其中一条时间序列做平移操作。

CoFlux可以用来对多条时间序列数据进行分析，利用时间序列之间的波动传播关系，在已有的业务范围内构建异常波动传播链，为时序数据的异常检测提供算法基础。

附录：
[1] 陈海燕, 刘晨晖, 孙博. 时间序列数据挖掘的相似性度量综述[J]. 控制与决策, 2017, 32(1): 1-11.
[2] Su Y, Zhao Y, Xia W, et al. CoFlux: robustly correlating KPIs by fluctuations for service troubleshooting[C]//Proceedings of the International Symposium on Quality of Service. 2019: 1-10.
[3] https://zhuanlan.zhihu.com/p/32849741
[4] https://vlambda.com/wz_wzlDGD8xRo.html
[5] https://zhuanlan.zhihu.com/p/346674141