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

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

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

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

4、nd One-Offcondition)，在具有間隙約束的模式中允許子模式串之間的間隙為負(fù)值，同時(shí)加入了one-off條件，允許序列串中任意位置的字符最多使用一次的精確的嚴(yán)格模式匹配。之后，通過(guò)理論證明了SPMGOO問(wèn)題為NP-Hard問(wèn)題。并首次使用線性表解決SPMGOO問(wèn)題，并且在模式匹配的過(guò)程中首次提出對(duì)模式串的結(jié)構(gòu)以及序列串中各字符頻度進(jìn)行分析，判斷是否需要轉(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)進(jìn)行模式匹配，具體分為定位階段、Forward階段、Backward階段，使MSAING算法在模式匹配過(guò)程中消耗的

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

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

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