改進(jìn)的Fp－Growth數(shù)據(jù)關(guān)聯(lián)挖掘算法研究

鄒永平

(江蘇省無(wú)錫交通高等職業(yè)技術(shù)學(xué)校，江蘇無(wú)錫 214151)

引言

數(shù)據(jù)關(guān)聯(lián)規(guī)則的挖掘一般包括兩個(gè)過(guò)程:首先尋找具有最小置信支持度的所有頻繁項(xiàng)集;基于滿足最小置信支持度和最小置信度的要求，再由頻繁項(xiàng)集產(chǎn)生強(qiáng)相數(shù)據(jù)關(guān)聯(lián)規(guī)則。數(shù)據(jù)關(guān)聯(lián)規(guī)則挖掘算法的研究重點(diǎn)是如何快速有效地找出滿足最小置信支持度的所有頻繁項(xiàng)集。由于Apriori算法在不停掃描數(shù)據(jù)庫(kù)時(shí)會(huì)通過(guò)產(chǎn)生大量的候選項(xiàng)集，并由此找出所有的頻繁項(xiàng)集，這就給算法在時(shí)間和空間上帶來(lái)太大的開(kāi)銷。Han等人提出一種新的基于所謂Fp－Tree的頻繁模式增長(zhǎng)算法已克服數(shù)據(jù)關(guān)聯(lián)規(guī)則的嚴(yán)重不足之處。

Fp－Growth算法采用新的分而治之的策略。該策略的原理是:首先將可以提供頻繁項(xiàng)集的數(shù)據(jù)源數(shù)據(jù)庫(kù)壓縮到一顆頻繁模式樹(shù)(frequent patern tree，簡(jiǎn)稱為Fp－Tree)，但項(xiàng)集關(guān)聯(lián)信息仍要保留;再通過(guò)一組條件數(shù)據(jù)庫(kù)(一種特殊類型的投影數(shù)據(jù)庫(kù))將通過(guò)壓縮后的數(shù)據(jù)庫(kù)分成得到，頻繁項(xiàng)由條件數(shù)據(jù)庫(kù)關(guān)聯(lián)，每個(gè)條件數(shù)據(jù)庫(kù)分別被挖掘。

1.改進(jìn)的Fp－Growth算法的挖掘過(guò)程

Fp－Growth數(shù)據(jù)關(guān)聯(lián)挖掘算法在性能上比以往的挖掘算法都有較大的改進(jìn)，但還是存在前面曾經(jīng)提到的不足?；诖?，本文基于分隔方法對(duì)Fp－Growth算法進(jìn)行改進(jìn)。

1.1 改進(jìn)的Fp－Growth算法描述

改進(jìn)算法中數(shù)據(jù)庫(kù)分隔，約束項(xiàng)挖掘以及頻繁項(xiàng)合并的具體過(guò)程描述如下:

輸入:M—數(shù)據(jù)源數(shù)據(jù)庫(kù);min_sup—最小置信支持度閾值。

輸出:M中的頻繁項(xiàng)集。

改進(jìn)算法具體過(guò)程描述如下:

(1)對(duì)數(shù)據(jù)庫(kù)M進(jìn)行掃描，找出由候選l－項(xiàng)集構(gòu)成的集合，得到其置信支持度計(jì)數(shù)。按置信支持度計(jì)數(shù)遞減順序?qū)蜻x1－項(xiàng)集的各項(xiàng)進(jìn)行排列，得到候選1，項(xiàng)集的集合F。將F中置信支持度小于最小置信支持度的項(xiàng)刪除，得到頻繁1－項(xiàng)集的集合L。設(shè) L={Im，Im－1，…I1}，其中，Im為最高置信支持度，I1為最小的置信支持度。

(2)對(duì)數(shù)據(jù)庫(kù)M進(jìn)行再次掃描，刪除各數(shù)據(jù)源中置信支持度小于最小置信支持度的項(xiàng)，按照遞增次序，基于各項(xiàng)置信支持度計(jì)數(shù)，對(duì)各數(shù)據(jù)源中的項(xiàng)進(jìn)行排列，得到數(shù)據(jù)庫(kù)為“M”。

(3)對(duì)數(shù)據(jù)庫(kù)“M”進(jìn)行掃描，將所有第一項(xiàng)為項(xiàng) Ii(i=1，2，…，m －1，m)的數(shù)據(jù)源進(jìn)行提取，在相應(yīng)的數(shù)據(jù)鏈表Vi中存放這些數(shù)據(jù)源?！癕”中所有數(shù)據(jù)源信息被保存在V={V1，V2，…，Vm}的數(shù)據(jù)鏈表組。

(4)根據(jù)前述過(guò)程中各項(xiàng)的置信支持度計(jì)數(shù)，在一定的規(guī)則下遞增地構(gòu)造各項(xiàng)的數(shù)據(jù)庫(kù)子集，通過(guò)Fp－Growth算法對(duì)其運(yùn)行約束頻繁項(xiàng)挖掘。

(5)將從Vi中導(dǎo)出的數(shù)據(jù)存放于數(shù)據(jù)庫(kù)“M”中，對(duì)“M”用Fp－Growth算法運(yùn)行包含項(xiàng)的約束頻繁項(xiàng)挖掘。挖掘過(guò)程包括:

①對(duì)數(shù)據(jù)庫(kù)“M”進(jìn)行掃描，按置信支持度計(jì)數(shù)遞減次序?qū)ⅰ癕”的數(shù)據(jù)源重新排列。

②通過(guò)“M”構(gòu)造Fp－Growth，創(chuàng)建項(xiàng)頭表HT。

注:構(gòu)造項(xiàng)頭表HT時(shí)，該HT中各項(xiàng)的次序等于L的排列次序，HT中的最后一項(xiàng)標(biāo)示的就是項(xiàng)Ii的置信支持度計(jì)數(shù)及其節(jié)點(diǎn)鏈信息。

③通過(guò)HT中的最后一項(xiàng)所表示的信息構(gòu)造該項(xiàng)的條件模式基，構(gòu)造其條件Fp－Tree，包含該項(xiàng)的頻繁項(xiàng)集ZLi就能在該條件Fp－Tree上挖掘出來(lái)，從而完成數(shù)據(jù)庫(kù)子集“M”上的約束頻繁項(xiàng)挖掘。

(6)刪除Vi中的頭元素，基于其不同的后繼元素，在其它相應(yīng)的數(shù)據(jù)鏈表中疊加去掉頭元素的數(shù)據(jù)源。

(7)在L中所有項(xiàng)的約束頻繁項(xiàng)集ZLi被依次挖掘出來(lái)后，將這些約束頻繁項(xiàng)集合并，即取這些約束頻繁項(xiàng)集ZLi的并集，從而得到M中的所有頻繁項(xiàng)集，挖掘工作完成。

2.具體應(yīng)用

為了說(shuō)明該算法的有效性，以列于圖1左側(cè)所示的數(shù)據(jù)源數(shù)據(jù)庫(kù)為例，說(shuō)明改進(jìn)算法的挖掘過(guò)程。共有10個(gè)數(shù)據(jù)源存在于數(shù)據(jù)庫(kù)中。其最小置信支持度設(shè)置為3，也就是min_sup=30%。

通過(guò)對(duì)該數(shù)據(jù)庫(kù)首次掃描，得到F(候選1－項(xiàng)集的集合)及其置信支持度計(jì)數(shù)，置信支持度小于最小置信支持度3的從F中刪除，及刪除g和f，得到頻繁1－項(xiàng)集的集合。再次掃描數(shù)據(jù)庫(kù)，將置信支持度小于最小置信支持度的項(xiàng)從各數(shù)據(jù)源中刪除，按置信支持度計(jì)數(shù)遞增的順序?qū)Ω黜?xiàng)數(shù)據(jù)源中的項(xiàng)重新排列，得到數(shù)據(jù)庫(kù)M，如圖1所示。

圖1 數(shù)據(jù)庫(kù)“M”形成

將M中的各數(shù)據(jù)源按照第一項(xiàng)的不同分別保存到數(shù)據(jù)鏈表組v中的不同數(shù)據(jù)鏈表。以遞增順序?qū)中各項(xiàng)的置信支持度計(jì)數(shù)進(jìn)行排序，在數(shù)據(jù)庫(kù)M中導(dǎo)入保存在數(shù)據(jù)鏈表中頭項(xiàng)為α的數(shù)據(jù)，基于Fp－Growth算法，對(duì)約束頻繁項(xiàng)進(jìn)行挖掘。運(yùn)行約束頻繁項(xiàng)挖掘時(shí)生成的Fp－Tree和相應(yīng)的項(xiàng)頭表示于圖2。

以項(xiàng)頭表中的最后一項(xiàng)所標(biāo)示的信息為基礎(chǔ)，構(gòu)造該項(xiàng)α的條件模式基，構(gòu)造條件Fp－Tree，該條件Fp－Tree就可以將包含項(xiàng)α的約束頻繁項(xiàng)集挖掘出來(lái)。挖掘出來(lái)的頻繁項(xiàng)集及其置信支持度為(a)(30%)。隨后，頭元素α將從頭項(xiàng)為α的數(shù)據(jù)鏈表中的刪除，如果后繼元素不同的話，就可以再其它相應(yīng)的數(shù)據(jù)鏈表中迭加去掉頭元素的數(shù)據(jù)源，新的數(shù)據(jù)鏈表組就可以得到了。

圖2 頭項(xiàng)為a的數(shù)據(jù)庫(kù)M生成的的項(xiàng)頭表

最后可以在數(shù)據(jù)庫(kù)“M”中導(dǎo)入來(lái)自新數(shù)據(jù)鏈表組中頭項(xiàng)為e的數(shù)據(jù)鏈表中的數(shù)據(jù)，基于Fp－Growth算法，進(jìn)行約束頻繁項(xiàng)挖掘，將該頭元素和組合形成新的數(shù)據(jù)鏈表組刪除。當(dāng)所有項(xiàng)的約束頻繁項(xiàng)集被挖掘出來(lái)后就停止挖掘，對(duì)約束項(xiàng)頻繁項(xiàng)集進(jìn)行合并，就可以得到實(shí)例數(shù)據(jù)庫(kù)的所有頻繁項(xiàng)集及其置信支持度，結(jié)束挖掘過(guò)程。

Apriori算法是現(xiàn)今研究數(shù)據(jù)關(guān)聯(lián)規(guī)則中最具代表性的方法，雖然之后有許多算法被提出。

2.2 實(shí)驗(yàn)過(guò)程分析

本文通過(guò)在 WebDocs，accidents和 bio－train等三個(gè)數(shù)據(jù)庫(kù)中的測(cè)試結(jié)果來(lái)分析和比較Fp－Growth算法及其改進(jìn)算法的性能。基于c語(yǔ)言，編制測(cè)試算法，算法運(yùn)行環(huán)境為 Petium IV2.8G，內(nèi)存512M。表1～表4列出了實(shí)驗(yàn)結(jié)果。其中，表1和表2分別列出了從數(shù)據(jù)庫(kù)WebDocs中抽取了300M，40萬(wàn)條左右的數(shù)據(jù)和500M，58萬(wàn)條左右的數(shù)據(jù)運(yùn)行測(cè)試所得的結(jié)果。

表1 改進(jìn)算法在(350M)數(shù)據(jù)庫(kù)上的測(cè)試結(jié)果

由此可以看出，對(duì)于webDocs(350M)數(shù)據(jù)庫(kù)，相比較于未改進(jìn)的算法，改進(jìn)的Fp－Growth算法在不同置信支持度下的運(yùn)行時(shí)間要大大縮短。

表2 改進(jìn)算法在webDocs(500M)數(shù)據(jù)庫(kù)上的測(cè)試結(jié)果

從表2中可以看出，在webDocs(500M)數(shù)據(jù)庫(kù)上，改進(jìn)的Fp－Growth算法在不同置信支持度下其運(yùn)行時(shí)間也均比未改進(jìn)的算法要短。

表3 改進(jìn)算法在accidents(33.8M)數(shù)據(jù)庫(kù)上的測(cè)試結(jié)果

表3的結(jié)果表明，在accidents(33.8M)數(shù)據(jù)庫(kù)上，相比較于未改進(jìn)的算法，改進(jìn)的Fp－Growth算法在不同置信支持度下其運(yùn)行時(shí)間也要縮短。

表4 改進(jìn)算法在bio_train(66.4M)數(shù)據(jù)庫(kù)上的測(cè)試結(jié)果

表4的結(jié)果表明，在bio_train(66.4M)數(shù)據(jù)庫(kù)上，相比較于未改進(jìn)的算法，改進(jìn)的Fp－Growth算法在不同置信支持度下其運(yùn)行時(shí)間也有所縮短。

綜合上述4種情況的結(jié)果表明，改進(jìn)算法要明顯快于原算法，因?yàn)楦倪M(jìn)算法只需對(duì)數(shù)據(jù)庫(kù)進(jìn)行一次掃描就可以創(chuàng)建數(shù)據(jù)庫(kù)子集，而原算法則需要對(duì)頻繁1－項(xiàng)集的項(xiàng)總數(shù)的數(shù)據(jù)庫(kù)掃描，改進(jìn)算法的實(shí)時(shí)性更強(qiáng)。

基于 Fp－Growth算法，提出了改進(jìn)的 Fp－Growth挖掘算法，改進(jìn)后的Fp－Growth挖掘算法可以適用于對(duì)大型數(shù)據(jù)庫(kù)的數(shù)據(jù)關(guān)聯(lián)規(guī)則的挖掘。改進(jìn)算法基于一種新的數(shù)據(jù)庫(kù)分隔方法來(lái)分隔數(shù)據(jù)庫(kù)，并對(duì)分隔得到的各數(shù)據(jù)庫(kù)子集用Fp－Growth算法進(jìn)行約束頻繁項(xiàng)集挖掘?；谌齻€(gè)測(cè)試數(shù)據(jù)集上的實(shí)驗(yàn)測(cè)試，對(duì)改進(jìn)算法與Fp－Growth算法的運(yùn)行情況進(jìn)行了比較分析?？梢缘贸鲞@樣的結(jié)論，如果最小置信支持度較小或數(shù)據(jù)庫(kù)很大時(shí)，F(xiàn)p－Growth算法單獨(dú)使用時(shí)需要十分巨大的內(nèi)存，而改進(jìn)的數(shù)據(jù)庫(kù)劃分策略克服了這種缺陷，明顯減小了占用的內(nèi)存，并導(dǎo)致比更高的挖掘速度，特別適合于對(duì)大型數(shù)據(jù)庫(kù)的數(shù)據(jù)關(guān)聯(lián)規(guī)則的挖掘。并且改進(jìn)算法創(chuàng)建子集的時(shí)間開(kāi)銷也有所縮短，使得改進(jìn)算法的運(yùn)行速度更快了。

3.結(jié)束語(yǔ)

雖然Fp－Growth數(shù)據(jù)關(guān)聯(lián)挖掘算法比以往的挖掘算法在求解性能上有了較大的改進(jìn)，但仍然存在2個(gè)主要缺點(diǎn):建樹(shù)和挖掘過(guò)程都要求占用大量的內(nèi)存;挖掘大型數(shù)據(jù)庫(kù)時(shí)運(yùn)算速度慢。以Fp－Growth算法為基礎(chǔ)，針對(duì)其存在的不足，本文提出一種改進(jìn)的數(shù)據(jù)關(guān)聯(lián)挖掘算法，改進(jìn)后的Fp－Growth算法的主要性能得到一定程度的提高，算法有效性在幾個(gè)具體應(yīng)用中得到體現(xiàn)。

［1］N.Pasquier，YBastide，R.Taouil，and L.Lakhal.Closed set based discovery of small covers for association rules［J］.Proc.BDA conL，October 1999.361—381.

［2］Brachman，R.，and Anand，T.The Process of Knowledge Discovery Databases［J］:A Human － Centered Approach，In Advance in Knowledge Discovery and DatMining，37—58，eds.U.Fryyad，G.Piatetsky—Shapiro.P.Smyth and R.Uthurusamy.Menlo Park.Calif，APress.1996.

［3］Jackson G.A.，Leclair R.S.，Ohmer C.M.，et a1.Rough set applied to materials data.Acta Material ia，1996，44(11).4475—4484.

［4］ Wang Dexing，Hu Xuegang，Wang Hao.The Research on Model of MiningAssociation Rules Based on Quantitative Extended Concept Lattice［J］.IEEE The First International Conference on Machine Learning and Cybernetics，Nov.4 －5，2002，Beijing.

［5］文拯.關(guān)聯(lián)規(guī)則算法的研究［D］:［碩士學(xué)位論文］.長(zhǎng)沙:中南大學(xué)信息科學(xué)與工程學(xué)院，2009