论文部分内容阅读
时间序列模式匹配是时间序列挖掘研究中一个基础和重要的问题,它是聚类、分类、规则发现、异常检测和知识发现等其它挖掘任务的基本技术手段和处理方法。该课题的研究目前还处在积极发展的阶段,现有的研究成果已经显示出模式匹配具有广阔的应用前景。以目前时间序列的主体框架GEMINI框架为基础,开展时间序列模式匹配技术中的分类、子序列的定位、序列间距离的度量、距离度量的优化和适合于动态时间序列的匹配方法等的研究具有重要意义。按照匹配的形式可以将模式匹配问题分为子序列匹配和全序列匹配两类。子序列匹配是从长度更长的主序列中查找与给定的模式序列相同或相似子序列的过程,最重要的操作是子序列定位,解决该问题的关键是如何减少匹配次数。全序列匹配是从时间序列数据库中查找与给定的模式序列相同或相似序列的过程。全序列匹配一般转换为距离度量的问题,如何提高序列之间距离度量的准确度和效率是该问题的研究热点。通过对现有的经典子序列定位方法的深入分析,提出了基于重复度的贪心定位算法和基于相异度的贪心定位算法。贪心定位算法运用最优化原理计算模式序列的特征值,模式匹配按照特征值的大小从大到小进行,具有匹配效率高、适应性好、易于扩展和易于优化的优点。针对全序列匹配中采用的距离度量方法存在度量准确度低、效率低的问题,提出了基于形态拟合的距离度量算法。该算法将欧式距离和动态弯曲距离两种度量方法进行优势组合,尽力消除影响欧式距离和动态弯曲距离度量的不利因素,具有度量准确度高和效率高的优点。现有精确的动态弯曲距离存在计算性能瓶颈,在深入分析动态弯曲距离计算原理的基础上,提出了距离上界函数的概念,并给出了动态弯曲距离的距离上界函数的设计方法。如果函数的计算路径是一条动态弯曲路径,那么它就是一个动态弯曲距离的距离上界函数。为提高精确的动态弯曲距离的计算效率,提出了应用提前终止技术加速计算过程的新算法,该算法以动态弯曲距离的距离上界函数作为提前终止判定值,在计算累积距离矩阵的过程中,当累积距离大于动态弯曲距离的距离上界函数值时,对该计算路径进行终止标识,重新选取其它的计算路径进行计算。该算法确保了动态弯曲距离的度量准确度,同时有效地提高了计算效率。在深入分析动态序列、动态匹配和匹配算法特点的基础上,提出了模式序列的模式阈值的概念,设计和实现了适合于动态时间序列的基于模式阈值的定位算法,并对该算法进行了优化。以上述研究成果为基础,设计和实现了一个同时支持子序列匹配、全序列匹配和动态匹配的时间序列模式匹配原型系统TSPM(Time Series Pattern Matching),为评估各类匹配方法的实际效果提供了实验研究平台。