核心挑战
直接进行时序相似搜索面临几个根本性的挑战：
（图片来源网络，侵删）
- 维度灾难：时间序列通常很长，比如一个传感器每秒采集一次数据，一天就有86400个数据点，即86400维，在高维空间中，距离度量变得没有意义（“所有点都差不多远”）,而且计算成本极高。
- 数据偏斜：不同序列的长度可能不同,如何比较一个长度为100的序列和一个长度为1000的序列？
- 距离度量的计算成本：即使维度不高，计算两条序列的距离（如欧氏距离）也需要线性时间，在数百万条序列中,对每一条都进行计算是不可行的。
- 序列的相位/时间偏移：两条本质上相同的序列，可能因为时间起始点不同（相位偏移）而看起来完全不同，一个正弦波和另一个向左平移了半个周期的正弦波,欧氏距离会非常大。
核心技术思想
为了应对这些挑战,高效时序相似搜索技术主要围绕以下两个核心思想展开：
- 降维：将高维的时间序列映射到一个低维空间，同时尽可能保留原始序列的相似性特征，这样,我们可以在低维空间中进行快速的近似搜索。
- 下界剪枝：利用数学性质，设计一种距离度量（下界），使得
LowerBound(Q, C) <= Distance(Q, C)，这意味着，如果一个候选序列C与查询序列Q的下界距离已经大于当前找到的最小距离，C的真实距离也必然更大，可以直接将其“剪枝”,无需进行精确计算。
主流技术分类与详解
目前主流的技术可以分为三大类：基于特征提取的方法、基于模型的方法和基于深度学习的方法。
基于特征提取的方法
这是最经典和广泛应用的一类方法，核心是降维。
a) 傅里叶变换
- 核心思想：任何时间序列都可以看作是不同频率的正弦波和余弦波的叠加，通过傅里叶变换，我们可以将序列从时域转换到频域，得到一组代表不同频率成分的系数，高频系数通常代表噪声,可以被丢弃。
- 如何工作：
- 对所有数据库中的序列和查询序列都进行FFT，只保留前
k个最重要的频率系数（实部和虚部）。 - 将这些低维系数作为序列的“指纹”存入索引结构（如R-tree, KD-tree）。
- 搜索时，计算查询序列的FFT指纹，在低维空间中找到最近的邻居,然后对这些候选进行精确的距离验证。
- 对所有数据库中的序列和查询序列都进行FFT，只保留前
- 优点：
- 计算速度快,FFT有成熟的算法实现。
- 对相位偏移不敏感（因为频域表示是全局的，不受起始点影响）。
- 缺点：
- 丢失了局部的时间信息。
- 对非平稳、突变的序列效果不佳。
b) 离散小波变换
- 核心思想：小波变换被誉为“数学显微镜”，它同时提供时间和频率的局部信息，它通过将序列与一组不同尺度和位置的“小波”函数进行卷积来分解序列。
- 如何工作：
- 对序列进行DWT,得到不同分辨率下的近似系数和细节系数。
- 保留最重要的
k个系数,构建低维特征向量。 - 与FFT类似,在低维空间进行搜索和精确验证。
- 优点：
- 能同时捕捉时域和频域特征,对局部模式更敏感。
- 压缩效果通常比FFT更好。
- 缺点：
- 实现比FFT复杂。
- 对边界效应较敏感。
c) 基于符号表示的方法
- 核心思想：将连续的数值序列转换成离散的符号序列，从而将问题转化为字符串相似搜索,这是一个研究得非常成熟的领域。
- 如何工作：
- 分段：使用滑动窗口将序列分割成若干段。
- 符号化：对每个段进行编码，生成符号，常见方法有：
- PAA (Piecewise Aggregate Approximation)：将每个窗口内的数据点取平均值,用这个平均值代表整个窗口。
- SAX (Symbolic Aggregate approXimation)：在PAA的基础上，将平均值映射到一个有限的字母表中（高斯分布下，将数值区间映射为A, B, C等）。
- 索引与搜索：为符号序列建立索引（如后缀数组、后缀树），然后使用高效的字符串距离（如编辑距离）进行搜索。
- 优点：
- 将问题转化为离散空间,可以利用成熟的字符串搜索算法。
- 数据压缩率高,存储和计算开销小。
- 缺点：
- 信息损失较大,搜索精度可能降低。
- 符号化过程是关键,需要仔细设计。
基于模型的方法
这类方法不直接比较原始序列,而是比较它们的生成模型。
（图片来源网络，侵删）
- 核心思想：为每个时间序列训练一个生成模型（如ARIMA、高斯过程），然后用模型的参数（如自回归系数）作为序列的“指纹”。
- 如何工作：
- 为数据库中的每条序列训练一个模型,提取模型参数。
- 在低维的模型参数空间中建立索引。
- 搜索时，为查询序列训练模型，找到参数空间中最近的邻居,再进行精确验证。
- 优点：
- 能够捕捉序列的动态特性。
- 对噪声有较好的鲁棒性。
- 缺点：
- 模型训练成本高,不适合在线或实时场景。
- 假设序列符合特定的模型，如果假设不成立,效果会很差。
基于深度学习的方法
这是目前最前沿、效果最好的方法，尤其是在处理复杂、非平稳的序列时。
- 核心思想：使用神经网络（特别是RNN, LSTM, 1D-CNN, Transformer）作为可学习的特征提取器，将序列映射到一个稠密的低维向量（嵌入空间 Embedding Space），在这个空间中,相似序列的向量距离也很近。
- 如何工作：
- 模型训练：
- 监督学习：有标签数据，使用Siamese Network（孪生网络）或Triplet Network（三元组网络）进行训练，网络的目标是让相似对的向量距离变小,不相似对的向量距离变大。
- 自监督学习：无标签数据，通过设计预训练任务（如掩码预测、上下文预测）让模型学习序列的通用表示，DTW (Dynamic Time Warping) 作为一种强大的对齐手段,也被用于自监督预训练。
- 索引与搜索：
- 将训练好的神经网络作为编码器，对数据库中所有序列进行编码,得到它们的嵌入向量。
- 使用高效的向量索引技术（如 FAISS (Facebook AI Similarity Search), Annoy, HNSW）来组织这些向量。
- 搜索时，将查询序列输入编码器得到其向量，然后在索引中快速找到最近的Top-K向量,再返回对应的原始序列。
- 模型训练：
- 优点：
- 表示能力最强：能自动学习最有效的特征,无需手动设计。
- 效果最好：在大多数复杂任务上,性能超越传统方法。
- 端到端优化：整个搜索流程可以联合优化。
- 缺点：
- 训练成本高：需要大量数据和计算资源。
- 推理延迟：虽然搜索快,但编码查询序列本身需要时间。
- “黑盒”特性：模型的可解释性较差。
经典算法示例
- ST (Search in Time)：最早的暴力搜索算法，逐一计算距离,效率极低。
- ST (Search in Time) with LB_Keogh：一种里程碑式的算法，它为DTW距离设计了一个非常紧的下界，利用DTW路径的对角线约束来快速剪枝,极大地提高了效率。
- ULM/ULIG (Upper/Lower Bounds on Measures)：为各种距离度量（欧氏距离、DTW等）设计了多种数学上严格的上界和下界,用于不同的剪枝场景。
- FastDTW：一种近似DTW算法，通过多尺度粗化策略，在保证近似精度的同时，将DTW的时间复杂度从
O(N^2)降低到O(N)。
技术选型与未来趋势
如何选择？
- 追求极致速度，数据简单：考虑 SAX 或 FFT。
- 需要处理局部模式，数据平稳：考虑 DWT。
- 追求高精度，有充足计算资源：基于深度学习的方法 是首选,特别是使用预训练模型。
- 经典学术问题，需要可解释性：DTW + LB_Keogh 仍然是一个强大的基线。
未来趋势
- 与深度学习的深度融合：利用深度学习学习更强大的特征，并结合传统方法（如DTW）的归纳偏置,设计出更鲁棒的模型。
- 自监督学习的普及：在无标签时间序列数据占绝大多数的今天,自监督学习将成为学习通用时间序列表示的主流范式。
- 可解释性：让深度学习模型不仅能给出“相似”的结果，还能解释“为什么相似”,例如高亮显示相似的时间段。
- 面向特定场景的优化：针对金融、医疗、物联网等不同领域的数据特性,开发专门的搜索技术和模型。
- 实时流式搜索：如何高效地对持续不断产生的时间流进行相似搜索,是一个重要的研究方向。
高效时序相似搜索是一个从数学优化（傅里叶、小波、下界剪枝）到离散化（SAX），再到端到端学习（深度学习）的演进过程，每种技术都有其适用场景和优缺点，对于追求最高精度的复杂应用，基于深度学习的嵌入向量搜索无疑是领导者，而经典的FFT、DWT和DTW及其变种，因其高效、轻量和可解释性,在许多工业场景中依然扮演着不可或缺的角色。
（图片来源网络，侵删）
