丁智慧，喬鋼柱，程 譚，宿 榮

中北大學(xué) 大數(shù)據(jù)學(xué)院，太原030051

時(shí)間序列是隨時(shí)間觀測(cè)和變化的一系列時(shí)值，廣泛用于金融行業(yè)[1]、醫(yī)療領(lǐng)域[2]、天氣預(yù)測(cè)[3]等。近年來隨著時(shí)間積累和數(shù)據(jù)類別的增長(zhǎng)，時(shí)間序列的數(shù)量和維度也大量增長(zhǎng)，海量高維數(shù)據(jù)的分析處理成了目前各個(gè)行業(yè)面臨的挑戰(zhàn)。時(shí)間序列數(shù)據(jù)的分類問題是數(shù)據(jù)挖掘中一類重要方法，其目的是從已標(biāo)定類別的訓(xùn)練集中提取出帶有能夠區(qū)分類別的顯著性特征，分類器根據(jù)這些特征與未標(biāo)記類別的時(shí)間序列之間的相似性進(jìn)行分類。根據(jù)文獻(xiàn)[4]將時(shí)間序列分類算法分為基于全局特征的算法、基于局部特征的算法和集成算法?；谌痔卣鞯乃惴ㄊ菍⒄麠l時(shí)間序列作為特征進(jìn)行相似性比較，解決該類問題最具代表的方法是基于歐氏距離（Euclidean Distance）和動(dòng)態(tài)時(shí)間規(guī)整（Dynamic Time Wrapping，DTW）的最近鄰（1-NN）算法，但采用歐氏距離會(huì)因?yàn)橄辔黄朴绊懡Y(jié)果，而DTW 算法消耗大量的時(shí)間和空間，只適用于小型數(shù)據(jù)集，對(duì)海量數(shù)據(jù)無能為力。近些年的研究均集中于尋找更優(yōu)秀的距離度量方法[5-8]，例如Batista 等人[6]提出復(fù)雜性不變的度量方式（CID）、Jeong 等人[8]提出全局加權(quán)DTW（WDTW）增加了一個(gè)基于扭曲路徑中各點(diǎn)之間的扭曲距離的乘法權(quán)重懲罰。基于局部特征的算法將時(shí)間序列的一部分作為特征，有分段聚集近似（PAA）[9]、符號(hào)聚集近似（SAX）[10]等分段表示方法，以及通過選擇多個(gè)區(qū)間并使用匯總測(cè)度作為特征的分類方法[11]，基于shapelets 的分類算法[12]枚舉出數(shù)據(jù)集中所有的子序列，通過信息增益選擇最佳shapelets 作為決策樹節(jié)點(diǎn)分類準(zhǔn)則，具有分類精度高、速度快、可解釋性強(qiáng)的優(yōu)點(diǎn)。

基于集成的算法是集成多種時(shí)間序列分類方法，Bagnall 等人[13]提出COTE 使用了35 種分類器，具有很高的分類精度，但相對(duì)耗時(shí)嚴(yán)重。本文主要研究基于shapelets的時(shí)間序列分類算法，并證明提出的算法在保證分類精度的前提下大幅度減少耗時(shí)。

shapelets是時(shí)間序列的子序列，是最能代表其所屬類別的時(shí)間序列，它可以較為充分地說明各個(gè)類別之間的差異，使得分類結(jié)果具有更強(qiáng)的可解釋性。近年來使用shapelets 和序列之間的相似性作為判別特征來解決時(shí)間序列的分類問題已經(jīng)成為當(dāng)前一個(gè)新的研究熱點(diǎn)。基于shapelets的分類算法最初由Ye等人[12]所提出，它將shapelets的發(fā)現(xiàn)過程嵌入到?jīng)Q策樹中，并使用信息增益來評(píng)估對(duì)象的質(zhì)量，提高了分類的準(zhǔn)確性，但該分類算法時(shí)間復(fù)雜度為O(n2m4)，這使得該方法在大部分情況下無法適用。

針對(duì)上述方法中候選集規(guī)模龐大、計(jì)算耗時(shí)長(zhǎng)的問題，Rakthanmanon 等人[14]提出一種基于符號(hào)聚合近似（SAX）離散化表示的快速shapelets 發(fā)現(xiàn)算法（Fast Shapelete，F(xiàn)S）；Grabocka等人[15]提出了Learned Shapelet（LS）算法，該算法采用啟發(fā)式梯度下降shapelets搜索過程。李禎盛等人[16]將轉(zhuǎn)換過程進(jìn)行主成分分析進(jìn)行降維，該方法雖然縮短了時(shí)間但降維造成了信息缺失，從而降低了分類準(zhǔn)確性。以上算法在shapelets 提取過程中均同時(shí)構(gòu)造分類器，一定程度上受應(yīng)用場(chǎng)景的限制。

Lines 等人[17]提出的shapelets 轉(zhuǎn)換技術(shù)將shapelets的發(fā)現(xiàn)過程與分類器相分離，從數(shù)據(jù)集中選取出質(zhì)量最好的k個(gè)shapelets，接著將每一條時(shí)間序列到這些shapelets的距離轉(zhuǎn)換成該時(shí)間序列的k個(gè)屬性，將原數(shù)據(jù)集轉(zhuǎn)換到新的數(shù)據(jù)空間，在提高精度的同時(shí)保留了shapelets的可解釋性，可以根據(jù)具體情況結(jié)合不同的分類器使用。

Ji 等人[18]使用子類分割方法對(duì)訓(xùn)練機(jī)進(jìn)行采樣，確定局部最遠(yuǎn)偏移點(diǎn)（LFDPs），并選擇兩個(gè)不相鄰的LFDPs 之間的子序列作為shapelets 候選。Hills 等人在文獻(xiàn)[19]提出對(duì)shapelets 進(jìn)行聚類以縮減候選集，并同時(shí)使用三種不同的方法衡量shapelets 的質(zhì)量。原繼東等人[20]針對(duì)上述方法中候選集大量相似和無法確定k取值的問題提出了shapelets剪枝和覆蓋方法，上述兩種方法均是在shapelets完全提取后進(jìn)行剪枝操作，導(dǎo)致所耗時(shí)間甚至多于原始shapelets發(fā)現(xiàn)時(shí)間。

雖然上述針對(duì)shapelets 轉(zhuǎn)換技術(shù)的研究都能在一定程度上提升運(yùn)算速度，但隨著數(shù)據(jù)規(guī)模的快速增長(zhǎng)，傳統(tǒng)方法由于逐個(gè)計(jì)算候選集中每一個(gè)子序列的質(zhì)量，再逐一比較選擇出最好shapelets，因此總體而言仍存在著計(jì)算耗時(shí)的問題。針對(duì)上述缺點(diǎn)，本文提出了一種基于改進(jìn)LSH的shapelets轉(zhuǎn)換方法，該方法先進(jìn)行一次預(yù)掃描，根據(jù)形狀快速去除相似冗余，隨后采用文獻(xiàn)[20]所提的shapelets覆蓋的方法確定最終shapelets集合，最后進(jìn)行數(shù)據(jù)集轉(zhuǎn)換。該算法由于先根據(jù)形狀的相似性過濾挑選候選序列，因而無需進(jìn)行大量shapelets質(zhì)量計(jì)算，從而大大降低了計(jì)算耗時(shí)。

1 相關(guān)知識(shí)與定義

定義1（時(shí)間序列及子序列）時(shí)間序列T=(t1,t2,…,tn)是按相等的時(shí)間間隔采樣的數(shù)據(jù)點(diǎn)構(gòu)成的序列，其中ti(i∈1,2,…,n)是任意的實(shí)數(shù)，n為時(shí)間序列的長(zhǎng)度。子序列S=(ti,ti+1,ti+2,…,ti+l-1)是一條時(shí)間序列中從位置開始，長(zhǎng)度為l的一段連續(xù)的序列，其中1 ≤i≤m-l+1。

定義2（時(shí)間序列的距離）將長(zhǎng)度為m的兩條時(shí)間序列A=(a1,a2,…,am)和B=(b1,b2,…,bm)看作向量，它們之間的距離Dist(A,B)用歐幾里德范數(shù)表示，如式（1）：

定義3（子序列和時(shí)間序列的距離）對(duì)于長(zhǎng)度不同的子序列S和時(shí)間序列T，距離定義為S與T中長(zhǎng)度與S相同的子序列的距離的最小值，即，其中Ti表示T中長(zhǎng)度與S相同的所有子序列。

定義4（信息增益）設(shè)數(shù)據(jù)集D被劃分為數(shù)據(jù)子集D1和D2，則其信息增益為：

其中，n、n1和n2分別表示數(shù)據(jù)集D、D1和D2的大小。E(D)表示D的熵，計(jì)算如下：

式中，pc是集合D中類標(biāo)號(hào)為c的序列的概率。

定義5（shapelet）[12]定義分裂點(diǎn)為一個(gè)二元組＜S,δ＞，由子序列S和距離閾值δ組成的，根據(jù)S與數(shù)據(jù)集中每一條時(shí)間序列之間的距離是否大于δ將時(shí)間序列數(shù)據(jù)集D分為DL和DR，當(dāng)信息增益最大時(shí)的即為shapelet，此時(shí)的距離閾值δ=dosp即：

圖1 展示的是Gun/NoGun 問題中的兩條質(zhì)量最好的shapelet，從形狀上來看，shapelets 就是形狀獨(dú)特、足以區(qū)分不同類別的子序列。

圖1 Gun/NoGun問題中的shapelets

定義6（局部敏感哈希）[21]對(duì)于哈希家族H，如果任意兩個(gè)對(duì)象x、y滿足如下兩個(gè)條件，則認(rèn)為H是敏感的。

其中，d1＞d2，p1＞p2，d(x,y)表示x與y之間的距離，分別表示對(duì)x和y進(jìn)行哈希變換。

局部敏感哈希函數(shù)在降維的同時(shí)能有效保持兩個(gè)高維數(shù)據(jù)之間的距離，第一個(gè)條件保證了兩個(gè)距離相近的向量會(huì)以很高的概率映射為同一個(gè)Hash 值，第二個(gè)條件則表明兩個(gè)距離較遠(yuǎn)的向量映射為同一個(gè)Hash值的概率會(huì)很低。

定義7（LSH 函數(shù)族）本文中采用歐氏距離度量下的Hash函數(shù)[22]：

其中，ω是窗口長(zhǎng)度參數(shù)（文獻(xiàn)[23]推薦用ω=4），ai是一個(gè)d維向量，每一維的值都滿足標(biāo)準(zhǔn)正態(tài)分布，bi滿足的均勻分布。

2 基于LSH的shapelets轉(zhuǎn)換算法（LSHST）

本文是基于Lines 等人[17]提出shapelets 變換算法（簡(jiǎn)稱ST）的改進(jìn)，該算法首先通過單次掃描訓(xùn)練集，找到最佳的k個(gè)shapelets，然后通過5 折交叉驗(yàn)證方法得到參數(shù)k的最優(yōu)值，用top-kshapelets得到一個(gè)新的數(shù)據(jù)集，其中新數(shù)據(jù)集中每一條時(shí)間序列有k個(gè)特征，每條數(shù)據(jù)的k個(gè)特征都代表了時(shí)間序列與shapelets 之間的距離。最后將不同的分類器與新數(shù)據(jù)集結(jié)合使用進(jìn)行時(shí)間序列分類。ST 方法的主要優(yōu)點(diǎn)在于將shapelets選擇過程單獨(dú)分離出來，可結(jié)合不同分類器靈活使用。然而該算法在運(yùn)行時(shí)間上消耗巨大，其中尋找top-kshapelets是最為耗時(shí)的部分：首先獲取數(shù)據(jù)集的所有子序列，其次對(duì)子序列計(jì)算其到每一條時(shí)間序列的距離用以衡量shapelets的質(zhì)量，最后去除來自同一序列且有重疊的冗余序列后，選擇質(zhì)量最好的k個(gè)shapelets。假設(shè)在數(shù)據(jù)集D中有長(zhǎng)度為m的時(shí)間序列n條，那么這個(gè)數(shù)據(jù)集一共有nm2條子序列，ST 算法中的shapelets 提取的時(shí)間復(fù)雜度為O(n2m4)，但最終從nm2條子序列中只選擇幾條到幾十條作為shapelets，由此可見，ST 算法的shapelets 提取過程中對(duì)大量相似冗余序列進(jìn)行了重復(fù)計(jì)算，導(dǎo)致時(shí)間消耗過大。

針對(duì)以上所提問題，本文提出一種shapelets提取的加速策略，引入局部敏感哈希函數(shù)（LSH）先過濾掉大量形狀上相似的候選序列，再計(jì)算剩余序列質(zhì)量，精簡(jiǎn)計(jì)算量，加快shapelets的提取過程。

2.1 用于shapelets過濾的改進(jìn)LSH算法

局部敏感哈希最早在1998 年由Indyk 提出[21]，基本思想是利用哈希函數(shù)值使得相似的數(shù)據(jù)以很高的概率發(fā)生沖突從而能夠被檢測(cè)到。歐氏局部敏感哈希（Exact Euclidean Locality Sensitive Hashing，E2LSH）是LSH 在歐氏空間的一種隨機(jī)化實(shí)現(xiàn)方法，由Datar 等人在文獻(xiàn)[22]中提出，利用基于p-stable分布的位置敏感函數(shù)對(duì)高維數(shù)據(jù)進(jìn)行降維映射，使原始空間中距離很近的兩個(gè)序列經(jīng)映射操作后依然很近。

LSH 算法的提出用來解決海量高維數(shù)據(jù)的最近鄰問題：首先將原始高維數(shù)據(jù)點(diǎn)經(jīng)過LSH函數(shù)，根據(jù)不同函數(shù)值映射到一張哈希表中的不同位置（哈希桶），每一個(gè)哈希桶中的點(diǎn)大概率相似，待到查找最近鄰時(shí)，將待查找的點(diǎn)經(jīng)過同樣的哈希函數(shù)映射到同一個(gè)哈希表的某一個(gè)桶中，最后直接對(duì)該桶中的數(shù)據(jù)進(jìn)行查找，大大提升了查找效率。

為了提升LSH 算法的準(zhǔn)確性，使得p1更大，p2更小，文獻(xiàn)[21]提出了增強(qiáng)LSH算法：定義了函數(shù)組g(·)，由同一個(gè)哈希函數(shù)族中獨(dú)立隨機(jī)地選擇k個(gè)哈希函數(shù)組成，即，只有k個(gè)hi()全部對(duì)應(yīng)相等時(shí)，才映射為同一個(gè)Hash值，該操作降低了false negtive rate（本身相似的序列被判斷為不相似），但這樣增加了false positive rate（本來不相似的兩條序列被判斷為是相似的），所以采用L個(gè)函數(shù)g1(·),g2(·),…,gL(·)，對(duì)長(zhǎng)度為l的全部子序列分別進(jìn)行L次哈希計(jì)算，建立L個(gè)哈希表，兩個(gè)序列只要在任意一個(gè)哈希表中被映射為同一個(gè)Hash值，就認(rèn)為這兩條序列是相似的。假設(shè)兩條等長(zhǎng)的序列v1和v2，經(jīng)過相同LSH哈希函數(shù)hi()的映射計(jì)算的值相等的概率為P，即，那么，經(jīng)過上述增強(qiáng)LSH算法，這兩條數(shù)據(jù)被認(rèn)為是近鄰的概率為。

本文所提LSHST算法就是利用LSH哈希表的每一個(gè)哈希桶中數(shù)據(jù)大概率相似、不同哈希桶的數(shù)據(jù)大概率不相似的特點(diǎn)對(duì)候選集進(jìn)行過濾，希望經(jīng)過LSH哈希后得到形狀上互不相似幾條序列。但是上述增強(qiáng)LSH 算法對(duì)于每一長(zhǎng)度的序列都需要建立L個(gè)哈希表，造成大量的空間消耗，同時(shí)在本文算法中，只關(guān)心經(jīng)哈希函數(shù)映射后互不相似的序列，而相似的序列是將要拋棄的部分，所以提出了逐級(jí)過濾LSH，具體算法如下：

（1）同樣生成L個(gè)函數(shù)g1(·),g2(·),…,gL(·)，先對(duì)長(zhǎng)度為l的子序列通過函數(shù)g1(·)進(jìn)行第一次LSH 映射，建立第一個(gè)哈希表T1。

（2）遍歷哈希表T1，從每一個(gè)哈希桶中挑選u條序列作為代表通過函數(shù)g2(·)進(jìn)行第二次映射，建立第二個(gè)哈希表T2，同時(shí)刪除第一個(gè)哈希表T1，釋放內(nèi)存。

（3）遍歷T2，從T2的每個(gè)桶中選擇u條序列進(jìn)行第三次映射，建立T3，刪除T2。這樣重復(fù)至第L次結(jié)束，哈希表TL中的所有序列即為逐級(jí)過濾的最終結(jié)果，該過程如圖2所示。

圖2 LSH逐級(jí)過濾過程示意圖

逐級(jí)過濾LSH在兩個(gè)方面做了提升：減少了空間開銷同時(shí)減少了計(jì)算量。既然只要兩條序列同時(shí)被映射在任意一個(gè)哈希表的同一個(gè)桶中，這兩條序列就相似，就可以提前對(duì)相似序列作剪枝操作，拋棄掉大量已經(jīng)被證明是相似的序列，這樣并不會(huì)影響TL最終留下的序列之間不相似的概率，節(jié)省了下一次映射過程中對(duì)這些無用序列的計(jì)算，大幅度提升運(yùn)算效率。

2.2 LSHST算法描述

本節(jié)具體描述基于LSH 的shapelets 轉(zhuǎn)換算法（LSHST）。整體思路是首先掃描數(shù)據(jù)集提取所有子序列，對(duì)數(shù)據(jù)集子序列集合進(jìn)行篩選過濾，得到形狀上具有代表性的shapelets候選集；其次計(jì)算候選集中每一條序列的質(zhì)量，從中挑選最終的shapelets；最后進(jìn)行shapelets轉(zhuǎn)換。下面具體展開闡述。

第一步過濾是利用2.1 節(jié)所提出的逐級(jí)過濾LSH算法去除shapelets候選集中在形狀上的相似冗余序列，留下形狀上互不相同的部分序列。在逐級(jí)過濾的過程中，怎樣從上一個(gè)哈希表的桶中選擇u條序列進(jìn)行下一次映射是需要考慮的問題。由于映射到同一桶中的子序列具有很高的相似程度，在后續(xù)計(jì)算質(zhì)量時(shí)幾乎差距不大，為了避免序列之間耗時(shí)的比較計(jì)算，所以在選擇代表序列時(shí)采用隨機(jī)選取的方式。以長(zhǎng)度l為10的全部子序列為例，圖3 展示的是從哈希表T1中隨機(jī)挑選的兩個(gè)哈希桶中的全部序列，可以看出，每一個(gè)桶中的序列形狀上高度相似，選擇哪一條作為代表序列區(qū)別并不大，其中加粗的序列為隨機(jī)挑選的代表序列（u=1 時(shí)）。

圖3 不同哈希桶中序列示意圖

經(jīng)過逐級(jí)過濾后得到無冗余序列的候選集，接下來計(jì)算每一條序列的質(zhì)量，本文使用信息增益作為衡量shapelets質(zhì)量的方法，然后采用文獻(xiàn)[20]所提的shapeles覆蓋方法根據(jù)質(zhì)量進(jìn)一步篩選確定最終的shapelets。表1為5個(gè)數(shù)據(jù)集在過濾過程中候選集中子序列數(shù)量的變化，表中第三列為經(jīng)過LSH逐級(jí)過濾后的候選集中序列的數(shù)量，可以看出，該步驟過濾掉大量相似序列，只需計(jì)算幾十或者幾百條序列的質(zhì)量便能得到shapelets，節(jié)省了時(shí)間。

表1 LSHST算法在過濾過程中序列數(shù)量變化表

2.3 LSHST算法實(shí)現(xiàn)

LSHST算法偽代碼見算法1。

算法1LSHST（data，L，u，minLength，maxLength）

輸入：數(shù)據(jù)集data，LSH哈希映射循環(huán)次數(shù)L，每個(gè)桶中隨機(jī)選取的子序列條數(shù)u，shapelets長(zhǎng)度最大值和最小值

輸出：轉(zhuǎn)換后的數(shù)據(jù)集

算法1描述了基于LSH的shapelets轉(zhuǎn)換過程，對(duì)長(zhǎng)度從minLength 到maxLength 的子序列分別進(jìn)行過濾（第4行～第13行），首先生成Hash函數(shù)族（第5行），所有子序列依次進(jìn)行LSH映射，存儲(chǔ)到哈希表Table中（第6行）；其次循環(huán)L-1 次更新哈希表Table（第7 行～第10行），每次更新都重新生成不同的Hash函數(shù)族（第8行）；接著將每一個(gè)長(zhǎng)度挑選出來的shapelets 候選序列合并到一個(gè)數(shù)據(jù)集中（第10行）；最終集合kShapelets就是過濾后的shapelets 候選集合。上述過濾過程無需計(jì)算shapelets候選序列的質(zhì)量，每次循環(huán)序列的數(shù)量均會(huì)減少很多，相應(yīng)地節(jié)省了大量的計(jì)算。過濾完成后進(jìn)一步進(jìn)行Shapeles 覆蓋[20]選擇shapelets，此時(shí)的候選序列僅有幾十或幾百條，大大縮短了運(yùn)行時(shí)間。最后返回轉(zhuǎn)換后的數(shù)據(jù)集（第13行）。其中哈希表更新算法見算法2。

算法2UpdateTable（Table，LSHfamily，u）

輸入：待更新哈希表Table，Hash 函數(shù)族LSHfamily，每個(gè)桶中隨機(jī)選擇子序列數(shù)量u

輸出：更新過后的哈希表newTable

算法2中首先初始化一個(gè)新的哈希表newTable（第1 行），其次遍歷待更新的哈希表Table（第2 行～第10行），依次提取出每一個(gè)哈希桶bucket 中的子序列集合seriesLists（第6 行），從該集合中隨機(jī)選擇u條序列uLists（第9行），將其插入到新的哈希表newTable中，遍歷結(jié)束返回newTable。

由于在哈希表更新過程中每個(gè)桶中只選擇u條序列進(jìn)行新一輪映射，所以新建的哈希表規(guī)模遠(yuǎn)遠(yuǎn)小于原哈希表，并且在提取出每個(gè)哈希表中的序列后，就會(huì)釋放掉該哈希表所占用的空間，由此可見對(duì)長(zhǎng)度為i的所有子序列的逐級(jí)過濾過程中，所占用的最大空間即為第一次建立哈希表所占的空間。而緊接著對(duì)長(zhǎng)度為i+1的子序列進(jìn)行過濾時(shí)，長(zhǎng)度為i的子序列哈希表也同樣被釋放，所以LSHST算法最終的空間復(fù)雜度為O(nm)，可見該算法大大節(jié)省了空間消耗。

3 實(shí)驗(yàn)與結(jié)論

本章所涉及所有算法均在Weka框架下使用Java代碼實(shí)現(xiàn)，為了全面衡量算法效果，根據(jù)數(shù)據(jù)集的規(guī)模，從UCR數(shù)據(jù)集中分別選擇6個(gè)較小和6個(gè)較大（見表2）的數(shù)據(jù)集，作為本章實(shí)驗(yàn)的數(shù)據(jù)集對(duì)前文所述算法進(jìn)行測(cè)試和評(píng)估。

表2 數(shù)據(jù)集

3.1 參數(shù)選擇

在建立子序列過濾的過程中，為了提高每一個(gè)桶中序列相似的概率，本文引入了哈希映射的次數(shù)L和隨機(jī)選取子序列的數(shù)量u，這兩個(gè)參數(shù)會(huì)決定shapelets的數(shù)量和質(zhì)量，進(jìn)而影響分類效果和轉(zhuǎn)換時(shí)間。為分析參數(shù)u和L的變化對(duì)分進(jìn)行了測(cè)試，結(jié)果如圖4所示，可以看出算法的分類準(zhǔn)確率的影響，分別對(duì)參數(shù)在不同組合情況下算法準(zhǔn)確性基本穩(wěn)定，不會(huì)因參數(shù)L和u的變化產(chǎn)生明顯的趨勢(shì)變化。

圖4 LSHST算法精度隨L和u的變化曲線

為分析參數(shù)變化對(duì)計(jì)算耗時(shí)的影響，本文首先對(duì)參數(shù)L不同取值情況下計(jì)算耗時(shí)情況進(jìn)行了測(cè)試，結(jié)果如圖5所示，實(shí)驗(yàn)結(jié)果表明參數(shù)L的變化對(duì)時(shí)間有明顯的影響。在u=1 的情況下，分別對(duì)兩組數(shù)據(jù)集進(jìn)行了實(shí)驗(yàn)。從圖5（a）可看出在規(guī)模較小的數(shù)據(jù)集上，所用時(shí)間消耗隨著L的增大總體呈減小趨勢(shì)，但L=45 變化趨于平緩，L=55 后會(huì)有一定程度的上升。圖5（b）所示在規(guī)模較大的數(shù)據(jù)集上，耗時(shí)曲線持續(xù)下降，L=50 時(shí)大部分?jǐn)?shù)據(jù)集變化基本平緩。

圖5 LSHST算法時(shí)間消耗隨L 的變化曲線

為整體觀察u和L對(duì)時(shí)間消耗的影響，本文同時(shí)也對(duì)u和L不同組合情況下的計(jì)算耗時(shí)做了對(duì)比實(shí)驗(yàn)，其中取u={1，2，3}，L={20，30，40，50}，實(shí)驗(yàn)結(jié)果如表3，其中表現(xiàn)最好的參數(shù)組合為u=1,L=50。

表3 LSHST算法在參數(shù)L 和u 的不同組合情況下的耗時(shí) s

3.2 算法評(píng)估

為綜合評(píng)價(jià)LSHST 算法的性能，設(shè)計(jì)了兩組對(duì)比實(shí)驗(yàn)，其一是與shapelets 轉(zhuǎn)換算法作對(duì)比，另一個(gè)是與其他經(jīng)典分類算法作對(duì)比，在前一實(shí)驗(yàn)所確定的最佳參數(shù)組合u=1 和L=50 基礎(chǔ)上將LSHST 算法與多種分類器組合，進(jìn)行分類準(zhǔn)確率和算法耗時(shí)的測(cè)試。

3.2.1 LSHST與其他shapelets轉(zhuǎn)換算法的比較

為了說明本文所提算法在基于shapelet 轉(zhuǎn)換的算法中處于領(lǐng)先水平，對(duì)比了LSHST 和ShapaletSelection（ST）[17]、ClusterShapelet（CST）[18]以 及Fast Shapelet Selection（FSS）[19]這三種shapelets 轉(zhuǎn)換算法，分別結(jié)合1-NN、C4.5、Naive Bayes（NB）、Support Vector Machines with Linear（SVML）、random forest（with 500 trees）（RandF）、Rotation Forest（with 50 trees）（RotF）這6 個(gè)分類器以計(jì)算平均分類精度，結(jié)果如表4，LSHST 算法在12個(gè)數(shù)據(jù)集中的7個(gè)數(shù)據(jù)集上表現(xiàn)優(yōu)于其他方法，在SonyAIBORobotSurface 數(shù)據(jù)集上相比FSS、ST、CST 分別提升了5.08、12.94和19.95個(gè)百分點(diǎn)，在TwoLeadECG數(shù)據(jù)集上分別提升了16.52、14.1和4.71個(gè)百分點(diǎn)，可以看出LSHST在分類精度上表現(xiàn)良好。

表4 LSHST、FSS、ST、CST算法的平均分類精度%

同時(shí)比較了這4 種方法的shapelets 轉(zhuǎn)換時(shí)間，如表5 所示，ST 和CST 隨著數(shù)據(jù)集規(guī)模的增長(zhǎng)，時(shí)間消耗也巨幅增長(zhǎng)，而LSHST 算法在時(shí)間消耗上比ST 提升了10～8 000 倍，CST 的時(shí)間消耗最長(zhǎng)達(dá)到兩天以上，在FiftyWords數(shù)據(jù)集上耗時(shí)是LSHST的16 000多倍。FSS是目前shapelets 轉(zhuǎn)換方法中最快的，從表5 中可得LSHST與FSS在規(guī)模較小的數(shù)據(jù)集上耗時(shí)相當(dāng)，但是在規(guī)模較大的數(shù)據(jù)集上，LSHST可以將耗時(shí)減少至FSS的一半以上，尤其在NonInvasiveFetalECGThorax 和Fifty-Words 數(shù)據(jù)集上FSS 的耗時(shí)分別是LSHST 的4.8 和8.5倍，這表明LSHST在大規(guī)模數(shù)據(jù)上具有較高的適用性，在保證有較好分類精度的前提下耗時(shí)最短。

表5 LSHST、FSS、ST、CST算法的shapelets轉(zhuǎn)換時(shí)間 s

3.2.2 LSHST與其他經(jīng)典分類算法的比較

為了說明LSHST 在時(shí)間序列分類方面的先進(jìn)性，對(duì)比了幾種經(jīng)典的分類方法，其中包括基于歐氏距離的最近鄰算法（DTW_1NN）、基于shapelets 學(xué)習(xí)的LS 算法[15]、基于SAX的shapelets發(fā)現(xiàn)算法（FS）[14]和集成算法（COTE）[13]。在實(shí)驗(yàn)中，LSHST 使用Random Forest 分類器。從實(shí)驗(yàn)結(jié)果可知，這5 種方法的分類精度（表6所示，下標(biāo)括號(hào)中為精度排名）平均排名分別是2.4（LSHST）、3.25（DTW_1NN）、2.5（LS）、4.25（FS）、2.67（COTE），其中LSHST排名第一，結(jié)合表7可以得出，F(xiàn)S算法在分類精度上表現(xiàn)不如其他算法，而LS 和COTE雖然具有較高的分類精度，但算法耗時(shí)巨大，特別是在數(shù)據(jù)規(guī)模較大的數(shù)據(jù)集StarLightCurves和NonInvasive-FetalECGThorax 上，分類時(shí)間均超過72 h（259 200 s）。DTW_1NN表現(xiàn)出對(duì)數(shù)據(jù)規(guī)模的敏感，在小規(guī)模的數(shù)據(jù)集上表現(xiàn)更好。而本文所提LSHST在保證分類精度的同時(shí)，大量縮減分類時(shí)間的消耗，特別是在大規(guī)模數(shù)據(jù)集上具有明顯優(yōu)勢(shì)。

表6 LSHST與其他經(jīng)典分類器分類精度對(duì)比%

表7 LSHST與其他經(jīng)典分類器的分類時(shí)間對(duì)比

4 結(jié)束語

介紹了一種基于LSH 的shapelets 轉(zhuǎn)換方法，利用LSH快速將相似的序列聚集在一個(gè)桶中的特性，對(duì)子序列候選集中大量相似序列進(jìn)行過濾篩選，再用覆蓋方法從其中選擇出shapelets 作進(jìn)一步轉(zhuǎn)換。該方法在保證分類精度不降低的前提下大幅縮減了分類時(shí)間，尤其在大規(guī)模時(shí)間序列的分類問題上具有很高的應(yīng)用前景。