最大頻繁項集挖掘算法綜述

摘要：關聯規則挖掘是近年來數據挖掘領域中一個相當活躍的領域，頻繁項集挖掘是關聯規則挖掘中最重要的任務。最大頻繁項集的規模遠遠小于頻繁項集的規模，通過最大頻繁項集可以導出所有的頻繁項集，因此進行了很多專門挖掘最大頻繁項集的研究。給出了關聯規則和相關術語的基本概念，對最大頻繁項集挖掘算法作了分析與評價，便于研究者對已有的算法進行改進，提出具有更好性能的新算法。

關鍵詞：數據挖掘；關聯規則；最大頻繁項集；算法綜述

中圖分類號：TP311文獻標識碼：A 文章編號：1009-3044(2008)32-1030-02

Survey of Algorithms for Mining Maximal Frequent Itemsets

CHEN Chen

(Jiangsu Finance and Economics Professional Technology Institute， Huai'an 223003， China)

Abstract: Mining association rules is quite an active field in the research of data mining in recent years， and mining frequent itemsets is the most important task of mining association rules. The scale of maximal frequent itemsets is much less than the scale of frequent itemsets， and all frequent itemsets can be educed from maximal frequent itemsets， so researchers do much work for mining maximal frequent itemsets specially. It presents that the definitions of association rule and relative terms， and simply surveys that the algorithms of max frequent itemsets mining and its incremental mining to provide a basis for for improving old algorithms or developing new effective ones.

Key words: data mining; association rules; maximal frequent itemset; algorithms survey

1 引言

數據挖掘技術是近年來國內外迅速發展起來的一門交叉學科，被認為是網絡技術之后的下一個信息技術熱點。數據挖掘又稱數據庫中的知識發現，是指從大量數據中發現有效的、新穎的、具有潛在作用的、能被用戶理解的模式的處理過程。R.Agrawal等人首先提出的關聯規則挖掘問題是數據挖掘的主要任務之一[1]，近年來受到了數據庫界的廣泛關注。

關聯規則挖掘是尋找在同一個事件中出現的不同項的相關性，即找出事件中頻繁發生的項或屬性的所有子集，以及它們之間應用相互關聯性。關聯規則最早用于發現顧客交易數據庫中不同商品間的聯系，后來諸多的研究人員對關聯規則的挖掘問題進行了大量的拓展和研究。關聯規則的挖掘一般可分成兩個步驟：1)找出所有支持度大于等于最小支持度閾值的頻繁項集FI(Frequent Itemset)；2) 由頻繁項集生成滿足置信度閾值的關聯規則。第1)步的工作是相當費時的，而第2)步在第1)步的基礎上很容易實現，因此發現頻繁項目集是關聯規則挖掘應用中的關鍵技術和步驟。

Bayardo針對挖掘所有的頻繁項集要考慮太多的候選集，提出挖掘最大頻繁項集MFI(Maximal Frequent Itemset)[2]。由于MFI的規模遠遠小于FI，通過MFI可以導出所有的FI，而且許多數據挖掘應用也只需要挖掘MFI而不用挖掘所有的FI，因此近些年來很多研究人員開始研究專門用于挖掘MFI的算法。下面簡單介紹關聯規則和頻繁項集的相關概念，然后對現有的一些最大頻繁項集挖掘算法作簡單評述，并著重介紹幾種典型的算法，便于研究者對已有算法進行改進，提出具有更好性能的新算法。

2 問題描述

設I ={il，i2，…，im}為m個不同文字的集合，其中的文字稱為項，或者商品。稱任何X?哿I為一個項集(如果|X|=k，則稱X為k項集)。記D={T1，T2，...，Tn }，其中Ti稱為一個交易或事務，稱D為I上的交易集或者數據集，簡稱交易集或者數據集。

定義2.1 給定I，關聯規則就是形如X?圯Y的一個表達式，其中，X?哿I， Y?哿I，X∩Y=?覫。

定義2.2 給定D和項集X，并給定min_sup∈(0 ，1)，稱sup D(X)=|DX|/|D|為項集X在數據集D上的支持度(簡記為sup(X))，當sup(X)≥min_sup時，項集X稱為D上的頻繁項集。D上所有頻繁項集的集合記為：FID={X|X?哿I∧sup(X)≥min_sup}。

定義2.3 稱項集X是數據集D上的最大頻繁項集，當且僅當滿足：①sup(X)≥min_sup；②?坌Y(Y?哿I∧X?奐Y→sup(Y)sup(Y)

顯然，任何頻繁項目集都是某最大頻繁項目集的子集，所以可以把發現所有頻繁項目集的問題轉化為發現所有最大頻繁項目集的問題。

3 最大頻繁項集挖掘算法

已有最大頻繁項集挖掘算法可以按照文獻[2]中提出的搜索空間樹的遍歷策略分為寬度優先算法和深度優先算法兩類。早期的最大頻繁項集挖掘算法多使用集合枚舉樹作為概念框架，Han等人提出FP-Tree結構和頻繁項集挖掘算法FP-Growth[3]后，新的最大頻繁項集挖掘算法大多基于FP-Tree結構，據此也可以將最大頻繁項集算法分為基于非FP-Tree結構和基于FP-Tree結構兩類。下面對現有的一些最大頻繁項集挖掘算法作簡單評述，并著重介紹幾種典型的算法。

1) Max-Miner[2]Bayardo在提出最大頻繁項集概念的同時提出了Max-Miner算法。Max-Miner算法使用集合枚舉樹作為概念框架，對枚舉樹采用廣度優先搜索策略，此外還使用了稱為“look ahead”的超集剪枝策略(即“如果一個結點的head∪tail是頻繁的，則該結點的所有分支一定是頻繁的而無須再處理”)和動態記錄技術(將項集按照其頻率從小到大動態排序的技術)，其缺陷是沒有利用自頂向下的信息和未對MFCS 進行適當的排序。

2) Pincer-Search[4]Pincer-Search算法采用了自底向上和自頂向下的雙向搜索策略，但其第k 次的MFCS 是由k-1次的MFCS 中的非頻繁項目集去掉一個元素來生成的，產生了過多的無用候選項目集，對海量數據庫來講，算法將陷入NP難度的陷阱。

3) DepthProject[5]DepthProject算法采用項集的字典順序樹作為概念模型，但對數據庫的表示采用的是項集位串(bitstring)。它采用了深度優先(depth first)搜索方法來生成MFI。在挖掘過程中該算法同樣采用了超集剪枝和動態記錄技術，另外還采用了稱為桶計數(bucket counting)的技術來加快項集的頻度計數。其實驗結果表明，DepthProject算法的性能比Max-Miner算法提高了一個數量級。

4) MAFIA[6]Burdick等人提出的MAFIA算法采用了與枚舉樹類似的項集網格和子集樹作為概念框架，并利用縱向位圖(vertical bitmap)存儲事務數據。MAFIA算法采用深度優先遍歷策略，采用PEP(parent equivalence pruning)，FHUT(frequent head union tail)，HUTMFI(利用已知的MFI去剪枝結點)和動態重排序(dynamic reordering)技術來進行搜索空間剪枝，并采用了有效的MFI超集檢測(superset checking)技術，使其性能比DepthProject提高了數倍。

5) GenMax[7]GenMax算法也采用基于集合枚舉樹的概念模型，它將剪枝與挖掘過程集成在一起，并使用兩種策略使之正好返回MFI。一種策略是將已找到的MFI都投影到當前結點以產生快速的超集檢測，另一種策略是利用Diffset技術(一種對數據的縱向表示法)減少存儲空間占用及實現快速頻度計算。GenMax算法使用局部最大頻繁項集用于超集檢測，在一定程度上降低了前瞻剪枝的開銷，實驗結果表明MAFIA算法和GenMax算法對不同數據集的性能各有不同，但總體性能基本相當。

6) SmartMiner[8]SmartMiner算法也是基于集合枚舉樹的概念模型和縱向數據表示法。該算法在挖掘過程中使用一種稱為尾信息的數據結構來指導挖掘過程，能充分利用已挖掘出來的最大頻繁項集中的相關信息。雖然SmartMiner算法不需要超集檢測，但是其尾信息的建立和訪問代價不菲。

7) DMFIA[9]DMFIA算法針對MaxMiner的缺陷進行了改進，通過兩次掃描建立FP-tree來壓縮表示事務數據庫中與頻繁項集相關的信息，從而避免了對數據庫的多遍掃描。DMFIA算法是首個基于FP-Tree結構的最大頻繁項集挖掘算法，相比以前的算法提高了執行效率。

8) FPmax*[10]Grahne提出的FPmax和Fpmax*算法同樣基于FP-tree結構。FPmax算法將最大頻繁項集保存在一棵MFI-Tree(maximal frequent itemsets tree)中，在一定程度上提高了最大頻繁項集的存取速度。FPmax*算法在FPmax算法的基礎上采用了一種名為FP-Array的技術，使得每次建立條件頻繁模式樹時可以只掃描一次上一層的條件頻繁模式樹。建立FP-array結構的代價很高，文獻[10]中提出的一種解決策略是預先判斷建立FP-array的代價，當這種代價可以承受時才采用這種策略。FPmax*在與MAFIA和GenMax的性能比較中，優于這兩個算法。

9) SFPMax[11]SFPMax算法基于排序Fp-樹結構，利用最大頻繁項集的性質減小產生的候選最大項集的規模，并通過設置中間結果集來縮小檢驗的范圍從而減少檢驗候選最大模式的時間。實驗表明，SFPMax的性能多數情況下都優于MAFIA算法。

10) FPMFI[12]Yan等人指出在最大頻繁項集的挖掘過程中，當最小支持度較小時超集檢測是算法的主要耗時操作，由此提出了FPMFI算法。FPMFI算法使用基于投影進行超集檢測的機制，有效地縮減了超集檢測的時間，另外通過刪除條件頻繁模式樹的冗余信息，有效地壓縮了條件頻繁模式樹的規模，減少了遍歷的開銷。

11) MMFI[13]Ju和Chen提出的MMFI算法基于改進的FP-Tree結構，通過修改結點結構建立有序FP-Tree以及采用一種名為NBN(node by node)的遍歷策略，使得在挖掘過程中既不需要進行超集檢測也不需要遞歸的建立條件頻繁模式樹，有效的提高了算法的執行效率。MMFI算法中需要沿結點鏈搜索本層右側的結點，檢測是否存在當前處理項集的子集，這一操作的效率有待提高。

5 結束語

本文討論了現有的最大頻繁項集挖掘算法，并對其中的典型算法進行了簡要的分析。關于這方面的研究已經取得了很大的成績，但仍存在許多問題有待進一步地深入研究，比如如何更為高效的進行超集檢測或者以更小的代價避免超集檢測和建立條件頻繁模式樹等。實踐證明，沒有一種挖掘算法對所有類型的數據都優于其它算法，每種相對較優的算法都有它具體的適用環境。所以，熟知不同算法的不同特性和適用條件，可使研究者明確算法的改進點和研究方向，讓使用者更易于使用。

參考文獻：

[1] Agrawal R， Imietinski T， Swami A. Mining association rules between sets of items in large database[C]. Washington: Proceeding of the ACM SIGMOD International Conference on Management of Data， 1993: 207-216.

[2] Bayardo R. Efficiently mining long patterns from databases[C]. New York: ACM Press ， Proceeding of 1998 ACM SIGMOD International Conference on Management of Data (SIGMOD'98)， 1998. 85-93.

[3] Han J， Pei J， Yin Y. Mining frequent patterns without candidate generation[C]. Dallas: Proceeding of the ACM SIGMOD International Conference on Management of Data， 2000: 1-12.

[4] Lin DI， Kedem ZM. Pincer-Search: A new algorithm for discovering the maximum frequent set[C]. Heidelberg: Springer-Verlag， Proceedings of the 6th European Conference on Extending Database Technology. 1998：105-119.

[5] Agarwal R， Aggarwal C， Prasad V. Depth first generation of long patterns[C]. In Proceedings of 6th ACM SIGKDD Int’l Conf. on Knowledge Discovery and Data Mining. Boston : ACM Press ， 2000：108-118.

[6] Burdick D， Calimlim M， Flannick J， et al. MAFIA: a maximal frequent itemset algorithm[J]. IEEE Transactions on Knowledge and Data Engineering， 2005， 11:1490-1504.

[7] Gouda K， Zaki MJ. Efficiently mining maximal frequent itemsets[C]. Proceeding of the IEEE International Conference on Data Mining， 2001: 163-170.

[8] Zhou Q H， Wesley C， LU B J. SmartMiner: A depth 1st algorithm guided by tail information for mining maximal frequent itemsets[C]. Proceeding of the IEEE International Conference on Data Mining， 2002: 570-577.

[9] 宋余慶， 朱玉全， 孫志輝， 等. 基于FP-Tree的最大頻繁項集挖掘及其更新算法[J]. 軟件學報， 2003， 14(9): 1586-1592.

[10] Grahne G， Zhu JF. Fast algorithms for frequent itemset mining using FP-trees[J]. IEEE Transactions on Knowledge and Data Engineering， 2005， 10: 1347-1362.

[11] 秦亮曦， 史忠植. SFP-Max－基于排序FP-樹的最大頻繁模式挖掘算法[J]. 計算機研究和發展， 2005， 42(2): 217-223.

[12] 顏躍進， 李舟軍， 陳火旺. 基于FP-Tree有效挖掘最大頻繁項集[J]. 軟件學報， 2005， 16(2): 215-222.

[13] SG J， Chen C. MMFI: an effective algorithm for mining maximal frequent itemsets[C]. Proceeding of the IEEE International Symposium on Information Processing， IEEE CS Press， 2008: 26-30.