分布式全局最大頻繁項集挖掘算法

楊君銳，何洪德，楊莉，李海文，薛萍

（西安科技大學 計算機科學與技術學院，陜西 西安，710054）

關聯規則挖掘的重點任務是頻繁項目集（亦稱頻繁模式）挖掘。然而，由于頻繁項目集挖掘具有特有的計算復雜度問題，業界提出最大頻繁項目集挖掘。在單處理機上的最大頻繁項目集挖掘研究方面，人們已取得許多成果[1?4]：Max-Miner算法是較早提出的典型算法[1]，其基于經典的Apriori思想[5]并采用寬度優先搜索策略，實現挖掘；DMFIA算法[2]和MMFI算法[3]均基于經典的 FP-growth算法[6]，不需要產生條件模式基和條件模式樹，且只需掃描2遍數據庫；而Mafia算法[4]采用深度優先搜索策略以及 3種剪枝方法，從而被認為是性能較好的經典算法。由于單處理機的計算能力和可利用的存儲空間有限，以及網絡技術與分布式數據庫技術的迅速發展，使得對分布式/并行挖掘的研究成為必然。在針對分布式/并行挖掘的（全局）頻繁項集算法的研究方面，研究者也已取得較多成果[7?12]，如：基于 Apriori思想的 CD，DD 和 CaD[7]算法；基于FP-growth算法的MLFPT算法[8]、PFP-tree算法[9]和 FDMA 算法[10]等。這些方法通過采用FP-tree[6]存儲結構，避免生成大量候選項集或條件模式樹，以減小網絡通信量，提高挖掘效率；還有其他算法，如FDM算法[11]、DDDM算法[12]等，它們通過減少候選項集的數目以及優化網絡通信策略來降低每次迭代的通信開銷，從而改善挖掘效率。與針對分布式/并行挖掘的頻繁項集算法的研究相比，分布式/并行挖掘的（全局）最大頻繁項集算法方面的研究較少[13?16]。DMM（Distributed Max-Miner）算法[13]采用 2階段挖掘策略即局部挖掘與全局挖掘。在局部挖掘時，采用Max-Miner方法得到局部最大頻繁項集，然后，所有節點通過交換與合并局部最大頻繁項集來生成全局最大頻繁項集的候選集，并將其存儲在 Prefix tree中，最后通過全局挖掘，得到全局最大頻繁項集；GridDMM（Grid-based distributed max-miner）算法[14]與DMM 類似，只是它是基于數據網格系統的分布式最大頻繁項集挖掘算法，并且在全局最大頻繁項集挖掘時采用自頂向下的搜索策略；這 2個算法均基于Apriori思想。FMGMFI（Fast mining global maximum frequent itemsets）算法[15]采用FP-Tree結構來壓縮存儲數據庫，通過掃描數據庫2遍，以及點到點通信方式和利用自底向上和自頂向下的雙向搜索策略來挖掘全局最大頻繁項集。但該算法存在的問題是，在挖掘時需多次掃描 FP-tree樹。MGMF（Mining global maximum frequent itemsets on FP-tree）算法[16]也是基于FP-Tree的結構來壓縮存儲數據庫，通過被約束子樹MGMF[16]進行超集檢測與剪枝，利用PDDM[16]播報消息的方式來廣播項集，從而完成挖掘，該算法存在的問題是，它沒有有效利用FP-tree結構，使得挖掘效率受到影響。本文提出一個分布式全局最大頻繁項集挖掘算法（DMFI），該算法基于 FP-tree的改進頻繁模式樹（IFP_tree），在各站點上分別建立該存儲樹，并使用有序方式存儲頻繁項目，然后通過對各局部數據庫的掃描，來挖掘出局部最大頻繁項集，最后利用共享各局部數據庫生成的最大頻繁項集以及利用 PDDM 組通信播報消息的方式，從而挖掘出全局最大頻繁項集的集合。仿真實驗表明：DMFI算法具有較好的性能。

1 問題描述

1.1 相關概念

定義 1 給定一個事務數據庫 D，其中事務集 T是由事務ti（i=1,2,…）組成的集合，每條事務t由標識符Tid唯一標識，則t（t∈T）所處理的項目的集合稱為項集（亦稱模式），記為It，T中所有事務處理的項目的集合記為 I，I={i1,i2,…,im}。設有項集 X?I和事務 t∈T，若X?It，則稱事務t包含項集X。而把一個項集X中所含項目的個數稱為該項集的維數或長度，記為|X|，若存在|X|=k（1≤k≤m），則稱X為k_項集。

定義2 設分布式數據庫D是水平劃分的，且各部分的數據庫邏輯同構。則在n個站點S1,S2,…,Sn上的事務數據庫分別為D1,D2,…,Dn，且則稱Di（1≤i≤n）為局部事務數據庫，D稱為全局事務數據庫。|D|及|Di|分別代表D和Di中所含的事務數。

定義 3 對于項集 X，Xc和 Xci分別表示 D和 Di中包含項集X的事務數，稱Xc為X在D中的全局支持數；Xci為 X在 Di中的局部支持數。若 Xs=Xc/|D|，則稱Xs為X在D中的全局支持度；若Xsi=Xci/|Di|，則稱Xsi（1≤i≤n）為X在Di中的局部支持度。

定義4 設給定最小支持度閾值S，對于項集X，當Xs≥S時，稱X為全局頻繁項集；否則，稱X為非全局頻繁項集。當Xsi≥S時，稱X為Di的局部頻繁項集；否則，稱X為Di的非局部頻繁項集。

定義5 對于項集X，若X為全局頻繁項集，而X在D中的任何超集都為非全局頻繁項集，則稱X為全局最大頻繁項集；所有X的集合稱為全局最大頻繁項集的集合，記為MFS（Maximal frequent sets）。若X為Di（1≤i≤n）的局部頻繁項集，而X在Di中的任何超集都為非全局頻繁項集，則稱X為局部最大頻繁項集；所有 X的集合稱為局部最大頻繁項集的集合，記為MFSi。

定義 6 對所有頻繁 1_項集（以下簡稱為頻繁項目），按其支持數降序的排列，稱為頻繁項目的列表L1。對L1中的頻繁項目依次進行編號（從“1”開始）后的列表，稱為頻繁項目的序列表L1′。

由上述定義易得下列性質和定理。

性質1 任一最大頻繁項集均由L1或L1′中的頻繁項目組成，且該最大頻繁項集的所有非空子集都是頻繁項集。

性質2[10]若項集X為全局頻繁項集，則至少存在一站點Si（1≤i≤n），使得X及X的所有非空子集在站點Si上為局部頻繁項集。

定理1[15]如果項集X是全局最大頻繁項集，則必存在一站點Si（1≤i≤n），使得X為其上某一局部最大頻繁項集的子集。

由定理1可得下列推論。

推論 若項集X不是任一站點Si（1≤i≤n）上的局部最大頻繁項集的子集，則X一定不是全局最大頻繁項集。

定理2 設項集Y為某站點上的局部最大頻繁項集，X?Y且為全局頻繁項集。若對任意站點上的任意局部最大頻繁項集Y′，不存在全局頻繁項集Z?Y′使得X?Z，則X是全局最大頻繁項集。

證明：（反證法）由推論1可知：全局最大頻繁項集可通過局部最大頻繁項集的子集得到。若X不是全局最大頻繁項集，因為X為全局頻繁項集，則設X?Z且Z為全局最大頻繁項集，由定理1知，一定存在某個站點Si使得Z?Y′且Y′為局部最大頻繁項集，這與已知條件矛盾。從而定理得證。

1.2 IFP-tree

針對最大頻繁項集的特點，提出基于FP-tree[6]的改進數據存儲結構IFP-tree，用于數據信息的存儲。

IFP-tree為滿足以下3個條件的樹型結構：

（1）有1個標記為“root”的根節點。

（2）IFP-tree的節點由 6個域組成：節點序號（node_no）為該節點所代表的頻繁項目在L1′中的序號；節點計數（node_count）記錄從根節點到該節點的路徑上所代表的頻繁項目在數據庫中出現的次數；節點的子鏈接（child_link）是指向該節點的第 1個子節點的指針；節點的兄弟鏈接（brother_link）是指向該節點的兄弟節點的指針；節點的父鏈接（parent_link）是指向該節點的父節點的指針；同名節點鏈（node_link）是指向IFP-tree中同名節點的指針。

（3）IFP-tree包含1個項目頭表Htable，而該表的每個表項包含 2個域：item_no（項目序號，其作用與node_no的相同）；item_head（項目鏈頭）為指向IFP-tree中具有相同的item_no的首節點指針。

IFP-tree的構造算法如下（各站點 Si（1≤i≤n）同步）：

（1）掃描各局部事務數據庫 Di，得到各項目的局部支持數。然后，對所有的局部支持數進行規約求和，繼而得到各項目的全局支持數。最后得到全局頻繁項目，并據此得到L1和L1′。

（2）創建IFP-tree的根節點R，標記為“root”，且使R.child_link=Null，R.brother_link=Null，R.parent_link=Null。

（3）按L1的次序排列事務t中的頻繁項目，忽略t中非頻繁項目，然后，按L1′對其進行對應編號代替，得到 t′。

（4）假定排序后t′的結果為[n|N]，其中n是第一個頻繁項目的編號，N是剩余頻繁項目的編號列表。然后，按照類似FP-Tree的生成過程得到初始樹IFP-tree。

（5）在初始樹IFP-tree中，對任意一個節點A，判斷A的孩子子樹和A的兄弟子樹中是否有node_no相同的節點，若有，則進行合并，即先將 2節點的node_count相加，作為 A的兄弟子樹中此節點新的node_count，A的孩子子樹保持不變；然后將層次計數器增1，比較下一層對應節點的node_no，重復上述過程，直到出現node_no不相同時停止。若node_no值不相同，則將A的孩子子樹中的節點插入到A的兄弟子樹中（詳細的合并過程見文獻[17]）。

（6）將Htable中item_no對應的item_head鏈接到節點序號為item-no的首節點。

設全局事務數據庫 D如表 1所示（表中 Frequent items欄給出的是：該D在最小支持度閾值S=0.5時的頻繁項集；item_no欄為頻繁項集對應的編號），有 2個站點S1和S2可用，D1存放D中的前4條事務，D2存放 D中的后 4條事務，則 D1對應的頻繁模式樹IFP-tree的構造結果如圖1所示。其中：圓圈中冒號前的數字為節點的 node_no，冒號后的數字為節點的node_count。

根據IFP-tree的結構和構造過程易得下列性質和定理。設給定事務數據庫D，D對應的頻繁模式樹為IFP-tree，最小支持度閾值 S，即最小支持數閾值 ξ（ξ=S×|D|）。

性質3 事務數據庫D中所含的任一頻繁項集都被記錄在IFP-tree的某條路徑上。

性質4 在IFP-tree中，節點的node_count值從上到下降序排列；節點的node_no值從左到右升序排列。

由IFP-tree結構易得下列定理3。

定理3 在IFP-tree中，若某節點計數不小于最小支持數閾值 ξ，則以該節點和其前綴路徑中的節點組成的項集必為頻繁項集。

表1 全局事務數據庫Table 1 Global Business database

圖1 D1對應的IFP-treeFig.1 IFP-tree of D1

定理4 在IFP-tree中，若某節點N的node_count≥ξ，而N的子節點的node_count＜ξ，則N的所有子孫節點的node_count＜ξ。這樣，從根節點R到N的路徑上的節點就是1個最大頻繁項集或最大頻繁項集的候選集。

證明：若某節點N的子節點的node_count＜ξ，由性質4可知，N的子節點以下的所有節點的node_count＜ξ，即 N的下層子樹沒有頻繁節點，故從根節點 R到N的路徑就構成了D的1個最大頻繁項集或最大頻繁項集的候選集。證畢。

2 分布式全局最大頻繁項集挖掘算法DMFI

假設有n臺基于共享體系結構的計算機，組成n個站點 Si（1≤i≤n），事務數據庫 D被均分成 n份 Di存于各站點。站點 Si上的 Di對應的頻繁模式樹記為IFP-treei，根節點為rooti，其對應的局部最大頻繁項集的集合和候選集合分別記為MFSi和 CFSi。而 MFCS為MFSi的并集。

2.1 DMFI算法的基本策略

DMFI算法的基本策略是：（1）對各站點Si，分別創建完全獨立、互不影響的 IFP-treei。另外，為提高挖掘效率，IFP-treei采用合并策略[17]，即把具有相同前綴的子樹合并在一起，從而不需要構造條件模式樹；（2）整個挖掘分為局部挖掘與全局挖掘2個階段；（3）根據定理3和4，在局部挖掘中，采用深度優先搜索和寬度優先搜索相結合的方式，即深度優先是根據child_link鏈接由根節點不斷向子節點的搜索，寬度優先是根據brother_link鏈接而完成的橫向搜索，從而先得到CFSi，繼而得到MFSi和MFCS；（4）在全局挖掘中，采用共享體系結構，共享各站點生成的局部最大頻繁項集MFCS，在各站點處理器同步的情況下，依次對MFCS中維數最大的項集利用PDDM組通信播報消息的方式來廣播以及挖掘，直至MFCS為空，最終得到全局最大頻繁項集的集合。

2.2 DMFI算法描述

DMFI算法由局部最大頻繁項集的挖掘 LMFI（ ）與全局最大頻繁項集的挖掘GMFI（ ）2部分組成。下面分別描述。

Procedure LMFI（ ）

輸入：局部事務數據庫 Di（1≤i≤n）對應的IFP-treei；最小支持度閾值S。

輸出：局部最大頻繁項集的集合MFSi。

1.MFSi=CFSi=NULL

2.將非根節點N設為當前節點;

3.while（當前節點!= NULL）

4.{ if（當前節點的計數 ≥ S×|Di|）

5.then { CFSi= CFSi∪從根節點到當前節點的路徑所組成的項集;

6.將N的子節點設為當前節點;}

7.else {將N的子節點的兄弟節點設置為當前節點;}

8.}

9.將N的兄弟節點設置為當前節點;

10.GOTO 3;

11.從CFSi中檢出局部最大頻繁項集，并送入MFSi;

12.return MFSi;

Procedure GMFI（ ）

輸入：MFSi（1≤i≤n）；最小支持數閾值ξ。

輸出：全局最大頻繁項集的集合MFS。

1.MFS=Null;MFCS = MFS1∪MFS2∪…∪MFSn;

2.while MFCS ≠ ? do

3.{ 同步各處理器;

4.從MFCS中無放回的取出維數最大的項集X，并設 X∈MFSi（i=1,…,n）；

5.if（X的計數X.ci≥ξ ）

6.then { MFS = MFS∪{X};break;}

7.else { 站點Si以組方式將X的信息發送到其他站點 Sj（1≤j≤n 且 j≠i）；

8.各站點 Sj將各自的局部支持數發送到站點Si；

9.站點 Si計算全局支持數，即 X.c＝

10.if（X.c≥ξ）then { MFS = MFS∪{X};break;}

11.else 將|X|_項集 X 的所有（|X|-1）維項集（即 X的所有（|X|-1）維子項集）并入MFCS；} }

12.return MFS;

3 算法測試與性能分析

為驗證算法DMFI的性能，對算法進行實驗測試。實驗環境是在10Mb的局域網中，用數臺PC機（具體臺數隨測試內容不同而不同）構成分布式站點，各臺PC機配置均為：操作系統為 Windows XP，CPU為PIV400，內存為1 GB。實驗程序均采用VC++6.0實現。實驗中選用的數據集分別是由 http://www.ics.uci.edu/～mlearn/MLRepository.html上提供的蘑菇數據庫mushroom（該數據庫含有8 124條記錄，記錄蘑菇的 23種屬性）和由 IBM Almaden實驗室（http://www.almaden.ibm.com/cs/projects/iis）提供的 T|T|I|I|D|D|合成數據庫（其中|T|表示數據集中事務的平均長度，|I|表示潛在頻繁項集的平均長度，|D|表示數據庫中總的事務數目）中的 T40I10D100k和 T40I10D1000k。測試從以下幾方面進行。

3.1 執行效率的對比測試與分析

由于目前針對基于分布式的最大頻繁項集的挖掘研究成果較少，在進行研究與分析后，選擇性能相對較好的FMGMFI算法[15]和MGMF算法[16]作為實驗中的比較測試對象。

測試方法（3.2節同樣也采用此方法）是：先由3臺PC機構成分布式站點，然后將選用的交易數據庫 D均分到3個站點，且使各站點的記錄數相等，最后，分別用FMGMFI，MGMF和DMFI來挖掘全局最大頻繁項集。

當最小支持度閾值S分別取10%，20%，30%，40%，50%，60%，70%，80%和90%，而當選用的數據庫分別為mushroom，T40I10D100k和T40I10D1000k時，3個算法的執行結果如圖2～4所示。另外，在不同情況下執行時，經比較3個算法挖掘的結果也完全一樣。從測試結果可看出，DMFI算法的性能明顯優于FMGMFI和MGMF算法。

3.2 通信次數測試與分析

當最小支持度閾值 S分別從 10%到 90%時，FMGMFI，MGMF和DMFI算法分別在T40I10D100k上挖掘全局最大頻繁項集時需要的通信次數結果如圖 5所示。

圖2 在mushroom數據庫上的對比Fig.2 Experimental results on mushroom database

圖3 在T40I10D100k數據集上的對比Fig.3 Experimental results on T40I10D100k

圖4 在T40I10D1000k數據集上的對比Fig.4 Experimental results on T40I10D1000k

從圖5可見：DMFI算法需要的通信次數最少。已知在分布式挖掘中，通信次數的多少將影響算法的執行效率，所以，此結果也說明DMFI算法的高效性。

圖5 在T40I10D100k上網絡通信次數的對比Fig.5 Comparison of communication on T40I10D100k

3.3 可擴展性測試與分析

可擴展性是指問題規模增大時，算法性能不會降低。對分布式關聯規則挖掘算法，問題規模增大時有以下 2種情況：（1）參與挖掘的處理器數目增加；（2）數據庫規模增大。下面分別從這 2個方面進行DMFI算法的可擴展性測試。

3.3.1 參與挖掘的處理器數目增加

對于分布式算法，處理器個數直接影響算法的執行效率。這里通過加速比反映處理器個數對算法性能的影響。分布式算法的加速比定義[18]為：Sp=T1/Tp（其中，T1指單個站點上算法的運行時間；Tp指p個站點上分布式算法的運行時間）。

最小支持度閾值取S=15%，處理器臺數依次增加，分別選用2，3，4，5，6和7臺，測試選用T40I10D100k，并將數據依次均分到不同站點。測試結果如表2所示。

表2 在T40I10D100k上的擴展性測試結果Table 2 Results of scalability tests on T40I10D100k

從表2可知：當處理器個數為2時，算法的執行時間最大，執行加速比最小。之后隨著處理器個數 p的不斷增加，算法執行時間依次減少，而加速比依次提高，也就是說執行效率不斷提高。

3.3.2 數據庫規模增大

分布式站點由 3臺 PC機構成。測試選用T40I10D100k，最小支持度閾值S取15%。測試方法是：先取數據集中的前10×103條記錄（均分到3站點）進行挖掘，隨后數據規模以10×103條記錄遞增后（同樣是均分到 3站點）再挖掘，直到 100×103條為止。測試結果如圖6所示。從圖6可見：隨著數據集規模的增長，算法執行時間基本呈線性穩步增長。

從以上測試結果，說明DMFI算法具有較好的可擴展性。

圖6 T40I10D100k數據集上的擴展性測試Fig.6 Scalability tests on T40I10D100k

4 結論

（1）根據分布式挖掘的特點，提出全局最大頻繁項集挖掘算法 DMFI。該算法采用文中提出的改進頻繁模式樹IFP-tree來存儲數據信息，并采用數字有序方式來表示項目信息，從而只需對事務數據庫掃描 2次，同時算法采用組通信播報消息的思想來實現站點間的通信，最終得到全局最大頻繁項集。

（2）DMFI具有較高的效率。

[1]Bayardo R J.Efficiently mining long patterns from databases[C]//Proceedings of the ACM SIGMOD Int’l Conference on Management of Data.New York:ACM Press,1998:85?93.

[2]宋余慶,朱玉全,孫志揮.基于FP-Tree的最大頻繁項目集挖掘及更新算法[J].軟件學報,2003,14（9）:1586?1592.SONG Yu-qing,ZHU Yu-quan,SUN Zhi-hui.An Algorithm and Its Updating Algorithm Based on FP-Tree for Mining Maximum Frequent Itemsets[J].Journal of Software,2003,14（9）:1586?1592.

[3]SG J,Chen C.MMFI:An effective algorithm for mining maximal frequent itemsets[C]//Proceedings of the IEEE International Symposium on Information Processing,IEEE CS Press,2008:26?30.

[4]Burdick D,Calimlim M,Gehrke J.Mafia:A maximal frequent itemset algorithm for transactional Database[C]//the 17th International Conference on Data Engineering.Heidelberg:IEEE Computer Society Press,2001:443?452.

[5]Agrawal R,Srikant R.Fast algorithms for mining association rules[C]//Proceedings of the 20th International Conference on Very Large Data Bases.Santigo,San Francisco:Morgan Kaufmann Publishers Inc,1994:487?499.

[6]Han J,Jian P,Yiwen Y.Mining frequent patterns without candidate generation[C]//Proceedings of 2000 ACM SIGMOD Int’l Conference on Management of Data.Dallas:ACM Press,2000:1?12.

[7]Agrawal R,Sharfer J.Parallel Mining of Association Rules[J].IEEE Transactions on Knowledge and Data Engineering,1996,8（6）:962?969.

[8]Zaiane O R,EI-Hajj M,Lu P.Fast parallel association rule mining without candidacy generation[C]//Proceedings of the 2001 IEEE International Conference on Data Mining.Washington:IEEE Computer Society Press,2001:665?668.

[9]Javed A,Khokhar A.Frequent pattern mining on message passing multiprocessor systems[J].Distributed and Parallel Databases,2004,16（3）:321?334.

[10]宋寶莉,覃征.分布式全局頻繁項目集的快速挖掘方法[J].西安交通大學學報,2006,40（8）:923?927.SONG Bao-li,QIN Zheng.Fast mining algorithm for distributed global frequent itemsets[J].Journal of Xi’an Jiaotong University,2006,40（8）:923?927.

[11]Cheung D W,Han J W,Ng V T.A fast distributed algorithm for mining association rules[C]//Proceedings of IEEE the 4th International Conference Parallel and Distributed Information Systems.Heidelberg:IEEE Computer Society Press,1996:31?44.

[12]Schuster A,Wolff R.Communication efficient distributed mining of association rules[C]//Proceedings of the ACM SIGMOD International Conference on Management of Data.New York:ACM Press,2001:473?484.

[13]Chung S M,Luo C.Distributed mining of maximal frequent itemsets from databases on a cluster of workstations[C]//2004 IEEE International Symposium on Cluster Computing and the Grid.Washington:IEEE Computer Society Press,2004:499?507.

[14]Luo C,Pereira A L,Chung S M.Distributed mining of maximal frequent itemsets on a data grid system[J].The Journal of Supercomputing,2006,37（1）:71?90.

[15]陸介平,楊明,孫志揮,等.快速挖掘全局最大頻繁項目集[J].軟件學報,2005,16（4）:553?560.LU Jie-ping,YANG Ming,SUN Zhi-hui,et al.Fast mining of global maximum frequent itemsets[J].Journal of Software,2005,16（4）:553?560.

[16]王黎明,趙輝.基于 FP樹的全局最大頻繁項集挖掘算法[J].計算機研究與發展,2007,44（3）:445?451.WANG Li-ming,ZHAO Hui.Algorithm of mining global maximum frequent itemsets based on FP-tree[J].Journal of Computer Research and Development,2007,44（3）:445?451.

[17]YANG Jun-rui,GUO Yun-kai.Fast mining maximal frequent itemsets based on sorted FP-tree[C]//Proceedings of the 7th World Congress on Intelligent Control and Automation.Chongqing:Chongqing University,2008:5391?5395.

[18]孫世新,盧光輝,張艷,等.并行算法及其應用[M].北京:機械工業出版社,2005:32?45.SUN Shi-xin,LU Guang-hui,ZHANG Yan,et al.Parallel algorithm and its application[M].Beijing:Machinery Industry Press,2005:32?45.