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

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

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

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

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

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

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

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

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