99999久久久久久亚洲,欧美人与禽猛交狂配,高清日韩av在线影院,一个人在线高清免费观看,啦啦啦在线视频免费观看www

熱線電話:13121318867

登錄
首頁(yè)精彩閱讀數(shù)據(jù)挖掘系列關(guān)聯(lián)規(guī)則FpGrowth算法
數(shù)據(jù)挖掘系列關(guān)聯(lián)規(guī)則FpGrowth算法
2016-08-15
收藏

數(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ù)集為例: 

TID Items
T1 {牛奶,面包}
T2 {面包,尿布,啤酒,雞蛋}
T3 {牛奶,尿布,啤酒,可樂(lè)}
T4 {面包,牛奶,尿布,啤酒}
T5 {面包,牛奶,尿布,可樂(lè)}

一、構(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ù)由多到少排序,如下所示: 

Item Count
牛奶 4
面包 4
尿布 4
啤酒 3

可以看到,雞蛋和可樂(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>

TID Items
T1 {牛奶,面包,尿布}
T2 {牛奶,尿布}
T3 {面包,尿布}

絕對(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ù)集為:

TID Items
T1 {面包}
T2 {牛奶}
T3 {牛奶,面包}
T4 {牛奶,面包}

注意{牛奶,面包: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算法。


數(shù)據(jù)分析咨詢請(qǐng)掃描二維碼

若不方便掃碼,搜微信號(hào):CDAshujufenxi

數(shù)據(jù)分析師資訊
更多

OK
客服在線
立即咨詢
客服在線
立即咨詢
') } function initGt() { var handler = function (captchaObj) { captchaObj.appendTo('#captcha'); captchaObj.onReady(function () { $("#wait").hide(); }).onSuccess(function(){ $('.getcheckcode').removeClass('dis'); $('.getcheckcode').trigger('click'); }); window.captchaObj = captchaObj; }; $('#captcha').show(); $.ajax({ url: "/login/gtstart?t=" + (new Date()).getTime(), // 加隨機(jī)數(shù)防止緩存 type: "get", dataType: "json", success: function (data) { $('#text').hide(); $('#wait').show(); // 調(diào)用 initGeetest 進(jìn)行初始化 // 參數(shù)1:配置參數(shù) // 參數(shù)2:回調(diào),回調(diào)的第一個(gè)參數(shù)驗(yàn)證碼對(duì)象,之后可以使用它調(diào)用相應(yīng)的接口 initGeetest({ // 以下 4 個(gè)配置參數(shù)為必須,不能缺少 gt: data.gt, challenge: data.challenge, offline: !data.success, // 表示用戶后臺(tái)檢測(cè)極驗(yàn)服務(wù)器是否宕機(jī) new_captcha: data.new_captcha, // 用于宕機(jī)時(shí)表示是新驗(yàn)證碼的宕機(jī) product: "float", // 產(chǎn)品形式,包括:float,popup width: "280px", https: true // 更多配置參數(shù)說(shuō)明請(qǐng)參見(jiàn):http://docs.geetest.com/install/client/web-front/ }, handler); } }); } function codeCutdown() { if(_wait == 0){ //倒計(jì)時(shí)完成 $(".getcheckcode").removeClass('dis').html("重新獲取"); }else{ $(".getcheckcode").addClass('dis').html("重新獲取("+_wait+"s)"); _wait--; setTimeout(function () { codeCutdown(); },1000); } } function inputValidate(ele,telInput) { var oInput = ele; var inputVal = oInput.val(); var oType = ele.attr('data-type'); var oEtag = $('#etag').val(); var oErr = oInput.closest('.form_box').next('.err_txt'); var empTxt = '請(qǐng)輸入'+oInput.attr('placeholder')+'!'; var errTxt = '請(qǐng)輸入正確的'+oInput.attr('placeholder')+'!'; var pattern; if(inputVal==""){ if(!telInput){ errFun(oErr,empTxt); } return false; }else { switch (oType){ case 'login_mobile': pattern = /^1[3456789]\d{9}$/; if(inputVal.length==11) { $.ajax({ url: '/login/checkmobile', type: "post", dataType: "json", data: { mobile: inputVal, etag: oEtag, page_ur: window.location.href, page_referer: document.referrer }, success: function (data) { } }); } break; case 'login_yzm': pattern = /^\d{6}$/; break; } if(oType=='login_mobile'){ } if(!!validateFun(pattern,inputVal)){ errFun(oErr,'') if(telInput){ $('.getcheckcode').removeClass('dis'); } }else { if(!telInput) { errFun(oErr, errTxt); }else { $('.getcheckcode').addClass('dis'); } return false; } } return true; } function errFun(obj,msg) { obj.html(msg); if(msg==''){ $('.login_submit').removeClass('dis'); }else { $('.login_submit').addClass('dis'); } } function validateFun(pat,val) { return pat.test(val); }