不平衡时间序列集成分类算法

，2*

（1.中国矿业大学计算机科学与技术学院，江苏徐州 221116；2.中国矿业大学灾害智能防控与应急救援创新研究中心，江苏徐州 221116）

0 引言

时间序列分类和不平衡数据分布是实际应用中普遍存在的问题。时间序列存在数据维度高、数据之间相关性强和噪声干扰多等特点，而不平衡数据学习则更加强调分类器对少数类样本的识别能力。一方面时间序列数据的特殊性使得不平衡学习领域的方法不能完全适用，时间序列的高维度、时间相关性和序列数据存在先后逻辑顺序的特点使不平衡问题在时间序列条件下变得更加复杂。例如序列数据中的少数类和噪声的判别会更加艰难，类重叠会更难以处理等；同时，现有的解决时间序列不平衡的方案以重采样为主，其中又是以生成少数类合成样本的过采样方法为重点，而时间序列较一般数据更难合成合适的人工样本，这导致合成的样本效果往往并不理想。

进一步，已有的解决时间序列不平衡的方案大多只适用于二分类问题，如果通过将多分类转换为二分类的问题分解方式，则会造成整体数据分布的变化，仍会影响最终的分类效果。综上所述，直至目前时间序列不平衡分类仍然是亟待解决的重要实际应用问题。集成学习方法在时间序列分类问题中取得了显著的精度优势，但是其对数据集分布的不均衡性不敏感。

基于变换的集合的层次投票集合（Hierarchical Vote Collective of Transformation-based Ensembles，HIVE-COTE）［1］是目前表现最为出色的时间序列集成分类框架，但其中的组件没有考虑数据集分布的不均衡问题，属于不平衡时间序列的弱分类器。由集成学习理论可以得知，组件算法中若是不存在强分类器会严重影响到集成算法的能力上限。其中，HIVE-COTE 针对shapelet 特征设计了算法组件ST-HESCA（Shapelet Transformation-Heterogeneous Ensembles of Standard Classification Algorithm），该算法由于存在子序列评价指标对不平衡数据不敏感问题，成为影响HIVE-COTE 集成框架的弱分类器组件。

本文首先提出了一个结合提升方法（Boosting）和基于K最近邻（K-NearestNeighbor，K-NN）的多类不平衡问题的合成少数过采样算法（K-NN-based Synthetic Minority Oversampling algorithm for Multiclass imbalance problems，SMOM）的改进集成分类算法SBST-HESCA（SMOM &Boosting into ST-HESCA algorithm），提高ST-HESCA 算法组件针对不平衡时序数据的分类准确率；同时结合SBST-HESCA 组件对HIVE-COTE 计算框架进行改进，提出IMHIVE-COTE（Imbalanced Hierarchical Vote Collective of Transformation-based Ensembles）集成算法，通过优化结果的集成策略，增强集成算法对少数类样本识别精度的倾斜力度。

1 相关算法介绍

本章对两个涉及到的基础算法进行介绍，方便理解后续本章提出算法的设计意义和动机。

1.1 SMOM 算法

SMOM 是一个基于K最近邻（K-NN）思想的综合少数类过采样算法，与典型基于K-NN的过采样算法不同，SMOM为每个近邻的方向分配一个选择权值；同时，对可能产生严重泛化的相邻方向赋予较小的选择权值，从而使SMOM形成了一种避免过度泛化的机制。

为了实现这一目的，SMOM算法在分配少数类K个方向上的权值之前，应用不平衡数据上的聚类方法对少数类样本进行划分，从少数类样本集中界定出了突出集群和困境集群：突出集群中由少数类占据主导地位，有明确的类边界；困境集群中则会包含很多其他类样本，难以界定类边界，这个区域的少数类会更需要在近邻的方向分配合适的选择权值。此外，聚类方法还起到了减少权值计算量的作用，因为突出集群中的少数类样本的近邻权值无需计算。

在文献［2］中，已经证明SMOM 算法的运行效率优于现有简单过采样方法，同时在G-means、曲线下面积（Area Under Curve，AUC）和召回率（Recall）等不平衡指标方面，SMOM在统计学上优于其他采样方法。在本文4.2 节的实验部分还可以证明该算法在不平衡时间序列方面有很好的适应能力，优于通用的SMOTE（Synthetic Minority Oversampling Technique）方法。

1.2 HESCA 和ST-HESCA算法

HESCA（HeterogeneousEnsemblesofStandard Classification Algorithm），最先在文献［3］出现，和传统的集成分类方法相比，该方法更注重基础分类器的多样性，为了达成这一目的，它采用了异构集成的构成模式，异构集成方法较原始集成方法泛化能力更强，是目前时间序列分类中整体分类效果最好的集成分类策略，下面对它的算法构成进行简单介绍。

HESCA 由八个分类器组成，其中：两个自身也是集成分类算法：分别是随机森林（500棵树）和旋转森林（50棵树）；其余6个为K近邻、朴素贝叶斯、C4.5 决策树、具有线性和多项式核函数的支持向量机和贝叶斯网络。这些选择囊括了基于概率、基于序列个体实例和基于树的分类器3类，确保了集成分类器整体的泛化能力。算法通过10折交叉验证获得其中每个组成算法的准确度估计值，作为后来预测测试集类别的加权指标。

在文献［4］中，Bagnall和Lines等进行了一个当前主流时间序列分类算法的对比实验，实验数据集采样UCR标准时间序列数据，在精度上取胜的分别是HIVE-COTE、FLAT-COTE［5］和shapelet变换算法，这其中的shapelet变换算法就是shapelet变换结合HESCA来实现的（ST-HESCA），这一方法同时也被运用于HIVE-COTE，FLAT-COTE之中作为shapelet分类模块的核心算法，即ST-HESCA算法，因为它有着目前shapelet分类方法中最高的平均精度［6］。为了保证shapelet 集合的完整性，在shapelet计算部分，ST-HESCA采用一对多（one vs all）编码方案简化了质量评估计算，在选取shapelet方面通过更频繁的早期放弃策略提高了执行速度，并提高了多类问题的准确性［7］。这使得该过程较蛮力shapelet计算相比有较大效率提升，但是整体效率还是偏低，不能用来处理大规模时间序列数据集。

2 结合Boosting 和SMOM 采样的ST-HESCA组件算法

已有的时间序列分类算法中，对子序列的评价标准大部分以信息增益为主。本节给出两种基于不平衡分类指标的子序列评价标准，分别是基于AUC 值和F（F-measure）值的评价指标（简称AF指标），以及基于AUCPR（Area Under Curve-Precision Recall）值和AUC值的评价指标（简称AR指标），两个指标均是在传统质量评价指标的基础上，引入不平衡率（Imbalance Rate，IR）来调和传统指标和不平衡数据指标之间的权重比例，满足“数据分布的IR值越大，不平衡数据指标作用越大”的条件，从而更加准确地评价分类结果，对不平衡分类的适用性更高，比常用指标对不平衡时序类别的代表能力更强。

2.1 指标定义

定义1AF 指标。多分类情况下计算AUC 值时，引入不平衡率作为权值，这里不平衡率指的是当前数据集中，多数类数量与少数类数量的比值，数量相差越悬殊，不平衡率越大。在不平衡率较小时，评价指标中根据IR值增加AUC值的比例，改进AF指标，如式（1）所示：

定义2AR 指标。评价指标AR 值的定义和AF 指标类似，引入不平衡率作为权值，如式（2）所示：

2.2 算法思路

传统基于Boosting 的集成模型的流程如图1，可以看出Boosting方法会迭代多次地训练一个分类器，通过不同分布的训练子集反复对分类模型进行训练达到增强模型泛化能力的目的，最终达成将弱分类器变为强分类器的效果［8］。在不平衡问题的解决思路中，利用重采样结合Boosting集成算法被证实是有效的［9］，可以根据分类结果迭代更新样本的权重，更准确地评估重采样样本的质量，平衡不均衡数据分布的同时，更有利于提升少数类样本的分类质量。

图1 Boosting 集成算法训练流程Fig.1 Training flowchart of Boosting-based ensemble algorithm

Boosting算法的弱可学习理论表明，有限的迭代次数将弱学习算法经过多次训练，可以组合为强学习算法［10］。在HIVECOTE 中，ST-HESCA 算法是一个对不平衡时间序列数据不敏感的弱学习算法组件［11］，本文的优化思路是：将SMOM 采样算法结合Boosting 算法思想在每轮迭代过程中对不平衡数据集进行重采样，在每轮ST-HESCA算法模型的训练过程中将不平衡分类指标G-means、AUC值、AUCPR 值作为分类模型的评价标准，并根据交叉验证预测结果更新当次训练所得ST-HESCA算法模型的样本权重，然后通过有限度的多次迭代过程实现对ST-HESCA算法模型的不平衡数据学习能力的反复训练提升，最后组合所有迭代过程所得到的分类模型构成一个完备训练的SBST-HESCA 集成分类算法模型，提高了SBST-HESCA 算法组件针对不平衡时序数据的分类准确率。

2.3 算法说明

SBST-HESCA 算法的实现流程如图2，算法训练测试数据为采用AR指标得到的shapelet进行转换后的数据集，采用AR指标是由于实验中AR 指标相对于AF 指标对shapelet 候选集质量的提升更加稳定。

图2 SBST-HESCA算法流程Fig.2 Flowchart of SBST-HESCA algorithm

迭代处理过程中，首先给每个训练样本初始化一个权重系数，其值为本轮迭代开始时所有少数类样本的权重均值，然后每一轮迭代利用SMOM 算法人工合成少数类样本，交给STHESCA 算法进行多次交叉预测，最后根据这些预测结果更新合成样本的权重，在本过程中HESCA算法更新权重的判断依据为通过交叉预测结果计算出的不平衡分类指标综合值，这个综合值由AUC、AUCPR 和G-means 值共同判定，而不是STHESCA算法所使用的分类精度。由该过程训练得到的分类器为对应迭代流程的基分类器，训练样本的决策权重在本轮迭代过程被更新后用于下一次迭代训练过程。相对于ST-HESCA，SBST-HESCA算法采用本文给出的AR指标对子序列质量进行评价，该指标比原算法中的“信息增益值”更能准确度量不平衡数据集中shapelets的质量。同时，引入Boosting结合重采样的思路，通过交叉验证预测结果更新样本权重，使数据集的重采样过程更有利于提升少数类样本的分类质量。

算法1 SBST-HESCA 迭代集成算法。

SBST-HESCA 算法在第1）～2）行对训练样本权值进行初始化，第4）行对训练样本进行SMOM 采样处理，第5）～7）行新建一个HESCA 算法模型，然后设定评价指标为AUC 值，AUCPR 和G-means 值，最后采样后的数据导入模型进行交叉验证，得到当次迭代后的集成分类模型。第8）～10）行对样本权值进行更新，更新依据为本次迭代训练获得的算法模型得到的交叉验证结果。最后在第11）行保存本次迭代获得的集成分类模型和样本权值，当次迭代结束。第13）～16）行组合所有迭代所得的集成模型和样本权值，依据不平衡分类指标构建SBST-HESCA 分类模型，最后对测试数据进行预测得到分类结果。

3 IMHIVE-COTE 集成分类算法

3.1 投票权重的调整

HIVE-COTE 算法的权值计算相对于其前身FLAT-COTE算法的权值计算有了一个很大的调整，FLAT-COTE 算法的权值计算是一个扁平（flat）的结构，即所有组件算法不受模块化限制，一同参与最后的集成分类决策［12］，存在的问题是：同类型数量多的算法往往占有投票的优势。HIVE-COTE 算法对组件算法的模块化和分层化解决了这一问题［13］。本节对HIVE-COTE 算法集成策略进行优化，重点在于对每个组件算法的投票权重进行优化，而对算法自身内容并不进行变动。

HIVE-COTE 算法在训练分类器的过程中，先由各模块对训练数据进行模块内部的集成分类器的训练，然后HIVECOTE以不同模块为单位进行训练数据的交叉分类训练，在这个过程中确定HIVE-COTE 算法赋予每个模块在分类模型中的投票权重。HIVE-COTE 算法的权值计算方法为式（3），集成学习算法中存在g个集成算法模块，对c个类的数据进行分类预测，集成算法给出这个类为i的可信度为所有模块算法对这个序列类标签为i的置信度与集成算法模块对应的决策权值乘积的和，除以当前集成算法所有的权值与预测置信度的乘积和，其中w权值的确定根据交叉训练获得的分类精度来估算。则权值w的计算公式（3）可以简写为w=f（accuracy）。

本文继续沿用式（3）的权值计算方法，但是在权值w的计算过程中，原算法是根据交叉训练过程中该集成模块得到的分类精度计算得到，本文算法则基于交叉训练结果的AUC 值、AUCPR值和G-means值（G）进行权值计算，将三者的算术平均值作为集成算法模块的权值判断依据，确定权值的方法如式（4）所示：

3.2 IMHIVE-COTE 算法的整体概述

在SBST-HESCA 算法对ST-HESCA 组件进行优化的基础上，针对HIVE-COTE 集成算法，提出不平衡时间序列的集成分类方法IMHIVE-COTE。该算法从以下三个方面对HIVECOTE进行了优化。

1）在shapelet 选择算法和时间序列森林（Time Series Forest，TSF）算法部分，原算法采用的是信息增益值对子序列质量进行评价［14］，IMHIVE-COTE 算法将采用提出的AR 指标进行替换。

2）将第2 章提出的SBST-HESCA 算法加入shapelet 模块，与原有的ST-HESCA算法组件进行竞争，这部分的算法决策权值由式（4）来决定，即不平衡集成算法参与异构集成的分类决策，改善现有组件算法对不平衡时间序列数据的学习能力。

3）由于HIVE-COTE 是平衡时间序列下的分类算法，组件算法的投票比重计算依据的是整体精度这准，IMHIVE-COTE算法则采用式（4）作为集成算法模块的权值判断依据，从整体上提升集成算法对不平衡时间序列数据集的分类精度。

4 实验结果与分析

实验采用了F 值、G/MG（G-means/MG）值、AUC 值、AUCPR值作为评价指标。

二元分类问题中真阳性率被称为召回率（Recall）它代表分类器正确识别出的少数类占所有少数类数量的比值，与其对应的精确率如式（5）所示：

其中：TP是被分类模型正确预测的正样本数，FP是被分类模型错误预测为正类的负样本数。精确率代表分类器正确识别出的多数类占所有多数类数量的比值。在不平衡分类的环境中，一般需要优先保证召回率足够高，其次是精确率。这两个数值调和起来就出现了F-measure值，其β系数通常取1，这个情况下它的表达式可以简写成式（6）：

F 值能相对较好地反映出不平衡数据分类结果的好坏。但是不平衡分类关注的重点在于召回率，比如同样的F 值下的两种分类结果中，不平衡分类效果上而言Recall 值更高的分类结果更应该得到较好的评价。此外G-means 值也是一个不平衡分类算法的通用评价指标，其公式为：

只有在召回率和精确率都比较大时才比较高，较F值更难达成，对不平衡分类算法在少数类样本上的学习能力要求更高。多分类对比指标MG值公式如下：

AUC值的确认方法如式（9）所示：

ranki表示第i条样本的序号，M、N分别是正样本数和负样本数。PR 曲线以召回率为x轴，精确率为y轴，在不同阈值下得到对应坐标点，进而完成曲线的绘制。其曲线下面积值即为AUCPR。AUCPR值由于其来源的横纵坐标都是正类样本的分类指标，以及在正负样本数量相差悬殊时会受到较大影响，被认为更适合于在不平衡程度更夸张的情况下考察不平衡分类算法的分类性能，而AUC 值能够不受数据的不平衡率给出整体上的分类效果评价。上述值越大，说明模型的性能越好。

4.1 实验说明

将2.1 节提出的AF 指标和AR 指标运用在DIMS（Dimensions）算法中，这里DIMS算法是在二分类数据上使用的Binary_DIMS算法和在多分类数据上使用的Multi_DIMS［15］算法的总称，实验中为了区分两个评价指标，应用了AF指标的算法称为AF_DIMS，应用了AR指标的算法称为AR_DIMS。本节对提出的两个算法：SBST-HESCA算法和IMHIVE-COTE算法进行分类效果验证。数据集为公共数据集UCR上的不平衡二分类和多分类时间序列数据集［16］。对比算法选取了时间序列分类算法HIVE-COTE、重采样算法Influential Neighbourhood for Over-Sampling（INOS）和时间序列不平衡分类算法SMOM 和AdakNN2+GIHS、shapelets方法AF_DIMS和AR_DIMS。

4.2 实验结果与分析

观察表1的实验数据，可以发现除和平衡分类关系较近的F值指标外，本文提出的有关算法在G/MG值、AUC值2个不平衡指标中获得了最大的指标领先数，其中G/MG 值IMHIVECOTE算法性能最好，其次是HIVE-COTE算法；在AUC值分类结果上，IMHIVE-COTE 算法领先，其次是SMOM 算法；针对F指标和AUCPR 指标，IMHIVE-COTE 算法效果不及AR_DIMS。总体来说，IMHIVE-COTE算法的优势体现在以下两个方面：

1）在不平衡指标值（G/MG，AUC，AUCPR）上，本文提出的IMHIVE-COTE 集成算法比HIVE-COTE 集成算法得到的评价值更好，证明IMHIVE-COTE更适用于不平衡分类问题。

2）在4 个评价指标中，本文提出的IMHIVE-COTE 集成算法比未采用AR 和AF 子序列评价指标的单一分类算法，评价值更好；在F 值和AUCPR 值上效果不及AR_DIMS，并与AF_DIMS 效果接近，说明两个子序列评价指标的改进对于shapelets 分类算法非常有效，但是由于HIVE-COTE 集成框架中还包括其他组件算法，没有针对不平衡数据进行改进，因此影响了IMHIVE-COTE 的整体性能。但上述两点也说明，IMHIVE-COTE 为集成学习方法针对不平衡数据分类问题，提出了一个有效的优化思路。

表1 不同分类算法的F值、G/MG值、AUC值、AUCPR值Tab.1 F values，G/MG values，AUC values and AUCPR values of different classification algorithms

总结实验结果，可以得出如下结论：

1）本文提出的两个子序列质量评价指标AF 值和AR 值，在不平衡时间序列数据集中，对于SBST-HESCA 组件中shapelets的选择起到了重要作用。

2）改进算法SBST-HESCA 在不平衡数据的分类上有了更好的分类效果，显著增强了IMHIVE-COTE 集成算法的对不平衡时间序列数据的泛化能力。

3）相较于表1中基于平衡分类的评价指标F值，在不平衡指标值中，IMHIVE-COTE 算法得到的评价值更好，证明IMHIVE-COTE更适应于不平衡时间序列数据分类。

5 结语

本文给出了一个新的不平衡时间序列分类方法SBSTHESCA，分析并验证了该算法在不平衡分类方面的能力，然后总结本文实验成果之后，给出了一个完善的不平衡时间序列上的异构集成分类算法IMHIVE-COTE。最后经过实验验证，表明了IMHIVE-COTE算法能很好地总结时间序列的不平衡分类特点，保持异构集成方法在不平衡时间序列数据上的分类优势。