基于FP-Tree的挖掘最大頻繁項(xiàng)目集的新算法

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

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

基于FP-Tree的挖掘最大頻繁項(xiàng)目集的新算法

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

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

引言

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

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

1 FP-GDMA算法

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

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

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

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

1.2 FP-GDMA算法的思想

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

1.3 FP-GDMA算法的過(guò)程描述

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

輸出：最大頻繁項(xiàng)目集MFS

方法：

一次自頂向下的搜索FP-Tree得到一個(gè)最大長(zhǎng)度的最大頻繁項(xiàng)集候選P；//P必是頻繁項(xiàng)集的前綴或是一個(gè)頻繁項(xiàng)集

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

if MaxFC[i]≥s 并且MaxF[i]不是MFS中某項(xiàng)集的子集

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

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

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

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

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

2 算法比較

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

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

3 結(jié)語(yǔ)

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

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

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

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

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

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

[10]路松峰,盧正鼎.快速開(kāi)采最大頻繁項(xiàng)目集.軟件學(xué)報(bào),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

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

最大頻繁項(xiàng)目集;數(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