数字趋势序列子序列匹配的DTW快速搜索算法

"数字趋势序列的子序列匹配算法 (2007年)，作者：贾素玲、陈当阳，北京航空航天大学经济管理学院" 在时序数据挖掘领域，传统的趋势序列分析方法存在一定的局限性。为了克服这些缺点，本文提出了“数字趋势序列”和“趋势序列展开”的新概念。数字趋势序列是一种对时间序列数据进行抽象和简化的方式，它关注的是数据片段的斜率，而非具体数值，以更好地捕捉数据的趋势变化。 文章的核心是设计了一种名为DTW（Dynamic Time Warping）的快速搜索算法来解决数字趋势序列之间的子序列匹配问题。DTW是一种常用于比较两个时序数据的相似性的技术，尤其适用于不完全同步或长度不同的序列。在数字趋势序列中，片段斜率对应于弧度值，这个度量方式更直观地反映了片段的趋势方向和强度。 算法由三部分组成： 1. **DTW顺序搜索**：这是基础的动态时间规整过程，通过构建一个距离矩阵来衡量两个序列的相似性。在每一步中，找到使得两个子序列匹配成本最低的对应点。 2. **约束机制**：引入约束条件以减少搜索空间，提高效率。例如，可以设置允许的时间偏移范围，限制匹配路径的形状等，这样可以在保持匹配精度的同时降低计算复杂性。 3. **冗余消除机制**：为了避免重复计算，通过剪枝策略提前终止不必要的计算。这通常基于先前计算的子问题结果，避免重复处理已知不匹配的片段。 作者通过实际的股票数据对DTW-QS算法进行了验证，这表明该算法能够有效地在数字趋势序列中找到相似的子序列，对于识别和预测时间序列中的模式具有潜在价值。这种算法在金融市场的分析、股票趋势预测、以及其他领域的时序数据分析中可能有广泛的应用前景。 关键词：时序数据挖掘，趋势序列，子序列匹配，动态时间规整 中图分类号：TP301.6 文献标识码：A 文章编号：1001-5965(2007)03-0350-04 这篇2007年的论文介绍了数字趋势序列的概念，并提出了一种基于DTW的快速搜索算法来解决这些序列的子序列匹配问题，这对于时序数据挖掘提供了新的思路和工具。