面向大數(shù)據(jù)的數(shù)據(jù)庫(kù)劃分FP-Growth改進(jìn)算法

張 樂(lè)，魏昕怡，徐 蘇,林兩位

(1.南昌大學(xué)數(shù)學(xué)與計(jì)算機(jī)學(xué)院,江西 南昌 330031;2.南昌大學(xué)際鑾書(shū)院,江西 南昌 330031;3.數(shù)字福建氣象大數(shù)據(jù)研究所(閩南師范大學(xué))，福建 漳州 363000)

在傳統(tǒng)的數(shù)據(jù)挖掘領(lǐng)域，對(duì)數(shù)據(jù)集進(jìn)行頻繁項(xiàng)集挖掘，可以采用經(jīng)典的Apriori算法[1]和FP-growth算法[2]及一些改進(jìn)算法。其中，Apriori算法需要多次掃描事務(wù)數(shù)據(jù)庫(kù)，一來(lái)產(chǎn)生很大的I/O負(fù)載，二來(lái)會(huì)產(chǎn)生龐大的候選集，從而占用大量?jī)?nèi)存空間；FP-growth算法雖然只需兩次掃描事務(wù)數(shù)據(jù)庫(kù)，大大降低了I/O負(fù)載，且不產(chǎn)生候選集，從而使算法效率更高[3]，但其算法的基礎(chǔ)是需要生成FP樹(shù)，所生成的FP樹(shù)同樣占用了大量?jī)?nèi)存空間。

在大數(shù)據(jù)時(shí)代，面對(duì)大規(guī)模海量數(shù)據(jù)，單機(jī)環(huán)境下的存儲(chǔ)和計(jì)算能力將成為數(shù)據(jù)挖掘的瓶頸[4]，因此，對(duì)傳統(tǒng)算法進(jìn)行改進(jìn)，利用大數(shù)據(jù)、并行計(jì)算技術(shù)等進(jìn)行頻繁項(xiàng)集挖掘成為人們研究的重點(diǎn)。

文獻(xiàn)[5-12]都是基于FP-growth算法的采用不同并行處理技術(shù)進(jìn)行頻繁項(xiàng)集挖掘的改進(jìn)的算法，算法效率有所提升。但它們都面臨著同一個(gè)問(wèn)題，即在大數(shù)據(jù)環(huán)境下，面對(duì)海量事務(wù)數(shù)據(jù)庫(kù)，在單機(jī)中無(wú)法存儲(chǔ)所生成的FP樹(shù)，從而導(dǎo)致算法失效。文獻(xiàn)[13]采用了投影數(shù)據(jù)庫(kù)技術(shù)，并通過(guò)MapReduce編程模型和并行處理技術(shù)實(shí)現(xiàn)，在一定程度上解決了以上問(wèn)題。但在實(shí)際應(yīng)用中，常常會(huì)遇到實(shí)際可用節(jié)點(diǎn)機(jī)資源有限及單個(gè)節(jié)點(diǎn)機(jī)內(nèi)存不足的情況，使該算法的應(yīng)用有一定局限性；在某些極端情況下還有可能出現(xiàn)某個(gè)投影數(shù)據(jù)庫(kù)的規(guī)模同樣很大，甚至接近原始事務(wù)數(shù)據(jù)庫(kù)的規(guī)模，從而同樣會(huì)導(dǎo)致算法失效的問(wèn)題。為此，本文提出一種劃分?jǐn)?shù)據(jù)庫(kù)的方法，允許用戶自行設(shè)置所劃分的子數(shù)據(jù)庫(kù)的規(guī)模，從而有效解決實(shí)際應(yīng)用環(huán)境中因受單機(jī)內(nèi)存資源的限制而算法失效的問(wèn)題。

1 傳統(tǒng)的FP-growth算法

FP-growth算法使用了一種稱為頻繁模式樹(shù)(FP樹(shù))的數(shù)據(jù)結(jié)構(gòu)，F(xiàn)P樹(shù)是一種特殊的前綴樹(shù)，由頻繁項(xiàng)頭表和項(xiàng)前綴樹(shù)構(gòu)成。算法分兩個(gè)階段進(jìn)行，第一個(gè)階段是將整個(gè)事務(wù)數(shù)據(jù)庫(kù)壓縮到一顆頻繁模式樹(shù)上，第二個(gè)階段是通過(guò)對(duì)頻繁模式樹(shù)進(jìn)行挖掘，生成所有的頻繁項(xiàng)集。

我們通過(guò)一個(gè)例子來(lái)說(shuō)明FP-growth算法的過(guò)程。假設(shè)事務(wù)數(shù)據(jù)庫(kù)如表1所示，該事務(wù)數(shù)據(jù)庫(kù)共有10個(gè)事務(wù)，其中包含a，b，c，d，e，f，g，h共8個(gè)項(xiàng)，設(shè)定最小支持度計(jì)數(shù)為min-support=2。

表1 事務(wù)數(shù)據(jù)庫(kù)DTable 1 Transaction database D

其算法的主要步驟如下：

(1)第一次掃描事務(wù)數(shù)據(jù)庫(kù)D，得到所有頻繁1項(xiàng)集，并對(duì)頻繁1項(xiàng)按支持度計(jì)數(shù)的降序排序，得到頻繁1項(xiàng)頭表L(如表2所示)。其中，f，g和h支持度計(jì)數(shù)為1，小于最小支持度計(jì)數(shù)，屬于非頻繁項(xiàng)，因此它們不會(huì)出現(xiàn)在頻繁1項(xiàng)集頭表L中。

表2 頻繁1項(xiàng)集頭表LTable 2 Frequent 1-item set

(2)FP樹(shù)構(gòu)造：首先創(chuàng)建樹(shù)的根節(jié)點(diǎn)，用“null”標(biāo)記。第二次掃描數(shù)據(jù)庫(kù)D，在FP樹(shù)中為每個(gè)事務(wù)創(chuàng)建一個(gè)分枝，分枝中的每個(gè)節(jié)點(diǎn)對(duì)應(yīng)該事務(wù)的每一個(gè)項(xiàng)(刪除非頻繁項(xiàng))，且按表L中的順序鏈接，同時(shí)分枝中的每個(gè)項(xiàng)計(jì)數(shù)加1。最后，建立頻繁1項(xiàng)頭表與FP樹(shù)的關(guān)聯(lián)，得到如下圖1所示的FP樹(shù)。

圖1 FP樹(shù)Fig.1 FP Tree

(3)對(duì)以上生成的FP樹(shù)進(jìn)行挖掘，得到全部頻繁項(xiàng)集。挖掘的過(guò)程是通過(guò)調(diào)用以下過(guò)程遞歸實(shí)現(xiàn)的：

Procedure FP-growth(tree,α)

IF tree含單個(gè)路徑P THEN

FOR each路徑P中節(jié)點(diǎn)的每個(gè)組合(記作β)

產(chǎn)生模式β∪α，其支持度等于β中節(jié)點(diǎn)的

最小支持度計(jì)數(shù)；

ELSE

FOR tree的頭表中的每個(gè)αi

{產(chǎn)生模式β=αi∪α，其支持度等于αi；

構(gòu)造β的條件模式基，然后構(gòu)造β的條件FP樹(shù)treeβ；

IF treeβ≠Φ THEN

調(diào)用FP-growth(treeβ,β)；

}

2 FP-growth算法的改進(jìn)

FP-growth算法在事務(wù)數(shù)據(jù)庫(kù)規(guī)模不是很大，F(xiàn)P樹(shù)能夠在單機(jī)內(nèi)存中存儲(chǔ)下的情況下是有效的。但在大數(shù)據(jù)環(huán)境下，面對(duì)海量數(shù)據(jù)庫(kù)，所構(gòu)建的FP樹(shù)根本無(wú)法在單機(jī)內(nèi)存中存儲(chǔ)，這種方法也就失效了。為此，我們對(duì)傳統(tǒng)的FP-growth算法進(jìn)行改進(jìn)。我們?nèi)匀灰郧懊娴氖聞?wù)數(shù)據(jù)庫(kù)D為例，說(shuō)明具體的改進(jìn)方法。本算法的運(yùn)行環(huán)境是一個(gè)由一臺(tái)mater主機(jī)和多臺(tái)slave節(jié)點(diǎn)機(jī)組成的并行計(jì)算環(huán)境。在這種運(yùn)行環(huán)境下，改進(jìn)后的算法的實(shí)現(xiàn)過(guò)程如下：

(1)第一次掃描事務(wù)數(shù)據(jù)庫(kù)D，得到所有頻繁1項(xiàng)集，并對(duì)頻繁1項(xiàng)按支持度計(jì)數(shù)的降序排序，得到頻繁1項(xiàng)頭表L(如表2所示)。這一步跟傳統(tǒng)FP-growth算法相同。

(2)對(duì)事務(wù)數(shù)據(jù)庫(kù)D進(jìn)行數(shù)據(jù)清理，將D中的所有非頻繁1項(xiàng)刪除。然后對(duì)D按每個(gè)頻繁1項(xiàng)(表L中第一個(gè)項(xiàng)b除外)進(jìn)行抽取，為每個(gè)頻繁1項(xiàng)建立一個(gè)所有事務(wù)均含該項(xiàng)的投影數(shù)據(jù)庫(kù)。a，c，d，e對(duì)應(yīng)的投影數(shù)據(jù)庫(kù)分別如表3～表6所示。

(3)由投影數(shù)據(jù)庫(kù)去直接生成的FP樹(shù)仍然有可能規(guī)模龐大，在單機(jī)內(nèi)存中無(wú)法存放。為此，我們對(duì)以上投影數(shù)據(jù)庫(kù)進(jìn)行進(jìn)一步的劃分，按預(yù)先設(shè)定所含最大事務(wù)數(shù)的方式，將投影數(shù)據(jù)庫(kù)分成一個(gè)個(gè)投影子數(shù)據(jù)庫(kù)。例如，上例中我們?cè)O(shè)定所有劃分后的投影子數(shù)據(jù)庫(kù)中包含的事務(wù)數(shù)最大為4，則a和c的投影數(shù)據(jù)庫(kù)各被進(jìn)一步劃分成兩個(gè)投影子數(shù)據(jù)庫(kù)Da:1，Da:2和Dc:1，Dc:2，如表7～表10所示。

表3 a對(duì)應(yīng)的投影數(shù)據(jù)庫(kù)DaTable 3 The corresponding projection database Da with a

表4 c對(duì)應(yīng)的投影數(shù)據(jù)庫(kù)DcTable 4 The corresponding projection database Dc with c

表5 d對(duì)應(yīng)的投影數(shù)據(jù)庫(kù)DdTable 5 The corresponding projection database Dd with d

表6 e對(duì)應(yīng)的投影數(shù)據(jù)庫(kù)DeTable 6 The corresponding projection database De with e

表7 a對(duì)應(yīng)的投影子數(shù)據(jù)庫(kù)Da:1Table 7 The corresponding projection sub-database Da:1 with a

這些投影子數(shù)據(jù)庫(kù)被分發(fā)在一個(gè)個(gè)節(jié)點(diǎn)機(jī)上。

(4)每個(gè)節(jié)點(diǎn)機(jī)對(duì)投影子數(shù)據(jù)庫(kù)進(jìn)行掃描，構(gòu)造對(duì)應(yīng)項(xiàng)的投影FP子樹(shù)。在這里我們需要對(duì)傳統(tǒng)FP-growth構(gòu)造FP樹(shù)的算法加以改進(jìn)。設(shè)第k個(gè)節(jié)點(diǎn)機(jī)處理的是頻繁1項(xiàng)m對(duì)應(yīng)的投影子數(shù)據(jù)庫(kù)Dm:i。在對(duì)Dm:i中的每個(gè)事務(wù)處理時(shí)，首先將每個(gè)事務(wù)中的項(xiàng)按表L的次序排序，并將m以及其后的所有項(xiàng)全部刪除，只將剩余的項(xiàng)在擬構(gòu)造的FP子樹(shù)中生成分枝。具體算法如下：

① 創(chuàng)建FP子樹(shù)的根節(jié)點(diǎn)，以“null”標(biāo)記。

② 遍歷數(shù)據(jù)庫(kù)Dm:i，對(duì)Dm:i中的每個(gè)事務(wù)執(zhí)行：

a.將事務(wù)中的項(xiàng)按L中的次序排序，并將m以及其后的所有項(xiàng)全部刪除，形成事務(wù)項(xiàng)列表記為[p│P]，其中p為第一個(gè)項(xiàng)元素，而P為剩余項(xiàng)元素的列表。

b.調(diào)用insert_tree([p│P]，T)。insert_tree([p│P]，T)執(zhí)行過(guò)程如下：如果T有一個(gè)子女N使得N.item-name=p.item-name，則N的計(jì)數(shù)增1，同時(shí)頭表中其對(duì)應(yīng)項(xiàng)支持度計(jì)數(shù)增1；否則創(chuàng)建一個(gè)新節(jié)點(diǎn)N，將其計(jì)數(shù)設(shè)置為1，鏈接到它的父節(jié)點(diǎn)T，同時(shí)頭表中添加一項(xiàng)，支持度計(jì)數(shù)設(shè)置為1。如果P非空，遞歸地調(diào)用insert_tree([p│P]，T)。

表8 a對(duì)應(yīng)的投影子數(shù)據(jù)庫(kù)Da:2Table 8 The corresponding projection sub-database Da:2 with a

表9 c對(duì)應(yīng)的投影數(shù)據(jù)庫(kù)Dc:1Table 9 The corresponding projection sub-database Dc:1 with c

表10 c對(duì)應(yīng)的投影數(shù)據(jù)庫(kù)Dc:2Table 10 The corresponding projection sub-database Dc:1 with c

由此改進(jìn)算法生成的FP樹(shù)稱為頻繁1項(xiàng)m所對(duì)應(yīng)的投影子數(shù)據(jù)庫(kù)的FP子樹(shù)Tm:i，為a，c，d，e構(gòu)建的投影FP子樹(shù)分別如圖2～圖7所示。

(5)每個(gè)節(jié)點(diǎn)機(jī)對(duì)所構(gòu)建的FP子樹(shù)進(jìn)行挖掘，產(chǎn)生局部頻繁項(xiàng)集。設(shè)某節(jié)點(diǎn)機(jī)處理生成的m的FP子樹(shù)為Tm:i，則由條件FP子樹(shù)挖掘頻繁項(xiàng)集的算法如下：

圖2 a的投影FP子樹(shù)Ta:1Fig.2 Projection FP subtree Ta:1 with a

圖3 a的投影FP子樹(shù)Ta:2Fig.3 Projection FP subtree Ta:2 with a

圖4 c的投影FP子樹(shù)Tc:1Fig.4 Projection FP subtree Tc:1 with c

圖5 c的投影FP子樹(shù)Tc:2Fig.5 Projection FP subtree Tc:2 with c

圖6 d的投影FP子樹(shù)Td:1Fig.6 Projection FP subtree Td:1 with d

FOR從樹(shù)Tm:i根節(jié)點(diǎn)null開(kāi)始的每一條路徑R

FOR路徑R中的每個(gè)節(jié)點(diǎn)p

產(chǎn)生模式C=p∪m，其支持度計(jì)數(shù)等于C中各節(jié)點(diǎn)支持度計(jì)數(shù)的最小值

FOR路徑R中的每個(gè)節(jié)點(diǎn)組合P

局部頻繁模式=P∪m，其支持度計(jì)數(shù)等于C的支持度計(jì)數(shù)

(6)將同一個(gè)頻繁1項(xiàng)的投影子數(shù)據(jù)庫(kù)生成的局部頻繁項(xiàng)集匯聚到同一個(gè)節(jié)點(diǎn)機(jī)進(jìn)行歸并，產(chǎn)生該頻繁1項(xiàng)的頻繁項(xiàng)集。

(7)最后匯總所有節(jié)點(diǎn)機(jī)生成的頻繁1項(xiàng)對(duì)應(yīng)的頻繁項(xiàng)集，從而得到全部的頻繁項(xiàng)集。

圖7 e的投影FP子樹(shù)Te:1Fig.7 Projection FP subtree Te:1 with e

3 并行頻繁項(xiàng)集挖掘?qū)崿F(xiàn)

改進(jìn)后的頻繁項(xiàng)集挖掘分為兩個(gè)階段：第一階段生成全部的頻繁1項(xiàng)集，并構(gòu)建頻繁1項(xiàng)頭表L，我們可以使用MapReduce編程模型并行實(shí)現(xiàn)[14,15]；第二階段由多個(gè)節(jié)點(diǎn)機(jī)并行挖掘頻繁項(xiàng)集，最后匯總得到全部的頻繁項(xiàng)集。

第一階段實(shí)現(xiàn)過(guò)程如下：

(1)在master主機(jī)上將事務(wù)數(shù)據(jù)庫(kù)中的事務(wù)分成相同的n個(gè)數(shù)據(jù)塊，然后把n個(gè)數(shù)據(jù)塊發(fā)送到n個(gè)slave節(jié)點(diǎn)機(jī)。

(2)每個(gè)slave節(jié)點(diǎn)機(jī)進(jìn)行并行Map處理，計(jì)算出局部的1項(xiàng)集及其支持度計(jì)數(shù)；然后通過(guò)Combiner函數(shù)合并相同項(xiàng)，并把結(jié)果發(fā)送給master主機(jī)。

(3)master主機(jī)進(jìn)行Reduce處理，將所有slave節(jié)點(diǎn)發(fā)送來(lái)的結(jié)果進(jìn)行匯總，計(jì)算出全局頻繁1項(xiàng)集及其支持度計(jì)數(shù)，然后按支持度計(jì)數(shù)值對(duì)頻繁1項(xiàng)集降序排序，最終得到排序后的結(jié)果頭表L(如表2所示)。

由于采用MapReduce模式并行實(shí)現(xiàn)，這一過(guò)程所花費(fèi)的時(shí)間將比傳統(tǒng)FP-growth算法更少。

第二階段實(shí)現(xiàn)過(guò)程如下：

(1)首先每個(gè)節(jié)點(diǎn)機(jī)對(duì)此前master分發(fā)來(lái)的數(shù)據(jù)塊進(jìn)行數(shù)據(jù)清理，將數(shù)據(jù)塊中的所有非頻繁1項(xiàng)刪除。然后對(duì)數(shù)據(jù)塊進(jìn)行頻繁1項(xiàng)抽取，為每個(gè)頻繁1項(xiàng)生成部分投影數(shù)據(jù)庫(kù)，同一頻繁1項(xiàng)的所有部分投影數(shù)據(jù)庫(kù)被匯聚到同一節(jié)點(diǎn)機(jī)，生成所有記錄都包含該頻繁1項(xiàng)的投影數(shù)據(jù)庫(kù)。

(2)由slave節(jié)點(diǎn)機(jī)對(duì)每個(gè)投影數(shù)據(jù)庫(kù)進(jìn)行進(jìn)一步的劃分，按預(yù)先設(shè)定所含最大事務(wù)記錄數(shù)的方式，將投影數(shù)據(jù)庫(kù)分成一個(gè)個(gè)投影子數(shù)據(jù)庫(kù)。

(3)每個(gè)slave節(jié)點(diǎn)機(jī)為投影子數(shù)據(jù)庫(kù)生成對(duì)應(yīng)的FP子樹(shù)，并對(duì)這些FP子樹(shù)進(jìn)行挖掘生成局部頻繁項(xiàng)集。

(4)同一投影數(shù)據(jù)庫(kù)對(duì)應(yīng)的所有子數(shù)據(jù)庫(kù)生成的局部頻繁項(xiàng)匯聚到同一節(jié)點(diǎn)機(jī)上，生成該投影數(shù)據(jù)庫(kù)對(duì)應(yīng)的頻繁項(xiàng)集，然后將結(jié)果發(fā)送給master主機(jī)。

(5)master主機(jī)將所有結(jié)果匯總后得到的就是全部的頻繁項(xiàng)集。

4 算法實(shí)驗(yàn)分析

傳統(tǒng)的FP-Growth算法在面對(duì)海量事務(wù)數(shù)據(jù)庫(kù)時(shí)將會(huì)遇到因所生成的FP樹(shù)規(guī)模龐大而無(wú)法在單機(jī)內(nèi)存中存儲(chǔ)從而導(dǎo)致算法失效這一問(wèn)題已在文獻(xiàn)[12]中進(jìn)行了驗(yàn)證。本文所提出的算法因?yàn)椴捎昧藬?shù)據(jù)庫(kù)劃分的方法，不會(huì)存在這一問(wèn)題。因此，本實(shí)驗(yàn)主要針對(duì)本文所提出的劃分?jǐn)?shù)據(jù)庫(kù)算法(記為DPFP算法)在并行計(jì)算環(huán)境下的運(yùn)行效率進(jìn)行分析。實(shí)驗(yàn)方法主要是將DPFP算法在Hadoop集群環(huán)境下的運(yùn)行時(shí)間與傳統(tǒng)的FP-growth算法在單機(jī)環(huán)境下的運(yùn)行時(shí)間進(jìn)行比對(duì)。Hadoop集群環(huán)境采用主從式架構(gòu)，包括1個(gè)master主機(jī)(配置為Intel i7-9700 CPU，16GB內(nèi)存)和最多10個(gè)slave節(jié)點(diǎn)機(jī)(配置為Intel i5-2450 CPU，4GB內(nèi)存)。

實(shí)驗(yàn)一：DPFP算法分別在由1臺(tái)master主機(jī)加5臺(tái)slave節(jié)點(diǎn)機(jī)和1臺(tái)master主機(jī)加10臺(tái)slave節(jié)點(diǎn)機(jī)組成的集群環(huán)境上運(yùn)行，F(xiàn)P-growth算法在單臺(tái)節(jié)點(diǎn)機(jī)上運(yùn)行。實(shí)驗(yàn)數(shù)據(jù)集選取Frequent Itemset Mining Data Repository[16]里的T1014D100K.dat，該數(shù)據(jù)集包含10萬(wàn)條記錄。其中設(shè)定的最小支持度分別為2%，4%，6%，8%和10%。實(shí)驗(yàn)結(jié)果分別如圖8，9所示。

從運(yùn)行結(jié)果看：

(1)DPFP算法在執(zhí)行效率上比傳統(tǒng)的FP-growth算法更高，且節(jié)點(diǎn)機(jī)數(shù)量越多，DPFP算法所需的時(shí)間越少，這也體現(xiàn)了并行處理的優(yōu)勢(shì)。

(2)隨著最小支持度數(shù)值的增加，兩種算法的挖掘時(shí)間都逐漸減少。這是因?yàn)樽钚≈С侄葦?shù)值越大，頻繁項(xiàng)越少。對(duì)FP-growth算法來(lái)說(shuō)，最小支持度數(shù)值越大，生成的FP樹(shù)越小，對(duì)FP樹(shù)遞歸挖掘的時(shí)間也就越少；對(duì)DPFP算法來(lái)說(shuō)，最小支持度數(shù)值越大，生成的頻繁1項(xiàng)投影數(shù)據(jù)庫(kù)越少，分發(fā)數(shù)據(jù)的時(shí)間就越少，對(duì)投影子數(shù)據(jù)庫(kù)進(jìn)行挖掘的時(shí)間也就越少。

(3)DPFP算法相比FP-growth算法的加速比并不會(huì)隨著最小支持度數(shù)值的增加而成線性增長(zhǎng)[17]，這是因?yàn)樽钚≈С侄仍酱?，DPFP算法中所進(jìn)行的投影數(shù)據(jù)庫(kù)生成和分發(fā)所占的時(shí)間比值越大，而這些操作在FP-growth算法中是沒(méi)有的。因此，當(dāng)最小支持度逐漸增大后，F(xiàn)P-growth算法所生成的FP樹(shù)越來(lái)越小，遞歸挖掘的時(shí)間會(huì)越來(lái)越呈線性遞減的趨勢(shì)。

最小支持度圖8 實(shí)驗(yàn)一5臺(tái)節(jié)點(diǎn)機(jī)Fig.8 Experiment 1:5-Node machines

最小支持度圖9 實(shí)驗(yàn)一10臺(tái)節(jié)點(diǎn)機(jī)Fig.9 Experiment 1:10-Node machines

實(shí)驗(yàn)二：DPFP算法在由1臺(tái)master主機(jī)加10臺(tái)slave節(jié)點(diǎn)機(jī)組成的集群環(huán)境上運(yùn)行，F(xiàn)P-growth算法仍然在單臺(tái)節(jié)點(diǎn)機(jī)上運(yùn)行。實(shí)驗(yàn)數(shù)據(jù)由IBM QUEST Market-Basket Synthetic Data Generator產(chǎn)生，選取包含100萬(wàn)條記錄的事務(wù)數(shù)據(jù)庫(kù)。設(shè)定的最小支持度同樣分別為2%，4%，6%，8%和10%。實(shí)驗(yàn)結(jié)果如圖10所示。

從運(yùn)行結(jié)果看，隨著事務(wù)數(shù)據(jù)庫(kù)規(guī)模的增大，DPFP算法的效率更加明顯。這是因?yàn)閿?shù)據(jù)庫(kù)規(guī)模越大，F(xiàn)P-growth算法生成的FP樹(shù)就越大，遞歸挖掘龐大的FP樹(shù)將非常耗時(shí)。而對(duì)DPFP算法來(lái)說(shuō)，投影數(shù)據(jù)庫(kù)生成和分發(fā)所占的時(shí)間比值變得更小，且因?yàn)镈PFP算法劃分的子數(shù)據(jù)庫(kù)規(guī)模接近，分配到各節(jié)點(diǎn)機(jī)的負(fù)載更均衡，由多個(gè)節(jié)點(diǎn)機(jī)并行處理的效率更加顯現(xiàn)出來(lái)。

最小支持度圖10 實(shí)驗(yàn)二10臺(tái)節(jié)點(diǎn)機(jī)Fig.10 Experiment 2:10-Node machines

5 總結(jié)

本文所提出的算法基于傳統(tǒng)的FP-growth算法進(jìn)行改進(jìn)，并通過(guò)Hadoop架構(gòu)和MapReduce編程模型實(shí)現(xiàn)。在該算法中，首先對(duì)所有頻繁1項(xiàng)生成投影數(shù)據(jù)庫(kù)，再對(duì)投影數(shù)據(jù)庫(kù)進(jìn)行劃分。由于用戶可以靈活設(shè)置所劃分的子數(shù)據(jù)庫(kù)中事務(wù)記錄的數(shù)量，因此可以有效控制由這些子數(shù)據(jù)庫(kù)生成的FP子樹(shù)的規(guī)模，從而有效解決因FP樹(shù)在單機(jī)內(nèi)存中存儲(chǔ)不下導(dǎo)致算法失效的問(wèn)題。同時(shí)由于采用MapReduce編程模型實(shí)現(xiàn)并行FP子樹(shù)的生成和挖掘，且分發(fā)到各節(jié)點(diǎn)機(jī)的用于生成FP子樹(shù)的子數(shù)據(jù)庫(kù)規(guī)模接近，使得各節(jié)點(diǎn)機(jī)上的負(fù)載更均衡。在大規(guī)模集群環(huán)境下使用該算法可以很好地解決對(duì)大數(shù)據(jù)的挖掘。