胡 軍,潘皓安
(重慶郵電大學(xué) 計(jì)算智能重慶市重點(diǎn)實(shí)驗(yàn)室,重慶 400065)
關(guān)聯(lián)規(guī)則挖掘是知識發(fā)現(xiàn)中的重要問題之一。自從1993年Agrawal教授[1]提出關(guān)聯(lián)規(guī)則的概念開始,關(guān)聯(lián)規(guī)則的研究一直未中斷過。挖掘關(guān)聯(lián)規(guī)則的關(guān)鍵是發(fā)現(xiàn)頻繁項(xiàng)集。1994年Agrawal等提出了Apriori算法[2],利用連接和剪枝對候選項(xiàng)集進(jìn)行處理,從而得到頻繁項(xiàng)集;2000年Han等基于樹型提出了頻繁模式增長(frequent pattern growth algorithm,F(xiàn)P-Growth)算法[3],該算法在挖掘過程中不產(chǎn)生候選項(xiàng),因此,較之前的算法,該算法時間優(yōu)勢明顯,但因要存儲所有頻繁模式,內(nèi)存占用較高。這些方法都以靜態(tài)數(shù)據(jù)為研究對象,然而在實(shí)際問題中廣泛存在著動態(tài)數(shù)據(jù)。為從動態(tài)數(shù)據(jù)中挖掘關(guān)聯(lián)規(guī)則,人們提出了關(guān)聯(lián)規(guī)則的增量更新挖掘算法。Cheung等在ICDE`96上提出了快速更新算法(fast update algorithm, FUP)算法[4]來解決在數(shù)據(jù)集增加情況下的頻繁項(xiàng)集挖掘,其后又在1997年提出了FUP2算法[5]解決數(shù)據(jù)集減少時的頻繁項(xiàng)集挖掘;馮玉才等于1998年提出了增量更新算法(incremental updating algorithm,IUA)算法[6]解決了支持度變化情況下頻繁項(xiàng)集的挖掘;Koh等在2003年基于FP-tree算法提出了基于FP樹的增量挖掘算法(adjusting FP-Tree for incremental mining algorithm,AFPIM)算法[7]解決數(shù)據(jù)集變化情況下的挖掘。在眾多面向增量關(guān)聯(lián)規(guī)則的算法中,F(xiàn)P-Growth改進(jìn)的算法性能要比Apriori改進(jìn)的算法好,但是操作遠(yuǎn)比后者繁瑣[8-9]。為了方便事務(wù)的增加刪除操作并保持挖掘效率,W.Cheung等[10]于2003年結(jié)合FP樹和前綴樹提出了壓縮排列的事務(wù)序列樹(compressed and arranged transaction sequences tree,CATS-tree),首次實(shí)現(xiàn)了“一次建立,多次挖掘”的目的;Leung在2005年在CATS樹基礎(chǔ)上改進(jìn)了樹節(jié)點(diǎn)的排列方式提出了Can樹[11],Can樹要求事務(wù)中的各項(xiàng)先按照某種順序排序,然后再開始建樹和挖掘等操作,以此再次提高了挖掘效率。
Can樹(Canonical order tree)利用樹型存儲了所有數(shù)據(jù),方便了數(shù)據(jù)的增刪以及支持度改變后的再次挖掘。在挖掘時采用了和FP-Growth同樣的方法。因?yàn)镃an樹比FP樹更加龐大,這導(dǎo)致在某些情況下Can樹挖掘頻繁項(xiàng)集所需時間有可能大于FP-Growth算法,例如Sadat等[12]在2015年對Can樹和FP-Growth算法進(jìn)行了比較,發(fā)現(xiàn)在高閾值的最小支持度時,Can樹的性能優(yōu)于FP-Growth,但在低閾值的最小支持度時,性能不如FP-Growth算法。雖然Can樹已提出了十多年,但改進(jìn)方法并不多。鄒力鹍等[13]在2008年采用了子父節(jié)點(diǎn)指針代替原先的父子節(jié)點(diǎn)指針,以此快速生成條件模式樹,提高算法效率。陳剛等[14]在2014年提出一種基于CAN樹的快速構(gòu)造算法(a fast construction algorithm based on Can-tree,F(xiàn)CCAN),該算法同樣使用子父節(jié)點(diǎn)指針代替原先的父子節(jié)點(diǎn)指針,并增加基于hash表的輔助存儲結(jié)構(gòu),用于減少項(xiàng)目的查找時間。Roul等[15]在2014年提出了生成和歸并樹(generate and merge tree,GM-tree),他們保留了Can樹生成的方式,在增量時對數(shù)據(jù)進(jìn)行分塊,每一塊生成一棵樹,最后再進(jìn)行樹合并。但是,Can樹由于存儲了所有數(shù)據(jù),導(dǎo)致規(guī)模過大,因此挖掘效率有待提升。為了優(yōu)化Can樹規(guī)模,提高挖掘效率并且改善Can樹的不穩(wěn)定性,本文中我們提出了一種改進(jìn)的基于Can樹的關(guān)聯(lián)規(guī)則增量更新算法,并通過實(shí)驗(yàn)對該算法的有效性進(jìn)行了驗(yàn)證。
Can樹是Leung于2005年基于CATS樹改進(jìn)后提出的解決關(guān)聯(lián)規(guī)則增量挖掘的算法[11]。Can樹采用了前綴樹,并讓盡量多的相同事務(wù)項(xiàng)合并在一起,以此來存儲所有數(shù)據(jù)。算法要求事務(wù)中的每個項(xiàng)按照某種特定順序進(jìn)行排序后再構(gòu)建Can樹,排序一般采用字典序、字母序等,這樣在挖掘增量關(guān)聯(lián)規(guī)則的時候,新來的數(shù)據(jù)可以直接鏈入到原來的Can樹中,不用重新構(gòu)建新樹以及再次掃面原來的數(shù)據(jù),從而提高了關(guān)聯(lián)規(guī)則增量更新的效率。
Can樹挖掘頻繁項(xiàng)集總共分為2步:先構(gòu)建Can樹,再從Can樹中挖掘頻繁項(xiàng)集。Can樹的構(gòu)建很簡單,先將事務(wù)中的項(xiàng)按照字典序或字母序排序(這2種排序方法是Can樹默認(rèn)的),然后將排序后的事務(wù)依次插入到Can樹中即可。因?yàn)?,事?wù)項(xiàng)已經(jīng)按照統(tǒng)一規(guī)則排序,在插入時無須對樹枝進(jìn)行多余的剪枝或轉(zhuǎn)換等操作。從Can樹中挖掘頻繁項(xiàng)集的過程如下。
1)從Can樹節(jié)點(diǎn)自下而上挖掘。首先找到最下面的項(xiàng),構(gòu)建每個項(xiàng)的條件模式基;順著Can樹,找出所有包含該項(xiàng)的前綴路徑,這些前綴路徑就是該項(xiàng)的條件模式基(conditional pattern base, CPB);所有這些CPB的頻繁度(計(jì)數(shù))為該路徑上項(xiàng)的頻繁度(計(jì)數(shù));
2)累加每個CPB上的項(xiàng)的頻繁度(計(jì)數(shù)),過濾低于閾值(最小支持度)的項(xiàng),構(gòu)建條件FP-tree;
3)遞歸挖掘每個條件FP-tree,累加后綴頻繁項(xiàng)集,直到條件FP-tree為空或者條件FP-tree只有一條路徑(只有一條路徑情況下,所有路徑上項(xiàng)的組合都是頻繁項(xiàng)集)。
Can樹相對于其他增量挖掘算法的優(yōu)勢是可以存儲所有數(shù)據(jù),在挖掘動態(tài)數(shù)據(jù)時,省去了再次讀取或掃描原數(shù)據(jù)的步驟,以此節(jié)約了時間,但缺點(diǎn)也較明顯:因要存儲所有數(shù)據(jù)而使得Can樹需要占用大量內(nèi)存存儲整棵Can樹,所以Can樹的規(guī)模大小直接決定了占用的內(nèi)存大小。此外,在增量挖掘時,不論是增刪數(shù)據(jù)還是挖掘頻繁項(xiàng)集,都需要遍歷Can樹,所以Can樹的規(guī)模大小還間接的決定了Can樹算法的時間效率。
根據(jù)前述,Can樹的規(guī)模對算法的效率有直接影響,而當(dāng)前預(yù)排列事務(wù)數(shù)據(jù)時所使用的順序?qū)⒂锌赡苁沟肅an樹的規(guī)模太大,從而使得算法效率較低。例如,數(shù)據(jù)集如表1所示。
表1 數(shù)據(jù)集
表1數(shù)據(jù)集已按照字母序排序,在此基礎(chǔ)上建立Can樹,則會得到如圖1a所示的Can樹。
圖1 數(shù)據(jù)集建立Can樹Fig.1 Built Can-tree
由圖1a可看出,該樹中有很多節(jié)點(diǎn)是表示相同數(shù)據(jù)項(xiàng)的,例如節(jié)點(diǎn)a,節(jié)點(diǎn)b,節(jié)點(diǎn)c,節(jié)點(diǎn)d,節(jié)點(diǎn)e的第一個子節(jié)點(diǎn)都是項(xiàng)x,由于未能合并在一起,在挖掘樹時,需要遍歷整棵樹,從而降低了挖掘效率。如果能夠盡量讓相同的數(shù)據(jù)項(xiàng)使用同一個樹節(jié)點(diǎn),則可以有效減小樹規(guī)模,從而提高挖掘效率。因此,本文通過改變以往的排序方法,提出了一種基于數(shù)據(jù)量排序的Can樹。具體而言就是將次數(shù)最多的數(shù)據(jù)項(xiàng)放在最前面,將次數(shù)最少的數(shù)據(jù)項(xiàng)放在最后面,這樣可以讓盡量多的相同數(shù)據(jù)項(xiàng)使用同一個節(jié)點(diǎn),以此來減小Can樹規(guī)模。以表1所示的數(shù)據(jù)集為例,該數(shù)據(jù)集在掃描一次數(shù)據(jù)后可得到:{a:1,b:1,c:1,d:1,e:1,x:5,y:5,z:5}。將該結(jié)果按遞減排序得到一個順序:{x,y,z,a,b,c,d,e},再將原數(shù)據(jù)項(xiàng)依照上面的順序排序,如表2所示。
表2 數(shù)據(jù)集按照數(shù)據(jù)量排序
這樣排序后,再進(jìn)行Can樹的建立,可得圖1b所示的Can樹。
比較圖1a和圖1b,可以計(jì)算出使用字母序排序建立的Can樹節(jié)點(diǎn)數(shù)有21個(包含root節(jié)點(diǎn)),而使用數(shù)據(jù)量排序建立的Can樹節(jié)點(diǎn)樹只有9個(包含root節(jié)點(diǎn))??梢姡捎谙嗤臄?shù)據(jù)項(xiàng)都使用了同一個樹節(jié)點(diǎn),本文的方法較原有的方法所得到的樹規(guī)模小得多。
在首次構(gòu)建Can樹時,需得到一個數(shù)據(jù)量排序順序(即原數(shù)據(jù)量順序),在增量更新時,由于數(shù)據(jù)量在變化,數(shù)據(jù)量排序順序也有可能發(fā)生改變,所以在增量更新挖掘時,排序順序仍采用原數(shù)據(jù)量順序進(jìn)行排序,同時數(shù)據(jù)量排序結(jié)果仍進(jìn)行更新,得到新數(shù)據(jù)量順序,以方便挖掘時在比較該項(xiàng)的總計(jì)數(shù)是否低于閾值(即該項(xiàng)是否為頻繁項(xiàng))時能夠直接判斷使用,不用再次計(jì)算。并在建樹同時,參考陳剛等[13]的改進(jìn)方法,增加hash表記錄每個項(xiàng)在樹中的位置,因?yàn)槌醮谓浜驮隽拷渎杂袇^(qū)別,所以實(shí)現(xiàn)部分稍有不同,初次建樹偽碼如下。
輸入:原數(shù)據(jù)集DB;
輸出:Can-tree,原數(shù)據(jù)量順序data_order
1) data_order=scan(DB);//掃描數(shù)據(jù)庫,獲得原數(shù)據(jù)量順序
2) for each trans in DB
3) sort(trans,data_data)//將每條事務(wù)根據(jù)原數(shù)據(jù)量順序排序
4) insert(trans,Can-tree)//將排序后的事務(wù)插入樹T中
5) end for
增量建樹偽碼為
輸入:增量數(shù)據(jù)集db,已生成的Can-tree,原數(shù)據(jù)量順序data_order;
輸出:Can-tree,新數(shù)據(jù)量順序new_data_order,
1) new_data_order=scan(db,data_order);//掃描增量數(shù)據(jù)庫,并結(jié)合原數(shù)據(jù)量順序,得到新數(shù)據(jù)量順序
2) for each trans in DB
3) sort(trans,data_data)//將每條事務(wù)根據(jù)原數(shù)據(jù)量順序排序
4) insert(trans,Can-tree)//將排序后的事務(wù)插入樹T中
5) end for
Can樹挖掘的流程如圖2a所示。因?yàn)镃an樹保存了所有數(shù)據(jù),該方法遍歷所有項(xiàng)時就會遍歷非頻繁項(xiàng),這樣會浪費(fèi)部分時間在非頻繁項(xiàng)上。所以本文結(jié)合之前得到的數(shù)據(jù)量排序順序?qū)ν诰蜻^程進(jìn)行了改進(jìn)。在挖掘時,根據(jù)數(shù)據(jù)量排序順序,將數(shù)據(jù)量低于閾值(最小支持度)的項(xiàng)舍去,只需要構(gòu)建數(shù)據(jù)量高于或等于閾值(最小支持度)的項(xiàng)的CPB即可,后續(xù)步驟則繼續(xù)原方法,改進(jìn)后的挖掘流程如圖2b所示。
圖2 挖掘Can樹流程圖Fig.2 Flow chart of mining Can-tree
這樣可以減少遍歷一些非頻繁項(xiàng)所花的時間。改進(jìn)后的挖掘偽碼如下。
輸入:Can-tree,最小支持度min_sup;
輸出:頻繁項(xiàng)集fre_items;
1) for item in new_data_order
2) if item.num>=min_sup
3) CPBs=add all item CPB
4) delete_unfrequentitem(CPBs)
5) CP-tree=constrct(CPBs)
6) fre_items=fre_items∩mining(CP-tree,min_sup)
7) end if
8) end for
實(shí)驗(yàn)主要從2方面進(jìn)行了對比,實(shí)驗(yàn)1利用不同量的數(shù)據(jù)進(jìn)行建樹,比較了2種不同排序方法建立的Can樹的規(guī)模大?。粚?shí)驗(yàn)2通過增量挖掘比較了基于2種不同排序方法的Can樹算法、FP-Growth算法、以及陳剛等提出的FCCAN算法的時間效率。
實(shí)驗(yàn)中使用了3個公開的數(shù)據(jù)集:①mushroom數(shù)據(jù):共有事務(wù)8 124條,項(xiàng)目26個;②Groceries數(shù)據(jù):共有事務(wù)9 835條,商品169件;③pumsb數(shù)據(jù):共有事務(wù)49 046條,項(xiàng)目711件。
實(shí)驗(yàn)的運(yùn)行環(huán)境是Intel(R)CoreTMi3-4170CPU@ 3.70 GHz,8 GByte 內(nèi)存,操作系統(tǒng)為Windows 7 旗艦版,所有算法使用EclipseSDK(Version: 4.2.2&Java1.7.0)編程實(shí)現(xiàn)。
實(shí)驗(yàn)1表3為改進(jìn)前后的2種Can樹在3個數(shù)據(jù)集上所生成的節(jié)點(diǎn)數(shù)量的對比。結(jié)果表明,由數(shù)據(jù)量順序排序生成的Can樹規(guī)模都小于由字典序排序生成的Can樹。具體而言,Can樹的節(jié)點(diǎn)數(shù)平均減少33.7%,最多減少56.9%??梢娛褂脭?shù)據(jù)量排序可以有效減小Can樹的規(guī)模。
實(shí)驗(yàn)2對于mushroom數(shù)據(jù)集,基礎(chǔ)數(shù)據(jù)量定為2 000,每次使用不同增量進(jìn)行試驗(yàn),試驗(yàn)結(jié)果如圖3所示。從圖3中可以看出,在增量挖掘時(圖3中后4組),F(xiàn)P-Growth所花時間高于Can樹挖掘時間,而在所有基于Can樹的算法中,本文的算法在時間效率上又優(yōu)于基于字典序的Can樹算法以及FCCAN算法。
對于Groceries數(shù)據(jù)集,基礎(chǔ)數(shù)據(jù)量定為1 000,每次使用不同增量進(jìn)行試驗(yàn),實(shí)驗(yàn)結(jié)果如圖4所示,從圖4中可看出,基于字典序的Can樹算法和FCCAN算法在事務(wù)量增加較多后(后3組),其時間效率反而不如FP-Growth算法,而本文的算法依然優(yōu)于所有其他算法。
表3 2種Can樹在3個數(shù)據(jù)上生成的節(jié)點(diǎn)數(shù)量對比
圖3 mushroom挖掘時間對照Fig.3 Time comparison onmushroom
圖4 Groceries挖掘時間對照Fig.4 Time comparison onGroceries
對于pumsb數(shù)據(jù)集,基礎(chǔ)數(shù)據(jù)量定為5 000,每次使用不同增量進(jìn)行試驗(yàn),試驗(yàn)結(jié)果如圖5所示。很明顯,所有Can樹算法均優(yōu)于FP-Growth算法,并且本文的算法最優(yōu)。
從以上3個數(shù)據(jù)集的對比可看出,基于字典序的Can樹算法和FCCAN算法存在不穩(wěn)定性[11],而本文提出的基于數(shù)據(jù)量排序的Can樹算法在處理增量挖掘時具有很好的穩(wěn)定性。
綜上,本文提出的基于數(shù)據(jù)量排序的Can樹算法在空間效率和時間效率上好于現(xiàn)有的Can樹算法,同時具有了較好的穩(wěn)定性。
圖5 pumsb挖掘時間對照Fig.5 Time comparison onpumsb
本文針對動態(tài)數(shù)據(jù)中的關(guān)聯(lián)規(guī)則挖掘,使用數(shù)據(jù)量順序替代字典序和字母序?qū)?shù)據(jù)進(jìn)行預(yù)處理,提出了一種基于數(shù)據(jù)量排序的Can樹,并基于新的Can樹對原有Can樹的建樹和挖掘方法進(jìn)行優(yōu)化,實(shí)驗(yàn)結(jié)果表明,本文提出的方法能夠有效降低Can樹的規(guī)模,提高增量關(guān)聯(lián)規(guī)則挖掘的效率。這種方法還可運(yùn)用在分布式、多源數(shù)據(jù)等多種環(huán)境中,這將是本文下一步的研究工作。