时间序列的分割及不一致发现研究

摘要

时间序列是随着时间次序而变化的系列数据。时间序列的分割和不一致发现在许多领域非常重要,如金融数据的分割、太空遥感和医学等数据的不一致发现、网络监控、移动对象轨迹流的跟踪和异常检测等。针对时间序列的分割和不一致发现方面存在的不足,开展了以下研究工作:基于符号化表示的时间序列分割、基于符号化表示的时间序列相似性度量、基于预测的时间序列分割、基于比特表示的静态时间序列不一致发现、基于分形的时间序列流异常检测。
　　针对基于符号化表示的已有分割方法只反映子段均值信息却丢失趋势信息的现状,提出基于趋势的符号化表示(Trend-based Symbolic approXimation,TSX)的分割方法。在对时间序列降维获得子段均值信息的同时,提炼出时间序列子段的重要趋势特征,并设计多辨析率的角度分裂区间查找表,将趋势特征离散化为符号,进而获得既提取均值信息又反映趋势信息的时间序列的符号化降维表示TSX。实验结果表明,在相似搜索中,基于TSX的分割较基于符号聚集近似法(Symbolic Aggregate approXimation,SAX)表示的分割可以更有效地支持相似搜索,错报率较低。
　　由于基于符号化表示的时间序列分割的度量MINIDIST_PAA_iSAX不具有对称性,提出了基于SAX的相似性度量方法Sym_PAA_SAX。Sym_PAA_SAX考虑了待衡量的两条时间序列在距离计算中的地位对等性,使该度量方法不仅具有对称性,而且满足下界定理。实验显示,Sym_PAA_SAX的下界紧密性较好,错报率降低。
　　为适应时间序列流数据在线、快速、数据量大、无法全部保存的重要特征,提出基于指数平滑预测的时间序列流的分割算法(Exponential Smoothing Prediction based Segmentation algorithm for time series stream,ESPS)。运用经典的指数平滑法提前计算未来时刻的平滑值并作为其预测值;提出预测误差判定定理,保证预测误差的正态分布,并进一步推导出预测误差与压缩率之间的关系,为判定数据点是否为分割关键点确立了依据;基于基本滑动窗口模型,设计了ESPS算法。为弥补大多数已有的分割方法仅仅以分割后的总驻留误差作为衡量标准的缺陷,实验中采用标准分段数、标准总误差、标准总性能、计算时间等作为评估的指标。实验结果显示,相对于滑动窗口算法和滑动窗口自底向上算法,ESPS算法效果较好、效率较高。
　　为解决不一致发现中算法复杂度高、计算量较大的问题,提出了基于比特表示聚类的静态时间序列不一致发现算法。首先,对给定原始时间序列采用基于PAA方式比特序列化的方法进行分割,该方法不仅提取了原始序列的主要趋势特征,而且能够避免噪声的影响;然后,基于比特表示并利用聚类可以加速的思想,提出了变形的k中心点聚类算法,将具有相似变化模式的子序列归为一类;基于该聚类算法提出了不一致发现的算法,算法中采取了启发式剪枝和根据簇中心距离剪枝两种剪枝策略。实验结果说明,基于比特表示聚类的不一致发现算法有效性较好,效率较高,且具有扩展性。
　　时间序列的不一致发现可以应用于异常检测。为改进已有时间序列流的异常检测的效果,提出了基于分形的时间序列流异常检测算法。由于关联分形维数的改变可以用作数据集中数据趋势改变的指示器,因此,采用含有基本窗口的滑动窗口模型,利用关联分形维数捕获滑动窗口中当前可见数据的模式特征,设计了基于分形的异常检测算法。与基于TSA-tree的方法、基于免疫的方法的对比实验显示,基于分形的异常检测方法可以有效地发现异常。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪论

1.1 研究背景、目的及意义

1.2 国内外研究概况

1.3 本文的主要工作及组织结构

2 基于符号化表示的时间序列分割

2.1 引言

2.2 符号聚集近似

2.3 基于趋势的符号化表示的分割

2.4 基于符号化的度量

2.5 本章小结

3 基于平滑指数预测的时间序列分割

3.1 引言

3.2 指数平滑预测模型

3.3 基于预测的分割算法

3.4 实验评估

3.5 本章小结

4 基于比特表示的静态时间序列不一致发现

4.1 引言

4.2 不一致发现相关定义和方法分类

4.3 基于比特表示的时间序列分割

4.4 基于比特表示的时间序列聚类

4.5 基于聚类的不一致发现

4.6 实验评估

4.7 本章小结

5 基于分形的时间序列流异常检测

5.1 引言

5.2 异常检测方法分类

5.3 分形数学基础

5.4 两种典型的分形方法

5.5 基于分形的异常检测算法

5.6 实验评估

5.7 本章小结

6 全文总结和研究展望

6.1 全文总结

6.2 研究展望

致谢

参考文献

附录 攻读博士学位期间发表论文目录