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

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

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

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

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

引言

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

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

1 FP-GDMA算法

1.1 FP-Tree的構(gòu)建

按以下步驟構(gòu)建FP-Tree：

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

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

1.2 FP-GDMA算法的思想

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

1.3 FP-GDMA算法的過程描述

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

輸出：最大頻繁項目集MFS

方法：

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

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

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

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

事務(wù)數(shù)據(jù)庫D

圖1 事務(wù)數(shù)據(jù)庫D的FP-Tree

首先構(gòu)建事務(wù)數(shù)據(jù)庫D的FP-Tree如圖1,s=3。

根據(jù)FP-GDMA算法對例1中給出的事務(wù)數(shù)據(jù)庫D，求最大頻繁項目集的過程如下：自頂向下搜索FPTree得到P={f,c,a,m,p}，進一步求得Q=,然后進入do-while循環(huán)。調(diào)用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 算法比較

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

圖2 DMFIA和FP-GDMA的挖掘?qū)Ρ?/p>

3 結(jié)語

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

[1]朱玉全,孫志輝,季小俊.基于頻繁模式數(shù)的關(guān)聯(lián)規(guī)則增量式更新算法.計算機學報，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]惠亮,錢雪忠.關(guān)聯(lián)規(guī)則中FP-Tree的最大頻繁模式非檢驗挖掘算法.計算機應(yīng)用,2010,30(7):1922～1925

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

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

[8]梅俊,鄭剛.一種基于FP-Tree的最大頻繁項目集挖掘算法.研究與發(fā)現(xiàn),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

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

最大頻繁項目集;數(shù)據(jù)挖掘；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