时间序列对称模式挖掘-李盼盼，宋韶旭，王建民.pdf
免费下载
软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn
Journal of Software, 2022,33(3):968−984 [doi: 10.13328/j.cnki.jos.006453] http://www.jos.org.cn
©中国科学院软件研究所版权所有. Tel: +86-10-62562563
时间序列对称模式挖掘
∗
李盼盼
1
,
宋韶旭
1,2, 3
,
王建民
1,2,3
1
(清华大学 软件学院, 北京 100084)
2
(大数据系统软件国家工程实验室(清华大学), 北京 100084)
3
(北京信息科学与技术国家研究中心(清华大学), 北京 100084)
通信作者: 宋韶旭, E-mail: sxsong@tsinghua.edu.cn
摘 要: 随着信息化和工业化的融合, 物联网和工业互联网蓬勃发展, 由此产生了以时间序列为代表的大量工业
大数据. 时间序列中蕴含着很多有价值的模式, 其中, 对称模式在各类时间序列中广泛存在. 挖掘对称模式对于
行为分析、轨迹跟踪、异常检测等领域具有重要的研究价值, 但时间序列的数据量往往高达几十甚至上百 GB.
使用直接的嵌套查询算法挖掘对称模式可能花费数月乃至数年的时间, 而索引、下界和三角不等式等典型加速技
术最多只能产生一两个数量级的加速. 因此, 基于动态时间规整算法的启发, 提出了一种能够在 O(w×|T|)的时间
复杂度内挖掘出时间序列所有对称模式的方法. 具体来说, 给定对称模式长度约束, 基于区间动态规划算法计算
出对称子序列,进而依据贪心策略选择数量最多且不重叠的对称模式. 此外, 还研究了在时间序列数据流挖掘对称
模式的算法,并根据窗口内数据的特征动态调节窗口大小, 保证了对称模式数据的完整性. 采用 1 个人工数据集、
3 个真实数据集在不同数据量下对上述方法进行实验. 由实验结果可知, 与其他对称模式挖掘方法相比, 该方法
在模式挖掘结果及时间开销方面均有较好的表现.
关键词: 时间序列; 对称模式; 距离度量; 动态规划
中图法分类号: TP311
中文引用格式: 李盼盼, 宋韶旭, 王建民. 时间序列对称模式挖掘. 软件学报, 2022, 33(3): 968–984. http://www.jos.org.cn/
1000-9825/6453.ht m
英文引用格式: Li PP, Song SX, Wang JM. Ti me Series Symmetric Pattern Mining. Ruan Jian Xue Bao/Journal of Software, 2022,
33(3): 968−984 (in Chinese). http://www.jos.org.cn/1000-9825/6453.htm
Time Series Symmetric Pattern Mining
LI Pan-Pan
1
, SONG Shao-Xu
1,2,3
, WANG Jian-Min
1,2,3
1
(School of Software, Tsinghua Universit y, Beijing 1000 84, Chin a)
2
(National Engineering Laboratory for Big Data Software (Tsinghua University), Beijing 100084, China)
3
(Beijing National Research Center for Information Science and Technology (Tsinghua University), Beijing 100084, China)
Abstra ct : With the integration of informatization and industrialization, the Internet of Things and industrial Internet have flourished,
resulting in a large amount of industrial big data represented by time s eries. There are many valuable patterns in time series, among which
symmetric patterns are widespread in various time series. Mining symmetric patterns has important research value in the fields of
behavior analysis, trajectory tracking, anomaly detection, etc. However, the data volume of time series is often as high as tens or even
hundreds of gigabytes. It can take months or even years to mine symmetric patterns using a direct nested query algorithm, and typical
acceleration techniques such as indexing, lower bounds, and triangular inequalities can only produce speedup of one or two orders of
∗ 基金项目: 国家重点研发计划(2019YFB1705301, 2019YFB1707001); 国家自然科学基金(62072265, 62021002, 71690231);
工信部 2020 年新兴平台软件项目
本文由“数据库系统新型技术”专题特约编辑李国良教授、于戈教授、杨俊教授和范举教授推荐.
收稿时间: 2021-06-30; 修改时间: 2021-07-31; 采用时间: 2021-09-13; jos 在线出版时间: 2021-10-21
李盼盼 等: 时间序列对称模式挖掘
969
magnitude at most. Therefore, b ased o n the insp iration of the d ynamic ti me warping algorith m, this stud y proposes a method that can mine
all the symmetric patterns of the time series within the time complexity of O(w×|T|). Specifically, given the symmetric pattern length
constraint, the symmetric subsequences can be calculated based on the interval dynamic programming. Then the largest number of
non-overlapping symmetric patterns can be selected according to th e greedy strategy. In addition, we also study the algorithm for mining
symmetric patterns in the time series dat a stream, and dynamically adjusts the window size according to the characteristics of the data in
the window to ensure the integrity of the symmetric pattern data. Using one artificial data set and three real data sets to experiment with
the above method under different data volumes, it can b e seen from the experimental results that compared with other symmetric pattern
mining methods, this method h as b etter performance in t erms of p attern mining r esults and ti me overhead.
Key words: time series; symmetri c pattern; dist ance me asurement; dyna mic programming
1 引 言
互联网、物联网、云计算等计算机科学技术经过长时间的共同发展与不断融合, 积累了规模庞大、种类
繁多的海量数据, 涉及计算机科学、宏观经济、军事科技、医疗卫生等诸多领域. 在这些海量数据之中, 有一
类按照数据生成的时间顺序, 把同一个变量或记录的数据值, 或者高维数据的一个元组, 排列而成的记录数
据信息, 被称为时间序列. 时间序列是工业界应用广泛的、与时间维度相关的高维数据, 也是数据挖掘技术的
一种主要研究对象. 挖掘时间序列中的对称子模式, 可以分析时间序列的对称特征, 方便时间序列的分类与
预测, 抽取出时间序列中蕴含的模式与规律, 既可以为未来的决策提供理论与数据支持, 又可以检测、判断、
预防突发错误的出现, 指导实际生产.
1.1 问题背景
随着信息技术的普及和发展, 各行各业, 尤其是工业领域, 通过相应的传感器和信息系统积累了大量的
时间序列数据, 对特定领域或者特定模式的时间序列数据, 利用数学建模、机器学习等方法进行建模和分析,
已经成为一项意义重大且研究价值极高的项目课题.
大部分时间序列数据中数据点会随着时间的变化而产生一定的变化规律
[1]
, 例如股票走势图、温度变化
图和行车路线图等时间序列数据, 在某些时间周期内呈现出较强的对称性. 然而, 如图 1 所示, 时间序列的对
称性并不像回文字符串序列的对称性具有非常严格的数学定义, 时间序列的对称性与时间间隔、序列模式和
数据特征密切相关. 因此, 需要立足于时间序列的时间和数据特征挖掘其子序列的对称性. 一般来说, 只要原
始时间序列和其反转时间序列的距离在合理阈值之内, 就可以认定为对称时间序列. 对称时间序列在挖掘机、
运输车等具有大量重复作业的工业场景频繁出现, 且每个对称模式都意味着一个完整作业的生命周期. 因此,
挖掘对称模式对于其轨迹跟踪和作业分析具有重要意义.
图 1 回文字符串序列和对称时间序列对比
(a) (b)
of 17
免费下载
【版权声明】本文为墨天轮用户原创内容，转载时必须标注文档的来源（墨天轮），文档链接，文档作者等基本信息，否则作者和墨天轮有权追究责任。如果您发现墨天轮中有涉嫌抄袭或者侵权的内容，欢迎发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。
下载排行榜
评论