基于LSH的shapelets轉換方法

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

中北大學 大數據學院，太原030051

時間序列是隨時間觀測和變化的一系列時值，廣泛用于金融行業[1]、醫療領域[2]、天氣預測[3]等。近年來隨著時間積累和數據類別的增長，時間序列的數量和維度也大量增長，海量高維數據的分析處理成了目前各個行業面臨的挑戰。時間序列數據的分類問題是數據挖掘中一類重要方法，其目的是從已標定類別的訓練集中提取出帶有能夠區分類別的顯著性特征，分類器根據這些特征與未標記類別的時間序列之間的相似性進行分類。根據文獻[4]將時間序列分類算法分為基于全局特征的算法、基于局部特征的算法和集成算法。基于全局特征的算法是將整條時間序列作為特征進行相似性比較，解決該類問題最具代表的方法是基于歐氏距離（Euclidean Distance）和動態時間規整（Dynamic Time Wrapping，DTW）的最近鄰（1-NN）算法，但采用歐氏距離會因為相位漂移影響結果，而DTW 算法消耗大量的時間和空間，只適用于小型數據集，對海量數據無能為力。近些年的研究均集中于尋找更優秀的距離度量方法[5-8]，例如Batista 等人[6]提出復雜性不變的度量方式（CID）、Jeong 等人[8]提出全局加權DTW（WDTW）增加了一個基于扭曲路徑中各點之間的扭曲距離的乘法權重懲罰。基于局部特征的算法將時間序列的一部分作為特征，有分段聚集近似（PAA）[9]、符號聚集近似（SAX）[10]等分段表示方法，以及通過選擇多個區間并使用匯總測度作為特征的分類方法[11]，基于shapelets 的分類算法[12]枚舉出數據集中所有的子序列，通過信息增益選擇最佳shapelets 作為決策樹節點分類準則，具有分類精度高、速度快、可解釋性強的優點。

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

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

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

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

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

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

1 相關知識與定義

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

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

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

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

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

式中，pc是集合D中類標號為c的序列的概率。

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

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

圖1 Gun/NoGun問題中的shapelets

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

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

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

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

其中，ω是窗口長度參數（文獻[23]推薦用ω=4），ai是一個d維向量，每一維的值都滿足標準正態分布，bi滿足的均勻分布。

2 基于LSH的shapelets轉換算法（LSHST）

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

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

2.1 用于shapelets過濾的改進LSH算法

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

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

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

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

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

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

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

圖2 LSH逐級過濾過程示意圖

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

2.2 LSHST算法描述

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

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

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

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

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

2.3 LSHST算法實現

LSHST算法偽代碼見算法1。

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

輸入：數據集data，LSH哈希映射循環次數L，每個桶中隨機選取的子序列條數u，shapelets長度最大值和最小值

輸出：轉換后的數據集

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

算法2UpdateTable（Table，LSHfamily，u）

輸入：待更新哈希表Table，Hash 函數族LSHfamily，每個桶中隨機選擇子序列數量u

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

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

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

3 實驗與結論

本章所涉及所有算法均在Weka框架下使用Java代碼實現，為了全面衡量算法效果，根據數據集的規模，從UCR數據集中分別選擇6個較小和6個較大（見表2）的數據集，作為本章實驗的數據集對前文所述算法進行測試和評估。

表2 數據集

3.1 參數選擇

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

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

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

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

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

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

3.2 算法評估

為綜合評價LSHST 算法的性能，設計了兩組對比實驗，其一是與shapelets 轉換算法作對比，另一個是與其他經典分類算法作對比，在前一實驗所確定的最佳參數組合u=1 和L=50 基礎上將LSHST 算法與多種分類器組合，進行分類準確率和算法耗時的測試。

3.2.1 LSHST與其他shapelets轉換算法的比較

為了說明本文所提算法在基于shapelet 轉換的算法中處于領先水平，對比了LSHST 和ShapaletSelection（ST）[17]、ClusterShapelet（CST）[18]以 及Fast Shapelet Selection（FSS）[19]這三種shapelets 轉換算法，分別結合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 個分類器以計算平均分類精度，結果如表4，LSHST 算法在12個數據集中的7個數據集上表現優于其他方法，在SonyAIBORobotSurface 數據集上相比FSS、ST、CST 分別提升了5.08、12.94和19.95個百分點，在TwoLeadECG數據集上分別提升了16.52、14.1和4.71個百分點，可以看出LSHST在分類精度上表現良好。

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

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

表5 LSHST、FSS、ST、CST算法的shapelets轉換時間 s

3.2.2 LSHST與其他經典分類算法的比較

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

表6 LSHST與其他經典分類器分類精度對比%

表7 LSHST與其他經典分類器的分類時間對比

4 結束語

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