帶有通配符的序列模式挖掘研究.pdf

1、實(shí)際應(yīng)用領(lǐng)域中產(chǎn)生了大量的序列數(shù)據(jù)，例如：超市顧客購買數(shù)據(jù)、信用卡交易記錄、電信數(shù)據(jù)、DNA和蛋白質(zhì)序列、文本數(shù)據(jù)等，這些序列數(shù)據(jù)中隱含著豐富的有價(jià)值的知識(shí)亟待挖掘。序列模式挖掘，旨在從序列數(shù)據(jù)庫中挖掘頻繁出現(xiàn)的序列模式，已成為數(shù)據(jù)挖掘領(lǐng)域中一項(xiàng)非常重要的研究任務(wù)。然而，模式的出現(xiàn)并不都是連續(xù)的，模式中每?jī)蓚€(gè)連續(xù)字符之間可能含有靈活的通配符。例如，在生物序列中，模式的相鄰字符之間可能插入或刪除較短的序列片段。因此，帶有通配符的序列模式挖

2、掘研究不僅具有理論上的研究?jī)r(jià)值，而且在文本挖掘、生物信息學(xué)、傳感器網(wǎng)絡(luò)等領(lǐng)域都有著巨大的應(yīng)用價(jià)值。
　　 本文圍繞帶有通配符的序列模式挖掘及其在文本領(lǐng)域中的應(yīng)用開展研究，研究?jī)?nèi)容涉及三個(gè)方面：(1)定義同時(shí)具有間隔約束和one-off條件的帶有通配符的序列模式挖掘問題；(2)帶有通配符的序列模式挖掘算法設(shè)計(jì)與分析；(3)將提出的帶有通配符的序列模式挖掘算法應(yīng)用在文本領(lǐng)域，利用挖掘的文本模式分析詞語之間的語義關(guān)系，抽取出關(guān)鍵詞。<

3、br>　　 主要研究?jī)?nèi)容和創(chuàng)新之處如下：
　　 (1)帶有通配符的序列模式挖掘問題定義。給定序列S，用戶定義的間隔約束g，以及最小支持度閾值min_sup，從序列S中挖掘同時(shí)滿足間隔約束和最小支持度的頻繁序列模式，并且要求模式在序列中的出現(xiàn)滿足one-off條件，即模式的任意兩次出現(xiàn)都不共享序列S中同一位置的字符。針對(duì)這一問題，提出一種基于寬度優(yōu)先搜索的帶有通配符的序列模式挖掘算法One-off Mining，基于一遍掃描技術(shù)

4、計(jì)算模式在序列中同時(shí)滿足間隔約束和one-off條件的支持度，利用Apriori性質(zhì)，由長(zhǎng)度為k-1的頻繁模式進(jìn)行連接，生成長(zhǎng)度為七的候選模式。實(shí)驗(yàn)結(jié)果表明，One-off Mining算法在挖掘更多的頻繁序列模式情況下，時(shí)間效率得到了顯著地提高。
　　 (2)提出一種基于模式擴(kuò)展的帶有通配符的序列模式挖掘算法MAIL，利用前綴模式的出現(xiàn)信息，構(gòu)造擴(kuò)展模式的候選出現(xiàn)空間，有效地降低了模式挖掘過程中產(chǎn)生的候選模式的規(guī)模，同時(shí)避免了

5、每次計(jì)算模式支持度時(shí)都需要重復(fù)掃描序列。設(shè)計(jì)了兩種對(duì)候選模式出現(xiàn)進(jìn)行有效約簡(jiǎn)的剪枝策略：最左優(yōu)先剪枝和最右優(yōu)先剪枝，討論了兩種剪枝策略對(duì)帶有通配符的序列模式挖掘算法性能的影響。實(shí)驗(yàn)結(jié)果表明，MAIL算法能進(jìn)一步提高解的完備性和算法的時(shí)間效率。
　　 (3)在MAIL算法基礎(chǔ)上，提出一種層次有向無環(huán)圖數(shù)據(jù)結(jié)構(gòu)，能在多項(xiàng)式時(shí)間和空間復(fù)雜度內(nèi)，構(gòu)造和存儲(chǔ)指數(shù)量級(jí)的模式的候選出現(xiàn)，利用深度優(yōu)先搜索策略對(duì)層次有向無環(huán)圖進(jìn)行遍歷，計(jì)算模式的

6、支持度。從理論上證明，基于層次有向無環(huán)圖的帶有通配符的序列模式挖掘算法，在模式擴(kuò)展過程中不會(huì)丟失解，在對(duì)圖進(jìn)行深度遍歷計(jì)算模式支持度時(shí)，能夠獲取模式的優(yōu)化解。從實(shí)驗(yàn)角度驗(yàn)證基于層次有向無環(huán)圖的序列模式挖掘算法計(jì)算出的解接近最優(yōu)解的精度達(dá)到90％以上。
　　 (4)基于文本模式的關(guān)鍵詞抽取研究，將帶有通配符的序列模式挖掘算法應(yīng)用在文本挖掘領(lǐng)域的關(guān)鍵詞抽取任務(wù)中。針對(duì)文本序列數(shù)據(jù)庫具有的長(zhǎng)序列、大字符集等特性，將基于層次有向無環(huán)圖的

7、MAIL算法進(jìn)行了改進(jìn)，以提高文本序列模式挖掘的效率。從文本序列中挖掘帶有通配符的詞語序列模式，分析詞語之間的語義關(guān)聯(lián)性。利用機(jī)器學(xué)習(xí)分類算法對(duì)獲取的詞語模式特征進(jìn)行學(xué)習(xí)，構(gòu)造關(guān)鍵詞抽取模型，討論了不同的模式特征對(duì)關(guān)鍵詞抽取算法性能的影響。實(shí)驗(yàn)結(jié)果表明，詞語的模式特征能夠提高抽取關(guān)鍵詞的質(zhì)量，并且不受具體語言和知識(shí)庫的限制。提出一種基于詞匯鏈的新聞網(wǎng)頁關(guān)鍵詞抽取方法，利用知識(shí)詞典HowNet獲取詞語語義知識(shí)，借助詞匯鏈模型計(jì)算詞語在文檔