




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
機(jī)器學(xué)習(xí)-FP-GROWTH算法李家豪機(jī)器學(xué)習(xí)-FP-GROWTH算法李家豪目錄2Apriori算法和FP-GROWTH算法的比較FP-GROWTH算法原理FP-GROWTH代碼實(shí)現(xiàn)(python)示例:從新聞網(wǎng)站點(diǎn)擊流中挖掘新聞報(bào)道目錄2Apriori算法和FP-GROWTH算法的比較FP-回憶Apriori算法3項(xiàng)集:項(xiàng)的集合稱為項(xiàng)集,即商品的組合。k項(xiàng)集:k件商品的組合,不關(guān)心商品件數(shù),僅商品的種類。頻繁項(xiàng)集:如果項(xiàng)集的相對支持度滿足給定的最小支持度閾值,則該項(xiàng)集是頻繁項(xiàng)集。強(qiáng)關(guān)聯(lián)規(guī)則:滿足給定支持度和置信度閾值的關(guān)聯(lián)規(guī)則支持度:support(A->B)=P(AB)置信度:confidence(A->B)=P(A|B)回憶Apriori算法3項(xiàng)集:項(xiàng)的集合稱為項(xiàng)集,即商品的組合回憶Apriori算法4回憶Apriori算法4回憶Apriori算法5回憶Apriori算法5Apriori算法的挑戰(zhàn)6挑戰(zhàn)多次數(shù)據(jù)庫掃描巨大數(shù)量的候補(bǔ)項(xiàng)集繁瑣的支持度計(jì)算改善Apriori:基本想法
減少掃描數(shù)據(jù)庫的次數(shù)
減少候選項(xiàng)集的數(shù)量簡化候選項(xiàng)集的支持度計(jì)算Apriori算法的挑戰(zhàn)6挑戰(zhàn)FP-GROWTH算法優(yōu)點(diǎn)相比Apriori算法需要多次掃描數(shù)據(jù)庫,F(xiàn)PGrowth只需要對數(shù)據(jù)庫掃描2次。第1次掃描事務(wù)數(shù)據(jù)庫獲得頻繁1項(xiàng)集。第2次掃描建立一顆FP-Tree樹。7FP-GROWTH算法優(yōu)點(diǎn)相比Apriori算法需要多次掃描FP-GROWTH算法原理-實(shí)例1要找總是一起購買的商品,比如[薯片,雞蛋]就是一條頻繁模式(規(guī)律)。8IDItems1牛奶,雞蛋,面包,薯片2雞蛋,爆米花,薯片,啤酒3牛奶,面包,啤酒4牛奶,雞蛋,面包,爆米花,薯片,啤酒5雞蛋,面包,薯片6雞蛋,面包,啤酒7牛奶,面包,薯片8牛奶,雞蛋,面包,黃油,薯片9牛奶,雞蛋,黃油,薯片F(xiàn)P-GROWTH算法原理-實(shí)例1要找總是一起購買的商品,比FP-GROWTH算法原理-實(shí)例1-統(tǒng)計(jì)頻次Step1:先掃描數(shù)據(jù)庫,統(tǒng)計(jì)所有商品的出現(xiàn)次數(shù)(頻數(shù)),然后按照頻數(shù)遞減排序,刪除頻數(shù)小于最小支持度的商品。設(shè)最小支持度數(shù)為:minsup=4統(tǒng)計(jì)頻數(shù):牛奶6,雞蛋7,面包7,薯片7,爆米花2,啤酒4,黃油2.降序排序:薯片7,雞蛋7,面包7,牛奶6,啤酒4(刪除小于minsup的商品)9IDItems1牛奶,雞蛋,面包,薯片2雞蛋,爆米花,薯片,啤酒3牛奶,面包,啤酒4牛奶,雞蛋,面包,爆米花,薯片,啤酒5雞蛋,面包,薯片6雞蛋,面包,啤酒7牛奶,面包,薯片8牛奶,雞蛋,面包,黃油,薯片9牛奶,雞蛋,黃油,薯片
頻繁1項(xiàng)集,記為F1FP-GROWTH算法原理-實(shí)例1-統(tǒng)計(jì)頻次Step1:先掃FP-GROWTH算法原理-實(shí)例1-重新排序10IDItems1牛奶,雞蛋,面包,薯片2雞蛋,爆米花,薯片,啤酒3牛奶,面包,啤酒4牛奶,雞蛋,面包,爆米花,薯片,啤酒5雞蛋,面包,薯片6雞蛋,面包,啤酒7牛奶,面包,薯片8牛奶,雞蛋,面包,黃油,薯片9牛奶,雞蛋,黃油,薯片IDItems1薯片,雞蛋,面包,牛奶2薯片,雞蛋,啤酒3面包,牛奶,啤酒4薯片,雞蛋,面包,牛奶,啤酒5薯片,雞蛋,面包6雞蛋,面包,啤酒7薯片,面包,牛奶8薯片,雞蛋,面包,牛奶9薯片,雞蛋,牛奶Step2:對每一條數(shù)據(jù)記錄,按照F1重新排序。FP-GROWTH算法原理-實(shí)例1-重新排序10IDItemFP-GROWTH算法原理-實(shí)例1-建立FP樹11IDItems1薯片,雞蛋,面包,牛奶2薯片,雞蛋,啤酒3面包,牛奶,啤酒4薯片,雞蛋,面包,牛奶,啤酒5薯片,雞蛋,面包6雞蛋,面包,啤酒7薯片,面包,牛奶8薯片,雞蛋,面包,牛奶9薯片,雞蛋,牛奶Step3:把第二步重新排序后的記錄,插入到fp-tree中Step3.1:插入第一條(第一步有一個(gè)虛的根節(jié)點(diǎn))FP-GROWTH算法原理-實(shí)例1-建立FP樹11IDIteFP-GROWTH算法原理-實(shí)例1-建立FP樹12IDItems1薯片,雞蛋,面包,牛奶2薯片,雞蛋,啤酒3面包,牛奶,啤酒4薯片,雞蛋,面包,牛奶,啤酒5薯片,雞蛋,面包6雞蛋,面包,啤酒7薯片,面包,牛奶8薯片,雞蛋,面包,牛奶9薯片,雞蛋,牛奶Step3.2:插入第二條。根結(jié)點(diǎn)不管,然后插入薯片,在step3.1的基礎(chǔ)上+1,則記為2;同理雞蛋記為2;啤酒在step3.1的樹上是沒有的,那么就開一個(gè)分支。FP-GROWTH算法原理-實(shí)例1-建立FP樹12IDIteFP-GROWTH算法原理-實(shí)例1-建立FP樹13IDItems1薯片,雞蛋,面包,牛奶2薯片,雞蛋,啤酒3面包,牛奶,啤酒4薯片,雞蛋,面包,牛奶,啤酒5薯片,雞蛋,面包6雞蛋,面包,啤酒7薯片,面包,牛奶8薯片,雞蛋,面包,牛奶9薯片,雞蛋,牛奶Step3.3:插入第三條FP-GROWTH算法原理-實(shí)例1-建立FP樹13IDIteFP-GROWTH算法原理-實(shí)例1-建立FP樹14IDItems1薯片,雞蛋,面包,牛奶2薯片,雞蛋,啤酒3面包,牛奶,啤酒4薯片,雞蛋,面包,牛奶,啤酒5薯片,雞蛋,面包6雞蛋,面包,啤酒7薯片,面包,牛奶8薯片,雞蛋,面包,牛奶9薯片,雞蛋,牛奶同理,剩余記錄依次插入fp-tree中。FP-GROWTH算法原理-實(shí)例1-建立FP樹14IDIteFP-GROWTH算法原理-實(shí)例1-建立FP樹15圖中左邊的一列叫做頭指針表,樹中相同名稱的節(jié)點(diǎn)要鏈接起來,鏈表的第一個(gè)元素就是頭指針表里的元素。虛線連接起來的表示同一個(gè)商品,各個(gè)連接的數(shù)字加起來就是該商品出現(xiàn)的總次數(shù)。FP-GROWTH算法原理-實(shí)例1-建立FP樹15圖中左邊的FP-GROWTH算法原理-實(shí)例1-挖掘頻繁項(xiàng)集Step4:從FP-Tree中找出頻繁項(xiàng)集。遍歷表頭項(xiàng)中的每一項(xiàng)(以“牛奶:6”為例),從FP-Tree中找到所有的“牛奶”結(jié)點(diǎn),向上遍歷它的祖先結(jié)點(diǎn),得到4條路徑,如表所示。16FP-GROWTH算法原理-實(shí)例1-挖掘頻繁項(xiàng)集Step4:FP-GROWTH算法原理-實(shí)例1-挖掘頻繁項(xiàng)集Step4:從FP-Tree中找出頻繁項(xiàng)集。對于每一條路徑上的節(jié)點(diǎn),其count都設(shè)置為牛奶的count(路徑中最末尾的商品數(shù))17FP-GROWTH算法原理-實(shí)例1-挖掘頻繁項(xiàng)集Step4:FP-GROWTH算法原理-實(shí)例1-挖掘頻繁項(xiàng)集Step4:從FP-Tree中找出頻繁項(xiàng)集。因?yàn)槊恳豁?xiàng)末尾都是牛奶,可以把牛奶去掉,得到條件模式基,此時(shí)的后綴模式是:牛奶。18FP-GROWTH算法原理-實(shí)例1-挖掘頻繁項(xiàng)集Step4:FP-GROWTH算法原理-實(shí)例2把例子簡化一下,請看以下實(shí)例219TidItems1I1,I2,I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3FP-GROWTH算法原理-實(shí)例2把例子簡化一下,請看以下實(shí)FP-GROWTH算法原理-實(shí)例2-統(tǒng)計(jì)頻次先掃描數(shù)據(jù)庫,統(tǒng)計(jì)所有商品的出現(xiàn)次數(shù)(頻數(shù))定義min_sup=2,按照頻數(shù)遞減排序,刪除頻數(shù)小于最小支持度的商品。重新排列得到頻繁1-項(xiàng)目集F20I1I2I3I4I567622I2I1I3I4I576622FP-GROWTH算法原理-實(shí)例2-統(tǒng)計(jì)頻次先掃描數(shù)據(jù)庫,統(tǒng)FP-GROWTH算法原理-實(shí)例2-重新排序21I27I16I36I42I52TidItems1I2,I1,I52I2,I43I2,I34I2,I1,I45I1,I36I2,I37I1,I38I2,I1,I3,I59I2,I1,I3FP-GROWTH算法原理-實(shí)例2-重新排序21I27I16FP-GROWTH算法原理-實(shí)例2-創(chuàng)建根結(jié)點(diǎn)和頻繁項(xiàng)目表22Item-nameNode-headI2NullI1NullI3NullI4NullI5NullNullFP-GROWTH算法原理-實(shí)例2-創(chuàng)建根結(jié)點(diǎn)和頻繁項(xiàng)目表2FP-GROWTH算法原理-實(shí)例2-加入第一個(gè)事務(wù)(I2,I1,I5)23FP-GROWTH算法原理-實(shí)例2-加入第一個(gè)事務(wù)(I2,IFP-GROWTH算法原理-實(shí)例2-加入第二個(gè)事務(wù)(I2,I4)24FP-GROWTH算法原理-實(shí)例2-加入第二個(gè)事務(wù)(I2,IFP-GROWTH算法原理-實(shí)例2-加入第三個(gè)事務(wù)(I2,I3)25FP-GROWTH算法原理-實(shí)例2-加入第三個(gè)事務(wù)(I2,IFP-GROWTH算法原理-實(shí)例2-加入第四個(gè)事務(wù)(I2,I1,I4)26FP-GROWTH算法原理-實(shí)例2-加入第四個(gè)事務(wù)(I2,IFP-GROWTH算法原理-實(shí)例2-加入第五個(gè)事務(wù)(I1,I3)27FP-GROWTH算法原理-實(shí)例2-加入第五個(gè)事務(wù)(I1,IFP-GROWTH算法原理-實(shí)例2-加入第六個(gè)事務(wù)(I2,I3)28FP-GROWTH算法原理-實(shí)例2-加入第六個(gè)事務(wù)(I2,IFP-GROWTH算法原理-實(shí)例2-加入第七個(gè)事務(wù)(I1,I3)29FP-GROWTH算法原理-實(shí)例2-加入第七個(gè)事務(wù)(I1,IFP-GROWTH算法原理-實(shí)例2-加入第八個(gè)事務(wù)(I2,I1,I3,I5)30FP-GROWTH算法原理-實(shí)例2-加入第八個(gè)事務(wù)(I2,IFP-GROWTH算法原理-實(shí)例2-加入第九個(gè)事務(wù)(I2,I1,I3)31FP-GROWTH算法原理-實(shí)例2-加入第九個(gè)事務(wù)(I2,IFP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集首先考慮I5,得到條件模式基:<(I2,I1:1)>、<I2,I1,I3:1>構(gòu)造條件FP-Tree32得到I5頻繁項(xiàng)集:{{I2,I5},{I1,I5},{I2,I1,I5}}FP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集首先考慮I5FP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集接著考慮I4,得到條件模式基:
<(I2,I1:1)>、<I2:1>構(gòu)造條件FP-Tree33得到I4頻繁項(xiàng)集:{{I2,I4}}FP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集接著考慮I4FP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集然后考慮I3,得到條件模式基:
<(I2,I1:2)>、<I2:2>、<I1:2>構(gòu)造條件FP-Tree34由于此樹不是單分支路徑,因此需要遞歸挖掘I3FP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集然后考慮I3FP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集遞歸考慮I3,此時(shí)得到I1條件模式基<(I2:2)>,即I1,I3的條件模式基為<(I2:2)>構(gòu)造條件FP-Tree35得到I3的頻繁項(xiàng)目集{{I2,I3},{I1,I3},{I2,I1,I3}}FP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集遞歸考慮I3FP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集最后考慮I1,得到條件模式基:<(I2:4)>構(gòu)造條件FP-Tree36得到I1的頻繁項(xiàng)目集:{I2,I1}FP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集最后考慮I1FP-GROWTH算法實(shí)現(xiàn)-數(shù)據(jù)處理37項(xiàng)集e,m,q,s,t,y,x,zx,s,r,o,ns,u,t,w,v,y,x,zq,p,r,t,y,x,zh,r,z,p,jz格式化處理FP-GROWTH算法實(shí)現(xiàn)-數(shù)據(jù)處理37項(xiàng)集e,m,q,s,代碼實(shí)現(xiàn)-FP樹數(shù)據(jù)結(jié)構(gòu)38代碼實(shí)現(xiàn)-FP樹數(shù)據(jù)結(jié)構(gòu)38代碼實(shí)現(xiàn)-構(gòu)造FP樹步驟39代碼實(shí)現(xiàn)-構(gòu)造FP樹步驟39代碼實(shí)現(xiàn)-構(gòu)造FP樹40代碼實(shí)現(xiàn)-構(gòu)造FP樹40代碼實(shí)現(xiàn)-構(gòu)造FP樹41代碼實(shí)現(xiàn)-構(gòu)造FP樹41代碼實(shí)現(xiàn)-構(gòu)造FP樹(updateTree函數(shù))42代碼實(shí)現(xiàn)-構(gòu)造FP樹(updateTree函數(shù))42代碼實(shí)現(xiàn)-構(gòu)造FP樹(updateHeader函數(shù))43代碼實(shí)現(xiàn)-構(gòu)造FP樹(updateHeader函數(shù))43代碼實(shí)現(xiàn)-構(gòu)造FP樹(驗(yàn)證)44代碼實(shí)現(xiàn)-構(gòu)造FP樹(驗(yàn)證)44代碼實(shí)現(xiàn)-挖掘頻繁項(xiàng)集步驟從構(gòu)建好的FP樹中抽取頻繁項(xiàng)集的步驟如下:(1)從FP樹中獲取條件模式基;(2)利用條件模式基,構(gòu)建一個(gè)條件FP樹;(3)迭代重復(fù)(1)(2),直到樹包含一個(gè)元素項(xiàng)為止。45代碼實(shí)現(xiàn)-挖掘頻繁項(xiàng)集步驟從構(gòu)建好的FP樹中抽取頻繁項(xiàng)集的步條件模式基定義條件模式基是以所查找元素項(xiàng)為結(jié)尾的路徑集合。每一條路徑其實(shí)都是一條前綴路徑。簡而言之,一條前綴路徑就是介于所查找元素項(xiàng)與樹根節(jié)點(diǎn)之間的所有內(nèi)容。每一個(gè)頻繁項(xiàng)的所有前綴路徑(條件模式基):46條件模式基定義條件模式基是以所查找元素項(xiàng)為結(jié)尾的路徑集合。每代碼實(shí)現(xiàn)-抽取條件模式基47eg:t的第1條前綴路徑prefixPath=t,s,y,x,z;代碼實(shí)現(xiàn)-抽取條件模式基47eg:t的第1條前綴路徑pref代碼實(shí)現(xiàn)-抽取條件模式基48代碼實(shí)現(xiàn)-抽取條件模式基48代碼實(shí)現(xiàn)-抽取條件模式基(驗(yàn)證)49代碼實(shí)現(xiàn)-抽取條件模式基(驗(yàn)證)49代碼實(shí)現(xiàn)-創(chuàng)建條件FP樹50代碼實(shí)現(xiàn)-創(chuàng)建條件FP樹50代碼實(shí)現(xiàn)-創(chuàng)建條件FP樹51代碼實(shí)現(xiàn)-創(chuàng)建條件FP樹51代碼實(shí)現(xiàn)-運(yùn)行52代碼實(shí)現(xiàn)-運(yùn)行52示例:從新聞網(wǎng)站點(diǎn)擊流中挖掘新聞報(bào)道-數(shù)據(jù)格式53示例:從新聞網(wǎng)站點(diǎn)擊流中挖掘新聞報(bào)道-數(shù)據(jù)格式53示例:從新聞網(wǎng)站點(diǎn)擊流中挖掘新聞報(bào)道-代碼在源數(shù)據(jù)集合中,包含將近100w條記錄,該文件中的每一行代表某個(gè)用戶瀏覽過的新聞報(bào)道。一些用戶只看過一篇報(bào)道,而有些用戶看過2498篇報(bào)道,用戶和報(bào)道被編碼成整數(shù)。54示例:從新聞網(wǎng)站點(diǎn)擊流中挖掘新聞報(bào)道-代碼在源數(shù)據(jù)集合中,包示例:從新聞網(wǎng)站點(diǎn)擊流中挖掘新聞報(bào)道-結(jié)果55示例:從新聞網(wǎng)站點(diǎn)擊流中挖掘新聞報(bào)道-結(jié)果55謝謝!56謝謝!56機(jī)器學(xué)習(xí)-FP-GROWTH算法李家豪機(jī)器學(xué)習(xí)-FP-GROWTH算法李家豪目錄58Apriori算法和FP-GROWTH算法的比較FP-GROWTH算法原理FP-GROWTH代碼實(shí)現(xiàn)(python)示例:從新聞網(wǎng)站點(diǎn)擊流中挖掘新聞報(bào)道目錄2Apriori算法和FP-GROWTH算法的比較FP-回憶Apriori算法59項(xiàng)集:項(xiàng)的集合稱為項(xiàng)集,即商品的組合。k項(xiàng)集:k件商品的組合,不關(guān)心商品件數(shù),僅商品的種類。頻繁項(xiàng)集:如果項(xiàng)集的相對支持度滿足給定的最小支持度閾值,則該項(xiàng)集是頻繁項(xiàng)集。強(qiáng)關(guān)聯(lián)規(guī)則:滿足給定支持度和置信度閾值的關(guān)聯(lián)規(guī)則支持度:support(A->B)=P(AB)置信度:confidence(A->B)=P(A|B)回憶Apriori算法3項(xiàng)集:項(xiàng)的集合稱為項(xiàng)集,即商品的組合回憶Apriori算法60回憶Apriori算法4回憶Apriori算法61回憶Apriori算法5Apriori算法的挑戰(zhàn)62挑戰(zhàn)多次數(shù)據(jù)庫掃描巨大數(shù)量的候補(bǔ)項(xiàng)集繁瑣的支持度計(jì)算改善Apriori:基本想法
減少掃描數(shù)據(jù)庫的次數(shù)
減少候選項(xiàng)集的數(shù)量簡化候選項(xiàng)集的支持度計(jì)算Apriori算法的挑戰(zhàn)6挑戰(zhàn)FP-GROWTH算法優(yōu)點(diǎn)相比Apriori算法需要多次掃描數(shù)據(jù)庫,F(xiàn)PGrowth只需要對數(shù)據(jù)庫掃描2次。第1次掃描事務(wù)數(shù)據(jù)庫獲得頻繁1項(xiàng)集。第2次掃描建立一顆FP-Tree樹。63FP-GROWTH算法優(yōu)點(diǎn)相比Apriori算法需要多次掃描FP-GROWTH算法原理-實(shí)例1要找總是一起購買的商品,比如[薯片,雞蛋]就是一條頻繁模式(規(guī)律)。64IDItems1牛奶,雞蛋,面包,薯片2雞蛋,爆米花,薯片,啤酒3牛奶,面包,啤酒4牛奶,雞蛋,面包,爆米花,薯片,啤酒5雞蛋,面包,薯片6雞蛋,面包,啤酒7牛奶,面包,薯片8牛奶,雞蛋,面包,黃油,薯片9牛奶,雞蛋,黃油,薯片F(xiàn)P-GROWTH算法原理-實(shí)例1要找總是一起購買的商品,比FP-GROWTH算法原理-實(shí)例1-統(tǒng)計(jì)頻次Step1:先掃描數(shù)據(jù)庫,統(tǒng)計(jì)所有商品的出現(xiàn)次數(shù)(頻數(shù)),然后按照頻數(shù)遞減排序,刪除頻數(shù)小于最小支持度的商品。設(shè)最小支持度數(shù)為:minsup=4統(tǒng)計(jì)頻數(shù):牛奶6,雞蛋7,面包7,薯片7,爆米花2,啤酒4,黃油2.降序排序:薯片7,雞蛋7,面包7,牛奶6,啤酒4(刪除小于minsup的商品)65IDItems1牛奶,雞蛋,面包,薯片2雞蛋,爆米花,薯片,啤酒3牛奶,面包,啤酒4牛奶,雞蛋,面包,爆米花,薯片,啤酒5雞蛋,面包,薯片6雞蛋,面包,啤酒7牛奶,面包,薯片8牛奶,雞蛋,面包,黃油,薯片9牛奶,雞蛋,黃油,薯片
頻繁1項(xiàng)集,記為F1FP-GROWTH算法原理-實(shí)例1-統(tǒng)計(jì)頻次Step1:先掃FP-GROWTH算法原理-實(shí)例1-重新排序66IDItems1牛奶,雞蛋,面包,薯片2雞蛋,爆米花,薯片,啤酒3牛奶,面包,啤酒4牛奶,雞蛋,面包,爆米花,薯片,啤酒5雞蛋,面包,薯片6雞蛋,面包,啤酒7牛奶,面包,薯片8牛奶,雞蛋,面包,黃油,薯片9牛奶,雞蛋,黃油,薯片IDItems1薯片,雞蛋,面包,牛奶2薯片,雞蛋,啤酒3面包,牛奶,啤酒4薯片,雞蛋,面包,牛奶,啤酒5薯片,雞蛋,面包6雞蛋,面包,啤酒7薯片,面包,牛奶8薯片,雞蛋,面包,牛奶9薯片,雞蛋,牛奶Step2:對每一條數(shù)據(jù)記錄,按照F1重新排序。FP-GROWTH算法原理-實(shí)例1-重新排序10IDItemFP-GROWTH算法原理-實(shí)例1-建立FP樹67IDItems1薯片,雞蛋,面包,牛奶2薯片,雞蛋,啤酒3面包,牛奶,啤酒4薯片,雞蛋,面包,牛奶,啤酒5薯片,雞蛋,面包6雞蛋,面包,啤酒7薯片,面包,牛奶8薯片,雞蛋,面包,牛奶9薯片,雞蛋,牛奶Step3:把第二步重新排序后的記錄,插入到fp-tree中Step3.1:插入第一條(第一步有一個(gè)虛的根節(jié)點(diǎn))FP-GROWTH算法原理-實(shí)例1-建立FP樹11IDIteFP-GROWTH算法原理-實(shí)例1-建立FP樹68IDItems1薯片,雞蛋,面包,牛奶2薯片,雞蛋,啤酒3面包,牛奶,啤酒4薯片,雞蛋,面包,牛奶,啤酒5薯片,雞蛋,面包6雞蛋,面包,啤酒7薯片,面包,牛奶8薯片,雞蛋,面包,牛奶9薯片,雞蛋,牛奶Step3.2:插入第二條。根結(jié)點(diǎn)不管,然后插入薯片,在step3.1的基礎(chǔ)上+1,則記為2;同理雞蛋記為2;啤酒在step3.1的樹上是沒有的,那么就開一個(gè)分支。FP-GROWTH算法原理-實(shí)例1-建立FP樹12IDIteFP-GROWTH算法原理-實(shí)例1-建立FP樹69IDItems1薯片,雞蛋,面包,牛奶2薯片,雞蛋,啤酒3面包,牛奶,啤酒4薯片,雞蛋,面包,牛奶,啤酒5薯片,雞蛋,面包6雞蛋,面包,啤酒7薯片,面包,牛奶8薯片,雞蛋,面包,牛奶9薯片,雞蛋,牛奶Step3.3:插入第三條FP-GROWTH算法原理-實(shí)例1-建立FP樹13IDIteFP-GROWTH算法原理-實(shí)例1-建立FP樹70IDItems1薯片,雞蛋,面包,牛奶2薯片,雞蛋,啤酒3面包,牛奶,啤酒4薯片,雞蛋,面包,牛奶,啤酒5薯片,雞蛋,面包6雞蛋,面包,啤酒7薯片,面包,牛奶8薯片,雞蛋,面包,牛奶9薯片,雞蛋,牛奶同理,剩余記錄依次插入fp-tree中。FP-GROWTH算法原理-實(shí)例1-建立FP樹14IDIteFP-GROWTH算法原理-實(shí)例1-建立FP樹71圖中左邊的一列叫做頭指針表,樹中相同名稱的節(jié)點(diǎn)要鏈接起來,鏈表的第一個(gè)元素就是頭指針表里的元素。虛線連接起來的表示同一個(gè)商品,各個(gè)連接的數(shù)字加起來就是該商品出現(xiàn)的總次數(shù)。FP-GROWTH算法原理-實(shí)例1-建立FP樹15圖中左邊的FP-GROWTH算法原理-實(shí)例1-挖掘頻繁項(xiàng)集Step4:從FP-Tree中找出頻繁項(xiàng)集。遍歷表頭項(xiàng)中的每一項(xiàng)(以“牛奶:6”為例),從FP-Tree中找到所有的“牛奶”結(jié)點(diǎn),向上遍歷它的祖先結(jié)點(diǎn),得到4條路徑,如表所示。72FP-GROWTH算法原理-實(shí)例1-挖掘頻繁項(xiàng)集Step4:FP-GROWTH算法原理-實(shí)例1-挖掘頻繁項(xiàng)集Step4:從FP-Tree中找出頻繁項(xiàng)集。對于每一條路徑上的節(jié)點(diǎn),其count都設(shè)置為牛奶的count(路徑中最末尾的商品數(shù))73FP-GROWTH算法原理-實(shí)例1-挖掘頻繁項(xiàng)集Step4:FP-GROWTH算法原理-實(shí)例1-挖掘頻繁項(xiàng)集Step4:從FP-Tree中找出頻繁項(xiàng)集。因?yàn)槊恳豁?xiàng)末尾都是牛奶,可以把牛奶去掉,得到條件模式基,此時(shí)的后綴模式是:牛奶。74FP-GROWTH算法原理-實(shí)例1-挖掘頻繁項(xiàng)集Step4:FP-GROWTH算法原理-實(shí)例2把例子簡化一下,請看以下實(shí)例275TidItems1I1,I2,I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3FP-GROWTH算法原理-實(shí)例2把例子簡化一下,請看以下實(shí)FP-GROWTH算法原理-實(shí)例2-統(tǒng)計(jì)頻次先掃描數(shù)據(jù)庫,統(tǒng)計(jì)所有商品的出現(xiàn)次數(shù)(頻數(shù))定義min_sup=2,按照頻數(shù)遞減排序,刪除頻數(shù)小于最小支持度的商品。重新排列得到頻繁1-項(xiàng)目集F76I1I2I3I4I567622I2I1I3I4I576622FP-GROWTH算法原理-實(shí)例2-統(tǒng)計(jì)頻次先掃描數(shù)據(jù)庫,統(tǒng)FP-GROWTH算法原理-實(shí)例2-重新排序77I27I16I36I42I52TidItems1I2,I1,I52I2,I43I2,I34I2,I1,I45I1,I36I2,I37I1,I38I2,I1,I3,I59I2,I1,I3FP-GROWTH算法原理-實(shí)例2-重新排序21I27I16FP-GROWTH算法原理-實(shí)例2-創(chuàng)建根結(jié)點(diǎn)和頻繁項(xiàng)目表78Item-nameNode-headI2NullI1NullI3NullI4NullI5NullNullFP-GROWTH算法原理-實(shí)例2-創(chuàng)建根結(jié)點(diǎn)和頻繁項(xiàng)目表2FP-GROWTH算法原理-實(shí)例2-加入第一個(gè)事務(wù)(I2,I1,I5)79FP-GROWTH算法原理-實(shí)例2-加入第一個(gè)事務(wù)(I2,IFP-GROWTH算法原理-實(shí)例2-加入第二個(gè)事務(wù)(I2,I4)80FP-GROWTH算法原理-實(shí)例2-加入第二個(gè)事務(wù)(I2,IFP-GROWTH算法原理-實(shí)例2-加入第三個(gè)事務(wù)(I2,I3)81FP-GROWTH算法原理-實(shí)例2-加入第三個(gè)事務(wù)(I2,IFP-GROWTH算法原理-實(shí)例2-加入第四個(gè)事務(wù)(I2,I1,I4)82FP-GROWTH算法原理-實(shí)例2-加入第四個(gè)事務(wù)(I2,IFP-GROWTH算法原理-實(shí)例2-加入第五個(gè)事務(wù)(I1,I3)83FP-GROWTH算法原理-實(shí)例2-加入第五個(gè)事務(wù)(I1,IFP-GROWTH算法原理-實(shí)例2-加入第六個(gè)事務(wù)(I2,I3)84FP-GROWTH算法原理-實(shí)例2-加入第六個(gè)事務(wù)(I2,IFP-GROWTH算法原理-實(shí)例2-加入第七個(gè)事務(wù)(I1,I3)85FP-GROWTH算法原理-實(shí)例2-加入第七個(gè)事務(wù)(I1,IFP-GROWTH算法原理-實(shí)例2-加入第八個(gè)事務(wù)(I2,I1,I3,I5)86FP-GROWTH算法原理-實(shí)例2-加入第八個(gè)事務(wù)(I2,IFP-GROWTH算法原理-實(shí)例2-加入第九個(gè)事務(wù)(I2,I1,I3)87FP-GROWTH算法原理-實(shí)例2-加入第九個(gè)事務(wù)(I2,IFP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集首先考慮I5,得到條件模式基:<(I2,I1:1)>、<I2,I1,I3:1>構(gòu)造條件FP-Tree88得到I5頻繁項(xiàng)集:{{I2,I5},{I1,I5},{I2,I1,I5}}FP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集首先考慮I5FP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集接著考慮I4,得到條件模式基:
<(I2,I1:1)>、<I2:1>構(gòu)造條件FP-Tree89得到I4頻繁項(xiàng)集:{{I2,I4}}FP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集接著考慮I4FP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集然后考慮I3,得到條件模式基:
<(I2,I1:2)>、<I2:2>、<I1:2>構(gòu)造條件FP-Tree90由于此樹不是單分支路徑,因此需要遞歸挖掘I3FP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集然后考慮I3FP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集遞歸考慮I3,此時(shí)得到I1條件模式基<(I2:2)>,即I1,I3的條件模式基為<(I2:2)>構(gòu)造條件FP-Tree91得到I3的頻繁項(xiàng)目集{{I2,I3},{I1,I3},{I2,I1,I3}}FP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集遞歸考慮I3FP-GROWTH算法原
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 北京市清華大學(xué)附中2025年化學(xué)高二下期末綜合測試試題含解析
- 江西省新余第四中學(xué)、上高第二中學(xué)2025屆高一化學(xué)第二學(xué)期期末聯(lián)考試題含解析
- 發(fā)票搖獎(jiǎng)資金管理辦法
- 園區(qū)企業(yè)梯隊(duì)管理辦法
- 江蘇工地進(jìn)度管理辦法
- 佛教用品規(guī)范管理辦法
- 農(nóng)業(yè)公司戰(zhàn)略管理辦法
- 新疆煤礦礦井管理辦法
- 村民身份認(rèn)定管理辦法
- 小學(xué)生經(jīng)典古詩文誦讀活動(dòng)
- 船廠安全用電培訓(xùn)課件
- 《2025年CSCO腎癌診療指南》解讀
- 人教版九年級(jí)化學(xué)上冊暑假銜接講義(初二升初三)
- 跆拳道館技術(shù)崗位薪酬制度
- 無人駕駛車法規(guī)-深度研究
- 《寧晉縣國土空間總體規(guī)劃(2021-2035年)》
- 2024年度乳腺癌篩查與早期診斷課件
- 2024年食品檢驗(yàn)員(高級(jí))職業(yè)鑒定理論考試題庫(含答案)
- 工廠物品回收合同模板
- JJF 1168-2024便攜式制動(dòng)性能測試儀校準(zhǔn)規(guī)范
- 經(jīng)橈動(dòng)脈介入診療患者術(shù)肢并發(fā)癥預(yù)防及護(hù)理專家共識(shí)解讀
評(píng)論
0/150
提交評(píng)論