魏 坤 王 芳 黃樹(shù)成

（江蘇科技大學(xué)計(jì)算機(jī)學(xué)院 鎮(zhèn)江 212001）

1 引言

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

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

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

2 問(wèn)題陳述

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

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

2.2 頻繁項(xiàng)集

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

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

2.3 FP-growth算法

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

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

輸出：頻繁模式集

方法：

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

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

Step3：調(diào)用FP-growth（Tree，null）開(kāi)始挖掘。偽代碼如下：

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

procedure FP_growth（Tree，α）

ifTree含單個(gè)路徑Pthen｛

for路徑P中結(jié)點(diǎn)的每個(gè)組合（β）

為了更好地說(shuō)明FP-growth算法的詳細(xì)過(guò)程，舉例如表1所示。

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

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

圖1 存放壓縮的頻繁模式信息的FP樹(shù)

通過(guò)FP-growth算法對(duì)圖1中的FP-tree進(jìn)行挖掘，得到如表2所示頻繁模式集。

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

3 改進(jìn)算法

3.1 改進(jìn)算法思想

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

3.2 矩陣

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

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

表3 存放事務(wù)的二維矩陣和項(xiàng)支持度計(jì)數(shù)的數(shù)組

3.3 分組

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

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

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

表5 分組后的group對(duì)象

3.4 構(gòu)建MGFP-tree

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

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

3.5 MGFP-growth挖掘

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

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

4 算法性能驗(yàn)證及結(jié)果分析

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

兩組實(shí)驗(yàn)是通過(guò)改變最小支持度閾值來(lái)計(jì)算算法運(yùn)行時(shí)間，實(shí)驗(yàn)對(duì)比如圖3、4所示。

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

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

從上面實(shí)驗(yàn)結(jié)果可以看出，隨著最小支持度的增加，兩種算法的運(yùn)行時(shí)間都在減小，但MG?FP-growth效率更高。mushroom該數(shù)據(jù)集相對(duì)稠密，說(shuō)明必然存在非常龐大的頻繁項(xiàng)集，而MG?FP-growth算法將每組事務(wù)中的頻繁項(xiàng)集進(jìn)行分組，減少了樹(shù)的分支，可以更快地發(fā)現(xiàn)頻繁模式，所以運(yùn)行更快。T10I4D100K該數(shù)據(jù)集相對(duì)稀疏，而且每條事務(wù)之間長(zhǎng)度差異較大，說(shuō)明其頻繁項(xiàng)集相對(duì)于項(xiàng)結(jié)點(diǎn)來(lái)說(shuō)較少，所以?xún)烧呋疽恢拢玀G?FP-tree利用矩陣存儲(chǔ)事務(wù)信息，只需要掃描事務(wù)數(shù)據(jù)庫(kù)一次，所以效果更好一些。

5 結(jié)語(yǔ)

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