時間序列模式匹配技術(shù)研究.pdf

1、時間序列模式匹配是時間序列挖掘研究中一個基礎(chǔ)和重要的問題，它是聚類、分類、規(guī)則發(fā)現(xiàn)、異常檢測和知識發(fā)現(xiàn)等其它挖掘任務(wù)的基本技術(shù)手段和處理方法。該課題的研究目前還處在積極發(fā)展的階段，現(xiàn)有的研究成果已經(jīng)顯示出模式匹配具有廣闊的應(yīng)用前景。
　　以目前時間序列的主體框架GEMINI框架為基礎(chǔ)，開展時間序列模式匹配技術(shù)中的分類、子序列的定位、序列間距離的度量、距離度量的優(yōu)化和適合于動態(tài)時間序列的匹配方法等的研究具有重要意義。
　　按照

2、匹配的形式可以將模式匹配問題分為子序列匹配和全序列匹配兩類。子序列匹配是從長度更長的主序列中查找與給定的模式序列相同或相似子序列的過程，最重要的操作是子序列定位，解決該問題的關(guān)鍵是如何減少匹配次數(shù)。全序列匹配是從時間序列數(shù)據(jù)庫中查找與給定的模式序列相同或相似序列的過程。全序列匹配一般轉(zhuǎn)換為距離度量的問題，如何提高序列之間距離度量的準確度和效率是該問題的研究熱點。
　　通過對現(xiàn)有的經(jīng)典子序列定位方法的深入分析,提出了基于重復度的貪心

3、定位算法和基于相異度的貪心定位算法。貪心定位算法運用最優(yōu)化原理計算模式序列的特征值，模式匹配按照特征值的大小從大到小進行，具有匹配效率高、適應(yīng)性好、易于擴展和易于優(yōu)化的優(yōu)點。
　　針對全序列匹配中采用的距離度量方法存在度量準確度低、效率低的問題，提出了基于形態(tài)擬合的距離度量算法。該算法將歐式距離和動態(tài)彎曲距離兩種度量方法進行優(yōu)勢組合，盡力消除影響歐式距離和動態(tài)彎曲距離度量的不利因素，具有度量準確度高和效率高的優(yōu)點。
　　現(xiàn)有

4、精確的動態(tài)彎曲距離存在計算性能瓶頸，在深入分析動態(tài)彎曲距離計算原理的基礎(chǔ)上，提出了距離上界函數(shù)的概念，并給出了動態(tài)彎曲距離的距離上界函數(shù)的設(shè)計方法。如果函數(shù)的計算路徑是一條動態(tài)彎曲路徑，那么它就是一個動態(tài)彎曲距離的距離上界函數(shù)。為提高精確的動態(tài)彎曲距離的計算效率，提出了應(yīng)用提前終止技術(shù)加速計算過程的新算法，該算法以動態(tài)彎曲距離的距離上界函數(shù)作為提前終止判定值，在計算累積距離矩陣的過程中，當累積距離大于動態(tài)彎曲距離的距離上界函數(shù)值時，對該

5、計算路徑進行終止標識，重新選取其它的計算路徑進行計算。該算法確保了動態(tài)彎曲距離的度量準確度，同時有效地提高了計算效率。
　　在深入分析動態(tài)序列、動態(tài)匹配和匹配算法特點的基礎(chǔ)上，提出了模式序列的模式閾值的概念，設(shè)計和實現(xiàn)了適合于動態(tài)時間序列的基于模式閾值的定位算法，并對該算法進行了優(yōu)化。
　　以上述研究成果為基礎(chǔ)，設(shè)計和實現(xiàn)了一個同時支持子序列匹配、全序列匹配和動態(tài)匹配的時間序列模式匹配原型系統(tǒng)TSPM(Time Series