基于FastDTW-LSH的shapelet篩選方法

張宏飛，喬鋼柱，宿 榮

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

0 引 言

時間序列數(shù)據(jù)，按一定先后順序排列而成，是一種隨著時間變化而發(fā)生變化的數(shù)據(jù)，它反映了觀測數(shù)據(jù)隨著時間不斷變化的趨勢，這個趨勢可能會具有混沌性、周期性、隨機性等性質(zhì). 對于時間序列的分析大致有兩類，一類是根據(jù)歷史數(shù)據(jù)對未來數(shù)據(jù)進行預(yù)測分析，例如天氣預(yù)測，空氣質(zhì)量預(yù)測，疫情預(yù)測[1-3]等； 另一類是對時間序列數(shù)據(jù)進行分類，例如心電圖診斷分類，設(shè)備故障分類[4-5]等.

與傳統(tǒng)數(shù)據(jù)分類不同的是，時間序列數(shù)據(jù)是一種強調(diào)時序順序的數(shù)據(jù)，不同的屬性次序可能會產(chǎn)生不同的特征提取結(jié)果，進而會影響最終的分類效果. 由于時間序列數(shù)據(jù)大多是高維海量數(shù)據(jù)，如果要全部處理，其計算開銷巨大，耗時嚴重且夾雜了許多噪聲. 鑒于此，Ye和Keogh[6]首先提出了shapelet的概念，根據(jù)不同時間序列之間略有差異的局部特征進行分類. Shapelet是時間序列中最具區(qū)別性的一組子序列，由一個或多個子序列組成，能明顯區(qū)分出不同類別的序列. 如圖 1 所示，Coffee兩類數(shù)據(jù)在全局特征上保持高度相似性，僅在局部特征上表現(xiàn)出明顯差異，即標注之處或可為Coffee數(shù)據(jù)的shapelets，在形狀上能直觀解釋不同類別數(shù)據(jù)的差異. Shapelet的優(yōu)勢在于將研究目標從時間序列本身轉(zhuǎn)換為研究其子序列，能夠大大減少時間消耗，且shapelet在形狀上可以直觀解釋分類結(jié)果和數(shù)據(jù)內(nèi)部特征差異.

圖 1 Coffee數(shù)據(jù)序列示意圖Fig.1 Data sequence diagram of Coffee

Ye和Keogh提出的基于shapelet的時間序列分類和分析方法也被應(yīng)用于時間序列數(shù)據(jù)挖掘的各個領(lǐng)域，但這種原始搜索shapelet方法的時間復(fù)雜度為O(n2m4)，需要枚舉所有候選子序列并比較其質(zhì)量，時間開銷太大，令研究難以為繼. 于是，在基于候選空間搜索shapelet的研究領(lǐng)域，研究者們提出以下方法來降低計算開銷.

在聚集近似方面，Rakthanmanon等[7]提出了一種基于符號聚集近似(SAX)的快速shapelet發(fā)現(xiàn)算法(Fast Shapelet，F(xiàn)S). 類似地，F(xiàn)ang等[8]也提出了一種基于分段聚合近似(PAA)的shapelet搜索方法來加快運行速度.

在降維方面，李禎盛等[9]提出了基于主成分分析(PCA)的shapelet搜尋方法(降維從而加快運算速度)，但是降維的方法可能會丟失原始數(shù)據(jù)中的有用信息，影響分類準確率.

在硬件方面，Chang等[10]從硬件角度出發(fā)，并行計算shapelet從而提升了效率，但候選者空間消耗巨大，冗余無法解決.

在剪枝操作方面，He等[11]提出了先將序列符號化，將較低頻率的序列列入候選空間； Wei等[12]提出了通過最大相似性和最小冗余度消除一部分相似shapelet； Ji等[13]提出了一種基于子類分裂方法，通過對訓(xùn)練實例采樣找出局部最遠偏移點，選擇兩個不相鄰的偏移點之間的子序列作候選shapelets.

對序列是否被列入為候選空間，Renard等[14]提出了隨機思想，但是通過隨機函數(shù)方法得到的結(jié)果解釋能力不強. Karlsson等[15]提出了shapelet隨機森林的方法，通過隨機選擇的序列和shapelet構(gòu)建決策樹構(gòu)成隨機森林.

針對在篩選shapelet的過程中同時構(gòu)建分類器，Lines等[16]提出了通過shapelet的轉(zhuǎn)換，將shapelet轉(zhuǎn)換到新的數(shù)據(jù)空間，使shapelet的發(fā)現(xiàn)過程和分類器構(gòu)建各自獨立，使用更加靈活. Grabocka等[17]第一次提出用目標函數(shù)求解shapelet(Learned Shapelet，LS)，然而，由于不能學(xué)習(xí)隨著時間軸彎曲的時間序列，又提出了基于DTW的學(xué)習(xí)shapelet方法,但是復(fù)雜度增加. 基于shapelet轉(zhuǎn)換方法上的難題在于無法確定用于轉(zhuǎn)換的shapelet的數(shù)量，原繼東等[18]提出了剪枝和覆蓋的shapelet轉(zhuǎn)換方法來解決此問題，但是隨著數(shù)據(jù)規(guī)模增大，時間復(fù)雜度難免增加. 鑒于此，丁智慧等[19]提出了基于LSH的shapelet轉(zhuǎn)換方法(LSH shapelet transform, LSHST)，采用解決高維海量數(shù)據(jù)問題的局部敏感哈希(LSH)方法在搜尋shapelet的過程中逐級過濾掉大量子序列，再通過文獻[18]的shapelet覆蓋方法再次篩選，以確定最終shapelet數(shù)量，最后進行shapelet轉(zhuǎn)換，縮減了時間復(fù)雜度，保證了一定的分類準確率.

由于LSHST在逐級過濾過程中，僅是對同一哈希桶中的子序列進行隨機篩選，可能會造成帶有關(guān)鍵性信息和局部特征區(qū)分度更高的候選子序列被剔除，導(dǎo)致最終篩選出來的shapelets對分類結(jié)果有一定影響. 因此，本文提出基于局部敏感哈希的FastDTW-LSH-Shapelet篩選方法，對LSH映射后的各哈希桶中的子序列采用FastDTW距離[20]衡量子序列間的相似性，對其進行分類并挑選出各類中具有極大不相似性的子序列以供下一次映射，循環(huán)操作后，使用shapelet覆蓋的方法確定最終shapelet數(shù)量并進行轉(zhuǎn)換. 相比LSHST方法循環(huán)映射中的隨機篩選，本文所提方法采用的分類后再篩選更具有公平性，而且在各數(shù)據(jù)集上都具有較好的分類結(jié)果.

1 相關(guān)公式與定義

定義1(時間序列)：時間序列T={t1,t2,t3,…,tn}是一個長度為n的實值連續(xù)型數(shù)據(jù)序列.其中每個元素ti(1≤i≤n)按照時間的先后順序采樣排列.

定義2(動態(tài)時間規(guī)整，Dynamic Time Wraping，DTW)[20]：是為了解決傳統(tǒng)歐式距離點對點計算要求序列等長的問題而提出的，可以對時間序列本身進行延伸和縮短，能實現(xiàn)不同長度時間序列距離的計算. 計算序列T={t1，t2，t3，…,tM}和T1={t11，t12，t13，…,t1N}之間DTW距離的步驟如下：

1) 計算兩個序列各個點之間的距離矩陣(Distance Matrix，DM).

DM=(a(i,j))M×N,a(i,j)=(ti-t1j)2.

(1)

2) 尋找一條從矩陣左下角到右上角的規(guī)整路徑，使得路徑上的元素和最小.

W=(w1,w2,…,wk),

(2)

式中：wk=a(i,j)，那么wk+1滿足以下條件

(3)

那么兩條序列之間的DTW距離為

(4)

定義3(局部敏感哈希，LSH)[21]：局部敏感哈希的提出是用來解決高維海量數(shù)據(jù)的近似近鄰搜索問題. 通過哈希函數(shù)對原始數(shù)據(jù)空間中的點進行哈希映射，映射到同一哈希桶中的數(shù)據(jù)被認為近似相似. 哈希函數(shù)H需要滿足以下兩個條件：

1) 如果d(x,y)≤d1，則h(x)=h(y)的概率至少為p1，即PrH[h(x)=h(y)]≥p1；

2) 如果d(x,y)≥d2，則h(x)=h(y)的概率至多為p2，即PrH[h(x)=h(y)]≤p2.

滿足以上條件則認為H是(d1,d2,p1,p2)敏感的. 哈希函數(shù)定義為

(5)

式中：ω是窗口長度參數(shù)；ai是一個d維向量，每一維的值都滿足標準正態(tài)分布；bi滿足[0,ω]的均勻分布.

2 基于FastDTW-LSH的shapelet篩選方法

為了解決海量高維數(shù)據(jù)查詢效率低的問題，局部敏感哈希利用哈希函數(shù)將近似相似的數(shù)據(jù)映射在同一哈希桶中，不相似的分別映射在其他桶中，保證同一哈希桶中數(shù)據(jù)近似相似，明顯降低了計算復(fù)雜度和時間消耗. LSHST通過歐式敏感哈希函數(shù)將大規(guī)模的候選子序列映射到不同哈希桶中，隨機篩選出每個哈希桶中具有代表性的集合并釋放空間，然后再逐級過濾掉大規(guī)模的冗余序列，篩選出最終的shapelets.

圖 2 為GunPoint數(shù)據(jù)集的原始序列和部分長度為20的子序列，這些子序列經(jīng)過局部敏感哈希映射有極大概率會落在同一個哈希桶HashBucket1中，但是子序列Subseq2與其他兩條相比，明顯具有更多特征，形狀上也更具區(qū)分度，更希望Subseq2參與下一次哈希映射，但隨機挑選時，同一哈希桶中每一條子序列都容易被選中，很可能會遺漏掉Subseq2； 另一方面原始序列在產(chǎn)生子序列時為保證時序數(shù)據(jù)的時序性，是在原始序列上進行窗口為1的滑動，會產(chǎn)生有大量重疊部分且高度相似的候選子序列，而這些冗余無意義的候選序列無疑會增大計算開銷和時間消耗. 因此，在逐級哈希的過程中使用FastDTW距離衡量序列相似性并剔除冗余序列，可以在減少計算開銷、降低時間消耗的同時選擇出更具有區(qū)分度的子序列來進行下一次哈希映射，提高最終shapelets集合的質(zhì)量，提升分類精度.

圖 2 GunPoint數(shù)據(jù)序列示意圖Fig.2 Data sequence diagram of GunPoint

2.1 LSH映射篩選子序列

由上述定義3可知，局部敏感哈希映射，即用滿足以下兩個條件的哈希函數(shù)將原始數(shù)據(jù)映射生成哈希表：

1) 相近的數(shù)據(jù)落在同一個哈希桶中的概率p1很高；

2) 不相近數(shù)據(jù)落在同一哈希桶中概率p2很低.

將序列引伸為向量數(shù)據(jù)，利用LSH映射篩選子序列的過程即將序列通過哈希函數(shù)映射生成哈希表，生成的哈希表中相似序列落在同一個哈希桶中的概率很大，不相似序列則落在不同哈希桶中. 在序列篩選過程中更多關(guān)注的是具有不同特征的序列而非具有高度相似性的序列，以便從不同哈希桶中挑選出更具有區(qū)分度的序列進行下次計算. 建立L個哈希表后，兩條序列相似的概率是P=1-(1-pk)L，利用LSH映射的這種性質(zhì)可以很快篩選出需要的待選序列，減少計算開銷，提高時間效率.

2.2 FastDTW衡量篩選過程

經(jīng)過LSH映射后，同一哈希桶中的序列只是保證了有一定概率相似而非完全相似. 以GunPoint數(shù)據(jù)集為例，長度為10的子序列經(jīng)過LSH映射，隨機選擇HashTable1中的哈希桶并隨機采樣如圖 3 所示. 由圖 3 可見，落入同一哈希桶中的序列并非完全相似，HashBucket1中序列1，2，5，6在形狀趨勢變化上相似，而序列3和4則與之不同. 將前者劃分為Class1，后者劃分為Class2. 在隨機篩選HashBucket1中的序列參與下一次映射計算時，Class1中的序列參選概率更大，會引起篩選過程中更具特征差異性的子序列被遺漏，導(dǎo)致候選空間的子序列質(zhì)量不高，降低最終篩選的shapelets質(zhì)量. 在HashBucket2中子序列集保持很大的相似性，在HashBucket3中子序列集明顯出現(xiàn)聚集情況. 本文提出將哈希桶中的序列先分類再篩選，確保涵蓋特征差異的子序列參與下一次哈希映射，提高最終篩選的shapelets質(zhì)量.

(a) HashBucket1 采樣序列

(b) HashBucket2 采樣序列

(c) HashBucket3 采樣序列圖 3 不同哈希桶中的子序列Fig.3 Sub-sequences in different Hash Buckets

對于序列分類而言，歐式距離無法解決序列彎曲拉伸的情況. 如圖 3 所示，HashBucket1中的序列1，5，6經(jīng)過一定程度平移伸縮可認為其相似性很高，而歐式距離無法評判這種相似性，故而采用DTW距離作為度量標準. 由式(4)定義可知，計算兩條序列DTW距離的時間復(fù)雜度是O(n2)，計算開銷太大. 經(jīng)過LSH映射篩選后落在同一個哈希桶中的序列已經(jīng)保持了極大的相似性，所以，對同一個哈希桶中的序列進行分類的目的是為了能夠盡可能公平地篩選出具備更多特征和區(qū)分度更強的子序列參與下一次計算，因而不需要精確計算出序列間的DTW距離. 使用FastDTW方法來加快計算過程，通過限制空間和抽象的手段求出兩條序列間一條近似最優(yōu)的彎曲路徑，且時間復(fù)雜度僅為O(n).

1) FastDTW計算步驟：

① 粗粒度化：原始序列粗粒度化收縮，收縮后各數(shù)據(jù)點為相鄰數(shù)據(jù)點的平均值. 可進行多次收縮求出粗粒度化空間.

② 投影：在粗粒度化收縮后的空間計算DTW距離，得到粗粒度化空間下的動態(tài)規(guī)整路徑.

③ 細粒度化：將上一步求到的規(guī)整路徑細化到細粒度空間，再逐步細化到原始空間.

如表 1 所示，隨機采樣HashTable1中的哈希桶，計算子序列與各桶中首個子序列的FastDTW距離，從數(shù)值上可以看出同一哈希桶中的子序列只是近似相似而非完全相似. 采用FastDTW距離對各桶中的序列進行分類后，再隨機篩選出子序列參與下一次LSH映射.

表 1 不同哈希桶中隨機采樣子序列間的FastDTW距離Tab.1 FastDTW distance between randomly sampled sub-sequences in different Hash Buckets

2) FastDTW分類篩選方法

FastDTW篩選流程如圖 4 所示.

圖 4 FastDTW篩選流程圖

首先，計算哈希桶中的子序列與各桶中第一條序列的FastDTW距離. FastDTW大于閾值a的劃分為特征相異的一類Class1，不大于閾值a的劃分為特征相近的一類Class2； 在Class1，Class2中各隨機選擇u1，u2條序列.

其次，對哈希表中的每個哈希桶中的子序列重復(fù)上述操作，篩選出高質(zhì)量的子序列候選集.

最后，刪除此次哈希映射生成的哈希表，釋放空間并進行下一次哈希映射.

2.3 FastDTW-LSH的shapelet篩選方法描述

FastDTW-LSH方法在篩選shapelets過程中對序列數(shù)據(jù)進行第一次LSH映射后，所有子序列被映射到HashTable1中，若此時對HashTable1中所有哈希桶的子序列進行FastDTW分類判別無疑增加了時間消耗. 由圖 3 可以看出，即使映射在同一哈希桶中的子序列也存在明顯類別差異. 為了增加隨機篩選的公平性(即增加了同一哈希桶中不同類別的子序列參與映射的概率)，同時為了避免龐大時間消耗，對HashTable1中各哈希桶隨機篩選兩條進行第2次哈希映射，在第2次LSH映射結(jié)束后再進行FastDTW分類篩選，將原本上千甚至上萬條子序列的分類判別轉(zhuǎn)變成對幾十條子序列的分類，在較低的計算開銷下篩選出更具代表性和特征差異性的子序列參與下一次映射，最終提高 shapelets的多樣性和可解釋性. 如圖 5 所示，F(xiàn)astDTW-LSH的shapelets篩選方法具體流程如下：

第一步，定義shapelets候選序列的最小長度minlength和最大長度maxlength，并根據(jù)原始序列生成子序列； 設(shè)置哈希映射次數(shù)L，設(shè)置同一哈希桶中序列相似閾值a和篩選條數(shù)u1和u2.

第二步，利用LSH映射建立哈希表HashTable1，將子序列集合映射到各哈希桶中，在各哈希桶中隨機篩選兩條序列參與下一次映射并刪除HashTable1釋放空間.

第三步，利用LSH映射建立哈希表HashTable2，將HashTable1中篩選出來的子序列映射到各哈希桶中，根據(jù)FastDTW距離來篩選過濾各哈希桶中的子序列； 計算HashBucket1中所有序列與第一條序列的FastDTW距離，大于a的序列劃分為Class1，其余歸為Class2，分別在Class1和Class2中各篩選u1和u2條； 遍歷HashTable2中所有哈希桶，挑出各桶中具有極大不相似性的子序列供下一次計算，并刪除HashTable2，剔除冗余無意義的序列，釋放空間.

第四步，重復(fù)上述操作，逐級篩選過濾至L次循環(huán)映射結(jié)束，得到具有明顯特征區(qū)分的候選序列.

圖 5 FastDTW-LSH篩選shapelets流程圖

3 實驗

針對shapelets篩選過程參數(shù)選擇和FastDTW-LSH算法評估分別進行對比實驗. 本文實驗環(huán)境為Java，Python3.7，數(shù)據(jù)集選用UCR公開數(shù)據(jù)集，實驗數(shù)據(jù)如表 2 所示，分別選用不同規(guī)模數(shù)據(jù)綜合評估算法.

表 2 實驗數(shù)據(jù)集Tab.2 Experimental dataset

3.1 參數(shù)選擇

為了提高篩選shapelets的質(zhì)量，本文方法在子序列篩選過程中引入?yún)?shù)L，a，u1和u2. 文獻[19] 實驗結(jié)果證明，哈希映射次數(shù)L和隨機篩選參數(shù)u的最佳組合是L=50，u=1. 在此基礎(chǔ)上，設(shè)計了子序列相似性閾值a，循環(huán)映射次數(shù)L和映射過程中的篩選子序列數(shù)量u1,u2等實驗參數(shù)組合，分別在各數(shù)據(jù)集上進行算法分類精度和耗時實驗，以便進行最優(yōu)參數(shù)的選擇.

3.1.1 子序列相似性閾值a

如圖 2 和表 1 所示，針對GunPoint數(shù)據(jù)集長度為10的子序列，經(jīng)過一次LSH映射后，隨機采樣HashTable1中的哈希桶并進行FastDTW距離計算，可以看到即使是映射到同一哈希桶中的子序列，其距離差異也很大，故針對后續(xù)篩選過程閾值a的選取應(yīng)該由各桶中序列的相似性決定.由于樣本均值反映的是樣本集中趨勢，而樣本方差和標準差反映的是樣本離散趨勢，均值結(jié)合標準差反映的是樣本偏離程度，故使用統(tǒng)計量μ，σ，μ+σ作為各哈希桶中分類篩選的閾值參數(shù)a，并進行多組實驗選出最適合的統(tǒng)計量作為閾值參數(shù).μ，σ分別表示樣本均值和標準差，對于統(tǒng)計量定義如下：

aii=μii+σii,

式中：aii表示HashTablei中HashBucketi進行FastDTW分類篩選的閾值；μii表示HashTablei中HashBucketi序列間FastDTW距離的均值；σii表示HashTablei中HashBucketi各序列間FastDTW距離的標準差.

3.1.2L和u1，u2組合參數(shù)

參數(shù)L是循環(huán)映射次數(shù)，參數(shù)u1，u2是在對同一哈希桶中的子序列分類后各類參與下一次映射的子序列數(shù)量.在不大幅增加時間消耗的前提下，為了保證映射和篩選過程的公平性，使用u1，u2組合函數(shù)f.

不同統(tǒng)計量定義的參數(shù)閾值a和循環(huán)映射次數(shù)L都會影響最終shapelets的質(zhì)量，進而影響FastDTW-LSH方法的分類效果. 為了探究參數(shù)的影響，分別在不同參數(shù)組合下對不同數(shù)據(jù)集進行實驗，結(jié)果如圖 6 所示.

圖 6 FastDTW-LSH方法精度在不同統(tǒng)計量下隨L變化的曲線Fig.6 The curve of FastDTW-LSH algorithm accuracy with L under different statistics

由圖 6 可以看到，在同一統(tǒng)計量定義的閾值下，F(xiàn)astDTW-LSH方法篩選出來的shapelets分類準確率總體隨L變化的趨勢不明顯，在L=40后準確率基本保持穩(wěn)定； 在不同統(tǒng)計量定義的閾值下，F(xiàn)astDTW-LSH方法篩選出來的shapelets分類準確率有所不同，在統(tǒng)計量μ+σ下的分類準確率比其他兩個統(tǒng)計量下的更高，篩選出來的shapelets質(zhì)量優(yōu)于其他兩個統(tǒng)計量下的篩選結(jié)果，因此，選用μ+σ作為閾值參數(shù)a的定義.

由于L=40后準確率曲線基本保持穩(wěn)定，為了選取最佳的循環(huán)映射參數(shù)L，對各數(shù)據(jù)集進行了耗時實驗，實驗結(jié)果如圖 7 所示.隨著參數(shù)L的不斷變化，算法耗時整體呈現(xiàn)減小趨勢，L=55左右算法耗時基本保持穩(wěn)定；L=60左右小數(shù)據(jù)集上耗時呈現(xiàn)一定上升趨勢.所以，參數(shù)L的最佳值選取55.

(a) 小規(guī)模數(shù)據(jù)集

(b) 大規(guī)模數(shù)據(jù)集圖 7 FastDTW-LSH方法耗時隨L變化的曲線Fig.7 The curve of FastDTW-LSH algorithm time consuming with L

3.2 FastDTW-LSH算法評估

3.2.1 與LSHST算法對比

為了評價FastDTW-LSH方法較LSHST方法的優(yōu)越性，結(jié)合不同分類器分別對表 2 所示12個數(shù)據(jù)集進行分類并計算平均分類精度，結(jié)果如表 3 所示. 由表 3 可以看到，在時間消耗上FastDTW-LSH方法相比LSHST有一定程度的增加，但是FastDTW-LSH方法結(jié)合分類器RandomForest，RotationForest，SVML的平均分類精度在8個數(shù)據(jù)集(見表 3)上的表現(xiàn)優(yōu)于LSHST方法，尤其在CricketZ和FiftyWords數(shù)據(jù)集上分別最高提升了11.57%和9.16%.

表 3 FastDTW-LSH與LSHST算法分類精度、shapelets轉(zhuǎn)換耗時和分類總耗時比較Tab.3 Comparison of accuracy, shapelets time consuming and total time between FastDTW-LSH and LSHST algorithms

3.2.2 與經(jīng)典分類算法對比

與經(jīng)典分類算法FS[7]、LS[17]、COTE[22]進行比較，分析FastDTW-LSH算法分類結(jié)果的優(yōu)越性. FastDTW-LSH方法結(jié)合3.2.1節(jié)實驗中所提的分類器計算分類準確率和耗時，所得實驗結(jié)果如表 4 所示. 可以看到，雖然FS方法利用SAX方法降低了時間消耗，但是一定程度上犧牲了分類精度； LS、COTE方法雖有較高的分類精度，但因時間消耗太大而不可取. 相比經(jīng)典分類算法，本文方法FastDTW-LSH二者兼得，在有著遠小于經(jīng)典分類方法LS、COTE的時間消耗的同時，其分類精度在6個數(shù)據(jù)集(見表 4)上也表現(xiàn)出良好的優(yōu)越性.

由表 4 可看出，F(xiàn)astDTW-LSH方法優(yōu)先適用于高維海量序列數(shù)據(jù)，在降低時間消耗的同時，提升了分類準確率，即使對于較小數(shù)據(jù)集CBF、ECG200和GunPoint，本文方法相比其他方法也有較強的競爭優(yōu)勢.

表 4 FastDTW-LSH與經(jīng)典分類算法分類精度、耗時比較Tab.4 Comparison of classification accuracy and time consuming between FastDTW-LSH and classic classifical algorithms

綜上所述，F(xiàn)astDTW-LSH方法具有普適性，在保證一定時間消耗的同時可以提高shapelets篩選的質(zhì)量，有卓越的分類效果.

4 結(jié) 論

本文提出一種基于FastDTW-LSH的shapelet篩選方法. 首先，采用局部敏感哈希利用空間投影的近似相似性快速將子序列映射到各個哈希桶中； 其次，通過FastDTW距離快速篩選出各桶中具有極大不相似性的子序列，以便作為下一次過濾的候選集，經(jīng)過多次過濾篩選得到最終的shapelets； 最后，通過shapelets轉(zhuǎn)換技術(shù)結(jié)合分類器進行分類.

與傳統(tǒng)方法相比，該方法能夠明顯降低時間消耗，提高分類效率，在軸承故障診斷、網(wǎng)絡(luò)故障診斷、電廠數(shù)據(jù)穩(wěn)定性評價等序列數(shù)據(jù)分類方面具有極大應(yīng)用前景. 在下一步的研究中，應(yīng)側(cè)重于優(yōu)化局部敏感哈希函數(shù)，使用更適用于時間序列相似性判斷的DTW距離來進行哈希映射，在進一步縮短耗時的同時明顯提升分類精度.