基于微局部特征的時序數(shù)據(jù)二分類算法①

舒?zhèn)ゲ?/p>

(中國科學技術大學 計算機科學與技術學院，合肥 230027)

1 引言

時間序列是一種重要且特殊的高維數(shù)據(jù)，它的各個維度之間存在固定的先后次序，這些次序中隱藏大量的有利于分類的特征信息.在現(xiàn)實生活中，時間序列有著廣泛的應用.例如天氣預報中的氣象數(shù)據(jù)、對外貿(mào)易中浮動的貨幣匯率、醫(yī)療器械捕獲的電波圖像，工程應用中的連續(xù)信號等，這些數(shù)據(jù)都可以看成是時間序列.

時間序列分類是時序數(shù)據(jù)分析中的主要任務之一.當前的時序數(shù)據(jù)分類算法可大致分為兩類，一類是將整個時間序列看成一個整體，即距離空間中的一個點，通過構造合適的距離度量方式，在距離空間中尋找分類邊界.

第二類是采用滑動窗口的方式捕捉時間序列的子序列，即所謂的“捕捉局部特征”.在通過某些方式選擇具有良好分類性能的局部特征后，通過這些局部特征來構造各式各樣的分類器，進而完成分類.

通過一些綜合的比較，基于局部特征的分類方法整體性能優(yōu)于第一類算法，尤其體現(xiàn)在更好的分類性能上[1].因而基于局部特征的分類方法也是現(xiàn)在研究的主要方向.

本文針對現(xiàn)階段在基于局部特征進行時序數(shù)據(jù)分類的研究領域內(nèi)存在的一些問題，設計了一個新的算法，該算法著重解決現(xiàn)階段存在于該領域內(nèi)的如下兩個問題：

(1)基于局部特征的分類算法在分類精度上依舊存在可以提升的空間.該問題尤其體現(xiàn)在一些二分類問題上.

(2)基于局部特征的分類算法在現(xiàn)階段存在太多的冗余局部特征，使得時間復雜度相對較高.

針對這兩個問題，本文提出的算法分別采用如下的策略進行改進：

(1)本算法針對二分類問題，采用一種新的指標來評價局部特征，使得原數(shù)據(jù)在轉換到特征空間后，具備更高的線性可分性.

(2)本算法在選擇局部特征前，首先拋棄大量局部特征，僅保留長度非常短的局部特征，使得局部特征數(shù)量大幅減小，因而在評估并選擇局部特征時，時間會被大幅減少.

對于這兩處創(chuàng)新，本文也會給出理論依據(jù)以證明其可行性，同時，實驗結果也證明了其帶來的時間優(yōu)勢和分類性能上的優(yōu)勢.

2 相關工作

2.1 幾個術語的定義

定義1.時間序列及其分類器：時序數(shù)據(jù)的一個樣本點是一個序對(x，y)，x是一個m維的有序觀測值(x1，x2，…，xm)，y為該樣本點的類標，在不需要討論其類別信息時，我們也會在文中將其簡寫為x.整個樣本集表示為T=(X，Y)=((x1，y1)，(x2，y2)，…，(xn，yn))，在不需要討論其類別信息時，我們也會在文中將其簡寫為X.

定義2.局部特征(shapelet)：局部特征又叫 shapelet，本質(zhì)上是時間序列的連續(xù)子序列，其具有一定的判別性能[2].所以一個局部特征由一段連續(xù)子序列以及一個類標組成，該類標即為該子序列的父序列(即某一原始時間序列)的類標.我們在文中用(s，z)來表示一個局部特征，其中s表示其代表的連續(xù)子序列，z為其類標，在不需要討論其類別信息時，我們也會在文中直接用s指代.為了尊重提出shapelet 的原作者，從此處開始，下文中的“局部特征”皆用“shapelet”替代.

2.2 基于shapelet 的時序數(shù)據(jù)分類算法

一個m維的數(shù)據(jù)，它的shapelet 的長度可以是1 到m，所以其一共產(chǎn)生m(m+1)/2 個shapelet.如果數(shù)據(jù)集里面有n個時間序列，那整個數(shù)據(jù)集一共擁有nm(m+1)/2 個shapelet.Ye LX 和Keogh E 首次提出用shapelet 進行時間序列分類.其使用方法是選擇具有判別性的shapelet 來構造一棵決策樹[2].該決策樹的判定節(jié)點為一個shapelet，而屬性即為時間序列與該判定節(jié)點中的shapelet 的距離，通過距離所處的區(qū)間來將時間序列選擇遞交給某下一個節(jié)點處理[2].

因為shapelet 是從原始數(shù)據(jù)上截取下來的子序列，所以與原始數(shù)據(jù)并不等長，這里特別說明一下如何計算shapelet 與原始數(shù)據(jù)之間的距離.

設原始數(shù)據(jù)的一個樣本點x=(x1，x2，…，xm)，某個shapelets=(s1，s2，…，sj)，其中j≤m，那么它們之間的距離用如下函數(shù)D(.，.)計算：

其中，d(·，·) 是歐式距離度量函數(shù).

該算法較好地利用了數(shù)據(jù)的局部特征進行分類，具有不錯的分類精度和可擴展性，但其缺點在于時間復雜性高.算法擁有O(n2m4)的計算復雜性，n是數(shù)據(jù)個數(shù)，m是數(shù)據(jù)維數(shù)，即時間序列數(shù)據(jù)的長度[2].

針對該方法時間復雜度高的問題，領域內(nèi)的研究者提出了種種解決方案[3-6]，這里介紹其中幾種比較有代表性的方案.該算法時間復雜度高的第一大原因在于候選shapelet 太多了，對每一個shapelet 進行評估的單位時間，被候選shapelet 的數(shù)量極大規(guī)模地放大.所以有一類叫做“快速shapelet”的方法針對候選shapelet的數(shù)量進行改進，它們犧牲掉一些shapelet 的覆蓋率，大幅減少shapelet 的候選數(shù)量，換取運行速率上的提升，但是精度上也有明顯退化[7].而另一類叫做“l(fā)earning shapelet”的算法，它并不從原始數(shù)據(jù)直接獲取shapelet，而是通過學習的方式習得最佳的shapelet.該shapelet可能與原始數(shù)據(jù)中的任意一個數(shù)據(jù)段都不匹配，因為它是通過feedback 的學習方式創(chuàng)造出的用于分類的shapelet.該方法開辟了另一條道路，然而其也存在過擬合的問題，時至今日尚無可觀的突破[8，9].

2.3 Shapelet 轉換算法與shapelet 集成算法

Ye LX 和Keogh E 使用shapelet 構造決策樹，該算法時間復雜度高的另一個原因在于，shapelet 的評估需要在每個節(jié)點的特征選擇階段進行一次.這是因為在構造完一個節(jié)點之后，數(shù)據(jù)集會被該節(jié)點劃分為若干新子集，而新子數(shù)據(jù)集與原來的數(shù)據(jù)集不相同了，所以shapelet 的判別性能需要在新子集上做重新的評估.同樣地，每一輪評估的時間被評估的輪數(shù)——即決策樹上的節(jié)點數(shù)——放大后，時間復雜度變得相當高.

于是有一類叫做“shapelet 轉換”的方法，它通過解決該問題來降低時間復雜度.該類方法通過一次性選取若干shapelet 來構建分類器，所以只需要對所有的shapelet 進行一輪評估，在評估并選取了合適的shapelet之后，則基于它們將原始數(shù)據(jù)轉換到一個特征空間中，轉換的方式是通過計算原始數(shù)據(jù)與第i個shapelet 的距離來作為原始數(shù)據(jù)在特征空間中的第i個坐標[10].當這些原始時序數(shù)據(jù)被轉換到特征空間中之后，它再使用kNN 算法來完成分類[10].該算法有效地避免了多輪shapelet 評估，但是其時間開銷依然不容小覷，主要原因還是上節(jié)中提到的候選的shapelet 數(shù)量太多.如果要減少候選shapelet 的數(shù)量，勢必會引起精度的下降，但是其相較于原來經(jīng)典的shapelet 算法已有了革命性的突破，使得后續(xù)的研究者工作開始圍繞如何快速地找到用來構建特征空間的若干shapelet 來進行[11].

“shapelet 轉換”的方法會有不穩(wěn)定的特性，因為數(shù)據(jù)在被轉換到特征空間之后，很難準確預料它們的分布特性，如果使用單一分類器，必須承擔錯誤估計它們分布特性的風險，所以很多時候特征空間中的單一分類器會帶來低分類性能的后果.為了解決這一問題，有人提出了“集成shapelet 轉換”的方法，即在特征空間中集成若干經(jīng)典分類器來完成分類[12].該方法能讓分類精度得到大幅提升，但是訓練集成分類器帶來的時間開銷也是很可觀的.

3 算法理論分析

該節(jié)對當前已有的基于局部特征的分類算法上存在的缺陷進行分析，探討如何能夠有效地改進它們.

3.1 時間序列與shapelet 的距離計算

從式(1)可以看到，計算一個shapelet 與一個時間序列的距離需要計算該shapelet 與該時間序列的所有與該shapelet 等長的連續(xù)子序列的距離，然后選擇其中最小的距離.如果假設一個時間序列的長度為m，一個shapelet 的長度為k，那么計算它們之間的距離需要O(k(m-k))的時間復雜度，當m＞＞k時，該復雜度接近O(km).

顯而易見，該距離度量方式的時間復雜度比較高，而且此種度量方式只關心該shapelet 代表的局部特征是否明顯出現(xiàn)在與其計算距離的時間序列中，而并不關心其出現(xiàn)的位置，這是因為最終的距離是取所有子序列與該shapelet 距離中的最小值.而對于不同的時間序列，取得最小距離的子序列的位置并不是固定的.由于shapelet 本身來自于時間序列，所以其本身就攜帶了位置信息，所以我們認為這種忽略位置信息的距離計算方式存在一定缺陷.

針對以上問題，我們設計了固定位置的距離度量方式，如下式所示：

其中，x，s，j和d(·，·)的含義同式(1)，由于s本身是某個時間序列的子序列，所以它擁有自己在原始時間序列數(shù)據(jù)中的起始位置，所以式(2)所表達的即是用x中與s位置對齊的子序列與s計算歐氏距離來作為x與s的距離.我們把這個距離稱作“定點距離”.

式(2)的計算加入了位置信息，既關注該時間序列是否具備shapelet 所代表的局部特征，還關注了其是否在對應的位置上與該局部特征有很好的近似性，同時，其時間開銷從O(km)降低至O(k)，其中k是shapelet的長度，m是原始時間序列的長度.所以，式(2)無論從最后的預測精度這一角度還是從時間開銷這一角度來說，都要優(yōu)于式(1).

考慮到時間序列數(shù)據(jù)經(jīng)常會發(fā)生遲滯，噪音等情況，我們對式(2)加入適當?shù)乃沙冢玫饺缦率?3)的距離計算公式：

上式中的x，s，m，j和d(·，·)的含義同式(2)，而l是左松弛因子，r是右松弛因子，都是超參數(shù).我們把這個距離稱作“定點浮動距離”.

3.2 固定候選shapelet 集中shapelet 的長度

基于shapelet 的算法因候選的shapelet 數(shù)量太大而具有很高的時間復雜度，而之所以需要如此龐大的候選shapelet 集，是為了保證局部特征的全覆蓋，因為你無法判定理想的局部特征所對應的shapelet 的長度應該是多少，所以只能選取所有長度的shapelet 來評估.這樣的話，我們時序數(shù)據(jù)的個數(shù)為n，長度為m，則根據(jù)2.2 節(jié)中的分析，整個數(shù)據(jù)集產(chǎn)生的shapelet 個數(shù)達到O(nm2)的量級，非常龐大，由于評估一個shapelet的時間開銷也不容小覷，所以單位評估時間被這個數(shù)量放大之后，時間開銷爆炸性增長.

然而，我們發(fā)現(xiàn)，如果我們使用“shapelet 轉換”的方式配合定點浮動距離(式(3))來構造分類器的話，我們可以通過固定shapelet 的長度來大幅縮減shapelet候選集的規(guī)模，接下來我們就來說明這件事.

我們看到“shapelet 轉換”的第一步是從候選shapelet中選擇判別性強的若干個shapelet 出來，第二步是基于這些選擇出來的shapelet 構造特征空間，將原始數(shù)據(jù)轉換至特征空間，第三步是在特征空間中對轉換后的數(shù)據(jù)進行分類.

在這個過程中，我們能夠發(fā)現(xiàn)最后對數(shù)據(jù)分類所倚賴的關鍵是構建特征空間的shapelet 的判別性.而shapelet 的判別性體現(xiàn)在，和該shapelet 同類的時間序列，與該shapelet 的距離要足夠小，而反之則要與該shapelet 的距離足夠大.而根據(jù)轉換的方式(參見2.3 節(jié))，當原始數(shù)據(jù)被轉換到特征空間之后，這就體現(xiàn)在和shapelet 同類的時間序列，轉換后在該shapelet 對應的坐標軸上的范數(shù)要比較小，而反之則對應的范數(shù)要比較大.

所以我們看到，在特征空間中分類的關鍵依據(jù)，其實質(zhì)是原始數(shù)據(jù)被轉換到特征空間之后的范數(shù).如果有兩個不同的特征空間，原始數(shù)據(jù)被轉換到它們之中后擁有相同的空間范數(shù)，那最終兩個特征空間中的分類依據(jù)就是相同的，分類效果也會大同小異，在某種程度上，我們可以認為這兩個特征空間是等價的.

現(xiàn)在假設原來的shapelet 候選集是A，如果我們找到一個A的很小的子集B，使得：從A里面找出的任意一組shapeletP，任意原始數(shù)據(jù)x被轉換到P構造的特征空間中的范數(shù)記錄為||x||P，B中都存在對應的一組shapeletQ，原始數(shù)據(jù)x被轉換到Q構造的特征空間中的范數(shù)記錄為||x||Q，且任意x，都有||x||P≈||x||Q，即這兩個特征空間是等價的.那么這樣的B顯然具備構造等價特征空間的能力.而如此一來，我們就能夠拋棄原來巨大的候選shapelet 集A，而只選用它的很小的子集B，這樣時間開銷會得到大幅降低.

我們現(xiàn)在就來證明這件事，即存在上述那樣一個小子集B，其具備構造同等特征空間的shapelet.此事關鍵在于證明如下的定理：

定理1.將一個shapelets分割成若干段C={s1，s2，…，sn}，使得它們按序拼接起來構成完整的s，我們稱這樣的C為s的一個劃分集.對任意時間序列x，其通過定點距離(式(2))轉換至s構造的特征空間中的歐氏范數(shù)記錄為||x||s，而其通過定點距離轉換至C構造的特征空間中的歐氏范數(shù)記錄為||x||C，則我們有||x||s=||x||C.

證明：不妨設s=(si，si+1，…，si+k)，其中i是s在原始時間序列中的起始位置，k+1 為其長度.令tj為C中sj的終止位置，且規(guī)定t0=i-1，tn=i+k，那么我們有sj=(stj-1+1,stj-1+1,···,stj).對于任意時間序列x，我們設x=(x1，x2，…，xm)，顯然m＞i+k.

則根據(jù)shapelet 轉換的規(guī)則，我們有：

證畢.

根據(jù)上述定理我們發(fā)現(xiàn)，在當前敘述背景下，一個shapelet 構造的特征空間，和它的劃分集構造的特征空間可以看成是等價的.盡管最后我們用作轉換的距離度量方式是定點浮動距離(式(3)) 而不是定點距離(式(2))，但是定點浮動距離只是定點距離的松弛版本，所以最后轉換后的數(shù)據(jù)的范數(shù)與定理1 中的范數(shù)并不會相差太遠，這樣我們依舊有||x||C≈||x||s.所以在定點浮動距離作為轉換坐標的計算公式的前提下，我們得到shapelet 構造的特征空間和它們的劃分集構造的特征空間是近似的.

而另一方面，每一個shapelet 都可以劃分為若干短的shapelet，所以我們只需要保留shapelet 候選集里足夠短的shapelet，就足夠我們找到好的shapelet 來構造好的特征空間了.如此一來，我們只需要選取長度為某個固定小數(shù)值的所有shapelet 來作為shapelet 候選集即可，這個數(shù)值一般取3 或者4 即可，我們把這樣的shapelet 稱作為“微局部特征”.我們將長度設置為3 或者4 是一種折衷，當長度設置比3 更小的時候，這些短shapelet 將失去統(tǒng)計意義，因為時序數(shù)據(jù)是連續(xù)的數(shù)據(jù)，在某個時間點的值并不能構成統(tǒng)計意義上的特征，它們提供的分類信息也因而不具備高可信度.而當長度比4 還大時，將無法覆蓋某些短shapelet，比如長度為4 的shapele，失去這些shapelet 會對分類結果造成影響.由這些微局部特征構成的集合正是我們需要尋找的原候選集的小子集.對于n個長度為m的時間序列構建的數(shù)據(jù)集，我們構建的shapelet 候選集只有O(nm)的規(guī)模，而不再是O(nm2)的量級.

3.3 shapelet 判別性的評價指標

在具備shapelet 候選集后，需要從中選取判別性強的shapelet 來作為構建特征空間的一組基底.

容易知道，選取shapelet 需要量化shapelet 的判別性能，目前普遍采用的做法是用最佳信息增益來量化shapelet 的判別性能.該做法如算法1 所示.

算法1.計算shapelet 的信息增益輸入：shapelet s，data set T=(X，Y)輸出：prime information gain of s 1) For each time series (x，y) in T 2) Calculate Ds，x)，namely distance between s and x；3) Depict D(s，x) with its label y in a real line r；4) End for 5) Find each possible segmentation in real line r to build C；6) Set prime_information_gain=0；7) For each segmentation c in C 8) Calculate information gain of c as g；9) If g＞prime_information_gain 10) Prime_information_gain=g；11) End if 12) End for 13) Return prime_information_gain；

從該算法中可以看到，如果要計算一個shapelet 的最佳信息增益，則需要計算所有“分割”的信息增益再挑出里面最大的.這樣做非常耗時，尤其當數(shù)據(jù)集里面數(shù)據(jù)比較多時，則可能的“分割”的數(shù)目指數(shù)增長，評價一個shapelet 的代價變得相當大.

為了避免這個問題，我們決定采用廣義雷利熵來作為shapelet 的判別性能的評價指標.對于一個實數(shù)軸上的二分類問題，我們假設兩類數(shù)據(jù)的集合分別為P和Q，則廣義雷利熵的計算公式如下式所示：

式中，μ(.)是均值函數(shù)，σ2(.)是方差函數(shù).

利用廣義雷利熵來作為判別指標后，我們有效避開了尋找最佳分割的過程，不再需要計算每種分割的信息增益來尋找最佳信息增益了，這種耗時的操作因此也被去除掉了.因為shapelet 的評估是一個單位操作，所以在單位操作上帶來的時間節(jié)省，被操作次數(shù)放大后，會得到非?？捎^的優(yōu)化效果.如此一來，評估一個shapelet 的算法如下所示.

算法2.計算shapelet 的判別性能(廣義雷利熵)輸入：shapelet s，data set T=(X，Y)輸出：prime information gain of s 1) For each time series (x，y) in T 2) Calculate D(s，x) by formula (3)；3) Depict D(s，x) with its label y in a real line r；4) End for 5) Calculate general Rayleigh quotient grq of points in r；6) Return grq；

3.4 特征空間中的分類器

正如我們2.3 節(jié)中所述，使用“shapelet 轉換”的方式必須承擔轉換后的數(shù)據(jù)在特征空間中的分布不定性這一代價，所以要想保證分類精度，需要在轉換后的特征空間中訓練多個類型不同的分類器，保證不遺漏可能的數(shù)據(jù)分布.但是這樣做的時間代價相當高.

自然地，我們想要避免這種操作來降低時間開銷.由于我們無法保證特征空間中的數(shù)據(jù)具有某種特定的分布特性，所以我們只能用不同類型的分類器把所有可能的分布特性都考慮進去.而造成這種現(xiàn)象的根源在于選擇shapelet 的環(huán)節(jié).我們確實選擇了最具判別性的shapelet 來作為特征空間的基底，但是卻忽略了它們的組合效應.在經(jīng)典的基于shapelet 的算法中，他們選擇最佳信息增益作為判別指標，這使得在“shapelet 轉換”后，特征空間的數(shù)據(jù)在每個坐標軸上的投影具有非常好的線性可分性，但是在每個坐標上的分量具有很好的線性可分性，并不能保證在整個空間上具備很好的線性可分性，這是問題的關鍵所在.

所以若我們可以保證原始數(shù)據(jù)被轉換到相應的特征空間之后，具備線性可分性這一分布特性.我們就能使用單個的SVM 去替代集成的分類器而避免訓練集成分類器這一耗時操作.

我們現(xiàn)在斷言，如果我們使用廣義雷利熵作為shapelet 的評價指標，那么高得分的shapelet 能夠保證特征空間中數(shù)據(jù)的線性可分性，這倚賴于如下的定理：

定理2.對于一個時序數(shù)據(jù)的二分類問題，shapelet的廣義雷利熵與特征空間中數(shù)據(jù)的線性可分性存在正相關.

證明：我們假設選擇了k個shapelet 構造好了一個特征空間，那我們要證明的是，將其中某個shapelets1替換為擁有更大廣義雷利熵的shapelets2，數(shù)據(jù)的線性可分性會提高.我們假設原始數(shù)據(jù)中有兩個類的時間序列，根據(jù)中心極限定理，它們通過這k個shapelet轉換到特征空間之后實際上形成了兩個隨機向量A，B，且A和B服從球形正態(tài)分布.

我們自然地按如下方式來定義這兩類數(shù)據(jù)的線性可分性：

式中，LS是線性可分性，P(·)是概率函數(shù).我們現(xiàn)規(guī)定μ(·)是均值函數(shù)，返回隨機向量的均值向量；σ2(·)為隨機向量的協(xié)方差矩陣的對角線函數(shù)，它返回由協(xié)方差矩陣的對角線構成的向量；[·]2是平方函數(shù)，對向量中每一維度的數(shù)據(jù)取平方來得到一新向量.根據(jù)A，B服從球形高斯分布，我們有：

式中，N(·，·)為正態(tài)分布的符號.結合式(7)，根據(jù)線性可分性的定義以及的取值范圍(式(6))，對于最佳的，我們顯然可以得到如下關系：

根據(jù)廣義雷利熵的計算式(式(5))，我們?nèi)糇C明任意0＜i＜k+1，|μi(A)-μi(B)|與式(6)中的線性可分性成正相關以及 σ2i(A)+σ2i(B)與其成負相關，則可完成定理的證明.

但這件事并不難，假設我們已經(jīng)擁有最佳的LS值(式(6))，現(xiàn)在將某個特定的μi(A)-μi(B)替換為擁有更大絕對值的 μi(A′)-μi(B′)，保持其它數(shù)值不變.我們不妨假設( μi(A′)-μi(B′))·＞0，因為若其小于0，我們只需將相應的取成相反數(shù)即可.由于(μi(A′)-μi(B′))·＞(μi(A)-μi(B))·→ ≥0，其他項不變，所以(μ(A′)-μ(B′))·＞(μ(A)-μ(B))·≥0.再根據(jù)正態(tài)分布的特性及式(8)，我們有：

這樣即證明了| μi(A)-μi(B)|與式(6)中的線性可分性成正相關，同樣地方法可以證明與 σ2i(A)+σ2i(B)式(6)中的線性可分性成負相關，此處不再贅述.

證畢.

定理2 為特征空間中的轉換后的數(shù)據(jù)的線性可分性這一分布特性提供了理論支撐，所以在我們提出的新算法中，當原始時間序列被轉換到特征空間之后，我們可以放心地使用單個的SVM 來執(zhí)行分類，而不再需要訓練集成分類器，這一結果極大優(yōu)化了時間性能.

4 算法框架與實驗結果

4.1 主體算法

我們在此節(jié)給出最終的算法框架，如算法3 和算法4 所示.

算法4.基于微局部特征的時序數(shù)據(jù)二分類算法(數(shù)據(jù)分類)輸入：shapelet queue Q，SVM classifier svm，data x輸出：class label of x 1) Transform x to the N-dimensional vector v by calculate distance with shapelet in Q by formula (3)；2) Use svm to classify v，get a label y；3) Return y.

4.2 實驗數(shù)據(jù)集

為了公平起見，我們選擇Bagnall 等人在其工作中所使用的數(shù)據(jù)集[1].他們在相關研究工作中精心篩選數(shù)據(jù)集以及各種算法，并做出了比較公平公正的對比，他們所使用的數(shù)據(jù)集也被選作時序數(shù)據(jù)分類算法社區(qū)的標準數(shù)據(jù)集[10].先對數(shù)據(jù)集做如下介紹：

Ham，火腿光譜圖數(shù)據(jù)，通過對光譜圖進行分類來判斷火腿的種類，訓練集109 個數(shù)據(jù)，測試集105 個數(shù)據(jù)，數(shù)據(jù)長度431.

MPOC，全稱Middle Phalanx Outline Correct，手指中部骨節(jié)的X 光投影輪廓圖.科學家根據(jù)該數(shù)據(jù)來判斷人們所處的年齡階段，訓練集600 個數(shù)據(jù)，測試集291 個數(shù)據(jù)，數(shù)據(jù)長度80.

Eq，全稱Earthquakes，用傳感器捕捉的地震波數(shù)據(jù)，用來判斷近期內(nèi)是否會有地震發(fā)生，數(shù)據(jù)來自于北加利福利亞地震研究中心.訓練集322 個數(shù)據(jù)，測試集139 個數(shù)據(jù)，數(shù)據(jù)長度512.

Herring，鯡魚的耳石輪廓，該數(shù)據(jù)用于生物多樣性研究，通過耳石輪廓對應的時序數(shù)據(jù)來判定鯡魚生活的地區(qū).訓練集64 個數(shù)據(jù)，測試集64 個數(shù)據(jù)，數(shù)據(jù)長度512.

IPD，即Italy Power Demand，意大利人民不同季度生活用電時序數(shù)據(jù)，不同類別的時序數(shù)據(jù)對應不同季度的用電水平.訓練集67 個，測試集1029 個，數(shù)據(jù)長度24.

Wine，葡萄酒的光譜圖，光譜圖上不同種類的時序數(shù)據(jù)對應不同種類的葡萄酒.訓練集57 個數(shù)據(jù)，測試集54 個數(shù)據(jù)，數(shù)據(jù)長度234.

用于做實驗的數(shù)據(jù)集來自于實際應用的各方各面，包括天文地理，衣食住行等多個領域，也從側面反映了時序數(shù)據(jù)有著廣泛的應用.

4.3 對比算法與算法超參

本文針對基于shapelet 的時序分類算法進行分析與改進，旨在提升算法的分類精度和降低算法的時間開銷，所選對比算法為基于shapelet 的時序分類算法中的優(yōu)秀算法，介紹如下：

FS，該算法專注于時間開銷，是現(xiàn)有的基于shapelet的算法中平均時間開銷比較低的，但是其犧牲了部分精度，采用近似的方法選取shapelet[7].

LS，是用學習的方式獲取shapelet 的代表算法，通過把獲取判別性shapelet 這一難題轉換為優(yōu)化問題，并用梯度下降來習得最優(yōu)shapelet，具有非常不錯的時間開銷和分類精度[8].

ST，是當今主流的基于shapelet 的時序數(shù)據(jù)分類算法，它通過shapelet 將原始數(shù)據(jù)轉換至特征空間，在特征空間里訓練集成分類器進行分類，擁有較高的時間復雜度，但是分類精度屬于領域內(nèi)的頂尖[12].

COTE，是基于shapelet 的集成算法中的集大成者，除了集成基于shapelet 的時序數(shù)據(jù)分類算法，也集成了其它類型的時序數(shù)據(jù)分類算法，因此是四個對比算法中時間復雜度最高的，同時也是分類精度最好的[13].

值得一提的是，在Bagnall 等人的工作中，ST 和COTE 不僅是基于shapelet (局部特征)的時序數(shù)據(jù)分類算法中的最好的，也是所有時序數(shù)據(jù)分類算法中分類精度最好的[1].詳情請見圖1[1].

圖1 最佳算法在UCI 數(shù)據(jù)集上的分類精度平均排名[1]

另外，我們提出的基于微局部特征的時序數(shù)據(jù)二分類算法，它的英文名稱為“mini-shapelet based algorithm”，簡寫為“MS”.MS 的超參選擇集如表1所示.

表1 MS 的超參取值

4.4 分類性能對比

關于分類性能，我們延用時序分類算法社區(qū)里面的硬指標，即分類精度對比以及分類精度的排名對比，具體的對比數(shù)據(jù)如表2，表3以及圖2所示.

表2 分類精度對比

表3 分類精度排名對比

圖2 算法分類精度點線對比圖

從表2以及表3中可以看出，在所有測試數(shù)據(jù)集上面，基于微局部特征的分類算法(MS)都取得了最優(yōu)的分類精度，并且在某些數(shù)據(jù)集上還具有非常明顯的分類精度優(yōu)勢，比如Herring 和Eq 這兩個數(shù)據(jù)集.綜合來看，相對于其它4 種經(jīng)典的基于shapelet 的分類算法，基于微局部特征的分類算法顯而易見地具有最佳的分類能力.而在Wine 這個數(shù)據(jù)集上，它甚至取得了無任何錯誤的分類結果，體現(xiàn)了其極強的分類能力.因而綜上所述，基于微局部特征的時序數(shù)據(jù)分類算法相較于4 種對比算法有明顯的分類精度優(yōu)勢.

從圖2中我們可以觀察出四種對比算法分類性能不太穩(wěn)定，都有大幅度的波動.而相比之下，基于微局部特征的分類算法(MS)具有較為穩(wěn)定的分類性能，其折線波動較小，相對來說比較平穩(wěn).所以基于微局部特征的時序數(shù)據(jù)分類算法在分類表現(xiàn)上穩(wěn)定性更好，且具有穩(wěn)定的分類性能優(yōu)勢.

4.5 時間開銷對比

關于時間開銷，因為5 個算法都是使用eager learning 的方式進行分類，而且其主要的時間都用在構造分類器上，所以我們主要比較它們的構建分類器的時間.我們在同樣的硬件條件(內(nèi)存：8 GB；CPU：2.5 GHz)及軟件條件下(OS：Win 10；platform：JAVA)進行實驗，具體數(shù)據(jù)如表4及表5所示.

表4 時間消耗對比(單位：秒)

表5 時間消耗排名對比(升序)

從表4和表5中可以觀察到，除了MPOC 和IPD這兩個數(shù)據(jù)集外，基于微局部特征的分類算法(MS)在剩余數(shù)據(jù)集上都具有最小的時間開銷，而在MPOC 和IPD 這兩個數(shù)據(jù)集上，也僅次于FS 這一算法，但是FS在MPOC 和IPD 上的精度遠不如基于微局部特征的時序數(shù)據(jù)分類算法.再結合表5中的平均排名，我們可以認為相對于其它4 個對比算法，在保持最高分類精度的同時，基于微局部特征的時序數(shù)據(jù)分類算法具有最佳的時間性能.

5 結語

本文針對當前基于局部特征的時序數(shù)據(jù)分類算法中存在的問題與挑戰(zhàn)，在充分的理論依據(jù)的支撐下，使用縮減候選集，調(diào)整判別性評定指標，修改距離度量以及替換集成分類器4 項技術設計了高效實用的新型算法.該基于微局部特征的時序數(shù)據(jù)分類算法在實驗數(shù)據(jù)集上表現(xiàn)出良好的分類性能和時間性能.通過實驗對比，也證明了其對當前研究領域內(nèi)存在的分類精度不足以及時間開銷過高等問題有不錯的改進.