朱 旭，朱晓晓，王继民

(河海大学计算机与信息学院,江苏 南京 211100)

0 引 言

作为模式发现和相似性搜索的交叉主题，模体挖掘最先由加利福尼亚大学河滨分校的Lin和Keogh等[1]在2002年首次提出，称这样的模式为“模体”。在相关文献中，模体被定义为重复模式、频繁出现的趋势或近似和重复的序列、形状、片段、子序列等。模体挖掘也可为分类的核心[2]、群集[3-4]、异常检测[5-6]及规则发现[7-8]算法。时间序列模体挖掘技术在遗传学、金融、工业等诸多领域也得到应用。例如，金融领域的证券交易数据[9]、工业领域的用电数据[10]等。

定长模体挖掘仅挖掘由用户指定长度的模体。目前对于定长模体挖掘研究较多。文献[1]提出的Brute-Force算法是第一个模体挖掘算法，算法采取枚举的方式计算所有子序列之间的距离，然后利用最近邻算法找到模体，它具有完全的覆盖率和准确率，被广泛用作基准算法以衡量其他算法的准确性。Chiu等[11]结合SAX算法与概率思想提出了Random Projection算法。Mueen等[12]提出了MK算法，使用早弃技术对Brute-Force算法进行改进，并提出通过选择参考序列得到更紧密的下界距离，从而提高算法效率。Yeh等[13]引入STAMP算法，使用快速相似性搜索算法[14]挖掘时间序列模体。Zhu等[15]对STAMP算法进行改进提出了STOMP算法，其计算速度更快，通过快速傅里叶变换实现子序列间的点积来计算子序列之间的距离，通过重用前一个相邻子序列的点积来加速当前子序列点积的计算。相较于STAMP的随机顺序计算，STOMP是一种有序搜索。

变长模体挖掘无需用户预先指定模体长度，相比时间序列定长模体挖掘更难以解决，针对此问题的研究也相对较少。……