基于約束的序列模式挖掘及其應(yīng)用研究.pdf

1、序列模式挖掘就是從給定序列數(shù)據(jù)庫(kù)中發(fā)現(xiàn)頻繁的子序列作為模式。它是數(shù)據(jù)挖掘領(lǐng)域的重要分支，具有廣泛的應(yīng)用場(chǎng)景，例如序列分類和預(yù)測(cè)，識(shí)別Web日志中的訪問(wèn)模式，生物序列分析以及自然語(yǔ)言分析。研究者們對(duì)序列模式挖掘有著深入的研究，主要包括一般序列模式挖掘、精簡(jiǎn)序列模式挖掘和興趣度序列模式挖掘。閉合序列模式挖掘和序列生成器挖掘是兩種最重要的序列模式挖掘方法，這是由于它們生成的模式是一般序列模式的精簡(jiǎn)且無(wú)損的表示，因此成為序列模式挖掘研究中的熱點(diǎn)

2、問(wèn)題。
　　然而，現(xiàn)有的閉合序列模式挖掘和序列生成器挖掘算法，當(dāng)使用的最小支持度較小或給定的序列數(shù)據(jù)庫(kù)較稠密時(shí)，會(huì)產(chǎn)生指數(shù)級(jí)的模式，其中含有大量的冗余模式。由于生成的結(jié)果集容量過(guò)大而無(wú)法有效用于序列分析和預(yù)測(cè)。這已成為精簡(jiǎn)序列模式挖掘的難點(diǎn)問(wèn)題。此外，算法中剪枝、生成和維護(hù)等過(guò)程使得這些算法具有高昂的時(shí)間和空間代價(jià)。本文致力于研究更精簡(jiǎn)但不丟失信息的序列模式挖掘算法。
　　為解決上述問(wèn)題，探索了將鄰接約束與閉合約束結(jié)合來(lái)進(jìn)行

3、更精簡(jiǎn)且無(wú)損的序列模式挖掘，即閉合鄰接序列模式挖掘和鄰接序列生成器挖掘。同時(shí)提出一個(gè)基于相似度的FIND-S算法，稱之為FIND-SS，來(lái)執(zhí)行定義序列模式挖掘。此外，所獲得的定義序列模式用于本體學(xué)習(xí)模型中的概念提取。如下給出本文的主要工作內(nèi)容。
　　1.提出CCSpan算法執(zhí)行閉合鄰接序列模式挖掘。CCSpan采用片段增長(zhǎng)的方法來(lái)生成潛在的序列模式，運(yùn)用三種剪枝策略來(lái)有效減少算法的搜索空間。通過(guò)上閉合約束（Upper-closed

4、 constraint）來(lái)生成完整的閉合鄰接序列模式集合。
　　2.探索了序列模式中等價(jià)類的屬性，提出鄰接序列生成器挖掘算法，即ConSgen算法?；贑CSpan算法的片段增長(zhǎng)方法和剪枝技術(shù)，得到一個(gè)具有鄰接屬性的序列模式集合。該集合可劃分為一系列的等價(jià)類，然后從每個(gè)等價(jià)類中識(shí)別出具有下閉合約束（Lower-closedconstraint）屬性的序列模式作為鄰接序列生成器。
　　3.提出基于相似度的FIND-S算法，稱之

5、為FIND-SS算法。Find-SS采用“越相似優(yōu)先級(jí)越高”的方法來(lái)泛化序列數(shù)據(jù)庫(kù)中的每對(duì)序列。同時(shí)，上界假設(shè)（Upper Bound Hypotheses）用于算法的搜索過(guò)程，產(chǎn)生一系列的目標(biāo)假設(shè)（Target concept）。FIND-SS能夠處理含噪聲的序列數(shù)據(jù)，并且不需要任何種子模式來(lái)挖掘定義序列模式。
　　4.設(shè)計(jì)出基于定義序列模式的概念提取方法來(lái)改進(jìn)本體學(xué)習(xí)系統(tǒng)性能。首先運(yùn)用定義序列模式在給定語(yǔ)料上提取定義句子，然后