本文是一篇计算机应用论文，本文针对基于 shapelet 的 TSC 算法进行研究和改进，主要改进包括相似性度量方法、shapelet 提取算法和 shapelet 转换数据的算法，并通过对现实交通领域中的数据集进行实验验证基于 shapelet 的时间序列分类算法的应用研究，本文的三四章分别介绍了两个基于 shapelet 的时间序列分类算法改进方法的详细描述和实验对比结果，第五章使用基于 shapelet 的时间序列分类算法对交通领域中是否发生交通事故进行判断。
第一章 绪论
1.1 研究背景和意义
时间序列数据是随时间变化生成的一系列连续实值，数据的产生方式一般是通过在相同的时间间隔内，使用特定的采样方法，对某些活动的观测结果，获取到的数据通常在逻辑上或者是时间上存在前后关系。在人们的日常生活中，金融、医疗、交通、天气等多个领域都会产生大量的时间序列数据，如何有效的对这些数据加以利用，促成时间序列分类（Time Series Classification,TSC）这一研究热点。TSC 可以把未标记过的时间序列数据通过特定分类算法划分到已知的不同类别中。比如在医疗领域中，患者心率（如图 1. 1）就是典型的时间序列数据，通过监控患者心跳从而对当前时间序列进行分类，以此来帮助医生进行诊断；在天气领域中的气候预测、交通领域中的堵塞判断、金融领域中的股市分析等等都可以视为 TSC 问题。时间序列分类还可以把逻辑上存在顺序的实值数据结合到 TSC 问题中。
图 1.1 患者心率时间序列
时间序列数据的特点是数据量大、数据维度高以及随时间或逻辑变化更新，因此当使用决策树、朴素贝叶斯、支持向量机等普通数据分类算法对时间序列数据进行分类或应用时，很难有效对数据进行分析并加以利用[1]。TSC 是数据挖掘领域中的重要研究内容，目的是通过对时间序列数据的训练集进行处理得到能够区分数据类别的分类特征，再使用这些分类特征来生成分类器，从而将时间序列数据有效地划分到相应的数据类别中。时间序列数据的实值也称为属性，不同于普通数据分类算法的是，TSC算法强调属性间的顺序，数据中的属性顺序如果不同，生成的分类特征提取结果也就不同，从而影响最终的分类结果。
..................................
1.2 国内外研究现状
TSC 算法需要在构造分类器之前或分类期间对时间序列数据进行处理或筛选，如今已经有许多分类算法可以应用到 TSC 领域中。根据分类算法找到分类特征的不同方式来对这些 TSC 算法进行划分，从而了解不同分类算法之间的相似性和差异，主要可以将其分为以下六类。
1.基于整条序列的时间序列分类算法。此类算法需要将时间序列转换为向量来进行相似性比较，或者是通过距离度量方法计算出时间序列间的距离值，使用距离值作为时间序列之间差异的表现，目前此类算法的研究重点是使用更有效的距离度量方法来计算时间序列之间的最小差异。
2.基于区间的时间序列分类算法。此类算法通过提取一个或多个时间序列上的区间（取决于相位），而不是整条时间序列用于进行数据分类，可以理解为对时间序列上连续子集的选择。
3.1 shapelet 的提取算法大致可以分为两类，第一类算法是从 shapelet 候选集中提取出区分度较高的 shapelet；第二类是通过优化目标函数学习 shapelet。
4.基于词典的时间序列分类算法。此类算法对时间序列数据进行分类时，先将时间序列转换为代表词，在分类的过程中，通常会对代表词在数据中出现的频率进行数学统计，然后根据这个统计出来的出现频率绘制直方图从而构建分类器。
5.基于模型的时间序列分类算法。这类算法选择能够拟合到每条时间序列的模型，再通过计算模型之间相似性以此来代表时间序列之间的相似性，主要使用的模型包括拟合自回归模型[33]、隐马尔科夫模型[34]和核模型[35]等，基于模型的时间序列分类算法适合用于长度不等的长时间序列数据的处理和分类。
6.基于组合算法的时间序列分类算法。通过将上述两种或多种时间序列分类算法组合到一起生成一个组合分类器，然后对时间序列数据进行分类。Kate 等人[36]提出一种特征生成算法，该算法将 DTW 和 SAX 相结合，以此来提升分类速度，减少实验的时间消耗；Bagnall 等人[37]提出转换集合算法，该算法将 shapelet 和距离测量方法相结合，大幅提升分类速度。
.............................
第二章 相关基础理论
2.1 时间序列表示方法
时间序列表示方法通过从时间序列上提取区分特征，并保证这个区分特征能够代表对应时间序列的信息和形态，以此来忽略时间序列中对分类没有帮助的多余部分，从而将高维时间序列数据转换成低维时间序列数据。表示方法处理后应该能以更简洁的形式来代替时间序列上的区分特征，从而减少后续实验的计算量，为时间序列数据分类奠定基础。除此以外，时间序列的表示过程还需要考虑存储效率，噪声影响和运算速度等问题，所以表示方法需要满足以下五个要求：
1.表示结果要能够保证全局或局部的区分特征； 2.表示后能够降低时间序列数据的维度； 3.表示后的时间序列可以重构； 4.表示过程要尽量简单，不会影响整个实验的速度； 5.在表示过程中防止噪声对表示结果产生影响。
目前已经提出多种时间序列表示方法，为了方便进行对比分析，可以根据表示过程的不同对表示方法进行总结和分类，大致可以分为以下三类：非数据自适应方法、数据自适应方法和基于模型的方法。
2.1.1 非数据自适应方法
此类方法不需要考虑时间序列的属性，只需要设定统一参数来对时间序列进行转换即可，数据本身和转换过程或参数选择无关，表示后的结果可能没有数据自适应方法的表示结果准确，但此类方法实现相对简单，适用范围广，适合处理等长且参数一致的时间序列数据，如果实验对精度的要求不高且数据集中时间序列较长可以采用这个方法。
..........................
2.2 相似性度量方法
相似性度量方法是时间序列数据分类领域中一个重要组成部分，主要应用于数据的预处理阶段和分类阶段，目的是通过计算时间序列之间的距离来验证时间序列是否相似。如果在时间序列数据的分类、聚类或回归分析实验前使用相似性度量方法去除掉相似的时间序列，对提升实验效率能起到巨大帮助。目前用来计算时间序列相似性的方法有很多，包括曼哈顿距离、欧氏距离以及动态时间弯曲距离等。
在处理时间序列数据集时，可以根据其数据类型的不同构建不同的相似度计算模型。如果对完整时间序列进行比较，通常比较复杂而且计算成本较高，所以可以从时间序列中选取出具有较高区分度的子序列来进行对比，从而衡量时间序列之间的相似性。
在时间序列相似性判断的过程中，尽量满足下列四点要求：
1.不需要考虑时间序列形状的完全相等，只需要将距离值结果视为相似依据即可； 2.尽量从时间序列局部范围内提取区分度较高的子序列来进行相似度计算； 3.计算方法要具有通用性，可以做到对任何需要计算的数据进行相似性计算； 4.计算方法要有健壮性，当数据中存在噪声或失真时，保证计算结果不会受到影响。
结合上述四个要求，研究人员提出多种策略来改善相似性计算，从而提升计算效率和结果的准确率。目前主要的改进方式包括：对时间序列进行放大、将时间序列上的振幅转移、时间序列缩放、去除数据中的异常值、附加噪声等等。保证计算方法不仅具备健壮性，还要有良好的鲁棒性。
为了方便理解方法之间的差异，将相似性度量方法总结为四类：
（1）基于形状的相似性度量方法，此类方法进行相似性计算时，比较时间序列形状差异；
（2）基于编辑的相似性度量方法，此类方法在对比时间序列之间相似性时，需要先将时间序列转换成字符串，再通过对比字符串之间的差异来代替时间序列之间的差异，从而简化相似性计算；
（3）基于特征的相似性度量方法，这类方法需要从时间序列数据中提取出特征属性，然后通过这个属性作为区分特征来对时间序列之间的相似性进行验证；
（4）基于模型的相似性度量方法，此类方法通过选择与时间序列相匹配的模型，然后在全局层面进行相似性对比。
.................................
第三章 基于 LDTW-shapelet 的时间序列分类算法研究 ............................. 19
3.1 本章相关知识和定义 ............................... 21
3.2 基于 LSH-DTW 处理原始时间序列数据集 ............................ 22
第四章 基于单类 shapelet 转换的时间序列分类研究 ............................. 35
4.1 基于单类 shapelet 转换时间序列数据 ................................ 36
4.1.1 传统 shapelet 提取算法................................... 36
4.1.2 单类 shapelet 概念及提取算法.......................... 37
第五章 基于 shapelet 的时间序列分类算法应用研究 .............................. 45
5.1 构建分类模型 ....................................... 46
5
