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

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

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

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