數(shù)據(jù)挖掘系列關(guān)聯(lián)規(guī)則FpGrowth算法

上一篇介紹了關(guān)聯(lián)規(guī)則挖掘的一些基本概念和經(jīng)典的Apriori算法，Aprori算法利用頻繁集的兩個(gè)特性，過(guò)濾了很多無(wú)關(guān)的集合，效率提高不少，但是我們發(fā)現(xiàn)Apriori算法是一個(gè)候選消除算法，每一次消除都需要掃描一次所有數(shù)據(jù)記錄，造成整個(gè)算法在面臨大數(shù)據(jù)集時(shí)顯得無(wú)能為力。今天我們介紹一個(gè)新的算法挖掘頻繁項(xiàng)集，效率比Aprori算法高很多。

FpGrowth算法通過(guò)構(gòu)造一個(gè)樹(shù)結(jié)構(gòu)來(lái)壓縮數(shù)據(jù)記錄，使得挖掘頻繁項(xiàng)集只需要掃描兩次數(shù)據(jù)記錄，而且該算法不需要生成候選集合，所以效率會(huì)比較高。我們還是以上一篇中用的數(shù)據(jù)集為例： 

一、構(gòu)造FpTree

FpTree是一種樹(shù)結(jié)構(gòu)，樹(shù)結(jié)構(gòu)定義如下： 

樹(shù)的每一個(gè)結(jié)點(diǎn)代表一個(gè)項(xiàng)，這里我們先不著急看樹(shù)的結(jié)構(gòu)，我們演示一下FpTree的構(gòu)造過(guò)程，F(xiàn)pTree構(gòu)造好后自然明白了樹(shù)的結(jié)構(gòu)。假設(shè)我們的最小絕對(duì)支持度是3。

Step 1：掃描數(shù)據(jù)記錄，生成一級(jí)頻繁項(xiàng)集，并按出現(xiàn)次數(shù)由多到少排序，如下所示： 

可以看到，雞蛋和可樂(lè)沒(méi)有出現(xiàn)在上表中，因?yàn)榭蓸?lè)只出現(xiàn)2次，雞蛋只出現(xiàn)1次，小于最小支持度，因此不是頻繁項(xiàng)集，根據(jù)Apriori定理，非頻繁項(xiàng)集的超集一定不是頻繁項(xiàng)集，所以可樂(lè)和雞蛋不需要再考慮。

Step 2：再次掃描數(shù)據(jù)記錄，對(duì)每條記錄中出現(xiàn)在Step 1產(chǎn)生的表中的項(xiàng)，按表中的順序排序。初始時(shí)，新建一個(gè)根結(jié)點(diǎn)，標(biāo)記為null；

1）第一條記錄：{牛奶,面包}，按Step 1表過(guò)濾排序得到依然為{牛奶,面包}，新建一個(gè)結(jié)點(diǎn)，idName為{牛奶}，將其插入到根節(jié)點(diǎn)下，并設(shè)置count為1，然后新建一個(gè){面包}結(jié)點(diǎn)，插入到{牛奶}結(jié)點(diǎn)下面，插入后如下所示：

2）第二條記錄：{面包,尿布,啤酒,雞蛋}，過(guò)濾并排序后為：{面包,尿布,啤酒}，發(fā)現(xiàn)根結(jié)點(diǎn)沒(méi)有包含{面包}的兒子（有一個(gè){面包}孫子但不是兒子），因此新建一個(gè){面包}結(jié)點(diǎn)，插在根結(jié)點(diǎn)下面，這樣根結(jié)點(diǎn)就有了兩個(gè)孩子，隨后新建{尿布}結(jié)點(diǎn)插在{面包}結(jié)點(diǎn)下面，新建{啤酒}結(jié)點(diǎn)插在{尿布}下面，插入后如下所示：

3）第三條記錄：{牛奶,尿布,啤酒,可樂(lè)}，過(guò)濾并排序后為：{牛奶,尿布,啤酒}，這時(shí)候發(fā)現(xiàn)根結(jié)點(diǎn)有兒子{牛奶}，因此不需要新建結(jié)點(diǎn)，只需將原來(lái)的{牛奶}結(jié)點(diǎn)的count加1即可，往下發(fā)現(xiàn){牛奶}結(jié)點(diǎn)有一個(gè)兒子{尿布}，于是新建{尿布}結(jié)點(diǎn)，并插入到{牛奶}結(jié)點(diǎn)下面，隨后新建{啤酒}結(jié)點(diǎn)插入到{尿布}結(jié)點(diǎn)后面。插入后如下圖所示：

4）第四條記錄：{面包,牛奶,尿布,啤酒}，過(guò)濾并排序后為：{牛奶，面包,尿布,啤酒}，這時(shí)候發(fā)現(xiàn)根結(jié)點(diǎn)有兒子{牛奶}，因此不需要新建結(jié)點(diǎn)，只需將原來(lái)的{牛奶}結(jié)點(diǎn)的count加1即可，往下發(fā)現(xiàn){牛奶}結(jié)點(diǎn)有一個(gè)兒子{面包}，于是也不需要新建{面包}結(jié)點(diǎn)，只需將原來(lái){面包}結(jié)點(diǎn)的count加1，由于這個(gè){面包}結(jié)點(diǎn)沒(méi)有兒子，此時(shí)需新建{尿布}結(jié)點(diǎn)，插在{面包}結(jié)點(diǎn)下面，隨后新建{啤酒}結(jié)點(diǎn)，插在{尿布}結(jié)點(diǎn)下面，插入后如下圖所示：

5）第五條記錄：{面包,牛奶,尿布,可樂(lè)}，過(guò)濾并排序后為：{牛奶，面包,尿布}，檢查發(fā)現(xiàn)根結(jié)點(diǎn)有{牛奶}兒子，{牛奶}結(jié)點(diǎn)有{面包}兒子，{面包}結(jié)點(diǎn)有{尿布}兒子，本次插入不需要新建結(jié)點(diǎn)只需更新count即可，示意圖如下：

按照上面的步驟，我們已經(jīng)基本構(gòu)造了一棵FpTree（Frequent Pattern Tree），樹(shù)中每天路徑代表一個(gè)項(xiàng)集，因?yàn)樵S多項(xiàng)集有公共項(xiàng)，而且出現(xiàn)次數(shù)越多的項(xiàng)越可能是公公項(xiàng)，因此按出現(xiàn)次數(shù)由多到少的順序可以節(jié)省空間，實(shí)現(xiàn)壓縮存儲(chǔ)，另外我們需要一個(gè)表頭和對(duì)每一個(gè)idName相同的結(jié)點(diǎn)做一個(gè)線索，方便后面使用，線索的構(gòu)造也是在建樹(shù)過(guò)程形成的，但為了簡(jiǎn)化FpTree的生成過(guò)程，我沒(méi)有在上面提到，這個(gè)在代碼有體現(xiàn)的，添加線索和表頭的Fptree如下：

至此，整個(gè)FpTree就構(gòu)造好了，在下面的挖掘過(guò)程中我們會(huì)看到表頭和線索的作用。

二、利用FpTree挖掘頻繁項(xiàng)集

FpTree建好后，就可以進(jìn)行頻繁項(xiàng)集的挖掘，挖掘算法稱為FpGrowth（Frequent Pattern Growth）算法，挖掘從表頭header的最后一個(gè)項(xiàng)開(kāi)始。

1）此處即從{啤酒}開(kāi)始，根據(jù){啤酒}的線索鏈找到所有{啤酒}結(jié)點(diǎn)，然后找出每個(gè){啤酒}結(jié)點(diǎn)的分支：{牛奶，面包，尿布，啤酒：1}，{牛奶，尿布，啤酒:1}，{面包，尿布，啤酒:1}，其中的“1”表示出現(xiàn)1次，注意，雖然{牛奶}出現(xiàn)4次，但{牛奶，面包，尿布，啤酒}只同時(shí)出現(xiàn)1次，因此分支的count是由后綴結(jié)點(diǎn){啤酒}的count決定的，除去{啤酒}，我們得到對(duì)應(yīng)的前綴路徑{牛奶，面包，尿布：1}，{牛奶，尿布:1}，{面包，尿布:1}，根據(jù)前綴路徑我們可以生成一顆條件FpTree，構(gòu)造方式跟之前一樣，此處的數(shù)據(jù)記錄變?yōu)椋?/span>

絕對(duì)支持度依然是3，構(gòu)造得到的FpTree為：

構(gòu)造好條件樹(shù)后，對(duì)條件樹(shù)進(jìn)行遞歸挖掘，當(dāng)條件樹(shù)只有一條路徑時(shí)，路徑的所有組合即為條件頻繁集，假設(shè){啤酒}的條件頻繁集為{S1,S2,S3}，則{啤酒}的頻繁集為{S1+{啤酒},S2+{啤酒},S3+{啤酒}}，即{啤酒}的頻繁集一定有相同的后綴{啤酒}，此處的條件頻繁集為：{{}，{尿布}}，于是{啤酒}的頻繁集為{{啤酒}{尿布，啤酒}}。

2）接下來(lái)找header表頭的倒數(shù)第二個(gè)項(xiàng){尿布}的頻繁集，同上可以得到{尿布}的前綴路徑為：{面包：1}，{牛奶：1}，{牛奶，面包：2}，條件FpTree的數(shù)據(jù)集為：

注意{牛奶，面包：2}，即{牛奶，面包}的count為2，所以在{牛奶，面包}重復(fù)了兩次，這樣做的目的是可以利用之前構(gòu)造FpTree的算法來(lái)構(gòu)造條件Fptree，不過(guò)這樣效率會(huì)降低，試想如果{牛奶，面包}的count為20000，那么就需要展開(kāi)成20000條記錄，然后進(jìn)行20000次count更新，而事實(shí)上只需要對(duì)count更新一次到20000即可。這是實(shí)現(xiàn)上的優(yōu)化細(xì)節(jié)，實(shí)踐中當(dāng)注意。構(gòu)造的條件FpTree為：

 　　這顆條件樹(shù)已經(jīng)是單一路徑，路徑上的所有組合即為條件頻繁集：{{}，{牛奶}，{面包}，{牛奶，面包}}，加上{尿布}后，又得到一組頻繁項(xiàng)集{{尿布}，{牛奶，尿布}，{面包，尿布}，{牛奶，面包，尿布}}，這組頻繁項(xiàng)集一定包含一個(gè)相同的后綴：{尿布}，并且不包含{啤酒}，因此這一組頻繁項(xiàng)集與上一組不會(huì)重復(fù)。

重復(fù)以上步驟，對(duì)header表頭的每個(gè)項(xiàng)進(jìn)行挖掘，即可得到整個(gè)頻繁項(xiàng)集，可以證明（嚴(yán)謹(jǐn)?shù)乃惴ê妥C明可見(jiàn)參考文獻(xiàn)[1]），頻繁項(xiàng)集即不重復(fù)也不遺漏。

程序的實(shí)現(xiàn)代碼還是放在我的github上，這里看一下運(yùn)行結(jié)果：

另外我下載了一個(gè)購(gòu)物籃的數(shù)據(jù)集，數(shù)據(jù)量較大，測(cè)試了一下FpGrowth的效率還是不錯(cuò)的。FpGrowth算法的平均效率遠(yuǎn)高于Apriori算法，但是它并不能保證高效率，它的效率依賴于數(shù)據(jù)集，當(dāng)數(shù)據(jù)集中的頻繁項(xiàng)集的沒(méi)有公共項(xiàng)時(shí)，所有的項(xiàng)集都掛在根結(jié)點(diǎn)上，不能實(shí)現(xiàn)壓縮存儲(chǔ)，而且Fptree還需要其他的開(kāi)銷，需要存儲(chǔ)空間更大，使用FpGrowth算法前，對(duì)數(shù)據(jù)分析一下，看是否適合用FpGrowth算法。