《动态时间弯曲算法在K线相似度计算中的应用》由会员分享，可在线阅读，更多相关《动态时间弯曲算法在K线相似度计算中的应用（13页珍藏版）》请在金锄头文库上搜索。
1、动态时间弯曲算法在K线相似度计算中的应用序言在证券交易数据中，股票K线图无疑是一种非常重要的数据它反映了股票在过去历史中基于开盘价与收盘价的交易价格的变动古有言，以史为鉴，历史往往存在相似性，对一支股过去历史波动的研究，往往可以对其自身，以及其他股票的未来价格变动作出一些合理预测而股票价格究其根本是一种时间序列对于时间序列，是一种以时间为轴，在一些特别规定的时间点上通过采样得到的一系列按照时间顺序排列的，从被观测对象获取到的观测值通过对时间序列的研究，找到两条时间序列相似程度的的度量方法就被称为时间序列相似性度量，这是时间序列聚类分析中一个不可缺少的步骤，同时也是分类、聚类、规律发现、模式识别
2、等工作的子进程对于研究股票k线图相似性，是为了对未来进行合理预测，因此度量方法应该考虑其性能对于后期时间序列数据挖掘的效果的的直接影响程度时间序列的相似程度是由度量距离的大小所决定的而相似性度量方式的特性又决定了 相似性度量的效果在时间序列相似性度量中，我们最常用的方法就是动态时间弯曲（Dynamic Time Warping，DTW）这是由Berndt于1994年提出将其应用在时间序列数据挖掘领域中，以此来发现时间序列中的模式而这刚好适用于股票k线图的相似程度的研究这是由于动态时间弯曲不仅可以消除欧式距离“点对点”的匹配缺陷，通过弯曲时间来达到时间序列数据点“一对多”的匹配，从而实现不等长时
3、间序列的度量，还对时间序列的偏移，振幅变化等情况具有较强的鲁棒性（鲁棒是Robust的音译，也就是健壮和强壮的意思鲁棒性指的是遭遇外来干扰，性质保持不变的能力）这对于不同股票的k线图在不同的时间跨度而可能形成相同价格形态有着重要意义一、 DTW算法原理动态时间弯曲是一种在语音识别领域得到首次应用的，准确性高并且鲁棒性强的时间序列相似性度量方法它区别于传统的欧几里的距离，其不同在于动态时间弯曲可以通过弯曲时间序列的时间区域从而对时间序列的数据点进行匹配，这样我们不单单能够得到更好的形态度量的效果，更重要的是我们能够度量两条不等长的时间序列对于股票K线图的相似性，我们寻求的是价格形态的相似性例如威
4、廉欧奈尔提到的一种最普遍的价格形态“带柄茶杯形态”,当我们找到与此形态相似的股票时就要做出准备，这可能是一支带动市场发展的“超级牛股”一如当年的微软与苹果要想实现股票K线图的这种相似度匹配，依靠欧式距离在度量中讲时间序列进行“一对一“的数据匹配是不够的，尽管它具有高效性，但是它并未能准确的使波峰、波谷匹配起来而动态时间弯曲则能够通过弯曲时间轴来实现“一对多”的数据匹配通过这样，动态时间弯曲就能成功将两条不同的股票K线图的波峰和波谷匹配起来，从而有助于我们度量价格形态的相似程度，体现了动态时间弯曲在形态度量上的优势1.1动态时间弯曲距离【1】在介绍动态时间弯曲算法之前，先简单的介绍一下动态时间弯
5、曲距离的定义定义1 给定两条时间序列x=x1,x2,xn和y=y1,y2,yn,计算它们之间的累积距离D(i,j)=d(xi.yj)+minD(i1,j)Di,j1D(i1,j1)其中 d(xi,yj)= | xi-y j| (1)为点xi到yj之间的距离，其中i=（1,2,n）,j=(1,2,m),当=2时为欧式距离得到的累积最小距离就是动态弯曲距离，我们记为Dwarp（）在这里我们需要特别注意一点，动态弯曲距离是不符合三角不等式的命题1 Dwarp()不满足三角不等式证明我们可以通过一个反例来证明这个论题，设x=0 y=1,2 和z=1,2,2， 那我们有： Dwarp（x，z）=5 Dw
6、arp（x，y）+Dwarp（y，z）=3+0=3如此命题得证1.2动态时间弯曲距离的计算 计算它的最终累积距离其实可以认为是在距离矩阵D中寻找一条最优的弯曲路径P，从而使得累积距离达到最小，其中距离矩阵可以表示为以任意两点之间的距离来确立nm的距离矩阵D D= d（x1,yn)d(xn,yn)d(x1,y1)d(xn,y1) 通过寻找弯曲路径Pbest=p1,p2,pK (max(n,m) Kn+m+1)来使得S和Q的累计距离的值达到最小其中pk表示的是弯曲路径元素在距离矩阵中的位置，即pk=（i，j）k表示si与hj之间的匹配关系则由此可以知道d（pk）=d（i，j）k通过观察距离矩阵，我
7、们可以看出一般存在着多条弯曲路径，有效的弯曲路径P必须符合三个要求：（1） 边界性：p1=（1,1），pK=（n，m）即路线必须从距离矩阵的第一行第一列出发到达矩阵的第n行第n列（2） 单调性：给定pk=（i，j）和pk+1=（x，y），则xi，yj（3） 连续性: 给定pk=（i，j）和pk+1=（x，y），xi+1，yj+1 单调性和连续性的存在保证了弯曲路径中某个点的下一个点在当前点的上方、右上方、右方1.3范例给定两条时间序列x=2,5,5,4,6,7，y=2,4,6,5,7,7,如下图，计算它们的动态时间弯曲距离：我们令d(xi,yj)=|x-y|，由此来构造一个距离矩阵，在这里为了
8、方便起见把它做成了一个网格形态，每一格中的数字代表距离矩阵相应位置的d(xi,yj)的值 由此我们便可以根据动态规划（AP）找到一条最优路径从而得到Dwarp（）在股票的相似性522310523310300112511201201023033245二、基于动态时间弯曲的股票k线图相似性计算在股票K线图的相似性计算中，我们通常是将股票进行两两比较在这里我们将选取其中一支具有特别价格形态的股票作为参考股票，另一支与它进行比较的股票就叫测量股票2.1将股票数据进行向量化和标准化【6】为了便于后续计算，我们首先要将采集到股票数据进行预先处理我们将参考股票具有研究意义的30天的价格变动以向量方式记录，记
9、为x=（x1,x2,xn）同样的我们将测量股票要测量的30天价格变动也用向量方式记录记为天价格变动也用向量方式记录，记为y=（y1,y2,yn）其中n为选取的K线图某时刻的时序标号，n=1为起点时刻，在这里我们选取的是30天，所以n=30为终点时刻xm为第m时刻的K线图的收盘价格由于股票价格差别巨大，统一的阙值不好判断，所以要进行规范处理，把所有股票的价格变动都转化为01之间，具体方法如下：Zi=ximin(x)maxxmin(x)2.2通过构建股票价格的距离矩阵寻找最优路径采用动态时间弯曲算法我们首先要根据参考股票和测试股票的收盘价格来构建一个距离矩阵Dnm我们可以用如下办法来快速构建距离矩
10、阵从而找到最优路径若把测试模板的各个时刻n=1N在一个二维直角坐标系中的横轴上标出，把参考股票的各时刻m=1M在纵轴上标出，通过这些表示时刻的整数坐标画出一些纵横线即可形成一个网络，网络中的每一个交叉点（n，m）表示测试股票与参考股票中某一时刻的交汇点用动态规划（DP）算法来计算并寻找一条通过此网络中若干格点的路径，路径通过的格点即为测试和参考股票中进行计算的时刻具体如下图：d(x30,y1)d(x30,y30)d(x3,y1)d(x2,y1)d（x1,y1）d（x1,y2）d(x1.y3)d(x1,y30)路径不是随意选择的，首先任何一种股票的价格涨幅都有可能变化，但是其各时刻的先后次序不可
11、能改变，因此所选的路径必定是从左下角出发，在右上角结束为了描述这条路径，假设路径通过的所有格点依次为（n1，m1），（ni，mj），（nN，mM），其中（n1，m1）=（1，1），（nN，mM）=（N，M）为了使路径不至于过倾斜，可以约束斜率在0.52的范围内，如果路径已经通过了格点（n ，m ），那么下一个通过的格点（n ，m ）只可能是下列三种情况之一：（n ，m ）=（n +1，m）（n ，m ）=（n +1，m +1）D(n-1,m),D(n-1,m-1),D(n,m-1)（n ，m ）=（n ，m+1 ）用r表示上述三个约束条件求最佳路径的问题可以归结为满足约束条件r时，求最佳路径，
12、使得沿路径的积累距离达到最小值，即：Dwarp（）2.3搜索该路径的方法搜索从（N, M）点出发，可以展开若干条满足r的路径，假设可计算每条路径达到（n, m）点时的总的积累距离，具有最小累积距离者即为最佳路径易于证明，限定范围的任一格点（n, m）只可能有一条搜索路径通过对于（n, m），其可达到该格点的前一个格点只可能是（n-1, m）、（n-1, m -1）和（n, m-1），那么（n, m）一定选择这3个距离之路径延伸而通过（n, m），这时此路径的积累距离为：D(n, m)=dxn,ym+minD(n1,m) D(n1,m1)D(n,m1)这样可以从（n ，m ）=（30，30）出发
13、搜索（n ，m ），对每一个（n ，m ）都存储相应的距离，这个距离是当前格点的匹配距离与前一个累计距离最小的格点（按照设定的斜率在三个格点中进行比较）搜索到（1 ，1）时，只保留一条最佳路径如果有必要的话，通过逐点向前寻找就可以求得整条路径DTW算法可以直接按上面描述来实现，即分配两个NM的矩阵，分别为积累距离矩阵D和时刻匹配距离矩阵d，其中时刻匹配距离矩阵d（i，j）的值为测试股票的第i时刻与参考股票的第j时刻间的距离D（N，M）即为最佳匹配路径所对应的匹配距离24范例例如我们选取两支股票，一支是中成股份（000151）作为参考股份x，另一支是翼凯股份（002691）作为测试股份y，为了计
14、算方便我们只取五天的数据第一步：提取数据X=（10.53，11.58，12.74，13.77，13.19）Y=（27.99，29.4，32.3，32.8，32.4）第二步：标准化经过Zi=ximin(x)maxxmin(x)后，X=( 0，0.324，0.682，1，0.820)Y=( 0，0.293，0.896，1，0.917)第三步：构建距离矩阵并寻找最优路径在这里我们让d(xi,yj)=|x-y|0.8200.5270.0760.1800.09710.7070.10400.0830.6820.3890.2140.3180.2350.3240.0310.5720.6760.59300.2930.89610.917最终我们得到一个最优累积距离Dwarp（）=0.046三、 DTW在K线图相似度计算机的实际应用【2】在中国A股总共有3470支甚至还有中小企业板，乃至创业板的股票，再涉及到各自的历史数据，这是一个非常庞大的数据库若要在这个数据可当中找寻于某一支股票相似的其他股票，将是一个计算量非常大的工作显然不可能人工手算，而是要借助计算机的索引技术但是如此庞大的数据对索引技术的准确性和高效性有着非常大的挑战 3.1索引技术索引技术是一种快速的文件访问技术，举个例子，好比我们查字典，会根据偏旁部首在索引表中找到这个字在第几页一样，
