馬超紅，翁小清
　　（河北經(jīng)貿(mào)大學(xué) 信息技術(shù)學(xué)院，河北 石家莊 050061）

       摘要：在總結(jié)了近年來關(guān)于時間序列早期分類相關(guān)文獻(xiàn)和相關(guān)研究進(jìn)展的基礎(chǔ)上，對參考文獻(xiàn)中的學(xué)術(shù)觀點(diǎn)、分類方法進(jìn)行了比較歸類，內(nèi)容涵蓋了時間序列原始數(shù)據(jù)的早期分類，時間序列早期分類的特征提取與選擇、評估方法，早期分類構(gòu)造模型等方面，為研究者了解最新的時間序列早期分類研究動態(tài)、新技術(shù)、發(fā)展趨勢提供了參考。
　　關(guān)鍵詞：時間序列；早期分類；特征提取與選擇　　

0引言
　　時間序列在狹義上是指按時間順序有次序的一組數(shù)據(jù)，而廣義上任何實(shí)值型的有次序的序列都可以當(dāng)作時間序列來處理。時間序列分類被廣泛應(yīng)用在醫(yī)學(xué)診斷、災(zāi)害預(yù)測、入侵檢測、過程控制、道路交通等生活中的方方面面。而在很多領(lǐng)域中越早做出分類對于指導(dǎo)決策越有利，時間序列的早期分類應(yīng)運(yùn)而生，并在一些時間敏感的應(yīng)用領(lǐng)域至關(guān)重要，例如健康信息學(xué)、災(zāi)害預(yù)測、入侵檢測、股市行情預(yù)測等領(lǐng)域。
　　時間序列早期分類即針對時間序列數(shù)據(jù)盡早地做出預(yù)測，并滿足預(yù)期的預(yù)測質(zhì)量(準(zhǔn)確率)。換句話說，在滿足一個給定的最小的準(zhǔn)確率情況下，早期分類嘗試著優(yōu)化分類的早期性，而不是像其他一般分類方法那樣只追求最大化準(zhǔn)確率［1］。
　　時間序列的早期分類方法大致分為三類：基于原始數(shù)據(jù)、基于特征和基于模型的分類方法。
1基于原始數(shù)據(jù)的時間序列早期分類
　　時間序列的早期分類是近幾年逐漸開始研究的，Xing Zhengzheng等人［2］在2008年對序列數(shù)據(jù)的早期預(yù)測進(jìn)行了研究，提出了SCR(Sequential Classification Rule)方法和GSDT(Generalized Sequential Decision Tree)方法。SCR挖掘序列分類規(guī)則構(gòu)造分類器，并根據(jù)早期預(yù)測效應(yīng)值在序列枚舉樹中進(jìn)行剪枝來選擇特征并構(gòu)造規(guī)則。GSDT采用分治策略構(gòu)造分類模型，在序列特征集中選擇分類屬性，確保訓(xùn)練集中的每條序列數(shù)據(jù)至少包含一條所選的屬性。SCR和GSDT適用于符號序列(Categorical Sequence)，而時間序列是連續(xù)數(shù)據(jù)，所以在應(yīng)用于時間序列早期識別時需要對時間序列進(jìn)行離散化。
　　Xing Zhengzheng等人［34］在2009提出將1NN分類器用于時間序列的早期分類，提出了最小預(yù)測長度(Minimum Prediction Length, MPL)的概念和一種時間序列早期分類方法（Early Classification on Time Series，ECTS)，ECTS方法在1NN方法有效的情況下既能保證分類準(zhǔn)確率，又能實(shí)現(xiàn)早期分類。Xing Zhengzheng等人還提出了Fixed 1NN分類器，即選用固定長度的MPL，適用于2class問題，同時也改進(jìn)了ECTS，提出了Relaxed ECTS，通過relaxed MPL來避免在原ECTS方法下由于處于決策邊界而沒有被分類的時間序列，從而提高了分類器的整體穩(wěn)定性。
　　1NN早期分類器已經(jīng)取得了較好的研究進(jìn)展，在實(shí)現(xiàn)早期分類的同時其準(zhǔn)確度可以與全長序列1NN分類器相媲美。但在一些領(lǐng)域如醫(yī)學(xué)、股市等，早期分類的可解釋性十分重要，有助于用戶更加信任早期分類的結(jié)果，并做出相應(yīng)的決策。
2基于特征的時間序列早期分類
　　基于可解釋性特征的早期分類，目前的方法大都是分為三個階段，即特征提取、特征選擇，最后再將特征用于分類。早期分類中提取的具有可解釋性的特征稱為shapelet［1］，通俗地講是時間序列的子序列，某種意義上最大程度地代表某一類的特性, shapelet f=(s,δ,c)其中s表示時間序列，f是s的某一子序列，δ表示距離閾值，c表示s所屬的類標(biāo)號。即如果某一時間序列s′與f的距離小于δ，則判定s′的類別標(biāo)號為c。
　　Xing Zhengzheng等人［1］在2011年提出在早期分類中提取具有可解釋性的特征(Local Shapelets)。針對單變量時間序列，提出了Best match distance(BMD)和BMDlists的概念，并分別使用核密度估計方法(Kernel Density Estimation)和切比雪夫不等式(Chebyshev′s Ineqaulity)來學(xué)習(xí)local shapelet f=(s, δ, c)中的距離閾值。在選擇用于分類的local shapelets時，通過計算每一個shapelets的效用值Utility來進(jìn)行排序選擇，計算方法如下：

　　　提取local shapelet的計算量非常大，對于大數(shù)據(jù)集則計算時間更長。盡管參考文獻(xiàn)［1］中也提出了加速的技術(shù)，計算BMD-lists時，在不同的local shapelets中間共享計算結(jié)果，但降低其計算復(fù)雜度仍然是一個有待研究的問題。提取local shapelets 的方法可用于1NN分類方法無效的情況下。
　　在多變量時間序列早期分類方面，GHALWASH M F等［5］在2012年提出了一種多變量Shapelets檢測(Multivariate Shapelets Detection, MSD)方法。該方法采用多變量信息增益選取δ值，在特征選擇階段運(yùn)用加權(quán)信息增益來計算shapelets的效應(yīng)值，計算公式如下：

　　He Guoliang等人［67］在2013年針對多變量時間序列早期分類的可解釋性，提出了一種挖掘核心特征的方法(Mining Core Feature for Early Classification，MCFEC)，通過實(shí)驗(yàn)證明，MCFEC效果比information gain［8］、greedy method［6］等其他方法要好。MCFEC方法用來獲得具有區(qū)別性且早期的shapelets，并使用提取出的核心特征構(gòu)造MCFECRules分類器和MCFECQBC分類器。MCFECRules在核心特征中選擇可用于早期分類的一致規(guī)則來構(gòu)造基于規(guī)則的分類器；MCFECQBC是基于投票選擇(query by committee)來進(jìn)行分類。特征提取階段采用的是通用方法，將每一個訓(xùn)練樣本中滿足長度在minL和maxL之間的子序列提取出來組成特征候選集；在特征選擇階段，不同于先前對整體的候選集進(jìn)行排序的方法。首先采用Silhouette Index將候選集中屬于同一變量類標(biāo)號的特征進(jìn)行聚類，形成若干簇，基于compactnessseparation 度量將候選shapelets動態(tài)地歸入最近的簇，另外不同于先前的多變量時間序列早期分類提取的shapelets起點(diǎn)必須相同［5］，MCFEC所提取的各個變量shapelets的起始點(diǎn)和結(jié)束點(diǎn)可以不同；運(yùn)用Fmeasure方法選取距離閾值δ，公式如下：        

　　然后在形成的每一個簇中運(yùn)用GEFM方法評估特征質(zhì)量并進(jìn)行排序，從中選出核心特征，該方法考慮了不平衡性，對于稀有但具有區(qū)別性的類核心特征也能選出。GEFM包含對Earliness、Precision、Recall三者的加權(quán)。GEFM的計算公式為：

　　同時He Guoliang等人［7］在2013年針對不平衡時間序列的早期預(yù)測也進(jìn)行了相應(yīng)研究，提出了EPIMTS(Early Prediction on Imbalanced Multivariate Time Series)方法。在構(gòu)造訓(xùn)練集時采用欠抽樣方法來處理不平衡數(shù)據(jù)集。
　　目前大部分方法是針對數(shù)值屬性進(jìn)行研究，LIN Y F等人［9］在2015年針對數(shù)值和符號屬性(Numerical and Categorical Attributes)的多變量時間序列進(jìn)行了研究，提出了REACT方法。該方法使用shapelets生成器挖掘等價類(Equivalence Classes Mining)，從多變量時間序列中成功地提取了符號序列的特征，并且考慮了數(shù)據(jù)集的不平衡問題，采用基于類別比例的子集聚類,評估方案采用平均fscore，如下：

3早期分類器評估方案及現(xiàn)有方法總結(jié)
　　時間序列x={(t1,x1),(t2,x2),…,(tL,xL)}的長度為L，且每一個實(shí)值{xj∈［1,L］}對應(yīng)一個時間點(diǎn){tj∈［1,L］}，訓(xùn)練集中的數(shù)據(jù)為{(xi,ci)|i∈［1,N］}，其中xi為一條時間序列，ci為其對應(yīng)的類標(biāo)號(ci∈C)，C是類標(biāo)號的有窮集合［10］。早期分類即在完全輸入xj前預(yù)測其類標(biāo)號，所以在早期分類中有兩個沖突的目標(biāo)：早期性和可靠性。早期性即盡可能早地對不完全輸入序列進(jìn)行預(yù)測；可靠性即分類器輸出的準(zhǔn)確率問題［11］。DACHRAOUI A等人［11］在2015年提出在多個數(shù)據(jù)集上對不同的早期分類器采用統(tǒng)計檢驗(yàn)的方法(威爾克森符號秩檢驗(yàn)Wilcoxon signedrank和帕累托最優(yōu)Pareto Optimum)進(jìn)行評估。
　　另外如何對早期分類的兩個指標(biāo)進(jìn)行權(quán)衡，DACHRAOUI A等人［12］在2015年將時間序列早期分類視為非近視的序貫決策樹問題，采用通用順序元算法來實(shí)現(xiàn)早期性和可靠性之間的權(quán)衡。
　　GHALWASH M F等人［13］在2014年針對可解釋性早期分類方法的不確定性估計提供了一種簡單有效的方法。沒有采用直接估計不確定性的方法，而是將一個時間序列分類c的不確定性定義為：U(c)=1-C(c)，其中C(c)是分類為類c的置信度。同時對EDSC進(jìn)行了修正，提出了MEDSCU(Modified EDSC with Uncertainty estimates)方法。
　　對于shapelet f=(s, δ, c)中距離閾值δ的計算有以下幾種方法：核密度估計函數(shù)、切比雪夫不等式、信息增益、Quality(Fβ-measure)。特征提取導(dǎo)致features存在冗余，且不具備代表性，特征候選集數(shù)量較大，所以特征選擇階段對候選集進(jìn)行縮減，主要思路為運(yùn)用Utility Score 方法對shapelets排序，選取排序第一的shapelet，并將其覆蓋的序列在訓(xùn)練集中刪除，再選取排序第二的shapelet，重復(fù)上述步驟，直到覆蓋了訓(xùn)練集中的所有時間序列。目前大致有以下幾種指標(biāo)用于候選shapelet的排序：Utility(f)、GEFM(f)、加權(quán)信息增益、Fmeasure(f)。
　　另外,除基于原始數(shù)據(jù)和特征的分類方法之外，GHALWASH M F等人［14］在2012年針對多變量時間序列的分類構(gòu)造了早期分類模型(Early Classification Model, ECM),其中集成了隱馬爾科夫模型和支持向量機(jī)模型。盡管在相同數(shù)據(jù)集上分類結(jié)果的平均準(zhǔn)確率較其他方法偏低，但ECM僅用了整個時間序列的40%。
4時間序列早期分類的應(yīng)用
　　在早期診斷方面，GHALWASH M F等人［12］在2015年提取可解釋性的多變量模式(Interpretable Patterns for Early Diagnostics, IPED)來實(shí)現(xiàn)時間序列早期分類。首先將時間序列數(shù)據(jù)轉(zhuǎn)化為二元矩陣(binary matrix)，然后運(yùn)用凸優(yōu)化方法在矩陣中提取多變量模式，并采用混合整數(shù)離散優(yōu)化方法來降低時間序列維度，最后將具有可解釋性的多變量模式用于臨床診斷。
　　在氣體識別方面，HATAMI N等人［15］在2013年基于帶有拒絕選項的一組連續(xù)分類器(Classifiers With a Reject Options, CWRO)，提出了一種時間序列早期分類的模型，并成功應(yīng)用發(fā)明了新型電子鼻——Forefront-Nose。第一個分類器利用一小部分可利用的信號對氣體的類型作出決策，第二個分類器利用新的一部分時間序列信號作出決策，分配一個可信的標(biāo)簽或者傳遞給下一分類器，迭代上述過程直到某個分類器分配了足夠可信的標(biāo)簽或者延遲分類的代價太大。
　　DACHRAOUI A等人［16］在2013年將時間序列的早期分類應(yīng)用于個人電力消費(fèi)(individual electricity consumption)。實(shí)驗(yàn)用的數(shù)據(jù)集是Irish CER提供的6 000個家庭在500天內(nèi)，抽樣間隔為30分鐘的家庭電力消費(fèi)數(shù)據(jù)。
5結(jié)論
　　時間序列的早期分類在醫(yī)療和健康信息學(xué)、工業(yè)生產(chǎn)管理、安全管理、災(zāi)害預(yù)測等重要領(lǐng)域都具有廣泛的應(yīng)用，目前已經(jīng)有了很大的研究進(jìn)展，但是仍然有很多需要研究的問題。
　　多變量時間序列的早期分類在時間序列挖掘中是一個研究熱點(diǎn)，由于它的多變量性和不同組成部分的序列長度可能不同，以及不同變量之間可能存在關(guān)聯(lián)性，很難用傳統(tǒng)的數(shù)據(jù)挖掘算法來對多變量時間序列進(jìn)行處理，因此將會是一個研究熱點(diǎn)［17］。在具體應(yīng)用中，存儲的時間序列以非?？斓乃俣仍谠鲩L，目前的分類方法大多是基于小型的數(shù)據(jù)集，所以針對大數(shù)據(jù)集的早期分類將是一個難點(diǎn)，時間序列每時每刻都在隨著時間變化更新，屬于流數(shù)據(jù)［1819］，對于流數(shù)據(jù)的數(shù)據(jù)挖掘，如何提高其分類精度同時實(shí)現(xiàn)早期分類將會是一個研究熱點(diǎn)。另外在基于模型的分類方法研究較少，值得今后進(jìn)一步研究。
　　參考文獻(xiàn)
　?。?］ Xing Zhengzheng, Pei Jian, YU P S, et al. Extracting interpretable features for early classification on time series［C］.SDM, 2011: 247258.
　?。?］ Xing Zhengzheng, Pei Jian, Dong Guozhu, et al. Mining Sequence Classifiers for Early Prediction［C］.SDM, 2008: 644655.
　?。?］ Xing Zhengzheng, Pei Jian, YU P S. Early classification on time series［J］. Knowledge and information systems, 2012, 31(1): 105127.
　?。?］ Xing Zhengzheng, Pei Jian, YU P S. Early prediction on time series: a nearest neighbor approach［C］.IJCAI, 2009: 12971302.
　　［5］ GHALWASH M F, OBRADOVIC Z. Early classification of multivariate temporal observations by extraction of interpretable shapelets［J］. BMC Bioinformatics, 2012, 13(1): 112.
　?。?］ He Guoliang,Duan Yong, Zhou Guofu, et al. Early classification on multivariate time series with core features［C］.Database and Expert Systems Applications. Springer International Publishing, 2014: 410422.
　?。?］ He Guoliang,Duan Yong, Peng Rong, et al. Early prediction on imbalanced multivariate time series［C］.Proceedings of the 22nd ACM International Conference on Conference on Information & Knowledge Management. ACM, 2013: 18891892.
　?。?］ HE G,DUAN Y, PENG R, et al. Early classification on multivariate time series［J］. Neurocomputing, 2014, 149(7): 777787.
　?。?］ LIN Y F, CHEN H H, TSENG V S, et al. Reliable early classification on multivariate time series with numerical and categorical attributes［A］.Advances in Knowledge Discovery and Data Mining. Springer International Publishing, 2015，9077：199211.
　?。?0］ 翁小清,沈鈞毅. 多變量時間序列的異常識別與分類研究［D］. 西安:西安交通大學(xué)，2008.　　

       ［11］ DACHRAOUI A, BONDU A, CORNUJOLS A. Evaluation protocol of early classifiers over multiple data sets［A］.Neural Information Processing［C］. Springer International Publishing, 2014，8835：548555.
　?。?2］ DACHRAOUI A, BONDU A, CORNUJOLS A. Early classification of time series as a non myopic sequential decision making problem［A］.Machine Learning and Knowledge Discovery in Databases［C］. Springer International Publishing, 2015: 433447.
　?。?3］ GHALWASH M F, RADOSAVLJEVIC V, OBRADOVIC Z. Utilizing temporal patterns for estimating uncertainty in interpretable early decision making［C］.Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining， ACM, 2014: 402411.
　　［14］ 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 (BIBM),  IEEE, 2012: 16.
　　［15］ 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.
　?。?6］ DACHRAOUI A, BONDU A, CORNUEJOLS A. Early classification of individual electricity consumptions［C］. Realstream 2013(ECML), 2013, 8190:1821.
　　［17］ HAN J,KAMBER M, PEI J. Data mining: concepts and techniques［M］. Elsevier, 2011.
　?。?8］ 原繼東, 王志海. 時間序列的表示與分類算法綜述［J］. 計算機(jī)科學(xué), 2015, 42(3): 17.
　?。?9］ 戚陸越, 吳升. 時間序列數(shù)據(jù)可視化研究綜述［J］. 微型機(jī)與應(yīng)用, 2015, 34(12):710.