關(guān)聯(lián)規(guī)則中FP樹算法的研究與改進

劉沖 陳曉輝 宋小小

桂林理工大學信息科學與工程學院 廣西 541004

0 引言

關(guān)聯(lián)規(guī)則是一個重要的知識發(fā)現(xiàn)(KDD)研究課題，它反映了大量數(shù)據(jù)中項目集之間有趣的關(guān)聯(lián)或相關(guān)聯(lián)系，經(jīng)過十多年的發(fā)展，目前已經(jīng)形成了一些較為有影響的挖掘算法，其中以Apriori算法，F(xiàn)P-樹算法為代表。Apriori算法通過產(chǎn)生候選頻繁項集來挖掘關(guān)聯(lián)規(guī)則，人們對其改進做了許多研究工作。2000年左右，J.Han等人提出了一種不產(chǎn)生候選項集的挖掘方法，即FP-樹算法。但是，該算法也有一些不足。

傳統(tǒng)的FP-樹算法主要缺點：(1)建樹和挖掘過程都需要占用大量的內(nèi)存。當數(shù)據(jù)庫很大或者數(shù)據(jù)庫中的頻繁1-項集的數(shù)目很大時，運行速度將大為降低；更有甚者，可能由于無法構(gòu)造基于內(nèi)存的FP樹，該算法將不能有效地工作。(2)挖掘大型數(shù)據(jù)庫時，運算速度慢。本文在深入研究 FP-樹算法的基礎(chǔ)上，提出了一種改進的 FP樹算法，新穎的分解方法分解數(shù)據(jù)庫，然后對分解后得到的各個數(shù)據(jù)庫子集進行約束頻繁項挖掘來挖掘關(guān)聯(lián)規(guī)則的新算法。

1 基本概念

設I={il,i2,……,in}是項的集合，D是數(shù)據(jù)庫事務的集合，其中每一個事務T是項的集合，使得T?I。每一個事務有一個標識符，稱作 TID。設A是一個項集，事務 T包含A當且僅當A?T。關(guān)聯(lián)規(guī)則是形如A?B的蘊含式，A?I，B?I，并且A∩B=空集。規(guī)則A?B在事務集D中成立，具有支持度s，其中s是D中事物包含A∪B的百分比。它是概率P(A∪B)規(guī)則A?B在事物集D中具有置信度c，如果D中包含A的事務同時也包含B的百分比c。這是條件概率P(B|A)。既是：

s= support(A?B)= P(A∪B);

c= confidence(A?B)= P(B|A)

同時滿足最小支持度閾值(min＿sup)和最小置信度閾值(min＿conf)的規(guī)則稱為強規(guī)則。

項的集合稱為項集(itemset)。包含k個項的項集稱為k-項集。項集的出現(xiàn)頻率是包含項集的事務數(shù)，簡稱為項集的頻率，支持度計數(shù)或計數(shù)。項集滿足最小支持度min＿sup，如果項集的出現(xiàn)頻率大于或等于min＿sup與D中事務總數(shù)的乘積。如果項集滿足最小支持度，則稱它為頻繁項集。頻繁k-項集的集合通常計作Lk。

2 FP-樹算法

FP-樹的主要思想是首先將代表頻繁物品集的數(shù)據(jù)庫壓縮成一個FP-樹，在FP-樹中包含了物品的關(guān)聯(lián)信息，然后再將這個被壓縮了的數(shù)據(jù)庫分割成一組條件數(shù)據(jù)庫(一類特殊的工程數(shù)據(jù)庫)，每一個條件數(shù)據(jù)庫與一個頻繁物品相關(guān)聯(lián)，對每一個這樣的數(shù)據(jù)庫進行單獨的挖掘。

FP-樹算法的發(fā)現(xiàn)過程可以總結(jié)如下：①對事務數(shù)據(jù)庫D進行第一次掃描，得到項目數(shù)為l的頻繁集L，同時以該頻繁集的支持行數(shù)為標準對其進行降序排序；②構(gòu)造 FP樹；③對 FP-樹進行數(shù)據(jù)挖掘，從中挖掘出關(guān)聯(lián)規(guī)則。其中，在構(gòu)造FP-樹的過程中，是對D進行第二次掃描，由其中的每一個事務產(chǎn)生一個分枝，而在對每一個事務中的項目進行處理的過程中，是按L的正向順序進行處理的，而在對FP-樹進行數(shù)據(jù)挖掘的過程中對事務的每一個項目的處理是按L的逆向順序進行的。

3 改進的FP-樹算法

FP-樹算法是當前挖掘頻繁項集算法中應用最廣，并且不需要候選集的一種關(guān)聯(lián)規(guī)則挖掘算法。針對該算法的不足，本文在 FP-樹算法的基礎(chǔ)上提一種采用分解方法分解數(shù)據(jù)庫，然后對分解后得到的各個數(shù)據(jù)庫子集進行約束頻繁項挖掘來挖掘關(guān)聯(lián)規(guī)則改進的FP-樹算法。

改進的FP-樹算法是在FP-樹算法的基礎(chǔ)上提出來的。它的主要思想是在繼承 FP-樹算法不需要產(chǎn)生侯選項集的優(yōu)點的基礎(chǔ)上，將數(shù)據(jù)庫進行頻繁1-項集的項總數(shù)次掃描，每次掃描分別得到各個頻繁1-項集的項的數(shù)據(jù)庫子集。然后分別對各項數(shù)據(jù)庫子集使用 FP-樹算法進行約束頻繁項挖掘，得到含有各個頻繁1-項集的項的頻繁項集，最后將這些頻繁項集合并起來便得到整個數(shù)據(jù)庫的所有頻繁項集。

3.1 改進的FP-樹算法發(fā)掘過程

改進的 FP-樹算法對數(shù)據(jù)庫分解，約束項挖掘以及頻繁項合并的具體過程如下:

輸入：事務數(shù)據(jù)庫D；最小支持度閾值min＿sup。

輸出：D中的頻繁項集。

算法：

(1) 掃描數(shù)據(jù)庫D，找出候選1-項集的集合，并得到它們的支持度計數(shù)(頻繁性)。然后，按照支持度計數(shù)遞減排列候選1-項集的各項，得到候選1-項集的集合F。將F中支持度小于最小支持度的項刪除，得到頻繁 1-項集的集合 L。設L={Im,Im-1,…,13,12,I1}，其中Im的支持度最高，I1的支持度最小。

(2) 再次掃描數(shù)據(jù)庫 D，將支持度小于最小支持度的項從各事務中刪除，然后按照各項的支持度計數(shù)遞減地將各事務中的項進行重新排列，得到數(shù)據(jù)庫為D′。

(3) 根據(jù)頻繁1-項集L中的各項的支持度計數(shù)，按照以下規(guī)則由小到大依次構(gòu)造各項的數(shù)據(jù)庫子集，并利用 FP-樹算法對其進行約束頻繁項挖掘：

對于L中的每個項Ii(i=m,m-1,…,1)：

第一步：掃描數(shù)據(jù)庫D′，從中提取所有含項Ii的事務，然后，刪除這些事務中支持度小于該項的支持度的項，所得事務集合便為項Ii的數(shù)據(jù)庫子集Di。

第二步：對數(shù)據(jù)庫子集D′，利用FP-樹算法進行包含項Ii的約束頻繁項集挖掘，其挖掘過程如下：

① 利用數(shù)據(jù)庫子集Di，構(gòu)造FP-樹，并創(chuàng)建項頭表HT。在這里構(gòu)造 FP-樹時，該數(shù)據(jù)庫子集中各事務項，按照頻繁1-項集L中的次序處理。因此，項頭表HT中的最后一項所標示就是項Ii的支持度計數(shù)及其節(jié)點鏈信息。

② 用項頭表HT中的最后一項所標示的信息，構(gòu)造該項的條件模式基，然后構(gòu)造其條件 FP-樹，就能在該條件 FP-樹上挖掘出包含該項的頻繁項集CLi，完成在數(shù)據(jù)庫子集Di上的約束頻繁項集挖掘。

(4) 當 L中所有的項的約束頻繁項集 CLi，被依次挖掘出來后，合并這些約束頻繁項集，即取這些約束頻繁項集CLi的并集，便可得到數(shù)據(jù)庫D的所有頻繁項集，結(jié)束挖掘過程。

3.2 實例說明

為了更好地描述該算法，本文通過一個實例來說明改進的FP-樹算法的挖掘過程。該實例基于表1所示的事務數(shù)據(jù)庫。該數(shù)據(jù)庫中共有10個事務。設最小支持度為3，即min＿support=30%。

表1 數(shù)據(jù)庫D

首先，對該數(shù)據(jù)庫D進行第一次掃描，找出候選1-項集F的集合及其支持計數(shù)。將F中支持度小于最小支持度3的項(I7和I6)刪除，得到頻繁1-項集L：I3，I2，I4，I5，I1；然后，重新排列該數(shù)據(jù)庫，得到數(shù)據(jù)庫D′如表2所示。

表2 重新得到的數(shù)據(jù)庫D′

其次，根據(jù)L中的各項的支持度計數(shù)，由小到大構(gòu)造各項的數(shù)據(jù)庫子集。以L中的項I5為例，項E的數(shù)據(jù)庫子集由含項 I5的四個事務{(diào)Tl，T6，T8，T10}組成，且 T6，T8中的最后一個項I1由于其支持度小于項I5的支持度而被刪除。項I5和L中其它各項的數(shù)據(jù)庫子集如下所示：

項 I1 的子集：I3，I2，I1；I3，I5，I1；I2，I5，I1

項 I5 的子集：I3，I2，I5；I3，I5；I2，I5；I3，I2，I4，I5

項 I4 的子集：I3，I4；I2，I3，I4；I2，I4；I3，I4；I3，I2，I4；I3，I2，I4

項 I2 的子集：I3，I2；I3，I2；I3，I2；I2；I2；I3，I2；I3，I2；

項I3的子集：I3；I3；I3；I3；I3；I3；I3；I3

再其次，對分解得到的各個子數(shù)據(jù)集利用 FP-樹算法進行約束頻繁項挖掘。利用各項的項頭表中的最后一項所標示的信息，構(gòu)造各項的條件模式基，然后構(gòu)造其條件 FP-樹，就能在該條件 FP-樹上挖掘出包含各項的約束頻繁項集。從實例數(shù)據(jù)庫中挖掘出來的頻繁項集及其支持度如表3所示。

表3 挖掘數(shù)據(jù)庫D所得到的頻繁項集(min＿support=30%)

4 實驗結(jié)果及分析

為了進一步驗證算法在挖掘大型數(shù)據(jù)庫方面的有效性，實驗在 Windows XP的環(huán)境，后臺數(shù)據(jù)庫采用 SQL Server2O00下進行，并用C#編程分別實現(xiàn)FP-樹算法和改進的FP-樹算法。表4是從大型通用數(shù)據(jù)庫WebDocs中隨機抽取了512M，60萬條左右的數(shù)據(jù)分別在支持度為10%，20%，30%，40%，50%的情況下進行測試所得到的結(jié)果。

表4 不同支持度下兩種算法挖掘時間

圖1 不同支持度下兩種算法挖掘時間對比圖

由圖1和表4分析知，在支持度為10%的時候FP-樹算法無法有效挖掘數(shù)據(jù)庫 WebDocs，但改進的 FP-樹算法卻能成功地挖掘數(shù)據(jù)庫。這是因為 FP-樹算法的挖掘過程是將數(shù)據(jù)庫壓縮到一棵頻繁式樹，但仍保留項集關(guān)聯(lián)信息；然后，將這種壓縮后的數(shù)據(jù)庫分成一組條件數(shù)據(jù)庫，每個關(guān)聯(lián)一個頻繁項，并分別挖掘每個數(shù)據(jù)庫。其優(yōu)點：算法的運算過簡單；對小型數(shù)據(jù)庫行挖掘時，運算速。其缺點：建樹時占用內(nèi)存大大；對大型數(shù)據(jù)進行挖掘時，F(xiàn)P-樹算法無法構(gòu)造基于內(nèi)存的FP-樹，從而導致挖掘失敗。而改進的 FP-樹算法的挖掘過程是對數(shù)據(jù)庫進行頻繁1-項集項總數(shù)次掃描，每次掃描分別得到各個項的數(shù)據(jù)庫子集。然后分別對各項數(shù)據(jù)庫子集使用 FP-樹算法進行約束頻繁項挖掘，得到含有各個頻繁1-項集的項的頻繁項集。最后，將這些頻繁項集合并起來便得到整個數(shù)據(jù)庫的所有頻繁項集。其優(yōu)點：占用內(nèi)存小；對大型數(shù)據(jù)進行挖掘時，運算速度比 FP-樹算法快。其缺點：算法的運算過程比較復雜；對小型數(shù)據(jù)進行發(fā)掘時會比FP-樹慢；創(chuàng)建子集的開銷時間大。

5 結(jié)束語

本文在FP-樹算法的基礎(chǔ)上提出了一種新的適合于大型數(shù)據(jù)庫的關(guān)聯(lián)規(guī)則挖掘新算法。新算法采用數(shù)據(jù)庫分解方法將數(shù)據(jù)庫分解，然后對分解得到的各個數(shù)據(jù)庫子集用FP-樹算法進行約束頻繁項集挖掘。當最小支持度較小，或者數(shù)據(jù)庫很大時，DFP算法由于所采用的數(shù)據(jù)庫劃分策略緩解了FP-樹算法單獨使用時對內(nèi)存的巨大需求，占用內(nèi)存小。因而，挖掘速度比FP樹算法快，更適合于大型數(shù)據(jù)庫的關(guān)聯(lián)規(guī)則挖掘算法。

[1] J.Han,M.Kamber.數(shù)據(jù)挖掘-概念與技術(shù)(影印版).[M]-高等教育出版社.2001.

[2] Jiawei Han,Micheline Kamber.范明,孟小峰等譯.數(shù)據(jù)挖掘概念與技術(shù)[M] (第2版).北京.機械工業(yè)出版社.2001.

[3] 劉喜蘋.基于FP-growth算法的關(guān)聯(lián)規(guī)則挖掘算法研究和應用.湖南大學.2006.

[4] 李志云,周國祥.一種基于 MFP樹的快速關(guān)聯(lián)規(guī)則挖掘算法.計算機技術(shù)與發(fā)展.2007.

[5] 毛國君,段立娟等.數(shù)據(jù)挖掘原理與算法.清華大學出版社.2005.

[6] 李志云,周國祥.基于 FP-Growth的關(guān)聯(lián)規(guī)則挖掘算法研究.全國第18屆計算機科學與技術(shù)應用學術(shù)會議論文集.2007.