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

楊青俠 何明祥 邱冬冬 聶寶軍

山東科技大學信息科學與工程學院，山東 青島 266000

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

楊青俠 何明祥 邱冬冬 聶寶軍

山東科技大學信息科學與工程學院，山東 青島 266000

引言

關聯規則是由Agrawal等人首先提出的一個重要的數據挖掘研究課題[1]。而挖掘頻繁項目集是關聯規則挖掘的關鍵技術。在此基礎上Agrawal等人于1993年首次提出為布爾關聯規則挖掘頻繁項集的Apriori算法。雖然，Apriori算法是數據挖掘中最重要的算法之一。但是它也存在著不足。Apriori算法為了挖掘頻繁項目集，必須產生所有的候選項目集，候選項目集的數量很龐大。并且為了得到候選項目集的支持度，算法必須重復的掃描數據庫來確定候選項目集的支持度。計算候選項目集的支持度是最耗時的工作。所以減小成本的最好手段就是降低候選項目集的數目和減少數據庫的掃描次數。FP-Tree[2]存儲結構就是為了解決這兩個問題而被提出的。FP-Tree的構造只掃描兩次數據庫。第一次數據庫掃描和Apriori相同，它導出頻繁項（1-項集）的集合和支持度計數（頻率）。第二次數據庫掃描用于構建FP-Tree和保存重要信息。

最大頻繁項目集中包含了所有的頻繁項目集信息。所以對頻繁項目集的挖掘就轉化為對最大頻繁項目集挖掘的問題。目前挖掘最大頻繁項目集的算法有Max-Miner[3]，Pincer-Search[4]，DMFI[5]及DMFIA[6]等算法。其中DMFIA基于FP-Tree存儲結構，雖然克服了先前的挖掘算法的不足，但仍然生產了過多的候選項目集。本文在研究大量算法的基礎上，提出了一種基于FP-Tree的新的挖掘算法FP-GDMA。該算法采用自頂向下和自底向上的雙向搜索策略有效減少了候選項目集的數目，提高了挖掘最大頻繁項目集的效率。FP-GDMA算法通過能快速的剪枝掉不在最大候選項目集中的項目集，減少候選項目集的數目。并通過實驗表明FP-GDMA算法優于DMFIA算法。

1 FP-GDMA算法

1.1 FP-Tree的構建

按以下步驟構建FP-Tree：

1）第一次掃描數據庫D,D為要挖掘的事務數據庫。導出頻繁項的集合和支持度計數。創建一個頂頭表L存放頻繁項的信息。L的每一個表項有3個域組成：項目名itemname，項目名的支持度計數item-count，項目鏈頭item-head，item-head為指向FP-Tree中與之具有相同item-name的首節點的指針。將導出的頻繁項的集合按支持度計數的降序排列，一次存放到L的各表項中。

2)第二次掃描數據庫D,創建FP-Tree。其中，FP-Tree中的每個節點有4個域組成：節點項目名node-name，節點的計數node-count，父節點指針node-parent，節點鏈node-link。其中，node-link為指向FP-Tree中擁有相同node-name值的下一個節點。首先，創建FP-Tree的根節點，用”root”標記。每個事務中的項按遞減支持度計數排序。對D中每個事務Trans，執行：選擇Trans中的頻繁項，并按L中的次序排列。調用insert_tree([p|P],t)。該過程執行情況如下：如果t有一個子女n.node-name=p.node-name，則n.nodecount++，否則創建一個新節點n，則n.node-name=p.node-name,n.node-count等于1,連接到它的父節點T，且通過節點鏈結構將其鏈接到具有相同node-name的節點。只要P非空，就遞歸調用insert_ tree(P,n)。

1.2 FP-GDMA算法的思想

FP-GDMA算法通過自頂向下和自底向上相結合的搜索策略來快速的挖掘最大頻繁項目集。該算法思想：1）自頂向下搜索FP-Tree的每一個分支，如果分支中的節點的n.node-count s,則繼續搜索分支中的下一個節點，直到節點的n.node-count s或節點n為葉子節點。將該分支中的所有滿足n.node-count s的節點項集作為最長的最大候選項集。2）如果n.node-parent還存在其他分支則重復1中的步驟。如果有更長的最大候選項集則更新。直到FP-Tree的每個分支搜索完畢,算法將得到一個最長的最大候選項集P和一個不在P中出現的項的集合Q。3）如果Q非空,對Q中的每一項利用項頭表中的信息,得到以該項為后綴的路徑。并利用交集的思想，將路徑兩兩相交求交集。如果交集的count大于s，則為頻繁項集。對Q中的項重復步驟3)最終可求得最大頻繁項目集。

1.3 FP-GDMA算法的過程描述

輸入：事務數據庫D生成的FP-Tree，最小支持度計數閾值s，

輸出：最大頻繁項目集MFS

方法：

一次自頂向下的搜索FP-Tree得到一個最大長度的最大頻繁項集候選P；//P必是頻繁項集的前綴或是一個頻繁項集

設Path數組中保存了以e為后綴的所有路徑信息,PathC數組保存了對應于Path數組中的各路徑的支持度計數。MaxF數組保存Path數組中的交集信息,MaxFC保存MaxF中各交集的支持度計數。

if MaxFC[i]≥s 并且MaxF[i]不是MFS中某項集的子集

例1 事務數據庫D如下，minsup=0.5,求D的最大頻繁項目集

事務數據庫D

圖1 事務數據庫D的FP-Tree

首先構建事務數據庫D的FP-Tree如圖1,s=3。

根據FP-GDMA算法對例1中給出的事務數據庫D，求最大頻繁項目集的過程如下：自頂向下搜索FPTree得到P={f,c,a,m,p}，進一步求得Q={b},然后進入do-while循環。調用getMFS（FP-Tree，b）自底向上搜索FP-Tree，最大頻繁項目集MFS={{f,b},{c,b}}。算法的最后判斷P不是MFS的子集，則將P并入MFS，最終得到MFS={{f,c,a,m,p},{c,b},{f,b}}。

2 算法比較

實驗環境為Windows XP Professional操作系統，CPU 1,59GHz和2GB的內存，用VC++6.0實現DMFIA和FP-GDMA算法。測試數據庫采用mushroom。該數據庫含有8124條記錄。記錄了蘑菇的23種屬性。圖2顯示了DMFIA和FP-GDMA算法在不同最小支持度（分7檔:25%，20%,15%，10%,5%,2%,1%）下的時間比較。由于FPGDMA產生的最大候選項目集的數目小于DFMIA，且執行時間比DMFIA短。故FPGDMA算法比DMFIA優越。

圖2 DMFIA和FP-GDMA的挖掘對比

3 結語

本文以FP-Tree的存儲結構為基礎，提出了挖掘最大頻繁項目集的FP-GDMA算法。FP-GDMA利用自頂向下和自底向上的雙向搜索策略快速的挖掘最大頻繁項目集。FP-GDMA算法采用了交集的方法克服了DMFIA算法產生大量最大候選項目集的缺點，提高了挖掘最大頻繁項目集的效率。

[1]朱玉全,孫志輝,季小俊.基于頻繁模式數的關聯規則增量式更新算法.計算機學報，2003,26(1):91～96

[2]Han JW,Pei J,Yin YW.Mining frequent patterns without candidate generation.In:Weidong C, Jeffrey F,eds.Proc.of the ACM SIGMOD Conf.on Management of Data.Dallas:ACM Press,2000. 1～12.

[3]BAYARDO R.Efficiently Mining Long Patterns from Databases[A].HAAS LM,ed.Proceedings of the ACM SIGMOD International Conference on Mangement of Data[C].New York:ACM Press,1998:85～93

[4]L IN D I,KEDEM ZM.Princer-Search:A New Algorithm for Discovering the Maximum Frequent Set[A].SCHEK HJ,ed.Proceedings of the 6th European Conference on Extending Database Technology[C].Heide lberg:SpringerVerlag,1998:105～119

[5]惠亮,錢雪忠.關聯規則中FP-Tree的最大頻繁模式非檢驗挖掘算法.計算機應用,2010,30(7):1922～1925

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

[7]吉根林,楊明,宋余慶,孫志輝.最大頻繁項目集的快速更新.計算機學報,2005,28(1):128～135

[8]梅俊,鄭剛.一種基于FP-Tree的最大頻繁項目集挖掘算法.研究與發現,2009,315(9):33～36

[9]鄭海明.基于FP-Tree最大頻繁項集的FP-MFI算法研究，2008,293(10):37～39

[10]路松峰,盧正鼎.快速開采最大頻繁項目集.軟件學報,2001,12(2):293～297

A New Algorithm for Mining Maximum Frequent Itemsets Based on FP-Tree

Yang Qingxia He Mingxiang Qiu Dongdong Nie Baojun
College of Information Science and Engineering, Shandong University of Science and Technology, Qingdao, China

挖掘最大頻繁項目集是數據挖掘領域的一個重要的研究內容。Apriori算法作為一種挖掘頻繁項目集的基本算法，其缺點是產生大量的候選項目集，算法的代價很大。本文在基于FP-Tree的基礎上提出了挖掘最大頻繁項目集的新算法FP-GDMA。該算法采用自頂向下和自底向上相結合的搜索策略有效減少了生產候選項目集的數目，有效提高了挖掘最大頻繁項目集的效率。并通過實驗比較FPGDMA與DMFIA算法。

最大頻繁項目集;數據挖掘；FP-Tree;FPGDMA;DMFIA

Mining maximum frequent itemsets is an important research in data mining field.Apriori,as the basic algorithm for mining frequent itemsets,has drawbacks such as generating many candidate maximum frequent itemsets and tremendous cost .This paper proposes a new algorithm for mining maximum frequent itemsets named FP-GDMA based on FP-Tree. It uses the search strategy with combination of top-down and bottom-up,which effectively reduces the number of candidate frequent itemsets and effectively improves the efficiency for mining maximum frequent itemsets. The paper also compares FP-GDFM and DMFIA by experiment.

Maximum Frequent Itemsets; Data Mining; FPTree;FP-GDMA;DMFIA

10.3969/j.issn.1001-8972.2012.14.047

DOI：10.3969/j.issn.1001-8972.2012.14.089