时间序列之动态时间规整.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 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 序列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 基本思想 首先利用线性化分段方法将时间序列转换为一离散的线性分段序列 然后根据其变化形态利用形态相似性度量和神经网络模糊聚类算法对各线性分段进行聚类分析并为每个