动态时间弯曲算法在K线相似度计算中的应用序言在证券交易数据中，股票K线图无疑是一种非常重要的数据．它反映了股票在过去历史中基于开盘价与收盘价的交易价格的变动．古有言，以史为鉴，历史往往存在相似性，对一支股过去历史波动的研究，往往可以对其自身，以及其他股票的未来价格变动作出一些合理预测．而股票价格究其根本是一种时间序列．对于时间序列，是一种以时间为轴，在一些特别规定的时间点上通过采样得到的一系列按照时间顺序排列的，从被观测对象获取到的观测值．通过对时间序列的研究，找到两条时间序列相似程度的的度量方法就被称为时间序列相似性度量，这是时间序列聚类分析中一个不可缺少的步骤，同时也是分类、聚类、规律发现、模式识别等工作的子进程．对于研究股票k线图相似性，是为了对未来进行合理预测，因此度量方法应该考虑其性能对于后期时间序列数据挖掘的效果的的直接影响程度．时间序列的相似程度是由度量距离的大小所决定的．而相似性度量方式的特性又决定了相似性度量的效果．在时间序列相似性度量中，我们最常用的方法就是动态时间弯曲（DynamicTimeWarping，DTW）．这是由Berndt于1994年提出将其应用在时间序列数据挖掘领域中，以此来发现时间序列中的模式．而这刚好适用于股票k线图的相似程度的研究．这是由于动态时间弯曲不仅可以消除欧式距离“点对点”的匹配缺陷，通过弯曲时间来达到时间序列数据点“一对多”的匹配，从而实现不等长时间序列的度量，还对时间序列的偏移，振幅变化等情况具有较强的鲁棒性（鲁棒是Robust的音译，也就是健壮和强壮的意思．鲁棒性指的是遭遇外来干扰，性质保持不变的能力．）．这对于不同股票的k线图在不同的时间跨度而可能形成相同价格形态有着重要意义．一、DTW算法原理动态时间弯曲是一种在语音识别领域得到首次应用的，准确性高并且鲁棒性强的时间序列相似性度量方法．它区别于传统的欧几里的距离，其不同在于动态时间弯曲可以通过弯曲时间序列的时间区域从而对时间序列的数据点进行匹配，这样我们不单单能够得到更好的形态度量的效果，更重要的是我们能够度量两条不等长的时间序列．对于股票K线图的相似性，我们寻求的是价格形态的相似性．例如威廉·欧奈尔提到的一种最普遍的价格形态“带柄茶杯形态”,当我们找到与此形态相似的股票时就要做出准备，这可能是一支带动市场发展的“超级牛股”一如当年的微软与苹果．要想实现股票K线图的这种相似度匹配，依靠欧式距离在度量中讲时间序列进行“一对一“的数据匹配是不够的，尽管它具有高效性，但是它并未能准确的使波峰、波谷匹配起来．而动态时间弯曲则能够通过弯曲时间轴来实现“一对多”的数据匹配．通过这样，动态时间弯曲就能成功将两条不同的股票K线图的波峰和波谷匹配起来，从而有助于我们度量价格形态的相似程度，体现了动态时间弯曲在形态度量上的优势．1.1动态时间弯曲距离【1】在介绍动态时间弯曲算法之前，先简单的介绍一下动态时间弯曲距离的定义．定义1给定两条时间序列x={x1,x2,…,xn}和y={y1,y2,…,yn},计算它们之间的累积距离D(i,j)=d(xi.yj)+min{D(i−1,j)D(i,j−1)D(i−1,j−1)其中d(xi,yj)=||xi-yj||ω(1)为点xi到yj之间的距离，其中i=（1,2,…,n）,j=(1,2,…,m),当=2时为欧式距离．得到的累积最小距离就是动态弯曲距离，我们记为Dwarp（）在这里我们需要特别注意一点，动态弯曲距离是不符合三角不等式的命题1Dwarp()不满足三角不等式证明我们可以通过一个反例来证明这个论题，设x=⟨0⟩y=⟨1,2⟩和z=⟨1,2,2⟩，那我们有：Dwarp（x，z）=5¿Dwarp（x，y）+Dwarp（y，z）=3+0=3如此命题得证．1.2动态时间弯曲距离的计算计算它的最终累积距离其实可以认为是在距离矩阵D中寻找一条最优的弯曲路径P，从而使得累积距离达到最小，其中距离矩阵可以表示为以任意两点之间的距离来确立n×m的距离矩阵DD=(¿¿⋯¿d(xn,yn)¿⋮¿⋱¿⋮¿d(x1,y1)¿⋯¿d(xn,y1)¿)通过寻找弯曲路径Pbest={p1,p2,…pK}(max(n,m)≤K≤n+m+1)来使得S和Q的累计距离的值达到最小．其中pk表示的是弯曲路径元素在距离矩阵中的位置，即pk=（i，j）k表示si与hj之间的匹配关系...
