基于小波和动态时间弯曲的主题查找算法

Finding motifs based on wavelet and dynamic time warping

针对以前查找图形主题算法的精度和时间复杂度不能兼容的问题,提出了基于小波和动态时间弯曲(DTW)的形状主题查询算法。本算法先利用小波变换进行数据降维并剪枝,以降低计算查找主题的复杂度;再应用DTW的高精度计算的特点来查找图形主题,同时结合v-shift公式,忽略了在垂直方向的距离,这样查找图形主题可以解决在现实世界中因形状大小不同而相似的问题。实验结果表明该方法具有较高的匹配精度和较低的计算代价,可以找到图形相似的主题,并不会产生漏报,具有很强的实际意义。

Since the proposed finding motifs algorithms could not combine the accuracy with complexity, and could not find the similar shapes, this paper proposed a finding motifs algorithm based on wavelet and dynamic time warping. Employed wavelet transform and a pruning strategy to reduce data dimension and complexity in motif finding, respectively. Because of its high accuracy, USED DTW to find the shape motifs. And combined with the formula v-shift, which ignored the vertical distance, this algorithm could find out the shapes which differed in size but actually similar to the predefined shape. Experiment shows that this algorithm not only has a higher matching accuracy and lower calculation cost, but also can find the shape motifs which are similar to the real world shape. It has great practical significance and there is no dismissal.