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