当对象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 -b′≥0 , 也就是说路径w 通过点(i , j)同时必须至少 通过点(i -1, j), (i -1 , j -1)或(i , j -1)中的一个, 强制保证弯曲路 在时间轴上是单调的。
CAUC
动态时间规整(DTW)
例1.
序列A：1, 1, 1, 10, 2, 3 序列B：1, 1, 1, 2, 10, 3 例2.
CAUC
动态时间规整(DTW)
时间序列Q = q1 , q2 , … , qn；C = c1 , c2 , … , cm 定义距离-相异矩阵
其中： d(qi , cj) (qi - cj)2 为欧几里的距离
C
时间序列符号化方法
基本思想：首先利用线性化分段方法将时间序列转换为一离散的 线性分段序列，然后根据其变化形态利用形态相似性度量和神经 网络模糊聚类算法对各线性分段进行聚类分析并为每个类分配一 个类标识符再以类标识符代表所有属于该类的线性分段,得到由各 类标识符所构成的符号序列.
LOGO
CAUC
动态时间规整(DTW)
序列Q和C的弯曲路径映射如图（1）
图（1）
图（2）
CAUC
动态时间规整(DTW)
CAUC
动态时间规整(DTW)
相似搜索的判据, 如下式:
其中：K的作用是对不同的长度的规整路径做补偿。 思考：怎样得到最小的路径？ --穷举搜索法？ --动态规划？
CAUC
动态时间规整(DTW)
LOGO
时间序列数据挖掘
姓名：罗云生 学号：1405024
CAUC
Contents
1 2
时间序列数据挖掘综述
动态时间规整的基本原理
3
时间序列符号化方法
CAUC
时间序列数据挖掘综述
时间序列 指将某种现象某一个统计指标在不同时间上的各 个数值，按时间先后顺序排列而形成的序列 时间序列数据挖掘 在对时间序列进行数据挖掘的过程中, 必须考虑 数据集之中数据间存在的时间关系, 这类数据挖掘称 为时间序列数据挖掘(time series data mining,TSDM)
动态规划算法 设有点(i , j)在最佳路径上, 那么从点(1, 1)到(i , j)的子路 径也是局部最优解, 也就是说从点(1,1)到点(m , n)的最佳路 径可以由时间起始点(1, 1)到终点(m , n)之间的局部最优解 通过递归搜索获得。即:
最终时间序列弯曲路径最小累加值为Sm, n 。从Sm , n 起 沿弯曲路径按最小累加值倒退直到起始点S1 , 1 即可找到整 个弯曲路径。
CAUC
时间序列数据挖掘的主要研究内容
时间序列数据变换 时间序列数据库相似搜索 时间序列聚类、分类分析 时间序列可视化 时间序列分割和模式发现 时间序列预测
CAUC
时间序列数据变换
时间序列数据变换就是将原始时间序列映射到某个特征空间中, 并用它在这个特征空间中的映像来描述原始的时间序列。这样 可以实现数据压缩, 减少计算代价。 目前已有的时间序列数据表示主要有 离散傅里叶变换( DFT) 奇异值分解(SVD) 离散小波变换(DWT) 动态时间规整(DTW) 分段合计近似(PAA) 分段线性表示(PLR) 分段多项式表示(PPR)