时间序列对称模式挖掘
CSTR:
作者:
作者单位:

作者简介:

李盼盼(1996-),男,硕士生,主要研究领域为时间序列模式挖掘;
王建民(1968-),男,博士,教授,博士生导师,CCF高级会员,主要研究领域为数据库,工作流,大数据与知识工程;
宋韶旭(1981-),男,博士,副教授,博士生导师,CCF专业会员,主要研究领域为数据库,数据质量,时序数据清理,大数据集成.

通讯作者:

宋韶旭,E-mail:sxsong@tsinghua.edu.cn

中图分类号:

基金项目:

国家重点研发计划(2019YFB1705301,2019YFB1707001);国家自然科学基金(62072265,62021002,71690231);工信部2020年新兴平台软件项目


Time Series Symmetric Pattern Mining
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    随着信息化和工业化的融合,物联网和工业互联网蓬勃发展,由此产生了以时间序列为代表的大量工业大数据.时间序列中蕴含着很多有价值的模式,其中,对称模式在各类时间序列中广泛存在.挖掘对称模式对于行为分析、轨迹跟踪、异常检测等领域具有重要的研究价值,但时间序列的数据量往往高达几十甚至上百GB.使用直接的嵌套查询算法挖掘对称模式可能花费数月乃至数年的时间,而索引、下界和三角不等式等典型加速技术最多只能产生一两个数量级的加速.因此,基于动态时间规整算法的启发,提出了一种能够在O(w×|T|)的时间复杂度内挖掘出时间序列所有对称模式的方法.具体来说,给定对称模式长度约束,基于区间动态规划算法计算出对称子序列,进而依据贪心策略选择数量最多且不重叠的对称模式.此外,还研究了在时间序列数据流挖掘对称模式的算法,并根据窗口内数据的特征动态调节窗口大小,保证了对称模式数据的完整性.采用1个人工数据集、3个真实数据集在不同数据量下对上述方法进行实验.由实验结果可知,与其他对称模式挖掘方法相比,该方法在模式挖掘结果及时间开销方面均有较好的表现.

    Abstract:

    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 series. 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 magnitude at most. Therefore, based on the inspiration of the dynamic time warping algorithm, this study 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 the greedy strategy. In addition, we also study the algorithm for mining symmetric patterns in the time series data 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 be seen from the experimental results that compared with other symmetric pattern mining methods, this method has better performance in terms of pattern mining results and time overhead.

    参考文献
    相似文献
    引证文献
引用本文

李盼盼,宋韶旭,王建民.时间序列对称模式挖掘.软件学报,2022,33(3):968-984

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-06-30
  • 最后修改日期:2021-07-31
  • 录用日期:
  • 在线发布日期: 2021-10-21
  • 出版日期: 2022-03-06
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号