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

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

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

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

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

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

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

3早期分類器評(píng)估方案及現(xiàn)有方法總結(jié)
　　時(shí)間序列x={(t1,x1),(t2,x2),…,(tL,xL)}的長(zhǎng)度為L(zhǎng)，且每一個(gè)實(shí)值{xj∈［1,L］}對(duì)應(yīng)一個(gè)時(shí)間點(diǎn){tj∈［1,L］}，訓(xùn)練集中的數(shù)據(jù)為{(xi,ci)|i∈［1,N］}，其中xi為一條時(shí)間序列，ci為其對(duì)應(yīng)的類標(biāo)號(hào)(ci∈C)，C是類標(biāo)號(hào)的有窮集合［10］。早期分類即在完全輸入xj前預(yù)測(cè)其類標(biāo)號(hào)，所以在早期分類中有兩個(gè)沖突的目標(biāo)：早期性和可靠性。早期性即盡可能早地對(duì)不完全輸入序列進(jìn)行預(yù)測(cè)；可靠性即分類器輸出的準(zhǔn)確率問(wèn)題［11］。DACHRAOUI A等人［11］在2015年提出在多個(gè)數(shù)據(jù)集上對(duì)不同的早期分類器采用統(tǒng)計(jì)檢驗(yàn)的方法(威爾克森符號(hào)秩檢驗(yàn)Wilcoxon signedrank和帕累托最優(yōu)Pareto Optimum)進(jìn)行評(píng)估。
　　另外如何對(duì)早期分類的兩個(gè)指標(biāo)進(jìn)行權(quán)衡，DACHRAOUI A等人［12］在2015年將時(shí)間序列早期分類視為非近視的序貫決策樹問(wèn)題，采用通用順序元算法來(lái)實(shí)現(xiàn)早期性和可靠性之間的權(quán)衡。
　　GHALWASH M F等人［13］在2014年針對(duì)可解釋性早期分類方法的不確定性估計(jì)提供了一種簡(jiǎn)單有效的方法。沒(méi)有采用直接估計(jì)不確定性的方法，而是將一個(gè)時(shí)間序列分類c的不確定性定義為：U(c)=1-C(c)，其中C(c)是分類為類c的置信度。同時(shí)對(duì)EDSC進(jìn)行了修正，提出了MEDSCU(Modified EDSC with Uncertainty estimates)方法。
　　對(duì)于shapelet f=(s, δ, c)中距離閾值δ的計(jì)算有以下幾種方法：核密度估計(jì)函數(shù)、切比雪夫不等式、信息增益、Quality(Fβ-measure)。特征提取導(dǎo)致features存在冗余，且不具備代表性，特征候選集數(shù)量較大，所以特征選擇階段對(duì)候選集進(jìn)行縮減，主要思路為運(yùn)用Utility Score 方法對(duì)shapelets排序，選取排序第一的shapelet，并將其覆蓋的序列在訓(xùn)練集中刪除，再選取排序第二的shapelet，重復(fù)上述步驟，直到覆蓋了訓(xùn)練集中的所有時(shí)間序列。目前大致有以下幾種指標(biāo)用于候選shapelet的排序：Utility(f)、GEFM(f)、加權(quán)信息增益、Fmeasure(f)。
　　另外,除基于原始數(shù)據(jù)和特征的分類方法之外，GHALWASH M F等人［14］在2012年針對(duì)多變量時(shí)間序列的分類構(gòu)造了早期分類模型(Early Classification Model, ECM),其中集成了隱馬爾科夫模型和支持向量機(jī)模型。盡管在相同數(shù)據(jù)集上分類結(jié)果的平均準(zhǔn)確率較其他方法偏低，但ECM僅用了整個(gè)時(shí)間序列的40%。
4時(shí)間序列早期分類的應(yīng)用
　　在早期診斷方面，GHALWASH M F等人［12］在2015年提取可解釋性的多變量模式(Interpretable Patterns for Early Diagnostics, IPED)來(lái)實(shí)現(xiàn)時(shí)間序列早期分類。首先將時(shí)間序列數(shù)據(jù)轉(zhuǎn)化為二元矩陣(binary matrix)，然后運(yùn)用凸優(yōu)化方法在矩陣中提取多變量模式，并采用混合整數(shù)離散優(yōu)化方法來(lái)降低時(shí)間序列維度，最后將具有可解釋性的多變量模式用于臨床診斷。
　　在氣體識(shí)別方面，HATAMI N等人［15］在2013年基于帶有拒絕選項(xiàng)的一組連續(xù)分類器(Classifiers With a Reject Options, CWRO)，提出了一種時(shí)間序列早期分類的模型，并成功應(yīng)用發(fā)明了新型電子鼻——Forefront-Nose。第一個(gè)分類器利用一小部分可利用的信號(hào)對(duì)氣體的類型作出決策，第二個(gè)分類器利用新的一部分時(shí)間序列信號(hào)作出決策，分配一個(gè)可信的標(biāo)簽或者傳遞給下一分類器，迭代上述過(guò)程直到某個(gè)分類器分配了足夠可信的標(biāo)簽或者延遲分類的代價(jià)太大。
　　DACHRAOUI A等人［16］在2013年將時(shí)間序列的早期分類應(yīng)用于個(gè)人電力消費(fèi)(individual electricity consumption)。實(shí)驗(yàn)用的數(shù)據(jù)集是Irish CER提供的6 000個(gè)家庭在500天內(nèi)，抽樣間隔為30分鐘的家庭電力消費(fèi)數(shù)據(jù)。
5結(jié)論
　　時(shí)間序列的早期分類在醫(yī)療和健康信息學(xué)、工業(yè)生產(chǎn)管理、安全管理、災(zāi)害預(yù)測(cè)等重要領(lǐng)域都具有廣泛的應(yīng)用，目前已經(jīng)有了很大的研究進(jìn)展，但是仍然有很多需要研究的問(wèn)題。
　　多變量時(shí)間序列的早期分類在時(shí)間序列挖掘中是一個(gè)研究熱點(diǎn)，由于它的多變量性和不同組成部分的序列長(zhǎng)度可能不同，以及不同變量之間可能存在關(guān)聯(lián)性，很難用傳統(tǒng)的數(shù)據(jù)挖掘算法來(lái)對(duì)多變量時(shí)間序列進(jìn)行處理，因此將會(huì)是一個(gè)研究熱點(diǎn)［17］。在具體應(yīng)用中，存儲(chǔ)的時(shí)間序列以非常快的速度在增長(zhǎng)，目前的分類方法大多是基于小型的數(shù)據(jù)集，所以針對(duì)大數(shù)據(jù)集的早期分類將是一個(gè)難點(diǎn)，時(shí)間序列每時(shí)每刻都在隨著時(shí)間變化更新，屬于流數(shù)據(jù)［1819］，對(duì)于流數(shù)據(jù)的數(shù)據(jù)挖掘，如何提高其分類精度同時(shí)實(shí)現(xiàn)早期分類將會(huì)是一個(gè)研究熱點(diǎn)。另外在基于模型的分類方法研究較少，值得今后進(jìn)一步研究。
　　參考文獻(xiàn)
　　［1］ 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.
　　［3］ 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.
　?。?］ GHALWASH M F, OBRADOVIC Z. Early classification of multivariate temporal observations by extraction of interpretable shapelets［J］. BMC Bioinformatics, 2012, 13(1): 112.
　　［6］ 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.
　　［8］ 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］ 翁小清,沈鈞毅. 多變量時(shí)間序列的異常識(shí)別與分類研究［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.
　　［12］ 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.
　?。?4］ 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］ 原繼東, 王志海. 時(shí)間序列的表示與分類算法綜述［J］. 計(jì)算機(jī)科學(xué), 2015, 42(3): 17.
　　［19］ 戚陸越, 吳升. 時(shí)間序列數(shù)據(jù)可視化研究綜述［J］. 微型機(jī)與應(yīng)用, 2015, 34(12):710.