时间序列之动态时间规整

1、LOGO姓名：罗云生姓名：罗云生 学号：学号：1405024时间序列数据挖掘时间序列数据挖掘Contents时间序列数据挖掘时间序列数据挖掘综述综述1动态时间规整的基本原理动态时间规整的基本原理2时间序列符号化方法时间序列符号化方法3CAUC时间序列数据挖掘时间序列数据挖掘综述综述v时间序列时间序列 指将某种现象某一个统计指标在不同时间上的各个数值，按时间先后顺序排列而形成的序列v时间序列数据挖掘时间序列数据挖掘 在对时间序列进行数据挖掘的过程中, 必须考虑数据集之中数据间存在的时间关系, 这类数据挖掘称为时间序列数据挖掘(time series data mining,TSDM)CAUC时间

2、序列数据挖掘的主要研究内容时间序列数据挖掘的主要研究内容v时间序列数据变换v时间序列数据库相似搜索v时间序列聚类、分类分析v时间序列可视化v时间序列分割和模式发现v时间序列预测CAUC时间序列数据变换时间序列数据变换时间序列数据变换就是将原始时间序列映射到某个特征空间中, 并用它在这个特征空间中的映像来描述原始的时间序列。这样可以实现数据压缩, 减少计算代价。目前已有的时间序列数据表示主要有 离散傅里叶变换( DFT) 奇异值分解(SVD) 离散小波变换(DWT) 动态时间规整(DTW) 分段合计近似(PAA) 分段线性表示(PLR) 分段多项式表示(PPR)CAUC动态时间规整动态时间规整(

3、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 , , cmv 定义距离-相异矩阵其中： 为欧几里的距离当对象q和c 越相似或越接近, 其值越接近0;两个对象越不相同, 其值越大CAUC动态时间规整动态时间规整(DTW) 2cj)- (qicj) , d(qiv 定义弯曲路径 弯曲路径满足以下条件:1)有界性:即max(m , n)K m + n -1;2) 边界条件:w1 = D_matrix(q1 , c1)与wK = D_matrix(qn , cm

4、), 即弯 曲路径的起止元素为距离矩阵的斜对角线上的两端元素。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 - a0 &b -b0 , 也就是说路径w 通过点(i , j)同时必须至少 通过点(i -1, j), (i -1 , j -1)或(i , j -1)中的一个, 强制保证弯曲路 在时间轴上是单调的。 CAUC动态

5、时间规整动态时间规整(DTW) 序列Q和C的弯曲路径映射如图（1）图（图（1） 图（图（2）CAUC动态时间规整动态时间规整(DTW) CAUC动态时间规整动态时间规整(DTW) v 相似搜索的判据, 如下式:其中：其中：K的作用是对不同的长度的规整路径做补偿。CAUC动态时间规整动态时间规整(DTW) 思考：怎样得到最小的路径？-穷举搜索法？-动态规划？v 动态规划算法 设有点(i , j)在最佳路径上, 那么从点(1, 1)到(i , j)的子路径也是局部最优解, 也就是说从点(1,1)到点(m , n)的最佳路径可以由时间起始点(1, 1)到终点(m , n)之间的局部最优解通过递归搜索获得。即: 最终时间序列弯曲路径最小累加值为Sm, n 。从Sm , n 起沿弯曲路径按最小累加值倒退直到起始点S1 , 1 即可找到整个弯曲路径。CAUC动态时间规整动态时间规整(DTW) 基本思想：首先利用线性化分段方法将时间序列转换为一离散的线性分段序列，然后根据其变化形态利用形态相似性度量和神经网络模糊聚类算法对