一種挖掘閉頻繁項集的優(yōu)化算法研究

摘 要：本文在FP-Growth算法的基礎(chǔ)上通過項合并的策略對FP-Growth做了優(yōu)化，從而減少了挖掘頻繁項集時的搜索空間，也減少了頻繁項集的數(shù)量。通過實驗可知，優(yōu)化后的挖掘閉頻繁項集算法在挖掘大量數(shù)據(jù)集上有明顯性能優(yōu)勢，挖掘的速度得到了相應(yīng)的提升。

關(guān)鍵詞：關(guān)聯(lián)規(guī)則；FP-Growth算法；閉頻繁項集；項合并

中圖分類號：TN929.5 文獻標識碼：A 文章編號：1674-7712 （2014） 24-0000-01

關(guān)聯(lián)規(guī)則算法應(yīng)用十分廣泛，然而其中主流的兩個算法分別為Apriori算法和FP-Growth算法。相比于前者，后者在性能上有一定的優(yōu)勢。Agrawal[1]提出了經(jīng)典的Apriori算法來挖掘數(shù)據(jù)集中的頻繁模式，從而挖掘出數(shù)據(jù)項集之間的關(guān)聯(lián)規(guī)則。為了更好的提高挖掘的效率，研究人員提出了基于散列的技術(shù)，事務(wù)壓縮，抽樣以及動態(tài)項集計數(shù)等改進算法。但是反復(fù)地掃描數(shù)據(jù)庫和產(chǎn)生大量候選項集的缺點給開銷帶來了不平凡的影響。于是提出了挖掘全部頻繁項集卻不產(chǎn)生大量候選集的頻繁模式增長，即FP-Growth算法[2]。

一、FP-Growth算法簡介

FP-Growth算法減少了全量掃描事務(wù)數(shù)據(jù)庫的次數(shù)，并且不產(chǎn)生候選集[3]。算法中的FP-tree是一種特殊的前綴樹，由頻繁項頭表和項前綴樹構(gòu)成。所謂前綴樹，是一種存儲候選項集的數(shù)據(jù)結(jié)構(gòu)，樹的分支用項名標識，樹的節(jié)點存儲后綴項，路徑表示項集[4]。

二、FP-Growth算法中項合并優(yōu)化

傳統(tǒng)的FP-Growth算法有如下優(yōu)點：無需產(chǎn)生候選集，并且大大減少了存儲空間；無需要反復(fù)掃描數(shù)據(jù)庫，降低了I/O操作壓力，提高了性能。但是在挖掘FP樹的過程中迭代的次數(shù)較多，產(chǎn)生的頻繁項集也非常多。

為了進一步優(yōu)化FP-Growth算法的性能，本文通過定理1來做一個剪枝的優(yōu)化。

（一）定理

在挖掘FP-Tree樹過程中，如果出現(xiàn)如下情況進行項合并：前綴項集A的子數(shù)據(jù)庫中每個事務(wù)都包含項集B，但不包含項集B的任何真超集，那么合并項集A和項集B，即A∪B形成一個閉頻繁項集，那么無需再挖掘前綴項集A的子數(shù)據(jù)庫中不包含項集B的閉項集[5]。

FP-Growth算法主要分為兩步：第一步是構(gòu)建FP-Tree，如上簡介介紹的過程。第二步：開始挖掘第一步建立好的FP-Tree，本文提出了項合并的策略來減少挖掘FP-Tree時產(chǎn)生的條件模式基，達到剪枝的效果。

（二）試驗結(jié)果

為了驗證本文提出的基于FP-Growth算法的優(yōu)化算法的性能，利用mushroom.dat數(shù)據(jù)來做試驗。試驗通過FP-Growth算法和優(yōu)化后的FP-Growth算法作比較。在相同的最小支持度下挖掘同一份數(shù)據(jù)的速率來做衡定，其中結(jié)果的橫坐標數(shù)值為支持度閥值，那么最小支持度為整個mushroom.dat數(shù)據(jù)中包含的事務(wù)數(shù)據(jù)條數(shù)乘于支持度閥值。

下圖為試驗的結(jié)果計算速率對比圖：

Fig.1 The computation rate comparison chart.

從圖中可以看出：隨著閥值的變大，相應(yīng)的最小支持度計數(shù)也變大，從而得到的頻繁項集的總量在減少，搜索的代價也隨著降低，所以優(yōu)化后的FP-Growth算法和傳統(tǒng)的FP-Growth算法在挖掘速度上很接近。

三、結(jié)束語

本文提出了一種FP-Growth算法挖掘FP-Tree過程的優(yōu)化算法，此優(yōu)化算法利用了項合并的策略減小挖掘FP-Tree時的搜索空間，進行剪枝合并，從而大大減少挖掘過程中迭代的次數(shù)。

參考文獻：

[1]高明.關(guān)聯(lián)規(guī)則挖掘算法的研究及其應(yīng)用[D].山東師范大學(xué)，2006.

[2]廖偉國，張宏書.關(guān)聯(lián)規(guī)則挖掘研究綜述[J].網(wǎng)絡(luò)財富，2009（4）：26-27.

[3]黃鶴.關(guān)聯(lián)規(guī)則算法綜述[J].軟件導(dǎo)刊，2009（03）：56-57.

[4]王小虎.關(guān)聯(lián)規(guī)則挖掘綜述[J].計算機工程與應(yīng)用，2003（33）：190-193.

[5]Jiawei Han，Micheline Kamber.數(shù)據(jù)挖掘：概念與技術(shù)[M].北京：機械工業(yè)出版社，2013：170.

[作者簡介]丁鐵凡（1988-），男，碩士學(xué)位，研究方向：大數(shù)據(jù)、數(shù)據(jù)挖掘；張振友（1964-），男，副教授，碩士學(xué)位，研究方向：異構(gòu)數(shù)據(jù)庫、電子商務(wù)；代晨旭（1988-），女，學(xué)士學(xué)位，研究方向：大數(shù)據(jù)、數(shù)據(jù)挖掘。

[基金項目]河北省自然科學(xué)基金資助項目（項目編號：F2012401050）。