早期時間序列分類方法研究綜述

楊夢晨 陳旭棟 蔡鵬 倪葬

摘要：傳感器技術(shù)的普及使得時間序列數(shù)據(jù)受到人們越來越多的關(guān)注.早期時間序列分類（Early Time Series Classification， ETSC）希望通過觀測盡可能短的時序數(shù)據(jù)而對其做出盡可能準確的分類，已在科技 金融領(lǐng)域發(fā)揮著重要的作用.首先概述了常見的時間序列分類器，并綜述了基于最小預(yù)測長度、基于最大 區(qū)分子序列和基于模型的3類早期時間序列分類框架的最新研究進展.然后在每類方法中，分析了具有代 表性的早期時間序列分類模型的關(guān)鍵技術(shù)及其優(yōu)缺點;整理了科技金融領(lǐng)域的公開數(shù)據(jù)集和常見的評價 指標(biāo).最后對未來的發(fā)展趨勢做了展望.

關(guān)鍵詞：早期時間序列分類;時間序列分類器;最小預(yù)測長度;最大區(qū)分子序列;機器學(xué)習(xí) 中圖分類號：TP391???? 文獻標(biāo)志碼：A DOI： 10.3969/j.issn.1000-5641.2021.05.011

Survey of early time series classification methods

YANG Mengchen， CHEN Xudong， CAI Peng， NI Lyu

（School of Data Science and Engineering， East China Normal University， Shanghai 200062， China）

Abstract： With the increasing popularity of sensors， time-series data have attracted significant attention. Early time series classification （ETSC） aims to classify time-series data with the highest level of accuracy and smallest possible size. ETSC， in particular， plays a critical role in fintech. First， this paper summarizes the common classifiers for time-series data and reviews the current research progress on minimum prediction length-based， shapelet-based， and model-based ETSC frameworks. There are pivotal technologies， advantages， and disadvantages of the representative ETSC methods in separate frameworks. Next， we review public time-series datasets in fintech and commonly used performance evaluation criteria. Lastly， we explore future research directions pertinent to ETSC.

Keywords： early time series classification; time series classifier; minimum prediction length; shapelet; machine learning

0引 言

時間序列數(shù)據(jù)是一組按照時間先后順序進行排列的觀測序列.時間序列數(shù)據(jù)分析是數(shù)據(jù)挖掘 領(lǐng)域的熱點之一，也在科技金融領(lǐng)域中發(fā)揮著重要的作用.隨著科技的進步，智能算法的成熟促使了 金融從業(yè)者有更多、更加精準的方式獲取數(shù)據(jù)和用戶需求.在金融市場中，深度挖掘金融產(chǎn)品歷史 價格數(shù)據(jù)對政府和投資者有著重要的意義[1-21.以證券價格為例，精確預(yù)判證券價格對政府而言，有利 于政府加強對證券市場的把控，做出及時有效的行政干預(yù)，正確推動證券市場的健康發(fā)展;對企業(yè)或 個人投資者來說，及時感知證券價格的變化，有效規(guī)避造成巨大損失的投資風(fēng)險，優(yōu)化金融產(chǎn)品的投資組合，以此實現(xiàn)投資收益最大化.因此，早期時間序列分類是科技金融領(lǐng)域內(nèi)亟待解決且具有應(yīng)用 價值的問題[3]，而早期時間序列分類應(yīng)用廣泛，如醫(yī)學(xué)檢測、智能交通、行為識別等領(lǐng)域，具有深遠且 重要的研究意義.

近年來，早期時間序列分類方法受到國內(nèi)外研究者的熱切關(guān)注，有些學(xué)者對已有的早期時間序列 分類模型進行了系統(tǒng)整理，其中不乏一些優(yōu)秀的綜述論文[4-6].馬超紅等⑷于2016年對基于原始數(shù)據(jù)、 基于特征的時間序列早期分類進行了總結(jié);同年，Santos等[5]歸納了當(dāng)前已實現(xiàn)的主要的早期分類框 架，如ECTS、RelClass、ECDIRE，但其論文發(fā)表時間較早.隨后，Gupta等[6]在早期時間序列分類領(lǐng) 域相關(guān)研究進展的基礎(chǔ)上，對其方法進行了比較和歸類，將其歸為基于前綴、基于特征、基于模型和 其他方法等4類，但未聚焦于科技金融領(lǐng)域.本文與已有的綜述文獻不同，在總結(jié)已有方法的基礎(chǔ)上， 更新了早期時間序列分類方法的最新進展，且側(cè)重于分類時間點的確定策略.

本文的主要貢獻：概述了時間序列分類器的構(gòu)造方法;從決策時刻的角度總結(jié)并綜述了以最小預(yù) 測長度（Minimum Prediction Length，MPL）、最大區(qū)分子序列（Shapelet）和模型這3類的時間序列分 類時間點的確定方法;系統(tǒng)性梳理了未來的研究方向，這將有助于學(xué)者后續(xù)的研究和探索.

本文的結(jié)構(gòu)：第1章介紹時間序列領(lǐng)域的基礎(chǔ)知識;第2章對時間序列分類器的構(gòu)造方法進行闡 述，如圖1（a）所示;第3章主要圍繞時間序列分類時間點的確定方法進行闡述，其框架如圖1（b）所示; 第4章整理早期時間序列分類問題的應(yīng)用領(lǐng)域、數(shù)據(jù)集及評價指標(biāo);第5章討論早期時間序列分類的 未來研究方向，并對全文進行總結(jié).

1基礎(chǔ)知識

本章主要介紹時間序列領(lǐng)域的相關(guān)定義、主要的研究問題.

1.1相關(guān)定義

（1）單變量時間序列（Univariate Time Series，UTS）： —組按時間順序排列的反映某一變量的隨機 數(shù)列，又稱為時間序列（Time Series，TS）.令

X = （Xi ，X2， ··· ，Xt， ··· ，XT）

表示時間序列數(shù)據(jù)，其中，下標(biāo)變量〖表示間隔的時刻，變量T表示結(jié)束時刻，xt表示在t時刻的觀測 值，1 ? t ? T.假定每組時間序列僅有唯一可識別的樣本標(biāo)簽c，令C表示樣本標(biāo)簽集合.

（2）多變量時間序列（Multivariate Time Series，MTS）：在同一個時間點上有多個觀測數(shù)據(jù)，可表示為

X = （Xi， X2， ··· ， Xt， ··· ， Xt ），

xt = （xt，l， xt，2， ' ' ' ， xt，j， ' ' ' ， xt，K），

其中，變量K表示時間序列向量的維度，xtj表示在^時刻第j個變量的觀測值，1 ? t ? T， 1 ? j ? K.

⑶最大區(qū)分子序列（Shapelet）：用于刻畫時間序列數(shù)據(jù)的某些屬性，可作為判斷依據(jù)用于預(yù)測過 程.最大區(qū)分子序列^通常定義為1個四元組

S = {s， l， S， c}.

如圖2所示，在標(biāo)簽為c的時間序列x上，提取時間長度為l ，代表標(biāo)簽為c的子集s C x ， J為距離閾值.

（4）準確率（Accuracy ，A）：定義為正確分類樣本數(shù)占總樣本數(shù)#的比率，&是標(biāo)記為^的第i個時 間序列樣本的預(yù)測標(biāo)記.準確率（A）的計算公式為

（5）早期性（Earliness ，五）：定義為總時間T和時間序列的分類時間T的差值與總時間T的比率. 早期性（妁的計算公式為

1.2問題描述

早期時間序列分類（ETSC）希望能夠通過盡可能少的時序數(shù)據(jù)的觀測做出盡可能準確的分類.與 傳統(tǒng)的時間序列分類不同之處在于，傳統(tǒng)時間序列分類是在觀測了所有的時序數(shù)據(jù)后做出的準確分 類判斷;而早期時間序列分類不僅關(guān)注分類結(jié)果的準確率，同樣也關(guān)注能夠近實時地產(chǎn)生分類結(jié)果， 這通常被稱為分類早期性.分類早期性可以讓人們及時地進行應(yīng)對處理，降低總體損失，如圖3所示. 早期時間序列分類過程的核心在于構(gòu)建時間序列分類器和確定決策時間點這兩個階段，從而達到使 用較少數(shù)據(jù)獲得較大可靠性的權(quán)衡過程.

2時間序列分類器的構(gòu)造方法

在早期時間序列分類的問題中，因為分類結(jié)果的準確性是一個較為重要的考量指標(biāo)，所以構(gòu)建適 合時間序列的分類器是一個基本問題.現(xiàn)有已不少應(yīng)用于時間序列分類的分類器.本節(jié)將已有文獻根 據(jù)分類器進行了歸納和總結(jié)，并強調(diào)了一些基于時間序列分類器而提出有針對性的早期時間序列分 類的方法.

2.1基于A;-NN分類器

念近鄰（A;-Nearest Neighbors， A;-NN）是一種基于實例的學(xué)習(xí)算法：計算與已知類別樣本的相似度， 從而評估未知類別樣本可能的分類.由于時間序列數(shù)據(jù)的有序性、緯度高、噪聲大以及序列不等長， 在以相似度作為衡量指標(biāo)的時間序列分類中，選擇合適的距離度量是一個關(guān)鍵問題.

以歐氏距離（Euclidean Distance，ED）為代表的鎖步測量方法[7]，是將2條時間序列的第i個時間 點進行一對一比較，如在樣本少量標(biāo)記的情況下，使用歐氏距離提高1-NN分類器的性能[8].另一類是 彈性測量方法，如動態(tài)時間規(guī)整（Dynamic Time Warping，DTW），其關(guān)注于創(chuàng)建非線性映射以對齊序 列并允許一對多點的比較.原繼東等[9]為解決同類復(fù)雜時間序列存在不同的全局特性這一問題，提出 了基于局部加權(quán)DTW方法的A;-NN分類器;該分類器可以挖掘出同類復(fù)雜時間序列中的共同點以及 異類序列之間的異同點;并且由于分類器具有可解釋性和有效性，他們也將其應(yīng)用到多變量時間序列 分類問題中.Jeong等[1°]考慮到由于相位差引起形狀相似對比時的誤分類問題，提出了一種加權(quán) DTW進行時間序列分類.Berndt等[11]將應(yīng)用在語音識別領(lǐng)域的DTW方法成功地應(yīng)用在時間序列的 模式識別中.Chen等[12]以使用歐氏距離的1-NN算法作為基準，與具有不同變形窗口的DTW方法進 行比較.鎖步測量方法對有噪聲、有相位差的數(shù)據(jù)較為敏感，而彈性測量方法能較好地處理時間維度 上數(shù)據(jù)的變形.實驗證明，平均而言，基于DTW的距離度量方法似乎很難被擊敗[13-19].

2.2基于SVM分類器

支持向量機（Support Vector Machine，SVM）理論是20世紀90年代Vapnik在統(tǒng)計學(xué)習(xí)理論的 框架下提出的一種新型的學(xué)習(xí)機器[20]，其學(xué)習(xí)策略是求解能夠正確劃分訓(xùn)練數(shù)據(jù)集，并且使得幾何間 隔為最大的分離超平面.當(dāng)輸入空間是非線性數(shù)據(jù)集時，可以將此問題通過非線性變換轉(zhuǎn)化為某個維 度特征空間中的線性分類問題，且在此特征空間中學(xué)習(xí)線性SVM分類器.SVM采用結(jié)構(gòu)風(fēng)險最小化， 能夠較好地解決小樣本、非線性和高維數(shù)問題，具有較好的泛化能力[21].

Tay等[22]通過修改SVM的正則化風(fēng)險函數(shù)，提出了 “C-ascending”支持向量機模型，并基于非平 穩(wěn)金融時間序列的輸入變量和輸出變量之間的依存關(guān)系隨時間逐漸變化這一先驗知識，對近期& 敏感度樣本的錯誤，設(shè)定了一個要比遠期s-敏感度樣本的錯誤進行更嚴厲的懲罰.也有一些學(xué)者并非 將原生時間序列作為SVM模型的輸入，如李翔宇等[23]提出了一種基于改進核函數(shù)的支持向量機算 法，即將樣本與空間基的時間序列的互相關(guān)距離作為新樣本映射到新的特征空間中，實現(xiàn)對線性核函 數(shù)改進;Jalalian等[24]引入兩步走的DTW-SVM分類器，即先使用DTW方法將原生時間序列轉(zhuǎn)換為 特征向量DFdtw，再將其作為SVM模型的輸入;Kate[25]在DTW-SVM分類器的基礎(chǔ)上，提出了受限 DTW窗口大小的特征向量DFdtw-r和歐氏距離提取的特征向量D^ed，依據(jù)特征向量對樣本數(shù)據(jù)進 行分類.

2.3基于決策樹分類器

決策樹是基于樹結(jié)構(gòu)進行分類的成熟的機器學(xué)習(xí)算法之一，對噪聲的干擾具有較好的魯棒性，且 決策樹一旦建立，未知樣本的分類速度較快.基于決策樹模型的特性，數(shù)據(jù)挖掘領(lǐng)域衍生出許多改進 算法適用于線性和非線性數(shù)據(jù)集的趨勢預(yù)測[26].

在時間序列分類問題中，最早采用決策樹思想的是Yamada等提出的二叉分類樹，即通過窮舉 搜索得到信息增益最大的1條或1對時間序列將其作為分裂節(jié)點的兩種不同策略，且策略均采用 DTW方法來度量時間序列的相似性.Douzal等[28]引入一種基于時間序列鄰近度的新劃分準則，該準 則綜合考慮了趨勢相似與數(shù)值相似的自適應(yīng)性的度量指標(biāo)，并采用此度量指標(biāo)建立能夠處理時 間序列的決策樹.施沫寒等[29]將基于子序列和基于決策樹的分類模型進行融合，提出了組合Shapelets 森林（Random Pairwise Shapelets Forest， RPSF）模型，該模型主要應(yīng)用于生物特征識別領(lǐng)域中，模型 不僅保留了原算法良好可解釋性的優(yōu)點，又降低了訓(xùn)練模型的開銷.徐雷等在多變量時間序列數(shù)據(jù) 中考慮數(shù)據(jù)間的自相關(guān)性，引入了序列熵的概念來代替決策樹中的信息熵，并提出了序列對信息增益 的新概念，以此構(gòu)建時間序列決策樹（Time Series Decision Tree， TSDT）. XGBoost算法是基于梯度 提升決策樹的改進算法[31]，優(yōu)化了算法本身和算法運行效率，包括回歸樹和分類樹[32-331.

2.4基于神經(jīng)網(wǎng)絡(luò)分類器

在理論上，神經(jīng)網(wǎng)絡(luò)能映射十分復(fù)雜的非線性關(guān)系，使其具備強大的非線性泛化能力.同時，自學(xué) 習(xí)、自適應(yīng)和大規(guī)模并行處理能力也是神經(jīng)網(wǎng)絡(luò)模型的優(yōu)點.因此，神經(jīng)網(wǎng)絡(luò)模型廣泛應(yīng)用于金融[34]、 自然語言處理岡、圖像識別[36]等領(lǐng)域.

Cui等最早在時間序列分類任務(wù)中引入神經(jīng)網(wǎng)絡(luò)模型，為解決時間序列具有不同時間尺度特 征這一問題，作者提出了一種新穎的端到端神經(jīng)網(wǎng)絡(luò)模型，即多尺度卷積神經(jīng)網(wǎng)絡(luò)（Multiscale Convolutional Neural Networks， MCNN）.該模型將特征提取和分類合并在一個框架中，借助新穎的多 分支層和可學(xué)習(xí)的卷積層，自動提取不同比例和頻率的特征，從而實現(xiàn)出色的特征表示.與基于特征 的分類模型不同，卷積神經(jīng)網(wǎng)絡(luò)（Convolutional Neural Networks， CNN）可以發(fā)現(xiàn)并提取合適的內(nèi)部 結(jié)構(gòu)，以通過使用卷積和池化操作自動生成輸入時間序列的深層特征.實驗結(jié)果[38]表明，CNN在分類 精度和噪聲容忍度方面均優(yōu)于SVM、1-NN時間序列分類模型.Wang等[39]提出的無須對原始數(shù)據(jù)或 特征進行任何預(yù)處理的端到端的基準模型，具有ResNet結(jié)構(gòu)超深層神經(jīng)網(wǎng)絡(luò)的完全卷積網(wǎng)絡(luò)（Fully Convolutional Network， FCN）.相對于 MCNN、COTE （Collective of Transform-Based Ensembles）、 SE1 （Shapelet Ensemble）、BOSS （Bag-of-SFA-Symbols）等方法，F(xiàn)CN 具有更出色的性能.為幫助網(wǎng)絡(luò) 快速融合，Ulyanov等[40]提出了實例歸一化的思想，通過梯度下降學(xué)習(xí)每個訓(xùn)練實例每層的均值和標(biāo) 準差.

另一種較為流行的深度學(xué)習(xí)框架是循環(huán)神經(jīng)網(wǎng)絡(luò)（Recurrent Neural Network， RNN）.文獻[41-43] 設(shè)計了 RNN自動編碼器，基于學(xué)習(xí)到的潛在特征訓(xùn)練分類器，以預(yù)測給定輸入時間序列的類別.長短 期記憶模型（Long Short-Term Memory， LSTM）是RNN模型的一種特殊結(jié)構(gòu)類型，特點是能夠?qū)W習(xí) 長距離依賴關(guān)系，解決了 RNN處理較長時間序列信息時容易出現(xiàn)梯度消失的問題.包振山等[44]針對 LSTM網(wǎng)絡(luò)預(yù)測收盤價時預(yù)測能力不佳這一問題，在LSTM的模塊中引入遺傳算法，保證了模型預(yù)測 的平衡性.

2.5 基于HMM分類器

隱馬爾可夫模型（Hidden Markov Model， HMM）是由馬爾可夫模型發(fā)展而來的一種統(tǒng)計模型，在 此基礎(chǔ)上增加了多個隱藏狀態(tài)，可用于捕捉時間序列數(shù)據(jù)變量間的依賴關(guān)系和相關(guān)性，因而能夠較好 地起到預(yù)測作用.1個HMM A可用1個三元組表示，即

Λ = （A， B， Π），

其中，義為狀態(tài)轉(zhuǎn)移概率矩陣，b為觀測概率矩陣，n為初始狀態(tài)概率向量.

Gupta等將HMM應(yīng)用在交通系統(tǒng)識別室外環(huán)境領(lǐng)域的多變量時間序列中，根據(jù)不同 標(biāo)記的MPL訓(xùn)練該變量的HMM：狀態(tài)對應(yīng)時間序列樣本標(biāo)簽，維度為/的狀態(tài)集合S = {S1， S2， · · · ， Sl}，狀態(tài)轉(zhuǎn)移矩陣A = （aij ）l×l，其中，

aij = P （state Sj at t + 1|state Si at t）.

因而得到輸入樣本最有可能隱藏的狀態(tài)序列，接著再使用MPL思想進行分類過程.Xing等[46]提出了 一種基于生成式模型和判別式模型的混合模型思想，即生成式模型選擇HMM模型，提取長度不等且 不相交的子序列作為HMM的輸入，其輸出再作為判別式模型的輸入，從而訓(xùn)練模型，一定程度上達 到了數(shù)據(jù)降維的效果.

隨后，有些研究者從分類器實現(xiàn)的角度出發(fā)，設(shè)置激勵時間序列早期分類的策略，探索基于分類 器的實現(xiàn)早期時間序列分類目標(biāo)，如Antonucci等[47]提出的基于HMM的不精確模型（iHMM），在計 算狀態(tài)概率時增加了約束條件.

3時間序列分類時間點的確定方法

早期時間序列分類的任務(wù)是在保證分類準確率的前提下，也關(guān)注于是否能夠較早地獲得分類結(jié) 果，即在分類準確率和時間早期性這兩個評測指標(biāo)中進行相互調(diào)節(jié)和權(quán)衡，從而降低數(shù)據(jù)收集的時間 成本和減小數(shù)據(jù)存儲的空間成本，特別是在對時間較為敏感的應(yīng)用領(lǐng)域.本章主要從確定時間序列分 類時間點的角度，對可適用于不同類型分類器的早期時間序列分類框架進行描述，并比較不同方法之 間的差異和優(yōu)缺點.

3.1基于MPL的確定方法

基于MPL的確定方法在原生前綴空間中，使用訓(xùn)練集樣本學(xué)習(xí)具有穩(wěn)定性的時間序列的MPL， 并以學(xué)習(xí)好的MPL作為決策規(guī)則進行分類過程.Xing等[48]于2008年較早地將基于前綴的思想應(yīng)用 在符號序列數(shù)據(jù)的早期分類問題中，并提出了 2種策略：序列分類規(guī)則（Sequential Classification Rule， SCR）和廣義序列決策樹（Generalized Sequential Decision Tree， GSDT）. SCR通過提取不同前綴空間 的不同特征，再依據(jù)特征的信息增益和早期性的效用指標(biāo)選擇前Z個特征作為特征集，并提出最佳搜 索策略修建特征枚舉樹，達到最小化預(yù)測代價的目的.而GSDT將特征集看作屬性，保證每個序列至 少有一個可以匹配的特征集，以此實現(xiàn)更早期的分類過程.

現(xiàn)有研究中，MPL的計算方法可以分為兩類：以反向最近鄰（Reverse Nearest Neighbors， RNNS） 為依據(jù)和借助標(biāo)記的后驗概率而構(gòu)造的決策規(guī)則.一旦測試樣本滿足MPL條件，那么早期分類模型 在分類時間點上有能力實現(xiàn)對該樣本的分類.

3.1.1 借助RNNS狀態(tài)

首先，先引入時間序列的RNNS定義.令P是包含W個時間序列樣本的有標(biāo)簽數(shù)據(jù)集，時間長度 為T ，在前綴空間記下，任一時間序列zG P *的RNNS定義為

RNNSt （x） = {x′ ∈ D|x ∈ NNSt （x′）}.

這里給出一個簡單的例子來加以說明.給定1個訓(xùn)練集D， T = 3， W = 4， “和句是標(biāo)簽，訓(xùn)練 集內(nèi)容如表1所示.

可以計算得出

RNNS1 （x） = RNNS2 （x） = RNNS3 （x） = {y} ，

RNNS1 （y） = RNNS2 （y） = RNNS3 （y） = {x} .

1-NN-Early框架[49]給出了時間序列;r的MPL計算方法，在T個前綴空間下，將第一個穩(wěn)定且與之 后時刻的RNNS狀態(tài)始終保持一致的時刻作為此時間序列的MPL值，在測試過程中，測試樣本心先 在訓(xùn)練集P中找到最近鄰，若滿足當(dāng)前時刻t不小于最近鄰的MPL值時，即可早期地分類測試樣本.

但上述MPL定義過于嚴苛，必須與某時刻及以后的RNNS保持一致，并且當(dāng)數(shù)據(jù)集樣本量過大 時，易存在過擬合現(xiàn)象，因此ECTS方法剛針對1-NN-Early的局限進行改進.為了實現(xiàn)時間序列分類 的早期性以此放松MPL定義，ECTS先求解訓(xùn)練集分簇后每簇的MPL值，再得到時間序列的MPL （r）. 但在簇^的MPL （5O求解時，ECTS要求簇5*從前綴空間開始RNNS需滿足完全穩(wěn)定，也即

MPL （S） = k，

RNNSr （S） = RNNSt （S） ，k < r < T.

隨之而后，又提出了 Relaxed ECTS模型[46]，即修改MPL （S）的計算方法，僅要求簇S的RNNS的子序 列保持穩(wěn)定即可.這樣就降低了簇的最小預(yù)測長度，提高了早期預(yù)測的時間.

Ma 等[50]提出的多變量早期時間序列分類模型（Multivariate Time Series Early Classification Based on PAA， MTSECP），基于中心序列（Center Sequence）和 PAA （Piecewise Aggregate Approximation） 的方法，將MTS轉(zhuǎn)換為UTS;再使用自下而上的單連接層次聚簇算法進行聚簇過程，并更新簇內(nèi)時間 序列MPL值，直至簇S內(nèi)所有序列MPL值不大于MPL （S）時，便停止迭代.

3.1.2借助后驗概率

除使用RNNS計算MPL外，一些研究人員還通過概率模型得到的后驗概率構(gòu)造多樣的決策規(guī) 則.這類方法的共同點是，先確定時間序列的MPL值，再確定變量的類判別性MPL.

有些決策規(guī)則僅依靠準確度閾值《151-53]和當(dāng)前時刻與T時刻的后驗概率比值進行比較，從而確定 時間序列的MPL值.Gupta等[52]采用高斯過程（Gaussian Process， GP）分類器，在定義時間序列 MPL（r）=t時，需滿足規(guī)則

ρt，c ? α · ρT ，c，

其中，Pt，c是t時刻真實標(biāo)簽為C的訓(xùn)練樣本的后驗概率值，且以“游戲比賽”的形象化方式，將準確度 和早期性作為運動員，生動刻畫了兩者的權(quán)衡或收益.ECDIRE （Early Classification Framework for Time Series Based on Class Discriminativeness and Reliability of Predictions）1511 以時間線的想法刻 畫每個標(biāo)簽c的“安全時刻”，這里的“安全時刻”可以理解為標(biāo)簽的最小預(yù)測長度或分類時間點，通過公式

AEa，c = α · AT ，c，

tc = min {ti ∈ e|?j > i， Atj ，c ? AEa，c}， e = {1， 2， · · · ， T}

進行計算.公式中，為T時刻標(biāo)簽為c的準確率，AEa，c為預(yù)想達到的準確度水平，tc是所學(xué)習(xí)到的 標(biāo)簽為C的安全點，由此可以看出，使用訓(xùn)練樣本得到的^時刻后的準確率均高于AEa，c .—旦測試樣 本達到預(yù)測標(biāo)簽的“安全時刻”和滿足訓(xùn)練的可靠性閾值，該樣本便可以被分配標(biāo)簽.Gupta團隊有僅 依靠準確度閾值a的早期策略[53]，也有將后驗概率的最大值maxi （內(nèi)）與第二大值max2 （內(nèi)）的差值考慮 在內(nèi)通過以下不等式

max1 （ρt） ? α · max1 （ρT ），

max1 （ρt） ? max2 （ρt） ? max1 （ρT ） ? max2 （ρT ）

確定MPL值.這表明t時刻的特征差異更明顯，且預(yù)測正確的概率要達到一定的準確率時，方可確定 時間序列的MPL值.特別地，文獻[53]和文獻[54]依據(jù)在交通領(lǐng)域存在數(shù)據(jù)采集速率不一致這一現(xiàn) 象所提出的框架和方法.

隨后，Gupta團隊也嘗試將早期時間序列分類應(yīng)用于人類行為識別領(lǐng)域.由于人類行為數(shù)據(jù)變量 之間存在高度相關(guān)性和依賴性，因此，依據(jù)相關(guān)性分數(shù)將變量重新按序排列[55]，借用偏序集的想法，選 擇相關(guān)變量的集合.訓(xùn)練過程中，F(xiàn)ECM （Fault-Tolerant Early Classification of MTS）引入效應(yīng)函數(shù)， 此效應(yīng)函數(shù)以優(yōu)化準確度和早期性二者為權(quán)衡.效應(yīng)函數(shù)通過公式為

其中，At表示前綴空間記時訓(xùn)練集樣本上使用GP分類器和fc-means聚簇算法獲得的準確率，E表 示分類的早期性.效應(yīng)值越高則代表當(dāng)前時刻能夠達到最佳的早期性與準確率之間的權(quán)衡.因此，時 間序列x的MPL定義為

MPL （x） = argmin{U （x [1， t]）} .

1?t?T

選取最高效應(yīng)值所對應(yīng)的時刻代表時間序列x的MPL值.

在多變量時間序列早期分類問題中，確定好時間序列MPL（x）值后，接下來進行基于變量的類判 別性MPL學(xué)習(xí)，如使用異常值檢驗算法后再取最大值記為類判別性MPL[52]，使用聚簇算法后取均 值[53]、取最大值[54]，也有選取最大的后驗概率比值和[45]等規(guī)則.表2總結(jié)了基于MPL的分類時間點確 定方法的特點.

基于MPL的方法思想簡單、易于理解，直接將原生時間序列數(shù)據(jù)作為輸入，但存儲和搜索整個數(shù) 據(jù)集使其具有較高的時空復(fù)雜度，這導(dǎo)致算法效率受限.如何更好地優(yōu)化時空復(fù)雜度，提高適用性還 有待進一步研究.

3.2基于Shapelet的確定方法

Gupta等和Douzal等成功地將時間序列特征思想應(yīng)用在時間序列分類領(lǐng)域，這便為許多學(xué)者研 究早期分類問題提供了嶄新的思路.由于Shapelet的想法簡單，在之后的一段時間里，它都是早期時 間序列分類領(lǐng)域的主流方法.其主要思想在于創(chuàng)建特征集（Bag of Features），作為早期預(yù)測的判斷標(biāo) 準.早些時候，研究者試圖挖掘完美的特征集[56]，致力于判別所有的時間序列，但事實證明這一想法是 不實際的;緊接著，研究者將注意力轉(zhuǎn)到挖掘有效的特征集.

在這里，特征S = {M，^c}，在學(xué)習(xí)距離閾值時，計算s和標(biāo)記為c的時間序列z的距離，相應(yīng)公式為

當(dāng)測試樣本到達時，計算特征^和測試樣本的距離d，若d不大于<5則分配特征^的標(biāo)簽c.此類早期 分類方法，對于給定的數(shù)據(jù)集，先提取所有可能的不同長度的特征序列，再進行優(yōu)質(zhì)特征的選擇.在進 行特征選擇時，主要歸納總結(jié)為兩種策略：借助效應(yīng)函數(shù)和聚簇算法.

3.2.1借助效應(yīng)函數(shù)

效應(yīng)函數(shù)可以作為衡量特征質(zhì)量的一種指標(biāo)，構(gòu)造不同表現(xiàn)形式的效應(yīng)函數(shù)，能夠體現(xiàn)特征本身 所隱含的價值信息.

文獻[57-58]使用相同的效應(yīng)函數(shù)，將其定義為關(guān)于特征S的精確度P （5O和加權(quán)召回率flw （5O的 調(diào)和平均數(shù)，通過進行計算，其中，P（S）代表特征S捕獲類別的判別能力.尤為注意的是，Rw（S）衡量了特征S的早期性和出現(xiàn)頻率.EDSC （Early Distinctive Shapelet Classification）[5M+算特征S的效應(yīng)值后，進行降序排 序，從高到低依次判別特征是否可以覆蓋訓(xùn)練集所有剩余的時間序列，直至覆蓋完畢后，停止特征集 的構(gòu)造過程，從而達到修剪特征集的目標(biāo).可以發(fā)現(xiàn)，EDSC通過特征選擇和滿足匹配的特征距離閾 值后，便可分配標(biāo)簽，但卻未考慮分類結(jié)果的可靠性或置信度.因此，Ghalwash等[58]提出帶有不確定 性估計的EDSC模型（MEDSC-U）. MEDSC-U與EDSC有兩點不同，一是在修剪特征集合的過程中， MEDSC-U不僅將當(dāng)前效應(yīng)值較高的特征加入特征集，而且把當(dāng)前相同效應(yīng)值的特征也加入進來，從 而增加選取特征的個數(shù)，豐富模型使得提高分類準確率;二是在分類過程中，MEDSC-U遵循的規(guī)則 也大不相同，首先測試樣本與所有選擇出的特征進行距離計算，再計算滿足要求且匹配特征的分類可 靠性，最終選取最大可靠性或最小不確定性的特征所對應(yīng)的標(biāo)記作為預(yù)測標(biāo)記.

一些學(xué)者[59-60]借助信息增益來完成有效特征集的選擇.REACT （Reliable EArly ClassificaTion）[59] 定義效應(yīng)函數(shù)為其中，F(xiàn)（辦）代表包含特征5·的訓(xùn)練集樣本的信息增益，^―⑶和^以⑶含義相似，參數(shù)^控制特 征的早期性和信息增益的相對重要性.為了避免挑選過多的冗余特征，特提出“等價類挖掘”思想，此 模型也適用于同時具有離散型變量和連續(xù)型變量的數(shù)據(jù)集.MSD （Multivariate Shapelets Detection）16。1 將基于特征的思想應(yīng)用在多變量時間序列早期分類中，先提取有相同起點維度和終點維度的多個多 變量特征，再為每個特征計算基于距離閾值的信息增益，最終以加權(quán)信息增益進行修剪和挑選必要的 特征.

指標(biāo)GEFM （Generalized Extended F-Measure）1611借鑒指標(biāo)巧分數(shù)的思想來構(gòu)建核心的特征集， 它是精確率、召回率和早期性的調(diào)和平均數(shù)，具體定義為其中，ω1 + ω2 + ω3 = 1. GEFM取值越大，代表特征5具有越優(yōu)質(zhì)的辨別特性.

3.2.2借助聚簇算法

在計算衡量特征質(zhì)量的指標(biāo)前，由于考慮到特征對分類過程的貢獻差異，因此一些學(xué)者借助聚簇 算法162-63]，過濾或修剪貢獻度較小的特征，使得在分類時特征更具有高效性和解釋性.IPED （Interpretable Patterns for Early Diagnostics）1621為了發(fā)現(xiàn)MTS中具有關(guān)聯(lián)性的變量，構(gòu)造優(yōu)化問題 進行求解，再對每個關(guān)聯(lián)變量的特征候選者聚簇為Z個組G為標(biāo)簽總數(shù)），在每組中選擇唯一的特征代 表，為分類階段提供特征依據(jù).MEShapelet （Multivariate Early Shapelet）1631計算每個特征候選者的時 間容忍度閾值，用于限制多變量特征的維度偏差，再使用聚簇算法后計算信息增益進而選擇最佳的特 征，使用決策樹進行分類過程，此框架適用于采樣速度不同的時間序列數(shù)據(jù)集中.

He等1641為MTS提出了一·個帶有可解釋性規(guī)則的早期分類框架（Confident Early Classification on Multivariate Time Series with Interpretable Rules，CECMR），這 一·規(guī)則使用局部極值和轉(zhuǎn)折點的 思想，類似于通過聚簇算法找到具有核心且關(guān)鍵的時刻：若時間序列$的局部極值點為z W，則需滿足 條件若時間序列X的轉(zhuǎn)折點為X [t]，可通過條件來確定.挖掘出解釋性規(guī)則后，估計每個規(guī)則的置信度從而構(gòu)造特征集.

同是應(yīng)用在 MTS 領(lǐng)域中，與 EPIMTS （Early Prediction on Imbalanced Multivariate Time Series）1611、 MSD、IPED 不同的是，MCFEC （Mining Core Feature for Early Classification）1651 考慮了不同變量特 征間的相關(guān)性，增加特征的可解釋性，但卻未考慮分類早期性的實現(xiàn).可以看出，基于Shapelet的時間 點確定方法主要圍繞特征提取和選擇的策略，有些方法并未涉及分類器的實現(xiàn).因此，表3仍按照分 類器實現(xiàn)進行簡要分類.

此類方法通過對原生時間序列進行特征提取和選擇，使得早期分類過程具有較強的可解釋性，相 比基于MPL的方法，減小了數(shù)據(jù)存儲的空間成本，但在特征選擇過程中，這類方法的計算成本較高.

3.3基于模型的確定方法

與基于MPL、基于Shapelet的方法不同，基于模型的確定方法主要思想可歸結(jié)為“兩步走”策略.

第一步使用判別式、生成式模型計算得到給定觀測下不同標(biāo)記所對應(yīng)的后驗概率，即得到后驗概率的 合理估計;第二步基于上述的后驗概率值，通過異常值檢測算法，停止規(guī)則等早期決策策略進行樣本 可靠性的核對和篩選.接下來，將從機器學(xué)習(xí)和深度學(xué)習(xí)領(lǐng)域的角度，主要闡述基于模型的早期分類 方法如何確定分類時間點.

3.3.1基于機器學(xué)習(xí)

在現(xiàn)有研究中，多數(shù)通過選取合適的數(shù)理模型，得到給定樣本下不同標(biāo)記的條件概率，分類器試 圖學(xué)習(xí)類別之間的決策邊界從而設(shè)計不同的決策規(guī)則或停止規(guī)則，以優(yōu)化預(yù)測的早期性和可靠性 之間的權(quán)衡.此外，一些現(xiàn)存方法167-681雖未將可靠性參數(shù)納入模型中，但仍提供了明顯的早期性.

Mori等[_]引人形式多樣的“停止規(guī)則”（Stopping Rule， SR），并構(gòu)造關(guān)于準確度和早期性的代價 函數(shù)（Cost Function， CF），以此訓(xùn)練時間序列的最優(yōu)預(yù)測時刻.他們根據(jù)分類器輸出的/個標(biāo)記對應(yīng) 的后驗概率值，構(gòu)造和當(dāng)前時刻i、最大后驗概率值maxi（pt）、最大與第二大后驗概率max2Oot）差值 有關(guān)的停止規(guī)則，定義為

其中，參數(shù)γ1 γ2 γ3 γ4 ∈ [?1， 1]，可通過優(yōu)化代價函數(shù)進而確定，且代價函數(shù)是早期性和準確度代價 的線性組合，具體形式為

CF1 = ∑x∈D（CF1 （x， SR1）） =x∑∈D（αCa （x， SR1） + （1 ? α） Ce （x， SR1））

其中，Ca代表使用O?1損失函數(shù)的準確度代價，Ce代表早期性代價，參數(shù)a G [0，1]調(diào)節(jié)準確度和早 期性代價的權(quán)重.隨后，又提出停止規(guī)則SR2，將/個后驗概率均考慮入內(nèi).SR2表示為

并且，將模型復(fù)雜度也作為代價函數(shù)CF2和CF3的影響因素，具體為

CF2 = ∑x∈D（αCa （x， SR1） + （1 ? α） Ce （x， SR1）） ? λ||γ||0，

CF3 = ∑x∈D（αCa （x， SR1） + （1 ? α） Ce （x， SR1）） ? λ||γ||xEV

一些學(xué)者在實現(xiàn)分類早期性時，提出新穎的“未來決策”觀點171-721，以長遠的眼光判斷當(dāng)前觀測序 列在未來是否會存在最佳預(yù)測時刻.兩者不同的是，Dachraoui等[71]尋找最佳時刻的代價函數(shù)時，采用 訓(xùn)練集聚簇后誤分類樣本A的期望損失加權(quán)和屄（x丄具體定義為

Et （xt） = ∑bk P （bk|xt）∑c ∑c? P （c|bk） Pt+τ （?c|c， bk） C （?c|c） + C （t + τ ），

其中，bkGB， B是簇的集合;參數(shù)TG（0，T-t），表示未來時刻和當(dāng)前時刻t的時間間隔;C（詠）表示 誤分類樣本的代價函數(shù);C（t + r）代表未來時刻預(yù)測時所消耗的時間等待成本.而Tavenard等[72]為降 低時空復(fù)雜度，舍棄聚類步驟，直接計算訓(xùn)練樣本的期望損失加權(quán)和，具體形式是

Et （xt） = ∑c P （c|xt）∑c? Pt （?c|c， xt） C（?c， c） + C （t）.

并且框架依舊具有適應(yīng)性和決策的未來性，提高了算法性能.

為提高分類準確率，提出了分類器“集成”思想[73-76]，并精心設(shè)計了分類器聚合過程.Ando等叫提 出并實現(xiàn)了由不同響應(yīng)間隔時間的SVM分類器組成的集成模型（Chronological Ensemble， CE），將構(gòu) 造集成分類器問題轉(zhuǎn)化為二次規(guī)劃問題，具體形式為

所需滿足的條件是其中，$表示所有訓(xùn)練數(shù)據(jù)上的平均松弛因子;是矩陣z在第〖時刻第&個取值，矩陣^表示預(yù)測 時間的0-1矩陣;心表示第個分類器的置信度閾值;懲罰參數(shù)Pk表示分類器fc的正則化因子，并使 用基于約束的cutting-plane迭代算法進行求解.集成分類器[74]根據(jù)前弱分類器的學(xué)習(xí)誤差率更新訓(xùn) 練樣本權(quán)重，希望誤差率高的樣本在后弱分類器中得到更多重視，如此反復(fù)進行，將多個弱分類器進 行整合得到最終的強學(xué)習(xí)器.為了實現(xiàn)早期預(yù)測的效果，在當(dāng)前迭代時刻的最終分類結(jié)果由有結(jié)果的 弱分類器的線性組合而確定，而無結(jié)果的弱分類器則被拋棄或不給予考慮.Hatami等在每個時刻 下構(gòu)建一對準確率最高且DF值最小的SVM分類器，其中DF值是兩個SVM分類器同時誤分類樣本 占總樣本數(shù)的比例，DF值越小，代表分類器間越具有豐富的多樣性，包含更多可識別特征進而體現(xiàn)分 類的早期性.與文獻[67]相同的是，TEASER （Two-tier Early and Accurate Series classifiER）[76]每隔 固定窗口大小也建立成對分類器（從分類器和主分類器），分別負責(zé)保證準確度和提高早期性，是“兩 步走”策略的經(jīng)典模型之一.在主分類器中，介于不平衡樣本可能導(dǎo)致模型的表現(xiàn)能力不佳這一擔(dān)憂， 因此使用單分類SVM模型.單分類SVM模型為正確分類的樣本構(gòu)造超球體，超球體的半徑越小即越 好，使得假陽性的樣本被劃分到超球體之外，優(yōu)化方程是

需滿足的條件為

|xi ? O| ? R + ξi， ξi > 0，

其中，超球體的球心為O，半徑為R， Xi是第i個時間序列樣本.在測試階段，從分類器的輸出作為主 分類器的輸入，判斷測試樣本是否落在超球體內(nèi)，進而給出決策.

也有其他機器學(xué)習(xí)模型應(yīng)用到早期分類問題中.當(dāng)輸入序列具有不確定性和不穩(wěn)定性時，使得在 估計模型參數(shù)時準確度有一定影響.Antonucci等|47]提出的基于HMM的不精確模型（iHMM）與HMM 模型的不同之處在于，計算狀態(tài)概率時設(shè)置了約束條件，使得狀態(tài)變量個數(shù)縮減.借用fc-NN算法的思 想，成功應(yīng)用于工廠故障檢測和定位[77]，但本質(zhì)上卻沒有考慮準確率和早期性之間的權(quán)衡.Li等[68]使 用泊松點過程模型（Dynamic Marked Point， DMP）[56]對時間動態(tài)變化這一特性進行建模，將連續(xù)空間 通過切片而離散化.由于人類行為[56]在時間上具有很大的相關(guān)性或依賴性，因此在文獻[68]基礎(chǔ)上， 增加使用部分觀測預(yù)測（Prediction of Partial Match， PPM）[56]的想法，在特征集中找到具有依賴性的 特征，從而避免等待無效特征的時間耗費，提高行為識別的早期性.

3.3.2基于深度學(xué)習(xí)

伴隨深度學(xué)習(xí)技術(shù)的快速發(fā)展，早期時間序列分類問題取得了突破性的進展，尤其在具有非平 穩(wěn)、非線性的金融時間序列中得以展現(xiàn)，它能夠挖掘出一些隱藏在數(shù)據(jù)中很難被發(fā)現(xiàn)的內(nèi)在規(guī)律，促 進了一些學(xué)者將深度學(xué)習(xí)框架應(yīng)用在早期分類領(lǐng)域中.

Martinez等[78]提出了一個端到端的強化學(xué)習(xí)智能體?????? 深度Q網(wǎng)絡(luò)（Deep Q-Network， DQN），

在此定義權(quán)衡準確性和早期性的獎勵函數(shù)，并適用于多種類型的時間序列，包括一元時間序列、多元 時間序列、符號時間序列.

文獻[79-80]均采用LSTM和CNN的混合模型：Huang等[79]應(yīng)用在MTS中，為實現(xiàn)較早地分配標(biāo) 簽，在全連接層將時域和頻域所提取的LSTM序列進行整合，再使用激活函數(shù)ReLU提取隱藏信息; 在最小化損失函數(shù)時[80]，特地將早期性考慮入內(nèi)，相應(yīng)公式為

La = 1 ? c?+， Le = tT ，

Lt = αLa + （1 ? α）Le.

在實驗中，設(shè)置較低的權(quán)重適用于低延遲項的懲罰.

Cheng等[67]使用深度神經(jīng)網(wǎng)絡(luò)，分別為人類復(fù)雜活動（Complex Activity， CA）和動作序列（Action Sequence， AS）構(gòu)建兩個獨立模型ASM （AS Model）和CAM （CA Model）.在真實數(shù)據(jù)集CA上，實驗結(jié) 果表明，與 LSTM、1-NN+DTW 和 MD+MPP （Multilevel-Discretized Marked Point-Process）方法相比， 他們提出的 SimRAD （Simultaneous Complex Activities Recognition and Action Sequence Discovering） 在預(yù)測準確度指標(biāo)上平均高出了 7.2%.表4為基于模型的分類時間點確定方法的總結(jié).

基于模型的方法具有較高的結(jié)構(gòu)化程度，相比于前兩類方法，應(yīng)用不同類型的分類時間點確定策 略使得早期性有所提升.但由于深度學(xué)習(xí)模型的“黑盒”特性，希望可以融合機器學(xué)習(xí)模型，增加分類 解釋性，以此推動早期時間序列分類領(lǐng)域的深度研究，也是未來重要的研究方向之一.表5是對上述 3類方法的總結(jié)和對比.

4應(yīng)用領(lǐng)域、數(shù)據(jù)集及評測指標(biāo)

近年來，早期時間序列分類在不同領(lǐng)域都受到了廣泛關(guān)注.與此同時，在該領(lǐng)域的研究活動中，高 質(zhì)量的公開數(shù)據(jù)集和統(tǒng)一的評價指標(biāo)至關(guān)重要，使得學(xué)者在相同數(shù)據(jù)集上進行不同模型的性能比較， 為進一步研究打下鋪墊.

4.1應(yīng)用領(lǐng)域

金融領(lǐng)域：以金融時間序列數(shù)據(jù)為載體的早期分類方法可用于解決諸多問題，例如，通過收集消 費者對多類金融產(chǎn)品的投訴聲音，以此改善金融市場的運作狀態(tài);預(yù)測企業(yè)在將來是否會出現(xiàn)財務(wù)困 境，判斷年度財務(wù)狀況是否健康，有利于幫助企業(yè)調(diào)整未來工作結(jié)構(gòu);根據(jù)真實成交量信息，預(yù)估該企 業(yè)是否存在財務(wù)欺詐行為等[81].

其他領(lǐng)域也有廣泛的應(yīng)用性.

（1）醫(yī)學(xué)檢測：心電圖時間序列是由心臟活動產(chǎn)生的電信號的時間序列，對重癥患者的心電圖數(shù) 據(jù)進行研究，從而降低心力衰竭和突發(fā)心臟病的發(fā)病概率[61，65，71];研究患者的病毒感染、對疾病的藥物 反應(yīng)和患者從疾病中的恢復(fù)狀況，達到降低疾病對患者損害的目的16°，62，821.

（2）智能交通：隨著交通設(shè)施的不斷完善和無人駕駛技術(shù)的成熟，早期分類問題對智能交通技術(shù) 的研究顯得尤為重要.研究人員通過在車輛內(nèi)外安裝傳感器來觀測駕駛員行為和外部路面環(huán)境，在惡 劣的天氣情況下，做出明智且及時的決策，增加駕車安全性[33，45，53—541.

（3）行為識別：分析由傳感器收集的人類行為數(shù)據(jù)，一方面有助于人們進一步了解自己的身體狀 態(tài)，促進培養(yǎng)健康的生活作息規(guī)律;另一方面能夠分析一些以用戶為中心的應(yīng)用識別不同的人類行為， 這些應(yīng)用包括手語研究[68]、身體姿態(tài)[56]、行為狀態(tài)[55]等.

4.2數(shù)據(jù)集

Kaggle是當(dāng)下所青睞的數(shù)據(jù)建模和數(shù)據(jù)分析競賽平臺，該平臺收集了用于企業(yè)和研究者的數(shù)據(jù)， 為統(tǒng)計學(xué)者和數(shù)據(jù)挖掘?qū)＜耶a(chǎn)生更好的模型.特別地，表6展示了 Kaggle金融領(lǐng)域熱度前五的數(shù)據(jù)集 信息，為研究者提供對比數(shù)據(jù)集.

但現(xiàn)有的早期時間序列分類文獻中采用科技金融領(lǐng)域中案例或數(shù)據(jù)較少.本文整理發(fā)現(xiàn)約八成 的參考文獻使用來自UCR數(shù)據(jù)庫的現(xiàn)有公開數(shù)據(jù)集，并統(tǒng)計了最為常見的五個公開數(shù)據(jù)集及其使用 的比例，如圖4所示.此外，在現(xiàn)有的早期時間序列分類模型的研究中，有些研究者從諸如無人駕駛、 基因檢測等實際應(yīng)用領(lǐng)域的問題出發(fā)而提出了具有創(chuàng)新性的方法與模型.由于隱私保護的原因，這部 分數(shù)據(jù)集未得到公開.

4.3評價指標(biāo)

由于時間序列早期分類本身是雙目標(biāo)問題，需要在準確率和早期性二者之間進行權(quán)衡.該領(lǐng)域常 用的評價指標(biāo)為巧分數(shù)、覆蓋率、平均FAvg分數(shù)等.

（1）巧分數(shù)（巧-score，巧）：該指標(biāo)將早期性（功和準確率（⑷的調(diào)和平均數(shù)用于度量，并且取值 越高，說明模型的表現(xiàn)能力越優(yōu)，具體形式為

（2）覆蓋率（Coverage Ratio， CCR）：定義為已分類樣本數(shù)占總樣本數(shù)#的比率，可表示為

其中，當(dāng)預(yù)測標(biāo)記為NA時，表明該樣本未被模型所識別或分類.

（3）平均4vg分數(shù)（Avg F-score， 4vg）：該指標(biāo)將所有標(biāo)簽的精確率（Precision，巧和召回率 （Recall，均的調(diào)和平均數(shù)的平均值作為評價指標(biāo)之一，同時結(jié)合早期性、覆蓋率進行綜合考量.具體 形式分別為

其中，c代表標(biāo)簽集.

5總結(jié)與展望

本文對時間序列分類時間點的確定方法進行了系統(tǒng)的分類和總結(jié)，并詳細介紹了每類中常被使 用的方法，對該領(lǐng)域近幾年出現(xiàn)的基于深度學(xué)習(xí)框架的早期分類方法進行了調(diào)研與總結(jié).除了對各類 方法的介紹外，也針對每類方法存在的問題進行了分析與評述.縱覽早期時間序列分類模型的發(fā)展歷 程，本文總結(jié)了一些未來可能的研究方向，具體如下.

（1）基于MPL的方法具有較高的時空復(fù)雜度，未來可結(jié)合解釋性，進而提升時間序列的空間利用率.

（2）特征選擇階段消耗了大量時間，提高算法效率是基于Shapelet的早期時間序列分類方法中值 得研究的方向之一.

（3）由于深度學(xué)習(xí)領(lǐng)域的快速發(fā)展，很多學(xué)者忽略了一些較為傳統(tǒng)的方法，導(dǎo)致深度學(xué)習(xí)框架和 傳統(tǒng)方法的割裂.希望未來將二者進行深度融合，在提高準確率和早期性的同時，也增加分類的可解 釋性.

在這項早期時間序列分類方法的研究工作中，我們期待有更多學(xué)者參與其中;也希望本文能夠?qū)?國內(nèi)基于時間序列的早期分類方法和科技金融領(lǐng)域的時間序列分析方法的研究提供一些啟發(fā)與幫助.

[參考文獻]

[1]KAO L J， CHIU C C， LU C J， et al. A hybrid approach by integrating wavelet-based feature extraction with MARS and SVR for stock index forecasting [J]. Decision Support Systems， 2013， 54（3）： 1228-1244.

[2]LEUNG M T， DAOUK H， CHEN A S， et al. Forecasting stock indices： A comparison of classification and level estimation models [J]. International Journal of Forecasting， 2000， 16（2）： 173-190.

[3 ] MORI U， MENDIBURU A， MIRANDA I M， et al. Early classification of time series using multi-objective optimization techniques [J]. Information Sciences， 2019， 492（3）： 204-218.

[4]馬超紅，翁小清.時間序列早期分類綜述[J].微型機與應(yīng)用，2016， 35（16）： 13-15.

[5]SANTOS T， KERN R. A literature survey of early time series classification and deep learning [C/OL]// SamI40 Workshop at i-KNOW'IG. [2021-07-02]. http：//ceur-ws.org/Vol-1793/paper4.pdf.

[6]GUPTA A， GUPTA H P， BISWAS B， et al. Approaches and applications of early classification of time series： A review [J]. IEEE Transactions on Artificial Intelligence， 2020， 1（1）： 47-61.

[7]ABANDA A， MORI U， LOZANO J A. A review on distance based time series classification [J]. Data Mining and Knowledge Discovery， 2018， 33： 378-412.

[8]WEI L， KEOGH E. Semi-supervised time series classication [C]// Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM， 2006： 748-753.

[9]原繼東，王志海，孫艷歌，等.面向復(fù)雜時間序列的近鄰分類器[J].軟件學(xué)報，2017， 28（1（1）： 3002-3017.

[10]JEONG Y S， JEONG M K， OMITAOMU O A. Weighted dynamic time warping for time series classification [J]. Pattern Recognition， 2011， 44（9）： 2231-2240.

[11]BERNDT D J， CLIFFORD J. Using dynamic time warping to find patterns in time series [C]// Proceedings of the 3rd International Conference on Knowledge Discovery and Data Mining. AAAI， 1994： 359-370.

[12]CHEN Y P， KEOGH E， HU B， et al. The UCR time series classication archive [EB/OL] .（2015-07-1（5） [2021-07-21]. https：//www.cs.ucr.edu/～eamonn/time_series_data/.

[13]LINES J， BAGNALL A. Time series classification with ensembles of elastic distance measures [J] . Data Mining and Knowledge Discovery， 2015， 29（3）： 565-592.

[14]XI X P， KEOGH E， SHELTON C， et al. Fast time series classification using numerosity reduction [C] // Proceedings of the 23rd International Conference on Machine Learning. 2006： 1033-1040.

[15]ESLING P， AGON C. Time-series data mining [J]. ACM Computing Surveys， 2012， 45（1）： 1-34.

[16]XING Z Z， PEI J， KEOGH E. A brief survey on sequence classification [J]. ACM SIGKDD Explorations Newsletter， 2010， 12（1）： 4048.

[17]WANG X Y， MUEEN A， DING H， et al. Experimental comparison of representation methods and distance measures for time series data [J]. Data Mining and Knowledge Discovery， 2013， 26（2）： 275-309.

[18]CHEN Y P， HU B， KEOGH E， et al. DTW-D： Time series semi-supervised learning from a single example [C] // Proceedings of the 19th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM， 2013： 383-391.

[19]DING H， TRAJCEVSKI G， SCHEUERMANN P， et al. Querying and mining of time series data： Experimental comparison of representations and distance measures [J]. VLDB Endowment， 2008， 1（2）： 1542-1552.

[20]胡蓉.多輸出支持向量回歸及其在股指預(yù)測中的應(yīng)用[J].計算機技術(shù)與發(fā)展，2007（10）： 226-229.

[21]張倩倩，林天華，祁旭陽，等.基于機器學(xué)習(xí)的股票預(yù)測研究綜述[J].河北省科學(xué)院學(xué)報，2020， 37（4）： 15-21.

[22]TAY F E H， CAO L J. Modified support vector machines in financial time series forecasting [J]. Neurocomputing， 2002， 48（1/2/3/（4）： 847-861.

[23]李翔宇，李瑞興，曾燕清.基于改進核函數(shù)的支持向量機時間序列數(shù)據(jù)分類[J].信陽農(nóng)林學(xué)院學(xué)報，2021， 31（1）： 121-126.

[24]JALALIAN A， CHALUP S K. GDTW-P-SVMs： Variable-length time series analysis using support vector machines [J]. Neurocomputing， 2013， 99（1）： 270-282.

[25]KATE R J. Using dynamic time warping distances as features for improved time series classification [J] . Data Mining and Knowledge Discovery， 2015， 30（2）： 283-312.

[26]PANIGRAHI S S， MANTRI J K. A text based Decision Tree model for stock market forecasting [C]// Proceedings of the 2015 International Conference on Green Computing and Internet of Things （ICGCIoT）. 2015： 405-411.

[27]YAMADA Y， SUZUKI E， YOKOI H， et al. Decision-tree induction from time-series data based on a standard-example split test [C]// Proceedings of the 20th International Conference on International Conference on Machine Learning. 2003： 840-847.

[28]DOUZAL A， AMBLARD C. Classification trees for time series [J]. Pattern Recognition， 2012， 45（3）： 1076-1091.

[29]施沫寒，王志海.一種基于時間序列特征的可解釋步態(tài)識別方法[J].中國科學(xué)：信息科學(xué)，2020， 50（3）： 438-460.

[30]徐雷，WEBB G I， PETITJEAN F，等.基于動態(tài)集成決策樹的多類別時間序列分類模型[J].計算機應(yīng)用研究，2018， 35（6）： 1712-1715.

[31]王燕，郭元凱.改進的XGBoost模型在股票預(yù)測中的應(yīng)用[J].計算機工程與應(yīng)用，2019， 55（20）： 202-207.

[32]ANDERSSON J O. The new foundations of evolution： on the tree of life [J]. Systematic Biology， 2010， 60（1）： 114-115.

[33]HENDRIK J， MURPHY M， ONSLOW T. Classification trees as a tool for operational avalanche forecasting on the Seward Highway， Alaska [J]. Cold Regions Science and Technology， 2014， 97： 113-120.

[34]LIU G， WANG X J， LI R F. Multi-scale RCNN model for financial time-series classication [EB/OL]. （2019-11-2（1） [2021-07-02]. https：//arxiv.org/pdf/1911.09359.pdf.

[35]SUTSKEVER I， VINYALS O， LE Q V. Sequence to sequence learning with neural networks [C]// Proceedings of the 27th International Conference on Neural Information Processing Systems - Volume 2. 2014： 3104-3112.

[36]SZEGEDY C， LIU W， JIA Y Q， et al. Going deeper with convolutions [C] // 2015 IEEE Conference on Computer Vision and Pattern Recognition （CVPR）. IEEE， 2015： 1-9. DOI： 10.1109/CVPR.2015.7298594.

[37]CUI Z C， CHEN W L， CHEN Y X. Multi-scale convolutional neural networks for time series classification [EB/OL]. （2016-032（2） [2021-07-02]. https：//arxiv.org/pdf/1603.06995v4.pdf.

[38]Z^BIK M， KORYTKOWSKI M， ANGRYK R， et al. Convolutional neural networks for time series classification [J]. Journal of Systems Engineering and Electronics， 2017， 28（1）： 162-169.

[39]WANG Z G， YAN W Z， OATES T. Time series classification from scratch with deep neural networks： A strong baseline [C]// 2017 International Joint Conference on Neural Networks （IJCNN） . IEEE， 2017： 1578-1585.

[40]ULYANOV D， VEDALDI A， LEMPITSKY V. Instance normalization： The missing ingredient for fast stylization [EB/OL]. （2016-0727） [2021-07-02]. https：//arxiv.org/pdf/1607.08022v3.pdf.

[41]MEHDIYEV N， LAHANN J， EMRICH A， et al. Time series classification using deep learning for process planning： A case from the process industry [J]. Procedia Computer Science， 2017， 114： 242-249.

[42]MALHOTRA P， TV V， VIG L， et al. TimeNet： Pre-trained deep recurrent neural network for time series classification [C]// 25th European Symposium on Artificial Neural Networks， Computational Intelligence and Machine Learning. 2018： 607-612.

[43]RAJAN D， THIAGARAJAN J. A generative modeling approach to limited channel ECG classification [C]// 2018 40th Annual International Conference of the IEEE Engineering in Medicine and Biology Society （EMBC）. IEEE， 2018： 2571-2574.

[44]包振山，郭俊南，謝源，等.基于LSTMG-GA的股票價格漲跌預(yù)測模型[J].計算機科學(xué)，2020， 47（1）： 467-473.

[45]GUPTA A， GUPTA H P， BISWAS B， et al. An early classification approach for multivariate time series of on-vehicle sensors in transportation [J]. IEEE Transactions on Intelligent Transportation Systems， 2020， 21（1（2）： 5316-5327.

[46]XING Z Z， PEI J， PHILIP S Y. Early classification on time series [J]. Knowledge and Information Systems， 2012， 31（1）： 105-127.

[47]ANTONUCCI A， SCANAGATTA M， MAUA D D， et al. Early classification of time series by hidden Markov models with set-valued parameters [C] // Proceedings of the NIPS Time Series Workshop. 2015： pp 1-5.

[48]XING Z Z， PEI J， DONG G Z， et al. Mining sequence classifiers for early prediction [C] // SIAM International Conference on Data Mining. 2008： 644-655.

[49]XING Z Z， PEI J， YU P S. Early prediction on time series： A nearest neighbor approach [C]// Proceedings of the 21st International Jont Conference on Artifical Intelligence. 2009： 1297-1302.

[50]MA C H， WENG X Q， SHAN Z N. Early classification of multivariate time series based on piecewise aggregate approximation [C]// International Conference on Health Information Science， HIS 2017， Lecture Notes in Computer Science， vol 10594. Cham： Springer， 2017： 81-88.

[51]MORI U， MENDIBURU A， KEOGH E， et al. Reliable early classification of time series based on discriminating the classes over time [J]. Data Mining and Knowledge Discovery， 2017， 31（1）： 233-263.

[52]GUPTA A， PAL R， MISHRA R， et al. Game theory based early classification of rivers using time series data [C]// 2019 IEEE 5th World Forum on Internet of Things （WF-IoT）. IEEE， 2019： 686-691.

[53]GUPTA A， GUPTA H P， DUTTA T. Early classification approach for multivariate time series using sensors of different sampling rate [C]// 2019 16th Annual IEEE International Conference on Sensing， Communication， and Networking （SECON）. IEEE， 2019： 1-2. DOI： 10.1109/SAHCN.2019.8824960.

[54]GUPTA A， GUPTA H P， BISWAS B， et al. A divide-and conquer -based early classification approach for multivariate?????? time series with

different sampling rate components in IoT [J] . ACM Transactions on Internet of Things， 2020， 1（2）： 1-21.

[55]GUPTA A， GUPTA H P， BISWAS B， et al. A fault-tolerant early classification approach for human activities using multivariate time series [J]. A fault-tolerant early classification approach for human activities using multivariate time series， 2021， 20（5）： 1747-1760.

[56]LI S， LI K， FU Y. Early recognition of 3D human actions [J] . ACM Transactions on Multimedia Computing， Communications， and Applications， 2018， 14（1）： 1-20.

[57]XING Z Z， PEI J， YU P S， et al. Extracting interpretable features for early classification on time series [C]// Proceedings of the 2011 SIAM International Conference on Data Mining （SDM）. SIAM， 2011： 247-258.

[58]GHALWASH M F， RADOSAVLJEVIC V， OBRADOVIC Z. Utilizing temporal patterns for estimating uncertainty in interpretable early decision making [C] //Proc SIGKDD， 2014： 402-411.

[59]LIN Y F， CHEN H H， TSENG V S， et al. Reliable early classification on multivariate time series with numerical??????? and categorical attributes [C] // Advances in Knowledge Discovery and Data Mining， PAKDD 2015， Lecture Notes in Computer Science，? vol 9077. Cham： Springer， 2015： 199-211.

[60]GHALWASH M F， OBRADOVIC Z. Early classification of multivariate temporal observations by extraction of interpretable shapelets [J]. BMC Bioinformatics， 2012， 13： Article number 195.

[61]HE G L， DUAN Y， QIAN T Y， et al. Early prediction on imbalanced multivariate time series [C]// Proceedings of the 22nd ACM International Conference on Information & Knowledge Management. ACM， 2013： 1889-1892.

[62]GHALWASH M F， RADOSAVLJEVIC V， OBRADOVIC Z. Extraction of interpretable multivariate patterns for early diagnostics [C]// 2013 IEEE 13th International Conference on Data Mining. IEEE， 2013： 201-210.

[63]ZHAO L， LIANG H Y， YU D M， et al. Asynchronous multivariate time series early prediction for ICU transfer [C]// Proceedings of the 2019 International Conference on Intelligent Medicine and Health. ACM， 2019： 17-22.

[64]HE G L， ZHAO W， XIA X W. Confidence-based early classification of multivariate time series with multiple interpretable rules [J] . Pattern Analysis and Applications， 2020， 23： 567-580.

[65]HE G L， DUAN Y， ZHOU G F， et al. Early classification on multivariate time series with core features [C]// Database and Expert Systems Applications， DEXA 2014， Lecture Notes in Computer Science， vol 8644. Cham： Springer， 2014： 410-422.

[66]NG A Y， JORDAN M I. On discriminative vs. generative classifiers： A comparison of logistic regression and naive bayes [C]// NIPS， 2002： 841-848.

[67]CHENG W H， ERFANI S M， ZHANG R， et al. Predicting complex activities from ongoing multivariate time series [C] // Proceedings of the 27th International Joint Conference on Artificial Intelligence. ACM， 2018： 3322-3328.

[68]LI K， LI S， FU Y. Early classification of ongoing observation [C] // 2014 IEEE International Conference on Data Mining. IEEE， 2014： 310-319.

[69]MORI U， MENDIBURU A， DASGUPTA S， et al. Early classification of time series by simultaneously optimizing the accuracy and earliness [J]. IEEE Transactions on Neural Networks and Learning Systems， 2017， 29（10）： 4569-4578.

[70]MORI U， MENDIBURU A， DASGUPTA S， et al. Early classification of time series from a cost minimization point of view [C]// Proceedings of the NIPS Time Series Workshop. 2015： 1-5.

[71]DACHRAOUI A， BONDU A， CORNU'EJOLS A. Early classification of time series as a non myopic sequential decision making problem [C] // Machine Learning and Knowledge Discovery in Databases， ECML PKDD 2015， Lecture Notes in Computer Science， vol 9284. Cham： Springer， 2015： 433-447.

[72]TAVENARD R， MALINOWSKI S. Cost-aware early classification of time series [C]// Machine Learning and Knowledge Discovery in Databases， ECML PKDD 2016， Lecture Notes in Computer Science， vol 9851. Cham： Springer， 2016： 632-647.

[73]ANDO S， SUZUKI E. Minimizing response time in time series classification [J]. Knowledge and Information Systems， 2016， 46（2）： 449-476.

[74]GONZALEZ C J A， DIEZ J J R. Boosting interval-based literals： Variable length and early classification [C]// Series in Machine Perception and Artificial Intelligence： Volume 83， Data Mining in Time Series and Streaming Databases. Singapore： World Scientific Publishing Co Pte Ltd， 2004： 149-171.

[75]HATAMI N， CHIRA C. Classifiers with a reject option for early time-series classification [C]//2013 IEEE Symposium on Computational Intelligence and Ensemble Learning （CIEL）. IEEE， 2013： 9-16.

[76]SCHAFER P， LESER U. Teaser： Early and accurate time series classification [J]. Data Mining and Knowledge Discovery， 2020， 34： 1336-1362.

[77]BREGON A， SIMON M A， RODRIGUEZ J J， et al. Early fault classification in dynamic systems using case-based reasoning [C]// Current Topics in Artificial Intelligence， CAEPIA 2005， Lecture Notes in Computer Science， vol 4177. Berlin： Springer， 2006： 211-220.

[78]MARTINEZ C， PERRIN G， RAMASSO E， et al. A deep reinforcement learning approach for early classification of time series [C]// 2018 26th European Signal Processing Conference （EUSIPCO）. IEEE， 2018： 2030-2034.

[79]HUANG H S， LIU C L， TSENG V S. Multivariate time series early classification using multi-domain deep neural network [C]// 2018 IEEE 5th International Conference on Data Science and Advanced Analytics （DSAA）. IEEE， 2018： 90-98.

[80]RU6WURM M， LEFEVRE S，COURTY N， et al. End-to-end learning for early classification of time series [EB/OL]. （2019-0130） [2021-07-02]. https：//arxiv.org/pdf/1901.10681.pdf.

[81]Kaggle Datssets [EB/OL]. [2021-07-02]. https：//www.kaggle.com/datasets.

[82]GHALWASH M F， RAMLJAK D， OBRADOVIC Z. Early classification of multivariate time series using a hybrid hmm/svm model [C] // 2012 IEEE International Conference on Bioinformatics and Biomedicine. IEEE， 2012： 1-6. DOI： 10.1109/BIBM.2012.6392654.

（責(zé)任編輯：李藝）