發(fā)布時間：2020-09-11 22:51

　　 序列數(shù)據(jù)廣泛存在于醫(yī)學、經(jīng)濟學等學科中,對其的數(shù)據(jù)挖掘在醫(yī)療診斷、金融數(shù)據(jù)分析等領(lǐng)域已有較為成功應用。序列數(shù)據(jù)是典型的海量、高維數(shù)據(jù),如何對海量的序列數(shù)據(jù)進行高效的分析,對于揭示事物發(fā)展規(guī)律、為科學決策提供依據(jù)具有重要的意義。本文針對序列數(shù)據(jù)挖掘中的兩項核心技術(shù):序列相似度量及相似搜索技術(shù)進行了研究。本文的具體工作和貢獻包括:(1)基于自適應搜索窗口的序列相似比對算法本文提出基于自適應搜索窗口的序列相似比對算法(Adaptive Searching WindowDTW,ADTW),算法利用分段聚集平均(Piecewise Aggregate Approximation,PAA)策略進行序列抽樣,得到低精度序列,然后計算低精度序列下的比對路徑,并根據(jù)低精度距離矩陣上的梯度變化預測路徑偏差,限制路徑搜索窗口的拓展范圍;隨后依次提高序列精度,并在搜索窗口內(nèi)修正路徑、計算新的搜索窗口,最終,實現(xiàn)DTW距離和相似比對路徑的快速求解。對比FastDTW,ADTW算法在同等度量準確率下計算效率提升約20%,其時間復雜度為O(n)。(2)基于多級下界過濾的時序相似搜索算法針對時序數(shù)據(jù)相似搜索效率較低的問題,本文提出基于多級下界過濾的相似搜索算法(Multi_LB),算法挑選多個下界距離函數(shù)組成多級過濾器,對候選集中的無效序列進行分級過濾,同時根據(jù)實時過濾成功率對下界函數(shù)的過濾順序進行動態(tài)調(diào)整,從而保持較高的過濾效率。Multi_LB避免了對部分差異明顯的無效序列進行耗時的下界度量,并降低了過濾失敗產(chǎn)生的額外計算開銷。實驗表明,相較基于單一下界過濾的搜索算法,本文算法在保證搜索完備性的同時,搜索效率提升15%左右。
【學位單位】：沈陽航空航天大學
【學位級別】：碩士
【學位年份】：2018
【中圖分類】：TP301.6
【部分圖文】：

大量多維的索引結(jié)果能夠被應用，如 R-tr將首尾之差作為特征值，則算法的時間復雜在搜索同起點的隨機游走數(shù)據(jù)時，它展現(xiàn)了出的一種緊致度更高的 DTW 下界距離[43]。= (min( ),max( ))，那么 LB_Yi 可以定義( , ) = ∑∑ | ( ) max( ( ) ( )∑ | ( ) max( ( ) ( )程如圖 4.3 所示，函數(shù)累加其中一條序列所然其時間復雜度為 O(n)，這個函數(shù)的計算遠也意味著，整個相似搜索過程可以在很短列。

圖 4.2 LB_Kim 函數(shù)的四個特征值之和作為下界距離。這四個兩條時間序列間的 LB_Kim 下界距離值為。LB_Kim函數(shù)的時間復雜度為O(n)。在得很高效，因為特征向量是四維的，所以每大量多維的索引結(jié)果能夠被應用，如 R-將首尾之差作為特征值，則算法的時間復搜索同起點的隨機游走數(shù)據(jù)時，它展現(xiàn)的一種緊致度更高的 DTW 下界距離[43] (min( ),max( ))，那么 LB_Yi 可以定( , ) = ∑∑ | ( ) max(( ) ( )∑ | ( ) max(( ) ( )

圖 4.4 LB_Keogh 函數(shù)計算過程對搜索窗口的限制，但也導致無法應為序列長度，R 為搜索窗口的半徑。需( , ) ≠ LB ( , )；但兩者都向計算候選序列 S 的包絡(luò)線，得到下距離，我們?nèi)∑渥畲笾底鳛榫o致度更圖 4.5 LB_Keogh 的反向度量數(shù)的過濾能力，我們采用多個數(shù)據(jù)集

【參考文獻】

相關(guān)期刊論文 前1條

1 馬建平;潘俊卿;陳渤;;Android智能手機自適應手勢識別方法[J];小型微型計算機系統(tǒng);2013年07期

本文編號：2817277