基于FP—Tree的最大頻繁項目集挖掘算法

陳向華++劉可昂

摘要：挖掘最大頻繁項目集是關聯規則挖掘中的關鍵問題，基于Apriori產生候選項目集需要付出很高的代價，尤其是在存在大量強模式或長模式的時候.提出一種基于頻繁模式樹（FP-Tree）的最大頻繁項目集挖掘算MFIP-Miner（maximum frequent itemsets pattern mmer），其挖掘過程無需產生候選項集，從而提高挖掘效率。

關鍵詞：數據挖掘；最大頻繁項集；關聯規則；頻繁模式樹

中圖分類號：TP311

文獻標識碼：A

DOI：10.3969/j.issn.1003-6970.2015.12.023

本文著錄格式：陳向華，劉可昂.基于FP-Tree的最大頻繁項目集挖掘算法[J]軟件，2015，36（12）：98-102

0 引言

關聯規則數據挖掘（簡稱關聯規則挖掘）就是從大量的數據中挖掘出有價值的描述數據項之間相互聯系的有關知識。自1993年Agrawal等人首先提出關聯規則概念以來，關聯規則挖掘便迅速受到數據挖掘域專家的廣泛關注。在迄今十幾年中，關聯規則挖掘技術得到了較為深入的發展。其中發現頻繁項目集是關聯規則挖據應用中的關鍵技術和步驟。對于頻繁項集挖掘，已經開發了許多有效的、可伸縮的算法，由它們可以導出關聯和相關規則。這些算法可以分成三類：（1）類Apriori算法；（2）基于頻繁模式增長的算法，如FP-growth；（3）使用垂數據格式的算法。在如上所述的諸多算法中，計算項目集的支持數是發現頻繁項目集中最耗時的工作，占據整個計算量的大部分，因此，降低候選項目集的數量是減小開銷的最好手段。

由于最大頻繁項目集中已經隱含了所有頻繁項目集，所以可把發現頻繁項目集的問題轉化為發現最大頻繁項目集的問題.另外，某些數據挖掘應用僅需發現最大頻繁項目集，而不必發現所有的頻繁項目集，因而發現最大頻繁項目集對數據挖掘具有重大意義。

目前已經提出的可用于發現最大頻繁項目集的算法主要有Gunopulos等人提出算法ALL-MFS，Bayardo等人提出的算法Max-Miner，Lin等人提出的算法Pincer-Search，以及Burdick等人提出的算法Mafia，路松峰等人提出的算法DMFI，宋余慶等人提出的算法DMFIA等。上文闡述的這些算法都能有效地挖掘出事務數據庫D中的最大頻繁項目集，然而它們也存在不足之處。比如：Max-Miner雖然突破了傳統的白底向上的搜索策略，盡可能早地對項目集進行修剪，但其存在的缺陷是：1）未利用白頂向下的信息進行剪枝；2）未對MFCS進行適當的排序，產生了多余的候選項目集；Pincer-Search雖然采用了白底向上和白頂向下的雙向搜索策略，但其在發現最大頻繁項目集的過程中產生了過多的無用候選項目集，對海量數據庫來講，將陷入NP難度的陷阱；DMFIA算法通過對D的兩次掃描，把其中的所有事務壓縮存儲到FP-Tree中，這樣在以后發現最大頻繁項目集的過程中僅需在FP-Tree中進行查找，無需再掃描D，所以該算法的效率相對于Max-Miner、Pincer-Search有顯著的提高，但它沒有充分利用FP-Tree的特點，且其第k次的最大頻繁候選集是由k-l次的最大頻繁候選集中的非頻繁項目集去掉一個項目來生成，所以也產生了大量的無用候選項目集；Mafia算法雖然利用垂直位圖來壓縮存儲數據庫中的事務，并且在挖掘過程中也采用了有效的剪枝技術，但其仍然要維護一個數量較大的候選項目集的集合，這降低了算法的整體性能。本文提出一種基于頻繁模式樹（FP-Tree）的最大頻繁項目集挖掘算法MFIP-Miner（maximum frequent itemsets pattemminer），其挖掘過程無需產生候選項集，從而提高挖掘效率。

1 問題描述

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

1.2 頻繁模式樹

在Han等人定義的頻繁模式樹FP-Tree中，每個節點由節點名稱node-name、節點計數node-count、節點鏈 node-link及父節點指針node-parent四部分組成。另外，為了方便樹的遍歷，創建一個頻繁項目頭表Htable，它包含兩個組成部分：項目名稱item-name和項目鏈頭item-head。FP-Tree的構造算法如下：

（1）掃描D一次，產生頻繁項目集合F及其支持數，并按支持數降序排列F生成頻繁項目列表IDF；

2 挖掘最大頻繁項集的算法MFIP-Miner

2.1 基本性質

性質1.在FP-Tree中，若某節點計數不小于s（s見定義1），則該節點和其前綴路徑中的節點組成的模式（項目集）必為頻繁模式。

證明：設節點Ⅳ為路徑P的后綴，且N.node-count≥s，由FP-Tree的構造過程可知，對于Ⅳ的前綴路徑p中的任一個節點N，一定有：N'.node-count≥N.node-count≥s，由此可知N即為P中最小節點，所以由P中所有節點組成的模式的計數必大于或等于s，即為頻繁模式。證畢。

性質2.若由某一頻繁項目T_i的條件模式基生成的條件FP-Tree中只含有單個路徑P時，則P中的所有項目與T_i的并集一定是頻繁項目集，且P∪T_i的支持數等于T_i中葉節點的支持數。

證明：由條件頻繁模式樹的構造過程可知，對于某一頻繁項目T_i，在其條件頻繁模式樹中的節點必為頻繁項目節點。由于此時樹中只含有單個路徑，而且路徑中的每個節點又都是頻繁項目節點，則由性質l可知，此路徑中的節點和項目T_i組成的模式必為頻繁模式。根據頻繁模式樹的構造方法可知，FP-Tree中的葉節點的節點計數是整個路徑中最小的，因此P∪T_i的支持數不可能大于或小于葉節點的節點計數，所以P∪T_i的支持數等于葉節點的支持數，證畢。

由上述性質可知，最大頻繁項目集一定存在于由條件FP-Tree產生的頻繁模式中。因此MFIP-Miner算法的基本思想是：依次從Htable中取出所有的頻繁項目，對每個項目構造其條件模式基和條件FP-Tree，對構造的條件FP-Tree進行如下處理：

（l）如果構造的條件FP-Tree中只含有單個路徑，則取出該路徑中所有項目，將它們與生成該條件FP-Tree的項目合并，組成一個頻繁模式，然后判斷此頻繁模式是否是MFIP中某項目集的子集，若不是，則此頻繁模式就為最大頻繁模式，并將其放入MFIP中，同時刪除MFIP中是該最大頻繁模式子集的項目集，若是則舍去。

（2）如果構造的條件中含有多個路徑，則依次從該條件FP-Tree所對應的Htable中取出所有項目，構造每個項目的條件FP-Tree，找出其包含的最大頻繁模式。可見整個發現過程是遞歸進行的，直到找出所有最大頻繁模式為止

（3）在挖掘過程中，若發現樹中的某個節點Ⅳ的計數不小于s，則從Htable中取出所有排列在N.node-name前面的項目組成集合X；然后，通過Ⅳ的同名節點鏈，找出節點鏈中所有計數不小于s的同名節點；最后，遍歷每條以同名節點為后綴的路徑P，檢查X是否存在于P中，一旦發現了這樣的路徑，則可將在當前頻繁模式（或條件頻繁模式）樹中的挖掘過程終止。

2.2 算法MFIP-Miner

輸入：最小支持度X._{sup D}，在此X._{sup D}下構造的FP-Tree T；

輸出：事務數據庫D中滿足X._{sup D}要求的最大頻繁項目集的集合MFIP。

（1）MFIP=NULL：

3 算法實現與比較

3.1 測試機配置

本文所用的測試機為Lenovo臺式機，其配置是：CPU為Pentium3.2GHz，操作系統為win7旗艦版，內存為4G，并選用R語言，在Eclipse+StatET編程環境中實現了算法MFIP-Miner算法和Mafia算法。

3.2 測試數據庫的選擇

為了能綜合測試MFIP-Miner算法的性能，本文選用了兩種類型的數據庫：Chess和Mushroom（它們可以從UCI Machine Leaming Repository上免費獲得）

3.3 對比算法選擇

本文通過對比MFIP-Miner算與Mafia算法在Chess和Mushroom數據庫運行效率，來分析和驗證MFIP-Miner算法的性能，之所以選擇Mafia算法作為比較的對象，主要是因為該算法是目前公認挖掘最大頻繁項目集最有效的算法。

3.4 在Chess數據庫上的測試分析

Chess數據庫的特點是最大頻繁項目集的分布比較對稱，而且大多數最大頻繁項目集的維數相對較低，平均長度約為37。從圖l中可以看出，算法MFIP-Miner在最小支持度大于20%時的執行效率要好于算法Mafia兩到三倍。然而，當最小支持度小于50%時算法MFIP-Miner的性能開始下降，而在最小支持度小于30%時性能下降的速度更大。產生這種現象的原因是：MFIP-Miner算法采用FP-Tree來壓縮存儲數據庫中的事務，并在該基礎上進行挖掘，由于充分利用了FP-Tree的特點，在挖掘過程中不需要產生候選項目集，這使其在挖掘過程中具有較高的效率。然而，MFIP-Miner算法在挖掘過程中需要產生條件頻繁模式基，當這種模式基數量巨大時會占用較多內存，以致復雜的內存管理花費了一些額外的開銷，使算法的性能趨于下降。而對于Mafia算法來說，由于其是基于Apriori算法的挖掘思想，需要生成大量的候選項目集，并對其進行支持度計算和頻繁性檢驗，因此Mafia算法需要花費大量的計算開銷。但是，Mafia算法采用了一種垂直位圖結構來表示事務，并且采用了一些有效的剪枝技術，因此，總的來說其在挖掘最大頻繁項目集方面也是很有效的。

3.5 在Mushroom數據庫上的測試分析

Mushroom數據庫的特點是最大頻繁項目集的分布比較密集，其中每個事務的長度為23，而絕大多數最大頻繁項目集的長度為20，因此，每個最大頻繁項目集中都有一些項目存在于每個事務中。從圖2中可以看出，MFIP-Miner算法在這種數據庫中的執行效率要好于在上面兩個數據庫中的執行效率，總的執行時間較少，這說明MFIP-Minerr算法對最大頻繁項目集較長且分布密集的數據庫有較大優勢。和Mafia算法相比，MFIP-Miner算法略優于前者，這也說明Mafia算法對最大頻繁項目集較長的挖掘也很有效。

4 結論

本文提出的MFIP-Miner算法能高效地挖掘出事務數據庫中的最大頻繁項目集，其在挖掘過程中不需要產生最大頻繁候選項目集，而且由于挖掘過程只需掃描事務數據庫D一次，從而提高了算法的執行效率。