數(shù)據(jù)挖掘(2)：關(guān)聯(lián)規(guī)則FpGrowth算法綜述

1、數(shù)據(jù)挖掘（2）:關(guān)聯(lián)規(guī)則FpGrowth算法2015/08/28-IT技術(shù)數(shù)據(jù)挖掘分享到：6An droid-精通 Activity新春特輯-Cocos搶紅包An droid攻城獅的第二門課（第 3季）An droid 攻城獅的第二門課（第 2季）原文出處：fen gfe nggirl（ 也愛數(shù)據(jù)挖掘）上一篇介紹了關(guān)聯(lián)規(guī)則挖掘的一些基本概念和經(jīng)典的Apriori算法，Aprori算法利用頻繁集的兩個(gè)特性，過濾了很多無關(guān)的集合，效率提高不少，但是我們發(fā)現(xiàn)Apriori算法是一個(gè)候選消除算法，每一次消除都需要掃描一次所有數(shù)據(jù)記錄，造成整個(gè)算法在面臨 大數(shù)據(jù)集時(shí)顯得無能為力。今天我們介紹一個(gè)新的算法

2、挖掘頻繁項(xiàng)集，效率比Aprori算法高很多。FpGrowth算法通過構(gòu)造一個(gè)樹結(jié)構(gòu)來壓縮數(shù)據(jù)記錄，使得挖掘頻繁項(xiàng)集只需要掃描兩次數(shù)據(jù)記錄，而且該算法不需要生成候選集合，所以效率會比較高。我們還是以上一篇中用的數(shù)據(jù)集為例：TIDItemsT1牛奶，面包T2面包,尿布，啤酒，雞蛋T3牛奶,尿布，啤酒，可樂T4面包,牛奶，尿布，啤酒T5面包,牛奶，尿布,可樂、構(gòu)造 FpTreeFpTree是一種樹結(jié)構(gòu)，樹結(jié)構(gòu)定義如下：public class FpNode 23 String idName;/ id 號4 List children;/ 孩子結(jié)點(diǎn)5 FpNode parent;/ 父結(jié)點(diǎn)6 FpNo

3、de next; / 下一個(gè)id號相同的結(jié)點(diǎn)7 long count; / 出現(xiàn)次數(shù)8樹的每一個(gè)結(jié)點(diǎn)代表一個(gè)項(xiàng)，這里我們先不著急看樹的結(jié)構(gòu)，我們演示一下FpTree的構(gòu)造過程，F(xiàn)pTree構(gòu)造好后自然明白了樹的結(jié)構(gòu)。假設(shè)我們的最小絕對支持度是3。Step 1 :掃描數(shù)據(jù)記錄，生成一級頻繁項(xiàng)集，并按出現(xiàn)次數(shù)由多到少排序，如下所示:Cou nt4443因?yàn)榭蓸分怀霈F(xiàn)2次，雞蛋只出現(xiàn)1次，小Apriori定理，非頻繁項(xiàng)集的超集一定不是頻Item牛奶面包尿布啤酒可以看到，雞蛋和可樂沒有出現(xiàn)在上表中, 于最小支持度，因此不是頻繁項(xiàng)集，根據(jù) 繁項(xiàng)集，所以可樂和雞蛋不需要再考慮。Step 2 :再次掃描數(shù)據(jù)

4、記錄，對每條記錄中出現(xiàn)在Step 1產(chǎn)生的表中的項(xiàng)，按表中的順序排序。初始時(shí)，新建一個(gè)根結(jié)點(diǎn)，標(biāo)記為null ；1）第一條記錄：牛奶，面包，按Step 1表過濾排序得到依然為牛奶，面包，新建一個(gè)結(jié)點(diǎn)，idName為牛奶，將其插入到根節(jié)點(diǎn)下，并設(shè)置 count為1，然后新建一個(gè)面 包結(jié)點(diǎn)，插入到牛奶結(jié)點(diǎn)下面，插入后如下所示：2）第二條記錄：面包，尿布，啤酒，雞蛋，過濾并排序后為：面包，尿布，啤酒，發(fā)現(xiàn)根結(jié) 點(diǎn)沒有包含面包的兒子（有一個(gè)面包孫子但不是兒子），因此新建一個(gè) 面包結(jié)點(diǎn)， 插在根結(jié)點(diǎn)下面，這樣根結(jié)點(diǎn)就有了兩個(gè)孩子，隨后新建 尿布結(jié)點(diǎn)插在面包結(jié)點(diǎn)下面，新建啤酒結(jié)點(diǎn)插在尿布下面，插入后如下所

5、示:count:*lnullcount:l3）第三條記錄：牛奶，尿布，啤酒，可樂，過濾并排序后為：牛奶，尿布，啤酒，這時(shí)候發(fā) 現(xiàn)根結(jié)點(diǎn)有兒子牛奶，因此不需要新建結(jié)點(diǎn)，只需將原來的 牛奶結(jié)點(diǎn)的count加1 即可，往下發(fā)現(xiàn)牛奶結(jié)點(diǎn)有一個(gè)兒子尿布，于是新建尿布結(jié)點(diǎn)，并插入到牛奶結(jié) 點(diǎn)下面，隨后新建啤酒結(jié)點(diǎn)插入到尿布結(jié)點(diǎn)后面。插入后如下圖所示：count:l4）第四條記錄：面包，牛奶，尿布，啤酒，過濾并排序后為：牛奶，面包，尿布，啤酒，這時(shí)候發(fā)現(xiàn)根結(jié)點(diǎn)有兒子牛奶，因此不需要新建結(jié)點(diǎn)，只需將原來的 牛奶結(jié)點(diǎn)的coun t加1即可，往下發(fā)現(xiàn) 件奶結(jié)點(diǎn)有一個(gè)兒子面包，于是也不需要新建面包結(jié)點(diǎn)，只 需將原來

6、面包結(jié)點(diǎn)的count加1，由于這個(gè)面包結(jié)點(diǎn)沒有兒子，此時(shí)需新建尿布 結(jié)點(diǎn)，插在面包結(jié)點(diǎn)下面，隨后新建啤酒結(jié)點(diǎn)，插在尿布結(jié)點(diǎn)下面，插入后如下圖 所示：匚 ount:-count:l5）第五條記錄：面包，牛奶，尿布，可樂，過濾并排序后為：牛奶，面包，尿布，檢查發(fā)現(xiàn)根結(jié)點(diǎn)有牛奶兒子，牛奶結(jié)點(diǎn)有面包兒子，面包結(jié)點(diǎn)有尿布兒子，本次插入不需要新建結(jié)點(diǎn)只需更新 count即可，示意圖如下：按照上面的步驟，我們已經(jīng)基本構(gòu)造了一棵FpTree ( Frequent Pattern Tree )，樹中每天路徑代表一個(gè)項(xiàng)集，因?yàn)樵S多項(xiàng)集有公共項(xiàng)，而且出現(xiàn)次數(shù)越多的項(xiàng)越可能是公 公項(xiàng)，因此按出現(xiàn)次數(shù)由多到少的順序可以

7、節(jié)省空間，實(shí)現(xiàn)壓縮存儲，另外我們需要一 個(gè)表頭和對每一個(gè)idName相同的結(jié)點(diǎn)做一個(gè)線索，方便后面使用，線索的構(gòu)造也是 在建樹過程形成的，但為了簡化FpTree的生成過程，我沒有在上面提到，這個(gè)在代碼有體現(xiàn)的，添加線索和表頭的Fptree如下:ccuntl4 牛奶4 面包4 .尿布3 啤酒counl-1至此，整個(gè)FpTree就構(gòu)造好了，在下面的挖掘過程中我們會看到表頭和線索的作用二、利用FpTree挖掘頻繁項(xiàng)集FpTree建好后，就可以進(jìn)行頻繁項(xiàng)集的挖掘，挖掘算法稱為FpGrowth (Frequent Pattern Growth )算法，挖掘從表頭 header的最后一個(gè)項(xiàng)開始。1 )此處

8、即從啤酒開始，根據(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決定的，除去啤 酒，我們得到對應(yīng)的前綴路徑牛奶，面包，尿布：1，牛奶，尿布:1，面包，尿布: 1，根據(jù)前綴路徑我們可以生成一顆條件FpTree，構(gòu)造方式跟之前一樣，此處的數(shù)據(jù)記錄變?yōu)椋篢IDItemsT1牛奶，面包，尿布T2牛奶，尿布T3面包，尿布絕對支持度依然是3，構(gòu)造得到的FpTree為:r- 3

9、尿布count:3構(gòu)造好條件樹后，對條件樹進(jìn)行遞歸挖掘，當(dāng)條件樹只有一條路徑時(shí)，路徑的所有組合即為條件頻繁集，假設(shè)啤酒的條件頻繁集為S1,S2,S3，則啤酒的頻繁集為S1+啤 酒,S2+啤酒,S3+啤酒，即啤酒的頻繁集一定有相同的后綴啤酒，此處的條件頻 繁集為：，尿布，于是啤酒的頻繁集為啤酒尿布，啤酒。2）接下來找header表頭的倒數(shù)第二個(gè)項(xiàng)尿布的頻繁集，同上可以得到尿布的前綴路徑為：面包：1，牛奶：1，牛奶，面包：2，條件FpTree的數(shù)據(jù)集為：TIDItemsT1面包T2牛奶T3牛奶，面包T4牛奶，面包注意牛奶，面包：2，即牛奶，面包的count為2，所以在牛奶，面包重復(fù)了兩次,這樣做的

10、目的是可以利用之前構(gòu)造 FpTree的算法來構(gòu)造條件 Fptree，不過這樣效率會 降低，試想如果牛奶，面包的count為20000，那么就需要展開成 20000條記錄， 然后進(jìn)行20000次count更新，而事實(shí)上只需要對 count更新一次到20000即可。 這是實(shí)現(xiàn)上的優(yōu)化細(xì)節(jié)，實(shí)踐中當(dāng)注意。構(gòu)造的條件FpTree為：這顆條件樹已經(jīng)是單一路徑，路徑上的所有組合即為條件頻繁集：，牛奶，面包，牛奶，面包，加上尿布后，又得到一組頻繁項(xiàng)集尿布，牛奶，尿布，面包，尿 布，牛奶，面包，尿布，這組頻繁項(xiàng)集一定包含一個(gè)相同的后綴：尿布，并且不包含啤酒，因此這一組頻繁項(xiàng)集與上一組不會重復(fù)。重復(fù)以上步驟，對header表頭的每個(gè)項(xiàng)進(jìn)行挖掘，即可得到整個(gè)頻繁項(xiàng)集，可以證明（嚴(yán)謹(jǐn)?shù)乃惴ê妥C明可見參考文獻(xiàn)1），頻繁項(xiàng)集即不重復(fù)也不遺漏。絕對支持度：3頻繁項(xiàng)集：面包尿布3尿布牛奶3牛奶4面包牛奶3尿布啤酒3面包4另外我下載了一個(gè)購物籃的數(shù)據(jù)集，數(shù)據(jù)量較大，測試了一下FpGrowth的效率還是不 錯(cuò)的。FpGrowth算法的平均效率遠(yuǎn)高于 Apriori算法，但是它并不能保證高效率，它 的效率