摘 要

时间序列是由一系列实值构成的序列数据，具有数据特征多、数据量多、随着时间推移不断更新的特点。时间序列分类问题已经在时间序列挖掘领域引起了广泛的关注。

shapelet是时间序列中具有辨别性的子序列，通常嵌入在基于shapelet的决策树中。gRSF算法（广义随机森林算法）将shapelet与随机森林算法相结合，将生成的shapelet决策树进行集成来执行时间序列分类任务。该算法相比于目前的主流算法在预测精度和计算开销方面都有显著提高，但在阈值计算等方面仍有不足。RSCF算法（原始组合shapelets随机森林算法）在决策树内组合不同类别的shapelets形成一个节点，省略了分裂阈值的计算，同时也提出了一种更具有解释性的解释方法。本文对该算法的计算开销等方面进行优化，简化shapelet筛选策略，在每个节点计算一对shapelets的信息增益，通过对比信息增益值来决定是否剪枝。改进后的算法称为generalized Random Pairwise Shapelets Forest（gRPSF）算法。在实验验证阶段，本文挑选了六种目前的主流算法，包括ShapeletTree算法、FastShapelet（FS）算法、LearningShapelets（LTS）算法、广义随机森林算法（gRSF）、原始组合shapelets随机森林算法（RSCF）以及基于DTW的近邻法（DTW_1NN）。在准确率和时间两个方面进行比较，结果证实gRPSF算法分类精度与原始算法持平，但在一些大规模数据集上的计算开销与原算法相比显著减小。这表明gRPSF算法可以运用在对时间要求较高的序列分类问题上。

关键字：时间序列；分类；shapelets；随机森林

Abstract

Time series is a series of real values, which has the characteristics of high dimension, large amount of data and continuous updating over time. In time series classification, the order of time series attributes is very important. Time series classification has attracted wide attention in the field of time series mining.

Shapelet is a discriminative subsequence of time series, which is usually embedded in the decision tree based on the shapelet. The gRSF algorithm combines shapelet with random forest and integrates the generated shapelet decision tree to perform the task of time series classification. Compared with other algorithms, this algorithm has significant improvement in prediction accuracy and computation cost, but still has some shortcomings in threshold calculation. The original combination shapelets random forest algorithm combines different types of shapelets in the decision tree to form a node, omits the calculation of the splitting threshold, and proposes a more explanatory interpretation method. In this thesis, the computational overhead of the algorithm is optimized by simplifying the shapelet screening strategy. The information gain of a pair of shapelets is calculated in each node, and the pruning is decided by comparing the information gain value. The improved algorithm is called generalized Random Pairwise Shapelets Forest(gRPSF) algorithm. In the experimental verification phase, this thesis selected six current mainstream algorithms, including ShapeletTree algorithm, FastShapelet(FS) algorithm, LearningShapelets(LTS) algorithm, generalized Random Shapelets Forest algorithm(gRSF), original Random Shapelets Combination Forest(RSCF) and DTW-based nearest neighbor method(DTW_1NN). Compared with the original algorithm in terms of accuracy and time, the results show that the classification accuracy of gRPSF algorithm is the same as that of the original algorithm, but the computational cost of gRPSF algorithm on some large-scale datasets is significantly reduced compared with the original algorithm. This shows that gRPSF algorithm can be applied to sequence classification problems with high time requirements.

Key words: time series; classification; shapelets; random forest

目 录

第1章 绪论1

1.1研究背景与意义1

1.1.1时间序列分类研究背景1

1.1.2时间序列分类研究的现实意义2

1.2 gRPSF算法相关研究工作3

1.3本文研究的主要内容5

1.4论文结构6

第2章 广义成对shapelets随机森林算法研究7

2.1背景知识7

2.1.1符号与定义7

2.1.2随机森林算法10

2.2 gRPSF算法前期设计10

2.2.1算法数据结构设计11

2.2.2算法设计要求12

2.3 gRPSF算法技术实施12

2.3.1 bootstrap框架12

2.3.2 shapelets组合13

2.3.3 shapelets剪枝14

2.4 gRPSF算法描述15

2.5 DMDI解释方法18

2.6小结19

第3章 实验与评估20

3.1实验数据集20

3.2算法参数的影响21

3.2.1集成分类器个数p的影响21

3.2.2 shapelet长度边界的影响22

3.3准确率对比23

3.4时间对比26

3.5实际应用效果评估27

3.5.1 ECGFiveDays数据集上的实际应用效果分析27

3.5.2 ArrowHead数据集上的实际应用效果分析31

3.6小结32

第4章 总结与展望33

4.1研究工作总结33

4.2未来工作展望33

参考文献34

致 谢36

第1章 绪论

1.1研究背景与意义

1.1.1时间序列分类研究背景

机器学习通常分为监督学习，无监督学习，强化学习等三种情况。其中，分类问题是监督学习的核心问题之一。在监督学习范畴中，当输出变量的取值为有限个离散值时，预测问题则属于分类问题^[1,2]。其中，时间序列的分类问题又是分类问题中较为复杂的问题之一。

一条时间序列是一组实数序列数据，可以通过在间隔相等的时间段内反复取样而得到，取样结果随时间的变化而变化，从而获得对象的特征或随时间演变的情况。时间序列可以是单变量的，也可以是多变量的。时间序列数据广泛地存在于我们的日常生活中，涉及多个领域，比如图像轮廓分类，心电图分类，谱分类，动作检测等。