寻找最不寻常时间序列子序列的新颖启发式方法

### 寻找最不寻常时间序列子序列的新颖启发式方法 在时间序列数据分析中，挖掘出那些与众不同的子序列（即时间序列不和谐子序列）是一项重要的任务。本文将介绍一些新颖的启发式方法，用于更高效地发现时间序列中的不和谐子序列，并且会详细阐述相关的背景知识、通用框架以及提出的新算法。 #### 1. 背景知识 ##### 1.1 时间序列不和谐子序列 直观上，时间序列不和谐子序列是与它最接近的匹配子序列差异很大的子序列。但通常情况下，给定子序列（除自身外）的最佳匹配往往与该子序列非常接近。例如，在位置 p 的某个子序列，其最接近的匹配可能是位置 q 的子序列，而 q 与 p 仅相差几个点。这种匹配被称为平凡匹配，通常不是我们所关注的。在寻找不和谐子序列时，应排除平凡匹配，否则会影响我们找到真正的不和谐子序列，因为真正的不和谐子序列可能也与其最接近的平凡匹配相似。 - **非自身匹配定义**：给定一个时间序列 T，包含一个从位置 p 开始、长度为 n 的子序列 C，以及一个从位置 q 开始的匹配子序列 M。如果 |p – q| ≥ n，则称 M 是 C 的非自身匹配。 - **时间序列不和谐子序列定义**：给定一个时间序列 T，从位置 p 开始、长度为 n 的子序列 C，如果它与其最近的非自身匹配的距离最大，则称 C 是 T 的顶级不和谐子序列。 ##### 1.2 符号聚合近似（SAX） 长度为 n 的时间序列 C = c1...cn 可以通过分段聚合近似（PAA）技术，将其分割成 w 个等大小的段，并用每段的均值 di 替换该段，从而在降维的 w 维空间中表示为另一个时间序列 D = d1...dw。之后，时间序列 D 通过查找表将每个实值 di 映射为一个符号 ai，转换为符号序列 A = a1...aw。这个查找表包含将高斯分布划分为任意数量（3 到 10 个）等概率区域的断点。这种离散化方法称为 SAX，它基于降维后的时间序列具有高斯分布的假设。 给定两个长度相同的时间序列 Q 和 C，将它们转换为 PAA 表示 Q’ 和 C’ 后，可以定义原始时间序列之间欧几里得距离的下界近似： \[DR(Q’, C’) = \sqrt{\frac{n}{w}\sum_{i = 1}^{w}(q_i' - c_i')^2}\] 进一步将数据转换为 SAX 表示（即两个符号字符串 Q’’ 和 C”）后，可以定义一个 MINDIST 函数，返回两个单词的原始时间序列之间的最小距离： \[MINDIST(Q”,C”) = \sqrt{\frac{n}{w}\sum_{i = 1}^{w}dist(q_i”, c_i”)^2}\] dist() 函数可以通过查找表实现，例如表 1 展示了字母表 a = 4 时的查找表。 | | a | b | c | d | | --- | --- | --- | --- | --- | | a | 0 | 0 | 0.67 | 1.34 | | b | 0 | 0 | 0 | 0.67 | | c | 0.67 | 0 | 0 | 0 | | d | 1.34 | 0.67 | 0 | 0 | ##### 1.3 寻找不和谐子序列的通用框架 Keogh 等人提出了一个通用框架，即 HDD 算法，用于在时间序列中寻找不和谐子序列。该算法利用了一个观察结果：只要所讨论的子序列不可能是时间序列不和谐子序列，就可以提前终止内循环。HDD 算法在原始暴力算法（BFDD）的外循环和内循环中分别引入了两种启发式方法，以显著减少 BFDD 的运行时间。以下是该通用框架的伪代码： ```plaintext Function Heuristic_Search (T, n, Outer, Inner) discord_distance = 0 discord_location = NaN for each subsequence p in T ordered by heuristic Outer do if p is marked then continue endif nearest_non_seft_distance = infinity // 最近邻距离 nearest_non_self_location = NaN // 最近邻位置 for each q in T ordered by heuristic Inner do if |p – q| ≥ n then // 非自身匹配 dist = EDist (Tp, Tq, n, nearest_non_seft_distance) if dist < nearest_non_seft_distance then nearest_non_self_distance = dist nearest_non_seft_location = q endif if dist < discord_distance then break // 跳出内循环 endif endfor // 内循环结束 ```