一種自底向上的最大頻繁項(xiàng)集挖掘方法

趙 陽(yáng)，吳廖丹

(江南計(jì)算技術(shù)研究所，江蘇 無(wú)錫 214083)

一種自底向上的最大頻繁項(xiàng)集挖掘方法

趙 陽(yáng)，吳廖丹

(江南計(jì)算技術(shù)研究所，江蘇 無(wú)錫 214083)

頻繁項(xiàng)集挖掘是關(guān)聯(lián)規(guī)則挖掘中最關(guān)鍵的步驟。最大頻繁項(xiàng)集是一種常用的頻繁項(xiàng)集簡(jiǎn)化表示方法。自頂向下的最大頻繁項(xiàng)集挖掘方法在最大頻繁項(xiàng)集維度遠(yuǎn)小于頻繁項(xiàng)數(shù)時(shí)往往會(huì)產(chǎn)生過(guò)多的候選頻繁項(xiàng)集。已有的自底向上的最大頻繁項(xiàng)集挖掘方法或者需多次遍歷數(shù)據(jù)庫(kù)，或者需遞歸生成條件頻繁模式樹(shù)，而預(yù)測(cè)剪枝策略有進(jìn)一步提升的空間。為此，提出了基于最小非頻繁項(xiàng)集的最大頻繁項(xiàng)集挖掘算法(BNFIA)，采用基于DFP-tree的存儲(chǔ)結(jié)構(gòu)，通過(guò)自底向上的方式挖掘出最小非頻繁項(xiàng)集，利用最小非頻繁項(xiàng)集的性質(zhì)進(jìn)行預(yù)測(cè)剪枝，以縮小搜索空間，再通過(guò)邊界頻繁項(xiàng)集快速挖掘出最大頻繁項(xiàng)集。驗(yàn)證實(shí)驗(yàn)結(jié)果表明，提出算法的性能較同類(lèi)算法有較為明顯的提升。

最大頻繁項(xiàng)集；關(guān)聯(lián)規(guī)則挖掘；FP-tree；最小非頻繁項(xiàng)集；邊界頻繁項(xiàng)集

0 引 言

關(guān)聯(lián)規(guī)則挖掘的概念由Agrawal等于1993年提出[1-3]，用于發(fā)現(xiàn)大量數(shù)據(jù)中項(xiàng)目或項(xiàng)目集之間有趣的關(guān)聯(lián)或相關(guān)關(guān)系，同時(shí)提出了經(jīng)典的關(guān)聯(lián)規(guī)則挖掘算法—Apriori。此后眾多學(xué)者對(duì)Apriori算法進(jìn)行了改進(jìn)。但Apriori系列算法需要多次掃描數(shù)據(jù)集的固有缺陷，使其在處理大型數(shù)據(jù)集時(shí)面臨無(wú)法容忍的時(shí)間開(kāi)銷(xiāo)。針對(duì)這一問(wèn)題，Han等[4]提出用FP-tree對(duì)數(shù)據(jù)進(jìn)行壓縮存儲(chǔ)以及基于FP-tree的頻繁模式挖掘方法—FP-growth。該算法只需掃描數(shù)據(jù)集兩次，避免了Apriori算法需多次掃描數(shù)據(jù)集的缺陷。……