摘  要： 在最大頻繁項(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)的支持度,。

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

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

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

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

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

　?。?）創(chuàng)建AFOPT子樹T′,。

　　（9）A-MFI（T′,，h′）,。

　　（10）將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.