一般間隙序列模式挖掘及其在關(guān)鍵詞抽取中的應(yīng)用.pdf

1、隨著大數(shù)據(jù)時代的到來，出現(xiàn)了大量的序列數(shù)據(jù)，而當前研究的熱點與難點是從其中挖掘出用戶感興趣以及有價值的信息。然而，目前大多數(shù)的研究都為非負間隙的序列模式匹配，對每個字符的出現(xiàn)順序有著嚴格的要求，限制了模式匹配的靈活性，降低了模式匹配的實用價值。關(guān)鍵詞抽取是文本挖掘的重點問題，關(guān)鍵詞是對一個文檔中信息的概括與濃縮，但是目前的關(guān)鍵詞抽取研究對抽取模式進行了嚴格的限制，不能夠靈活的獲取詞語間的語義關(guān)系，導(dǎo)致不能對文檔進行有效自主的關(guān)鍵詞提取。

2、因此，本文提出了一般間隙的序列模式挖掘算法并在關(guān)鍵抽取中進行應(yīng)用研究，一般間隙的模式匹配研究不僅在理論上具有研究的價值，而且在生物信息學(xué)，文本挖掘等領(lǐng)域具有廣泛的應(yīng)用價值。
　　本文是基于一般間隙與one-off條件的序列模式匹配，序列模式挖掘及其在文本領(lǐng)域中關(guān)鍵詞抽取的應(yīng)用進行研究。內(nèi)容主要關(guān)于三個方面:
　　(1)同時具有一般間隙與one-off條件約束的序列模式匹配的算法設(shè)計及分析;
　　(2)在序列模式匹配的基

3、礎(chǔ)上，進行一般間隙與one-off條件下的序列模式挖掘問題研究;
　　(3)將一般間隙與one-off條件下的序列模式挖掘算法應(yīng)用到文本信息挖掘中，通過挖掘出詞語間的語義關(guān)系，進行關(guān)鍵詞的抽取。
　　本文主要的工作與創(chuàng)新點如下:
　　(1)在序列模式匹配研究中，提出了一般間隙與one-off條件的序列模式匹配問題SPMGOO(Sequential Pattern Matching with General gaps a

4、nd One-Offcondition)，在具有間隙約束的模式中允許子模式串之間的間隙為負值，同時加入了one-off條件，允許序列串中任意位置的字符最多使用一次的精確的嚴格模式匹配。之后，通過理論證明了SPMGOO問題為NP-Hard問題。并首次使用線性表解決SPMGOO問題，并且在模式匹配的過程中首次提出對模式串的結(jié)構(gòu)以及序列串中各字符頻度進行分析，判斷是否需要轉(zhuǎn)置操作，使模式與序列達到最佳匹配狀態(tài)。
　　(2)在序列模式匹配

5、研究中，提出了基于一般間隙與one-off條件的最大數(shù)目的序列模式匹配算法MSAING(Maximum Sequential pattern mAtching wIthoNe-off and General gaps condition)。MSAING算法首先采用Reverse策略判斷是否需要轉(zhuǎn)置操作;然后，利用線性表的結(jié)構(gòu)進行模式匹配，具體分為定位階段、Forward階段、Backward階段，使MSAING算法在模式匹配過程中消耗的

6、時間和內(nèi)存大大的減少，同時在Backward階段使用回溯機制，使匹配的成功率大幅度提高;最后，提出了inside_Checking機制判斷模式串是否會產(chǎn)生內(nèi)部重復(fù)現(xiàn)象，以及如果產(chǎn)生內(nèi)部重復(fù)會在模式串的哪個位置產(chǎn)生，從而有效的提高了MSAING算法的運行效率。并首先從理論上證明了MSAING算法比目前已有算法具有更好的完備性，對于不含重復(fù)的模式能夠取得完備解。其次，本文在真實的生物數(shù)據(jù)集以及文本上，與DCNP等多種相關(guān)的改進算法進行了對比

7、實驗，通過實驗結(jié)果驗證了MSAING算法具有較高的準確性，和較低的時空復(fù)雜度，并對實驗結(jié)果及其意義進行了分析。
　　(3)在序列模式挖掘研究中，提出了一般間隙與one-off條件的序列模式挖掘算法SPING(Sequential Pattern mIning with oNe-off and General gaps condition)。SPING算法在一般間隙的條件下不僅能夠獲取不連續(xù)的序列模式，同時也可以挖掘出前后顛倒的頻繁

8、模式，提高了模式挖掘的靈活性。該算法獲取模式更加完備的解，從而挖掘出更加真實的信息，并通過在生物序列及其對比實驗驗證了該算法的有效性。
　　(4)在關(guān)鍵詞抽取研究中，提出了關(guān)鍵詞抽取算法KEING(KeyphraseExtraction using sequentIal patterns with oNe-off and General gaps condition)。一般間隙能夠更有效的獲取詞語，詞組之間的語義關(guān)系，因此利用SP