王 菊,刘付显,靳春杰

(1. 空军工程大学防空反导学院, 陕西 西安 710051;2. 中国人民解放军93527部队, 河北 张家口 075000)

0 引 言

时间序列是一种按照时间先后顺序排列的记录序列,具有很广泛的应用范围,如医药、生物、计算机、金融等[1-2]。而模体是指时间序列中一些相似度很高的时间序列片段[3]。由于模体中包含被研究时间序列的一些很重要信息[4-5],且模体发现(motif discovery,MD)也是分类[6-7]、聚类[8-9]、异常检测[10-11]和规则发现[12-13]等处理时间序列算法的核心,因此MD对于理解、建模和预测隐藏在时间序列背后的系统具有基础性的作用。

目前针对时间序列MD的算法主要可以分为近似型算法和精确型算法2种。近似型算法的计算复杂度较低,是早些年的研究热点,其核心思想是将时间序列划分为一系列小的时间序列片段,并用符号或实数近似地表示这些时间序列片段,典型的算法主要有矩阵逼近的基元枚举(enumeration of motifs through matrix approximation,EMMA)[14]、主题跟踪算法(motif tracking algorithm,MTA)[15]和节省空间算法(space saving algorithm,SS)[16]等。但是这类算法的缺陷在于需要确定大量的参数,且这些参数通常与被研究的时间序列相关。由于精确型算法的计算量非常大,一直以来被认为是不可实现的,直到文献[17]提出了MK算法。基于他们的工作,一些改进算法被陆续提出,但是这些算法的一个共同缺点是需要指定模体的长度。为解决这个问题,文献[18]提出了可以发现不同长度模体的MOEN算法。但是,该算法仍然存在一些缺点有待改进:①运算时间比较长;②只适用于欧式距离;③只能针对确定的时间序列展开研究。……