精华内容
下载资源
问答
  • 博客https://blog.csdn.net/l5678go/article/details/80383113中提到的数据以及代码 涉及到内容CIR模型,Vasicek模型,最小二乘法拟合,动态时间规整(dynamic time warping,DTW),RCR
  • 时间序列相似度计算 DTW算法

    千次阅读 2019-10-30 22:48:27
    在论文Deep Multi-viewSpatial-Temporal Network for Taxi Demand Prediction所提出的模型框架的Semantic View模块中,...在相似度计算方法中,我们常用的方法有余弦相似度、欧式距离相似度等。对于不同长度的时间...

    在论文Deep Multi-view Spatial-Temporal Network for Taxi Demand Prediction所提出的模型框架的Semantic View模块中,利用Dynamic Time Warping(DTW) 方法来计算其节点node(或位置)的相似性。

    现将其整理如下:

    在相似度计算方法中,我们常用的方法有余弦相似度、欧式距离相似度等。对于不同长度的时间序列,传统的相似度计算方法不能有效的求出其相似度。

    基于上述存在的问题,采用DTW方法来计算不同时间序列长度的相似度计算。论文中没有给出具体的计算方法。

    具体的后续再更

     

    参考链接:

    https://www.cnblogs.com/tornadomeet/archive/2012/03/23/2413363.html

    展开全文
  • 为提高多元时间序列相似性度量的效率,采用扩展Frobenius范数(Eros)的主元分析(PCA)方法,通过主元和本征值构造主元相似因子,用于比较多元时间序列矩阵之间的相似性。为了验证这种方法的有效性,针对三组数据...
  • 方法:比较两个序列相似度最简单就是欧式距离,但其缺点也很明显,一是它只能测量长度相等的时序,二是它对噪声是敏感的,因为个别很远的偏离平均值的点可能对结果造成很大的影响。 为了克服这些缺点,人出现其他更...

    对于之前证券公司的笔试整理下,应该去证券面试的都不会遇到我这种情况,lol,没办法专业在那

    下面就是试题内容以及一个小白的答题内容了:

    债券收益率建模:

    在研究瞬时短期利率模型中,单因子均衡模型(one-factor model)一搬考虑以下三种:

    a.     Rendleman和Bartter 模型:  

    b.    Vasicek模型:

    c.     CIR模型: 

    这里,请分别用Vasicek模型和CIR模型对附件data1.xlsx中的各币种收益率建模,并比较两种模型的优劣。

    要求:

    1.  分别给出各个币种在两种模型下的拟合曲线

    2.  熟练运用统计推断,给出两模型的拟合优劣并简单分析

    三组数据统计信息:美元:平均收益率是1.12000,标准偏差是0.82894;欧元:平均收益率是0.36680,标准偏差是0.59846;人民币:平均收益率是2.80961,标准偏差是0.59815。

    两个模型均假设短期利率r风险中性过程是随机的,且仅有一个不确定性来源。随机过程包括漂移和波动率两个参数,它们只与短期利率r有关,与时间无关。

    @实施过程及结果分析:代码文件CKLS.py

    ·对于两个模型参数的估计采用的是最小二乘法进行的,参考文献是董烈刚,朱全新的《一种均值回复利率模型的求解与参数估计》(http://www.docin.com/p-235581620.html)。


    ·结果:

    Vasicek模型:初始化参数为([0.01,-0.11,0.0089])。对于美元,欧元和人民币参数估计拟合参数R方:0.9774,-0.4739和0.54018,求出来的,和分别是:0.0117,-0.0225,和-1.093*10^(-5)。

    CIR模型:初始化参数为([0.001, -0.05, 0.2])。对于美元,欧元和人民币参数估计拟合参数R方:0.6400,0.4966,0.5543,求出来的,和分别是:0.0011,-0.0595, 0.2155。

    ·结果分析

    两种模型拟合不稳定,R方有些甚至会达到1,但是之后曲线明显不合理,证明有过拟合现象。有些文献指出CIR模型是为克服Vasicek模型利率可以为负的缺陷,但是貌似我做出来的模型还是会出现有负的现象,可能是我用的参数估计方法不够准确吧,这个还是有待进一步去找一些参考文献来改进。还有一个问题是,对于CIR模型的显式表达式我并没有找到,

    拟合曲线图样例如下:

    CIR方法三张图片如下:


    Vasicek方法三张图片如下:


    ======================================================================================================================================================

    试题2:
    附件data2.xlsx中给出了2014年9月29日至2014年11月7日的150支股票每日成交额数据,请以601688.sh这支股票的日成交额序列作为模板,以余下股票的日成交额序列作为目标,匹配出目标序列中你认为与模板序列具有较高相似程度的那一部分;
    请用任意程序完成以下要求:
     1,目标序列与模板序列的相似度应仅与序列中数据有关
     2,定义你的两支序列相似程度的表达
     3,说明相似阈值的选取理由
     4,输出与模板相似的目标序列到xlsx中
     5,将程序包含在附件中发回并附上说明
    对某一个或者一组变量 x(t) 进行观察测量,将在一系列时刻 t1,t2,⋯,tn 所得到的离散数字组成的序列集合,称之为时间序列。时间序列数据本身所具备的高维性、复杂性、动态性、高噪声特性以及容易达到大规模的特性,因此时间序列挖掘是数据挖掘研究中最具有挑战性的十大研究方向之一。目前重点的研究内容包括时间序列的模式表示、时间序列的相似性度量和查询、时间序列的聚类、时间序列的异常检测、时间序列的分类、时间序列的预测等。本题目主要考查的是时间序列的相似性度量时间序列的相似性度量。
    @实施过程及结果分析:代码文件timeseries.py和timeseriesRCR.py
    ·实施流程:
    数据预处理:先将需要匹配的序列与需要去匹配的序列分别放入数组中,然后将其中的异常值0换成均值,之后采用标准差均一化以及最大最小值进行归一化。
    方法:比较两个序列相似度最简单就是欧式距离,但其缺点也很明显,一是它只能测量长度相等的时序,二是它对噪声是敏感的,因为个别很远的偏离平均值的点可能对结果造成很大的影响。 为了克服这些缺点,人出现其他更好的测度。比如动态时间规整(dynamic time warping,DTW),最长公共子序列(LCSS)等。本题采用方法其中一种就是DTW,但是效果并不明显,得到了前10%相似的序列。之后参考了尚书敬的《RCR:一种面向金融时间序列的相似度量模型》(http://www.doc88.com/p-582326221170.html),通过检测满足模型要求的序列获得相似序列,但是问题是:我的误差阈值比文章中的要大很多,而且是尝试出来的,不具有代表性。
    ·结果及分析:
    DTW方法测试出来的距离成段分布,距离70左右的,2000左右的,每段之间相差无几,所以最后得到距离原始序列最近的前10%作为最终的相似序列,存储在文件” matheditem.xlsx”中。对于DTW方法得到的距离分段分布应该是由于算法本身动态规划矩阵分布情况决定的,我最终选择的相似序列也具有主观性,若想得到更好的结果距离计算公式应该是需要更新的。
    RCR方法测试出来满足相对变化率小于4.5的有两个,若阈值再选小一点就没有匹配的序列了,最终结果存储在” matheditemrcr.xlsx”中。这种方法阈值选取得很有问题,或者说这个模型在应用于这个问题的时候就是需要首先进行一些其他的预处理。亦或者说本题有其他一些成熟的模型可以应用并改进。




    展开全文
  • 快速,准确的相似度检测新的时间序列表示模型和相似度度量
  • 图像序列相似,只是数值不太相同导致奇异点问题,请问时间序列相似度度量使用动态时间规整算法会出现奇异点问题,如何用python解决动态时间规整(DTW)奇异点问题,
  • 时间序列相似性度量综述

    千次阅读 2021-02-03 03:53:08
    时间序列相似性属于曲线相似性/曲线匹配(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.

    展开全文
  • 上面是我要进行相似度度量的时间序列,看起来蛮像的,应该很相似,但是用动态时间规整算法跑出来,出现了奇异点问题,也就是也就是下图 请问该如何修改算法去解决呢?
  • Python库,用于计算可散列数据类型序列的距离和相似度。 虽然seqsim是作为通用库开发的, seqsim其主要目的是用于文化进化特别是文本传统文化进化领域的研究中。 一些方法充当标准Python库或其他库(例如。 安装 ...
  • 时间序列分析 23 DTW (时序相似度度量算法) 上 DTW解析     我们已经给出了算法的原理和实现代码。在这一部分,我们将从直观上深度解析一下DTW算法,就以前面所给出的图形中的蓝色A,绿色B序列为...

    接上文,
    时间序列分析 23 DTW (时序相似度度量算法) 上

    DTW解析

        我们已经给出了算法的原理和实现代码。在这一部分,我们将从直观上深度解析一下DTW算法,就以前面所给出的图形中的蓝色A,绿色B序列为例。见下图,
    在这里插入图片描述
    DTW算法是建立在计算两个序列的距离混淆矩阵的基础上的。图(a)中时序A的值显示在X轴上,时序B的值显示在Y轴上。图(b)显示了最佳对齐方式,连接A,B序列的红线就对应了图(a)中的红点。

    关键问题在于我们如何找到这个最佳对齐方式,请见下图
    在这里插入图片描述
    如何找到这个最佳对齐方式演变成了如何找到上图网格中红点所对应的路径。其中,
    P = p 1 , … , p s , … , p k P=p_1,\dots,p_s,\dots,p_k P=p1,,ps,,pk
    p s = ( i s , j s ) p_s=(i_s,j_s) ps=(is,js)
    这里这个映射关系 P P P被称为变形函数(Warping Function)

    我们定义两个序列的时间规范化距离为:
    D ( A , B ) = ∑ s = 1 k d ( p s ) ⋅ w s ∑ s = 1 k w s D(A,B)=\frac{\sum\limits_{s=1}^{k}d(p_s)\cdot w_s}{\sum\limits_{s=1}^{k}w_s} D(A,B)=s=1kwss=1kd(ps)ws
    这里, d ( p s ) d(p_s) d(ps) i s i_s is j s j_s js之间的距离,而 w s w_s ws是权重系数。
    最佳路径就是

    arg ⁡ min ⁡ P D ( A , B ) . \mathop{\arg\min}_{P} D(A,B). argminPD(A,B).

    前面提到,DTW需要满足边界条件和规则,保证不是部分匹配。
    在这里插入图片描述
    i 1 = 1 , i k = n ; j 1 = 1 , j k = m i_1=1,i_k=n;j_1=1,j_k=m i1=1,ik=n;j1=1,jk=m

    增加窗口条件限制下 ∣ i s − j s ∣ ≤ r , r > 0 |i_s-j_s|\le r, r \gt 0 isjsr,r>0, r r r就是窗口大小
    在这里插入图片描述
    令最佳路径表示为 g ( ) g() g()

    1. 计算 g ( 1 , 1 ) = d ( 1 , 1 ) g(1,1)=d(1,1) g(1,1)=d(1,1)
    2. 计算第一行 g ( i , 1 ) = g ( i − 1 , 1 ) + d ( i , 1 ) g(i,1)=g(i-1,1)+d(i,1) g(i,1)=g(i1,1)+d(i,1)
    3. 计算第一列 g ( 1 , j ) = g ( 1 , j − 1 ) + d ( 1 , j ) g(1,j)=g(1,j-1)+d(1,j) g(1,j)=g(1,j1)+d(1,j)
      移动到第二行
      g ( i , 2 ) = m i n ( g ( i , 1 ) , g ( i − 1 , 1 ) , g ( i − 1 , 2 ) ) + d ( i , 2 ) g(i,2)=min(g(i,1),g(i-1,1),g(i-1,2))+d(i,2) g(i,2)=min(g(i,1),g(i1,1),g(i1,2))+d(i,2)
      继续保持从左向右,从下向上计算完整个网格
      g ( i , j ) = m i n ( g ( i − 1 , j ) + g ( i , j − 1 ) + g ( i − 1 , j − 1 ) ) + d ( i , j ) g(i,j)=min(g(i-1,j)+g(i,j-1)+g(i-1,j-1))+d(i,j) g(i,j)=min(g(i1,j)+g(i,j1)+g(i1,j1))+d(i,j)
      回溯 g ( n , m ) 到 g ( 1 , 1 ) g(n,m)到g(1,1) g(n,m)g(1,1)即为最佳路径
      DTW算法的时间复杂度为 O ( m ∗ n ) O(m*n) O(mn) m , n m,n m,n 分别为两个序列的长度。
    展开全文
  • 函数计算所选窗口跨度的阈值交叉时间序列之间的窗口交叉相似度。 原始分辨率记录随时间聚合的高时间分辨率记录之间的相关性。 更多信息http://www.ida.liu.se/~agbur/Software.htm
  • 函数计算具有时间滞后的阈值交叉时间序列之间的余弦交叉相似度。 它还计算显性滞后和最大值。 更多细节http://www.ida.liu.se/~agbur/Software.htm
  • 在对我国证券市场交易数据的研究基础上,提出了一种新的面向金融时间序列的相似度量模型。此模型的数学定义清晰,易于计算机实现,能够有效完成形态搜索的自动化。给出了模型的形式化定义和模型的性质,并在实际股票...
  • 时间序列相似性的度量方法可分为三类: (1)基于时间步长的,如反映逐点时间相似性的欧氏距离; (2)基于形状,如Dymanic Time Warping(Berndt和Clifford 1994)根据趋势出现; (3)基于变化的,如高斯混合模型(GMM) ...
  • 时间序列分析 23 DTW (时序相似度度量算法) 中 时间序列分析 23 DTW (时序相似度度量算法) 上 DTW 实践1 声音识别 这个实例中,我们将引入四个音频文件。 第一个是原始声音 第二个与第一个所说的内容一样,但是语调...
  • 多变量时间序列相似度量

    千次阅读 2019-08-06 21:07:13
    单变量时间序列可以看成是向量,其相似度量最常用的两种方法是欧式距离和DTW,将其应用到多元时间序列(可用矩阵存储表达)。 令Q为多元时间序列矩阵,该时间序列共有n个变量,即有n列,每一列维度为m。再令C为另一...
  • 论文精读——基于模式序列相似度的大数据时间序列预测及其在电力需求中的应用
  • 目录:序列相似度度量算法

    千次阅读 2019-07-20 15:32:49
    序列相似度度量算法目录 (1)序列相似度之豪斯多夫距离(Hausdorff Distance)算法 (2)序列相似度之动态时间归整(Dynamic Time Warping,DTW)算法 (3)序列相似度之弗雷歇离散距离(Fréchet Distance)算法 ...
  • 时间序列相似性度量-DTW

    万次阅读 多人点赞 2019-01-25 16:44:59
    最近项目中遇到求解时间序列相似性问题,这里序列也可以看成向量。在传统算法中,可以用余弦相似度和pearson相关系数来描述两个序列的相似度。但是时间序列比较特殊,可能存在两个问题: 两段时间序列长度不同。...
  • 时间序列相似性

    万次阅读 2017-10-11 14:59:17
    DTW是一种衡量两个时间序列之间的相似度的方法,主要应用在语音识别领域来识别两段语音是否表示同一个单词 原理: DTW通过把时间序列进行延伸和缩短,来计算两个时间序列性之间的相似性。 1,两个要进行匹配的数据A=...
  • 时间序列相似性度量是时间序列相似性检索、时间序列无监督聚类、时间序列分类以及其他时间序列分析的基础。给定时间序列的模式表示之后,需要给出一个有效度量来衡量两个时间序列的相似性。时间序列的相似性可以分为...
  • 夹角余弦(Cosine)也可以叫余弦相似度。 几何中夹角余弦可用来衡量两个向量方向的差异,机器学习中借用这一概念来衡量样本向量之间的差异。(1)在二维空间中向量A(x1,y1)与向量B(x2,y2)的夹角余弦公式:(2) 两个n维...
  • 论文学习:2018-TIFS-sequence covering for efficient host based intrusion detection •引入:想要根据系统调用序列进行异常检测...但是用于序列相似度计算时,它只能反映出同一位置上序列元素的差异性,而无法捕获
  • DTW(Dynamic Time Warping / 动态时间归整) python实现的Demo 基于 python 2.7 实现
  • 时间序列相似性搜索总结

    万次阅读 2015-08-17 21:58:10
    前段时间一直在看时间序列相似性搜索(Time Series Similarity Search)的相关论文,现在终于放暑假了,开心度假中,也正好对那段时间读的论文做些总结。 首先来说明一下什么是时间序列(Time Series,以下简称时序)...
  • 时间序列分析 - 23 DTW (时序相似度度量算法) 上 DTW初探 简介     在时序分析中,DTW(Dynamic Time Warping)是用来检测两个时序相似程度的算法,而这个相似程度通常用一个距离来表示。例如如下...
  • 本文通过计算位置时间序列的余弦相似度找到确定与其近似的位置时间序列。同时针对余弦相似度在计算位置时间序列相似性出现的偏差,提出了一种余弦相似度的改进方法(单侧相似度)。单侧相似度给出了不同位置时间序列...
  • 针对现有模糊时间序列预测算法无法适应预测中新关系出现的问题,提出了一种基于区间相似度的模糊时间序列预测(ISFTS)算法。首先,在模糊理论的基础上,采用基于均值的方法二次划分论域的区间,在论域区间上定义相应...
  • 人员轨迹数据按照时间顺序,以地点id的序列来表示。示例:a = [180, 180, 141, 146, 141, 200, 235, 235, 173, 141, 141, 172, 180]b = [165, 235, 180, 141, 240, 171, 173, 172]LCSS算法则可以计算出两个序列之间...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 14,964
精华内容 5,985
关键字:

时间序列相似度