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

LOGO 姓 名 ： 罗 云 生 学 号 ： 1405024时 间 序 列 数 据 挖 掘 Contents 时 间 序 列 数 据 挖 掘 综 述1 动 态 时 间 规 整 的 基 本 原 理2 时 间 序 列 符 号 化 方 法3 CAUC 时 间 序 列 数 据 挖 掘 综 述v时 间 序 列 指 将 某 种 现 象 某 一 个 统 计 指 标 在 不 同 时 间 上 的 各个 数 值 ， 按 时 间 先 后 顺 序 排 列 而 形 成 的 序 列v时 间 序 列 数 据 挖 掘 在 对 时 间 序 列 进 行 数 据 挖 掘 的 过 程 中 , 必 须 考 虑数 据 集 之 中 数 据 间 存 在 的 时 间 关 系 , 这 类 数 据 挖 掘 称为 时 间 序 列 数 据 挖 掘 (time series data mining,TSDM) CAUC 时 间 序 列 数 据 挖 掘 的 主 要 研 究 内 容v时 间 序 列 数 据 变 换v时 间 序 列 数 据 库 相 似 搜 索v时 间 序 列 聚 类 、 分 类 分 析v时 间 序 列 可 视 化v时 间 序 列 分 割 和 模 式 发 现v时 间 序 列 预 测 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 , , cmv定 义 距 离 -相 异 矩 阵其 中 ： 为 欧 几 里 的 距 离当 对 象 q和 c 越 相 似 或 越 接 近 , 其 值 越 接 近 0;两 个 对 象 越 不 相 同 , 其 值 越 大 CAUC动 态 时 间 规 整 (DTW) 2cj)-(qicj),d(qi v定 义 弯 曲 路 径 弯 曲 路 径 满 足 以 下 条 件 :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 - 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) 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) 基 本 思 想 ： 首 先 利 用 线 性 化 分 段 方 法 将 时 间 序 列 转 换 为 一 离 散 的线 性 分 段 序 列 ， 然 后 根 据 其 变 化 形 态 利 用 形 态 相 似 性 度 量 和 神 经网 络 模 糊 聚 类 算 法 对 各 线 性 分 段 进 行 聚 类 分 析 并 为 每 个 类 分 配 一个 类 标 识 符 再 以 类 标 识 符 代 表 所 有 属 于 该 类 的 线 性 分 段 ,得 到 由 各类 标 识 符 所 构 成 的 符 号 序 列 . CAUC时 间 序 列 符 号 化 方 法 LOGO