基于哈希表與線性表建立FP-Tree的改進(jìn)算法

阮群生,李豫穎,劉錫鈴 (寧德師范學(xué)院計(jì)算機(jī)與信息工程系,福建寧德352100)

數(shù)據(jù)挖掘是數(shù)據(jù)庫的重要內(nèi)容,其中的關(guān)聯(lián)挖掘是研究最為活躍的部分,發(fā)現(xiàn)頻繁項(xiàng)目集則是關(guān)聯(lián)規(guī)則挖掘應(yīng)用中的關(guān)鍵步驟。近年來,在頻繁項(xiàng)目集的算法研究中先后出現(xiàn)了Apriori,AIS[1],SETM[2]等數(shù)據(jù)挖掘算法。在眾多算法中,以Agrawal等人提出的Apriori算法最為著名,其后的數(shù)據(jù)挖掘算法大多數(shù)建立在Apriori算法基礎(chǔ)之上,如AprioriTid,AprioriHybird[1,2]等。由于Apriori需多次掃描事務(wù)數(shù)據(jù)庫,需要很大的I/O負(fù)載,因此文獻(xiàn) [3]提出了不產(chǎn)生候選集的FP-grow th算法,FP-growth算法大大節(jié)省了時間和空間,對大規(guī)模數(shù)據(jù)采用分而治之的辦法,以避免出現(xiàn)數(shù)據(jù)規(guī)模巨大難以接受的情況。試驗(yàn)表明,FP-growth算法的性能比Apriori算法快了一個數(shù)量級[4]。數(shù)據(jù)關(guān)聯(lián)挖掘算法中發(fā)現(xiàn)頻繁項(xiàng)目集是最耗時的工作,占據(jù)整個計(jì)算量的大部分。目前國內(nèi)外學(xué)者提出很多頻繁項(xiàng)目集挖掘相關(guān)的算法,諸如DEclat[5],Eclat[6]以及DMFI[7]等。2005年,文獻(xiàn) [4]提出一種基于向量的FP-growth改進(jìn)算法,該算法利用向量表示法,使得FP-T ree的構(gòu)造只需掃描數(shù)據(jù)庫一次,減小了開銷,在支持度變化和有新增數(shù)據(jù)時也有一定的改進(jìn)效果,但是對稀疏數(shù)據(jù)處理效果并不理想。為此,筆者從減少I/O負(fù)載和數(shù)據(jù)支持度變化或事務(wù)項(xiàng)動態(tài)變化時如何建立頻繁樹這個角度,提出了基于哈希表與線性表的FP-grow th更新算法,該算法充分利用第一次掃描數(shù)據(jù)庫得來的事務(wù)項(xiàng)信息,在支持度或事務(wù)項(xiàng)動態(tài)變化下避免重復(fù)掃描數(shù)據(jù)庫,同時,在哈希表上實(shí)現(xiàn)對頻繁項(xiàng)排序的操作如同在稀疏矩陣實(shí)現(xiàn)列置換一樣簡單快速,因而能夠提高建立FP-Tree樹的執(zhí)行效率。

1 相關(guān)概念及問題描述

定義1(事務(wù)哈希表) 使用在哈希函數(shù)的基礎(chǔ)上建立的哈希表來存儲、處理數(shù)據(jù)庫每次事務(wù)記錄,把這種哈希表結(jié)構(gòu)命名為事務(wù)哈希表 (T ranHashT ab)。

定義2(線性對象表) 一組有序線性對象元素的集合稱為線性對象表 (ItemList),它是一種接口類對象,并且所有類型的列表都可實(shí)現(xiàn)這個接口,該接口也可定義列表所有的標(biāo)準(zhǔn)操作方法,列表中每個元素都是對象。

傳統(tǒng)算法的建樹過程就是將事務(wù)數(shù)據(jù)庫中的所有事務(wù)對應(yīng)的項(xiàng)集作為FP-Tree結(jié)點(diǎn),壓縮到一棵FP-T ree上,得到一棵頻繁模式樹,具體執(zhí)行過程如下:①掃描一次事務(wù)數(shù)據(jù)庫得到1-頻繁項(xiàng)集L,并根據(jù)頻繁項(xiàng)計(jì)數(shù)從大到小排列L。②初始化一棵空樹,再次掃描事務(wù)數(shù)據(jù)庫遞歸執(zhí)行樹結(jié)點(diǎn)插入函數(shù):Insert_T ree([p|P],N),選取事務(wù)數(shù)據(jù)中的頻繁項(xiàng)目,并按L的順序排列,記為 [p|P],其中,p為第一個元素;P為余下元素的列表。

從傳統(tǒng)算法建樹的過程可得知,需2次掃描事務(wù)數(shù)據(jù)庫,如使用冒泡排序算法對1-頻繁項(xiàng)集排序,則建樹過程的算法時間復(fù)雜度為O(m·n2),其中,m為事務(wù)總數(shù);n為每條事務(wù)項(xiàng)目總數(shù)的平均值。

2 基于事務(wù)哈希表和線性對象表建立FP-Tree算法

2.1 哈希函數(shù)選擇

設(shè)一個數(shù)據(jù)庫中含有m個事務(wù),全部事務(wù)共涉及n個項(xiàng)目,原事務(wù)數(shù)據(jù)表見表1。為了達(dá)到更好的表述效果,借助于二維數(shù)據(jù)存儲結(jié)構(gòu)矩陣工具把事務(wù)數(shù)據(jù)表中的數(shù)據(jù)直觀表示出來,因此數(shù)據(jù)存儲需要構(gòu)造m×n形式的矩陣Matrix,但該矩陣并未在算法中使用到。表1每個數(shù)據(jù)項(xiàng)在每條事務(wù)中出現(xiàn)的位置對應(yīng)下述矩陣中的行或列 (以7行5列的數(shù)據(jù)為例)。

表1 事務(wù)數(shù)據(jù)表

根據(jù)矩陣的行列號特性為哈希表的生成確定哈希函數(shù) f(Kij)=Rij(其中,i為矩陣的行號;j為列號)。以矩陣的行列號i,j為變量的哈希函數(shù)f(Kij)=Rij得出的任何2個項(xiàng)的哈希地址都不會發(fā)生沖突[8]。所以選擇Rij作為哈希函數(shù)是可行的。

2.2 改進(jìn)算法實(shí)現(xiàn)過程

圖1 改進(jìn)算法建立FP-Tree的流程圖

該算法與傳統(tǒng)算法不同之處是建FP-Tree的過程。改進(jìn)算法在建FP-T ree過程中使用了裝載事務(wù)數(shù)據(jù)項(xiàng)的事務(wù)哈希表和線性對象2種數(shù)據(jù)存儲結(jié)構(gòu)。其建立FP-tree的具體步驟如下 (見圖1):①如果不是首次操作,僅當(dāng)支持度發(fā)生變化,則不用創(chuàng)建事務(wù)哈希表和線性對象表,轉(zhuǎn)入步驟③,否則需先創(chuàng)建事務(wù)哈希表和線性對象表;如果是新增數(shù)據(jù),則直接執(zhí)行步驟②。②讀取數(shù)據(jù)庫中的事務(wù)數(shù)據(jù)或新增數(shù)據(jù)部分。把數(shù)據(jù)項(xiàng)填入線性對象表中,并修改線性對象表關(guān)于該項(xiàng)的計(jì)數(shù)值,然后分別把數(shù)據(jù)項(xiàng)、數(shù)據(jù)項(xiàng)在線性對象表中位置序號和本次事務(wù)的序號(對應(yīng)哈希函數(shù)Rij中的j,i值)填入事務(wù)哈希表,循環(huán)步驟②,直至數(shù)據(jù)庫中的末條事務(wù)數(shù)據(jù)。③把線性對象表中各項(xiàng)的計(jì)數(shù)值從大到小排列,按照稀疏矩陣交換列的方法,根據(jù)線性對象表中項(xiàng)大小順序,把事務(wù)哈希表的各項(xiàng)也相應(yīng)地從大到小排列。④依據(jù)事務(wù)哈希表和線性數(shù)據(jù)表創(chuàng)建FP-tree,樹結(jié)點(diǎn)構(gòu)建過程與傳統(tǒng)算法一致。

3 算法試驗(yàn)結(jié)果

試驗(yàn)軟件環(huán)境為操作系統(tǒng)為Windows XP,開發(fā)語言為Visual Studio 2005 C#.NET。硬件環(huán)境如下:①內(nèi)存為DDR2 1024M(Kingston DDR400)。②CPU為Intel(R)Pentium(R)4(2.80GHz)。通過文獻(xiàn) [1]提供的生成程序來得到3萬條類似于上述矩陣中數(shù)據(jù)形式的測試記錄,挖掘支持度閾值以等比的增長方式設(shè)為0.05、0.1、0.2、0.4、0.8、1.6共6檔,以這6檔支持閾值為挖掘參數(shù),分別對更新算法與傳統(tǒng)算法進(jìn)行測試,這6檔支持度下的關(guān)聯(lián)挖掘過程所花時間結(jié)果比較如圖2所示。另外,為了進(jìn)一步驗(yàn)證更新算法在事務(wù)數(shù)據(jù)發(fā)生變化時高效性,隨機(jī)從范例數(shù)據(jù)庫中抽取了10000條記錄作為原始數(shù)據(jù)庫T,1000條記錄作為新增加的數(shù)據(jù)集Tt,分別對更新算法和傳統(tǒng)算法進(jìn)行了測試,測試結(jié)果如圖3所示。由圖2、圖3結(jié)果可知,由于更新算法結(jié)合了事務(wù)哈希表和線性對象表特點(diǎn)和優(yōu)勢,充分利用了已有信息 (即利用內(nèi)存中已經(jīng)處理足夠好的事務(wù)表和1-頻繁項(xiàng)集線性對象表)快速發(fā)現(xiàn)最新事務(wù)數(shù)據(jù)庫中所有的最大頻繁項(xiàng)目集,無須讀取數(shù)據(jù)庫,避免了讀取I/O設(shè)備帶來的開銷,縮短了建樹過程的執(zhí)行時間。

圖2 不同支持度時的2種算法執(zhí)行時間比較

圖3 數(shù)據(jù)更新、不同支持度時的算法執(zhí)行時間比較

4 改進(jìn)算法優(yōu)勢分析

改進(jìn)算法的優(yōu)勢在于充分利用事務(wù)哈希表和線性對象表特點(diǎn),在建立FP-Tree前,把事務(wù)數(shù)據(jù)庫中的數(shù)據(jù)項(xiàng)等信息掃描到2個表的結(jié)構(gòu)空間中,算法后續(xù)操作可在這2個表上進(jìn)行,避免傳統(tǒng)算法需2次訪問事務(wù)數(shù)據(jù)的缺點(diǎn),減少了讀取I/O設(shè)備的開銷,而且基于哈希表和線性數(shù)據(jù)的存儲和查找消耗的時間大大降低,幾乎可以看成是常數(shù)時間,進(jìn)一步減少了建立FP-Tree的時間,因此,在支持度閾值或新增部分事務(wù)數(shù)據(jù)變化時的關(guān)聯(lián)規(guī)則重復(fù)挖掘中,改進(jìn)算法優(yōu)勢更加突出。

由于FP-grow th改進(jìn)算法對數(shù)據(jù)庫的第2次掃描改成對事務(wù)哈希表的掃描,這可能對小型數(shù)據(jù)庫優(yōu)勢不明顯,但對于大型數(shù)據(jù)庫優(yōu)勢則很明顯。那么,計(jì)算機(jī)內(nèi)存空間能否承受全部數(shù)據(jù)的裝入呢?為了更好說明這個問題,現(xiàn)假設(shè)1個大型數(shù)據(jù)庫有1000個項(xiàng)目,共有100萬次交易記錄,每次交易涉及到的項(xiàng)目集平均數(shù)為20個,則內(nèi)存中存儲的項(xiàng)目總數(shù)為2000萬個,每個項(xiàng)目占4個字節(jié),加上其他項(xiàng)目集表頭所占的空間,則全部數(shù)據(jù)共占空間不超過300MB,如果交易記錄上億條時,還可采用大型數(shù)據(jù)庫的一些優(yōu)化方法進(jìn)行處理,如把數(shù)據(jù)進(jìn)行豎直分割處理、水平分割處理等。另外,改進(jìn)算法時間復(fù)雜度雖與傳統(tǒng)算法一樣,但是采用從大到小排序的線性對象和事務(wù)哈希表能夠避免不符合支持度閾值要求的項(xiàng)被訪問,大大縮小了n的取值范圍,從而減少了算法的執(zhí)行時間。當(dāng)然,更新算法也有自身的缺點(diǎn),即需要開辟存儲事務(wù)數(shù)據(jù)的空間,但由于如今用戶使用的內(nèi)存存儲容量越來越大,這種用空間換時間的策略還是值得的,同時,事務(wù)哈希表建構(gòu)也增加了算法的設(shè)計(jì)復(fù)雜性,但哈希表的建構(gòu)比較簡單,程序?qū)崿F(xiàn)簡單,因此,可以很好地解決算法的設(shè)計(jì)復(fù)雜性的問題。

5 結(jié) 語

提出了一種基于事務(wù)哈希表和線性對象表快速建立FP-Tree的改進(jìn)算法,提高了關(guān)聯(lián)規(guī)則的整體效率,在實(shí)際應(yīng)用中比原有FP-growth算法在建樹方面更有效,在數(shù)據(jù)庫中數(shù)據(jù)沒有發(fā)生更新時,它只需掃描數(shù)據(jù)庫一次,尤其是重復(fù)的關(guān)聯(lián)挖掘過程中,如果僅僅是支持度參數(shù)改變或新增部分事務(wù)數(shù)據(jù),則可不用掃描數(shù)據(jù)庫或只需掃描數(shù)據(jù)庫中的新增部分?jǐn)?shù)據(jù)。但是這種算法也有著自身的不足,即預(yù)存儲所有經(jīng)簡化處理后的事務(wù)數(shù)據(jù)項(xiàng)時增大了存儲空間,同時改進(jìn)算法沒有克服當(dāng)挖掘頻繁項(xiàng)時對FP-Tree遍歷的缺陷。因此,改進(jìn)在頻繁FP-Tree樹中挖掘頻繁項(xiàng)的算法部分,將是今后需要研究的重要內(nèi)容。

[1]Ag rawal R,Srikant R.Fast algo rithm for mining association rules[J].Proceeding s of the 20th International Conference on VLDB.Santiago,1994,12(2):487～499.

[2]Houtsma M,Swami A.Set-Oriented mining fo r association rules in relational databases[J].Proceedings of the International Conference on Data Engineering.Los Alamitos:IEEE Computer Society Press,1995,38(4):25～33.

[3]Han J K.數(shù)據(jù)挖掘:概念與技術(shù) [M].范明,孟小峰譯.北京:機(jī)械工業(yè)出版社,2001.

[4]鄧豐義,劉震宇.基于模式矩陣的FP-growth改進(jìn)算法 [J].廈門大學(xué)學(xué)報(bào) (自科版),2005,44(5):629～634.

[5]熊忠陽,耿曉斐,張玉芳.一種新頻繁項(xiàng)集挖掘算法[J].計(jì)算機(jī)學(xué)報(bào),2009,36(4A):42～44.

[6]Zaki M J.Scanlable Alg orithms for Association Mining[J].Knowledge and Data Engineering,2000,19(3):52～55.

[7]Lu S F,Lu Z D.Fast mining maximum frequent itemsets[J].Journal of Software,2001,12(2):293～297.

[8]劉錫鈴.關(guān)聯(lián)規(guī)則挖掘算法及其在購物籃分析的應(yīng)用研究算法的設(shè)計(jì)復(fù)雜性 [D].蘇州:蘇州大學(xué),2009.