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

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

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

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

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

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

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

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