基于AUC的时间序列Shapelets提取方法

摘  要：近年来，基于Shapelets的时间序列分类方法受到了广泛关注。现有的基于Shapelets转换的时间序列分类方法使用信息增益作为评价Shapelets的标准，并主要关注分类准确率，不能很好地适应不平衡时间序列分类。为了解决上述问题，使用AUC作为提取Shapelets的标准，并用于后续的数据集转换和分类，最后使用不平衡评价指标F-measure和AUC值对分类结果进行评价。结果显示，该方法能够很好地适应不平衡时间序列分类。

关键词：时间序列分类；Shapelets；不平衡数据分类；AUC

中图分类号：TP311    文献标识码：A    文章编号：2096-4706（2023）03-0083-04

AUC-based Time Series Shapelets Extraction Method

SUN Qifa

（Xuzhou Finance and Economics Branch of Jiangsu Union Technical Institute， Xuzhou  221008， China）

Abstract： In recent years， Shapelets-based time series classification methods have received extensive attention. Existing time series classification methods based on Shapelets transformation use information gain as a criterion for evaluating Shapelets， and mainly focus on classification accuracy， which cannot be well adapted to imbalanced time series classification. In order to solve the above problems， AUC （Area Under the Curve） is used as the criterion for extracting Shapelets and used for subsequent data set transformation and classification. Finally， the classification results are evaluated using the imbalanced evaluation index F-measure and AUC value. The results show that the method can adapt well to imbalanced time series classification.

Keywords： time series classification; Shapelets; imbalanced data classification; AUC

0  引  言

時间序列分类[1]问题已经引起了数据挖掘团体极大的兴趣，是时间序列数据挖掘领域中的一个重要分支。由于时间序列数据的维度高、高度的特征关联性和高度的噪声数据[2]，使时间序列分析成为一个感兴趣的研究问题。几乎所有的应用领域都在以前所未有的速度产生时间序列数据，比如，股票市场每天的股价波动[3]，基于位置服务对象的位置更新数据[4]，传感器网络[5]各种各样的读数。时间序列数据的高维性、高噪声以及不平衡性给时间序列数据的分类造成了极大的阻碍[6]。

目前，基于时间序列Shapelets[7]以及Shapelets转换[8]的分类方法主要使用信息增益来评价Shapelets，并主要关注时间序列Shapelets的提取[9]和筛选[10]。对于数据集的分类结果，多数人还是以数据集的整体分类准确率[11]来衡量分类效果。而对于不平衡数据集来说，尽管分类准确率非常高，这在实际应用中却不是想要的结果。因此，找到有效的时间序列Shapelets提取方法对于不平衡数据的分类，特别是高维不平衡数据分类，有着重要的意义。

1  基于AUC的时间序列Shapelets提取方法

在现有的研究工作中，大多数研究者采用了信息增益作为评价候选Shapelets的标准，并取得了不错的分类准确率[11]。针对不平衡时间序列数据集，本文采用曲线下面积（Area Under the Curve， AUC）来对不同的Shapelets进行评估和提取，使得基于Shapelets的时间序列分类方法更适应不平衡数据集分类。为方便描述，本文将算法命名为DivAUCShapelet。算法伪代码如下：

算法DivAUCShapelet （T， min， max）

输入：训练集T，最小长度min，最大长度max

输出：所有的候选shapelets

（1）allShapelets =?

（2）for all time series Ti in T

（3）    shapelets=?

（4）    for  l=min to max do

（5）        Wi，l=generateCandidates（Ti， min， max）

（6）        for all subsequence S in Wi，l

（7）            for m=0 to |T|

（8）Ds=calcDistance（S，Tm）

（9）            end for

（10）            sort（Ds）

（11）AUCvalue=0

（12）for i=0 to | Ds |

（13）                    for j=0 to i

（14）Tn=Ds[ j].ts

（15）                        if Tn. label=positive

（16）tp=tp+1

（17）                        else

（18）fp=fp+1

（19）                    end for

（20）tpr[i]=tp/#positive

（21）fpr[i]=fp/#negtive

（22）end for

（23）            AUCvalue=calcAUC（tpr， fpr）

（24）allShapelets.add（shapelets， AUCvalue）

（25）        end for

（26）    end for

（27）end for

（28）return allShapelets

算法DivAUCShapelet的第一行是对所有候选shapelets的初始化；第2～5行是对训练集中的所有时间序列，生成长度最小为min，最大为max的候选shapelets，第5行的generateCandidates（）函数使用了SAX技术对时间序列进行降维；第6～10行是对所有的候选shapelets计算它们与训练集中每一条时间序列之间的距离，然后从小到大排序；第12～22行表示，依次增大阈值，计算阈值下的TPR和FPR值，计算方法如下：使用距离作为阈值，由于Ds中的距离已经排好序，依次选取Ds中的距离作为阈值，小于或等于此阈值的时间序列均被预测为正类，其余的被预测为负类，第14行的Tn表示距离向量Ds第j个位置所对应的时间序列，如果Tn实际的类标号为正类，那么TP的个数加1，否则FP的个数加1，这样就可以计算出TP和FP的个数，进而得出TPR和FPR值；第23和24行是根据之前计算的多个TPR和FPR值计算每个候选shapelets的AUC值，并把带有AUC值的shapelets放入allShapelets中；最后返回所有的shapeletsallShapelets。

以上为时间序列shapelets的提取过程，接下来，采用和文献[12]相同的方法，构造多样化图并进行查询选取出最优的k个多样化shapelets。最后，利用选出的k个shapelets将原始的数据集转换并进行分类。

2  实验结果及分析

2.1  数据集

实验数据选用了来自UCR[13]的ECG200、Wafer、Fish和Adiac共四个数据集，数据集中所有的数据均为实数类型。

表1给出了本次实验使用的数据集的相关信息，包括数据集名称、数据集中每条时间序列的长度、类别个数、用作少数类的个数、训练集和测试集中的样本数以及不平衡比率IR。

从表1可知，ECG200和Wafer数据集只包含2类数据，多数类和少数类的IR值均大于2，可以视为不平衡的数据集。在Fish和Adiac数据集中，分别包含7类和37类数据，并且多数类和少数类样本之间的IR值分别在5.3和7.3、25和96.5之間。对于包含多个类的数据集，可以把其中一个样本数小于1/3的类视为少数类，同时将所有其他类的样本视为多数类，以此类推。以Fish数据集为例，该数据集共包含7类样本，每个类的样本数均在21～28之间。因此，可以将这7类样本均分别视为少数类，剩下的其他样本视为多数类，并进行分类操作，最终对所有7类样本分别进行分类后的结果求平均值。这样，就可以把包含多类的数据集分类问题转换为二分类问题。

为了验证算法的有效性，将DivTopKShapelet方法和DivAUCShapelet方法分别作为时间序列shapelets的提取方法，并利用提取结果分别与C4.5、1NN、Naive Bayes、Bayesian Network、Random Forest和Rotation Forest六种分类算法进行结合，并使用以上数据集运行10遍，最后对结果求平均值。下面将从分类的准确率、分类结果的AUC值以及F-measure值三个维度进行分析。

2.2  F-measure值分析

F-measure值是Precision和Recall的加权调和平均，综合考虑了准确率和召回率，能够衡量不平衡数据集的分类效果，值越接近1表示分类效果越好。表2为DivTopKShapelet和DivAUCShapelet方法与六种分类器结合使用后的F-measure值，加粗数据为两种方法对同一个数据集分类得到的最高F-measure值。由表中可知，相比DivTopKShapelet方法，DivAUCShapelet方法在与六种分类器结合使用后，对四个数据集分类的F-measure平均值分别提高了0.10、0.17、0.04和0.02，并使用Naive Bayes分类器在ECG200数据集和Wafer数据集、使用Random Forest分类器Adiac数据集上取得了最好的结果。因此，DivAUCShapelet方法在对不平衡数据集进行分类时相比DivTopKShapelet拥有更好的结果。

2.3  AUC值分析

表3给出了DivTopKShapelet和DivAUCShapelet方法与六种分类器结合使用后的AUC值，加粗数据为两种方法对同一个数据集分类得到的最高AUC值。相比DivTopKShapelet方法，DivAUCShapelet方法在与六种分类器结合使用后，对四个数据集分类的AUC平均值分别提高了0.06、0.16、0.06和0.04，并使用Naive Bayes分类器在ECG200数据集和Wafer数据集、使用Rotation Forest分类器在Fish数据集、使用Bayesian Network分类器在Adiac数据集上取得了最好的结果。因此，DivAUCShapelet方法在对不平衡数据集进行分类时相比DivTopKShapelet拥有更好的结果。

3  结  论

针对基于时间序列shapelets转换的算法不能很好地使用不平衡数据集的分类问题，本文使用AUC作为衡量shapelets好坏的标准，提出了一种基于多样化top-k shapelets的不平衡数据集分类方法，并从分类结果的准确率、AUC值以及F-measure值三个方面进行分析。实验表明，该方法在不平衡数据集上分类时在多数情况下均优于原本的DivTopkShapelet方法，具有较大的实际应用价值。

参考文献：

[1] FAOUZI J. Time Series Classification：A review of Algorithms and Implementations [J/OL].Machine Learning（Emerging Trends and Applications），2022：1-34[2022-09-21].https：//hal.inria.fr/hal-03558165/document.

[2] 杨海民，潘志松，白玮.时间序列预测方法综述 [J].计算机科学，2019，46（1）：21-28.

[3] 刘恒，侯越.贝叶斯神经网络在股票时间序列预测中的应用 [J].计算机工程与应用，2019，55（12）：225-229+244.

[4] 潘晓，马昂，郭景峰，等.基于时间序列的轨迹数据相似性度量方法研究及应用综述 [J].燕山大学学报，2019，43（6）：531-545.

[5] 付国庆.传感器网络时间序列数据计算及可视化研究 [D].大连：大连理工大学，2019.

[6] 杨梦晨，陈旭栋，蔡鹏，等.早期时间序列分类方法研究综述 [J].华东师范大学学报：自然科学版，2021（5）：115-133.

[7] GRABOCKA J，SCHILLING N，WISTUBA M，et al. Learning time-series shapelets [C]//Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining.New York：Association for Computing Machinery，2014：392-401.

[8] HILLS J，LINES J，BARANAUSKAS E，et al. Classification of time series by shapelet transformation [J].Data Mining and Knowledge Discovery，2014，28（4）：851-881.

[9] 金海波.一种时间序列shapelets快速发现算法 [J].太原科技大学学报，2019，40（3）：229-235.

[10] YAN W H，LI G L，Wu Z D，et al. Extracting diverse-shapelets for early classification on time series [J].World Wide Web，2020，23（6）：3055-3081.

[11] 閆汶和，李桂玲.基于shapelet的时间序列分类研究 [J].计算机科学，2019，46（1）：29-35.

[12] 孙其法，闫秋艳，闫欣鸣.基于多样化top-k shapelets转换的时间序列分类方法 [J].计算机应用，2017，37（2）：335-340.

[13] Hexagon．The UCR Time Series Classification Archive [EB/OL].[2022-08-25].https：//www.cs.ucr.edu/～eamonn/time_series_data_2018．

作者简介：孙其法（1991—），男，汉族，山东枣庄人，初级职称，硕士研究生，研究方向：数据挖掘、计算机网络。

收稿日期：2022-10-20