异常检测算法-Time2Graph

Time2Graph提出了一种可解释的时间序列表示学习的方法

在Time2Graph里，寻找出最优的shapelet时，需要去计算shapelet与时序样本之间的距离。欧式距离只能度量两个长度相等的序列，而无法适用于长度不等的序列。因此我们需要使用一种可以计算变长序列之间距离的方法，因此在了解Time2Graph之前我们需要先学习一下DTW（Dynamic Time Warping）。

DTW算法

DTW最开始运用于比较两段语音之间的相似性，假设我们用数字表示音调高低，例如某个单词发音的音调为1-3-2-4。现在有两个人说这个单词，A在前半部分拖长，其发音为1-1-3-3-2-4；B在后半部分拖长，其发音为1-3-2-2-4-4。这两种发音在我们的认知里相似性应该是很高的（都是同一个单词的发音），但是如果我们使用欧式距离来计算两种发音的距离：

$dist(A,B)=|A(1)-B(1)|+|A(2)-B(2)|+|A(3)-B(3)|+|A(4)-B(4)|+|A(5)-B(5)|+|A(6)-B(6)|$

$=|1-1|+|1-3|+|3-2|+|3-2|+|2-4|+|4-4|$

$=0+2+1+1+2+0=6$

DTW算法允许一个时序中的点可以与另外一个时序中多个点对应，因此即使两个序列长度不一致，DTW算法也可以计算两者的距离。对于上述发音的例子，DTW的对应关系可以如下图所示：

v2-72ba59b88c66f2d2f988af6e0278286a_1440w.jpg

因此在DTW的对应关系下，A发音与B发音的距离应该为

$dist(A,B)=|A(1)-B(1)|+|A(2)-B(1)|+|A(3)-B(2)|+|A(4)-B(2)|+|A(5)-B(3)|+|A(5)-B(4)|+|A(6)-B(5)|+|A(6)-B(6)|$

$=|1-1|+|1-1|+|3-3|+|3-3|+|2-2|+|2-2|+|4-4|+|4-4|=0$

我们把一个序列的一个时刻的点与另外一个序列中多个连续时刻点对应的做法称之为时间规整（Time Warping）。

我们使用一个6*6的矩阵M来表示序列A与序列B之间的距离，$M(i,j)$代表$A_i$与$B_j$之间的距离

v2-cb7847982b803b42c745cab86489ee71_1440w.jpg

上图中，对角线的灰色虚线代表了欧式距离，而红色箭头代表了DTW。

总结下来，DTW算法流程如下所示：

  1. 构建两个序列的距离矩阵；
  2. 从矩阵的左上角到右下角，找到距离之和最短的路径；

在DTW算法中，路径的上一个元素必须是下列三种之一：

  1. 当前元素相邻左边的元素(i,j-1)；
  2. 当前元素相邻上方的元素(i-1,j)；
  3. 当前元素相邻左上角的元素(i-1,j-1)；

DTW的实现主要是用动态规划来做，它的状态转移方程为：$f(i,j)=Min(f(i-1,j-1), f(i-1,j), f(i,j-1))+M(i,j)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def solution(matrix):
    row_nums = len(matrix)
    col_nums = len(matrix[0])

    result = np.zeros([row_nums, col_nums])
    result[0][0] = matrix[0][0]
    for i in range(1, row_nums):
        result[i][0] = result[i - 1][0] + matrix[i][0]
    for j in range(1, col_nums):
        result[0][j] = result[0][j - 1] + matrix[0][j]

    for i in range(1, row_nums):
        for j in range(1, col_nums):
            result[i][j] = min([result[i - 1][j], result[i][j - 1], result[i - 1][j - 1]]) + matrix[i][j]
    return result[-1][-1]

Time2Graph

Time2Graph主要提出了一种可解释的高效时间序列建模方法，也就是如何在一段时间序列中提取出具有代表性的特征片段。通过提取的shapelet来为分类任务服务，并且shapelet在时序分类任务中具有着良好的可解释性。对于传统的基于shapelet的时序方法，它们有一个共同的缺点就是忽略了shapelet在不同时间序列的动态性。作者基于此来设计了动态的Time-aware shapelet，定义了shapelet evolution graph来获取shapelet在时间维度的动态变化。

shapelet的提取

文章定义了两个因子，来衡量在不同阶段shapelet的影响力。第一个是局部因子$w_n$，它主要用于在衡量shapelet与时序片段s之间的距离时，控制shapelet的每一个元素的权重。因此，shapelet与时序片段s的距离为：

$d(v,s|w)=\tau(v,s|a^*,w)=(\sum^p_{k=1}w_{a^_1(k)}(w_{a^1(k)}-s{a^_2(k)})^2)^\frac 12$

其中$a^*$是通过DWT算法找到的最佳对齐方式。

第二个是全局因子，用于衡量同一个shapelet对于不同时序片段的重要程度，因此shapelet和整个时序的距离为：

$D(v,t|w,u)=\underset{1\le{k}\le{m}}{min}u_k*d(v,s|w)$

其中t是整体的时间序列被划分为m个时序片段的集合，$t={s_1,…,s_m}$。通过给定一个分类任务，建立一个监督学习方法，从候选的shapelet中学习出最佳的shapelet以及参数w和u，shapelet候选集生成算法如下所示：

1616490537158

当我们需要K个shapelet作为候选集时，算法首选选取时序片段中距离集合T中心最近的子序列作为候选集的第一个shapelet，然后再从剩下的集合中挑选离第一个shapelet距离最远的作为第二个shapelet，重复以上步骤，直到挑选出K个候选集算法结束。

而当得到了shapelet的候选集之后，对于每一个shapelet，我们可以通过最小化目标函数：

$L=-g(S_{pos}(v,T),S_{neg}(v,T))+\lambda||w||+\epsilon||u||$

获取到最优的参数w和u，再选出目标函数最小的前K个shapelet。

Shapelet进化图

在获取到了Shapelet之后，为了刻画Shapelet到动态演化，通过构建一个Shapelet evolution graph，图的定义如下所示：

Shapelet evolution graph是一个带权重的有向图G=(V,E)，其中V是由K个shapelet组成，每条边$e_{ij}\in{E}$的权重$w_{ij}$代表了两个shapelet $v_i$和$v_j$被分配给连个相邻时序片段的联合概率。

图的构建算法入下图所示：

1616570730348

图首先会将筛选出的K个Shapelet作为图的顶点，然后遍历时序片段$s_i$，计算每个shapelet与时序片段$s_i$的距离，如果shapelet和时序片段的距离小于我们设定的阈值$\delta$，那么我们将这个shapelet分配给这个时序片段。通过归一化的方式，将这个时序片段到各个shapelet距离转化为概率：

$p_{i,j}=\frac {max(d_{i,}(v_{s},s_i))-d_{i,j}(v_{i,j},s_i)}{max(d_{i,}(v_{s},s_i))-min(d_{i,}(v_{s},s_i))}$

这时我们会得到每一个时序片段所属的shapelet的集合，以及每一个shapelet的概率值$p_{i,j}$，对于连续的两个时序片段，我们将对片段1和片段2所属的shapelet进行连接，边的权重为两个shapelet的概率的乘积$w_{i,j}=p_{i,j}*p_{i+1,k}$。最后我们将重复的边做合并，这样就能得到了Shapelet evolution graph

表征学习

在最后，通过使用Deep Walk算法来提取每个shapelet的特征表示，通过对于时序$t={s_1,⋯,s_m}$即对应的Shapelet ${v_{1,∗},⋯,v_{m,∗}}$和对应的概率${p_{1,∗},⋯,p_{m,∗}}$，每个Shaplet $v_{i,j}$的特征向量记为$μ(v_{i,j})$。片段$s_i$对应的嵌入向量为对应的Shapelet嵌入向量与对应的概率值加权求和：

$\Phi_i=\sum_jp_{i,j}*μ(v_{i,j}), 1\le{i}\le{m}$

再得到了每一个时序片段的特征向量后，我们可以通过训练一个分类器来判断这个时序片段是否异常。