一種自底向上的最大頻繁項集挖掘方法

趙 陽，吳廖丹

(江南計算技術研究所，江蘇 無錫 214083)

一種自底向上的最大頻繁項集挖掘方法

趙 陽，吳廖丹

(江南計算技術研究所，江蘇 無錫 214083)

頻繁項集挖掘是關聯規則挖掘中最關鍵的步驟。最大頻繁項集是一種常用的頻繁項集簡化表示方法。自頂向下的最大頻繁項集挖掘方法在最大頻繁項集維度遠小于頻繁項數時往往會產生過多的候選頻繁項集。已有的自底向上的最大頻繁項集挖掘方法或者需多次遍歷數據庫，或者需遞歸生成條件頻繁模式樹，而預測剪枝策略有進一步提升的空間。為此，提出了基于最小非頻繁項集的最大頻繁項集挖掘算法(BNFIA)，采用基于DFP-tree的存儲結構，通過自底向上的方式挖掘出最小非頻繁項集，利用最小非頻繁項集的性質進行預測剪枝，以縮小搜索空間，再通過邊界頻繁項集快速挖掘出最大頻繁項集。驗證實驗結果表明，提出算法的性能較同類算法有較為明顯的提升。

最大頻繁項集；關聯規則挖掘；FP-tree；最小非頻繁項集；邊界頻繁項集

0 引 言

關聯規則挖掘的概念由Agrawal等于1993年提出[1-3]，用于發現大量數據中項目或項目集之間有趣的關聯或相關關系，同時提出了經典的關聯規則挖掘算法—Apriori。此后眾多學者對Apriori算法進行了改進。但Apriori系列算法需要多次掃描數據集的固有缺陷，使其在處理大型數據集時面臨無法容忍的時間開銷。針對這一問題，Han等[4]提出用FP-tree對數據進行壓縮存儲以及基于FP-tree的頻繁模式挖掘方法—FP-growth。該算法只需掃描數據集兩次，避免了Apriori算法需多次掃描數據集的缺陷。

在關聯規則挖掘過程中，頻繁項集的挖掘是算法主要的開銷，而最大頻繁項集涵蓋了所有的頻繁項集，因此最大頻繁項集挖掘的優化對于提升關聯規則挖掘算法的整體效率至關重要。已有的最大頻繁項集挖掘算法包括：Max-Miner[5]、Pincer-Search[6]、FP-Max[7]、DMFI[8]、DMFIA[9]等。Max-Miner突破了傳統的自底向上的挖掘方法，盡早地進行了剪枝，而Pincer-Search則采用雙向搜索策略，這兩種算法在最大頻繁項集挖掘過程中都產生了過多的候選項集，并且需多次掃描數據集；FP-Max采用FP-tree的數據壓縮表示，避免了多次掃描數據集，但需遞歸地生成條件FP-tree，影響了算法的效率；DMFI將自底向上和自頂向下的搜索策略進行有效合并,在海量數據庫中發現最大頻繁項集和僅需要發現最大頻繁項目集的數據挖掘應用中效果顯著,但該算法仍需多次重復掃描數據庫,計算項目集的支持數；DMFIA采用FP-tree的數據結構及自頂向下的搜索策略，避免了遞歸的生成條件FP-tree，但當最大頻繁項集的維度相比頻繁項的數目較小時，將產生大量的候選頻繁項集，而在大量數據集的實際應用中，最大頻繁項集的維度往往遠小于頻繁項的數目[10]。文獻[11]提出的基于降維的最大頻繁項集挖掘算法(BDRFI)，采用數字頻繁模式樹對FP-tree進行了一定的優化，并從提高FP-tree的生成速度、減少超集檢測的次數等方面進行了改進，性能相比DFMIA有了較大提高，但仍然存在自頂向下算法的固有缺陷。文獻[12]通過獲取低維的非頻繁項集的信息對較高維度的最大候選頻繁項集進行快速降維，但是應該對于哪些搜索層次計算非頻繁項集，以及對于每一層計算哪些非頻繁項集，仍需進一步研究確定。而顯然計算并記錄所有的非頻繁項集是不可行的，浪費了存儲空間，而且增加了超集檢測的開銷。

以上問題表明，針對最大頻繁項集維度較小的數據集，提升算法性能的關鍵在于：避免自頂向下的搜索所產生的大量候選項集；選擇盡可能少的非頻繁項集進行預測剪枝。對此，提出了一種基于最小非頻繁項集的最大頻繁項集挖掘算法(BNFIA)。該算法通過自底向上的方法挖掘最小非頻繁項集，在該過程中用子集檢驗的方法進行預測剪枝，同時記錄中間結果的邊界頻繁項集，并應用邊界頻繁項集快速生成最大頻繁項集。

1 相關知識

設I={i1,i2,…,im}是m個不同項目的集合。給定事務數據庫D,對于項目集X?I,X在D中的支持數是指D中包含X的事務數,記為X.countD；X在D中的支持度是指D中包含X事務的百分比,記為X.supD。

關于頻繁項集、非頻繁項集、最大頻繁項集的定義參見文獻[13]。

定義1：對于項目集X?I,如果X.supD

定義2：對于k-項集X，其所有(k-1)-項子集稱為X的直接子集，其所有(k+1)-項超集稱為X的直接超集。

性質1：任何一個非頻繁項集至少存在一個最小非頻繁項集的子集。

證明：對于任何一個非頻繁k-項集Xk：

(1)若其所有直接子集Xk-1都是頻繁項集，則Xk為最小非頻繁項集；

(2)令k=k-1，對于所有非頻繁項集Xk-1，重復步驟(1)。

由于1-項集是頻繁的，因此一定會找到一個所有直接子集為頻繁項集的最小非頻繁項集為X的子集，證畢。

定義3：對于項目集X?I，如果X.supD≥s，并且存在Y是X的直接超集且Y.supD

性質2：最大頻繁項集一定是邊界頻繁項集。

證明：由最大頻繁項集的定義可知，其所有超集都是非頻繁的，因此最大頻繁項集一定是邊界頻繁項集。

性質3：若X為頻繁項集，則X的直接超集有可能是最小非頻繁項目集。

性質4：如果X是最大頻繁項集，則X的任何真子集都不是最大頻繁項集。

定理1：設降序頻繁項頭表為{1,2,…,k}，若存在t-項頻繁項集X={1,2,…,t}，則以t為后綴生成的不包含X的所有項集必定是非最大頻繁項集[11,14]。

2 DFP-tree與DMFIA

頻繁模式樹(FP-tree)是一種樹的結構，它的每個節點對應一個項，事務數據庫中的某條事務在該樹中的表現為從根到某個子孫節點的路徑集合。由于某些路徑會有重疊，所以FP-tree可以通過共享這些重疊的項來壓縮保存數據。在FP-tree中，每個節點由4個域組成[4]:節點名稱(node-name)、節點計數(node-count)、節點鏈(node-link)(用于指向樹中具有相同node-name的下一個節點)及父節點指針(node-parent)。同時為方便樹的遍歷，FP-tree還包含一個頻繁項頭表Htable，它由兩個域組成:項目名稱(item-name)、指向FP-tree中具有相同item-name的首節點的指針(head of node-link)。

數字頻繁模式樹(Digital Frequent Patten tree，DFP-tree)是對傳統FP-tree的一種改進，其核心思想是“字符串或漢字串的匹配速度要比數字集合慢”，以此來達到提高超級檢驗速度的目的。其改進的主要方法是用頻繁項按照支持度降序排列的序號來代替頻繁項本身，關于DFP-tree的構建方法和詳細介紹參見文獻[11]。

DMFIA采用FP-tree的存儲結構和自頂向下的搜索策略。它采用雙重循環的方式挖掘最大頻繁項集，外層循環是在MFCS非空狀態下進行，內層循環是由自底向上的方式進行處理，若MFCS中項集的支持度大于等于最小支持度閾值，則將該項集加入最大頻繁項集(Maximum Frequent Sets，MFS)。對非頻繁項集，通過循環每次刪除該項集中的一個項來產生新的候選項集，對于新的候選項集，需要判斷在MFS和MFCS中是否存在超集，若不存在則將其加入MFCS中，否則刪除。該算法的主要問題是，當最大頻繁項集的維度相對于頻繁項的數目較小時，會產生大量的最大頻繁候選項集。

3 基于最小非頻繁項集的最大頻繁項集挖掘算法

3.1 算法思想

如前文所述，當最大頻繁項集的維度相對于頻繁項的數目較小時，采用自頂向下的搜索策略往往會產生大量的候選項集。而已有的自底向上的搜索策略有些需要遞歸產生FP-tree，有些沒有充分利用非頻繁項集進行剪枝，或者用于剪枝的非頻繁項集過于冗余。而BNFIA采用DFP-tree的數據壓縮存儲方式，參考DMFIA自頂向下挖掘最大頻繁項集以及運用超集檢測進行剪枝的思想，提出自底向上挖掘最小非頻繁項集并運用子集檢測進行剪枝，同時保存中間結果中的邊界頻繁項集，最后所有的邊界頻繁項集都包含在中間結果的邊界頻繁項集與最小非頻繁項集的直接超集之中。

性質1說明算法使用最簡化的非頻繁項集進行了充分的剪枝，性質2保證了算法的正確性，同時采用了性質3包含的剪枝策略。

3.2 算法流程

算法1：最小非頻繁項集挖掘算法。

輸入：D的數字頻繁模式樹DFP-tree，頻繁項目頭表Header({1,2,…,k})，最小支持度閾值s；

輸出：D的最小非頻繁項目集(MUFS)，邊界頻繁項集(BFS)。

(1)MUFS=?,BUFS=?,BFS={{1,2,…,endItem}}

//{1,2,…,endItem}可能是邊界頻繁項集，將其加入BFS以確保完備性

(2)MFCS={最后一個項目大于endItem的2項集}

//因為已經確定1項集為頻繁項集，故初始化為2項集

(3)While(MFCS!=?) do begin

(4)for(i=k;i>endItem;i--) do begin//定理1

(5)MFCSi={c|c∈MFCS andc的最后一項為i};

(6)MFCS=MFCS-MFCSi;

(7)調用過程ComputeCount(DFP-tree,Header,MFCSi);

//計算項目集在D中的支持數

(8)for allm∈MFCSido begin

(9)ifm.supD

(10)MUFS=MUFS∪{m}

(11)else

(12)ifm.iteritor(1)==1 then

(13)BFS=BFS∪{m}//同前，確保結果的完備性

(14)for(j=m的最后一個項+1;j≤k;j++) do begin//性質3

(15)if {j}+m不是MUFS中某元素的超集 then

(16)MFCS=MFCS∪{{j}+m}

(17)else

(18)BFS=BFS∪{m}

(19)end

(20)end

(21)end

(22)end

算法2:最大頻繁項集的計算。

輸入：D的最小非頻繁項目集，邊界頻繁項集；

輸出：D的最大頻繁項集(MFS)。

(1)MFS=?,CFS=?

(2)for(allm為MUFS中元素的直接子集) do begin

(3)CFS=CFS∪{m}

(4)end

(5)CFS=CFS∪BFS

(6)對CFS中集合元素按照集合大小降序排列

(7)for(allm∈CFS) do begin

(8)ifm不是MFS中某元素的子集 then

(9)MFS=MFS∪m

(10)end

算法ComputeCount參見文獻[9]。

3.3 算法實例

表1所示為一組事務的原始形式、按照頻繁項降序排列以及數字化后的結果。圖1所示為該事務集對應的DFP-tree。endItem=2,MFCS={{1,3},{2,3},{1,4}{2,4}{3,4},{1,5},{2,5},{3,5},{4,5},{1,6},{2,6},{3,6},{4,6},{5,6}};第1輪循環后，MFCS=?,MUFS={{1,2,3},{2,4},{3,4},{3,5},{4,5},{2,6},{3,6},{4,6},{5,6}}，BFS={{1,2},{1,3},{1,4},{1,5},{1,6},{1,2,5}}。

經過算法2得到MFS={{1,3},{1,4},{1,6},{1,2,5}}。

表1 事務數據集實例

圖1 事務數據集實例的數字頻繁模式樹

4 實驗結果及分析

實驗中在8 G RAM，Intel Core i5-2430M CPU 2.40 GHz，Windows7操作系統上用Java實現了DMFIA、FPMax、BNFIA算法。圖2采用的測試數據集為mushroom，包含8 124條記錄，記錄平均長度為23，共有115個蘑菇屬性。

圖2 mushroom數據集上算法的執行時間對比

為了更好地驗證算法在頻繁項數目較大，最大頻繁項維度較小的數據集下的挖掘效率，實驗中隨機生成了具有200個屬性、事務平均長度為15的10 000條事務組成的事務集，在該事務集上采用上述三種算法進行了最大頻繁項集挖掘的對比實驗，結果如圖3所示。

從以上兩種數據集的挖掘中可以看出，當頻繁項數目較多而最大頻繁項集維度較小時，BNFIA的運行時間明顯少于DMFIA和FpMax，并且在支持度較高的情況下執行效率的差別仍然明顯。這是因為隨著最小支持度的提高，最大頻繁項集的維度降低，BNFIA算法采用自底向上的搜索策略以及基于最小非頻繁項集的剪枝策略，相比自頂向下搜索的DMFIA，產生了更少的頻繁項集，而與FpMax相比則不需要遞歸地生成條件頻繁模式樹。

圖3 隨機生成的數據集上算法的執行時間對比

5 結束語

針對最大頻繁項集維度遠小于頻繁項數量的數據的特點，提出了最大頻繁項集挖掘算法—BNFIA。該算法采用DFP-tree的數據存儲結構，避免多次掃描數據庫；采用自底向上的搜索策略，利用最小非頻繁項集作為非頻繁項集信息的最簡化表示，用于搜索剪枝，避免了自頂向下的搜索策略在最大頻繁項集維度較小而頻繁項較多時會產生過多的候選項集的缺陷；同時通過邊界頻繁項集迅速確定最大頻繁項集，而不必記錄所有的頻繁項集，減少了候選項集的數量；與FpMax算法相比該算法無需遞歸地生成條件頻繁模式樹，因此減少了產生的時間開銷。

[1] Imielinski T，Swami A, Agrawal R．Mining association rules between sets of items in large database[C]//Proceedings of 1993 ACM SIGMOD conference on management of data.New York:ACM，1993:207-216．

[2] Han J, Kamber M. Data mining:concepts and techniques[M].Beijing:High Education Press,2001.

[3] Fan M, Meng X F.Data mining:concepts and techniques[M].Beijing:Mechanical Industrial Press,2001.

[4] Han J，Pei J，Yin Y.Mining frequent patterns without candidate generation[C]//Proceedings of the 2000 ACM-SIGMOD international conference on management of data．New York:ACM,2000:1-12．

[5] Bayardo R. Efficiently mining long patterns from databases[C]//Proceedings of the ACM SIGMOD international conference on management of data.New York:ACM,1998:85-93.

[6] Lin D，Kedem Z．Pincer-search:a new algorithm for discovering the maximum frequent set[C]//Proceedings of the 6th European conference on extending database technology．Ber-lin:Springer-Verlag，1998:105-119．

[7] Grahne G，Zhu J．High performance mining of maximal frequent itemset[EB/OL]．[2014-07-06]．http://www．docin．com/p-773109811．html．

[8] 路松峰，盧正鼎.快速開采最大頻繁項目集[J].軟件學報，2001，12(2)：293-297.

[9] 宋余慶，朱玉全，孫志揮，等．基于FP-tree的最大頻繁項目集挖掘及更新算法[J]．軟件學報，2003，14(9):1586-1592．

[10] 吉根林，楊 明，宋余慶，等．最大頻繁項目集的快速更新[J]．計算機學報，2005，28(1):128-135．

[11] 錢雪忠，惠 亮．關聯規則中基于降維的最大頻繁模式挖掘算法[J]．計算機應用，2011，31(5):1339-1344．

[12] 楊鵬坤，彭 慧，周曉鋒，等．改進的基于頻繁模式樹的最大頻繁項集挖掘算法—FP-MFIA[J].計算機應用，2015，35(3):775-778.

[13] Tan Pangning.數據挖掘導論:英文[M].北京：人民郵電出版社,2006.

[14] 秦亮曦，史忠植．SFP-Max—基于排序FP-樹的最大頻繁模式挖掘算法[J]．計算機研究與發展，2005，42(2):217-223．

A Bottom-up Method for Mining Maximum Frequent Itemsets

ZHAO Yang，WU Liao-dan

(Jiangnan Institute of Computer Technology,Wuxi 214083,China)

Mining frequent itemsets is the most critical step in mining association rules.Maximum frequent itemsets is a common compressed representation of frequent itemsets.In mining maximum frequent itemsets,the top-down methods would produce lots of candidate itemsets when the dimensions of maximum frequent itemsets is smaller than the number of frequent itemsets.The existing bottom-up methods need either traversal in database many times or building FP-tree recursively,and the prediction pruning strategies have further room for improvement.The algorithm of discovering maximum frequent itemsets based on minimum non-frequent itemsets named BNFIA has been proposed,which uses storage structure based on FP-tree and digs out the minimum non-frequent itemsets through a bottom-up approach first,then prunes with the minimum non-frequent itemsets to narrow search space for acquiring the maximum frequent itemsets fast through boundary frequent itemsets.Experimental results show that the proposed algorithm has performed better than the algorithm with same type.

maximum frequent itemsets;association rules mining;FP-tree;minimum non-frequent itemsets;boundary frequent itemsets

2016-09-09

2016-12-14 網絡出版時間：2017-06-05

國家科技重點專項“核高基”(2015ZX01040-201)

趙 陽(1991-)，男，碩士研究生,研究方向為數據挖掘、文本分析及可視化。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170605.1511.082.html

TP311

A

1673-629X(2017)08-0057-04

10.3969/j.issn.1673-629X.2017.08.012