研究了當(dāng)前幾種時(shí)興的頻集挖掘算法（Apriori，DF，F(xiàn)P－growth 和DCI）及其技術(shù)特點(diǎn)，并對其分類和界定適用范圍。對其算法復(fù)雜性及時(shí)空執(zhí)行效率等性能指標(biāo)進(jìn)行了定性和定量的綜合分析。研究的結(jié)果對于在各種應(yīng)用環(huán)境下的
關(guān)聯(lián)挖掘系統(tǒng)的設(shè)計(jì)具有參考價(jià)值。
關(guān)鍵詞：　頻集挖掘；　Apriori；　DF；　FP－growth；　DCI
種頻集挖掘算法及其特點(diǎn)
2．1　Apriori 算法
A priori算法是目前最為著名也是應(yīng)用最為廣泛的一種算法，并且目前許多算法都是在A priori的基礎(chǔ)上優(yōu)化和改進(jìn)而來的。A priori算法核心思想是：首先掃描一遍數(shù)據(jù)庫D ，產(chǎn)生頻繁1 項(xiàng)集L 1，然后產(chǎn)生頻繁2 項(xiàng)集L 2，直到有某個(gè)r 值使得L r 為空，這時(shí)算法停止。在第k 次循環(huán)過程中，首先產(chǎn)生候選k－項(xiàng)集的集合C k，C k 中的每一個(gè)項(xiàng)集是對2 個(gè)只有一個(gè)項(xiàng)不同的屬于L k－1 的頻集做一個(gè)（k － 2） 連接產(chǎn)生的。C k 是用來產(chǎn)生頻集的候選集，為了決定C k 中的元素是否頻繁，必須掃描數(shù)據(jù)庫D 計(jì)算其支持度，因此頻集L k 是C k 的一個(gè)子集［1］。C k 中的每個(gè)元素需進(jìn)行驗(yàn)證來決定其是否加入L k ，這里的驗(yàn)證過程是算法性能的一個(gè)瓶頸。A priori算法的不足之處在于：1）可能產(chǎn)生大量的候選集。例如，當(dāng)長度為1 的頻集有104 個(gè)的時(shí)候，長度為2 的候選集個(gè)數(shù)將會(huì)超過107；2）如果要生成一個(gè)很長的規(guī)則時(shí)，要產(chǎn)生的中間元素也是巨量的。
2．2　DF 算法
D F 算法其實(shí)是A priori的一種改進(jìn)算法，最重要的區(qū)別在于其采用了深度優(yōu)先的方法，這也正是其稱之為D F（D epth F irst）的原因。D F 算法采用了層次樹（trie）來存儲(chǔ)頻繁項(xiàng)集。因?yàn)槿魏我粋€(gè)頻繁集的子集也是頻繁的，所以trie 很適合用來存儲(chǔ)頻繁項(xiàng)集。D F 算法執(zhí)行如下操作［2］：掃描一遍數(shù)據(jù)庫；計(jì)算各個(gè)項(xiàng)的支持度；并將頻繁項(xiàng)按支持度排序；在主存中建立trie，trie 從根到葉子的每一條路徑代表一個(gè)唯一的頻繁項(xiàng)集；最后，算法輸出trie 中的所有路徑，即所有的頻繁項(xiàng)集。