基于增量式決策樹的時間序列分類算法研究

王樹英，王志海

（北京交通大學計算機與信息技術學院，北京　100044）

基于增量式決策樹的時間序列分類算法研究

王樹英，王志海

（北京交通大學計算機與信息技術學院，北京100044）

1　問題的定義

近幾年來，數據挖掘技術已經應用到很多研究領域中，時間序列數據也得到越來越廣泛的關注，例如股票交易數據、醫學腦電波數據、經濟銷售預測數據、字跡識別數據以及人體姿勢數據等。所有這些數據都有一個共同的特征，那就是數據本身是有順序相關的，且都是實值型數據，定義具有這樣特征的數據為時間序列數據。

主要針對時間序列數據維度高、實值有序、數據間存在自相關性［1］等特點，以及大數據理論的發展趨勢，提出了一種增量式的時間序列數據挖掘算法。這一部分主要描述時間序列分類涉及到的符號、定義及公式。表1總結了本文中出現的關于時間序列分類的相關記號。

下面，主要講述關于本文中出現的一些定義。當然，這里假定所有的分類問題都是兩類分類問題，多類分類問題是可以實現，只是有些繁瑣，這里為了簡便起見，只考慮了兩類相關的問題。

定義1 時間序列：一條時間序列是T=t1，…，tm，一個具有m個實值變量的有序集合。數據點t1，…，tm是相等時間間隔內數據的有序排列。

表1　時間序列有關符號

定義2時間子序列：假定一條時間序列T的長度為m，時間序列T的子序列S是一條從T中長度1≤m的連續位置的序列，即S=tp，…，tp+l-1，其中1≤p≤m-l+1。

定義3滑動窗口：給定一條長度為m的時間序列T，以及一個用戶定義的長度l，所有的子序列為一個長度為l的滑動窗口通過T之后所得到的。并且我們定義時間序列T的每一個長度l的子序列為Slp，其中上標l為子序列的長度，下標p表示的是滑動窗口在時間序列T中的位置。從時間序列T中獲取的所有長度為l的時間序列子序列定義為SlT，其中SlT=｛Slp，1≤p≤ml+1｝。

定義4時間序列之間的距離：距離函數Dist（T，R）表示輸入為兩條具有相同長度的時間序列T和R，輸出為非負值d，即兩條時間序列之間的距離［2］。且由函數我們知道，距離公式具有對稱性，即Dist（T，R）= Dist（R，T）。

定義5時間序列到子序列之間的距離：函數SubsequenceDist（T，S）用于定義時間序列T與子序列S之間的距離，其中輸入為時間序列T和子序列S，輸出為非負值d，即兩條時間序列之間的距離，如公式（1）所示。

SubsquenceDist（T，S）=min（Dist（S，S'）），

從公式（1）可以看出，時間序列T與子序列S之間的距離為兩個序列之間的最小距離。另外，可能需要一些度量標準來分裂數據集，傳統的決策樹中的信息增益即為典型的例子。

定義6熵：一個時間序列數據集D共有兩個類A 和B，假定數據集D中屬于類A的對象比例為P（A），屬于類B的對象比例為P（B），則熵的定義如公式（2）所示。

每一種分裂策略將整個數據集D分裂為兩個數據集D1和D2，那么分裂之后保留在整個數據集D上的信息，使用每一個分裂子集的加權平均熵定義。假定數據集D1占總體的比例為f（D1），數據集D2占總體的比例為f（D2），則分裂之后數據集D的整體熵如公式（3）所示。

定義7信息增益：給定一個分裂策略sp將數據集D分裂為兩個數據集D1和D2，分裂之前和之后的熵記為和，那么基于此分裂策略sp的信息增益如公式（4）所示。

對于基于決策樹的時間序列分類問題，主要考慮到時間序列數據維度高、自相關性以及連續數據的特點，提出了一種基于增量式決策樹的時間序列分類算法。

2　基于決策樹的時間序列分類

正如基本決策樹理論所描述，它采用了一種分而治之的策略，而且算法本身具有可解釋性。在此基礎上，提出了一種發現shapelet的過程，即發現一條時間序列中最具代表性的時間序列［3］。事實上，這個過程需要很大的存儲空間去存儲候選集的相關信息，能夠在判斷最優shapelet的同時，生成候選集然后刪除非最優的候選集，這樣就能夠節省大量的空間。從另一方面來說，shapelet的方法會產生很大的時間復雜性［4］。假定時間序列shapelet的長度為k，平均每一個時間序列的長度為，那么候選集的空間復雜度為O（2k）。其中搜索每一個候選集需要的時間復雜度為O（k），那么搜索整個候選集的時間復雜度為O（3k2）。

基于上述描述的時間序列分類問題的時間復雜度和空間復雜度，那么提出了兩種加速策略：

（1）子序列早期放棄（SDEA）策略

在發現shapelet的過程中，需要全局搜索時間序列數據集。在全局搜索的過程中，涉及到計算候選序列到一條時間序列序列的距離。子序列到一條時間序列序列的距離為子序列到時間序列中相同長度的子序列距離長度最小的那個。那么在計算這個距離的過程中，設置一個參數μ為當前情況下的最小距離。子序列到時間序列的計算過程中，如果發現得到的歐幾里得距離小于這個參數 ，那么就可以舍棄這一部分的計算過程，因為當前計算的距離只可能比這個參數μ要大，而子序列到時間序列的距離去最小值即可。

（2）可容許的熵剪枝（AEP）策略

SDTC算法在發現shapelet的過程中需要的時間代價最高，相比之下計算信息增益需要的時間代價非常小?；谶@樣的考慮，代替計算候選集到所有時間序列的距離，可以計算當前所得距離的信息增益上限。如果shapelet發現過程任意點的信息增益上限小于當前最好的信息增益，可以停止當前距離的計算，并減掉當前正在計算距離的那個候選集，因為可以確定這個候選集不是目前為止最好的候選集。

下面給出SDTC算法的具體算法描述：

輸入： 數據集 D，shapelet候選集的最大值MAXLEN、最小值MINLEN

輸出：shapelet決策樹分類器

//發現 shapelet過程，返回shapelet及最佳分裂距離splitdist

3　基于增量式決策樹的時間序列分類

從決策樹的構造過程來看，隨著樣本的增加，并不需要對決策樹進行重新構造，而只需要重構與樣本相關的子樹，大大降低了建樹的復雜性［5］?？紤]到時間序列數據集實例多且構造決策樹的速度慢，本算法在SDTC算法的基礎上，結合了增量式學習的思想［6］，可先用部分數據進行訓練，然后將剩余部分進行增量學習，繼而提出了一種新的基于增量式決策樹的時間序列分類算法ISDTC算法。

這里存在一個問題，當有一條新的實例到達訓練集時，原先選擇的分裂屬性的分類能力可能會隨著新實例的到達而降低。當候選屬性中存在比原先選擇的分列屬性分類能力更好的屬性時，本能就用新的候選集取代原先選擇的分類屬性。根據定義7信息增益可知，兩個屬性的信息增益之間的差值比較之后，可以得到如下所示的公式。

pi和ni分別為分類屬性兩個值的數目大小，p和n分別為正例和負例的數目。當增加的實例數目小于等于InsNummax時，不需要更新分類屬性；當增加的實例數目大于InsNummax時，就需要更新分類屬性．在研究增量式時序分類問題時，就是基于此公式來判斷是否需要更新分類屬性。

ISDTC算法的具體算法描述：

輸入：時間序列數據集，shapelet候選集的最大值MAXLEN、最小值MINLEN

輸出：增量式決策樹

（1）初始化。樹型根節點的初始化，指定可以發現shapelet的數據集數目m值，以及記錄每條實例信息的結果InsInfo；

（2）判斷接收到的實例個數是否達到m值。如果未達到指定的值m，繼續接收實例。如果達到m值，運行FindShapeletBF（）找到最好的shapelet，計算到該屬性到每條序列的距離，根據距離將數據離散化表示，并計算該shapelet的正例數目和負例數目。

（3）當下一條數據到達時，根據當前的shapelet計算子序列距離并離散化表示，存在下面兩種情況：

①如果實際數目小于InsNummax，則繼續接收實例；

②如果實際數目大于InsNummax，則說明存在更具可辨別性的子序列shapelet。重新計算shapelet的值，計算到每條時間序列距離并離散化，并以這個屬性為分裂點分裂這個數據集。

（4）分裂數據集以后，遞歸循環2、3過程，直到決策樹到達葉節點，最終生成一顆健壯的決策樹。

這里需要注意的是，初始化階段直接指定了需要發現shapelet的數據集數目m的值，可以考慮采用一種動態生成的方式來確定m的值。另外，發現shapelet的過程與分裂數據集的過程，都用了信息論中的熵和信息增益的概念，可以考慮定義一個數據結構記錄這些信息增益的基本情況，這樣在犧牲一定存儲空間的基礎上，大大減小了計算上所花費的時間。另外，在發現shapelet的過程中，應該遵循下面一些基本原則：

①發現的shapelet盡可能具有可解釋性；

②在信息增益相同的情況，選定的shapelet的長度盡量采用短時間序列，這樣會減少計算距離的時間。

4　實驗結果分析

4.1實驗平臺和數據

（1）簡要說明進行該實驗時涉及到的實驗環境，如下所示：

①JDK版本：Java SE Development Kit 7u11 for Windows x86；

②IDE環境：eclipse-standard-luna-R-win32；

③Weka版本：weka-3-7-12 for Windows x86。

（2）實驗數據：

為了評價shapelet轉化的性能，選擇了UCR時間序列數據庫中14個數據集，數據集詳細信息如表3所示。

4.2實驗結果分析

下面對本文提到的兩種加速策略以及基于增量式決策樹的時間序列分類算法進行詳細的結果分析，分析結果如下所示。

表2　兩種加速策略的時間和精確度比較

為了便于比較提出的兩種加速技術與相結合后的性能比較，通過圖1進行可視化展示。

圖1　兩種加速策略和合并兩種策略后的時間比較

針對提出的基于增量式決策樹的時間序列分類算法，可以采用比較精確度的方式與決策樹的時間序列分類算法進行比較，下面是在14個UCR數據集上進行精確度驗證的結果展示。

表3　兩種時間序列分類算法的精確度比較

為了便于比較ISDTC算法和SDTC算法的準確率，將上述過程展示如圖2所示。

圖2　ISDTC算法和SDTC算法的分類精確度比較

從圖2可以看出，兩種分類方法的分類精確度非常接近，說明提出的基于增量式決策樹的時間序列分類算法——ISDTC算法能夠產生與使用靜態數據進行構建決策樹的時間序列分類算法——SDTC算法類似的決策樹。當然，事實這種比較方法是不嚴謹的，但是基于時間序列數據為高維數值型數據，很難可視化表示的特點，本文以比較精確度的方式進行說明。

5　結語

隨著數據挖掘技術的廣泛研究，復雜數據類型的挖掘得到越來越多研究人員的關注。本文從復雜數據類型中的時間序列數據出發，研究了當前國內外關于時間序列分類的研究現狀［7～8］，根據當前大數據的實際以及對時間和空間的要求，以及基于決策樹分而治之的測量以及可解釋性，提出基于增量式決策樹的時間序列分類算法——ISDTC算法。實驗表明本文中提出的基于增量式決策樹的時間序列分類算法最終生成的增量式決策樹，能夠產生與在靜態數據中進行時間序列分類算法生成的決策樹相似精確的決策樹。

［1］Esling P，Agon C.Time-series Data Mining［J］.ACM Computing Surveys（CSUR），2012，45（1）:12

［2］Faloutsos C，Ranganathan M，Manolopulos Y.Fast Subsequence Matching in Time-Series Databases.SIGMOD Rec，1994:419～429

［3］Ye L X，Keogh E.Time Series Shapelets:A New Primitive for Data Mining［C］.In:Flach P and Zaki M（eds.）.Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining（KDD2009，Paris，France）.New York:ACM Press，2009：947～956

［4］Ye L，Keogh E.Time Series Shapelets:A Novel Technique that Allows Accurate.Interpretable and Fast Classification.Data Mining and Knowledge Discovery，2011，22（1-2）：149～182

［5］Utgoff P E.An Improved Algorithm for Incremental Induction of Decision Trees［C］.In:Proceedings of the Eleventh International Conference on Machine Learning，1994：318～325

［6］Utgoff P E.Incremental Induction of Decision Trees［J］.Machine Learning，1989，4（2）:161～186

［7］何曉旭.時間序列數據挖掘若干關鍵問題研究［D］.中國科學技術大學，2014

［8］Hills J，Lines J，Baranauskas E，et al.Classification of Time Series by Shapelet Transformation.Data Mining and Knowledge Discovery. 2013：1～31

Time Series；Incremental Learning；Decision Tree；Algorithm Research

Research on the Time Series Classification Algorithm Based on Incremental Decision-Tree

WANG Shu-ying，WANG Zhi-hai
（School of Computer and Information Technology，Beijing Jiaotong University，Beijing 100044）

1007-1423（2015）08-0026-05

10.3969/j.issn.1007-1423.2015.08.006

王樹英（1988-），女，山東人，碩士研究生，研究方向為數據挖掘、模式識別

2015-01-13

2015-02-13

數據挖掘技術已經應用到很多研究領域中，數據挖掘的類型也越來越復雜。其中一類數據本身是有順序相關的，且是實值型數據，定義具有這樣特征的數據為時間序列數據，使用常見的數據挖掘方法從時間序列數據中進行知識學習是不適用的。并且隨著大數據理論的不斷發展，能夠增量式地處理數據以減小對時間和存儲空間的需求。基于時間序列數據維度高、實值有序、數據間存在自相關性等特點，提出一種增量式決策樹的時間序列分類算法。

時間序列；增量式學習；決策樹；算法研究

北京市自然科學基金（No.4142042）

王志海（1963-），男，河南人，博士，教授，研究方向為數據挖掘

Data mining technology has been attracting great interest in a vast array of research areas,and their types are more and more complex. The data is related and ordered set of real valued variables,and then such data with above characters is called time series.The following conclusion is that common method of data mining method can't be suit to time series data mining.And with the continuous development of the theory of big data,incremental method is essential in order to decrease temporal and space demand for implement of time series. Focuses on the research on time series classification according to time series features of high dimensionality,ordered real-valued variables,auto-correlation and so on.And proposes incremental decision-tree algorithm for time series classification.