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

1、隨著大數(shù)據(jù)時代的到來，出現(xiàn)了大量的序列數(shù)據(jù)，而當(dāng)前研究的熱點與難點是從其中挖掘出用戶感興趣以及有價值的信息。然而，目前大多數(shù)的研究都為非負(fù)間隙的序列模式匹配，對每個字符的出現(xiàn)順序有著嚴(yán)格的要求，限制了模式匹配的靈活性，降低了模式匹配的實用價值。關(guān)鍵詞抽取是文本挖掘的重點問題，關(guān)鍵詞是對一個文檔中信息的概括與濃縮，但是目前的關(guān)鍵詞抽取研究對抽取模式進行了嚴(yá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)，在具有間隙約束的模式中允許子模式串之間的間隙為負(fù)值，同時加入了one-off條件，允許序列串中任意位置的字符最多使用一次的精確的嚴(yán)格模式匹配。之后，通過理論證明了SPMGOO問題為NP-Hard問題。并首次使用線性表解決SPMGOO問題，并且在模式匹配的過程中首次提出對模式串的結(jié)構(gòu)以及序列串中各字符頻度進行分析，判斷是否需要轉(zhuǎn)置操作，使模式與序列達(dá)到最佳匹配狀態(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算法具有較高的準(zhǔn)確性，和較低的時空復(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