馬超紅，翁小清
　　（河北經貿大學 信息技術學院，河北 石家莊 050061）

       摘要：在總結了近年來關于時間序列早期分類相關文獻和相關研究進展的基礎上，對參考文獻中的學術觀點、分類方法進行了比較歸類，內容涵蓋了時間序列原始數據的早期分類，時間序列早期分類的特征提取與選擇、評估方法，早期分類構造模型等方面，為研究者了解最新的時間序列早期分類研究動態、新技術、發展趨勢提供了參考。
　　關鍵詞：時間序列；早期分類；特征提取與選擇　　

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

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

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

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

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

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