基于回溯的最大頻繁項集挖掘算法

張心靜，于嘉威，王紅梅

(長春工業大學 計算機科學與工程學院，吉林 長春 130012)

?

基于回溯的最大頻繁項集挖掘算法

張心靜，于嘉威，王紅梅

(長春工業大學 計算機科學與工程學院，吉林 長春 130012)

針對Apriori類算法多次掃描數據庫和FP-tree類算法需要構建大量條件模式樹的問題，文中提出了挖掘最大頻繁項集的GBMFI算法。采用垂直格式存儲事務數據庫，以枚舉樹為基礎，利用子集非頻繁性質和父子節點支持度信息在搜索過程中對枚舉樹進行剪枝，最終得到最大頻繁項集。通過實驗對比，結果證明了算法的有效性，尤其適用于稀疏數據集。

數據挖掘；最大頻繁項集；關聯規則；回溯法；剪枝

隨著大數據時代的發展，數據挖掘技術在這個領域發揮的作用變得不可小覷[1]。發現關聯規則是數據挖掘工作的重點。而挖掘頻繁項集又是尋找關聯規則的重要步驟之一。但在通常情況下得到的頻繁項集數量龐大，且彼此之間存在項重復的現象，這就導致了信息冗余的問題。由于最大頻繁項集隱含了所有頻繁項集的信息，大幅縮減了頻繁項集的數量，因此挖掘最大頻繁項集的任務應運而生。挖掘最大頻繁項集的算法通常基于Apriori[2]和FP-tree[3]思想。一方面，基于Apriori改進的算法自底向上逐漸產生所有頻繁項集，但在這一過程中也會因連接操作生成大量的候選項集，同時為了削減候選項集，導致算法多次掃描整個事務數據庫，耗費了時間與資源。尤其是針對大數據進行處理時，產生的項集規模過大使得計算機難以對其進行存儲與計算，高效得到價值密度高的數據更加困難。……