基于动态时间弯曲的数据流模式匹配方法

摘要

本发明公开了一种基于动态时间弯曲的数据流模式匹配方法。首先，通过编码识别数据流转折模式，将数据流分割为包含完整波动趋势的子段；然后，利用第一类切比雪夫多项式分解子段，提取切比雪夫系数作为子段特征；最后，在数据流上基于局部模式匹配进行增量式的动态规划计算，实现快速的数据流模式匹配。本发明在匹配精度和计算效率方面都以较大的程度优于现有的方法，在人们的日常活动和工业生产中可发挥重要作用，如在金融交易、交通管理、气象观测、工业流程监控、医疗诊断等应用中，对大规模采样数据或高速动态数据流进行异常检测、风险监控、自动应答等。

主权项

一种基于动态时间弯曲的数据流模式匹配方法，其特征在于，包括以下步骤：(1)分段特征抽取，具体包括以下子步骤：(1.1)对数据流T做移动平滑处理，得到平滑数据流T'；(1.2)基于滑动窗口依次截取T'的相邻3点，并计算平均值，通过判断各点与平均值的大小关系对其编码，得到T的编码序列C_T，并定义转折模式表TP_table；(1.3)顺序扫描C_T，对每对相邻编码组合查询TP_table中的转折模式，如果模式匹配，则将该编码组合所在位置作为T的分段点，得到子段S_i；(1.4)对S_i做Z‑规范化处理，得到规范化的子段S_i'；(1.5)采用第一类切比雪夫多项式分解S'_i，计算前a个多项式系数c_i作为子段特征，构造子段特征向量V'_i＝[c₁,c₂,...,c_a]；(1.6)扫描完毕，将现有的T切分为X条子段，保存它的分段切比雪夫近似表示PCHA(T)＝{V'₁,...,V'_X}；(2)在线模式匹配，具体包括以下子步骤：(2.1)根据步骤(1)对查询序列Q做相同处理，将其切分为M条子段，得到Q的分段切比雪夫近似表示PCHA(Q)＝{V₁,...,V_M}；(2.2)根据实际应用需求设定模式匹配阈值ε，初始化动态规划表(2.3)计算V₁与V'₁的距离dist(V₁,V'₁)，记入Table的单元格cell(1,1)，作为动态规划最优路径ξ的起始路径点p_1,1；(2.4)计算{dist(V₂,V'₁),dist(V₂,V'₂),dist(V₁,V'₂)}，通过比较得到三者的最小值min，将min+dist(V₁,V'₁)记入{cell(2,1)，cell(2,2)，cell(1,2)}中的相应单元格，作为ξ的第二个路径点；(2.5)假设ξ的当前路径点是p_i,j，则计算{dist(V_i+1,V'_j),dist(V_i+1,V'_j+1),dist(V_i,V'_j+1)}，并筛选其中最小值min，将min+dist(V_i,V'_j)记入{cell(i+1,j)，cell(i+1,j+1)，cell(i,j+1)}中的相应单元格，作为ξ的最新路径点；(2.6)循环执行步骤(2.5)，直至PCHA(Q)完全匹配，得到最优路径ξ＝{p_1,1,…,p_M‑1,j,p_M,N}，N表示与Q匹配的子序列长度；(2.7)比较cell(M,N)与ε的大小，若cell(M,N)≤ε，则将ξ所对应的数据流子序列加入模式匹配结果集R，并以cell(V₁,V'_N+1)作为下一条最优路径ξ'的起点；若cell(M,N)>ε,则以dist(V₁,V'₂)作为下一条最优路径ξ'的起点；(2.8)重复执行步骤(2.3)～(2.7)计算ξ'，匹配下一条子序列；(2.9)扫描数据流完毕，返回结果集R。