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

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

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

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

【參考文獻(xiàn)】

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

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

本文編號：2817277