12624.序列的公共特征提取算法研究

1、碩士學(xué)位論文序列的公共特征提取算法研究AResearchonFindingtheConjunctMo僦ofSeries學(xué)號：21324023史連理工大學(xué)DaJjanUhiVersityofTecllIl0109y大連理工大學(xué)碩士學(xué)位論文摘要序列的公共特征在現(xiàn)實生活中有著重要的應(yīng)用。離散的序列的公共特征主要應(yīng)用在信息檢索，基因序列匹配等領(lǐng)域。連續(xù)序列的公共特征主要應(yīng)用在股票預(yù)測，音頻識別等領(lǐng)域。序列的公共特征應(yīng)用廣泛，因此受到越來越多的學(xué)

2、者的研究與關(guān)注。離散序列的公共特征提取往往指求解多條離散序列的最長公共子序列問題，該問題是著名的NP難問題。精確算法已經(jīng)盡可能的降低時間復(fù)雜度，但其復(fù)雜度仍是指數(shù)級別的。當(dāng)數(shù)據(jù)集的規(guī)模增大時，采用精確算法求解的開銷十分的龐大。近似算法雖然時間復(fù)雜度較低，但求出的解的數(shù)量較少，使得結(jié)果集的信息損失較大。連續(xù)序列的公共特征提取往往指求解多條連續(xù)序列的中心序列問題，該問題利用動態(tài)時間規(guī)整(DTW)，來衡量時間序列間的相似性。但因其不滿足三角不

3、等式且計算復(fù)雜度較高，因此求解多時間序列的中心序列問題也是NP難問題。本文對一些前人的研究做了綜述與回顧，介紹部分算法的核心思想。在離散序列的公共特征提取方面，引入了“格”(La廿ice)結(jié)構(gòu)提出了一個新的計算序列公共格的算法，該算法亦可近似計算序列的最長公共子序列。算法采用局部合并策略，并使用格結(jié)構(gòu)來存儲合并過程中的信息。通過實驗，驗證了對于離散序列的公共特征提取，本文算法得到解的精確性與數(shù)量方面均具有優(yōu)勢。在連續(xù)序列的公共特征提取方