魏 坤 王 芳 黃樹成

（江蘇科技大學計算機學院 鎮(zhèn)江 212001）

1 引言

數(shù)據(jù)挖掘，也稱為數(shù)據(jù)中的知識發(fā)現(xiàn)，用于發(fā)現(xiàn)隱藏在大型數(shù)據(jù)庫中的知識模式［1］。許多數(shù)據(jù)挖掘方法被用來提取有趣的東西，比如從龐大的數(shù)據(jù)中獲取關聯(lián)規(guī)則。關聯(lián)規(guī)則挖掘是搜索給定數(shù)據(jù)集中項之間的關聯(lián)關系，即本質是對頻繁模式的挖掘。頻繁項集挖掘是大多數(shù)數(shù)據(jù)挖掘應用程序中的經(jīng)典問題之一［2］。

提取頻繁項集的算法有很多，兩種主要的算法是Apriori和FP-Growth［3］。Apriori是一種典型的事務數(shù)據(jù)庫頻繁項集挖掘和關聯(lián)規(guī)則發(fā)現(xiàn)的算法，然而，挖掘過程中多次數(shù)據(jù)庫掃描引起大量I/O開銷［4］。FP-Growth是一種基于樹的頻繁項集挖掘算法，它以一種分而治之的方式工作，這種方式可以在很大程度上減小后續(xù)條件FP樹的大小，它僅需對數(shù)據(jù)集進行兩次掃描［5］。FP樹是事務的壓縮表示，然而，并不減少候選項集的潛在組合數(shù)，這是FP增長的瓶頸。此外，由于可能生成非常大的樹，會消耗大量的時間和空間，大型數(shù)據(jù)庫結構并不適合此算法［6］。

為解決上述問題，本篇論文在FP-Growth算法的基礎上提出了一種改進的頻繁模式挖掘算法MGFP-growth。主要改進有兩點：1）采用二維矩陣按列存儲事務信息，只需要掃描事務數(shù)據(jù)庫一次；2）提出了一種分組構建頻繁模式樹的結構，可以快速發(fā)現(xiàn)頻繁模式，同時減少內存消耗。

2 問題陳述

2.1 關聯(lián)規(guī)則

關聯(lián)規(guī)則是X→Y形式的表達式，其中X，Y是項集。它表示項X和項Y之間的關系，關聯(lián)規(guī)則有兩個重要的基本度量［7］：支持度（sup）和置信度（c）；支持度（sup）是包含X和Y中所有項的事務百分比，即sup（X→Y）=P（X∪Y），置信度（conf）定義為包含X的事務中也包含Y的部分，即P（Y|X）=P（X∪Y）/P（X）［8～9］。

2.2 頻繁項集

頻繁的項目集在現(xiàn)實生活數(shù)據(jù)中很常見，例如在超級商店中一起購買的項目集，頻繁出現(xiàn)在交易數(shù)據(jù)集中的一組項目（例如牛奶和咖啡）就是頻繁項集。頻繁項集的定義如下：

令I=｛I1，I2，I3，…，In｝為項目的集合。D是數(shù)據(jù)庫中的一組事務，其中每個事務T是一組項，因此I包含T。對于包含在I中的任何事務A，當且僅A?T時，A才能稱為項目集。項目集A的支持計數(shù)是數(shù)據(jù)庫D中包含A的事務的數(shù)目。如果項目集A的支持計數(shù)大于或等于給定的最小支持度minsup，則A可以稱為頻繁項目集［10～11］。

2.3 FP-growth算法

FP-growth算法在不產(chǎn)生候選項的情況下挖掘出完整的頻繁項集，它將表示頻繁項的數(shù)據(jù)庫壓縮到頻繁模式樹中來保留項之間的關聯(lián)。當挖掘所有頻繁項集時，只需要兩次數(shù)據(jù)集掃描［12］。第一次掃描統(tǒng)計每個項的出現(xiàn)次數(shù)，第二次掃描構造包含原始數(shù)據(jù)集所有頻繁信息的初始FP樹［13］。挖掘數(shù)據(jù)集就變成了挖掘FP樹，F(xiàn)P-gowth算法的挖掘過程如下所示［14～16］。

輸入：事務數(shù)據(jù)庫，最小支持度minsup

輸出：頻繁模式集

方法：

Step1：掃描事務數(shù)據(jù)庫，得到頻繁向的集合和每個項的支持度計數(shù)，并按其支持度降序排序，記為L。

Step2：把數(shù)據(jù)庫中的每個事務的頻繁項按照L的順序重排。并按照重排之后的順序把每個事務的每個頻繁項插入以null為根的FP-tree中。如果插入時頻繁項節(jié)點已經(jīng)存在了，則把該頻繁項節(jié)點支持度加1；如果該節(jié)點不存在，則創(chuàng)建支持度為1的節(jié)點，并把該節(jié)點鏈接到項頭表中。

Step3：調用FP-growth（Tree，null）開始挖掘。偽代碼如下：

為了得到的數(shù)據(jù)更加完整和準確，本研究確立了多個統(tǒng)計對象：浙江省農(nóng)業(yè)廳休閑觀光協(xié)會處得到的“各地區(qū)農(nóng)慶節(jié)慶活動調查”資料；百度首頁搜索的結果，輸入“城市名”+“果名”+節(jié)，如“杭州蜜梨節(jié)”，“浙江省“2012’四季鮮果采摘游系列活動”中以時鮮水果采摘游的形式串成一線的35個優(yōu)秀農(nóng)慶節(jié)慶活動；“最具影響力農(nóng)慶名單”中與果樹觀光采摘相關的節(jié)慶；“浙江省優(yōu)秀農(nóng)慶節(jié)慶名單”中與果樹觀光采摘相關的節(jié)慶。

procedure FP_growth（Tree，α）

ifTree含單個路徑Pthen｛

for路徑P中結點的每個組合（β）

為了更好地說明FP-growth算法的詳細過程，舉例如表1所示。

表1 樣本數(shù)據(jù)

使用表1中的樣本數(shù)據(jù)生成FP-tree，如圖1所示，設置最小支持度閾值minsup=3。

圖1 存放壓縮的頻繁模式信息的FP樹

通過FP-growth算法對圖1中的FP-tree進行挖掘，得到如表2所示頻繁模式集。

表2 通過創(chuàng)建條件（子）模式基挖掘FP樹

3 改進算法

3.1 改進算法思想

為了提高FP-growth算法的挖掘效率，從縮減掃描事務數(shù)據(jù)庫的次數(shù)以及優(yōu)化FP-tree的結構方向改進。首先，棄用項目表頭，用二維矩陣存儲項集的信息。由于項目頭表需要掃描一次數(shù)據(jù)庫才能生成，所以減少了一次遍歷數(shù)據(jù)庫的次數(shù)。其次，對FP-tree構造進行擴展，提出了一種新的樹結構MGFP-tree（matrix and group frequent pat?tern-tree）。由于在生成FP-tree過程中沒有充分利用原事務中頻繁項之間的關聯(lián)關系，因此降低了頻繁模式的挖掘效率。在新構造的MGFP-tree中，利用存儲在數(shù)組中的分組節(jié)點，可以快速構建頻繁模式樹并發(fā)現(xiàn)原事務中的頻繁項集。

3.2 矩陣

掃描事務數(shù)據(jù)庫D并將其映射成矩陣Dmxn，其中M表示的項數(shù)，N表示的是事務數(shù)加1。Dmxn中的第一列表示的是事務中不同的項Ii（i<=M），每一行表示的是每個項Ii在每一條事務Tj（j<=N）中對應的值，如果存在值標記為1，否則標記為0。設置輔助一維數(shù)組count，記錄每個項Ii的個數(shù)，同時根據(jù)數(shù)組count存儲的值刪除不滿足最小支持度閾值的行。最后，為方便后續(xù)MGFP-tree的生成，根據(jù)count中對應每個項的不同支持度進行降序排序。

為了更好的說明二維矩陣的存儲方式，使用表1中給的樣本數(shù)據(jù)進行說明。其中表3中第一列表示的是項集，最后一列表示的是存放在數(shù)組count中的每個項的支持度計數(shù)。

表3 存放事務的二維矩陣和項支持度計數(shù)的數(shù)組

3.3 分組

根據(jù)上述生成的矩陣，按列垂直向下掃描，如果邊界值matrix［j］［i］和martix［j-1］［i］為“0，1”、“1，1”、“1，0”的情況，將其分組存到ArrayList（group表示自定義的類）中并為每個group設置name，colname，end，parenttrace，parent，lastparent屬性。其中end表示每個group結束的下標位置，方便樹的快速建立。parent表示同一列不同group的父親節(jié)點，如果無則為空。parenttrace屬性表示每個group的路徑信息，若group1和group2的name、parenttrace相 同，將group1的count加1、group2的count置為0、valid置為0，可以進一步地縮小建立頻繁模式樹的內存空間和時間。

根據(jù)表4可以得到如下分組。

表4 按minsup排序后的二維矩陣和數(shù)組

表5 分組后的group對象

3.4 構建MGFP-tree

通過分組已經(jīng)建立了各個group的關系，類似于一個樹的層次關系存儲在數(shù)組中。首先按照group中end的值的大小從數(shù)組中取值，如果valid是有效地將其賦值給封裝好的ItemsetTree對象并建立輔助根節(jié)點root，最后通過二叉樹的后序遍歷以及parenttrace和parrent屬性依次向二叉樹中插入節(jié)點。如圖2所示。

圖2 存放分組節(jié)點的MGFP-tree

3.5 MGFP-growth挖掘

通過后續(xù)遍歷統(tǒng)計各個節(jié)點的孩子個數(shù)count，并將count值賦值給tempcount，tempcount用來保存新的節(jié)點計數(shù)。因為葉子節(jié)點沒有孩子節(jié)點，所以能夠很快的得到左孩子和父節(jié)點的關系，如果左孩子節(jié)點的nodename包含父節(jié)點的node?name，則父節(jié)點的tempcount更新為左孩子節(jié)點的tempcount加父親節(jié)點的tempcount。將右子樹上的不同于父節(jié)點的項添加到父節(jié)點的nodesplit中，用來跟左子樹的nodesplit進行對比，如果遍歷過程中包含相同的項，則將其nodesplit的nodesplitcount值加1。最后，將每個節(jié)點項nodesplitcount值和最小支持度比較，如果滿足則和父節(jié)點組合，產(chǎn)生頻繁項集。

為了更好地說明改進后算法的挖掘過程，根據(jù)圖2中的MGFP-tree詳細說明：首先通過后續(xù)遍歷，得到節(jié)點“f，c，a，m，p”，判斷其有沒有孩子節(jié)點，如果沒有遍歷下一個節(jié)點“b”，因為節(jié)點“f，c，a，m，p”和“b”都沒有孩子節(jié)點，所以遍歷“f，c，a，m”，從圖中可以看出節(jié)點“f，c，a，m”和“f，c，a，m，p”存在父子關系，而且子節(jié)點的nodename包含父節(jié)點的nodename，所以“f，c，a，m”的tempcount加1，依次遍歷得到滿足最小支持度閾值的有：“f，c，a，m：3”，“f：4”。其次，將非葉子節(jié)點添加到其父節(jié)點的nodesplit中，比如節(jié)點“f”的nodesplit為“f，b”，然后循環(huán)遍歷左子樹上左孩子就可以得到每個節(jié)點的nodesplitcount值，比如“b”在“f，c，a，m，b”中出現(xiàn)了一次，故將其nodesplitcount值加1；得到節(jié)點“f”的nodesplit為（b，f），nodesplitcount為（2，4）。最后將滿足最小支持度閾值的節(jié)點和其父節(jié)點組合得到頻繁模式。

4 算法性能驗證及結果分析

為驗證改進算法MGFP-growth的有效性，將MGFP-growth算法、FP-growth算法在相同的實驗環(huán)境下進行兩組不同的實驗比較。文中算法的實驗平臺為：Intel Core i5-3210M CPU 2.5 GHz處理器和4 GB內存，Windows 7 64操作系統(tǒng)，開發(fā)平臺為MyEclipse 2015。實驗所采用兩組數(shù)據(jù)集。一組數(shù)據(jù)集為mushroom，該數(shù)據(jù)集事務總數(shù)為8124條，項的個數(shù)為19個，每個事務的平均長度和最大長度為23；另外一組數(shù)據(jù)集為T10I4D100K，該數(shù)據(jù)集事務總數(shù)為100000條，項的個數(shù)為870個，每個事務的平均長度和最大長度為分別為29、10。下載地址為：http：//fimi.uantwerpen.be/data。

兩組實驗是通過改變最小支持度閾值來計算算法運行時間，實驗對比如圖3、4所示。

圖3 mushroom數(shù)據(jù)集上的運行時間

圖4 T10I4D100K數(shù)據(jù)集上的運行時間

從上面實驗結果可以看出，隨著最小支持度的增加，兩種算法的運行時間都在減小，但MG?FP-growth效率更高。mushroom該數(shù)據(jù)集相對稠密，說明必然存在非常龐大的頻繁項集，而MG?FP-growth算法將每組事務中的頻繁項集進行分組，減少了樹的分支，可以更快地發(fā)現(xiàn)頻繁模式，所以運行更快。T10I4D100K該數(shù)據(jù)集相對稀疏，而且每條事務之間長度差異較大，說明其頻繁項集相對于項結點來說較少，所以兩者基本一致，但MG?FP-tree利用矩陣存儲事務信息，只需要掃描事務數(shù)據(jù)庫一次，所以效果更好一些。

5 結語

本篇論文針對傳統(tǒng)的關聯(lián)規(guī)則算法存在的固有缺陷，提出了一種基于FP-growth算法的頻繁模式挖掘算法。首先，利用矩陣對事務存儲，不需要創(chuàng)建項目頭表，減少了事務數(shù)據(jù)庫的掃描時間。其次，對FP-tree數(shù)進行改進，提出了一種新的樹形結構MGFP-tree，新的樹結構，可以充分利用每條事務中的頻繁項集，同時不需要遞歸產(chǎn)生大量的FP-tree，減少了內存消耗。最后，通過實驗設置兩組不同的實驗驗證了改進后的算法執(zhí)行效率優(yōu)于傳統(tǒng)算法。