软件学报

作者：李盼盼，宋韶旭，王建民

单位：李盼盼，清华大学 软件学院, 北京 10008411,宋韶旭，清华大学 软件学院, 北京 100084;大数据系统软件国家工程实验室(清华大学), 北京 100084;北京信息科学与技术国家研究中心(清华大学), 北京 10008402,王建民，清华大学 软件学院, 北京 100084;大数据系统软件国家工程实验室(清华大学), 北京 100084;北京信息科学与技术国家研究中心(清华大学), 北京 10008403

关键词：时间序列;对称模式;距离度量;动态规划

基金：国家重点研发计划（2019YFB1705301，2019YFB1707001）；国家自然科学基金（62072265，62021002，71690231）；工信部2020年新兴平台软件项目

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

来源：2022年第3期

《软件学报》期刊编辑部

查看软件学报杂志2022年第3期