基于FP—Tree的最大頻繁項目集挖掘算法

陳向華++劉可昂

摘要：挖掘最大頻繁項目集是關(guān)聯(lián)規(guī)則挖掘中的關(guān)鍵問題，基于Apriori產(chǎn)生候選項目集需要付出很高的代價，尤其是在存在大量強模式或長模式的時候.提出一種基于頻繁模式樹（FP-Tree）的最大頻繁項目集挖掘算MFIP-Miner（maximum frequent itemsets pattern mmer），其挖掘過程無需產(chǎn)生候選項集，從而提高挖掘效率。

關(guān)鍵詞：數(shù)據(jù)挖掘；最大頻繁項集；關(guān)聯(lián)規(guī)則；頻繁模式樹

中圖分類號：TP311

文獻(xiàn)標(biāo)識碼：A

DOI：10.3969/j.issn.1003-6970.2015.12.023

本文著錄格式：陳向華，劉可昂.基于FP-Tree的最大頻繁項目集挖掘算法[J]軟件，2015，36（12）：98-102

0 引言

關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘（簡稱關(guān)聯(lián)規(guī)則挖掘）就是從大量的數(shù)據(jù)中挖掘出有價值的描述數(shù)據(jù)項之間相互聯(lián)系的有關(guān)知識。自1993年Agrawal等人首先提出關(guān)聯(lián)規(guī)則概念以來，關(guān)聯(lián)規(guī)則挖掘便迅速受到數(shù)據(jù)挖掘域?qū)＜业膹V泛關(guān)注。在迄今十幾年中，關(guān)聯(lián)規(guī)則挖掘技術(shù)得到了較為深入的發(fā)展。其中發(fā)現(xiàn)頻繁項目集是關(guān)聯(lián)規(guī)則挖據(jù)應(yīng)用中的關(guān)鍵技術(shù)和步驟。對于頻繁項集挖掘，已經(jīng)開發(fā)了許多有效的、可伸縮的算法，由它們可以導(dǎo)出關(guān)聯(lián)和相關(guān)規(guī)則。這些算法可以分成三類：（1）類Apriori算法；（2）基于頻繁模式增長的算法，如FP-growth；（3）使用垂數(shù)據(jù)格式的算法。在如上所述的諸多算法中，計算項目集的支持?jǐn)?shù)是發(fā)現(xiàn)頻繁項目集中最耗時的工作，占據(jù)整個計算量的大部分，因此，降低候選項目集的數(shù)量是減小開銷的最好手段。

由于最大頻繁項目集中已經(jīng)隱含了所有頻繁項目集，所以可把發(fā)現(xiàn)頻繁項目集的問題轉(zhuǎn)化為發(fā)現(xiàn)最大頻繁項目集的問題.另外，某些數(shù)據(jù)挖掘應(yīng)用僅需發(fā)現(xiàn)最大頻繁項目集，而不必發(fā)現(xiàn)所有的頻繁項目集，因而發(fā)現(xiàn)最大頻繁項目集對數(shù)據(jù)挖掘具有重大意義。

目前已經(jīng)提出的可用于發(fā)現(xiàn)最大頻繁項目集的算法主要有Gunopulos等人提出算法ALL-MFS，Bayardo等人提出的算法Max-Miner，Lin等人提出的算法Pincer-Search，以及Burdick等人提出的算法Mafia，路松峰等人提出的算法DMFI，宋余慶等人提出的算法DMFIA等。上文闡述的這些算法都能有效地挖掘出事務(wù)數(shù)據(jù)庫D中的最大頻繁項目集，然而它們也存在不足之處。比如：Max-Miner雖然突破了傳統(tǒng)的白底向上的搜索策略，盡可能早地對項目集進(jìn)行修剪，但其存在的缺陷是：1）未利用白頂向下的信息進(jìn)行剪枝；2）未對MFCS進(jìn)行適當(dāng)?shù)呐判颍a(chǎn)生了多余的候選項目集；Pincer-Search雖然采用了白底向上和白頂向下的雙向搜索策略，但其在發(fā)現(xiàn)最大頻繁項目集的過程中產(chǎn)生了過多的無用候選項目集，對海量數(shù)據(jù)庫來講，將陷入NP難度的陷阱；DMFIA算法通過對D的兩次掃描，把其中的所有事務(wù)壓縮存儲到FP-Tree中，這樣在以后發(fā)現(xiàn)最大頻繁項目集的過程中僅需在FP-Tree中進(jìn)行查找，無需再掃描D，所以該算法的效率相對于Max-Miner、Pincer-Search有顯著的提高，但它沒有充分利用FP-Tree的特點，且其第k次的最大頻繁候選集是由k-l次的最大頻繁候選集中的非頻繁項目集去掉一個項目來生成，所以也產(chǎn)生了大量的無用候選項目集；Mafia算法雖然利用垂直位圖來壓縮存儲數(shù)據(jù)庫中的事務(wù)，并且在挖掘過程中也采用了有效的剪枝技術(shù)，但其仍然要維護(hù)一個數(shù)量較大的候選項目集的集合，這降低了算法的整體性能。本文提出一種基于頻繁模式樹（FP-Tree）的最大頻繁項目集挖掘算法MFIP-Miner（maximum frequent itemsets pattemminer），其挖掘過程無需產(chǎn)生候選項集，從而提高挖掘效率。

1 問題描述

顯然，任何頻繁項目集都是某最大頻繁項目集的子集，所以可以把發(fā)現(xiàn)所有頻繁項目集的問題轉(zhuǎn)化為發(fā)現(xiàn)所有最大頻繁項目集的問題.

1.2 頻繁模式樹

在Han等人定義的頻繁模式樹FP-Tree中，每個節(jié)點由節(jié)點名稱node-name、節(jié)點計數(shù)node-count、節(jié)點鏈 node-link及父節(jié)點指針node-parent四部分組成。另外，為了方便樹的遍歷，創(chuàng)建一個頻繁項目頭表Htable，它包含兩個組成部分：項目名稱item-name和項目鏈頭item-head。FP-Tree的構(gòu)造算法如下：

（1）掃描D一次，產(chǎn)生頻繁項目集合F及其支持?jǐn)?shù)，并按支持?jǐn)?shù)降序排列F生成頻繁項目列表IDF；

2 挖掘最大頻繁項集的算法MFIP-Miner

2.1 基本性質(zhì)

性質(zhì)1.在FP-Tree中，若某節(jié)點計數(shù)不小于s（s見定義1），則該節(jié)點和其前綴路徑中的節(jié)點組成的模式（項目集）必為頻繁模式。

證明：設(shè)節(jié)點Ⅳ為路徑P的后綴，且N.node-count≥s，由FP-Tree的構(gòu)造過程可知，對于Ⅳ的前綴路徑p中的任一個節(jié)點N，一定有：N'.node-count≥N.node-count≥s，由此可知N即為P中最小節(jié)點，所以由P中所有節(jié)點組成的模式的計數(shù)必大于或等于s，即為頻繁模式。證畢。

性質(zhì)2.若由某一頻繁項目T_i的條件模式基生成的條件FP-Tree中只含有單個路徑P時，則P中的所有項目與T_i的并集一定是頻繁項目集，且P∪T_i的支持?jǐn)?shù)等于T_i中葉節(jié)點的支持?jǐn)?shù)。

證明：由條件頻繁模式樹的構(gòu)造過程可知，對于某一頻繁項目T_i，在其條件頻繁模式樹中的節(jié)點必為頻繁項目節(jié)點。由于此時樹中只含有單個路徑，而且路徑中的每個節(jié)點又都是頻繁項目節(jié)點，則由性質(zhì)l可知，此路徑中的節(jié)點和項目T_i組成的模式必為頻繁模式。根據(jù)頻繁模式樹的構(gòu)造方法可知，F(xiàn)P-Tree中的葉節(jié)點的節(jié)點計數(shù)是整個路徑中最小的，因此P∪T_i的支持?jǐn)?shù)不可能大于或小于葉節(jié)點的節(jié)點計數(shù)，所以P∪T_i的支持?jǐn)?shù)等于葉節(jié)點的支持?jǐn)?shù)，證畢。

由上述性質(zhì)可知，最大頻繁項目集一定存在于由條件FP-Tree產(chǎn)生的頻繁模式中。因此MFIP-Miner算法的基本思想是：依次從Htable中取出所有的頻繁項目，對每個項目構(gòu)造其條件模式基和條件FP-Tree，對構(gòu)造的條件FP-Tree進(jìn)行如下處理：

（l）如果構(gòu)造的條件FP-Tree中只含有單個路徑，則取出該路徑中所有項目，將它們與生成該條件FP-Tree的項目合并，組成一個頻繁模式，然后判斷此頻繁模式是否是MFIP中某項目集的子集，若不是，則此頻繁模式就為最大頻繁模式，并將其放入MFIP中，同時刪除MFIP中是該最大頻繁模式子集的項目集，若是則舍去。

（2）如果構(gòu)造的條件中含有多個路徑，則依次從該條件FP-Tree所對應(yīng)的Htable中取出所有項目，構(gòu)造每個項目的條件FP-Tree，找出其包含的最大頻繁模式。可見整個發(fā)現(xiàn)過程是遞歸進(jìn)行的，直到找出所有最大頻繁模式為止

（3）在挖掘過程中，若發(fā)現(xiàn)樹中的某個節(jié)點Ⅳ的計數(shù)不小于s，則從Htable中取出所有排列在N.node-name前面的項目組成集合X；然后，通過Ⅳ的同名節(jié)點鏈，找出節(jié)點鏈中所有計數(shù)不小于s的同名節(jié)點；最后，遍歷每條以同名節(jié)點為后綴的路徑P，檢查X是否存在于P中，一旦發(fā)現(xiàn)了這樣的路徑，則可將在當(dāng)前頻繁模式（或條件頻繁模式）樹中的挖掘過程終止。

2.2 算法MFIP-Miner

輸入：最小支持度X._{sup D}，在此X._{sup D}下構(gòu)造的FP-Tree T；

輸出：事務(wù)數(shù)據(jù)庫D中滿足X._{sup D}要求的最大頻繁項目集的集合MFIP。

（1）MFIP=NULL：

3 算法實現(xiàn)與比較

3.1 測試機配置

本文所用的測試機為Lenovo臺式機，其配置是：CPU為Pentium3.2GHz，操作系統(tǒng)為win7旗艦版，內(nèi)存為4G，并選用R語言，在Eclipse+StatET編程環(huán)境中實現(xiàn)了算法MFIP-Miner算法和Mafia算法。

3.2 測試數(shù)據(jù)庫的選擇

為了能綜合測試MFIP-Miner算法的性能，本文選用了兩種類型的數(shù)據(jù)庫：Chess和Mushroom（它們可以從UCI Machine Leaming Repository上免費獲得）

3.3 對比算法選擇

本文通過對比MFIP-Miner算與Mafia算法在Chess和Mushroom數(shù)據(jù)庫運行效率，來分析和驗證MFIP-Miner算法的性能，之所以選擇Mafia算法作為比較的對象，主要是因為該算法是目前公認(rèn)挖掘最大頻繁項目集最有效的算法。

3.4 在Chess數(shù)據(jù)庫上的測試分析

Chess數(shù)據(jù)庫的特點是最大頻繁項目集的分布比較對稱，而且大多數(shù)最大頻繁項目集的維數(shù)相對較低，平均長度約為37。從圖l中可以看出，算法MFIP-Miner在最小支持度大于20%時的執(zhí)行效率要好于算法Mafia兩到三倍。然而，當(dāng)最小支持度小于50%時算法MFIP-Miner的性能開始下降，而在最小支持度小于30%時性能下降的速度更大。產(chǎn)生這種現(xiàn)象的原因是：MFIP-Miner算法采用FP-Tree來壓縮存儲數(shù)據(jù)庫中的事務(wù)，并在該基礎(chǔ)上進(jìn)行挖掘，由于充分利用了FP-Tree的特點，在挖掘過程中不需要產(chǎn)生候選項目集，這使其在挖掘過程中具有較高的效率。然而，MFIP-Miner算法在挖掘過程中需要產(chǎn)生條件頻繁模式基，當(dāng)這種模式基數(shù)量巨大時會占用較多內(nèi)存，以致復(fù)雜的內(nèi)存管理花費了一些額外的開銷，使算法的性能趨于下降。而對于Mafia算法來說，由于其是基于Apriori算法的挖掘思想，需要生成大量的候選項目集，并對其進(jìn)行支持度計算和頻繁性檢驗，因此Mafia算法需要花費大量的計算開銷。但是，Mafia算法采用了一種垂直位圖結(jié)構(gòu)來表示事務(wù)，并且采用了一些有效的剪枝技術(shù)，因此，總的來說其在挖掘最大頻繁項目集方面也是很有效的。

3.5 在Mushroom數(shù)據(jù)庫上的測試分析

Mushroom數(shù)據(jù)庫的特點是最大頻繁項目集的分布比較密集，其中每個事務(wù)的長度為23，而絕大多數(shù)最大頻繁項目集的長度為20，因此，每個最大頻繁項目集中都有一些項目存在于每個事務(wù)中。從圖2中可以看出，MFIP-Miner算法在這種數(shù)據(jù)庫中的執(zhí)行效率要好于在上面兩個數(shù)據(jù)庫中的執(zhí)行效率，總的執(zhí)行時間較少，這說明MFIP-Minerr算法對最大頻繁項目集較長且分布密集的數(shù)據(jù)庫有較大優(yōu)勢。和Mafia算法相比，MFIP-Miner算法略優(yōu)于前者，這也說明Mafia算法對最大頻繁項目集較長的挖掘也很有效。

4 結(jié)論

本文提出的MFIP-Miner算法能高效地挖掘出事務(wù)數(shù)據(jù)庫中的最大頻繁項目集，其在挖掘過程中不需要產(chǎn)生最大頻繁候選項目集，而且由于挖掘過程只需掃描事務(wù)數(shù)據(jù)庫D一次，從而提高了算法的執(zhí)行效率。