壓縮FP－Tree的改進搜索算法

吳 倩，羅健旭

（華東理工大學 信息學院，上海200237）

0 引 言

通過算法輸出頻繁項集是關聯規則挖掘的核心步驟［1］。頻繁項集挖掘大致可以分為兩類：一類是基于候選項集產生－檢驗的Apriori類算法，如IAA［2］，RAAT［3］，IApriori［4］，這類算法從經典算法Apriori上演變而來，算法流程簡單且易于理解，在候選項集得到約減時，算法效率會得到很大提高，但是算法需要多次掃描數據庫以統計項集支持度，在數據庫較大時，處理效率很低，在I／O 上消耗時間很多［5］；另一類算法是基于樹形結構的模式增長類算法，如FP－Growth［6］、COFI－Tree［7］、CT－PRO［8］等，它們在挖掘過程中無候選頻繁項集產生，且均基于分而治之的策略，對基于主樹建立的子樹進行挖掘，這類算法在數據庫巨大時有效壓縮了數據中的重要信息，使得搜索效率較Apriori類算法得到很大提高［9］。

本文結合兩類算法的優點，采用模式增長類算法緊湊的樹形數據結構，第一步，遍歷原始數據庫，找到滿足最小支持數的所有頻繁1項集，構建壓縮頻繁模式樹 （CFPTree）；第二步，基于分而治之的策略，分別建立了局部壓縮頻繁模式樹LocalCFP－Tree；第三步，利用Apriori算法的產生候選項集，自底向上遍歷LocalCFP－Tree來統計其支持數，從而得到全部頻繁模式。改進算法解決了Apriori算法因多次掃描數據庫而耗時長的問題，也避免了模式增長類算法因大量遞歸調用出現內存費用大的現象。在數據集T10I4D100K、Mushroom 和Accidents上進行測試，測試結果表明，該MCFP－Tree算法頻繁項集的挖掘效率明顯優于Apriori算法和FP－Growth算法。

1 頻繁項集的概念及相關理論

設I＝｛i1，i2，…，in｝是n個項目的全集，D 是事務數據庫，事務T是I的子集，如：T＝｛i1，i2，…，im｝，此時T為m項集。每個事務T 都對應唯一的事務標識符TID。設有事務X，Y，有XI，YI，且X ∩Y ＝，則形如XY 的蘊含式就是一條關聯規則，其中X，Y 分別為規則的前項集和后項集。如果D 中有a%的事務既包含X 又包含Y，那么則稱規則的支持度為 a%， 對應的計算表達式為Support（XY）＝P（X ∪Y），即XY 同時出現的概率。

定義1 項集的支持度［10］為項集在數據庫中出現概率，一般由人為設定，本文中支持度取值范圍1%～90%。項集的支持數為項集在數據庫中出現次數

定義2 給定最小支持數閾值MinSup，如果項集的支持數不小于該閾值，則該項集為頻繁項集。如果頻繁項集含有k個元素，則稱為頻繁k項集。

定理1 （頻繁項集的反單調性［11］）如果一個項集的支持度小于最小支持度，則其是一個非頻繁的項集，那么它的任何超集均為非頻繁項集。反之，如果一個項集是頻繁的，那么它的任意非空子集均為頻繁項集。

Apriori算法核心：Apriori算法可分為兩步：連接和剪枝。任取兩個頻繁k 項集，將其中各項按字典順序排列，如p＝｛ti1，ti2，…，tik｝，q＝｛tj1，tj2，…，tjk｝，當滿足ti1＝tj1，ti2＝tj2…，tik－1＝tjk－1，且tik≠tjk時，連接p，q產生的候選k＋1項候選項集為｛ti1，ti2，…，tik，tjk｝。剪枝則是利用了頻繁項集的反單調性 （定理2），設有候選k＋1項集包含任意非頻繁項或項集，則可直接判定其為非頻繁項集，否則需要對數據庫遍歷進行支持數的統計，進一步驗證其是否頻繁。

CFP－Tree的構建：在CFP－Tree樹中，每個節點由4部分組成：節點序號node－id、節點名字node－name、節點鏈node－sibling、計數數組［11］。其中計數數組中每個元素值均對應表示某一個項集的出現次數，例如C ＝｛c1，c2，…，ck｝是某個節點對應的計數數組，ci則表示全局頻繁項目頭表 （GlobalItemTable）中第i項到當前節點序號項的項集出現的次數。若當前節點序號為3，其計數數組C 為 ｛2，1，0｝，C 中第1項表示序號為1的節點到序號為3的節點的項集 ｛1，2，3｝在數據庫中出現的次數為2次，C 中第2項表示項集 ｛2，3｝的出現次數為1次，C 中第3項表示項集｛3｝出現的次數為0次。

GlobalItemTable也由4部分組成：節點名字、節點序號、節點數目和節點指針。節點序號為從1 開始的整數，相當于GlobalItemTable中各節點名字的事務標志符；節點指針是從GlobalItemTable中每一項分別指向GlobalCFPTree中對應的同序號節點，該節點通過節點鏈指向下一個具有相同節點序號的節點。CFP－Tree 的構造算法ConstructCFP－Tree如下：

輸入：數據庫D，最小支持數MinSup

輸出：GlobalCFP－Tree

（1）掃描數據庫D，統計所有項出現的次數，將其與MinSup進行比較，將小于MinSup的項全部去除，剩余的頻繁一次項按頻次降序排列，依次對其添加序號，從1開始遞增，形成GlobalItemTable。

（2）掃描數據庫D，將D 中不屬于GlobalItemTable的項去除，D 中保留下的均是頻繁一次項，形成的新數據庫叫D′。

（3）根據GlobalItemTable建立最左枝樹。如從GlobalItemTable的第1項開始，該項指針指向一個新的節點，節點序號為該項在表中的序號1，節點名為該項在表中對應的名字，新節點鏈連接為空，計數數組長度為當前序號的大小，計數數組內元素全部置0。

（4）將D′中的數據按條讀取，設第一條事務數據為｛a，b，c｝，首先將各數據項變換為GlobalItemTable中對應的序號，如 ｛1，3，2｝，再對其按大小進行升序排列，得到一條對應的數據項集 ｛1，2，3｝，叫mappedTrans，再調用第 （5）步中函數InsertToCFPTree，將mappedTrans插入CFP－Tree中。

（5）函數InsertToCFPTree。首先令FirstItem 為mappedTrans中第1 項，當前起始節點currNode 為GlobalItemTable中第FirstItem 個的項指針指向的節點。對于mappedTrans里每個元素i，如果currNode已經有序號為i的子節點，則將該節點計數數組的第FirstItem 項加1，否則創建一個序號為i的新節點，新節點的計數數組長度等于其父節點的計數數組長度，令該新節點計數數組的第FirstItem 項為1。

2 MCFP－Tree的提出

MCFP－Tree主要基于CFP－Tree緊湊的數據結構，改進了頻繁項集的搜索方法，打破了候選項集生成－檢驗方法在含有較短頻繁模式的大數據庫下處理效率低下的劣勢，使得算法具有更全面的適用性。

輸入：數據庫D 的CFP－Tree，CFPTreeD；全局頻繁模式項目頭表，GlobalItemTable；最小支持數閾值，Min－Sup；只包含頻繁一項集的數據庫，D’。

輸出：D 中滿足最小支持數的所有頻繁模式FS。

中間變量：非頻繁項集，NFS；候選頻繁項集，CFS；局部頻繁項目頭表LocalItemTable中所有項對應的序號集合，LocalIdTable。

挖掘部分主程序：

（1）Procedure Mining

（2） Clear CFS

（3） For each frequent itemi∈ reversedGlobalItemTable

（4） Clear NFS

（5） ConstructLocalItemTable（i）

（6） If the size of LocalItemTable isnot 0

（7） Retraverse CFPTreeDto record the count of each item appeared with i

（8） Construct the LocalItemTable（i）

（9） Construct LeftMostBranch （i）

（10） Construct LocalCFP－Tree（i）

（11） MineFrequentItems（i）；

（12） Print all sets in FS

（13） End if

（14） End for

（15）End

算法從GlobalItemTable表中的最不頻繁項集開始逆序遍歷，在當前項基礎上重新掃描數據庫D’，統計當前項基礎上各項的出現頻次，尋找當前項基礎上的頻繁項，重新給他們賦予新的序號，從1開始，逐個遞增，形成LocalItemTable，類比GlobalCFP－Tree的構造方法構造Local－CFP－Tree。在LocalCFP－Tree的基礎上采用改進算法進行搜索頻繁項集。

（1）Procedure MineFrequentItems（i）

（2） Clear CFS

（3） iterNum＝1； ／／the number of iteration

（4） For each node j∈LocalItemTable

（5） Attach the name of i and j into FS

（6） Attach the node－id j into LocalIdTable

（7） End for

（8） Sort the LocalIdTable in ascending order

（9） Scan the LocalIdTable to create all combination of two different node－id into CFS

（10） For each itemj∈CFS

（11） SearchforCount（j）；

（12） If the count＞＝MinSup

（13） Attach j into FS

（14） Else

（15） Attach j into NFS

（16） End if

（17） End for

（18） If the size of CFS isnot 0or 1

（19） Increment the count of iterNum

（20） Combination （CFS，i，iterNum）

（21） End if

（22）End

要搜索基于序號為i的頻繁項的頻繁項集，可以挖掘基于該項建立的LocalCFP－Tree，這棵子樹中儲存了所有滿足MinSup的頻繁項集。LocalItemTable中是基于該項的所有頻繁1次項，若這些項的數目不大于1，則直接輸出這些項與序號為i的項的組合，它們為輸出頻繁2次項；否則，采用Apriori算法候選項集的生成方法，按照候選項集的連接條件，調用Combination 函數，生成候選多項集，再調用SearchforCount函數計算候選項集的出現頻數。

（1） Procedure SearchforCount（j）

（2） Count＝0；

（3） FirstItem＝the first of j

（4） LastItem＝the last of j

（5） Find the node k whose id is LastItem in LocalItemTable

（6） While the sibling of K is null

（7） K is the sibling of itself

（8） If the sum of countArray is not 0

（9） Attach all the parent of k to local root into parentList

（10） End if

（11） If parentList contains j

（12） If （the size of countArray of node K ＜FirstItem）

（13） Add up the values in the countArray of K

（14） Else

（15） Add up the value from countArray ［0］to countArray［FirstItem－1］

（16） End if

（17） End if

（18） End while

（19） End

（20） Procedure Combination（CFS，i，iterNum）

（21） Create new candidate frequent itemset newCFS from CFS according to Apriori’s candidate generation rule

（22） Clear CFS

（23） For each itemj∈newCFS

（24） If j not in the NFS

（25） If j＞＝MinSup

（26） Attach j into FS

（27） Attach j into CFS

（28） Else

（29） Attach j into NFS

（30） End if

（31） End if

（32） End for

（33） If the Size of CFS is not 0

（34） Increment the count of iterNum

（35） Combination （CFS，i，iterNum）

（36） End if

（37） End

SearchforCount函數的作用是計算候選項集j的支持數C。首先需要明確j的首元m 和尾元n，然后找到基于當前節點的LocalItemTable指向的最左枝，求得最左枝上序號為n的節點的計數數組中第m 項到n項的和c1。然后需要考慮節點n的節點鏈指向是否為空，如果為空則返回的C為c1；否則，該節點鏈指向的節點變為當前節點n，向上找到節點n的父節點鏈，并判斷是否包含j，如果不包含則繼續判斷當前節點n的節點鏈指向是否為空，直到當前節點鏈指向的節點為空再跳出SearchforCount函數；否則c1要加上當前節點n父節點鏈中j出現次數c2。最后將所有的c1＋c2＋…的和返回給C，作為當前候選項集的出現次數。

為了方便理解，當搜索所有基于序號為i的頻繁項的頻繁項集結束后，輸出的所有頻繁項或項集均統一用節點名字或名字的組合表示。如要輸出序號為5名字為x的頻繁項的一個頻繁項集 ｛1，2，3｝，項集支持數為 ｛10｝，該項集對應的節點名字為 ｛a，c，d｝，支持數也應為 ｛10｝，則輸出結果應為 ｛a，c，d，x｝，支持數為 ｛10｝。下面我們給出一個事務數據庫例子，用本文提出的改進算法MCFPTree進行挖掘。

例1：設事務數據庫D 如果所示，最小支持度為40%（最小支持數為2），圖1 為建立GlobalCFP－Tree之前的數據處理工作，數據庫D 的GlobalCFP－Tree如圖2所示。

圖1 事務數據庫處理流程

圖2 全局壓縮頻繁模式樹GlobalCFP－Tree

樣例數據庫 （圖1 （a）），首先遍歷數據庫，統計所有項出現的次數，找到頻繁1 次項，將其按頻次降序排列，每一個頻繁項均對應一個Id號，從1開始，逐個加1，形成GlobalItemTable （圖1 （b）），按照函數ConstructCFPTree建造最左枝樹，根據該表重新掃描數據庫，剔除非頻繁項 （圖1 （c）），并將所有頻繁項一一對應到GlobalItemTable表中Id值，逐行升序排列 （圖1 （d）），插入到GlobalCFP－Tree中。

從GlobalItemTable中最不頻繁項 （序號為5的項）開始，該項由指針指向的節點計數數組為空，則繼續沿節點鏈指向下一個同序號節點，找到第一條以序號為5節點為結尾的項集：｛1，2，4｝，沿節點鏈指向下一個節點，找到第二個項集： ｛1，3，4｝，此時該節點無下一個同序號節點，則以序號為5節點為結尾的項搜索結束。將找到的數據項集組合作為一個新的數據庫newD，調用ConstructCFP－Tree方法建造基于序號為5 的節點的LocalItemTable和LocalCFP－Tree。遍歷newD，得知項 ｛1 （4），2 （3），3 （1），4 （5）｝的支持數數分別為 ｛2，1，1，2｝，括號內為項的名字，和MinSup對比得知，只有名字為4，5的節點是基于序號為5節點的頻繁項集，將其按支持數大小降序排列，并給每一項重新賦Id 值，形成新的LocalItemTable，根據該表重新調用函數ConstructCFP－Tree建立新的LocalCFP－Tree，如圖3 （a）所示。

搜索以序號為5 的頻繁項為基礎建立的LocalCFPTree時，已知LocalItemTable中各項均為在其基礎上的頻繁1項集：｛｛1｝，｛2｝｝，支持數分別為 ｛2，2｝。則它們分別與該頻繁項組合而成的輸出頻繁二項集名字為 ｛｛7，4｝，｛7，5｝｝，支持數為這兩個節點在LocalItemTable里面的數量 ｛2，2｝。由于此時頻繁1項集的個數大于1，可以調用Combination函數連接產生候選2項集 ｛｛1，2｝｝，調用搜索函數SearchforCount，我們可知其支持數為 ｛2｝，大于最小支持數閾值，所以這個候選項集是頻繁2 項集，輸出完整的頻繁3項集的名字為 ｛｛7，4，5｝｝，支持數為 ｛2｝。

MCFP－Tree采用Apriori算法的候選項集產生機制，產生候選項集后直接搜索各個局部頻繁模式樹，比遍歷數據庫計數節省時間，效率得到顯著提升。與FP－Growth相比，CFP－Tree數據結構更為緊湊，節點數目最多的時候可以減少為FP－Growth的一半，大大節約了系統內存的占用，此外搜索過程有效的減少對樹的遍歷，可以更高效的計算出候選項集的出現頻次。

3 算法實現與比較

本文用java語言在內存2 G，CPU 為Intel（R）Core（TM）2Duo，32位的Windows7操作系統上實現了Apriori、FP－Growth、MCFP－Tree算法，使用了1組IBM 人工數據集T10I4D100K，2組經典測試數據集Mushroom、Accidents。

表1中，Mushroom 是從UCI機器學習數據庫（http：／／archive.ics.uci.edu／ml／datasets.html）下載，Accidents、T10I4D100K數據集從頻繁項集挖掘數據庫（http：／／fimi.ua.ac.be／data／）下載。

圖3 基于GlobalItemTable中頻繁項建立的LocalCFP－Tree

表1 數據集

由于頻繁項集數量在支持度范圍30%～90%之間變化很大 （數量從幾個至兩千多個），為便于分析，我們統一對頻繁項集的維數分布圖在不同支持度時分別取以10為底的對數 （如圖5、圖8所示），縮小數量的變化范圍。

Mushroom 最大事務長為23，所以很可能出現較多長頻繁模式 （頻繁模式的維數大于10）。由圖4可知，MCFPTree網格區域所占面積遠比同支持度時其它兩種算法的面積小，結合圖5，在支持度范圍內，頻繁模式的長度均較短（以長度不大于5的頻繁模式為主），此時，改進算法效率遠高于兩種經典算法。在支持度為40%時，改進算法運行效率較Apriori算法提高了75.2%，較FP－Growth算法提高了76.1%。明顯可以看出在處理含有較多短小頻繁項集時，改進算法擁有顯著的優越性。

圖4 Mushroom 數據集的算法性能對比

圖5 Mushroom 數據集頻繁集的數量

下面兩個數據集數據量分別為100000和340183，屬于數據量很大的數據庫，而且挖掘頻繁項集的耗時在支持度范圍內跨度較 Mushroom 更大，所以我們統一對T10I4D100K 和Accidents的性能對比圖的縱坐標取log以10為底的對數，壓縮時間的變化范圍，如圖6、圖7所示。對Accidents的頻繁項集維數分布圖的縱坐標也取以10為底的log函數，如圖8所示。

圖6 T10I4D100K 數據集的算法性能對比

圖8 Accidents數據集頻繁項集的數量

T10I4D100K 是個數據量為100000的人工數據庫，但在支持度大于5%時，它的頻繁項集很少，所以我們取挖掘的范圍為1%～5%。在支持度低于5%的時候，頻繁項集的數目增加很快，還是以短小頻繁模式為主，但是由于數據庫變大，搜索時間相應就會變長，Apriori的運行效率顯然明顯低于其它兩種算法。當最小支持度為3% 時，MCFP－Tree算法效率比Apriori算法提高了94%，比FPGrowth算法提高了40%，當支持度降為1%時，涌現較多長頻繁模式，MCFP－Tree算法所占面積略小于FP－Growth算法，效率只比FP－Growth算法提高了3.6%。

結合表1和圖8發現，Accidents的平均事務長度和頻繁模式的長度都比Mushroom 更長，且此時數據庫變得很大 （約為Mushroom 的66 倍），但是頻繁模式還是以維度在10之內的頻繁項集為主，證明Accidents數據庫本身就是較為稀疏的數據庫，此時改進算法所占面積比兩種經典算法所占面積都小，運行效率也更高。在支持度范圍內，改進算法比Apriori算法平均提高91%左右，比FP－Growth算法提高95%左右，由此可以看出MCFP－Tree更適合挖掘數據量大的稀疏數據庫。

4 結束語

本文提出的MCFP－Tree算法融合了CFP－Tree的數據結構和Apriori算法的候選項集產生方法，可以顯著提高頻繁項集的挖掘效率，尤其是在含有較多較短的頻繁模式的挖掘過程中 （大部分頻繁模式的長度不超過10），可以取得更好的挖掘效率。但在有較多較長頻繁模式時運行效率和FP－Growth接近，所以后續研究可以利用已經在Apriori類算法上發展起來的雙向搜索策略分別對LocalCFP－Tree挖掘，提高算法的搜索效率，此外考慮到只挖掘GlobalCFPTree主樹內存消耗會更少，后續可以針對主樹來設計更加靈活的搜索算法，提高挖掘效率。

［1］YANG Zeming.Association rules incremental updating method based on cloud computing ［J］.Computer Engineering and Design，2014，35 （2）：504－508 （in Chinese）. ［楊澤明.云計算模型中關聯規則增量更新方法 ［J］.計算機工程與設計，2014，35 （2）：504－508.］

［2］Wu H，Lu ZG，Pan L，et al.An improved apriori－based algorithm for association rules mining ［C］／／6th International Conference on Fuzzy Systems and Knowledge Discovery，2009：51－55.

［3］Yu WJ，Wang XC，Wang FY，et al.The research of improved apriori algorithm for mining association rules ［C］／／11th IEEE International Conference on Communication Technology Proceedings，2008：513－516.

［4］Li XC，Teng SH.The research on improvement of apriori algorithm based on mining frequent itemsets ［J］.Journal of Jiangxi Normal University （Natural Science Edition），2011，35 （5）：498－502.

［5］Gupta B，Garg D.FP－tree based algorithms analysis：FPGrowth，COFI－Tree and CT－PRO ［J］.International Journal on Computer Science and Engineering，2011，3 （7）：2691－2699.

［6］ZHOU Lijuan，WANG Xiang.Research on association rules algorithms based on cloud environment ［J］.Computer Engineering and Design，2014，35 （2）：499－503 （in Chinese）.［周麗娟，王翔.云環境下關聯規則算法的研究 ［J］.計算機工程與設計，2014，35 （2）：499－503.］

［7］XIAO Jihai，CUI Xiaohong，CHEN Junjie.Mining N－most interesting itemsets algorithm based on COFI－Tree［J］.Computer Technology and Development，2012，22 （3）：99－102 （in Chinese）.［肖繼海，崔曉紅，陳俊杰.基于COFI－Tree的N－最有興趣項目集挖掘算法 ［J］.計算機技術與發展，2012，35（2）：99－102.］

［8］Yudho GS，Raj PG.CT－PRO：A bottom－up non recursive frequent itemset mining algorithm using compressed FP－tree data structure［C］／／Proceedings of the IEEE ICDM Workshop on Frequent Itemset Mining Implementations，2004：212－223.

［9］Shen B.Research on the technology of association rules［M］.Hangzhou：Zhejiang University Press，2012：5－7.

［10］Liu B，Hsu W，Chen S，et al.Analyzing the subjective interestingness of association rules ［J］.IEEE Intelligent Systems and Their Applications，2000，15 （5）：47－55.

［11］Luo XW，Wang WQ.Improved algorithms research for association rule based on matrix ［C］／／International Conference on Intelligent Computing and Informatics，2010：415－429.