
數(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
LSTM 模型輸入長(zhǎng)度選擇技巧:提升序列建模效能的關(guān)鍵? 在循環(huán)神經(jīng)網(wǎng)絡(luò)(RNN)家族中,長(zhǎng)短期記憶網(wǎng)絡(luò)(LSTM)憑借其解決長(zhǎng)序列 ...
2025-07-11CDA 數(shù)據(jù)分析師報(bào)考條件詳解與準(zhǔn)備指南? ? 在數(shù)據(jù)驅(qū)動(dòng)決策的時(shí)代浪潮下,CDA 數(shù)據(jù)分析師認(rèn)證愈發(fā)受到矚目,成為眾多有志投身數(shù) ...
2025-07-11數(shù)據(jù)透視表中兩列相乘合計(jì)的實(shí)用指南? 在數(shù)據(jù)分析的日常工作中,數(shù)據(jù)透視表憑借其強(qiáng)大的數(shù)據(jù)匯總和分析功能,成為了 Excel 用戶 ...
2025-07-11尊敬的考生: 您好! 我們誠(chéng)摯通知您,CDA Level I和 Level II考試大綱將于 2025年7月25日 實(shí)施重大更新。 此次更新旨在確保認(rèn) ...
2025-07-10BI 大數(shù)據(jù)分析師:連接數(shù)據(jù)與業(yè)務(wù)的價(jià)值轉(zhuǎn)化者? ? 在大數(shù)據(jù)與商業(yè)智能(Business Intelligence,簡(jiǎn)稱 BI)深度融合的時(shí)代,BI ...
2025-07-10SQL 在預(yù)測(cè)分析中的應(yīng)用:從數(shù)據(jù)查詢到趨勢(shì)預(yù)判? ? 在數(shù)據(jù)驅(qū)動(dòng)決策的時(shí)代,預(yù)測(cè)分析作為挖掘數(shù)據(jù)潛在價(jià)值的核心手段,正被廣泛 ...
2025-07-10數(shù)據(jù)查詢結(jié)束后:分析師的收尾工作與價(jià)值深化? ? 在數(shù)據(jù)分析的全流程中,“query end”(查詢結(jié)束)并非工作的終點(diǎn),而是將數(shù) ...
2025-07-10CDA 數(shù)據(jù)分析師考試:從報(bào)考到取證的全攻略? 在數(shù)字經(jīng)濟(jì)蓬勃發(fā)展的今天,數(shù)據(jù)分析師已成為各行業(yè)爭(zhēng)搶的核心人才,而 CDA(Certi ...
2025-07-09【CDA干貨】單樣本趨勢(shì)性檢驗(yàn):捕捉數(shù)據(jù)背后的時(shí)間軌跡? 在數(shù)據(jù)分析的版圖中,單樣本趨勢(shì)性檢驗(yàn)如同一位耐心的偵探,專注于從單 ...
2025-07-09year_month數(shù)據(jù)類型:時(shí)間維度的精準(zhǔn)切片? ? 在數(shù)據(jù)的世界里,時(shí)間是最不可或缺的維度之一,而year_month數(shù)據(jù)類型就像一把精準(zhǔn) ...
2025-07-09CDA 備考干貨:Python 在數(shù)據(jù)分析中的核心應(yīng)用與實(shí)戰(zhàn)技巧? ? 在 CDA 數(shù)據(jù)分析師認(rèn)證考試中,Python 作為數(shù)據(jù)處理與分析的核心 ...
2025-07-08SPSS 中的 Mann-Kendall 檢驗(yàn):數(shù)據(jù)趨勢(shì)與突變分析的有力工具? ? ? 在數(shù)據(jù)分析的廣袤領(lǐng)域中,準(zhǔn)確捕捉數(shù)據(jù)的趨勢(shì)變化以及識(shí)別 ...
2025-07-08備戰(zhàn) CDA 數(shù)據(jù)分析師考試:需要多久?如何規(guī)劃? CDA(Certified Data Analyst)數(shù)據(jù)分析師認(rèn)證作為國(guó)內(nèi)權(quán)威的數(shù)據(jù)分析能力認(rèn)證 ...
2025-07-08LSTM 輸出不確定的成因、影響與應(yīng)對(duì)策略? 長(zhǎng)短期記憶網(wǎng)絡(luò)(LSTM)作為循環(huán)神經(jīng)網(wǎng)絡(luò)(RNN)的一種變體,憑借獨(dú)特的門控機(jī)制,在 ...
2025-07-07統(tǒng)計(jì)學(xué)方法在市場(chǎng)調(diào)研數(shù)據(jù)中的深度應(yīng)用? 市場(chǎng)調(diào)研是企業(yè)洞察市場(chǎng)動(dòng)態(tài)、了解消費(fèi)者需求的重要途徑,而統(tǒng)計(jì)學(xué)方法則是市場(chǎng)調(diào)研數(shù) ...
2025-07-07CDA數(shù)據(jù)分析師證書考試全攻略? 在數(shù)字化浪潮席卷全球的當(dāng)下,數(shù)據(jù)已成為企業(yè)決策、行業(yè)發(fā)展的核心驅(qū)動(dòng)力,數(shù)據(jù)分析師也因此成為 ...
2025-07-07剖析 CDA 數(shù)據(jù)分析師考試題型:解鎖高效備考與答題策略? CDA(Certified Data Analyst)數(shù)據(jù)分析師考試作為衡量數(shù)據(jù)專業(yè)能力的 ...
2025-07-04SQL Server 字符串截取轉(zhuǎn)日期:解鎖數(shù)據(jù)處理的關(guān)鍵技能? 在數(shù)據(jù)處理與分析工作中,數(shù)據(jù)格式的規(guī)范性是保證后續(xù)分析準(zhǔn)確性的基礎(chǔ) ...
2025-07-04CDA 數(shù)據(jù)分析師視角:從數(shù)據(jù)迷霧中探尋商業(yè)真相? 在數(shù)字化浪潮席卷全球的今天,數(shù)據(jù)已成為企業(yè)決策的核心驅(qū)動(dòng)力,CDA(Certifie ...
2025-07-04CDA 數(shù)據(jù)分析師:開(kāi)啟數(shù)據(jù)職業(yè)發(fā)展新征程? ? 在數(shù)據(jù)成為核心生產(chǎn)要素的今天,數(shù)據(jù)分析師的職業(yè)價(jià)值愈發(fā)凸顯。CDA(Certified D ...
2025-07-03