基于Fp—Tree頻繁模式的挖掘算法

趙健

Fp-Tree算法在挖掘最大頻繁模式和搜索關聯(lián)規(guī)則中得到了廣泛應用。本文闡述了Fp-Tree算法的一般過程，并對其效率瓶頸作了分析：傳統(tǒng)的Fp-Tree算法在構建頻繁樹的過程中需要遞歸地插入頻繁項，在頻繁模式的挖掘過程中需要遞歸地產生條件Fp-Tree， 這些遞歸過程會增大算法開銷，降低算法效率。本文使用非遞歸機制對Fp-Tree的構建過程做了一些改進，同時，在挖掘頻繁項過程中使用了組合頻繁前綴的方法，避免了條件Fp-Tree的產生。本文就改進算法與傳統(tǒng)算法作了對比實驗，可以看出，這些改進一定程度上提高了效率。

【關鍵詞】頻繁模式 關聯(lián)規(guī)則Fp-Tree頻繁 前綴

1 前言

隨著信息社會的發(fā)展，關聯(lián)規(guī)則挖掘在數(shù)據(jù)挖掘中的地位日益重要。關聯(lián)規(guī)則是對事物之間相互依存和關聯(lián)關系的一種描述。挖掘頻繁模式是挖掘關聯(lián)規(guī)則的基礎，針對這種模式的挖掘有一系列優(yōu)秀算法，比如Aprior算法和Fp-Tree算法。其中Aprior算法思路直觀，更易實現(xiàn)，但需多次掃描數(shù)據(jù)集并產生大量候選頻繁項集。相對的，F(xiàn)p-Tree在挖掘過程中無需產生候選集，與Aprior 相比效率更高。

但是，傳統(tǒng)的Fp-Tree算法建立Fp-Tree的過程是遞歸的，會頻繁進出棧，這就增加了內存開銷，提高算法的時間復雜性，特別是在數(shù)據(jù)集很大的情況下。同時，在頻繁模式的挖掘過程中需遞歸地構建條件Fp樹，這也會降低算法效率。本文從這兩方面改進了Fp-Tree算法，使之更有效率。

2 傳統(tǒng)的Fp-Tree算法

2.1 傳統(tǒng)Fp-Tree算法的的基本步驟

每個待插入Fp-Tree數(shù)據(jù)集的項包含四個字段：項目名稱、父結點指針、指向同名結點的指針（該指針構成同名指針的結點鏈）以及結點的支持度計數(shù)。

傳統(tǒng)Fp-Tree算法的的基本步驟如下：

（1）將頻繁項集按降序排序。掃描事務數(shù)據(jù)集D以生成頻繁1項集，并計算它們的支持度，然后對滿足不小于最小支持度要求的頻繁1項集按支持度降序排序，排序后的結果形成了一個項列表，記為L。

（2）建立FP-Tree。創(chuàng)建一個以root標記的根結點T，對數(shù)據(jù)集中的每筆事務t。刪除L中未包含的項目，對剩余項目按照L中的順序進行排序，記作[i|P]，其中i表示排序后序列的第一項，P表示剩余項。調用insert_tree（T，[i|P]）方法將交易的頻繁項插入到Fp-Tree中。若T有一個子結點N滿足條件N.項名=i.項名，也即兩個結點具有相同的項目名稱，insert_tree方法將N的計數(shù)加1。否則，創(chuàng)建新的子結點N，并將其計數(shù)置為1，然后，將結點N鏈接到其父結點T，同時，再將N鏈接到到具有相同項名的結點上（這些相同item_name的結點最終形成結點鏈結構，該鏈的頭結點為L中的同名項）。若P不為空，insert_tree（N，P）方法會遞歸地調用。掃描所有的交易后，一顆完整的Fp-Tree被構建出來。

（3）挖掘Fp-Tree以獲得頻繁項集合。挖掘過程需要在（2）中建立好的原始Fp-Tree結構中遞歸挖掘以得到頻繁項集，在此過程中還需生成很多條件Fp-Tree，具體步驟如下：逆序遍歷頻繁項列表L，對每項找出其條件模式基，以條件模式基的集合作為新的交易集（每個條件基對應一條交易）建立條件Fp-Tree，條件Fp-Tree的構建方式與原始Fp-Tree構建方式相同。條件模式基是指從根節(jié)點出發(fā)到所有以該項為最后一項（不含該項）的前綴路徑上結點的集合。條件模式基的計數(shù)為路徑中結點的最小計數(shù)。

結束條件：條件Fp_Tree為空則退出；如果新的Fp-Tree只有一條單一的路徑到葉子結點，則輸出該路徑上所有結點的組合，并上L中的頻繁項即為頻繁項集。

2.2 傳統(tǒng)Fp-Tree算法存在的問題

首先，傳統(tǒng)的Fp-Tree算法需要使用遞歸機制去插入頻繁項以形成Fp-Tree。只要剩余項列表P仍是非空集，insert_tree（N，P）過程將會被遞歸調用。根據(jù)遞歸函數(shù)調用棧的原理可知，在遞歸結束前，變量和子函數(shù)占用的存儲空間必須保留，當事務中有很多項目時，需要大量的遞歸，這時調用棧中的大量出棧入棧操作非常費時。此外，在建立好Fp-Tree之后，對頻繁模式的挖掘也是遞歸的，此過程還會產生很多條件Fp-Tree，這也拉低了算法的效率，尤其是在數(shù)據(jù)集較大的情況下。

3 改進Fp-Tree算法

3.1 構建Fp-Tree

在這種改進的算法中，沒有遞歸的函數(shù)調用，從而減少了內存使用，提高了效率。下面用表1中的交易數(shù)據(jù)為例，說明Fp-Tree的建立過程。本例中最小支持度閾值為2：

首先，根據(jù)交易數(shù)據(jù)集D，計算D中每項的支持度計數(shù)，若該計數(shù)不小于最小支持度閾值則為頻繁項，將這些項（頻繁1-項集）按支持度計數(shù)降序排列，得到頻繁項列表L：{b：7， a：6， c：6， d：2， e：2}。

接著，我們再次掃描數(shù)據(jù)集D，將其中的每筆交易數(shù)據(jù)項插入到Fp-Tree中。每次添加一筆事務的頻繁項之前，先對這些事務進行預處理：將其中的非頻繁項刪除，剩余項按照L中的順序排列。然后，讓輔助指針指向根結點，待新項添加到樹中后，讓輔助指針指向新添加的結點。每次結束一個數(shù)據(jù)集的插入之后，都讓輔助指針指向根結點。圖1顯示了將t1和t2插入Fp-Tree的具體步驟：

將整個事務數(shù)據(jù)庫的交易都處理完畢之后，得到如下Fp-Tree。

3.2 挖掘頻繁模式

改進的算法使用頻繁前綴以及頻繁子孫集連接構成頻繁項集，不必再去構建條件fp-tree，這就減小了內存開銷，在一定程度上提高了算法效率。其中頻繁前綴和頻繁子孫集的定義如下：

定義一頻繁前綴：Fp-Tree中若結點i的支持度計數(shù)大于等于最小支持度計數(shù)，則從根結點遍歷到i所經(jīng)過結點的集合稱為i的頻繁前綴。

定義二頻繁子孫：若Fp-Tree中結點i的所有同名子孫結點j的支持度計數(shù)之和大于等于最小支持度計數(shù)，則稱j為i的頻繁子孫。所有i的頻繁子孫的集合稱為i的頻繁子孫集。

以圖2中數(shù)據(jù)為例，改進后挖掘頻繁項的過程如下：

（1）自底向上后根遍歷圖中的Fp-Tree，獲得非葉子結點c，計算出c的頻繁子孫集為?。

（2）繼續(xù)后根遍歷Fp-Tree，獲得非葉子結點a。其頻繁子孫集為{c：2，e：2}，并找到a的頻繁前綴。將a和他的頻繁子集連接生成頻繁2項集{ac：2，ae：2}，再與其頻繁前綴組合得到頻繁項集FI={ac：2，ae：2，bac：2，bae：2}。

（3）繼續(xù)后根遍歷Fp-Tree，找到非葉子結點b， 其頻繁子孫集{a：4，c：4，d：2，e：2}，頻繁前綴為空。將b和他的頻繁子集連接生成頻繁2項集{ba：4，bc：4，bd：2，be：2}，與頻繁前綴組合得到頻繁項集FI={ba：4，bc：4，bd：2，be：2}。

（4）將（2）（3）步中得到的頻繁項集組合并更新其支持度，得到新的頻繁項集FI={ ba：4，bc：4，bd：2，be：2， ac：2，ae：2，bac：2，bae：2}。

（5）繼續(xù)后根遍歷Fp-Tree，得到非葉子結點a，其頻繁子孫集{c：2}，頻繁前綴為?。二者連接得到頻繁二項集{ac：2}，與頻繁前綴組合得到頻繁集FI={ac：2}。

（6）合并（4）（5）得到的頻繁集，得到新的頻繁集FI，并更新其支持度，得到新的頻繁集FI={ ba：4，bc：4，bd：2，be：2， ac：4，ae：2，bac：2，bae：2}。

（7）至此，F(xiàn)p-Tree中所有非葉子結點被遍歷一遍。將（6）中FI與L中頻繁項做并集運算，得到最后的頻繁集FI={ ba：4，bc：4，bd：2，be：2， ac：4，ae：2，bac：2，bae：2，b：7，a：6，c：6，d：2，e：2}。

4 實驗及結論

使用三種數(shù)據(jù)量規(guī)模的樣本做數(shù)據(jù)集，分別使用傳統(tǒng)及改進過的Fp-Tree算法挖掘頻繁集，記下其運行時間，如圖3所示：

圖3：算法運行時間

從圖中可以看出，在數(shù)據(jù)量較小的情況下，兩種算法花費的時間幾乎相等。但是當處理較大數(shù)據(jù)量的時候，改進的算法所花費時間明顯小于傳統(tǒng)方法，效率有了一定的提高。

參考文獻

[1]范明，孟小峰等譯.數(shù)據(jù)挖掘概念與技術[M].北京：機械工業(yè)出版社，2006：3-29.

[2]AGRAWAL R，IMIELINSKI T，SWAMI A.Mining association rules between sets of items in large database[C]//Proceedings of 1993 ACM SIGMOD Conference on Management of Data.NewYork：ACM，1993：207-216.

[3]Han，J.，Kamber，M.Data Mining Concepts and Techniques[M]，Second Edition，translated by Ming Fan and Xiaofeng Meng.Machinery Industry Press（2007）.

[4]Hui，L.，Qian，X.Non Check Mining Algorithm of Maximum Frequent Patterns in Association Rules based on FP-tree[J].Journal of Computer Applications 7（30），1923-1924（2010）.

[5]范明，李川.在FP-樹中挖掘頻繁模式而不產生條件FP-樹[J].計算機研究與發(fā)展，2003，40（08）：1216-1222.

作者單位

長治學院計算機系 山西省長治市 046011