，2*

（1.中國礦業(yè)大學計算機科學與技術學院，江蘇徐州 221116；2.中國礦業(yè)大學災害智能防控與應急救援創(chuàng)新研究中心，江蘇徐州 221116）

0 引言

時間序列分類和不平衡數(shù)據(jù)分布是實際應用中普遍存在的問題。時間序列存在數(shù)據(jù)維度高、數(shù)據(jù)之間相關性強和噪聲干擾多等特點，而不平衡數(shù)據(jù)學習則更加強調分類器對少數(shù)類樣本的識別能力。一方面時間序列數(shù)據(jù)的特殊性使得不平衡學習領域的方法不能完全適用，時間序列的高維度、時間相關性和序列數(shù)據(jù)存在先后邏輯順序的特點使不平衡問題在時間序列條件下變得更加復雜。例如序列數(shù)據(jù)中的少數(shù)類和噪聲的判別會更加艱難，類重疊會更難以處理等；同時，現(xiàn)有的解決時間序列不平衡的方案以重采樣為主，其中又是以生成少數(shù)類合成樣本的過采樣方法為重點，而時間序列較一般數(shù)據(jù)更難合成合適的人工樣本，這導致合成的樣本效果往往并不理想。

進一步，已有的解決時間序列不平衡的方案大多只適用于二分類問題，如果通過將多分類轉換為二分類的問題分解方式，則會造成整體數(shù)據(jù)分布的變化，仍會影響最終的分類效果。綜上所述，直至目前時間序列不平衡分類仍然是亟待解決的重要實際應用問題。集成學習方法在時間序列分類問題中取得了顯著的精度優(yōu)勢，但是其對數(shù)據(jù)集分布的不均衡性不敏感。

基于變換的集合的層次投票集合（Hierarchical Vote Collective of Transformation-based Ensembles，HIVE-COTE）［1］是目前表現(xiàn)最為出色的時間序列集成分類框架，但其中的組件沒有考慮數(shù)據(jù)集分布的不均衡問題，屬于不平衡時間序列的弱分類器。由集成學習理論可以得知，組件算法中若是不存在強分類器會嚴重影響到集成算法的能力上限。其中，HIVE-COTE 針對shapelet 特征設計了算法組件ST-HESCA（Shapelet Transformation-Heterogeneous Ensembles of Standard Classification Algorithm），該算法由于存在子序列評價指標對不平衡數(shù)據(jù)不敏感問題，成為影響HIVE-COTE 集成框架的弱分類器組件。

本文首先提出了一個結合提升方法（Boosting）和基于K最近鄰（K-NearestNeighbor，K-NN）的多類不平衡問題的合成少數(shù)過采樣算法（K-NN-based Synthetic Minority Oversampling algorithm for Multiclass imbalance problems，SMOM）的改進集成分類算法SBST-HESCA（SMOM &Boosting into ST-HESCA algorithm），提高ST-HESCA 算法組件針對不平衡時序數(shù)據(jù)的分類準確率；同時結合SBST-HESCA 組件對HIVE-COTE 計算框架進行改進，提出IMHIVE-COTE（Imbalanced Hierarchical Vote Collective of Transformation-based Ensembles）集成算法，通過優(yōu)化結果的集成策略，增強集成算法對少數(shù)類樣本識別精度的傾斜力度。

1 相關算法介紹

本章對兩個涉及到的基礎算法進行介紹，方便理解后續(xù)本章提出算法的設計意義和動機。

1.1 SMOM 算法

SMOM 是一個基于K最近鄰（K-NN）思想的綜合少數(shù)類過采樣算法，與典型基于K-NN的過采樣算法不同，SMOM為每個近鄰的方向分配一個選擇權值；同時，對可能產(chǎn)生嚴重泛化的相鄰方向賦予較小的選擇權值，從而使SMOM形成了一種避免過度泛化的機制。

為了實現(xiàn)這一目的，SMOM算法在分配少數(shù)類K個方向上的權值之前，應用不平衡數(shù)據(jù)上的聚類方法對少數(shù)類樣本進行劃分，從少數(shù)類樣本集中界定出了突出集群和困境集群：突出集群中由少數(shù)類占據(jù)主導地位，有明確的類邊界；困境集群中則會包含很多其他類樣本，難以界定類邊界，這個區(qū)域的少數(shù)類會更需要在近鄰的方向分配合適的選擇權值。此外，聚類方法還起到了減少權值計算量的作用，因為突出集群中的少數(shù)類樣本的近鄰權值無需計算。

在文獻［2］中，已經(jīng)證明SMOM 算法的運行效率優(yōu)于現(xiàn)有簡單過采樣方法，同時在G-means、曲線下面積（Area Under Curve，AUC）和召回率（Recall）等不平衡指標方面，SMOM在統(tǒng)計學上優(yōu)于其他采樣方法。在本文4.2 節(jié)的實驗部分還可以證明該算法在不平衡時間序列方面有很好的適應能力，優(yōu)于通用的SMOTE（Synthetic Minority Oversampling Technique）方法。

1.2 HESCA 和ST-HESCA算法

HESCA（HeterogeneousEnsemblesofStandard Classification Algorithm），最先在文獻［3］出現(xiàn)，和傳統(tǒng)的集成分類方法相比，該方法更注重基礎分類器的多樣性，為了達成這一目的，它采用了異構集成的構成模式，異構集成方法較原始集成方法泛化能力更強，是目前時間序列分類中整體分類效果最好的集成分類策略，下面對它的算法構成進行簡單介紹。

HESCA 由八個分類器組成，其中：兩個自身也是集成分類算法：分別是隨機森林（500棵樹）和旋轉森林（50棵樹）；其余6個為K近鄰、樸素貝葉斯、C4.5 決策樹、具有線性和多項式核函數(shù)的支持向量機和貝葉斯網(wǎng)絡。這些選擇囊括了基于概率、基于序列個體實例和基于樹的分類器3類，確保了集成分類器整體的泛化能力。算法通過10折交叉驗證獲得其中每個組成算法的準確度估計值，作為后來預測測試集類別的加權指標。

在文獻［4］中，Bagnall和Lines等進行了一個當前主流時間序列分類算法的對比實驗，實驗數(shù)據(jù)集采樣UCR標準時間序列數(shù)據(jù)，在精度上取勝的分別是HIVE-COTE、FLAT-COTE［5］和shapelet變換算法，這其中的shapelet變換算法就是shapelet變換結合HESCA來實現(xiàn)的（ST-HESCA），這一方法同時也被運用于HIVE-COTE，F(xiàn)LAT-COTE之中作為shapelet分類模塊的核心算法，即ST-HESCA算法，因為它有著目前shapelet分類方法中最高的平均精度［6］。為了保證shapelet 集合的完整性，在shapelet計算部分，ST-HESCA采用一對多（one vs all）編碼方案簡化了質量評估計算，在選取shapelet方面通過更頻繁的早期放棄策略提高了執(zhí)行速度，并提高了多類問題的準確性［7］。這使得該過程較蠻力shapelet計算相比有較大效率提升，但是整體效率還是偏低，不能用來處理大規(guī)模時間序列數(shù)據(jù)集。

2 結合Boosting 和SMOM 采樣的ST-HESCA組件算法

已有的時間序列分類算法中，對子序列的評價標準大部分以信息增益為主。本節(jié)給出兩種基于不平衡分類指標的子序列評價標準，分別是基于AUC 值和F（F-measure）值的評價指標（簡稱AF指標），以及基于AUCPR（Area Under Curve-Precision Recall）值和AUC值的評價指標（簡稱AR指標），兩個指標均是在傳統(tǒng)質量評價指標的基礎上，引入不平衡率（Imbalance Rate，IR）來調和傳統(tǒng)指標和不平衡數(shù)據(jù)指標之間的權重比例，滿足“數(shù)據(jù)分布的IR值越大，不平衡數(shù)據(jù)指標作用越大”的條件，從而更加準確地評價分類結果，對不平衡分類的適用性更高，比常用指標對不平衡時序類別的代表能力更強。

2.1 指標定義

定義1AF 指標。多分類情況下計算AUC 值時，引入不平衡率作為權值，這里不平衡率指的是當前數(shù)據(jù)集中，多數(shù)類數(shù)量與少數(shù)類數(shù)量的比值，數(shù)量相差越懸殊，不平衡率越大。在不平衡率較小時，評價指標中根據(jù)IR值增加AUC值的比例，改進AF指標，如式（1）所示：

定義2AR 指標。評價指標AR 值的定義和AF 指標類似，引入不平衡率作為權值，如式（2）所示：

2.2 算法思路

傳統(tǒng)基于Boosting 的集成模型的流程如圖1，可以看出Boosting方法會迭代多次地訓練一個分類器，通過不同分布的訓練子集反復對分類模型進行訓練達到增強模型泛化能力的目的，最終達成將弱分類器變?yōu)閺姺诸惼鞯男Ч?］。在不平衡問題的解決思路中，利用重采樣結合Boosting集成算法被證實是有效的［9］，可以根據(jù)分類結果迭代更新樣本的權重，更準確地評估重采樣樣本的質量，平衡不均衡數(shù)據(jù)分布的同時，更有利于提升少數(shù)類樣本的分類質量。

圖1 Boosting 集成算法訓練流程Fig.1 Training flowchart of Boosting-based ensemble algorithm

Boosting算法的弱可學習理論表明，有限的迭代次數(shù)將弱學習算法經(jīng)過多次訓練，可以組合為強學習算法［10］。在HIVECOTE 中，ST-HESCA 算法是一個對不平衡時間序列數(shù)據(jù)不敏感的弱學習算法組件［11］，本文的優(yōu)化思路是：將SMOM 采樣算法結合Boosting 算法思想在每輪迭代過程中對不平衡數(shù)據(jù)集進行重采樣，在每輪ST-HESCA算法模型的訓練過程中將不平衡分類指標G-means、AUC值、AUCPR 值作為分類模型的評價標準，并根據(jù)交叉驗證預測結果更新當次訓練所得ST-HESCA算法模型的樣本權重，然后通過有限度的多次迭代過程實現(xiàn)對ST-HESCA算法模型的不平衡數(shù)據(jù)學習能力的反復訓練提升，最后組合所有迭代過程所得到的分類模型構成一個完備訓練的SBST-HESCA 集成分類算法模型，提高了SBST-HESCA 算法組件針對不平衡時序數(shù)據(jù)的分類準確率。

2.3 算法說明

SBST-HESCA 算法的實現(xiàn)流程如圖2，算法訓練測試數(shù)據(jù)為采用AR指標得到的shapelet進行轉換后的數(shù)據(jù)集，采用AR指標是由于實驗中AR 指標相對于AF 指標對shapelet 候選集質量的提升更加穩(wěn)定。

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

迭代處理過程中，首先給每個訓練樣本初始化一個權重系數(shù)，其值為本輪迭代開始時所有少數(shù)類樣本的權重均值，然后每一輪迭代利用SMOM 算法人工合成少數(shù)類樣本，交給STHESCA 算法進行多次交叉預測，最后根據(jù)這些預測結果更新合成樣本的權重，在本過程中HESCA算法更新權重的判斷依據(jù)為通過交叉預測結果計算出的不平衡分類指標綜合值，這個綜合值由AUC、AUCPR 和G-means 值共同判定，而不是STHESCA算法所使用的分類精度。由該過程訓練得到的分類器為對應迭代流程的基分類器，訓練樣本的決策權重在本輪迭代過程被更新后用于下一次迭代訓練過程。相對于ST-HESCA，SBST-HESCA算法采用本文給出的AR指標對子序列質量進行評價，該指標比原算法中的“信息增益值”更能準確度量不平衡數(shù)據(jù)集中shapelets的質量。同時，引入Boosting結合重采樣的思路，通過交叉驗證預測結果更新樣本權重，使數(shù)據(jù)集的重采樣過程更有利于提升少數(shù)類樣本的分類質量。

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

SBST-HESCA 算法在第1）～2）行對訓練樣本權值進行初始化，第4）行對訓練樣本進行SMOM 采樣處理，第5）～7）行新建一個HESCA 算法模型，然后設定評價指標為AUC 值，AUCPR 和G-means 值，最后采樣后的數(shù)據(jù)導入模型進行交叉驗證，得到當次迭代后的集成分類模型。第8）～10）行對樣本權值進行更新，更新依據(jù)為本次迭代訓練獲得的算法模型得到的交叉驗證結果。最后在第11）行保存本次迭代獲得的集成分類模型和樣本權值，當次迭代結束。第13）～16）行組合所有迭代所得的集成模型和樣本權值，依據(jù)不平衡分類指標構建SBST-HESCA 分類模型，最后對測試數(shù)據(jù)進行預測得到分類結果。

3 IMHIVE-COTE 集成分類算法

3.1 投票權重的調整

HIVE-COTE 算法的權值計算相對于其前身FLAT-COTE算法的權值計算有了一個很大的調整，F(xiàn)LAT-COTE 算法的權值計算是一個扁平（flat）的結構，即所有組件算法不受模塊化限制，一同參與最后的集成分類決策［12］，存在的問題是：同類型數(shù)量多的算法往往占有投票的優(yōu)勢。HIVE-COTE 算法對組件算法的模塊化和分層化解決了這一問題［13］。本節(jié)對HIVE-COTE 算法集成策略進行優(yōu)化，重點在于對每個組件算法的投票權重進行優(yōu)化，而對算法自身內容并不進行變動。

HIVE-COTE 算法在訓練分類器的過程中，先由各模塊對訓練數(shù)據(jù)進行模塊內部的集成分類器的訓練，然后HIVECOTE以不同模塊為單位進行訓練數(shù)據(jù)的交叉分類訓練，在這個過程中確定HIVE-COTE 算法賦予每個模塊在分類模型中的投票權重。HIVE-COTE 算法的權值計算方法為式（3），集成學習算法中存在g個集成算法模塊，對c個類的數(shù)據(jù)進行分類預測，集成算法給出這個類為i的可信度為所有模塊算法對這個序列類標簽為i的置信度與集成算法模塊對應的決策權值乘積的和，除以當前集成算法所有的權值與預測置信度的乘積和，其中w權值的確定根據(jù)交叉訓練獲得的分類精度來估算。則權值w的計算公式（3）可以簡寫為w=f（accuracy）。

本文繼續(xù)沿用式（3）的權值計算方法，但是在權值w的計算過程中，原算法是根據(jù)交叉訓練過程中該集成模塊得到的分類精度計算得到，本文算法則基于交叉訓練結果的AUC 值、AUCPR值和G-means值（G）進行權值計算，將三者的算術平均值作為集成算法模塊的權值判斷依據(jù)，確定權值的方法如式（4）所示：

3.2 IMHIVE-COTE 算法的整體概述

在SBST-HESCA 算法對ST-HESCA 組件進行優(yōu)化的基礎上，針對HIVE-COTE 集成算法，提出不平衡時間序列的集成分類方法IMHIVE-COTE。該算法從以下三個方面對HIVECOTE進行了優(yōu)化。

1）在shapelet 選擇算法和時間序列森林（Time Series Forest，TSF）算法部分，原算法采用的是信息增益值對子序列質量進行評價［14］，IMHIVE-COTE 算法將采用提出的AR 指標進行替換。

2）將第2 章提出的SBST-HESCA 算法加入shapelet 模塊，與原有的ST-HESCA算法組件進行競爭，這部分的算法決策權值由式（4）來決定，即不平衡集成算法參與異構集成的分類決策，改善現(xiàn)有組件算法對不平衡時間序列數(shù)據(jù)的學習能力。

3）由于HIVE-COTE 是平衡時間序列下的分類算法，組件算法的投票比重計算依據(jù)的是整體精度這準，IMHIVE-COTE算法則采用式（4）作為集成算法模塊的權值判斷依據(jù)，從整體上提升集成算法對不平衡時間序列數(shù)據(jù)集的分類精度。

4 實驗結果與分析

實驗采用了F 值、G/MG（G-means/MG）值、AUC 值、AUCPR值作為評價指標。

二元分類問題中真陽性率被稱為召回率（Recall）它代表分類器正確識別出的少數(shù)類占所有少數(shù)類數(shù)量的比值，與其對應的精確率如式（5）所示：

其中：TP是被分類模型正確預測的正樣本數(shù)，F(xiàn)P是被分類模型錯誤預測為正類的負樣本數(shù)。精確率代表分類器正確識別出的多數(shù)類占所有多數(shù)類數(shù)量的比值。在不平衡分類的環(huán)境中，一般需要優(yōu)先保證召回率足夠高，其次是精確率。這兩個數(shù)值調和起來就出現(xiàn)了F-measure值，其β系數(shù)通常取1，這個情況下它的表達式可以簡寫成式（6）：

F 值能相對較好地反映出不平衡數(shù)據(jù)分類結果的好壞。但是不平衡分類關注的重點在于召回率，比如同樣的F 值下的兩種分類結果中，不平衡分類效果上而言Recall 值更高的分類結果更應該得到較好的評價。此外G-means 值也是一個不平衡分類算法的通用評價指標，其公式為：

只有在召回率和精確率都比較大時才比較高，較F值更難達成，對不平衡分類算法在少數(shù)類樣本上的學習能力要求更高。多分類對比指標MG值公式如下：

AUC值的確認方法如式（9）所示：

ranki表示第i條樣本的序號，M、N分別是正樣本數(shù)和負樣本數(shù)。PR 曲線以召回率為x軸，精確率為y軸，在不同閾值下得到對應坐標點，進而完成曲線的繪制。其曲線下面積值即為AUCPR。AUCPR值由于其來源的橫縱坐標都是正類樣本的分類指標，以及在正負樣本數(shù)量相差懸殊時會受到較大影響，被認為更適合于在不平衡程度更夸張的情況下考察不平衡分類算法的分類性能，而AUC 值能夠不受數(shù)據(jù)的不平衡率給出整體上的分類效果評價。上述值越大，說明模型的性能越好。

4.1 實驗說明

將2.1 節(jié)提出的AF 指標和AR 指標運用在DIMS（Dimensions）算法中，這里DIMS算法是在二分類數(shù)據(jù)上使用的Binary_DIMS算法和在多分類數(shù)據(jù)上使用的Multi_DIMS［15］算法的總稱，實驗中為了區(qū)分兩個評價指標，應用了AF指標的算法稱為AF_DIMS，應用了AR指標的算法稱為AR_DIMS。本節(jié)對提出的兩個算法：SBST-HESCA算法和IMHIVE-COTE算法進行分類效果驗證。數(shù)據(jù)集為公共數(shù)據(jù)集UCR上的不平衡二分類和多分類時間序列數(shù)據(jù)集［16］。對比算法選取了時間序列分類算法HIVE-COTE、重采樣算法Influential Neighbourhood for Over-Sampling（INOS）和時間序列不平衡分類算法SMOM 和AdakNN2+GIHS、shapelets方法AF_DIMS和AR_DIMS。

4.2 實驗結果與分析

觀察表1的實驗數(shù)據(jù)，可以發(fā)現(xiàn)除和平衡分類關系較近的F值指標外，本文提出的有關算法在G/MG值、AUC值2個不平衡指標中獲得了最大的指標領先數(shù)，其中G/MG 值IMHIVECOTE算法性能最好，其次是HIVE-COTE算法；在AUC值分類結果上，IMHIVE-COTE 算法領先，其次是SMOM 算法；針對F指標和AUCPR 指標，IMHIVE-COTE 算法效果不及AR_DIMS?？傮w來說，IMHIVE-COTE算法的優(yōu)勢體現(xiàn)在以下兩個方面：

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 集成框架中還包括其他組件算法，沒有針對不平衡數(shù)據(jù)進行改進，因此影響了IMHIVE-COTE 的整體性能。但上述兩點也說明，IMHIVE-COTE 為集成學習方法針對不平衡數(shù)據(jù)分類問題，提出了一個有效的優(yōu)化思路。

表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 值，在不平衡時間序列數(shù)據(jù)集中，對于SBST-HESCA 組件中shapelets的選擇起到了重要作用。

2）改進算法SBST-HESCA 在不平衡數(shù)據(jù)的分類上有了更好的分類效果，顯著增強了IMHIVE-COTE 集成算法的對不平衡時間序列數(shù)據(jù)的泛化能力。

3）相較于表1中基于平衡分類的評價指標F值，在不平衡指標值中，IMHIVE-COTE 算法得到的評價值更好，證明IMHIVE-COTE更適應于不平衡時間序列數(shù)據(jù)分類。

5 結語

本文給出了一個新的不平衡時間序列分類方法SBSTHESCA，分析并驗證了該算法在不平衡分類方面的能力，然后總結本文實驗成果之后，給出了一個完善的不平衡時間序列上的異構集成分類算法IMHIVE-COTE。最后經(jīng)過實驗驗證，表明了IMHIVE-COTE算法能很好地總結時間序列的不平衡分類特點，保持異構集成方法在不平衡時間序列數(shù)據(jù)上的分類優(yōu)勢。