基于FP—Tree的最大頻繁項(xiàng)目集挖掘算法

陳向華++劉可昂

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

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

中圖分類號(hào)：TP311

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

DOI：10.3969/j.issn.1003-6970.2015.12.023

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

0 引言

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

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

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

1 問題描述

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

1.2 頻繁模式樹

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

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

2 挖掘最大頻繁項(xiàng)集的算法MFIP-Miner

2.1 基本性質(zhì)

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

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

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

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

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

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

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

（3）在挖掘過程中，若發(fā)現(xiàn)樹中的某個(gè)節(jié)點(diǎn)Ⅳ的計(jì)數(shù)不小于s，則從Htable中取出所有排列在N.node-name前面的項(xiàng)目組成集合X；然后，通過Ⅳ的同名節(jié)點(diǎn)鏈，找出節(jié)點(diǎn)鏈中所有計(jì)數(shù)不小于s的同名節(jié)點(diǎn)；最后，遍歷每條以同名節(jié)點(diǎn)為后綴的路徑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ù)庫(kù)D中滿足X._{sup D}要求的最大頻繁項(xiàng)目集的集合MFIP。

（1）MFIP=NULL：

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

3.1 測(cè)試機(jī)配置

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

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

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

3.3 對(duì)比算法選擇

本文通過對(duì)比MFIP-Miner算與Mafia算法在Chess和Mushroom數(shù)據(jù)庫(kù)運(yùn)行效率，來(lái)分析和驗(yàn)證MFIP-Miner算法的性能，之所以選擇Mafia算法作為比較的對(duì)象，主要是因?yàn)樵撍惴ㄊ悄壳肮J(rèn)挖掘最大頻繁項(xiàng)目集最有效的算法。

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

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

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

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

4 結(jié)論

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