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

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

1 相關概念及問題描述

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

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

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

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

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

2.1 哈希函數選擇

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

表1 事務數據表

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

2.2 改進算法實現過程

圖1 改進算法建立FP-Tree的流程圖

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

3 算法試驗結果

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

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

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

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

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

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

5 結 語

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

[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.數據挖掘:概念與技術 [M].范明,孟小峰譯.北京:機械工業(yè)出版社,2001.

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

[5]熊忠陽,耿曉斐,張玉芳.一種新頻繁項集挖掘算法[J].計算機學報,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ī)則挖掘算法及其在購物籃分析的應用研究算法的設計復雜性 [D].蘇州:蘇州大學,2009.