时间序列之动态时间规整.ppt

姓名：罗云生学号：1405024,时间序列数据挖掘,Contents,CAUC,时间序列数据挖掘综述,时间序列指将某种现象某一个统计指标在不同时间上的各个数值，按时间先后顺序排列而形成的序列时间序列数据挖掘在对时间序列进行数据挖掘的过程中,必须考虑数据集之中数据间存在的时间关系,这类数据挖掘称为时间序列数据挖掘(timeseriesdatamining,TSDM),CAUC,时间序列数据挖掘的主要研究内容,时间序列数据变换时间序列数据库相似搜索时间序列聚类、分类分析时间序列可视化时间序列分割和模式发现时间序列预测,CAUC,时间序列数据变换,时间序列数据变换就是将原始时间序列映射到某个特征空间中,并用它在这个特征空间中的映像来描述原始的时间序列。这样可以实现数据压缩,减少计算代价。目前已有的时间序列数据表示主要有离散傅里叶变换(DFT)奇异值分解(SVD)离散小波变换(DWT)动态时间规整(DTW)分段合计近似(PAA)分段线性表示(PLR)分段多项式表示(PPR),CAUC,动态时间规整(DTW),例1.序列A：1,1,1,10,2,3序列B：1,1,1,2,10,3例2.,CAUC,时间序列Q=q1,q2,qn；C=c1,c2,cm定义距离-相异矩阵其中：为欧几里的距离当对象q和c越相似或越接近,其值越接近0;两个对象越不相同,其值越大,CAUC,动态时间规整(DTW),定义弯曲路径弯曲路径满足以下条件:1)有界性:即max(m,n)Km+n-1;2)边界条件:w1=D_matrix(q1,c1)与wK=D_matrix(qn,cm),即弯曲路径的起止元素为距离矩阵的斜对角线上的两端元素。3)连续性:给定wk=D_matrix(qa,cb)、wk-1=D_matrix(qa,cb),必须a-a1&b-b1,即弯曲路径中的元素是相互连续的。4)单调性:对wk=D_matrix(qa,cb)、wk-1=D_matrix(qa,cb),必须a-a0&b-b0,也就是说路径w通过点(i,j)同时必须至少通过点(i-1,j),(i-1,j-1)或(i,j-1)中的一个,强制保证弯曲路在时间轴上是单调的。,CAUC,动态时间规整(DTW),序列Q和C的弯曲路径映射如图（1）图（1）图（2）,CAUC,动态时间规整(DTW),CAUC,动态时间规整(DTW),相似搜索的判据,如下式:其中：K的作用是对不同的长度的规整路径做补偿。,CAUC,动态时间规整(DTW),思考：怎样得到最小的路径？-穷举搜索法？-动态规划？,动态规划算法设有点(i,j)在最佳路径上,那么从点(1,1)到(i,j)的子路径也是局部最优解,也就是说从点(1,1)到点(m,n)的最佳路径可以由时间起始点(1,1)到终点(m,n)之间的局部最优解通过递归搜索获得。即:最终时间序列弯曲路径最小累加值为Sm,n。从Sm,n起沿弯曲路径按最小累加值倒退直到起始点S1,1即可找到整个弯曲路径。,CAUC,动态时间规整(DTW),基本思想：首先利用线性化分段方法将时间序列转换为一离散的线性分段序列，然后根据其变化形态利用形态相似性度量和神经网络模糊聚类算法对各线性分段进行聚类分析并为每个类分