時(shí)間序列早期分類綜述

馬超紅，翁小清

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

?

時(shí)間序列早期分類綜述

馬超紅，翁小清

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

在總結(jié)了近年來關(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í)間序列；早期分類；特征提取與選擇

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

0　引言

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

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

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

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

時(shí)間序列的早期分類是近幾年逐漸開始研究的，Xing Zhengzheng等人[2]在2008年對(duì)序列數(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適用于符號(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ù)測長度(Minimum Prediction Length, MPL)的概念和一種時(shí)間序列早期分類方法(Early Classification on Time Series，ECTS)，ECTS方法在1NN方法有效的情況下既能保證分類準(zhǔn)確率，又能實(shí)現(xiàn)早期分類。Xing Zhengzheng等人還提出了Fixed 1NN分類器，即選用固定長度的MPL，適用于2-class問題，同時(shí)也改進(jìn)了ECTS，提出了Relaxed ECTS，通過relaxed MPL來避免在原ECTS方法下由于處于決策邊界而沒有被分類的時(shí)間序列，從而提高了分類器的整體穩(wěn)定性。

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

2　基于特征的時(shí)間序列早期分類

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

(1)

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

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

(2)

He Guoliang等人[6-7]在2013年針對(duì)多變量時(shí)間序列早期分類的可解釋性，提出了一種挖掘核心特征的方法(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)行分類。特征提取階段采用的是通用方法，將每一個(gè)訓(xùn)練樣本中滿足長度在minL和maxL之間的子序列提取出來組成特征候選集；在特征選擇階段，不同于先前對(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方法選取距離閾值δ，公式如下：

(3)

(4)

同時(shí)He Guoliang等人[7]在2013年針對(duì)不平衡時(shí)間序列的早期預(yù)測也進(jìn)行了相應(yīng)研究，提出了EPIMTS(Early Prediction on Imbalanced Multivariate Time Series)方法。在構(gòu)造訓(xùn)練集時(shí)采用欠抽樣方法來處理不平衡數(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ù)集的不平衡問題，采用基于類別比例的子集聚類,評(píng)估方案采用平均f-score，如下：

(5)

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

時(shí)間序列x={(t1,x1),(t2,x2),…,(tL,xL)}的長度為L，且每一個(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ù)測其類標(biāo)號(hào)，所以在早期分類中有兩個(gè)沖突的目標(biāo)：早期性和可靠性。早期性即盡可能早地對(duì)不完全輸入序列進(jìn)行預(yù)測；可靠性即分類器輸出的準(zhǔ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í)間序列早期分類視為非近視的序貫決策樹問題，采用通用順序元算法來實(shí)現(xiàn)早期性和可靠性之間的權(quán)衡。

GHALWASH M F等人[13]在2014年針對(duì)可解釋性早期分類方法的不確定性估計(jì)提供了一種簡單有效的方法。沒有采用直接估計(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ì)于shapeletf=(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)來實(shí)現(xiàn)時(shí)間序列早期分類。首先將時(shí)間序列數(shù)據(jù)轉(zhuǎn)化為二元矩陣(binary matrix)，然后運(yùn)用凸優(yōu)化方法在矩陣中提取多變量模式，并采用混合整數(shù)離散優(yōu)化方法來降低時(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)簽或者傳遞給下一分類器，迭代上述過程直到某個(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ù)測等重要領(lǐng)域都具有廣泛的應(yīng)用，目前已經(jīng)有了很大的研究進(jìn)展，但是仍然有很多需要研究的問題。

多變量時(shí)間序列的早期分類在時(shí)間序列挖掘中是一個(gè)研究熱點(diǎn)，由于它的多變量性和不同組成部分的序列長度可能不同，以及不同變量之間可能存在關(guān)聯(lián)性，很難用傳統(tǒng)的數(shù)據(jù)挖掘算法來對(duì)多變量時(shí)間序列進(jìn)行處理，因此將會(huì)是一個(gè)研究熱點(diǎn)[17]。在具體應(yīng)用中，存儲(chǔ)的時(shí)間序列以非?？斓乃俣仍谠鲩L，目前的分類方法大多是基于小型的數(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)一步研究。

[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] 翁小清,沈鈞毅. 多變量時(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.

[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] 原繼東, 王志海. 時(shí)間序列的表示與分類算法綜述[J]. 計(jì)算機(jī)科學(xué), 2015, 42(3): 1-7.

[19] 戚陸越, 吳升. 時(shí)間序列數(shù)據(jù)可視化研究綜述[J]. 微型機(jī)與應(yīng)用, 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ù)挖掘。