时间序列之动态时间规整

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Company Logo,#,单击此处编辑母版标题样式,姓名：罗云生,学号：,1405024,时间序列数据挖掘,Contents,时间序列数据挖掘,综述,1,动态时间规整的基本原理,2,时间序列符号化方法,3,CAUC,时间序列数据挖掘,综述,时间序列,指,将某种现象某一个统计指标在不同时间上的各个数值，按时间先后顺序排列而形成的序列,时间序列数据挖掘,在对,时间序列,进行数据,挖掘的过程中,必须考虑数据集之中数据间存在的时间,关系,这类数据挖掘称为时间序列,数据挖掘,(time series data mining,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)K m + 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 - a,1&b -b 1 ,即弯曲路径中的元素是相互连续的。,4),单调性,:,对,wk = D_matrix(qa , cb),、,wk-1 =D_matrix(qa , cb) ,必,须,a - a,0 &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),基本思想：首先,利用线性,化分,段方法将时间序列转换为一,离散的线性,分段,序列，然后,根据其变化,形态利用形态,相似性度量,和神经网络,模糊聚类算法对各,线性分段,进行聚类分析并为每个类,分配一,个类标识符再以类标识符代表,所,有属于该类的线性,分段,得到由各,类,标识符所构成的符号,序列,.,CAUC,时间序列符号化方法,Thank You !,