帶通配符和間隔約束的近似頻繁模式挖掘研究.pdf

1、近年來,隨著生物信息計算、網(wǎng)絡(luò)入侵檢測、文本檢索等領(lǐng)域的發(fā)展,如何從序列數(shù)據(jù)中快速地提取用戶感興趣的、有意義的模式成為了一項(xiàng)關(guān)鍵的研究課題。對于已有的模式定義,最具挑戰(zhàn)性的問題是發(fā)現(xiàn)帶通配符和間隔約束的模式。
　　在進(jìn)行模式匹配和挖掘的過程中,允許模式在目標(biāo)序列中的出現(xiàn)帶有編輯誤差能夠使得問題更加滿足實(shí)際應(yīng)用需要,在生物信息學(xué)等領(lǐng)域有著實(shí)際的應(yīng)用價值。本文針對帶通配符和間隔約束的近似頻繁模式挖掘展開研究。用戶可以指定模式字符間通配

2、符的間隔約束范圍、以及允許出現(xiàn)的編輯誤差。對該問題的研究,完善了模式匹配與挖掘問題的研究,而且在許多實(shí)際領(lǐng)域具備應(yīng)用價值。
　　本文的研究工作主要包括以下方面:
　　(1)文本中字符分布特征和模式特征是傳統(tǒng)模式匹配和挖掘問題的重要參數(shù),有助于揭示問題求解復(fù)雜性。因此,以此為研究對象,本文建立了數(shù)學(xué)模型E(Ω)=n*D*π(P),其中Ω為模式精確出現(xiàn)數(shù)目,n為文本長度,D為模式中各通配符間隔 gapi的乘積,π(P)為基于字符

3、分布的模式出現(xiàn)概率。在人工隨機(jī)數(shù)據(jù)和DNA真實(shí)數(shù)據(jù)上的實(shí)驗(yàn)表明,模型的預(yù)測誤差率分別為1.8％~3.2%和4.7%~7.8%。本文同時揭示了在不同字符分布中,模式模長和通配符跨度對匹配數(shù)Ω的影響。因此,本文提出的統(tǒng)計模型可用于估計真實(shí)大文本中的模式出現(xiàn)數(shù)目,為模式挖掘問題中支持度的分析提供參考。
　　(2)針對帶通配符和間隔約束的近似模式匹配挖掘問題,本文提出了MARP(Mining Approximate Repeating P

4、atterns with wildcards and gap lengths)算法。算法的核心工作包括兩個組成部分:一,使用模式支持率度量模式出現(xiàn)的頻繁程度,為此,本文給出了滿足間隔約束的近似補(bǔ)償序列的計算公式?；诖?本文給出了類Apriori性質(zhì),該性質(zhì)可以對候選模式集進(jìn)行有效的確定性剪枝,降低了候選模式集的規(guī)模并能夠及時終止算法,從而提高了挖掘的效率;二,本文給了模式的近似出現(xiàn)的計算方法,該方法基于改進(jìn)的動態(tài)規(guī)劃編輯矩陣,在計算編