基于AUC的時(shí)間序列Shapelets提取方法

摘? 要：近年來，基于Shapelets的時(shí)間序列分類方法受到了廣泛關(guān)注。現(xiàn)有的基于Shapelets轉(zhuǎn)換的時(shí)間序列分類方法使用信息增益作為評(píng)價(jià)Shapelets的標(biāo)準(zhǔn)，并主要關(guān)注分類準(zhǔn)確率，不能很好地適應(yīng)不平衡時(shí)間序列分類。為了解決上述問題，使用AUC作為提取Shapelets的標(biāo)準(zhǔn)，并用于后續(xù)的數(shù)據(jù)集轉(zhuǎn)換和分類，最后使用不平衡評(píng)價(jià)指標(biāo)F-measure和AUC值對(duì)分類結(jié)果進(jìn)行評(píng)價(jià)。結(jié)果顯示，該方法能夠很好地適應(yīng)不平衡時(shí)間序列分類。

關(guān)鍵詞：時(shí)間序列分類；Shapelets；不平衡數(shù)據(jù)分類；AUC

中圖分類號(hào)：TP311? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? 文章編號(hào)：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? 引? 言

時(shí)間序列分類[1]問題已經(jīng)引起了數(shù)據(jù)挖掘團(tuán)體極大的興趣，是時(shí)間序列數(shù)據(jù)挖掘領(lǐng)域中的一個(gè)重要分支。由于時(shí)間序列數(shù)據(jù)的維度高、高度的特征關(guān)聯(lián)性和高度的噪聲數(shù)據(jù)[2]，使時(shí)間序列分析成為一個(gè)感興趣的研究問題。幾乎所有的應(yīng)用領(lǐng)域都在以前所未有的速度產(chǎn)生時(shí)間序列數(shù)據(jù)，比如，股票市場(chǎng)每天的股價(jià)波動(dòng)[3]，基于位置服務(wù)對(duì)象的位置更新數(shù)據(jù)[4]，傳感器網(wǎng)絡(luò)[5]各種各樣的讀數(shù)。時(shí)間序列數(shù)據(jù)的高維性、高噪聲以及不平衡性給時(shí)間序列數(shù)據(jù)的分類造成了極大的阻礙[6]。

目前，基于時(shí)間序列Shapelets[7]以及Shapelets轉(zhuǎn)換[8]的分類方法主要使用信息增益來評(píng)價(jià)Shapelets，并主要關(guān)注時(shí)間序列Shapelets的提取[9]和篩選[10]。對(duì)于數(shù)據(jù)集的分類結(jié)果，多數(shù)人還是以數(shù)據(jù)集的整體分類準(zhǔn)確率[11]來衡量分類效果。而對(duì)于不平衡數(shù)據(jù)集來說，盡管分類準(zhǔn)確率非常高，這在實(shí)際應(yīng)用中卻不是想要的結(jié)果。因此，找到有效的時(shí)間序列Shapelets提取方法對(duì)于不平衡數(shù)據(jù)的分類，特別是高維不平衡數(shù)據(jù)分類，有著重要的意義。

1? 基于AUC的時(shí)間序列Shapelets提取方法

在現(xiàn)有的研究工作中，大多數(shù)研究者采用了信息增益作為評(píng)價(jià)候選Shapelets的標(biāo)準(zhǔn)，并取得了不錯(cuò)的分類準(zhǔn)確率[11]。針對(duì)不平衡時(shí)間序列數(shù)據(jù)集，本文采用曲線下面積（Area Under the Curve， AUC）來對(duì)不同的Shapelets進(jìn)行評(píng)估和提取，使得基于Shapelets的時(shí)間序列分類方法更適應(yīng)不平衡數(shù)據(jù)集分類。為方便描述，本文將算法命名為DivAUCShapelet。算法偽代碼如下：

算法DivAUCShapelet （T， min， max）

輸入：訓(xùn)練集T，最小長(zhǎng)度min，最大長(zhǎng)度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的第一行是對(duì)所有候選shapelets的初始化；第2～5行是對(duì)訓(xùn)練集中的所有時(shí)間序列，生成長(zhǎng)度最小為min，最大為max的候選shapelets，第5行的generateCandidates（）函數(shù)使用了SAX技術(shù)對(duì)時(shí)間序列進(jìn)行降維；第6～10行是對(duì)所有的候選shapelets計(jì)算它們與訓(xùn)練集中每一條時(shí)間序列之間的距離，然后從小到大排序；第12～22行表示，依次增大閾值，計(jì)算閾值下的TPR和FPR值，計(jì)算方法如下：使用距離作為閾值，由于Ds中的距離已經(jīng)排好序，依次選取Ds中的距離作為閾值，小于或等于此閾值的時(shí)間序列均被預(yù)測(cè)為正類，其余的被預(yù)測(cè)為負(fù)類，第14行的Tn表示距離向量Ds第j個(gè)位置所對(duì)應(yīng)的時(shí)間序列，如果Tn實(shí)際的類標(biāo)號(hào)為正類，那么TP的個(gè)數(shù)加1，否則FP的個(gè)數(shù)加1，這樣就可以計(jì)算出TP和FP的個(gè)數(shù)，進(jìn)而得出TPR和FPR值；第23和24行是根據(jù)之前計(jì)算的多個(gè)TPR和FPR值計(jì)算每個(gè)候選shapelets的AUC值，并把帶有AUC值的shapelets放入allShapelets中；最后返回所有的shapeletsallShapelets。

以上為時(shí)間序列shapelets的提取過程，接下來，采用和文獻(xiàn)[12]相同的方法，構(gòu)造多樣化圖并進(jìn)行查詢選取出最優(yōu)的k個(gè)多樣化shapelets。最后，利用選出的k個(gè)shapelets將原始的數(shù)據(jù)集轉(zhuǎn)換并進(jìn)行分類。

2? 實(shí)驗(yàn)結(jié)果及分析

2.1? 數(shù)據(jù)集

實(shí)驗(yàn)數(shù)據(jù)選用了來自UCR[13]的ECG200、Wafer、Fish和Adiac共四個(gè)數(shù)據(jù)集，數(shù)據(jù)集中所有的數(shù)據(jù)均為實(shí)數(shù)類型。

表1給出了本次實(shí)驗(yàn)使用的數(shù)據(jù)集的相關(guān)信息，包括數(shù)據(jù)集名稱、數(shù)據(jù)集中每條時(shí)間序列的長(zhǎng)度、類別個(gè)數(shù)、用作少數(shù)類的個(gè)數(shù)、訓(xùn)練集和測(cè)試集中的樣本數(shù)以及不平衡比率IR。

從表1可知，ECG200和Wafer數(shù)據(jù)集只包含2類數(shù)據(jù)，多數(shù)類和少數(shù)類的IR值均大于2，可以視為不平衡的數(shù)據(jù)集。在Fish和Adiac數(shù)據(jù)集中，分別包含7類和37類數(shù)據(jù)，并且多數(shù)類和少數(shù)類樣本之間的IR值分別在5.3和7.3、25和96.5之間。對(duì)于包含多個(gè)類的數(shù)據(jù)集，可以把其中一個(gè)樣本數(shù)小于1/3的類視為少數(shù)類，同時(shí)將所有其他類的樣本視為多數(shù)類，以此類推。以Fish數(shù)據(jù)集為例，該數(shù)據(jù)集共包含7類樣本，每個(gè)類的樣本數(shù)均在21～28之間。因此，可以將這7類樣本均分別視為少數(shù)類，剩下的其他樣本視為多數(shù)類，并進(jìn)行分類操作，最終對(duì)所有7類樣本分別進(jìn)行分類后的結(jié)果求平均值。這樣，就可以把包含多類的數(shù)據(jù)集分類問題轉(zhuǎn)換為二分類問題。

為了驗(yàn)證算法的有效性，將DivTopKShapelet方法和DivAUCShapelet方法分別作為時(shí)間序列shapelets的提取方法，并利用提取結(jié)果分別與C4.5、1NN、Naive Bayes、Bayesian Network、Random Forest和Rotation Forest六種分類算法進(jìn)行結(jié)合，并使用以上數(shù)據(jù)集運(yùn)行10遍，最后對(duì)結(jié)果求平均值。下面將從分類的準(zhǔn)確率、分類結(jié)果的AUC值以及F-measure值三個(gè)維度進(jìn)行分析。

2.2? F-measure值分析

F-measure值是Precision和Recall的加權(quán)調(diào)和平均，綜合考慮了準(zhǔn)確率和召回率，能夠衡量不平衡數(shù)據(jù)集的分類效果，值越接近1表示分類效果越好。表2為DivTopKShapelet和DivAUCShapelet方法與六種分類器結(jié)合使用后的F-measure值，加粗?jǐn)?shù)據(jù)為兩種方法對(duì)同一個(gè)數(shù)據(jù)集分類得到的最高F-measure值。由表中可知，相比DivTopKShapelet方法，DivAUCShapelet方法在與六種分類器結(jié)合使用后，對(duì)四個(gè)數(shù)據(jù)集分類的F-measure平均值分別提高了0.10、0.17、0.04和0.02，并使用Naive Bayes分類器在ECG200數(shù)據(jù)集和Wafer數(shù)據(jù)集、使用Random Forest分類器Adiac數(shù)據(jù)集上取得了最好的結(jié)果。因此，DivAUCShapelet方法在對(duì)不平衡數(shù)據(jù)集進(jìn)行分類時(shí)相比DivTopKShapelet擁有更好的結(jié)果。

2.3? AUC值分析

表3給出了DivTopKShapelet和DivAUCShapelet方法與六種分類器結(jié)合使用后的AUC值，加粗?jǐn)?shù)據(jù)為兩種方法對(duì)同一個(gè)數(shù)據(jù)集分類得到的最高AUC值。相比DivTopKShapelet方法，DivAUCShapelet方法在與六種分類器結(jié)合使用后，對(duì)四個(gè)數(shù)據(jù)集分類的AUC平均值分別提高了0.06、0.16、0.06和0.04，并使用Naive Bayes分類器在ECG200數(shù)據(jù)集和Wafer數(shù)據(jù)集、使用Rotation Forest分類器在Fish數(shù)據(jù)集、使用Bayesian Network分類器在Adiac數(shù)據(jù)集上取得了最好的結(jié)果。因此，DivAUCShapelet方法在對(duì)不平衡數(shù)據(jù)集進(jìn)行分類時(shí)相比DivTopKShapelet擁有更好的結(jié)果。

3? 結(jié)? 論

針對(duì)基于時(shí)間序列shapelets轉(zhuǎn)換的算法不能很好地使用不平衡數(shù)據(jù)集的分類問題，本文使用AUC作為衡量shapelets好壞的標(biāo)準(zhǔn)，提出了一種基于多樣化top-k shapelets的不平衡數(shù)據(jù)集分類方法，并從分類結(jié)果的準(zhǔn)確率、AUC值以及F-measure值三個(gè)方面進(jìn)行分析。實(shí)驗(yàn)表明，該方法在不平衡數(shù)據(jù)集上分類時(shí)在多數(shù)情況下均優(yōu)于原本的DivTopkShapelet方法，具有較大的實(shí)際應(yīng)用價(jià)值。

參考文獻(xiàn)：

[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] 楊海民，潘志松，白瑋.時(shí)間序列預(yù)測(cè)方法綜述 [J].計(jì)算機(jī)科學(xué)，2019，46（1）：21-28.

[3] 劉恒，侯越.貝葉斯神經(jīng)網(wǎng)絡(luò)在股票時(shí)間序列預(yù)測(cè)中的應(yīng)用 [J].計(jì)算機(jī)工程與應(yīng)用，2019，55（12）：225-229+244.

[4] 潘曉，馬昂，郭景峰，等.基于時(shí)間序列的軌跡數(shù)據(jù)相似性度量方法研究及應(yīng)用綜述 [J].燕山大學(xué)學(xué)報(bào)，2019，43（6）：531-545.

[5] 付國慶.傳感器網(wǎng)絡(luò)時(shí)間序列數(shù)據(jù)計(jì)算及可視化研究 [D].大連：大連理工大學(xué)，2019.

[6] 楊夢(mèng)晨，陳旭棟，蔡鵬，等.早期時(shí)間序列分類方法研究綜述 [J].華東師范大學(xué)學(xué)報(bào)：自然科學(xué)版，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] 金海波.一種時(shí)間序列shapelets快速發(fā)現(xiàn)算法 [J].太原科技大學(xué)學(xué)報(bào)，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的時(shí)間序列分類研究 [J].計(jì)算機(jī)科學(xué)，2019，46（1）：29-35.

[12] 孫其法，閆秋艷，閆欣鳴.基于多樣化top-k shapelets轉(zhuǎn)換的時(shí)間序列分類方法 [J].計(jì)算機(jī)應(yīng)用，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．

作者簡(jiǎn)介：孫其法（1991—），男，漢族，山東棗莊人，初級(jí)職稱，碩士研究生，研究方向：數(shù)據(jù)挖掘、計(jì)算機(jī)網(wǎng)絡(luò)。

收稿日期：2022-10-20