關聯規則中FP樹算法的研究與改進

劉沖 陳曉輝 宋小小

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

0 引言

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

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

1 基本概念

設I={il,i2,……,in}是項的集合，D是數據庫事務的集合，其中每一個事務T是項的集合，使得T?I。每一個事務有一個標識符，稱作 TID。設A是一個項集，事務 T包含A當且僅當A?T。關聯規則是形如A?B的蘊含式，A?I，B?I，并且A∩B=空集。規則A?B在事務集D中成立，具有支持度s，其中s是D中事物包含A∪B的百分比。它是概率P(A∪B)規則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)的規則稱為強規則。

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

2 FP-樹算法

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

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

3 改進的FP-樹算法

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

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

3.1 改進的FP-樹算法發掘過程

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

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

輸出：D中的頻繁項集。

算法：

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

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

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

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

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

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

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

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

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

3.2 實例說明

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

表1 數據庫D

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

表2 重新得到的數據庫D′

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

項 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

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

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

4 實驗結果及分析

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

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

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

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

5 結束語

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

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

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

[3] 劉喜蘋.基于FP-growth算法的關聯規則挖掘算法研究和應用.湖南大學.2006.

[4] 李志云,周國祥.一種基于 MFP樹的快速關聯規則挖掘算法.計算機技術與發展.2007.

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

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