用手绘无尺度限制草图查询时间序列(Expressive Time Series Querying with Hand-Drawn Scale-Free Sketches)

关于时间序列查询的工作已有不少,不论是利用形状定义语言SDL或是正则表达式匹配算法进行查询,还是功能强大的TimeSearcher、基于手绘草图的QuerySketch、QueryLines、RINSE、TimeSketch等。但是他们都有各自的缺点,SDL和正则表达式太不直观,不易于使用,查询系统有都有各自的限制。对于时间序列的查询,目前仍然没有很好的解决方案。

本文来自CHI 2018,设计并实现了时间序列查询系统Qetch,并在其中使用了全新的算法。评估表明,Qetch在许多任务中表现优异。

Qetch简介

目前基于手绘草图的查询系统都对绘制有限制,只能在data基础上进行绘制、绘制形状有限制或是需要指明绘制的幅度以及时间长度,而且用户绘制的草图会带有主观倾向错误,例如夸大特征等。而不基于手绘草图的系统又不够直观,用户难以查询到心中想象的模式。Qetch允许用户自由绘制草图,并且提出了新的匹配算法。

Qetch’s user interface

Qetch’s user interface

首先Qetch将时间序列做不同程度的平滑,然后对于每个平滑后的时间序列,按照上升或者是下降分段,而不考虑倾斜的角度,因为任何两个角度不同的线段,只要同为上升或是同为下降,就可以通过伸缩相互转化。用户手绘的草图也用相同的方式切割,然后进行匹配。

本文提出了新的距离测量方法,之前的距离计算都是将手绘草图与匹配到的序列整个计算,本文的方法则是将草图切割后的每个切割段与时间序列中对应的段进行距离计算。

Qetch可以同时搜索多个时间序列,多个画板在时间轴上对齐,用户可以通过草图的相对位置调整多个序列查询时间。Qetch还支持3个正则表达式运算:重复、重复n次以及not。

评估
User study

User study

Qetch在使用正则表达式的查询中表现优异,例如查询重复模式、查询异常。在对于多个时间序列的相关查询中,Qetch表现依然优异。但是Qetch的算法只适用于手绘草图到时间序列的匹配,在时间序列与时间序列的标准匹配测试中,Qetch的匹配表现比DTW差。

总结

Qetch确实很好的解决了手绘草图查询的问题,但是同时也带来了别的问题。对于上升下降斜率敏感的模式,或者是大量高维度时间序列的查询,Qetch依然束手无策。

参考文献

Mannino, Miro, and Azza Abouzied. “Expressive Time Series Querying with Hand-Drawn Scale-Free Sketches.” Proceedings of the 2018 CHI Conference on Human Factors in Computing Systems. ACM, 2018.

评论关闭。