挖掘序列模式和結(jié)構(gòu)化模式的精簡(jiǎn)集.pdf

1、在今天的信息社會(huì)中，人們已經(jīng)擁有了大量的數(shù)據(jù)，迫切需要將這些數(shù)據(jù)轉(zhuǎn)化為有用的信息和知識(shí)。在這樣的背景下，數(shù)據(jù)挖掘這門新興學(xué)科受到廣泛的關(guān)注。數(shù)據(jù)挖掘是在大量的數(shù)據(jù)中尋找知識(shí)，其中，序列模式和結(jié)構(gòu)化模式的挖掘是一個(gè)重要的數(shù)據(jù)挖掘問題，有著廣泛的應(yīng)用。 在序列模式的挖掘中，最為重要、最有影響力的算法包括GSP 算法和PrefixSpan算法。這些算法都是挖掘頻繁序列模式的全集，當(dāng)序列模式的數(shù)量很大時(shí)，挖掘序列模式的全集不僅效率很低，

2、而且效果也不好，因?yàn)橐鎯?chǔ)和理解這么多的序列模式是不現(xiàn)實(shí)的。解決這個(gè)問題的一種途徑就是不再去挖掘序列模式的全集，而是只挖掘它的一個(gè)精簡(jiǎn)集。精簡(jiǎn)集保留了頻繁序列模式的總體信息，但序列模式的數(shù)目大為減少，有助于用戶理解挖掘結(jié)果，也有助于提高挖掘算法的效率。 精簡(jiǎn)的頻繁序列模式基就是這樣一種精簡(jiǎn)集，它是頻繁序列模式全集的一個(gè)特殊子集，能用它來估計(jì)不在其中的序列模式的支持度，而且誤差能保證在用戶指定的誤差上限內(nèi)。有兩種構(gòu)造精簡(jiǎn)的頻繁序列

3、模式基的方法：第一種方法逐級(jí)檢查所有的頻繁序列模式，當(dāng)一個(gè)頻繁序列模式不能被它在精簡(jiǎn)基中的子模式估計(jì)支持度時(shí)，它才被加到精簡(jiǎn)基中；第二種方法用相對(duì)于一系列支持度閾值的最大序列模式構(gòu)造精簡(jiǎn)的頻繁序列模式基。在采用這種方法的算法中，給出了如何判斷最大序列模式的方法，還設(shè)計(jì)了一些搜索空間剪枝技術(shù)，提前剪掉那些不可能生成最大序列模式的分支來加速挖掘過程。 壓縮頻繁序列模式集是針對(duì)頻繁序列模式的全集太大這個(gè)問題的另一種解決方法。為了得到高

4、質(zhì)量的壓縮效果，先對(duì)頻繁序列模式聚簇，再?gòu)拿總€(gè)簇中挑選出有代表性的序列模式，使這些有代表性的序列模式的數(shù)目盡可能地少。一個(gè)貪婪算法和一個(gè)基于候選集的快速算法是壓縮頻繁序列模式集的有效算法。有代表性的序列模式集合也是頻繁序列模式的一種精簡(jiǎn)集，實(shí)驗(yàn)結(jié)果表明它能取得很好的壓縮效果。 樹模式的挖掘比序列模式的挖掘更為困難，因?yàn)樵跇淠Ｊ降耐诰蛑?，子樹的組合方式太多。而精簡(jiǎn)的頻繁子樹基由相對(duì)于一系列支持度閾值的最大頻繁子樹組成，它是頻繁子樹

5、的一個(gè)精簡(jiǎn)集，可以用它來估計(jì)任一頻繁子樹的支持度，并能將誤差控制在確定范圍內(nèi)。一個(gè)算法能用來從帶標(biāo)號(hào)的有根有序樹的數(shù)據(jù)庫(kù)中挖掘子樹精簡(jiǎn)基，這個(gè)算法經(jīng)過簡(jiǎn)單的擴(kuò)展后也能用來挖掘有根無序樹。該算法采用最右擴(kuò)展的方式系統(tǒng)地生成頻繁子樹，采用的剪枝技術(shù)能減小搜索空間，合理安排的計(jì)算次序能提高計(jì)算的效率。 數(shù)據(jù)庫(kù)中的頻繁模式可以用于建立數(shù)據(jù)庫(kù)索引。基于樹模式的數(shù)據(jù)庫(kù)索引首先挖掘頻繁子樹，并從中挑選出有判別力的子樹作為索引屬性，然后將索引屬