摘  要： 在最大頻繁項(xiàng)集的挖掘過程中，尤其在數(shù)據(jù)規(guī)模龐大并且最小支持度較小的情況下，超集檢測(cè)成為算法運(yùn)行的主要時(shí)間消耗，提出最大頻繁項(xiàng)集算法A-MFI，其通過優(yōu)化基于投影的超集檢測(cè)機(jī)制有效地減少了超集檢測(cè)的時(shí)間。另外，將事務(wù)數(shù)據(jù)庫(kù)數(shù)據(jù)映射至一種壓縮的AFOPT-tree結(jié)構(gòu)，該結(jié)構(gòu)結(jié)合自頂向下的遍歷策略，具有更小的時(shí)間開銷。

　　關(guān)鍵詞： 最大頻繁項(xiàng)集；關(guān)聯(lián)規(guī)則；超集檢測(cè)；最大頻繁項(xiàng)集投影

　　1993年AGRAWAL R等人提出了一個(gè)重要的反映大規(guī)模數(shù)據(jù)中項(xiàng)目集之間有趣的關(guān)聯(lián)或相關(guān)聯(lián)系的研究課題[1]，找出屬性間有價(jià)值的關(guān)系，即關(guān)聯(lián)規(guī)則的研究。頻繁項(xiàng)集的挖掘是獲取關(guān)聯(lián)規(guī)則不可或缺的步驟。但挖掘頻繁項(xiàng)集時(shí)需要考慮太多的候選項(xiàng)集。最大頻繁項(xiàng)集中已經(jīng)隱含了所有的頻繁項(xiàng)集，并且在許多數(shù)據(jù)挖掘應(yīng)用中也只需要挖掘最大頻繁項(xiàng)集，而不是獲取所有的頻繁項(xiàng)集，因此對(duì)最大頻繁項(xiàng)集的挖掘具有重大的現(xiàn)實(shí)意義。

　　已有的最大頻繁項(xiàng)集挖掘算法可以按照對(duì)搜索空間樹的遍歷策略分為寬度優(yōu)先算法和深度優(yōu)先算法兩種。其中，MaxMiner、DMFI和DMFIA為寬度優(yōu)先算法。MaxMiner[2]采用傳統(tǒng)的橫向數(shù)據(jù)集來計(jì)算頻繁項(xiàng)集的支持度，雖然動(dòng)態(tài)排序的方法能保證高效的前瞻剪枝，但掃描次數(shù)與Apriori[3]算法相同，掃描數(shù)據(jù)集的次數(shù)等于最長(zhǎng)頻繁項(xiàng)集的規(guī)模。GenMax、SmartMiner、Fp-Max和FPMFI是挖掘最大頻繁項(xiàng)集的深度挖掘算法。算法GenMax[4]使用差集的方式表示事務(wù)數(shù)據(jù)庫(kù)，在稀疏事務(wù)數(shù)據(jù)庫(kù)的情況下有效減少了內(nèi)存開銷，并提出使用局部最大頻繁項(xiàng)集的方式進(jìn)行超集檢測(cè)。SmartMiner[5]算法使用尾信息進(jìn)行數(shù)據(jù)挖掘，不需要超集檢測(cè)，但尾信息數(shù)據(jù)結(jié)構(gòu)建立和訪問代價(jià)太高。Fp-Max[6]算法也是基于Fp-tree的最大頻繁項(xiàng)集挖掘算法，并將最大頻繁項(xiàng)集保存在MFI-tree[7]中，在一定程度上提高了挖掘效率。

　　本文提出的A-MFI（Ascending Frequency Ordered Prefix-tree For Maximal Frequent Item Set）算法通過對(duì)基于投影超集檢測(cè)方法[8]的優(yōu)化，有效地提升了超集檢測(cè)的效率；并采用AFOPT-tree（Ascending Frequency Ordered Prefix-tree）[9]來存儲(chǔ)數(shù)據(jù)挖掘的相關(guān)信息，有效地減少了自頂向下遍歷的時(shí)間開銷和遞歸次數(shù)[10]。

　　1 相關(guān)知識(shí)

　　1.1 頻繁項(xiàng)集和最大頻繁項(xiàng)集

　　設(shè)I={i1，i2，i3，…，in}是一個(gè)項(xiàng)目集合，給定事務(wù)數(shù)據(jù)庫(kù)D，對(duì)于項(xiàng)目集X?哿I且k=|X|，稱X為k項(xiàng)集，或者簡(jiǎn)稱為一個(gè)項(xiàng)集。記D為事務(wù)T的集合且T?哿I。對(duì)于給定的事務(wù)數(shù)據(jù)庫(kù)D，定義X的支持度為D中包含X的事務(wù)個(gè)數(shù)，記為Sup（X）。用戶自定義一個(gè)小于|D|的最小支持度，記為min_s。

　　定義1 給定書屋數(shù)據(jù)庫(kù)D和最小支持度min_s，對(duì)于項(xiàng)集X?哿I，若Sup（X）≥min_s，則稱X為D中的頻繁項(xiàng)集。

　　定義2 給定事務(wù)數(shù)據(jù)庫(kù)D和最小支持度min_s，對(duì)于項(xiàng)集X?哿I，若Sup（X）≥min_s并且對(duì)于任意（Y?哿I∧X?哿Y）均有Sup（Y）≦min_s，則稱X為D的最大頻繁項(xiàng)集。

　　性質(zhì)1 任何頻繁項(xiàng)集的真子集都不是最大頻繁項(xiàng)集。

　　1.2 頻繁模式樹AFOPT-tree

　　Liu Guimei等提出使用一種稱為AFOPT-tree[9]的數(shù)據(jù)結(jié)構(gòu)來存儲(chǔ)數(shù)據(jù)庫(kù)中與當(dāng)前挖掘過程相關(guān)的頻繁信息。AFOPT-tree中每個(gè)結(jié)點(diǎn)對(duì)應(yīng)一個(gè)項(xiàng)。樹中每一條從根結(jié)點(diǎn)到某個(gè)子孫結(jié)點(diǎn)的路徑表示一個(gè)項(xiàng)集，每個(gè)結(jié)點(diǎn)記錄了根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑對(duì)應(yīng)項(xiàng)集的支持度。由于某些項(xiàng)集前部項(xiàng)的重疊，AFOPT-tree可以通過共享這些重疊的項(xiàng)來達(dá)到壓縮保存的目的。

　　AFOPT-tree中有頭表，頭表中的頻繁1-項(xiàng)集按照頻繁次數(shù)的升序排列，它記錄了相應(yīng)頻繁項(xiàng)的名稱和支持度。AFOPT-tree樹體中相同項(xiàng)的指針鏈接在一條鏈表上，鏈?zhǔn)字羔樢脖４嬖陬^表中。數(shù)據(jù)庫(kù)中的各項(xiàng)事務(wù)項(xiàng)集也按照頭表中的次序添加到頻繁模式樹中。給定一個(gè)事務(wù)數(shù)據(jù)庫(kù)D，與其對(duì)應(yīng)的AFOPT-tree如圖1所示。AFOPT-tree的建立需要掃描兩次數(shù)據(jù)庫(kù)，AFOPT子樹的建立需要掃描兩次搜索空間中結(jié)點(diǎn)的AFOPT子樹中相應(yīng)的條件模式基[10]。

　　2 基于AFOPT-tree的最大頻繁項(xiàng)集挖掘算法A-MFI

　　2.1 優(yōu)化的基于投影的超集檢測(cè)

　　AFOPT-tree的頭表和加入的事務(wù)項(xiàng)集都是按照頻繁次數(shù)的升序排列的，按照頭表中頻繁1-項(xiàng)集的順序挖掘出的頻繁項(xiàng)集若存在超集，則必定在已挖掘到的最大頻繁項(xiàng)集中[11]。

　　MFI即最大頻繁集，是所有的最大頻繁項(xiàng)目集組成的集合。MFI-tree是類似于AFOPT-tree的樹形結(jié)構(gòu)，用來存儲(chǔ)最大頻繁項(xiàng)集。從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的一條路徑就是最大頻繁項(xiàng)，中間節(jié)點(diǎn)不記錄支持度，只有葉子節(jié)點(diǎn)記錄支持度數(shù)。這里將MFI-tree樹體中相同項(xiàng)的指針鏈接在一條鏈表上，鏈?zhǔn)字羔樢脖４嬖陬^表中[12]。

　　在進(jìn)行超集檢測(cè)時(shí)，不需要對(duì)整棵MFI-tree進(jìn)行投影，先檢測(cè)待檢測(cè)項(xiàng)集的第一項(xiàng)在頭表中指向MFI-tree的指針是否為空。若為空，則不需要投影，直接添加到MFI-tree中；若不為空，將待檢測(cè)項(xiàng)集第一項(xiàng)為根節(jié)點(diǎn)構(gòu)建MFI子樹。MFI子樹構(gòu)建過程只需要掃描一次MFI-tree中對(duì)應(yīng)結(jié)點(diǎn)的后繼結(jié)點(diǎn)。

　　對(duì)于圖1中的AFOPT-tree中已挖掘的最大頻繁項(xiàng)集{ampfc：3}，MFI-tree如圖2所示。有項(xiàng)集{bc：3}，檢查其是否在MFI-tree中存在超集。首先檢測(cè)頻繁1-項(xiàng)集b指向MFI-tree的指針為空，故項(xiàng)集在MFI-tree中不存在超集，將項(xiàng)集作為最大頻繁項(xiàng)集加入到MFI-tree中，如圖2所示虛線分支。再檢測(cè)項(xiàng)集{bf：3}，因?yàn)轭l繁1-項(xiàng)集b指向MFI-tree的指針不為空，構(gòu)建以b為根節(jié)點(diǎn)的MFI子樹，采用基于投影的超集檢測(cè)該項(xiàng)集在其中不存在超集，將項(xiàng)集作為最大頻繁項(xiàng)集加入到MFI-tree中，如圖2所示加粗分支。

　　2.2 A-MFI算法

　　與FP-max算法一樣，A-MFI算法采用分治遞歸的策略進(jìn)行挖掘。在深度優(yōu)先遍歷搜索AFOPT-tree時(shí)，通過對(duì)遍歷到的節(jié)點(diǎn)及對(duì)應(yīng)的AFOPT子樹頭表中的某一項(xiàng)來生成搜索空間的子節(jié)點(diǎn)。并在構(gòu)建AFOPT子樹之前先通過優(yōu)化的基于投影的超集檢測(cè)來檢測(cè)首尾項(xiàng)集的并集在已有的最大頻繁項(xiàng)集是否存在超集。若存在，則可以進(jìn)行前瞻剪枝；若不存在，遞歸的調(diào)用算法直到挖掘到某個(gè)子孫節(jié)點(diǎn)的AFOPT子樹為一個(gè)單路徑樹為止，將這個(gè)單路徑樹頭表中項(xiàng)集和對(duì)應(yīng)前綴節(jié)點(diǎn)的并集作為一個(gè)最大頻繁項(xiàng)集，加入到MFI-tree中。

　　2.3 算法步驟

　　全局變量：前綴項(xiàng)集p，最大頻繁項(xiàng)集樹MFI-tree

　　輸入：數(shù)據(jù)量對(duì)應(yīng)的AFOPT-tree，記為T，AFOPT-tree頭表中對(duì)應(yīng)的項(xiàng)集h

　　輸出：最大頻繁項(xiàng)集樹MFI-tree

　　A-MFI（T，h）

　?。?）if T是單路徑樹。

　　（2）將項(xiàng)集p∪h插入MFI-tree中，支持度為單路徑樹中葉子節(jié)點(diǎn)的支持度。

　?。?）else對(duì)T頭表中的每一項(xiàng)i。

　?。?）將i并入前綴項(xiàng)集p中，為p′。

　　（5）遍歷AFOPT-tree獲取p′對(duì)應(yīng)的子樹頭表項(xiàng)集h′。

　　（6）對(duì)p′∪h′進(jìn)行超集檢測(cè)。

　　（7）if在MFI-tree中不存在超集。

　　（8）創(chuàng)建AFOPT子樹T′。

　?。?）A-MFI（T′，h′）。

　?。?0）將i從p中移除。

　　3 實(shí)驗(yàn)分析

　　為驗(yàn)證算法性能，在內(nèi)存為DDR3 2 GB、CPU為Core i5-2410M、操作系統(tǒng)為Windows 7 Professional的實(shí)驗(yàn)環(huán)境下，用VC++ 6.0分別實(shí)現(xiàn)了A-MFI算法、FP-max算法和FPMFI算法。實(shí)驗(yàn)采用的數(shù)據(jù)為參考文獻(xiàn)[12]中的Mushroom數(shù)據(jù)庫(kù)。該數(shù)據(jù)庫(kù)中共有8 124條事務(wù)記錄，平均事務(wù)長(zhǎng)度為23，一共包含了蘑菇的115種屬性。A-MFI與FP-max和FPMFI的運(yùn)行時(shí)間比較如圖3所示。

　　從圖3的實(shí)驗(yàn)結(jié)果可以看出，由于A-MFI算法對(duì)基于投影的超集檢測(cè)機(jī)制進(jìn)行了優(yōu)化，并在存儲(chǔ)與數(shù)據(jù)挖掘相關(guān)數(shù)據(jù)時(shí)應(yīng)用了AFOPT-tree樹形結(jié)構(gòu)，在支持度較小時(shí)，尤其當(dāng)支持度小于1%時(shí)，相比FPMFI算法和FP-max算法在執(zhí)行時(shí)間上有較大優(yōu)勢(shì)。例如在最小支持度為0.1%時(shí)，算法FP-max、FPMFI和A-MFI的執(zhí)行時(shí)間分別為15.9 s，8.7 s和6.4 s，算法A-MFI的性能比較同類算法有明顯的提升。

　　本文提出了一種基于AFOPT-tree的最大頻繁項(xiàng)集挖掘算法，通過對(duì)基于投影的超集檢測(cè)機(jī)制進(jìn)行優(yōu)化，降低了超集檢測(cè)的時(shí)間消耗；采用AFOPT-tree樹形結(jié)構(gòu)存儲(chǔ)與數(shù)據(jù)挖掘相關(guān)的信息，提升自頂向下的遍歷效率并減少遞歸次數(shù)。實(shí)驗(yàn)比較表明，在支持度較小的情況下，本文的A-MFI算法具有明顯的優(yōu)越性。在算法的執(zhí)行過程中，遞歸構(gòu)建AFOPT子樹和超集檢測(cè)消耗了大量的時(shí)間和內(nèi)存，如何進(jìn)一步地減少遞歸次數(shù)并提高超集檢測(cè)的效率是以后研究的重點(diǎn)。

　　參考文獻(xiàn)

　　[1] AGRAWAL R， IMIELINSKI T， SWAMI A. Mining association rules between sets of items in large databases[C]. Proceedings of ACM SIGMOD International Conference on Management of Data，1993：207-216．

　　[2] BAYARDO R. Efficiently mining long patterns from databases[C]. Proceeding of 1998 ACM S1 GMOD International Conference on Management of Data， New York： ACM Press， 1998：85-93．

　　[3] AGRAWAL R， SRIKANT R. Fast algorithms for mining association， rules[C]. Proceedings of the 20th International Conference on Very Large Database，1994：478-499．

　　[4] GOUDA K， ZAKI M J. Efficiently mining maximal frequent item sets[C]. Proceedings of the IEEE International Conference on Data Mining，2001：163-170．

　　[5] ZHOU QH， WESLEY C， LU BJ. SmartMiner. A depth 1st algorithm guided by tail information for mining maximal frequent item sets[C]. Proceedings of the IEEE International Conference on Data Mining， 2002：570-577.

　　[6] GRAHNE G， ZHU J E． High performance mining of maximal frequent item sets[C]. Proceedings of the 6th SIAM International Workshop on High Performance Data Mining，2003：135-143．

　　[7] GRAHNE G， ZHU J F． High performance mining of maximal frequent item sets[C]. Proceedings of the 6th SIAM Int′I Workshop on High Performance Data Mining，2003：135-143．

　　[8] 顏躍進(jìn)，李舟軍，陳火旺．基于FP-Tree有效挖掘最大頻繁項(xiàng)集[J]．軟件學(xué)報(bào)，2005，16（2）：216-219．

　　[9] Liu Guimei， Lu Hongjun， Xu Yabo. Ascending frequency ordered prefix-tree：efficient mining of frequent patterns[C]. Proceedings of the 8th International Conference on Database Systems for Advanced Applications， Kyoto， Japan，2003：65-72.

　　[10] 毛宇星，陳彤兵，施伯樂.一種高效的多層和概化關(guān)聯(lián)規(guī)則挖掘方法[J]．軟件學(xué)報(bào)，2011，22（15）：2965-2980.

　　[11] 陳光鵬，楊育彬，高陽(yáng)，等.一種基于MapReduce的頻繁閉項(xiàng)集挖掘算法[J].模式識(shí)別與人工智能，2012，25（2）：220-224.

　　[12] 胡德敏，趙瑞可.一種改進(jìn)的最大頻繁項(xiàng)集挖掘算法[J].計(jì)算機(jī)應(yīng)用與軟件，2012，29（12）：186-188.