一種最大頻繁模式的快速挖掘算法

摘 要：挖掘最大頻繁模式是多種數據挖掘應用中的關鍵問題。提出一種挖掘最大頻繁模式的快速算法，該算法利用前綴樹壓縮存放數據，并通過調整前綴樹中節點信息和節點鏈直接在前綴樹上采用深度優先的策略進行挖掘，而不需要創建條件模式樹，從而大大提高了挖掘效率。

關鍵詞：最大頻繁模式; FPTree; 前綴樹; 數據挖掘

中圖法分類號：TP311．12 文獻標識碼：A 文章編號：1001-3695(2006)10-0086-03

Fast Algorithm for Mining Maximum Frequent Patterns

WANG Yunpeng1，2， HU Xiulin1， RUAN Youlin1，3

(1.Dept. of Eletronics Information， Huazhong University of Science Technology， Wuhan Hubei 430074， China; 2.Information Center of Jianghan Oilfield， China Petrochemical Corporation， Qianjiang Hubei 433124， China; 3.College of Information Engineering， Wuhan University of Technology， Wuhan Hubei 430070， China)

Abstract:Mining maximum frequent patterns is a key problem in data mining research. In this paper， a fast algorithm DMFP based on Prefix Tree for mining maximum frequent patterns is proposed. Prefix Tree stores information in a highly compact form. DMFP mines frequent patterns in depthfirst order and directly in Prefix Tree by adjusting node information and node links without creating conditional pattern tree. Thus， it improves performance greatly.

Key words:Maximum Frequent Pattern; FPTree; PrefixTree; Data Mining

頻繁模式的挖掘是關聯規則、序列分析等許多重要數據挖掘任務的關鍵步驟。在眾多頻繁模式的挖掘算法[1~8]中，以Agrawal等人提出的Apriori算法[1]最為著名。該類算法采用候選項集生成—篩選方法，必須耗費大量時間處理規模巨大的候選項集，多次掃描數據庫對候選項集進行篩選。隨后Han等人提出了FPTree和一種基于模式增長的挖掘算法FPGrowth[4]，該算法無需生成候選項集、只需兩次掃描數據庫，挖掘效率明顯提高。然而，FPTree結構動態維護復雜，在挖掘過程中需要遞歸地創建大量的條件模式樹。特別是在支持度閾值較小或存在長模式時，即使對于不太大的數據，也會產生數以萬計的條件FPTree。動態地創建數以萬計的條件FPTree將消耗大量的時間和空間。因而FPGrowth算法的時空效率不高。

由于最大頻繁模式已經隱含了所有頻繁模式，所以可把發現頻繁模式的問題轉換為發現最大頻繁模式的問題。另外，某些數據挖掘應用僅需發現最大頻繁模式，而不必發現所有的頻繁模式，因而發現最大頻繁模式對數據挖掘具有重大意義。目前已經提出的可用于發現最大頻繁模式的算法有MaxMiner[8]，PincerSearch[9]及DMFI[10]等。這些算法均是基于Apriori算法或FPTree，因而不可避免地存在上述缺陷。

為此，本文提出一種基于前綴樹的挖掘最大頻繁模式的新算法DMFP。該算法通過調整前綴樹中相關節點信息和節點鏈直接在前綴樹上采用深度優先的策略挖掘，而不需要創建大量條件模式樹，從而大大提高了挖掘效率。

1 相關概念

1．1 最大頻繁模式

設I={i1，i2，…，im}是m個不同項目的集合。給定事務數據庫DB，對于項目集XI， X在DB中的支持數是指DB中包含X的事務數，記為X.count。X在DB中的支持度是指DB中包含X事務的百分比，記為X.sup。如果X的支持度不小于用戶給定的最小支持度閾值minsup，則稱X為DB中的頻繁項目集。如果X包含k個項目，那么又稱為頻繁k項目集。項目集中項目的個數稱為項目集的維數或長度，頻繁l項目集簡稱頻繁項目。

性質1 如果X是頻繁項目集，那么X的任何子集都是頻繁項目集。

性質2 如果X是非頻繁項目集，那么X的任何超集都是非頻繁項目集。

如果頻繁項目集F的所有超集都是非頻繁項目集，那么稱F為最大頻繁項目集或最大頻繁模式，所有F的集合稱為最大頻繁項目集合，記作MFS(Maximum Frequent Sets)。顯然，任何頻繁模式都是最大頻繁模式的子集。所以，發現所有頻繁模式的問題可以轉換為發現所有最大頻繁模式的問題。

1．2 前綴樹PrefixTree

前綴樹PrefixTree和頻繁模式樹FPTree一樣記錄的都是DB中每個事務Trans的頻繁項。頻繁模式樹FPTree中事務中的項按支持度計數降序排列，而前綴樹PrefixTree中出現的項組成一個偏序集（），事務中的項嚴格按某種順序排列。因此，兩者只是記錄項的順序不同。在PrefixTree中，每個節點由四個域組成:節點名稱itemname、節點計數count、節點鏈nodelink和父節點指針parent。圖1所示的是有四個頻繁項的完全前綴樹，表示四個頻繁項所構成的所有可能模式。從根節點Root到其他節點表示每種模式，如1234表示長度為4的模式。每個子樹表示以該子樹的根為前綴的所有模式，如1prefix表示包含1的所有模式，2prefix表示包含2但不包含1的所有模式，依次類推。下面，ij和 ik分別用來表示單個前綴項，而α，β和γ表示通用前綴項。

性質3 事務數據庫DB的每次事務記錄在前綴樹PrefixTree的某條路徑中。

性質4 前綴樹PrefixTree中每條路徑的計數表示事務數據庫DB中相同事務的個數。

性質5 前綴樹PrefixTree的深度為相應的事務數據庫DB中事務的最大長度。

性質6 給定一個滿足偏序關系（）的項集I={i1，i2，…，im}，如果α.ijprefix包含的模式是頻繁的，則α.ij.ikprefix(ij≤ik)包含的模式才可能是頻繁的。如果α.ijprefix包含的模式不頻繁，則α.ij.ikprefix包含的模式一定不頻繁。

性質7 如果α.ijprefix包含的模式是頻繁的，對于所有ik有α.ij.ikprefix(ij≤ik)包含的模式不頻繁，則α.ij是最大頻繁模式。

性質6和性質7提供了一個很好的挖掘最大頻繁模式的策略：如果某節點的計數小于支持度閾值minsup，即該項不頻繁，則以該節點為根的整個子樹不需考慮。如果該項頻繁，而且該節點的所有子節點都不頻繁，則該節點的前綴就是一個最大頻繁模式。因此，利用該性質可以顯著地縮小搜索空間，有效地避免了組合爆炸，極大提高挖掘效率。

定義1 當滿足ij≤ik時，如果ij.αprefix包含在ik.αprefix中，就記作ij.αprefixik.αprefix。

定義2 αprefix的覆蓋是指包含αprefix的所有βprefix，即αprefixβprefix。

如b.c.dprefix的覆蓋包括b.c.dprefix和a.b.c.dprefix;c.dprefix的覆蓋包括c.dprefix，b.c.dprefix，a.c.dprefix和a.b.c.dprefix。

性質8 挖掘αprefix包含的頻繁模式就轉換為挖掘αprefix的覆蓋包含的頻繁模式。

因此，要想挖掘αprefix包含的頻繁模式，只需得到αprefix的覆蓋即可。如要確定c.dprefix包含的模式是否頻繁只需對以上四個子樹進行挖掘即可。由于相同模式可能分布在不同子樹中，當分別對每個子樹進行挖掘時，無法利用性質6和性質7判斷其是否頻繁，必須遞歸構造其條件模式樹才能判斷，就如同FPtree和FPGrowth算法。但如果把這四個子樹合并成一個樹（αprefix的覆蓋），就不需要構造條件模式樹，基于性質6和性質7采用深度優先的策略即可判斷該模式是否頻繁。

2 最大頻繁模式挖掘算法

通常基于FPTree的挖掘算法的主要步驟分為以下三個：

（1）掃描DB一遍得到各項目的頻度，根據最小支持度minsup得到頻繁項集；對頻繁項目按其頻度由大到小排列成表L，形成頭表；

（2）再次掃描DB，對每一條交易中的所有頻繁項目，按表L中的次序插入到FPTree中；

（3）調用FP_Growth算法對FPTree進行挖掘。

在FPTree中，相同模式可能存在不同的子樹中；當對某個子樹進行挖掘時，無法判斷該模式是否頻繁，必須對出現該模式的所有子樹進行挖掘，構造其條件模式樹。由于本算法采用前綴樹PrefixTree存放事務，并把不同子樹中的相同模式并入一個子樹中，故而可以直接判斷該模式是否頻繁而無須構造其條件模式樹。因此，本算法在性質6和性質7的基礎上由頂向下采用深度優先搜索進行挖掘。因此，挖掘算法DMFP也分為以下三個步驟：

(1)掃描DB一遍得到各項目的頻度，根據最小支持度minsup得到頻繁項集；對頻繁項目按其字典順序排列成表L，形成頭表。

(2)再次掃描DB，對每一條交易中的所有頻繁項目，按表L中的次序插入到前綴樹PrefixTree中。

（3）基于前綴樹PrefixTree采用深度優先搜索進行挖掘。

2．1 前綴樹PrefixTree的構造算法

輸入：事務數據庫DB

輸出：前綴樹PrefixTree和項集合F及其支持數

前綴樹PrefixTree的構造算法如下：

（1）創建前綴樹PrefixTree的根節點，以“Root”標記它。掃描事務數據庫DB一次，構造前綴樹PrefixTree。

（2）對于DB中的每個事務Trans進行如下處理:

事務Trans中的頻繁項按字典順序排列。設排序后的項列表為[p|P]，其中p是第l個項目，而P是剩余項目的列表。

調用 insert_tree([p|P]，T)。如果T有子女N使得N.nodename=p.itemname，則N的計數應增加1;否則創建一個新節點N，將其名稱nodename、計數nodecount應分別設置為p和l，由父節點指針nodeparent鏈接到它的父節點T，并通過節點鏈nodelink將其鏈接到具有相同名稱nodename的節點。如果P非空，遞歸調用insert_tree(P，N)。

2．2 基于前綴樹的最大頻繁模式挖掘算法

Algorithm DMFP(α，minsup)

Input:

α is the prefix path of αprefix tree;

minsup is the minimum support threshold;

Description:

1: for all children croot of α do

2:sroot=the right sibling of whose item equal to subroot.item;

3: Merge(croot， sroot);

4:end for

5: found=1;

6: for all children ai of α do

7:if ai. count≥minsup then

8: if found==1 then found=true;

9: DMFP (α.ai，minsup);

10: end if

11:end for

12:if found==1 then output α and α.count;

DMFP算法直接在PrefixTree上采用深度優先的策略自頂向下進行挖掘。當挖掘αprefix包含的頻繁模式時，根據性質8，要想挖掘αprefix包含的頻繁模式，必須得到αprefix的覆蓋。因此，在挖掘αprefix之前，應把包含各兄弟節點的子樹croot合并到各兄弟節點所在子樹sroot，即得到各兄弟節點的覆蓋srootprefix。歸并完后，分別對αprefix的每個子節點ai進行挖掘；如果ai頻繁，采用相同的策略對α.ai進行挖掘。如果αprefix的每個子節點ai均不頻繁，則αprefix的每個子樹α.aiprefix都不用考慮。根據性質7，α就是一個最大頻繁模式。

3 應用實例

對表1所示的交易數據庫DB，數據項集I={a，b，c，d，e，f，g，h，i，k}，設最小支持度計數為2，則由前綴樹構造算法可得DB的前綴樹，如圖2(a)所示，并有頻繁項集L=[a∶3，c∶3，d∶3，e∶3，g∶2]。當挖掘aprefix時，acprefix子樹應與cprefix子樹合并，adprefix子樹應成為樹根Root的新子樹dprefix，結果如圖2(b)所示。當挖掘acprefix時，acdprefix子樹應與adprefix子樹合并，如圖2(c)所示。同理，當挖掘cprefix時，其cdprefix子樹和dprefix子樹合并，結果如圖2(d)所示。最后可得所有的最大頻繁模式，如表2所示。

4 算法實現與比較

由于DMFI的性能比MaxMiner和PincerSearch都要好，因此我們用VC++6．0在內存256MB，CPU為Pentium Ⅲ 1GHz，操作系統為Windows 2000的機上實現了DMFP算法并與DMFI進行了性能測試。利用http://www.ics.uci.eud/~mlearn/JLsummary.html上提供的蘑菇數據庫（mushroom database）來進行實驗。該數據庫有8 124條記錄，記錄了蘑菇的23種屬性。圖3顯示了在不同的最小支持度下算法的性能比較。由于DMFP算法無須遞歸地創建大量的條件FPTree，僅僅通過調整前綴樹中節點信息和節點鏈直接在PrefixTree上采用深度優先的策略挖掘最大頻繁模式，而不需要創建大量候選項和條件模式樹，因此DMFP算法的執行時間比DMFI算法要少得多，如圖3所示。

5 結束語

挖掘最大頻繁模式是多種數據挖掘應用中的關鍵問題。本文提出了一種快速的基于前綴樹的最大頻繁模式挖掘算法DMFP。該算法通過前綴樹用來壓縮存放數據的相關信息，通過調整前綴樹中節點信息和節點鏈直接在前綴樹上采用深度優先的策略挖掘最大頻繁模式，并舉例說明了算法的執行過程。

參考文獻：

[1]Agrawal R， Srikant R. Fast Algorithm for Mining Association Rules[C]. VLDB’94， 1994.489-499.

[2]Park J S， Chen M S， Yu P S. An Effective Hash Based Algorithm for Mining Association Rules[C]. Proc.of ACM SIGMOD Int. Conf. on Management of Data， 1995.175186.

[3]M Y Chen， J Han， P Yu. Data Mining: An Overview from a Database Perspective[J]. IEEE Transactions on Knowledge and Data Engineering， 1996，8(6):866-883.

[4]J Han， J Pei， Y Yin. Mining Frequent Patterns without Candidate Generation[C]. Dallas: Proc.of ACMSIGMOD， 2000.

[5]Agarwal R， Aggrawal C， VVV Prasad. A Tree Projection Algorithm for Generation of Frequent Itemsets[J]. Journal of Parallel and Distributed Computing， 2000，10(2):427-434.

[6]Huang H， Wu X， Relue R. Association Analysis with One Scan of Databases[C]. Proc.of PacificAsia Conference， PAKDD， 2002.334-340.

[7]Guimei Liu， Hongjun Lu， Yabo Xu， et al. Ascending Frequency Ordered PrefixTree: Efficient Mining of Frequent Patterns[C]. Proc.of the 8th Database Systems for Advanced Applications， 2003.

[8]Bayardo R. Efficiently Mining Long Patterns from Databases[C]. Proceedings of the ACM SIGMOD International Conference on Management of Data， New York: ACM Press， 1998.85-93.

[9]Lin DI， Kedem ZM. PincerSearch: A New Algorithm for Discovering the Maximum Frequent Set[C]. Proceedings of the 6th European Conference on Extending Database Technology， Heidelberg: SpringerVerlag， 1998.105119.

[10]Lu SF， Lu ZD. Fast Mining Maximum Frequents Itemsets[J]. Journal of Software， 2001，12(2):293-297.

作者簡介：

王運鵬(1963-)，男，湖北潛江人，高級工程師，博士研究生，主要研究方向為數據挖掘、網絡管理與測量；胡修林(1945-)，男，河南滑縣人，教授， 博導，主要研究方向為多媒體通信網絡、人工智能；阮幼林（1972-），湖北武漢人，男，副教授，博士，主要研究方向為并行與分布式計算、數據挖掘。

注:本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文