時間序列相似性問題研究.pdf

1、時間序列相似性問題是時間序列挖掘中的一個重要而基礎的問題，為其他的挖掘手段提供必要的技術支持和手段，也經(jīng)常作為其他挖掘問題的一個子程序，自從提出以來一直是一個備受關注的研究熱點問題。圍繞靜態(tài)時間序列比較、動態(tài)時間序列匹配等方面，開展了六方面的研究工作：時間序列建模、靜態(tài)時間序列的相似比較、動態(tài)時間序列的相似匹配、時間序列相似比較的提前終止和效率估算、相似序列的排序以及相似序列搜索原型系統(tǒng)的研究。 為改變當前時間序列建模表示方法缺少

2、時間特征的現(xiàn)狀，通過分析逐段聚集平均(Piecewise Aggregate Approximation，PAA)表示方法，提煉出時間序列的時間特性，對于較近時間段的數(shù)據(jù)具有較高的參考價值，而較遠時間段內(nèi)的數(shù)據(jù)則具有較低的參考價值。改造PAA表示方法，得到逆向逐段聚集平均(Reversed Piecewise Aggregate Approximation，RPAA)表示方法，對不同的分段引入不同的影響因子，證明了基于RPAA 方法的距

3、離下界于Euclidean距離，保證在時間序列相似搜索中不會發(fā)生漏查。實驗結(jié)果表明，RPAA 較PAA在相似搜索中具有較小的錯差率。將自適應逐段常量近似(Adaptive Piecewise Constant Approximation，APCA)表示方法擴展到動態(tài)時間序列的分段中，得到自適應逐段常量近似(Adaptive Piecewise Constant Approximation onStream，APCAS)。APCAS能夠在

4、線性時間內(nèi)完成在線時間序列流的分段，比APCA具有更少的內(nèi)存消耗和更短的分段時間。當前的動態(tài)時間序列彎曲距離(Dynamic Time Warping，DTW)下界函數(shù)，要么采用序列間的較少特征而與實際的DTW具有較大差異，要么不具備對稱特性而限制了下界函數(shù)的應用范圍。在分析DTW下界函數(shù)特性的基礎上，給出了一種DTW下界函數(shù)LB_HUST，證明了LB_HUST具有對稱性和下界性。將LB_HUST擴展到時間序列集合的距離計算中，證明了L

5、B_HUST在時間序列集合計算中的性質(zhì)。 實驗結(jié)果表明，LB_HUST不僅是時間序列基于DTW計算的一種緊密而對稱的下界函數(shù)，而且在時間序列聚類中能夠取得較好效果。為改變當前時間序列流匹配中多是采用單一的相似比較手段的現(xiàn)狀，給出一種支持多種比較方法的時間序列流匹配模型框架Multi-Tsource，將比較方法和其他的時間序列流處理手段分離。在Multi-Tsource的基礎上，分別重點分析了基于Euclidean和DTW的比較方

6、法，最后通過實驗驗證了Multi-Tsource框架的可行性。結(jié)果表明，支持多種比較方法并不會使系統(tǒng)的效率有顯著降低，通過分發(fā)機制可以使多種比較方法相互獨立，為系統(tǒng)的動態(tài)擴展提供了保證。為提高計算的效率，將提前終止技術引入到了DTW 距離的計算中，在分析DTW提前終止性質(zhì)的基礎上，給出DTW提前終止算法EA_DTW，用實驗驗證了DTW提前終止算法的效率。EA_DTW方法可以跳過冗余的DTW 方格計算，經(jīng)常在不需要全部計算精確DTW距離的

7、情形下即可完成序列的DTW相似比較，從而節(jié)省計算資源。 以前的提前終止技術的效率都是建立在實驗驗證的基礎上，而缺乏理論化的工具，為此，設計了一種提前終止的效率估算方法EA_Estimate，通過對有效計算路徑上溢出的估計，最終估算出最終的提前終止的效率。理論計算和實際的計算的實驗對比結(jié)果表明，EA_Estimate可以確定一個大致的效率范圍，幫助用戶確定最終有效值。由于時間序列不具備顯式的關鍵字，目前出現(xiàn)的基于關鍵字的排序方法不

8、能直接應用于時間序列的排序。在對時間序列排序的問題進行定義的基礎上，根據(jù)時間序列與序列集合邊界的關系得出了基于時間序列邊界的排序方法TS-Sort，并且在實現(xiàn)時實現(xiàn)了基于劃分的改進方法，證明了改進方法與直接方法的等效性。最后通過實驗對TS-Sort進行了驗證。結(jié)果表明，TS-Sort不僅可以作為一項時間序列處理的工具，而且可能根據(jù)排序的結(jié)果對所處理的數(shù)據(jù)有深層次的認識。 以上述研究成果為基礎，設計和實現(xiàn)了一個時間序列相似搜索的原