馬超紅，翁小清

(河北經(jīng)貿(mào)大學 信息技術學院，河北 石家莊 050061)

?

時間序列早期分類綜述

馬超紅，翁小清

(河北經(jīng)貿(mào)大學 信息技術學院，河北 石家莊 050061)

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

時間序列；早期分類；特征提取與選擇

引用格式：馬超紅，翁小清. 時間序列早期分類[J].微型機與應用，2016,35(16)：13-15，19.

0　引言

時間序列在狹義上是指按時間順序有次序的一組數(shù)據(jù)，而廣義上任何實值型的有次序的序列都可以當作時間序列來處理。時間序列分類被廣泛應用在醫(yī)學診斷、災害預測、入侵檢測、過程控制、道路交通等生活中的方方面面。而在很多領域中越早做出分類對于指導決策越有利，時間序列的早期分類應運而生，并在一些時間敏感的應用領域至關重要，例如健康信息學、災害預測、入侵檢測、股市行情預測等領域。

時間序列早期分類即針對時間序列數(shù)據(jù)盡早地做出預測，并滿足預期的預測質(zhì)量(準確率)。換句話說，在滿足一個給定的最小的準確率情況下，早期分類嘗試著優(yōu)化分類的早期性，而不是像其他一般分類方法那樣只追求最大化準確率[1]。

時間序列的早期分類方法大致分為三類：基于原始數(shù)據(jù)、基于特征和基于模型的分類方法。

1　基于原始數(shù)據(jù)的時間序列早期分類

時間序列的早期分類是近幾年逐漸開始研究的，Xing Zhengzheng等人[2]在2008年對序列數(shù)據(jù)的早期預測進行了研究，提出了SCR(Sequential Classification Rule)方法和GSDT(Generalized Sequential Decision Tree)方法。SCR挖掘序列分類規(guī)則構(gòu)造分類器，并根據(jù)早期預測效應值在序列枚舉樹中進行剪枝來選擇特征并構(gòu)造規(guī)則。GSDT采用分治策略構(gòu)造分類模型，在序列特征集中選擇分類屬性，確保訓練集中的每條序列數(shù)據(jù)至少包含一條所選的屬性。SCR和GSDT適用于符號序列(Categorical Sequence)，而時間序列是連續(xù)數(shù)據(jù)，所以在應用于時間序列早期識別時需要對時間序列進行離散化。

Xing Zhengzheng等人[3-4]在2009提出將1NN分類器用于時間序列的早期分類，提出了最小預測長度(Minimum Prediction Length, MPL)的概念和一種時間序列早期分類方法(Early Classification on Time Series，ECTS)，ECTS方法在1NN方法有效的情況下既能保證分類準確率，又能實現(xiàn)早期分類。Xing Zhengzheng等人還提出了Fixed 1NN分類器，即選用固定長度的MPL，適用于2-class問題，同時也改進了ECTS，提出了Relaxed ECTS，通過relaxed MPL來避免在原ECTS方法下由于處于決策邊界而沒有被分類的時間序列，從而提高了分類器的整體穩(wěn)定性。

1NN早期分類器已經(jīng)取得了較好的研究進展，在實現(xiàn)早期分類的同時其準確度可以與全長序列1NN分類器相媲美。但在一些領域如醫(yī)學、股市等，早期分類的可解釋性十分重要，有助于用戶更加信任早期分類的結(jié)果，并做出相應的決策。

2　基于特征的時間序列早期分類

基于可解釋性特征的早期分類，目前的方法大都是分為三個階段，即特征提取、特征選擇，最后再將特征用于分類。早期分類中提取的具有可解釋性的特征稱為shapelet[1]，通俗地講是時間序列的子序列，某種意義上最大程度地代表某一類的特性, shapeletf=(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 shapeletf=(s,δ,c)中的距離閾值。在選擇用于分類的local shapelets時，通過計算每一個shapelets的效用值Utility來進行排序選擇，計算方法如下：

(1)

提取local shapelet的計算量非常大，對于大數(shù)據(jù)集則計算時間更長。盡管參考文獻[1]中也提出了加速的技術，計算BMD-lists時，在不同的local shapelets中間共享計算結(jié)果，但降低其計算復雜度仍然是一個有待研究的問題。提取local shapelets 的方法可用于1NN分類方法無效的情況下。

在多變量時間序列早期分類方面，GHALWASH M F等[5]在2012年提出了一種多變量Shapelets檢測(Multivariate Shapelets Detection, MSD)方法。該方法采用多變量信息增益選取δ值，在特征選擇階段運用加權(quán)信息增益來計算shapelets的效應值，計算公式如下：

(2)

He Guoliang等人[6-7]在2013年針對多變量時間序列早期分類的可解釋性，提出了一種挖掘核心特征的方法(Mining Core Feature for Early Classification，MCFEC)，通過實驗證明，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)來進行分類。特征提取階段采用的是通用方法，將每一個訓練樣本中滿足長度在minL和maxL之間的子序列提取出來組成特征候選集；在特征選擇階段，不同于先前對整體的候選集進行排序的方法。首先采用Silhouette Index將候選集中屬于同一變量類標號的特征進行聚類，形成若干簇，基于compactness-separation 度量將候選shapelets動態(tài)地歸入最近的簇，另外不同于先前的多變量時間序列早期分類提取的shapelets起點必須相同[5]，MCFEC所提取的各個變量shapelets的起始點和結(jié)束點可以不同；運用F-measure方法選取距離閾值δ，公式如下：

(3)

(4)

同時He Guoliang等人[7]在2013年針對不平衡時間序列的早期預測也進行了相應研究，提出了EPIMTS(Early Prediction on Imbalanced Multivariate Time Series)方法。在構(gòu)造訓練集時采用欠抽樣方法來處理不平衡數(shù)據(jù)集。

目前大部分方法是針對數(shù)值屬性進行研究，LIN Y F等人[9]在2015年針對數(shù)值和符號屬性(Numerical and Categorical Attributes)的多變量時間序列進行了研究，提出了REACT方法。該方法使用shapelets生成器挖掘等價類(Equivalence Classes Mining)，從多變量時間序列中成功地提取了符號序列的特征，并且考慮了數(shù)據(jù)集的不平衡問題，采用基于類別比例的子集聚類,評估方案采用平均f-score，如下：

(5)

3　早期分類器評估方案及現(xiàn)有方法總結(jié)

時間序列x={(t1,x1),(t2,x2),…,(tL,xL)}的長度為L，且每一個實值{xj∈[1,L]}對應一個時間點{tj∈[1,L]}，訓練集中的數(shù)據(jù)為{(xi,ci)|i∈[1,N]}，其中xi為一條時間序列，ci為其對應的類標號(ci∈C)，C是類標號的有窮集合[10]。早期分類即在完全輸入xj前預測其類標號，所以在早期分類中有兩個沖突的目標：早期性和可靠性。早期性即盡可能早地對不完全輸入序列進行預測；可靠性即分類器輸出的準確率問題[11]。DACHRAOUI A等人[11]在2015年提出在多個數(shù)據(jù)集上對不同的早期分類器采用統(tǒng)計檢驗的方法(威爾克森符號秩檢驗Wilcoxon signed-rank和帕累托最優(yōu)Pareto Optimum)進行評估。

另外如何對早期分類的兩個指標進行權(quán)衡，DACHRAOUI A等人[12]在2015年將時間序列早期分類視為非近視的序貫決策樹問題，采用通用順序元算法來實現(xiàn)早期性和可靠性之間的權(quán)衡。

GHALWASH M F等人[13]在2014年針對可解釋性早期分類方法的不確定性估計提供了一種簡單有效的方法。沒有采用直接估計不確定性的方法，而是將一個時間序列分類c的不確定性定義為：U(c)=1-C(c)，其中C(c)是分類為類c的置信度。同時對EDSC進行了修正，提出了MEDSC-U(Modified EDSC with Uncertainty estimates)方法。

對于shapeletf=(s,δ,c)中距離閾值δ的計算有以下幾種方法：核密度估計函數(shù)、切比雪夫不等式、信息增益、Quality(Fβ-measure)。特征提取導致features存在冗余，且不具備代表性，特征候選集數(shù)量較大，所以特征選擇階段對候選集進行縮減，主要思路為運用Utility Score 方法對shapelets排序，選取排序第一的shapelet，并將其覆蓋的序列在訓練集中刪除，再選取排序第二的shapelet，重復上述步驟，直到覆蓋了訓練集中的所有時間序列。目前大致有以下幾種指標用于候選shapelet的排序：Utility(f)、GEFM(f)、加權(quán)信息增益、F-measure(f)。

另外,除基于原始數(shù)據(jù)和特征的分類方法之外，GHALWASH M F等人[14]在2012年針對多變量時間序列的分類構(gòu)造了早期分類模型(Early Classification Model, ECM),其中集成了隱馬爾科夫模型和支持向量機模型。盡管在相同數(shù)據(jù)集上分類結(jié)果的平均準確率較其他方法偏低，但ECM僅用了整個時間序列的40%。

4　時間序列早期分類的應用

在早期診斷方面，GHALWASH M F等人[12]在2015年提取可解釋性的多變量模式(Interpretable Patterns for Early Diagnostics, IPED)來實現(xiàn)時間序列早期分類。首先將時間序列數(shù)據(jù)轉(zhuǎn)化為二元矩陣(binary matrix)，然后運用凸優(yōu)化方法在矩陣中提取多變量模式，并采用混合整數(shù)離散優(yōu)化方法來降低時間序列維度，最后將具有可解釋性的多變量模式用于臨床診斷。

在氣體識別方面，HATAMI N等人[15]在2013年基于帶有拒絕選項的一組連續(xù)分類器(Classifiers With a Reject Options, CWRO)，提出了一種時間序列早期分類的模型，并成功應用發(fā)明了新型電子鼻——Forefront-Nose。第一個分類器利用一小部分可利用的信號對氣體的類型作出決策，第二個分類器利用新的一部分時間序列信號作出決策，分配一個可信的標簽或者傳遞給下一分類器，迭代上述過程直到某個分類器分配了足夠可信的標簽或者延遲分類的代價太大。

DACHRAOUI A等人[16]在2013年將時間序列的早期分類應用于個人電力消費(individual electricity consumption)。實驗用的數(shù)據(jù)集是Irish CER提供的6 000個家庭在500天內(nèi)，抽樣間隔為30分鐘的家庭電力消費數(shù)據(jù)。

5　結(jié)論

時間序列的早期分類在醫(yī)療和健康信息學、工業(yè)生產(chǎn)管理、安全管理、災害預測等重要領域都具有廣泛的應用，目前已經(jīng)有了很大的研究進展，但是仍然有很多需要研究的問題。

多變量時間序列的早期分類在時間序列挖掘中是一個研究熱點，由于它的多變量性和不同組成部分的序列長度可能不同，以及不同變量之間可能存在關聯(lián)性，很難用傳統(tǒng)的數(shù)據(jù)挖掘算法來對多變量時間序列進行處理，因此將會是一個研究熱點[17]。在具體應用中，存儲的時間序列以非?？斓乃俣仍谠鲩L，目前的分類方法大多是基于小型的數(shù)據(jù)集，所以針對大數(shù)據(jù)集的早期分類將是一個難點，時間序列每時每刻都在隨著時間變化更新，屬于流數(shù)據(jù)[18-19]，對于流數(shù)據(jù)的數(shù)據(jù)挖掘，如何提高其分類精度同時實現(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.

[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.

[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] 戚陸越, 吳升. 時間序列數(shù)據(jù)可視化研究綜述[J]. 微型機與應用, 2015, 34(12):7-10.

Review of early classification on time series

Ma Chaohong，Weng Xiaoqing

(Information Technology College, Hebei University of Economics & Business, Shijiazhuang 050061, China)

On the base of reading the literatrues about early classification on time series in recent years, this paper summarized the relevant research development of early classification of time series, and categorized the academic opinions, classification methods. This paper covers feature extraction and selection, evaluation methodology, and the construction of model. It provides reference for researchers to get the research trends, development and new techniques.

time series; early classification; feature extraction and selection

TP391.4

A

10.19358/j.issn.1674- 7720.2016.16.003

2016-05-29)

馬超紅(1994-)，女，碩士研究生，主要研究方向：數(shù)據(jù)挖掘與信息檢索。

翁小清(1965-)，男，博士，教授，主要研究方向：數(shù)據(jù)挖掘。