機(jī)器學(xué)習(xí)FPGROWTH算法第1頁，共56頁。目錄2Apriori算法和FP-GROWTH算法的比較FP-GROWTH算法原理FP-GROWTH代碼實(shí)現(xiàn)（python）示例：從新聞網(wǎng)站點(diǎn)擊流中挖掘新聞報(bào)道第2頁，共56頁?；貞汚priori算法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)第3頁，共56頁?；貞汚priori算法4第4頁，共56頁?；貞汚priori算法5第5頁，共56頁。Apriori算法的挑戰(zhàn)6挑戰(zhàn)多次數(shù)據(jù)庫掃描巨大數(shù)量的候補(bǔ)項(xiàng)集繁瑣的支持度計(jì)算改善Apriori:基本想法

減少掃描數(shù)據(jù)庫的次數(shù)

減少候選項(xiàng)集的數(shù)量簡化候選項(xiàng)集的支持度計(jì)算第6頁，共56頁。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樹。7第7頁，共56頁。FP-GROWTH算法原理-實(shí)例1要找總是一起購買的商品，比如[薯片，雞蛋]就是一條頻繁模式(規(guī)律)。8IDItems1牛奶，雞蛋，面包，薯片2雞蛋，爆米花，薯片，啤酒3牛奶，面包，啤酒4牛奶，雞蛋，面包，爆米花，薯片，啤酒5雞蛋，面包，薯片6雞蛋，面包，啤酒7牛奶，面包，薯片8牛奶，雞蛋，面包，黃油，薯片9牛奶，雞蛋，黃油，薯片第8頁，共56頁。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)集，記為F1第9頁，共56頁。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重新排序。第10頁，共56頁。FP-GROWTH算法原理-實(shí)例1-建立FP樹11IDItems1薯片,雞蛋,面包,牛奶2薯片,雞蛋,啤酒3面包,牛奶,啤酒4薯片,雞蛋,面包,牛奶,啤酒5薯片,雞蛋,面包6雞蛋,面包,啤酒7薯片,面包,牛奶8薯片,雞蛋,面包,牛奶9薯片,雞蛋,牛奶Step3：把第二步重新排序后的記錄，插入到fp-tree中Step3.1：插入第一條（第一步有一個虛的根節(jié)點(diǎn)）第11頁，共56頁。FP-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的樹上是沒有的，那么就開一個分支。第12頁，共56頁。FP-GROWTH算法原理-實(shí)例1-建立FP樹13IDItems1薯片,雞蛋,面包,牛奶2薯片,雞蛋,啤酒3面包,牛奶,啤酒4薯片,雞蛋,面包,牛奶,啤酒5薯片,雞蛋,面包6雞蛋,面包,啤酒7薯片,面包,牛奶8薯片,雞蛋,面包,牛奶9薯片,雞蛋,牛奶Step3.3：插入第三條第13頁，共56頁。FP-GROWTH算法原理-實(shí)例1-建立FP樹14IDItems1薯片,雞蛋,面包,牛奶2薯片,雞蛋,啤酒3面包,牛奶,啤酒4薯片,雞蛋,面包,牛奶,啤酒5薯片,雞蛋,面包6雞蛋,面包,啤酒7薯片,面包,牛奶8薯片,雞蛋,面包,牛奶9薯片,雞蛋,牛奶同理，剩余記錄依次插入fp-tree中。第14頁，共56頁。FP-GROWTH算法原理-實(shí)例1-建立FP樹15圖中左邊的一列叫做頭指針表，樹中相同名稱的節(jié)點(diǎn)要鏈接起來，鏈表的第一個元素就是頭指針表里的元素。虛線連接起來的表示同一個商品，各個連接的數(shù)字加起來就是該商品出現(xiàn)的總次數(shù)。第15頁，共56頁。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條路徑，如表所示。16第16頁，共56頁。FP-GROWTH算法原理-實(shí)例1-挖掘頻繁項(xiàng)集Step4：從FP-Tree中找出頻繁項(xiàng)集。對于每一條路徑上的節(jié)點(diǎn)，其count都設(shè)置為牛奶的count（路徑中最末尾的商品數(shù)）17第17頁，共56頁。FP-GROWTH算法原理-實(shí)例1-挖掘頻繁項(xiàng)集Step4：從FP-Tree中找出頻繁項(xiàng)集。因?yàn)槊恳豁?xiàng)末尾都是牛奶，可以把牛奶去掉，得到條件模式基，此時的后綴模式是：牛奶。18第18頁，共56頁。FP-GROWTH算法原理-實(shí)例2把例子簡化一下，請看以下實(shí)例219TidItems1I1,I2,I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3第19頁，共56頁。FP-GROWTH算法原理-實(shí)例2-統(tǒng)計(jì)頻次先掃描數(shù)據(jù)庫，統(tǒng)計(jì)所有商品的出現(xiàn)次數(shù)(頻數(shù))定義min_sup=2，按照頻數(shù)遞減排序，刪除頻數(shù)小于最小支持度的商品。重新排列得到頻繁1-項(xiàng)目集F20I1I2I3I4I567622I2I1I3I4I576622第20頁，共56頁。FP-GROWTH算法原理-實(shí)例2-重新排序21I27I16I36I42I52TidItems1I2,I1,I52I2,I43I2,I34I2,I1,I45I1,I36I2,I37I1,I38I2,I1,I3,I59I2,I1,I3第21頁，共56頁。FP-GROWTH算法原理-實(shí)例2-創(chuàng)建根結(jié)點(diǎn)和頻繁項(xiàng)目表22Item-nameNode-headI2NullI1NullI3NullI4NullI5NullNull第22頁，共56頁。FP-GROWTH算法原理-實(shí)例2-加入第一個事務(wù)(I2,I1,I5)23第23頁，共56頁。FP-GROWTH算法原理-實(shí)例2-加入第二個事務(wù)(I2,I4)24第24頁，共56頁。FP-GROWTH算法原理-實(shí)例2-加入第三個事務(wù)(I2,I3)25第25頁，共56頁。FP-GROWTH算法原理-實(shí)例2-加入第四個事務(wù)(I2,I1,I4)26第26頁，共56頁。FP-GROWTH算法原理-實(shí)例2-加入第五個事務(wù)(I1,I3)27第27頁，共56頁。FP-GROWTH算法原理-實(shí)例2-加入第六個事務(wù)(I2,I3)28第28頁，共56頁。FP-GROWTH算法原理-實(shí)例2-加入第七個事務(wù)(I1,I3)29第29頁，共56頁。FP-GROWTH算法原理-實(shí)例2-加入第八個事務(wù)(I2,I1,I3,I5)30第30頁，共56頁。FP-GROWTH算法原理-實(shí)例2-加入第九個事務(wù)(I2,I1,I3)31第31頁，共56頁。FP-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}}第32頁，共56頁。FP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集接著考慮I4，得到條件模式基：

<(I2,I1:1)>、<I2:1>構(gòu)造條件FP-Tree33得到I4頻繁項(xiàng)集：{{I2,I4}}第33頁，共56頁。FP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集然后考慮I3，得到條件模式基：

<(I2,I1:2)>、<I2:2>、<I1:2>構(gòu)造條件FP-Tree34由于此樹不是單分支路徑，因此需要遞歸挖掘I3第34頁，共56頁。FP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集遞歸考慮I3，此時得到I1條件模式基<(I2:2)>,即I1,I3的條件模式基為<(I2:2)>構(gòu)造條件FP-Tree35得到I3的頻繁項(xiàng)目集{{I2,I3},{I1,I3},{I2,I1,I3}}第35頁，共56頁。FP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集最后考慮I1，得到條件模式基：<(I2:4)>構(gòu)造條件FP-Tree36得到I1的頻繁項(xiàng)目集：{I2,I1}第36頁，共56頁。FP-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格式化處理第37頁，共56頁。代碼實(shí)現(xiàn)-FP樹數(shù)據(jù)結(jié)構(gòu)38第38頁，共56頁。代碼實(shí)現(xiàn)-構(gòu)造FP樹步驟39第39頁，共56頁。代碼實(shí)現(xiàn)-構(gòu)造FP樹40第40頁，共56頁。代碼實(shí)現(xiàn)-構(gòu)造FP樹41第41頁，共56頁。代碼實(shí)現(xiàn)-構(gòu)造FP樹（updateTree函數(shù)）42第42頁，共56頁。代碼實(shí)現(xiàn)-構(gòu)造FP樹（updateHeader函數(shù)）43第43頁，共56頁。代碼實(shí)現(xiàn)-構(gòu)造FP樹（驗(yàn)證）44第44頁，共56頁。代碼實(shí)現(xiàn)-挖掘頻繁項(xiàng)集步驟從構(gòu)建好的FP樹中抽取頻繁項(xiàng)集的步驟如下：(1)從FP樹中獲取條件模式基；(2)利用條件模式基，構(gòu)建一個條件FP樹；(3)迭代重