在长的时间序列上使用形状语法对手绘图案进行高效匹配(Shape Grammar Extraction for Efficient Query-by-Sketch Pattern Matching in Long Time Series)

数千甚至数百万的时间步的长的时间序列,在许多应用领域是常见的,但是我们想要交互性的探索这些时间序列及其困难。通常我们的分析任务数据是识别特定模式,但是找到有趣的模式是非常复杂的和需要大量的计算。我们提出一种有效的方法来探索用户绘制的模式,结合领域专家的知识,通过形状语法的方法来探索时间序列数据。形状语法是从时间序列中提取我们定义的基本形状组合。我们使用比率值来表示这些基本形状,使用对比值进行模式匹配。我们提出的模式匹配方法是基于幅度,尺度和翻译不变性。在图1中,将感兴趣的草图模式与时间序列数据匹配。 我们能够基于梯度比对非常大的时间序列进行实时的模式匹配[1]。

shapegrammer

图1:工作流程的示意图

首先,我们将计算相邻时间序列点之间的梯度的比率。然后,我们将梯度比分类成由基本的形状构成的序列。接下来,我们使用正则表达式对原始数据的进行计算。最后,用户可以通过绘制手绘图案来搜索时间序列中的感兴趣模式。

pattern

图2:基本元素

我们可以定义一些基本的元素。在图2中,我们定义了13种基本形状时间序列。每种形状包含有两个梯度,可以使用斜率表示。 值的范围为0.0-1.0。 (a)比值通过将最低梯度的绝对值除以最高来计算梯度。 (b)比值是非零梯度的绝对值。(c)绝对梯度的比值为1.0(d)线性增加,减少和零梯度。 这些都是基于用户草图的输入提取出的基本的元素。我们计算每种基本元素的两个梯度,对于不同的基本元素,我们斜率的定义不同。

当出现连续的递增递减的序列的时候,我们可以按照图3进行近似。在图4中,我们可以对我们定义的基本元素的组合进行近似。

increase

图3:连续梯度近似

approximate

图4:组合梯度近似

table

图5:梯度近似对照表

在图5中,我们可以看到第一列是连续的基本元素,第三列是其近似值,第二列是第一列的正则表达式。用户可以收现手绘一张草图,然后我们提取其中的关键的节点, 使用基本元素的写对与提取的草图进行匹配。匹配上的基本元素可能有多个,然后再提取出匹配元素的正则表达式,使用正则表达式对,时间序列进行匹配,在图6中,红色为匹配上的线段。

steam

图6:手绘草图匹配过程

sketch

图7:输入手绘草图

caseshape

图8:案例分析

在图7中,我们可以看到系统的整体界面, 对用户输入的手绘草图进行匹配后得效果。在图8种,第一个时间序列为原始的数据,第二个时间序列重,红色未匹配上的序列。都可以对第二个时间序列使用正则表达式作进一步的近似,再进行匹配。

本文提出了基于视觉查询的形状语法,它适合于用户实时绘制图案匹配,它不是直接对原始数据进行操作,而是对我们定义的符号空间中进行操作。我们用十万个时间点测试了我们的算法。 由于我们的算法具有线性时间复杂性,处理是毫秒级。我们使用Dart框架,它只支持非重叠的正则表达式匹配该方法不适用于低分辨率周期数据,因为基于正则表达式的平滑操作可能使周期性失真。

[1] Prithiviraj K. Muthumanickam, Katerina Vrotsou, Matthew Cooper, Jimmy Johansson. Shape Grammar Extraction for Efficient Query-by-Sketch Pattern Matching in Long Time Series. In Proceedings of IEEE Conference on Visual Analytics Science and Technology (VAST’16), pages 121-130, Baltimore, USA, Oct. 23-28, 2016.

评论关闭。