機(jī)器學(xué)習(xí)-FPGROWTH算法PPT課件

1、2021/3/91機(jī)器學(xué)習(xí)-FP-GROWTH算法李家豪2021/3/92目錄2021/3/93回憶Apriori算法 項(xiàng)集：項(xiàng)的集合稱(chēng)為項(xiàng)集，即商品的組合。 k項(xiàng)集：k件商品的組合，不關(guān)心商品件數(shù)，僅商品的種類(lèi)。 頻繁項(xiàng)集：如果項(xiàng)集的相對(duì)支持度滿(mǎn)足給定的最小支持度閾值，則該項(xiàng)集是頻繁項(xiàng)集。 強(qiáng)關(guān)聯(lián)規(guī)則:滿(mǎn)足給定支持度和置信度閾值的關(guān)聯(lián)規(guī)則 支持度：support(A-B) = P(AB) 置信度：confidence(A-B) = P(A|B) 2021/3/94回憶Apriori算法2021/3/95回憶Apriori算法2021/3/96Apriori算法的挑戰(zhàn)挑戰(zhàn) 多次數(shù)據(jù)庫(kù)掃描 巨大

2、數(shù)量的候補(bǔ)項(xiàng)集 繁瑣的支持度計(jì)算改善Apriori: 基本想法 減少掃描數(shù)據(jù)庫(kù)的次數(shù) 減少候選項(xiàng)集的數(shù)量 簡(jiǎn)化候選項(xiàng)集的支持度計(jì)算2021/3/97FP-GROWTH算法優(yōu)點(diǎn) 相比Apriori算法需要多次掃描數(shù)據(jù)庫(kù)，F(xiàn)PGrowth只需要對(duì)數(shù)據(jù)庫(kù)掃描2次。 第1次掃描事務(wù)數(shù)據(jù)庫(kù)獲得頻繁1項(xiàng)集。 第2次掃描建立一顆FP-Tree樹(shù)。2021/3/98FP-GROWTH算法原理-實(shí)例1 要找總是一起購(gòu)買(mǎi)的商品，比如薯片，雞蛋就是一條頻繁模式(規(guī)律)。IDItems1牛奶，雞蛋，面包，薯片2雞蛋，爆米花，薯片，啤酒3牛奶，面包，啤酒4牛奶，雞蛋，面包，爆米花，薯片，啤酒5雞蛋，面包，薯片6雞蛋，面

3、包，啤酒7牛奶，面包，薯片8牛奶，雞蛋，面包，黃油，薯片9牛奶，雞蛋，黃油，薯片2021/3/99FP-GROWTH算法原理-實(shí)例1-統(tǒng)計(jì)頻次Step1:先掃描數(shù)據(jù)庫(kù)，統(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的商品）IDItems1牛奶，雞蛋，面包，薯片2雞蛋，爆米花，薯片，啤酒3牛奶，面包，啤酒4牛奶，雞蛋，面包，爆米花，薯片，啤酒5雞蛋，面包，薯片6雞蛋，面包，啤酒7牛奶，面包

4、，薯片8牛奶，雞蛋，面包，黃油，薯片9牛奶，雞蛋，黃油，薯片 頻繁1項(xiàng)集，記為F12021/3/910FP-GROWTH算法原理-實(shí)例1-重新排序IDItems1牛奶，雞蛋，面包，薯片2雞蛋，爆米花，薯片，啤酒3牛奶，面包，啤酒4牛奶，雞蛋，面包，爆米花，薯片，啤酒5雞蛋，面包，薯片6雞蛋，面包，啤酒7牛奶，面包，薯片8牛奶，雞蛋，面包，黃油，薯片9牛奶，雞蛋，黃油，薯片IDItems1薯片,雞蛋,面包,牛奶2薯片,雞蛋,啤酒3面包,牛奶,啤酒4薯片,雞蛋,面包,牛奶,啤酒5薯片,雞蛋,面包6雞蛋,面包,啤酒7薯片,面包,牛奶8薯片,雞蛋,面包,牛奶9薯片,雞蛋,牛奶Step2:對(duì)每一條數(shù)據(jù)記

5、錄，按照F1重新排序。2021/3/911FP-GROWTH算法原理-實(shí)例1-建立FP樹(shù)IDItems1薯片,雞蛋,面包,牛奶2薯片,雞蛋,啤酒3面包,牛奶,啤酒4薯片,雞蛋,面包,牛奶,啤酒5薯片,雞蛋,面包6雞蛋,面包,啤酒7薯片,面包,牛奶8薯片,雞蛋,面包,牛奶9薯片,雞蛋,牛奶Step3：把第二步重新排序后的記錄，插入到fp-tree中Step3.1：插入第一條（第一步有一個(gè)虛的根節(jié)點(diǎn)）2021/3/912FP-GROWTH算法原理-實(shí)例1-建立FP樹(shù)IDItems1薯片,雞蛋,面包,牛奶2薯片,雞蛋,啤酒3面包,牛奶,啤酒4薯片,雞蛋,面包,牛奶,啤酒5薯片,雞蛋,面包6雞蛋,面包

6、,啤酒7薯片,面包,牛奶8薯片,雞蛋,面包,牛奶9薯片,雞蛋,牛奶Step3.2：插入第二條。根結(jié)點(diǎn)不管，然后插入薯片，在step3.1的基礎(chǔ)上+1，則記為2；同理雞蛋記為2；啤酒在step3.1的樹(shù)上是沒(méi)有的，那么就開(kāi)一個(gè)分支。2021/3/913FP-GROWTH算法原理-實(shí)例1-建立FP樹(shù)IDItems1薯片,雞蛋,面包,牛奶2薯片,雞蛋,啤酒3面包,牛奶,啤酒4薯片,雞蛋,面包,牛奶,啤酒5薯片,雞蛋,面包6雞蛋,面包,啤酒7薯片,面包,牛奶8薯片,雞蛋,面包,牛奶9薯片,雞蛋,牛奶Step3.3：插入第三條2021/3/914FP-GROWTH算法原理-實(shí)例1-建立FP樹(shù)IDItem

7、s1薯片,雞蛋,面包,牛奶2薯片,雞蛋,啤酒3面包,牛奶,啤酒4薯片,雞蛋,面包,牛奶,啤酒5薯片,雞蛋,面包6雞蛋,面包,啤酒7薯片,面包,牛奶8薯片,雞蛋,面包,牛奶9薯片,雞蛋,牛奶同理，剩余記錄依次插入fp-tree中。2021/3/915FP-GROWTH算法原理-實(shí)例1-建立FP樹(shù)圖中左邊的一列叫做頭指針表，樹(shù)中相同名稱(chēng)的節(jié)點(diǎn)要鏈接起來(lái)，鏈表的第一個(gè)元素就是頭指針表里的元素。虛線(xiàn)連接起來(lái)的表示同一個(gè)商品，各個(gè)連接的數(shù)字加起來(lái)就是該商品出現(xiàn)的總次數(shù)。2021/3/916FP-GROWTH算法原理-實(shí)例1-挖掘頻繁項(xiàng)集Step4：從FP-Tree中找出頻繁項(xiàng)集。遍歷表頭項(xiàng)中的每一項(xiàng)（以

8、“牛奶：6”為例），從FP-Tree中找到所有的“牛奶”結(jié)點(diǎn)，向上遍歷它的祖先結(jié)點(diǎn)，得到4條路徑，如表所示。2021/3/917FP-GROWTH算法原理-實(shí)例1-挖掘頻繁項(xiàng)集Step4：從FP-Tree中找出頻繁項(xiàng)集。對(duì)于每一條路徑上的節(jié)點(diǎn)，其count都設(shè)置為牛奶的count（路徑中最末尾的商品數(shù)）2021/3/918FP-GROWTH算法原理-實(shí)例1-挖掘頻繁項(xiàng)集Step4：從FP-Tree中找出頻繁項(xiàng)集。因?yàn)槊恳豁?xiàng)末尾都是牛奶，可以把牛奶去掉，得到條件模式基，此時(shí)的后綴模式是：牛奶。2021/3/919FP-GROWTH算法原理-實(shí)例2 把例子簡(jiǎn)化一下，請(qǐng)看以下實(shí)例2TidItems1

9、I1,I2,I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I32021/3/920FP-GROWTH算法原理-實(shí)例2-統(tǒng)計(jì)頻次 先掃描數(shù)據(jù)庫(kù)，統(tǒng)計(jì)所有商品的出現(xiàn)次數(shù)(頻數(shù)) 定義min_sup=2，按照頻數(shù)遞減排序，刪除頻數(shù)小于最小支持度的商品。重新排列得到頻繁1-項(xiàng)目集FI1I2I3I4I567622I2I1I3I4I5766222021/3/921FP-GROWTH算法原理-實(shí)例2-重新排序I27I16I36I42I52TidItems1I2, I1,I52I2,I43I2,I34I2, I1,I45I1,I36I2

10、,I37I1,I38I2, I1,I3,I59I2, I1,I32021/3/922FP-GROWTH算法原理-實(shí)例2-創(chuàng)建根結(jié)點(diǎn)和頻繁項(xiàng)目表Item-nameNode-headI2NullI1NullI3NullI4NullI5NullNull2021/3/923FP-GROWTH算法原理-實(shí)例2-加入第一個(gè)事務(wù)(I2,I1,I5)2021/3/924FP-GROWTH算法原理-實(shí)例2-加入第二個(gè)事務(wù)(I2,I4)2021/3/925FP-GROWTH算法原理-實(shí)例2-加入第三個(gè)事務(wù)(I2,I3)2021/3/926FP-GROWTH算法原理-實(shí)例2-加入第四個(gè)事務(wù)(I2,I1,I4)202

11、1/3/927FP-GROWTH算法原理-實(shí)例2-加入第五個(gè)事務(wù)(I1,I3)2021/3/928FP-GROWTH算法原理-實(shí)例2-加入第六個(gè)事務(wù)(I2,I3)2021/3/929FP-GROWTH算法原理-實(shí)例2-加入第七個(gè)事務(wù)(I1,I3)2021/3/930FP-GROWTH算法原理-實(shí)例2-加入第八個(gè)事務(wù)(I2,I1,I3,I5)2021/3/931FP-GROWTH算法原理-實(shí)例2-加入第九個(gè)事務(wù)(I2,I1,I3)2021/3/932FP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集首先考慮I5，得到條件模式基： 、構(gòu)造條件FP-Tree得到I5頻繁項(xiàng)集：I2,I5,I1,I5,I

12、2,I1,I52021/3/933FP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集接著考慮I4，得到條件模式基： 、構(gòu)造條件FP-Tree得到I4頻繁項(xiàng)集：I2,I42021/3/934FP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集然后考慮I3，得到條件模式基： 、 構(gòu)造條件FP-Tree由于此樹(shù)不是單分支路徑，因此需要遞歸挖掘I32021/3/935FP-GROWTH算法原理-實(shí)例2-挖掘頻繁項(xiàng)集 遞歸考慮I3，此時(shí)得到I1條件模式基,即I1, I3的條件模式基為 構(gòu)造條件FP-Tree得到I3的頻繁項(xiàng)目集I2,I3,I1,I3,I2,I1,I32021/3/936FP-GROWTH算法原

13、理-實(shí)例2-挖掘頻繁項(xiàng)集 最后考慮I1，得到條件模式基： 構(gòu)造條件FP-Tree得到I1的頻繁項(xiàng)目集：I2,I12021/3/937FP-GROWTH算法實(shí)現(xiàn)-數(shù)據(jù)處理項(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,z h,r,z,p,jz格式化處理2021/3/938代碼實(shí)現(xiàn)-FP樹(shù)數(shù)據(jù)結(jié)構(gòu)2021/3/939代碼實(shí)現(xiàn)-構(gòu)造FP樹(shù)步驟2021/3/940代碼實(shí)現(xiàn)-構(gòu)造FP樹(shù)2021/3/941代碼實(shí)現(xiàn)-構(gòu)造FP樹(shù)2021/3/942代碼實(shí)現(xiàn)-構(gòu)造FP樹(shù)（updateTree函數(shù)）2021/3/943代碼實(shí)現(xiàn)-構(gòu)造FP樹(shù)（updateH

14、eader函數(shù)）2021/3/944代碼實(shí)現(xiàn)-構(gòu)造FP樹(shù)（驗(yàn)證）2021/3/945代碼實(shí)現(xiàn)-挖掘頻繁項(xiàng)集步驟從構(gòu)建好的FP樹(shù)中抽取頻繁項(xiàng)集的步驟如下：(1)從FP樹(shù)中獲取條件模式基；(2)利用條件模式基，構(gòu)建一個(gè)條件FP樹(shù)；(3)迭代重復(fù)(1)(2)，直到樹(shù)包含一個(gè)元素項(xiàng)為止。2021/3/946條件模式基定義 條件模式基是以所查找元素項(xiàng)為結(jié)尾的路徑集合所查找元素項(xiàng)為結(jié)尾的路徑集合。每一條路徑其實(shí)都是一條前綴路徑前綴路徑。簡(jiǎn)而言之，一條前綴路徑就是介于所查找元素項(xiàng)與樹(shù)根節(jié)點(diǎn)之間的所有內(nèi)容。 每一個(gè)頻繁項(xiàng)的所有前綴路徑（條件模式基）：2021/3/947代碼實(shí)現(xiàn)-抽取條件模式基eg：t的第1條前綴路徑prefixPath=t,s,y,x,z；2021/3/948代碼實(shí)現(xiàn)-抽取條件模式基2021/3/949代碼實(shí)現(xiàn)-抽取條件模式基（驗(yàn)證）2021/3/950代碼實(shí)現(xiàn)-創(chuàng)建條件FP樹(shù)2021/3/951代碼實(shí)現(xiàn)-創(chuàng)建條件FP樹(shù)2021/3/952代