胡 軍，潘皓安

(重慶郵電大學 計算智能重慶市重點實驗室，重慶 400065)

0 引 言

關聯(lián)規(guī)則挖掘是知識發(fā)現(xiàn)中的重要問題之一。自從1993年Agrawal教授[1]提出關聯(lián)規(guī)則的概念開始，關聯(lián)規(guī)則的研究一直未中斷過。挖掘關聯(lián)規(guī)則的關鍵是發(fā)現(xiàn)頻繁項集。1994年Agrawal等提出了Apriori算法[2]，利用連接和剪枝對候選項集進行處理，從而得到頻繁項集；2000年Han等基于樹型提出了頻繁模式增長(frequent pattern growth algorithm，F(xiàn)P-Growth)算法[3]，該算法在挖掘過程中不產(chǎn)生候選項，因此，較之前的算法，該算法時間優(yōu)勢明顯，但因要存儲所有頻繁模式，內(nèi)存占用較高。這些方法都以靜態(tài)數(shù)據(jù)為研究對象，然而在實際問題中廣泛存在著動態(tài)數(shù)據(jù)。為從動態(tài)數(shù)據(jù)中挖掘關聯(lián)規(guī)則，人們提出了關聯(lián)規(guī)則的增量更新挖掘算法。Cheung等在ICDE`96上提出了快速更新算法(fast update algorithm, FUP)算法[4]來解決在數(shù)據(jù)集增加情況下的頻繁項集挖掘，其后又在1997年提出了FUP2算法[5]解決數(shù)據(jù)集減少時的頻繁項集挖掘；馮玉才等于1998年提出了增量更新算法(incremental updating algorithm，IUA)算法[6]解決了支持度變化情況下頻繁項集的挖掘；Koh等在2003年基于FP-tree算法提出了基于FP樹的增量挖掘算法(adjusting FP-Tree for incremental mining algorithm，AFPIM)算法[7]解決數(shù)據(jù)集變化情況下的挖掘。在眾多面向增量關聯(lián)規(guī)則的算法中，F(xiàn)P-Growth改進的算法性能要比Apriori改進的算法好，但是操作遠比后者繁瑣[8-9]。為了方便事務的增加刪除操作并保持挖掘效率，W.Cheung等[10]于2003年結(jié)合FP樹和前綴樹提出了壓縮排列的事務序列樹(compressed and arranged transaction sequences tree,CATS-tree)，首次實現(xiàn)了“一次建立，多次挖掘”的目的；Leung在2005年在CATS樹基礎上改進了樹節(jié)點的排列方式提出了Can樹[11]，Can樹要求事務中的各項先按照某種順序排序，然后再開始建樹和挖掘等操作，以此再次提高了挖掘效率。

Can樹(Canonical order tree)利用樹型存儲了所有數(shù)據(jù)，方便了數(shù)據(jù)的增刪以及支持度改變后的再次挖掘。在挖掘時采用了和FP-Growth同樣的方法。因為Can樹比FP樹更加龐大，這導致在某些情況下Can樹挖掘頻繁項集所需時間有可能大于FP-Growth算法，例如Sadat等[12]在2015年對Can樹和FP-Growth算法進行了比較，發(fā)現(xiàn)在高閾值的最小支持度時，Can樹的性能優(yōu)于FP-Growth，但在低閾值的最小支持度時，性能不如FP-Growth算法。雖然Can樹已提出了十多年，但改進方法并不多。鄒力鹍等[13]在2008年采用了子父節(jié)點指針代替原先的父子節(jié)點指針，以此快速生成條件模式樹，提高算法效率。陳剛等[14]在2014年提出一種基于CAN樹的快速構(gòu)造算法(a fast construction algorithm based on Can-tree，F(xiàn)CCAN)，該算法同樣使用子父節(jié)點指針代替原先的父子節(jié)點指針，并增加基于hash表的輔助存儲結(jié)構(gòu)，用于減少項目的查找時間。Roul等[15]在2014年提出了生成和歸并樹(generate and merge tree，GM-tree)，他們保留了Can樹生成的方式，在增量時對數(shù)據(jù)進行分塊，每一塊生成一棵樹，最后再進行樹合并。但是，Can樹由于存儲了所有數(shù)據(jù)，導致規(guī)模過大，因此挖掘效率有待提升。為了優(yōu)化Can樹規(guī)模，提高挖掘效率并且改善Can樹的不穩(wěn)定性，本文中我們提出了一種改進的基于Can樹的關聯(lián)規(guī)則增量更新算法，并通過實驗對該算法的有效性進行了驗證。

1 Can樹

Can樹是Leung于2005年基于CATS樹改進后提出的解決關聯(lián)規(guī)則增量挖掘的算法[11]。Can樹采用了前綴樹，并讓盡量多的相同事務項合并在一起，以此來存儲所有數(shù)據(jù)。算法要求事務中的每個項按照某種特定順序進行排序后再構(gòu)建Can樹，排序一般采用字典序、字母序等，這樣在挖掘增量關聯(lián)規(guī)則的時候，新來的數(shù)據(jù)可以直接鏈入到原來的Can樹中，不用重新構(gòu)建新樹以及再次掃面原來的數(shù)據(jù)，從而提高了關聯(lián)規(guī)則增量更新的效率。

Can樹挖掘頻繁項集總共分為2步：先構(gòu)建Can樹，再從Can樹中挖掘頻繁項集。Can樹的構(gòu)建很簡單，先將事務中的項按照字典序或字母序排序(這2種排序方法是Can樹默認的)，然后將排序后的事務依次插入到Can樹中即可。因為，事務項已經(jīng)按照統(tǒng)一規(guī)則排序，在插入時無須對樹枝進行多余的剪枝或轉(zhuǎn)換等操作。從Can樹中挖掘頻繁項集的過程如下。

1)從Can樹節(jié)點自下而上挖掘。首先找到最下面的項，構(gòu)建每個項的條件模式基；順著Can樹，找出所有包含該項的前綴路徑，這些前綴路徑就是該項的條件模式基(conditional pattern base, CPB)；所有這些CPB的頻繁度(計數(shù))為該路徑上項的頻繁度(計數(shù))；

2)累加每個CPB上的項的頻繁度(計數(shù))，過濾低于閾值(最小支持度)的項，構(gòu)建條件FP-tree；

3)遞歸挖掘每個條件FP-tree，累加后綴頻繁項集，直到條件FP-tree為空或者條件FP-tree只有一條路徑(只有一條路徑情況下，所有路徑上項的組合都是頻繁項集)。

Can樹相對于其他增量挖掘算法的優(yōu)勢是可以存儲所有數(shù)據(jù)，在挖掘動態(tài)數(shù)據(jù)時，省去了再次讀取或掃描原數(shù)據(jù)的步驟，以此節(jié)約了時間，但缺點也較明顯：因要存儲所有數(shù)據(jù)而使得Can樹需要占用大量內(nèi)存存儲整棵Can樹，所以Can樹的規(guī)模大小直接決定了占用的內(nèi)存大小。此外，在增量挖掘時，不論是增刪數(shù)據(jù)還是挖掘頻繁項集，都需要遍歷Can樹，所以Can樹的規(guī)模大小還間接的決定了Can樹算法的時間效率。

2 一種基于數(shù)據(jù)量排序的Can樹

根據(jù)前述，Can樹的規(guī)模對算法的效率有直接影響，而當前預排列事務數(shù)據(jù)時所使用的順序?qū)⒂锌赡苁沟肅an樹的規(guī)模太大，從而使得算法效率較低。例如，數(shù)據(jù)集如表1所示。

表1 數(shù)據(jù)集

表1數(shù)據(jù)集已按照字母序排序，在此基礎上建立Can樹，則會得到如圖1a所示的Can樹。

圖1 數(shù)據(jù)集建立Can樹Fig.1 Built Can-tree

由圖1a可看出，該樹中有很多節(jié)點是表示相同數(shù)據(jù)項的，例如節(jié)點a，節(jié)點b，節(jié)點c，節(jié)點d，節(jié)點e的第一個子節(jié)點都是項x，由于未能合并在一起，在挖掘樹時，需要遍歷整棵樹，從而降低了挖掘效率。如果能夠盡量讓相同的數(shù)據(jù)項使用同一個樹節(jié)點，則可以有效減小樹規(guī)模，從而提高挖掘效率。因此，本文通過改變以往的排序方法，提出了一種基于數(shù)據(jù)量排序的Can樹。具體而言就是將次數(shù)最多的數(shù)據(jù)項放在最前面，將次數(shù)最少的數(shù)據(jù)項放在最后面，這樣可以讓盡量多的相同數(shù)據(jù)項使用同一個節(jié)點，以此來減小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ù)項依照上面的順序排序，如表2所示。

表2 數(shù)據(jù)集按照數(shù)據(jù)量排序

這樣排序后，再進行Can樹的建立，可得圖1b所示的Can樹。

比較圖1a和圖1b，可以計算出使用字母序排序建立的Can樹節(jié)點數(shù)有21個(包含root節(jié)點)，而使用數(shù)據(jù)量排序建立的Can樹節(jié)點樹只有9個(包含root節(jié)點)。可見，由于相同的數(shù)據(jù)項都使用了同一個樹節(jié)點，本文的方法較原有的方法所得到的樹規(guī)模小得多。

2.1 構(gòu)建Can樹

在首次構(gòu)建Can樹時，需得到一個數(shù)據(jù)量排序順序(即原數(shù)據(jù)量順序)，在增量更新時，由于數(shù)據(jù)量在變化，數(shù)據(jù)量排序順序也有可能發(fā)生改變，所以在增量更新挖掘時，排序順序仍采用原數(shù)據(jù)量順序進行排序，同時數(shù)據(jù)量排序結(jié)果仍進行更新，得到新數(shù)據(jù)量順序，以方便挖掘時在比較該項的總計數(shù)是否低于閾值(即該項是否為頻繁項)時能夠直接判斷使用，不用再次計算。并在建樹同時，參考陳剛等[13]的改進方法，增加hash表記錄每個項在樹中的位置，因為初次建樹和增量建樹略有區(qū)別，所以實現(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)//將每條事務根據(jù)原數(shù)據(jù)量順序排序

4) insert(trans,Can-tree)//將排序后的事務插入樹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)//將每條事務根據(jù)原數(shù)據(jù)量順序排序

4) insert(trans,Can-tree)//將排序后的事務插入樹T中

5) end for

2.2 挖掘Can樹

Can樹挖掘的流程如圖2a所示。因為Can樹保存了所有數(shù)據(jù)，該方法遍歷所有項時就會遍歷非頻繁項，這樣會浪費部分時間在非頻繁項上。所以本文結(jié)合之前得到的數(shù)據(jù)量排序順序?qū)ν诰蜻^程進行了改進。在挖掘時，根據(jù)數(shù)據(jù)量排序順序，將數(shù)據(jù)量低于閾值(最小支持度)的項舍去，只需要構(gòu)建數(shù)據(jù)量高于或等于閾值(最小支持度)的項的CPB即可，后續(xù)步驟則繼續(xù)原方法，改進后的挖掘流程如圖2b所示。

圖2 挖掘Can樹流程圖Fig.2 Flow chart of mining Can-tree

這樣可以減少遍歷一些非頻繁項所花的時間。改進后的挖掘偽碼如下。

輸入：Can-tree,最小支持度min_sup;

輸出：頻繁項集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

3 實驗結(jié)果與分析

實驗主要從2方面進行了對比，實驗1利用不同量的數(shù)據(jù)進行建樹，比較了2種不同排序方法建立的Can樹的規(guī)模大小；實驗2通過增量挖掘比較了基于2種不同排序方法的Can樹算法、FP-Growth算法、以及陳剛等提出的FCCAN算法的時間效率。

實驗中使用了3個公開的數(shù)據(jù)集：①mushroom數(shù)據(jù)：共有事務8 124條，項目26個；②Groceries數(shù)據(jù)：共有事務9 835條，商品169件；③pumsb數(shù)據(jù)：共有事務49 046條，項目711件。

實驗的運行環(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)編程實現(xiàn)。

實驗1表3為改進前后的2種Can樹在3個數(shù)據(jù)集上所生成的節(jié)點數(shù)量的對比。結(jié)果表明，由數(shù)據(jù)量順序排序生成的Can樹規(guī)模都小于由字典序排序生成的Can樹。具體而言，Can樹的節(jié)點數(shù)平均減少33.7%，最多減少56.9%?？梢娛褂脭?shù)據(jù)量排序可以有效減小Can樹的規(guī)模。

實驗2對于mushroom數(shù)據(jù)集，基礎數(shù)據(jù)量定為2 000，每次使用不同增量進行試驗，試驗結(jié)果如圖3所示。從圖3中可以看出，在增量挖掘時(圖3中后4組)，F(xiàn)P-Growth所花時間高于Can樹挖掘時間，而在所有基于Can樹的算法中，本文的算法在時間效率上又優(yōu)于基于字典序的Can樹算法以及FCCAN算法。

對于Groceries數(shù)據(jù)集，基礎數(shù)據(jù)量定為1 000，每次使用不同增量進行試驗，實驗結(jié)果如圖4所示，從圖4中可看出，基于字典序的Can樹算法和FCCAN算法在事務量增加較多后(后3組)，其時間效率反而不如FP-Growth算法，而本文的算法依然優(yōu)于所有其他算法。

表3 2種Can樹在3個數(shù)據(jù)上生成的節(jié)點數(shù)量對比

圖3 mushroom挖掘時間對照Fig.3 Time comparison onmushroom

圖4 Groceries挖掘時間對照Fig.4 Time comparison onGroceries

對于pumsb數(shù)據(jù)集，基礎數(shù)據(jù)量定為5 000，每次使用不同增量進行試驗，試驗結(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

4 結(jié)束語

本文針對動態(tài)數(shù)據(jù)中的關聯(lián)規(guī)則挖掘，使用數(shù)據(jù)量順序替代字典序和字母序?qū)?shù)據(jù)進行預處理，提出了一種基于數(shù)據(jù)量排序的Can樹，并基于新的Can樹對原有Can樹的建樹和挖掘方法進行優(yōu)化，實驗結(jié)果表明，本文提出的方法能夠有效降低Can樹的規(guī)模，提高增量關聯(lián)規(guī)則挖掘的效率。這種方法還可運用在分布式、多源數(shù)據(jù)等多種環(huán)境中，這將是本文下一步的研究工作。