精华内容
下载资源
问答
  • 确定时间序列相似性匹配方法都没有考虑数据的不确定性,而现实世界中诸如温度传感器等设备采集到的数据往往是不确定的,并且两条不确定时间序列之间的距离也是不确定的,所以现有的确定时间序列相似性匹配方法不...
  • 时间序列相似性属于曲线相似性/曲线匹配(curve matching)领域的内容,在这一领域,有许多有用的方法,但是国内的博客上鲜有这方面的内容,因此我选取了几种常用的方法进行一下综述性的阐述。衡量相似性之前,我们...

    8d0323f8f87c84bc31428c115707bbe2.png

    时间序列相似性属于曲线相似性/曲线匹配(curve matching)领域的内容,在这一领域,有许多有用的方法,但是国内的博客上鲜有这方面的内容,因此我选取了几种常用的方法进行一下综述性的阐述。

    衡量相似性之前,我们首先定义“相似”。

    9163edb2eb8c9de3e8bbe47d138a1f71.png

    正常情况下,我们认为x,y,z是形状相似的,在这三条曲线中,我们认为y,z是最相似的两条曲线(因为y,z的距离最近)。

    ok,那我们先来看看寻常意义上的相似:距离最近且形状相似。本文主要详细介绍时间序列相似度计算的DTW算法和PLR算法。

    1. 欧式距离

    要衡量距离与形状,显然欧式距离是一个天然完美的指标,上图中我们正是基于欧式距离认为y与z是最相似的,欧式距离在诸多算法都有广泛的应用。对于长度相同的序列,计算每两点之间的距离然后求和,距离越小相似度越高(whole matching)。对于不同长度的序列,一般有两种方法处理:

    1)子序列匹配(subsequence matching): 找出长序列中与短序列最相似的部分。举个栗子,设序列

    ,序列
    ,其中
    。滚动地计算A与B的距离:

    ,然后找出所有d中的最小值,该距离所对应的A序列的索引即为A中与B最相似的部分。

    2)滑动窗口:微软在2001年在Dimensionality Reduction for Fast Similarity Search文中提出为了减少算法复杂度,可以复制B序直到与A序列等长。

    6edd4ccef787d21996b82a3e5d55af3d.png

    由于微软之后使用了独特的降维方法,且计算复杂度不是本文考虑的主要内容,因此,在涉及长短序列相似度计算的时候,本文均使用第一种方法。

    似乎时间序列的相似性度量的计算可以就此为止了,然而远非如此。

    天津大学的XIAO-LI DONG, CHENG-KUI GU, ZHENG-OU WANG在2006年Research on shape-based time series similarity measure[C]//2006 International Conference on Machine Learning and Cybernetics. IEEE, 2006: 1253-1258一文中指出了欧式距离用于衡量时间序列相似性的三个缺陷:

    • 不能辨别形状相似性
    • 不能反映趋势动态变化幅度的相似性
    • 基于点距离的计算不能反映不同分析频率的不同

    举个栗子:

    9a3a6223db1585b775f480c08185e388.png

    A与B的变化趋势几乎完全相反,A与C的变化趋势几乎完全相同。如果使用欧式距离去度量,那么结论就是A与B是最相似的。而实际上,在变化是A与C是相似的。

    为了进一步加强对欧式距离的理解,我们不妨再举一个简单的例子:

    4772799e923fb08cf1ccc0d7c60f26a7.png

    正常来说,我们认为与y1最相似的是y3,实际上,y3就是y1向下平移得到的。然而欧式距离告诉我们,距离y1最近的是y2。

    下面是使用Python进行模拟的源代码:

    import numpy as np
    import matplotlib.pyplot as plt
    x=np.arange(0,np.pi*2,0.1)
    y1=np.sin(x)
    y2=np.cos(x)-2
    y3=y1-2
    plt.plot(y1)
    plt.plot(y2)
    plt.plot(y3)
    plt.legend(['y1','y2','y3'])
    def dis(x,y):
        return(sum(x-y)**2)
    dis(y1,y2)
    Out[15]: 15831.914509398732
    
    dis(y1,y3)
    Out[16]: 15876.0

    欧式距离对形状的度量如此糟糕,有没有更好的模型能度量形状呢?

    2. 模式距离Pattern distance

    首先引入一个算法,PLR(piecewise linear representation)分段线性表示。

    一个时间序列,无非有三种状态:上升、下降和不变,我们将这种状态对应表示为

    。假设有某个长度为S的序列,我们将其等分为K段。对于每一段计算一个斜率,斜率为正表示上升,为负表示下降,为0表示不变。

    我画了一个草图,可能emm……不是很美观。

    89954916062c064857faf0c5799f2fbd.png

    那么我们就可以将这个序列表示为[1,1,0,-1...]这样的序列,将相邻的相同模式进行合并,我们得到[1,0,-1...]的序列。这就是PLR算法。

    关于PLR算法的点的分割,为了便于说理,我这里直接用的是等分的方式,然而观察上图可知,第三个模式表示为了0,实际上第三个模式是一个尖峰,是先上升后下降的,所以等分切割的方法并不科学。

    KEOGH E. 在Fast similarity search in the presence of longitudinal scaling in time series data bases中提出的自底向上的搜索方法很好的解决了这个问题,感兴趣的读者可以自行了解。

    因为我们将相邻的相同模式进行了合并,所以我们得到的模式序列一定是1,-1,0间隔排列的,每一个模式可能跨越了不同的时间长度,在合并模式后,序列S1可能有N个模式,S2可能有M个模式。现在我们要将他们等模式数化

    9b60e2308a3c5d20cacccdb6adcf8d10.png

    如上图所示,经过PLR后,我们将S1,S2表示为:

    分表表示S1,S2的第i,j个模式,即
    ,t表示时间,且无论怎么切割,最后的终点都是相等的,即
    。结合上图,具体一点就是:

    等模式数化后将他们变形为:

    说白了就让他们使用共同的分割点,以获得最后长度相等的模式序列。

    OK现在我们已经完全定义好了何为模式,接下来我们计算距离。这里我们使用绝对值距离,当然使用欧式距离也是可以的。模式距离公式为:

    ,显然
    ,距离越靠近0,表示模式越相似;越靠近2,表明模式越不相似。把所有的模式距离加起来即时间序列的模式距离:

    嗯……目前为止看起来还不错。但是需要注意的是,每一个模式可能跨越了不同的时间长度,而一个模式持续时间越长,它包含整个序列的信息就越多,这启发我们需要进行加权。因此:

    ,其中
    为第i个模式所跨越的时间长度,
    为总时间长度。

    3. 形状距离shape distance

    在模式距离的基础上,XIAO-LI DONG, CHENG-KUI GU, ZHENG-OU WANG提出了形状距离,进一步提升了度量效果。该算法于2006年在国际机器学习与控制会议上提出。

    如果理解了pattern distance的计算,那么理解shape distance将会非常简单,因为shape distance归根到底、总而言之就是加了一个振幅的改变量并重新设定了模式序列。

    假设我们已经得到了等模式数化后的序列:

    设振幅amplitude改变量序列为A,则:

    ,就是我们每一个分割区间的端点对应的序列值值差,那么我们可以得到:

    形状距离的最终计算公式为:

    ,同样
    为时间权重。注意原序列S有N个点,模式序列和振幅改变量序列都是只有N-1个点。而这里的模式m也要重新定义。

    下面以股票为例进行说明。我们认为股票的价格走势通常有七种状态:{加速下降,水平下降,减速下降,不变,减速上升,水平上升,加速上升},我们用模式

    来描述这一点。

    现在我们设定一个阈值th来帮助我们区分这7种状态,设Ki表示通过PLR划分后的第K段直线的斜率,还记得在模式距离中怎么设定模式的吗?

    如果斜率小于0,则表示下降,记为-1;斜率大于0,则表示上升,记为1;如果斜率等于0,则表示不变,那么记为0。

    现在情况稍微复杂了一些,因为我们引入了更多的模式(7种)。

    • 此时属于{-3,-2,-1}中的一种,那如何来知晓这支股票是加速下降、水平下降还是减速下降呢?斜率的改变量可以帮助我们,如果下一期斜率的改变量小于0,那说明斜率在递减,直线变得更陡峭了,是加速下降的,因此设为-3模式。如果
      ,那么是水平下降的,设为-2。如果
      ,说明是减速下降的,设为-1。
    • 如果斜率的在这个范围内,那么就认为是近似不变的,设为0。
    • 以此类推。

    用一张表来总结一下:

    a31daace1b722af4c3ef3adaedf22626.png

    形状距离公式是满足以下四个距离定理的:

    14192c71228a789eedad833d1bfd6e86.png

    此外,为了提高模型的准确度,较少绝对值的差异对整个模型的影响,一般需要对原序列进行标准化处理。完整的算法流程图如下:

    b4e907a98b8c7b0aa99fb4371a837abd.png

    形状距离由于加入了更多的模式,使得距离的度量更加精确,效果会好于模式距离。


    4. DTW

    讲了这么多距离,有没有更简单的方法来度量时间序列的相似性呢?相关系数可以吗?

    相关系数是一个非常优美的指标,不仅能衡量相关性,也能衡量相似性,但是在时间序列中一般不使用相关系数衡量相似性,这是因为它不能解决图形平移的问题。

    还是举个栗子~

    7a70c6e95b971de8037eee57f96f344d.png

    y1与y2是平移的关系,显然与y1最相似的应该是y2,然而相关系数告诉我们是y3。

    下面是Python进行模拟的代码:

    import numpy as np
    x=np.arange(-np.pi*2,np.pi*2,0.1)
    y1=np.sin(x)
    y2=np.cos(x)
    y3=x
    plt.plot(y1)
    plt.plot(y2)
    plt.plot(y3)
    plt.legend(['y1','y2','y3'])
    
    np.corrcoef([y1,y2,y3])
    Out[57]: 
    array([[ 1.00000000e+00, -1.76804105e-04, -3.88194383e-01],
           [-1.76804105e-04,  1.00000000e+00, -1.28528471e-02],
           [-3.88194383e-01, -1.28528471e-02,  1.00000000e+00]])

    DTW(dynamic time warping)动态时间规整就是专为解决此问题而生~

    4d38958ebbf670a8c268fa5381f1b7c7.png

    DTW实际上是计算欧式距离,我们在之前讲过,欧式距离不能很好地度量形状相似性。左边这幅图更清楚地表现了这一点,按照一般欧式距离的计算方法,所有点直接对应下来。而DTW就是找到序列之间正确对应的点再计算他们的距离。而由于DTW这一出色的特质,这使得DTW在语音识别领域有着广泛的应用。因为一个音节,它可能拖的很长或很短,如何去正确地识别相似声音或音节对于语音识别至关重要。

    78798d2d71ba2a805c0dd2e21d3cbe73.png
    图源自:https://blog.csdn.net/zouxy09/article/details/9140207

    如上图所示,a对应的点应该是b而不是b',DTW的根本任务就是将点进行正确的对应。

    那正确对应的标准是什么呢?

    DTW认为,如果两个序列的点正确对应了,那么他们的距离(欧式距离)达到最小。

    OK,现在问题很简单了,就找距离最小的点。一个序列的一个点可能对应另一个序列的多个点,如果穷举出所有的可能去找出最合适的点,这在时间复杂度上属于一个NP难的问题。我们需要一个行之有效的算法——动态规划。

    由于DTW的理论比较晦涩,直接看公式让人云里雾里,为了更清楚简单地把DTW讲明白,我用Python进行一遍模拟的计算。

    简单点,说话的方式简单点~~~

    import pandas as pd
    import numpy as np
    import matplotlib.pyplot as plt
    import seaborn as sns
    x = np.array([1, 1, 2, 3, 2, 0])
    y = np.array([0, 1, 1, 2, 3, 2, 1])
    plt.plot(x,'r', label='x')
    plt.plot(y, 'g', label='y')
    plt.legend()

    954df324d70c7f3e07a16c16182de40c.png

    生成了两个长度不等的序列x,y。

    distances = np.zeros((len(y), len(x)))
    for i in range(len(y)):
        for j in range(len(x)):
            distances[i,j] = (x[j]-y[i])**2 
    distances
    Out[60]: 
    array([[1., 1., 4., 9., 4., 0.],
           [0., 0., 1., 4., 1., 1.],
           [0., 0., 1., 4., 1., 1.],
           [1., 1., 0., 1., 0., 4.],
           [4., 4., 1., 0., 1., 9.],
           [1., 1., 0., 1., 0., 4.],
           [0., 0., 1., 4., 1., 1.]])

    计算两个序列的距离矩阵。横着表示x序列,竖着是y序列,比如说第0行第0个元素1表示x序列的第0个值和y序列的第0个值的距离(Python的索引从0开始),即

    ;再比如第4行第1列的元素4(如果你的第4行第1列元素没有找到4的话,请把索引从0开始)表示x序列第1个值和y序列的第4个值间的距离,即

    我们来做个可视化,颜色越深表示距离越远,比如说最远的距离是x的第三个值和y的第0个值之间的距离。

    这里注意一下,我们的图形和距离矩阵是没有一一对应的。我们的距离矩阵中,索引0从左上角开始,图形从左下角开始。

    def distance_cost_plot(distances):
        plt.imshow(distances, interpolation='nearest', cmap='Reds') 
        plt.gca().invert_yaxis()#倒转y轴,让它与x轴的都从左下角开始
        plt.xlabel("X")
        plt.ylabel("Y")
    #    plt.grid()
        plt.colorbar()
    distance_cost_plot(distances)

    46c32eb07ab1c4a1679e8a970d0e2d74.png

    现在我们计算一个累积距离矩阵,累积距离最小是我们的最终目标。

    accumulated_cost = np.zeros((len(y), len(x)))
    accumulated_cost[0,0] = distances[0,0]
    accumulated_cost
    Out[80]: 
    array([[1., 0., 0., 0., 0., 0.],
           [0., 0., 0., 0., 0., 0.],
           [0., 0., 0., 0., 0., 0.],
           [0., 0., 0., 0., 0., 0.],
           [0., 0., 0., 0., 0., 0.],
           [0., 0., 0., 0., 0., 0.],
           [0., 0., 0., 0., 0., 0.]])
    distance_cost_plot(accumulated_cost)

    c446741c359a742d999f308bc43c60dd.png

    显然累积距离矩阵的第0行第0列=距离矩阵的第0行第0列=1,我们必须经过起点吧……如果我们一直往右走,那么累积距离距离矩阵:

    for i in range(1, len(x)):
        accumulated_cost[0,i] = distances[0,i] + accumulated_cost[0, i-1] 
    accumulated_cost
    array([[ 1.,  2.,  6., 15., 19., 19.],
           [ 0.,  0.,  0.,  0.,  0.,  0.],
           [ 0.,  0.,  0.,  0.,  0.,  0.],
           [ 0.,  0.,  0.,  0.,  0.,  0.],
           [ 0.,  0.,  0.,  0.,  0.,  0.],
           [ 0.,  0.,  0.,  0.,  0.,  0.],
           [ 0.,  0.,  0.,  0.,  0.,  0.]])
    distance_cost_plot(accumulated_cost)

    4cfb90c9966fe1b312096261e809978c.png

    如果我们一直往上走,那么:

    for i in range(1, len(y)):
        accumulated_cost[i,0] = distances[i, 0] + accumulated_cost[i-1, 0]  
    accumulated_cost
    array([[ 1.,  2.,  6., 15., 19., 19.],
           [ 1.,  0.,  0.,  0.,  0.,  0.],
           [ 1.,  0.,  0.,  0.,  0.,  0.],
           [ 2.,  0.,  0.,  0.,  0.,  0.],
           [ 6.,  0.,  0.,  0.,  0.,  0.],
           [ 7.,  0.,  0.,  0.,  0.,  0.],
           [ 7.,  0.,  0.,  0.,  0.,  0.]])
    distance_cost_plot(accumulated_cost)

    5a1d27878902cb635ebfb3ffdc4ad025.png

    好了,累积距离矩阵的计算方式已经完全明白了。在继续下去之前,必须讲明累积距离矩阵中路径的意义。我们的目标是找一条路径使得累积距离最小。

    962160bb69afdaf6938ebae8e63c0582.png
    • 从(0,0)开始,经过这个方块表示将x,y的第0个点对应起来,当然,起点是必须经过的~
    • 如果路径经过(1,0),表示将x的第1个点和y序列的第0个点对应起来。
    • 如果路径经过(1,1),表示将x的第1个点和y序列的第1个点对应起来。

    所以,路径的前进方向只有三个:向右,向上,斜右上。

    这是显然,我们的路径不能后退,如果路径向右或向上了多个方块,这表明一个序列的一个点对应了另一个序列的多个点。

    目前为止,我们已经完成了累积距离矩阵的两列的计算。对于任何其他的点,累积距离的新增只可能来自于三个方向:左边,下边,斜左下。所谓动态规划就是我每前进一步都选取使我当前行进距离最小的方向。因此,对于任何其他的点,累积距离的计算公式为:

    现在,我们把累积距离矩阵计算完整:

    for i in range(1, len(y)):
        for j in range(1, len(x)):
            accumulated_cost[i, j] = min(accumulated_cost[i-1, j-1], accumulated_cost[i-1, j], accumulated_cost[i, j-1]) + distances[i, j]
    accumulated_cost
    Out[86]: 
    array([[ 1.,  2.,  6., 15., 19., 19.],
           [ 1.,  1.,  2.,  6.,  7.,  8.],
           [ 1.,  1.,  2.,  6.,  7.,  8.],
           [ 2.,  2.,  1.,  2.,  2.,  6.],
           [ 6.,  6.,  2.,  1.,  2., 11.],
           [ 7.,  7.,  2.,  2.,  1.,  5.],
           [ 7.,  7.,  3.,  6.,  2.,  2.]])
    distance_cost_plot(accumulated_cost)

    30e0f5bb2c4054f970410bdfc873f5ef.png

    现在,最佳路径已经清晰地显示在了累积距离矩阵之中,就是图中颜色最淡的方块。

    现在,我们只需要通过回溯的方法找回最佳路径就可以了:

    path = [[len(x)-1, len(y)-1]]
    i = len(y)-1
    j = len(x)-1
    while i>0 and j>0:
        if i==0:
            j = j - 1
        elif j==0:
            i = i - 1
        else:
            if accumulated_cost[i-1, j] == min(accumulated_cost[i-1, j-1], accumulated_cost[i-1, j], accumulated_cost[i, j-1]):
                i = i - 1#来自于左边
            elif accumulated_cost[i, j-1] == min(accumulated_cost[i-1, j-1], accumulated_cost[i-1, j], accumulated_cost[i, j-1]):
                j = j-1#来自于下边
            else:
                i = i - 1#来自于左下边
                j= j- 1
        path.append([j, i])
    path.append([0,0])
    path
    Out[89]: [[5, 6], [4, 5], [3, 4], [2, 3], [1, 2], [1, 1], [0, 1], [0, 0]]
    path_x = [point[0] for point in path]
    path_y = [point[1] for point in path]
    distance_cost_plot(accumulated_cost)
    plt.plot(path_x, path_y)

    926923593777537a5db754c159dc818b.png

    在刚才,我们已经讲明,最优路径所经过的地方表示两个序列应该对应的点。

    计算这些点的欧式距离作为相似性的度量,这就是DTW。

    Reference:

    1. https://nipunbatra.github.io/blog/2014/dtw.html
    2. Dong X L, Gu C K, Wang Z O. Research on shape-based time series similarity measure[C]//2006 International Conference on Machine Learning and Cybernetics. IEEE, 2006: 1253-1258.
    3. Wang D, Rong G. Pattern distance of time series[J]. Zhejiang Daxue Xuebao(Gongxue Ban)/Journal of Zhejiang University(Engineering Science), 2004, 38(7): 795-798.
    4. Kim S, Lee H, Ko H, et al. Pattern Matching Trading System Based on the Dynamic Time Warping Algorithm[J]. Sustainability, 2018, 10(12): 4641.
    5. Keogh E, Chakrabarti K, Pazzani M, et al. Dimensionality reduction for fast similarity search in large time series databases[J]. Knowledge and information Systems, 2001, 3(3): 263-286.
    6. Mori U, Mendiburu A, Lozano J A. Distance measures for time series in R: The TSdist package[J]. R journal, 2016, 8(2): 451-459.
    7. https://blog.csdn.net/xsdxs/article/details/86648605
    8. 知乎:如何判断两条轨迹(或曲线)的相似度?
    9. 张戎的博客
    10. https://blog.csdn.net/qq_40006058/article/details/79992255
    11. https://www.cnblogs.com/tornadomeet/archive/2012/03/23/2413363.html
    展开全文
  • 时间序列相似性属于曲线相似性/曲线匹配(curve matching)领域的内容,在这一领域,有许多有用的方法,但是国内的博客上鲜有这方面的内容,因此我选取了几种常用的方法进行一下综述性的阐述。衡量相似性之前,我们...

    时间序列相似性属于曲线相似性/曲线匹配(curve matching)领域的内容,在这一领域,有许多有用的方法,但是国内的博客上鲜有这方面的内容,因此我选取了几种常用的方法进行一下综述性的阐述。

    衡量相似性之前,我们首先定义“相似”。

    正常情况下,我们认为x,y,z是形状相似的,在这三条曲线中,我们认为y,z是最相似的两条曲线(因为y,z的距离最近)。

    ok,那我们先来看看寻常意义上的相似:距离最近且形状相似。本文主要详细介绍时间序列相似度计算的DTW算法和PLR算法。

    1. 欧式距离

    要衡量距离与形状,显然欧式距离是一个天然完美的指标,上图中我们正是基于欧式距离认为y与z是最相似的,欧式距离在诸多算法都有广泛的应用。对于长度相同的序列,计算每两点之间的距离然后求和,距离越小相似度越高(whole matching)。对于不同长度的序列,一般有两种方法处理:

    1)子序列匹配(subsequence matching): 找出长序列中与短序列最相似的部分。举个栗子,设序列

    equation?tex=A%3A%5Ba_1%2Ca_2...a_n%5D ,序列

    equation?tex=B%3A%5Bb_1%2Cb_2%2C...b_m%5D ,其中

    equation?tex=n%3Em 。滚动地计算A与B的距离:

    equation?tex=d1%3D%5Csqrt%7B%28a_1-b_1%29%5E2%2B%28a_2-b_2%29%5E2%2B...%2B%28a_m-b_m%29%5E2%7D

    equation?tex=d2%3D%5Csqrt%7B%28a_2-b_1%29%5E2%2B%28a_3-b_2%29%5E2%2B...%2B%28a_%7Bm%2B1%7D-b_m%29%5E2%7D ,然后找出所有d中的最小值,该距离所对应的A序列的索引即为A中与B最相似的部分。

    2)滑动窗口:微软在2001年在Dimensionality Reduction for Fast Similarity Search文中提出为了减少算法复杂度,可以复制B序直到与A序列等长。

    由于微软之后使用了独特的降维方法,且计算复杂度不是本文考虑的主要内容,因此,在涉及长短序列相似度计算的时候,本文均使用第一种方法。

    似乎时间序列的相似性度量的计算可以就此为止了,然而远非如此。

    天津大学的XIAO-LI DONG, CHENG-KUI GU, ZHENG-OU WANG在2006年Research on shape-based time series similarity measure[C]//2006 International Conference on Machine Learning and Cybernetics. IEEE, 2006: 1253-1258一文中指出了欧式距离用于衡量时间序列相似性的三个缺陷:不能辨别形状相似性

    不能反映趋势动态变化幅度的相似性

    基于点距离的计算不能反映不同分析频率的不同

    举个栗子:

    A与B的变化趋势几乎完全相反,A与C的变化趋势几乎完全相同。如果使用欧式距离去度量,那么结论就是A与B是最相似的。而实际上,在变化是A与C是相似的。

    为了进一步加强对欧式距离的理解,我们不妨再举一个简单的例子:

    正常来说,我们认为与y1最相似的是y3,实际上,y3就是y1向下平移得到的。然而欧式距离告诉我们,距离y1最近的是y2。

    下面是使用Python进行模拟的源代码:

    import numpy as np

    import matplotlib.pyplot as plt

    x=np.arange(0,np.pi*2,0.1)

    y1=np.sin(x)

    y2=np.cos(x)-2

    y3=y1-2

    plt.plot(y1)

    plt.plot(y2)

    plt.plot(y3)

    plt.legend(['y1','y2','y3'])

    def dis(x,y):

    return(sum(x-y)**2)

    dis(y1,y2)

    Out[15]: 15831.914509398732

    dis(y1,y3)

    Out[16]: 15876.0

    欧式距离对形状的度量如此糟糕,有没有更好的模型能度量形状呢?

    2. 模式距离Pattern distance

    首先引入一个算法,PLR(piecewise linear representation)分段线性表示。

    一个时间序列,无非有三种状态:上升、下降和不变,我们将这种状态对应表示为

    equation?tex=M%3D%5C%7B1%2C-1%2C0%5C%7D 。假设有某个长度为S的序列,我们将其等分为K段。对于每一段计算一个斜率,斜率为正表示上升,为负表示下降,为0表示不变。

    我画了一个草图,可能emm……不是很美观。

    那么我们就可以将这个序列表示为[1,1,0,-1...]这样的序列,将相邻的相同模式进行合并,我们得到[1,0,-1...]的序列。这就是PLR算法。

    关于PLR算法的点的分割,为了便于说理,我这里直接用的是等分的方式,然而观察上图可知,第三个模式表示为了0,实际上第三个模式是一个尖峰,是先上升后下降的,所以等分切割的方法并不科学。

    KEOGH E. 在Fast similarity search in the presence of longitudinal scaling in time series data bases中提出的自底向上的搜索方法很好的解决了这个问题,感兴趣的读者可以自行了解。

    因为我们将相邻的相同模式进行了合并,所以我们得到的模式序列一定是1,-1,0间隔排列的,每一个模式可能跨越了不同的时间长度,在合并模式后,序列S1可能有N个模式,S2可能有M个模式。现在我们要将他们等模式数化。

    如上图所示,经过PLR后,我们将S1,S2表示为:

    equation?tex=S1%3D%5C%7B%28m_%7B11%7D%2Ct_%7B11%7D%29%2C...%2C%28m_%7B1N%7D%2Ct_%7B1N%7D%5C%7D+

    equation?tex=S2%3D%5C%7B%28m_%7B21%7D%2Ct_%7B21%7D%29%2C...%2C%28m_%7B2M%7D%2Ct_%7B2M%7D%5C%7D

    equation?tex=s_%7B1i%7D%2Cs_%7B2j%7D 分表表示S1,S2的第i,j个模式,即

    equation?tex=s_%7B1i%7D%3D%28m_%7B1i%7D%2Ct_%7B1i%7D%29 ,t表示时间,且无论怎么切割,最后的终点都是相等的,即

    equation?tex=t_%7B1N%7D%3Dt_%7B2M%7D 。结合上图,具体一点就是:

    equation?tex=S1%3D%5C%7B%281%2Ct_%7B11%7D%29%2C%28-1%2Ct_%7B12%7D%29%2C%280%2Ct_%7B13%7D%29%5C%7D

    equation?tex=S2%3D%5C%7B%28-1%2Ct_%7B21%7D%29%2C%281%2Ct_%7B22%7D%29%5C%7D

    等模式数化后将他们变形为:

    equation?tex=S1%3D%5C%7B%281%2Ct_1%29%2C%28-1%2Ct_2%29%2C%28-1%2Ct_3%29%2C%280%2Ct_4%29%5C%7D

    equation?tex=S2%3D%5C%7B%281%2Ct_1%29%2C%281%2Ct_2%29%2C%28-1%2Ct_3%29%2C%28-1%2Ct_4%29%5C%7D

    说白了就让他们使用共同的分割点,以获得最后长度相等的模式序列。

    OK现在我们已经完全定义好了何为模式,接下来我们计算距离。这里我们使用绝对值距离,当然使用欧式距离也是可以的。模式距离公式为:

    equation?tex=D%3D%7Cm_%7B1i%7D-m_%7B2i%7D%7C ,显然

    equation?tex=D%5Cin%5C%7B0%2C1%2C2%5C%7D ,距离越靠近0,表示模式越相似;越靠近2,表明模式越不相似。把所有的模式距离加起来即时间序列的模式距离:

    equation?tex=D_%7BS1%2CS2%7D%3D%5Csum_%7Bi%3D1%7D%5Ek%7Cm_%7B1i%7D-m_%7B2i%7D%7C

    嗯……目前为止看起来还不错。但是需要注意的是,每一个模式可能跨越了不同的时间长度,而一个模式持续时间越长,它包含整个序列的信息就越多,这启发我们需要进行加权。因此:

    equation?tex=D_%7BS1%2CS2%7D%3D%5Csum_%7Bi%3D1%7D%5Ekt_%7Bwi%7D%2A%7Cm_%7B1i%7D-m_%7B2i%7D%7C ,其中

    equation?tex=t_%7Bwi%7D%3D%5Cfrac%7Bti%7D%7Bt_N%7D

    equation?tex=t_i 为第i个模式所跨越的时间长度,

    equation?tex=t_N 为总时间长度。

    3. 形状距离shape distance

    在模式距离的基础上,XIAO-LI DONG, CHENG-KUI GU, ZHENG-OU WANG提出了形状距离,进一步提升了度量效果。该算法于2006年在国际机器学习与控制会议上提出。

    如果理解了pattern distance的计算,那么理解shape distance将会非常简单,因为shape distance归根到底、总而言之就是加了一个振幅的改变量并重新设定了模式序列。

    假设我们已经得到了等模式数化后的序列:

    equation?tex=S1%3D%5C%7B%281%2Ct_1%29%2C%28-1%2Ct_2%29%2C%28-1%2Ct_3%29%2C%280%2Ct_4%29%5C%7D

    equation?tex=S2%3D%5C%7B%281%2Ct_1%29%2C%281%2Ct_2%29%2C%28-1%2Ct_3%29%2C%28-1%2Ct_4%29%5C%7D

    设振幅amplitude改变量序列为A,则:

    equation?tex=A_i%3Dy_i-y_%7Bi-1%7D ,就是我们每一个分割区间的端点对应的序列值值差,那么我们可以得到:

    equation?tex=A1%3D%5C%7B%28%5CDelta%7By11%7D%2Ct_1%29%2C%28%5CDelta%7By12%7D%2Ct_2%29%2C%28%5CDelta%7By13%7D%2Ct_3%29%2C%28%5CDelta%7By14%7D%2Ct_4%29%5C%7D

    equation?tex=+A2%3D%5C%7B%28%5CDelta%7By21%7D%2Ct_1%29%2C%28%5CDelta%7By22%2C%7Dt_2%29%2C%28%5CDelta%7By23%7D%2Ct_3%29%2C%28%5CDelta%7By24%7D%2Ct_4%29%5C%7D+

    形状距离的最终计算公式为:

    equation?tex=D_%7BS1%2CS2%7D%3D%5Csum_%7Bi%3D1%7D%5Ekt_%7Bwi%7D%2A%7Cm_%7B1i%7D-m_%7B2i%7D%7C%2A%7CA_%7B1i%7D-A_%7B2i%7D%7C ,同样

    equation?tex=t_%7Bwi%7D 为时间权重。注意原序列S有N个点,模式序列和振幅改变量序列都是只有N-1个点。而这里的模式m也要重新定义。

    下面以股票为例进行说明。我们认为股票的价格走势通常有七种状态:{加速下降,水平下降,减速下降,不变,减速上升,水平上升,加速上升},我们用模式

    equation?tex=M%3D%5C%7B-3%2C-2%2C-1%2C0%2C1%2C2%2C3%5C%7D 来描述这一点。

    现在我们设定一个阈值th来帮助我们区分这7种状态,设Ki表示通过PLR划分后的第K段直线的斜率,还记得在模式距离中怎么设定模式的吗?

    如果斜率小于0,则表示下降,记为-1;斜率大于0,则表示上升,记为1;如果斜率等于0,则表示不变,那么记为0。

    现在情况稍微复杂了一些,因为我们引入了更多的模式(7种)。equation?tex=k_i%3C-th%EF%BC%8C 此时属于{-3,-2,-1}中的一种,那如何来知晓这支股票是加速下降、水平下降还是减速下降呢?斜率的改变量可以帮助我们,如果下一期斜率的改变量小于0,那说明斜率在递减,直线变得更陡峭了,是加速下降的,因此设为-3模式。如果

    equation?tex=%5CDelta%7Bk_i%7D%3D0 ,那么是水平下降的,设为-2。如果

    equation?tex=%5CDelta%7Bk_i%7D%3E0 ,说明是减速下降的,设为-1。

    equation?tex=-th%3Ck_i%3Cth%EF%BC%8C 如果斜率的在这个范围内,那么就认为是近似不变的,设为0。

    equation?tex=k_i%3Eth%EF%BC%8C 以此类推。

    用一张表来总结一下:

    形状距离公式是满足以下四个距离定理的:

    此外,为了提高模型的准确度,较少绝对值的差异对整个模型的影响,一般需要对原序列进行标准化处理。完整的算法流程图如下:

    形状距离由于加入了更多的模式,使得距离的度量更加精确,效果会好于模式距离。

    4. DTW

    讲了这么多距离,有没有更简单的方法来度量时间序列的相似性呢?相关系数可以吗?

    相关系数是一个非常优美的指标,不仅能衡量相关性,也能衡量相似性,但是在时间序列中一般不使用相关系数衡量相似性,这是因为它不能解决图形平移的问题。

    还是举个栗子~

    y1与y2是平移的关系,显然与y1最相似的应该是y2,然而相关系数告诉我们是y3。

    下面是Python进行模拟的代码:

    import numpy as np

    x=np.arange(-np.pi*2,np.pi*2,0.1)

    y1=np.sin(x)

    y2=np.cos(x)

    y3=x

    plt.plot(y1)

    plt.plot(y2)

    plt.plot(y3)

    plt.legend(['y1','y2','y3'])

    np.corrcoef([y1,y2,y3])

    Out[57]:

    array([[ 1.00000000e+00, -1.76804105e-04, -3.88194383e-01],

    [-1.76804105e-04, 1.00000000e+00, -1.28528471e-02],

    [-3.88194383e-01, -1.28528471e-02, 1.00000000e+00]])

    DTW(dynamic time warping)动态时间规整就是专为解决此问题而生~

    DTW实际上是计算欧式距离,我们在之前讲过,欧式距离不能很好地度量形状相似性。左边这幅图更清楚地表现了这一点,按照一般欧式距离的计算方法,所有点直接对应下来。而DTW就是找到序列之间正确对应的点再计算他们的距离。而由于DTW这一出色的特质,这使得DTW在语音识别领域有着广泛的应用。因为一个音节,它可能拖的很长或很短,如何去正确地识别相似声音或音节对于语音识别至关重要。图源自:https://blog.csdn.net/zouxy09/article/details/9140207

    如上图所示,a对应的点应该是b而不是b',DTW的根本任务就是将点进行正确的对应。

    那正确对应的标准是什么呢?

    DTW认为,如果两个序列的点正确对应了,那么他们的距离(欧式距离)达到最小。

    OK,现在问题很简单了,就找距离最小的点。一个序列的一个点可能对应另一个序列的多个点,如果穷举出所有的可能去找出最合适的点,这在时间复杂度上属于一个NP难的问题。我们需要一个行之有效的算法——动态规划。

    由于DTW的理论比较晦涩,直接看公式让人云里雾里,为了更清楚简单地把DTW讲明白,我用Python进行一遍模拟的计算。

    简单点,说话的方式简单点~~~

    import pandas as pd

    import numpy as np

    import matplotlib.pyplot as plt

    import seaborn as sns

    x = np.array([1, 1, 2, 3, 2, 0])

    y = np.array([0, 1, 1, 2, 3, 2, 1])

    plt.plot(x,'r', label='x')

    plt.plot(y, 'g', label='y')

    plt.legend()

    生成了两个长度不等的序列x,y。

    distances = np.zeros((len(y), len(x)))

    for i in range(len(y)):

    for j in range(len(x)):

    distances[i,j] = (x[j]-y[i])**2

    distances

    Out[60]:

    array([[1., 1., 4., 9., 4., 0.],

    [0., 0., 1., 4., 1., 1.],

    [0., 0., 1., 4., 1., 1.],

    [1., 1., 0., 1., 0., 4.],

    [4., 4., 1., 0., 1., 9.],

    [1., 1., 0., 1., 0., 4.],

    [0., 0., 1., 4., 1., 1.]])

    计算两个序列的距离矩阵。横着表示x序列,竖着是y序列,比如说第0行第0个元素1表示x序列的第0个值和y序列的第0个值的距离(Python的索引从0开始),即

    equation?tex=%281-0%29%5E2%3D1 ;再比如第4行第1列的元素4(如果你的第4行第1列元素没有找到4的话,请把索引从0开始)表示x序列第1个值和y序列的第4个值间的距离,即

    equation?tex=%EF%BC%881-3%EF%BC%89%5E2%3D4

    我们来做个可视化,颜色越深表示距离越远,比如说最远的距离是x的第三个值和y的第0个值之间的距离。

    这里注意一下,我们的图形和距离矩阵是没有一一对应的。我们的距离矩阵中,索引0从左上角开始,图形从左下角开始。

    def distance_cost_plot(distances):

    plt.imshow(distances, interpolation='nearest', cmap='Reds')

    plt.gca().invert_yaxis()#倒转y轴,让它与x轴的都从左下角开始

    plt.xlabel("X")

    plt.ylabel("Y")

    # plt.grid()

    plt.colorbar()

    distance_cost_plot(distances)

    现在我们计算一个累积距离矩阵,累积距离最小是我们的最终目标。

    accumulated_cost = np.zeros((len(y), len(x)))

    accumulated_cost[0,0] = distances[0,0]

    accumulated_cost

    Out[80]:

    array([[1., 0., 0., 0., 0., 0.],

    [0., 0., 0., 0., 0., 0.],

    [0., 0., 0., 0., 0., 0.],

    [0., 0., 0., 0., 0., 0.],

    [0., 0., 0., 0., 0., 0.],

    [0., 0., 0., 0., 0., 0.],

    [0., 0., 0., 0., 0., 0.]])

    distance_cost_plot(accumulated_cost)

    显然累积距离矩阵的第0行第0列=距离矩阵的第0行第0列=1,我们必须经过起点吧……如果我们一直往右走,那么累积距离距离矩阵:

    for i in range(1, len(x)):

    accumulated_cost[0,i] = distances[0,i] + accumulated_cost[0, i-1]

    accumulated_cost

    array([[ 1., 2., 6., 15., 19., 19.],

    [ 0., 0., 0., 0., 0., 0.],

    [ 0., 0., 0., 0., 0., 0.],

    [ 0., 0., 0., 0., 0., 0.],

    [ 0., 0., 0., 0., 0., 0.],

    [ 0., 0., 0., 0., 0., 0.],

    [ 0., 0., 0., 0., 0., 0.]])

    distance_cost_plot(accumulated_cost)

    如果我们一直往上走,那么:

    for i in range(1, len(y)):

    accumulated_cost[i,0] = distances[i, 0] + accumulated_cost[i-1, 0]

    accumulated_cost

    array([[ 1., 2., 6., 15., 19., 19.],

    [ 1., 0., 0., 0., 0., 0.],

    [ 1., 0., 0., 0., 0., 0.],

    [ 2., 0., 0., 0., 0., 0.],

    [ 6., 0., 0., 0., 0., 0.],

    [ 7., 0., 0., 0., 0., 0.],

    [ 7., 0., 0., 0., 0., 0.]])

    distance_cost_plot(accumulated_cost)

    好了,累积距离矩阵的计算方式已经完全明白了。在继续下去之前,必须讲明累积距离矩阵中路径的意义。我们的目标是找一条路径使得累积距离最小。从(0,0)开始,经过这个方块表示将x,y的第0个点对应起来,当然,起点是必须经过的~

    如果路径经过(1,0),表示将x的第1个点和y序列的第0个点对应起来。

    如果路径经过(1,1),表示将x的第1个点和y序列的第1个点对应起来。

    所以,路径的前进方向只有三个:向右,向上,斜右上。

    这是显然,我们的路径不能后退,如果路径向右或向上了多个方块,这表明一个序列的一个点对应了另一个序列的多个点。

    目前为止,我们已经完成了累积距离矩阵的两列的计算。对于任何其他的点,累积距离的新增只可能来自于三个方向:左边,下边,斜左下。所谓动态规划就是我每前进一步都选取使我当前行进距离最小的方向。因此,对于任何其他的点,累积距离的计算公式为:

    equation?tex=Accumulated+Cost+%28i%2Cj%29%3DMin%5C%7BD%28i%E2%88%921%2Cj%E2%88%921%29%2CD%28i%E2%88%921%2Cj%29%2CD%28i%2Cj%E2%88%921%29%5C%7D%2Bdistance%28i%2Cj%29

    现在,我们把累积距离矩阵计算完整:

    for i in range(1, len(y)):

    for j in range(1, len(x)):

    accumulated_cost[i, j] = min(accumulated_cost[i-1, j-1], accumulated_cost[i-1, j], accumulated_cost[i, j-1]) + distances[i, j]

    accumulated_cost

    Out[86]:

    array([[ 1., 2., 6., 15., 19., 19.],

    [ 1., 1., 2., 6., 7., 8.],

    [ 1., 1., 2., 6., 7., 8.],

    [ 2., 2., 1., 2., 2., 6.],

    [ 6., 6., 2., 1., 2., 11.],

    [ 7., 7., 2., 2., 1., 5.],

    [ 7., 7., 3., 6., 2., 2.]])

    distance_cost_plot(accumulated_cost)

    现在,最佳路径已经清晰地显示在了累积距离矩阵之中,就是图中颜色最淡的方块。

    现在,我们只需要通过回溯的方法找回最佳路径就可以了:

    path = [[len(x)-1, len(y)-1]]

    i = len(y)-1

    j = len(x)-1

    while i>0 and j>0:

    if i==0:

    j = j - 1

    elif j==0:

    i = i - 1

    else:

    if accumulated_cost[i-1, j] == min(accumulated_cost[i-1, j-1], accumulated_cost[i-1, j], accumulated_cost[i, j-1]):

    i = i - 1#来自于左边

    elif accumulated_cost[i, j-1] == min(accumulated_cost[i-1, j-1], accumulated_cost[i-1, j], accumulated_cost[i, j-1]):

    j = j-1#来自于下边

    else:

    i = i - 1#来自于左下边

    j= j- 1

    path.append([j, i])

    path.append([0,0])

    path

    Out[89]: [[5, 6], [4, 5], [3, 4], [2, 3], [1, 2], [1, 1], [0, 1], [0, 0]]

    path_x = [point[0] for point in path]

    path_y = [point[1] for point in path]

    distance_cost_plot(accumulated_cost)

    plt.plot(path_x, path_y)

    在刚才,我们已经讲明,最优路径所经过的地方表示两个序列应该对应的点。

    计算这些点的欧式距离作为相似性的度量,这就是DTW。

    Reference:Dong X L, Gu C K, Wang Z O. Research on shape-based time series similarity measure[C]//2006 International Conference on Machine Learning and Cybernetics. IEEE, 2006: 1253-1258.

    Wang D, Rong G. Pattern distance of time series[J]. Zhejiang Daxue Xuebao(Gongxue Ban)/Journal of Zhejiang University(Engineering Science), 2004, 38(7): 795-798.

    Kim S, Lee H, Ko H, et al. Pattern Matching Trading System Based on the Dynamic Time Warping Algorithm[J]. Sustainability, 2018, 10(12): 4641.

    Keogh E, Chakrabarti K, Pazzani M, et al. Dimensionality reduction for fast similarity search in large time series databases[J]. Knowledge and information Systems, 2001, 3(3): 263-286.

    Mori U, Mendiburu A, Lozano J A. Distance measures for time series in R: The TSdist package[J]. R journal, 2016, 8(2): 451-459.

    展开全文
  • DTW 动态时间规整

    2019-11-20 18:43:43
    面临的问题 当数据在时间线上不对齐的时候,使用传统的匹配方法,是无法使用传统的全局匹配度量法的。...DTW通过把时间序列进行延伸和缩短,来计算两个时间序列性之间的相似性。 如下图所示,上下两条实线代表两个...

    面临的问题

    当数据在时间线上不对齐的时候,使用传统的匹配方法,是无法使用传统的全局匹配度量法的。DTW是一种衡量两个时间序列之间的相似度的方法,主要应用在语音识别领域来识别两段语音是否表示同一个单词。

     

    DTW原理

    (Dynamic Time Warping, DTW) 动态时间归整
    DTW通过把时间序列进行延伸和缩短,来计算两个时间序列性之间的相似性。
    如下图所示,上下两条实线代表两个时间序列,时间序列之间的虚线代表两个时间序列之间的相似度,虚线的两端代表两个相似的点。


    DTW使用所有这些相似点之间的距离的和,称之为归整路径距离(Warp Path Distance)来衡量两个时间序列之间的相似度。

    给出两个序列:

    Q = q_1,q_2,...,q_i,...,q_n \\ C = c_1,c_2,...,c_j,...,c_m \\

    Warping通常采用动态规划算法。为了对齐这两个序列,我们需要构造一个n x m的矩阵网格,矩阵元素(i, j)表示qi和cj两个点的距离d(qi, cj),一般采用欧式距离,d(q_i,c_j)=(q_i -c_j)^2(也可以理解为失真度)。每一个矩阵元素(i, j)表示点qi和cj的对齐。

    DP(dynamic programming)算法可以归结为寻找一条通过此网格中若干格点的路径,路径通过的格点即为两个序列进行计算的对齐的点。

    有三个性质:

    • 边界条件:w1=(1, 1)和wK=(m, n)。两个人分别说了同一个单词,但是由于语速、语气、语调等等各不相同,会导致采样得到的数据无法对齐。但是两段语音采样的第一个采样值和最后一个采样值肯定是两两对应的。
    • 连续性:如果wk-1= (a', b'),那么对于路径的下一个点wk=(a, b)需要满足 (a-a') <=1和 (b-b') <=1。也就是不可能跨过某个点去匹配,只能和自己相邻的点对齐。这样可以保证Q和C中的每个坐标都在W中出现。
    • 单调性:如果wk-1= (a', b'),那么对于路径的下一个点wk=(a, b)需要满足0<=(a-a’)和0<= (b-b’)。这限制W上面的点必须是随着时间单调进行的。以保证上图中的虚线不会相交。

    由连续性和单调性可知,每次格点(i, j)前进方向只有三种:(i+1, j),(i, j+1) 或 (i+1, j+1)。我们的目的是使得下面的规整代价最小的路径:

    分母中的K主要是用来对不同的长度的规整路径做补偿。

    这里我们定义一个累加距离(cumulative distances)。从(0, 0)点开始匹配这两个序列Q和C,每到一个点,之前所有的点计算的距离都会累加。到达终点(n, m)后,这个累积距离就是我们上面说的最后的总的距离,也就是序列Q和C的相似度。

    示例:

    对于两个序列:

    X:3,5,6,7,7,1

    Y:3,6,6,7,8,1,1

    X和Y的距离矩阵M如下

    然后根据距离矩阵生成损失矩阵(Cost Matrix)或者叫累积距离矩阵 M_c,其计算方法如下:

    • 第一行第一列元素为 M的第一行第一列元素,在这里就是0;

    • 其他位置的元素 M_c(i,j)的值则需要逐步计算,具体值的计算方法为M_c(i,j)=Min(M_c(i-1,j-1),M_c(i-1,j),M_c(i,j-1))+M(i,j) ,得到的M_c如下:

     最后,两个序列的距离,由损失矩阵最后一行最后一列给出,在这里也就是2。

    给定了距离矩阵,如何找到一条从左上角到右下角的路径,使得路径经过的元素值之和最小。

     

    python 代码实现

     代码里用到的sys.maxsize,需要python3支持

    import sys
    
    def distance(a,b):
        return abs(a-b)
    
    def Min(a,b,c):
        return min(a,min(b,c))
    
    def dtw(X, Y):
        M = [[distance(X[j], Y[i]) for i in range(len(Y))] for j in range(len(X))]
        l1 = len(X)
        l2 = len(Y)
        D = [[0 for i in range(l2+1)] for i in range(l1+1)]
        D[0][0] = 0
        for i in range(1, l2 + 1):
            D[0][i] = sys.maxsize
        for j in range(1, l1 + 1):
            D[j][0] = sys.maxsize
        for j in range(1, l2+1):
            for i in range(1, l1+1):
                D[i][j] = M[i - 1][j - 1] + Min(D[i - 1][j], D[i][j - 1], D[i - 1][j - 1])
        return D[l1][l2]
    
    if __name__ == '__main__':
        X = [3,5,6,7,7,1]
        Y = [3,6,6,7,8,1,1]
        Z = [2,5,7,7,7,7,2]
        value = dtw(X, Y)
        print(value)
        value = dtw(X, Z)
        print(value)
    

    DTW虽然使用线性规划可以快速的求解,但是在面对比较长的时间序列是,O(N2)的时间复杂度还是很大。已经有很多改进的快速DTW算法,比如FastDTW等。

    DTW常用加速手段

      常用的DTW加速手段:

    (1). 限制。亦即减少累积距离矩阵M_c的搜索空间,下图中阴影部分为实际的探索空间,空白的部分不进行探索。

     (2). 数据抽象。亦即把之前长度为N的时间序列规约成长度为M(M<N)表述方式:

     

     (3). 索引。索引是在进行分类和聚类时减少需要运行的DTW的次数的方法,并不能加速一次的DTW计算。

     FastDTW

      FastDTW综合使用限制和数据抽象两种方法来加速DTW的计算,主要分为三个步骤:

      (1). 粗粒度化。亦即首先对原始的时间序列进行数据抽象,数据抽象可以迭代执行多次1/1->1/2->1/4->1/16,粗粒度数据点是其对应的多个细粒度数据点的平均值。

      (2). 投影。在较粗粒度上对时间序列运行DTW算法。

      (3). 细粒度化。将在较粗粒度上得到的归整路径经过的方格进一步细粒度化到较细粒度的时间序列上。除了进行细粒度化之外,我们还额外的在较细粒度的空间内额外向外(横向,竖向,斜向)扩展K个粒度,K为半径参数,一般取为1或者2.

      FastDTW算法的具体执行流程如下图所示:

      第一个图表示在较粗粒度空间(1/8)内执行DTW算法。第二个图表示将较粗粒度空间(1/8)内求得的归整路径经过的方格细粒度化,并且向外(横向,竖向,斜向)扩展一个(由半径参数确定)细粒度单位后,再执行DTW得到的归整路径。第三个图和第四个图也是这样。

      由于采取了减少搜索空间的策略,FastDTW并不一定能够求得准确的DTW距离,但是FastDTW算法的时间复杂度比较低,为O(N)。

     

    参考:

    https://blog.csdn.net/raym0ndkwan/article/details/45614813

    https://www.cnblogs.com/kemaswill/archive/2013/04/18/3028610.html

    https://www.cnblogs.com/kemaswill/archive/2013/04/18/3029078.html

    展开全文
  • 数据结构(C++)有关练习题

    热门讨论 2008-01-02 11:27:18
    2、实现1所要求的代码后,运行设计好的代码,将以下的几组整数序列建成搜索二叉树,并记录下它们的前序遍历序列和后序遍历序列: a. 1、3、5、7、9; b. 1、13、35、13、27; c. 50、25、78、13、44、...
  • 能准确识别英文、数字,以及日期、时间等数量词,能识别人名、地名、组织机构名等未登录词。能通过自定义配置文件来改变组件行为,能自定义用户词库、自动检测词库变化、支持大规模分布式环境,能灵活指定多种分词...
  • antlr4权威指南

    2017-09-30 10:47:22
    规则不能引用另外一规则,如果后者的备选分支之一在左侧直接引用了前者(而没有匹配一个词法符号)。详见5.4节。  除了上述项与语法相关的改进,ANTLR 4还使得编写语言类应用程序更加容易。ANTLR生成的语法...
  • 、Python字符串相似性算法库、PyLaia:面向手写文档分析的深度学习工具包、TextFooler:针对文本分类/推理的对抗文本生成模块、Haystack:灵活、强大的可扩展问答(QA)框架、中文关键短语抽取工具。 1. textfilter: ...
  • 类与结构有很多相似之处:结构可以实现接口,并且可以具有与类相同的成员类型。然而,结构在几个重要方面不同于类:结构为值类型而不是引用类型,并且结构不支持继承。结构的值存储在“在堆栈上”或“内联”。细心的...
  • 28.SQLSERVER服务器中,给定表 table1 中有个字段 ID、LastUpdateDate,ID表示更新的事务号, LastUpdateDate表示更新时的服务器时间,请使用一句SQL语句获得最后更新的事务号 答:Select ID FROM table1 Where ...
  • flash shiti

    2014-03-14 10:32:41
    11. 全等(===)运算符和相同运算符基本相似,但是它们有一个很重要的区别 □ A. 全等(===)运算符执行数据类型的转换 □ B. 全等(===)运算符不执行数据类型的转换 □ C. 全等(===)运算符永远返回...
  • 入门学习Linux常用必会60个命令实例详解doc/txt

    千次下载 热门讨论 2011-06-09 00:08:45
    在前种格式中,会将<来源>复制至<目的地>或将多个<来源>文件复制至已存在的<目录>,同时设定权限模式及所有者/所属组。在第三种格式中,会创建所有指定的目录及它们的主目录。长选项必须用的参数在使用短选项时也...
  • powerbuilder

    2013-11-21 17:11:48
    功能在当前打印页上绘出指定厚度的一线。 语法PrintLine ( printjobnumber, x1, y1, x2, y2, thickness ) 参数printjobnumber:用PrintOpen()函数打开的打印作业号x1:integer类型,指定直线起点的x坐标,以千分...
  • C++MFC教程

    热门讨论 2013-05-21 13:37:15
    |------ 3.5 利用序列化进行文件读写 |------ 3.6 MFC中所提供的各种视类介绍 +-- 第四章 窗口控件 |------ 4.1 Button |------ 4.2 Static Box |------ 4.3 Edit Box |------ 4.4 Scroll Bar |------ 4.5 List Box/...
  • C#微软培训教材(高清PDF)

    千次下载 热门讨论 2009-07-30 08:51:17
    第十二章 域 和 属 .139 12.1 域 .139 12.2 属 .143 12.3 小 结 .146 第十三章 事件和索引指示器 .148 13.1 事 件 .148 13.2 索引指示器 .151 13.3 小 结 .154 第十四章 继 承 .155 14.1 C#的...
  • C#微软培训资料

    2014-01-22 14:10:17
    第十二章 域 和 属 .139 12.1 域 .139 12.2 属 .143 12.3 小 结 .146 第十三章 事件和索引指示器 .148 13.1 事 件 .148 13.2 索引指示器 .151 13.3 小 结 .154 第十四章 继 承 .155 14.1 C#的...
  • java 面试题 总结

    2009-09-16 08:45:34
    在实现中,assertion就是在程序中的一语句,它对一个boolean表达式进行检查,一个正确程序必须保证这个boolean表达式的值为true;如果该值为false,说明程序已经处于不正确的状态下,系统将给出警告或退出。...
  • LINGO软件的学习

    2009-08-08 22:36:50
    借助于集,能够用一个单一的、长的、简明的复合公式表示一系列相似的约束,从而可以快速方便地表达规模较大的模型。 2.2 什么是集 集是一群相联系的对象,这些对象也称为集的成员。一个集可能是一系列产品、卡车或...
  •  事务控制语言(Transactional Control Language,TCL),用于维护数据的一致,包括COMMIT(提交事务)、ROLLBACK(回滚事务)和SAVEPOINT(设置保存点)3语句 二、 Oracle的数据类型 类型 参数 描述 字符类型...
  • 范例1-21 字符串的匹配 42 ∷相关函数:nfind函数 1.1.22 字符串的合并 43 范例1-22 字符串的合并 43 ∷相关函数:catstr函数 1.1.23 文本编辑 45 范例1-23 文本编辑 45 ∷相关函数:StrAssign函数 1.2 栈和...
  • C语言通用范例开发金典.part2.rar

    热门讨论 2012-08-31 14:18:18
    范例1-21 字符串的匹配 42 ∷相关函数:nfind函数 1.1.22 字符串的合并 43 范例1-22 字符串的合并 43 ∷相关函数:catstr函数 1.1.23 文本编辑 45 范例1-23 文本编辑 45 ∷相关函数:StrAssign函数 1.2 栈和...
  • C 开发金典

    2013-06-20 16:20:03
    范例1-21 字符串的匹配 42 ∷相关函数:nfind函数 1.1.22 字符串的合并 43 范例1-22 字符串的合并 43 ∷相关函数:catstr函数 1.1.23 文本编辑 45 范例1-23 文本编辑 45 ∷相关函数:StrAssign函数 1.2 栈和...

空空如也

空空如也

1 2
收藏数 22
精华内容 8
关键字:

两条相似性匹配时间序列