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

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

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

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

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

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