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

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

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

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

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