FP-Growth算法講解

1、講解人： XXXFrequent Pattern Algorithm頻繁模式算法Frequent Pattern Algorithm 頻繁模式算法TidItems1牛奶,雞蛋,面包,薯片2雞蛋,爆米花,薯片,啤酒3雞蛋,面包,薯片4牛奶,雞蛋,面包,爆米花,薯片,啤酒5牛奶,面包,啤酒6雞蛋,面包,啤酒7牛奶,面包,薯片8牛奶,雞蛋,面包,黃油,薯片9牛奶,雞蛋,黃油,薯片ItemsTimes啤酒,雞蛋3啤酒,面包3牛奶,雞蛋4牛奶,雞蛋,面包3牛奶,雞蛋,面包,薯片3牛奶,雞蛋,薯片4牛奶,面包5牛奶,面包,薯片4牛奶,薯片5雞蛋,面包5雞蛋,面包,薯片4雞蛋,薯片6面包,薯片5頻繁模式算法

2、Frequent Pattern Algorithm 頻繁模式算法項(xiàng)與項(xiàng)集基本概念這是一個(gè)集合的概念，在一籃子商品中的一件消費(fèi)品即為一項(xiàng)（Item），則若干項(xiàng)的集合為項(xiàng)集，如尿布，面包構(gòu)成一個(gè)二元項(xiàng)集。支持度 支持度是指在所有項(xiàng)集中X, Y出現(xiàn)的可能性，即項(xiàng)集中同時(shí)含有X和Y的概率。通過(guò)設(shè)定最小閾值（minsup），剔除“出鏡率”較低的無(wú)意義規(guī)則設(shè)定最小閾值為5%，由于尿布，啤酒的支持度為800/10000=8%，滿足基本輸了要求，成為頻繁項(xiàng)集，保留規(guī)則；而尿布，面包的支持度為100/10000=1%，被剔除。 有10000個(gè)消費(fèi)者購(gòu)買了商品，其中購(gòu)買尿布1000個(gè)，購(gòu)買啤酒2000個(gè)，購(gòu)買面

3、包500個(gè)，同時(shí)購(gòu)買尿布和面包800個(gè)，同時(shí)購(gòu)買尿布和面包100個(gè)。Frequent Pattern Algorithm 頻繁模式算法1FP-Growth算法演示-構(gòu)造FP樹TidItems1I1,I2.I52I2,I43I2,I34I1,I2,I45I1,I36I2,I37I1,I38I1,I2,I3,I59I1,I2,I3事務(wù)數(shù)據(jù)庫(kù)的建立掃描事務(wù)數(shù)據(jù)庫(kù)得到頻繁項(xiàng)目集FI1I2I3I4I567622定義minsup=20%,即最小支持度為2,重新排列FI2I1I3I4I576622Frequent Pattern Algorithm 頻繁模式算法TidItems1I2,I1,I52I2,I4

4、3I2,I34I2,I1,I45I1,I36I2,I37I1,I38I2,I1,I3,I59I2,I1,I3重新調(diào)整事務(wù)數(shù)據(jù)庫(kù)Frequent Pattern Algorithm 頻繁模式算法構(gòu)建FP樹TidItems1I2,I1,I52I2,I43I2,I34I2,I1,I45I1,I36I2,I37I1,I38I2,I1,I3,I59I2,I1,I3rootI2:1I1:2I5:11I4:13I3:142I4:1I1: 1I3: 1522263I3:1I5:1742Frequent Pattern Algorithm 頻繁模式算法rootI2:I1:I5:14I4:1I3:2I4:1I1:

5、 2I3: 2I3:2I5:17FP樹1FP-Growth算法演示-FP-樹挖掘挖掘從表頭header的最后一個(gè)項(xiàng)開始I2I1I3I4I576622Frequent Pattern Algorithm 頻繁模式算法rootI2:I1:I5:14I4:1I3:2I4:1I1: 2I3: 2I3:2I5:17挖掘I5FP樹 在FP樹中可以看到，從根節(jié)點(diǎn)到i5:1的路徑有兩條：i2:7-i1:4-i5:1i2:7-i14-i3:2-i5:1 i2:7-i1:4和i2:7-i14-i3:2因?yàn)樽罱K到達(dá)的節(jié)點(diǎn)肯定是i5，所以將i5省略就是i5的條件模式基，記為i2,i1:1i2,i1,i3:1為什么每個(gè)

6、條件模式基的計(jì)數(shù)為1呢？ 雖然i2和i1的計(jì)數(shù)都很大，但是由于i5的計(jì)數(shù)為1，最終到達(dá)i5的重復(fù)次數(shù)也只能為1。所以條件模式基的計(jì)數(shù)是根據(jù)路徑中節(jié)點(diǎn)的最小計(jì)數(shù)來(lái)決定的。Frequent Pattern Algorithm 頻繁模式算法rootI2:I1:2I3:2挖掘I5條件FP樹1條件模式基：i2,i1:1i2,i1,i3:1根據(jù)條件模式基，我們可以得到該商品的條件FP樹因?yàn)閕3:1x小于最小支持度2,所以講i3:1省略不計(jì),i5的條件FP樹記為 i2:2,I1:2項(xiàng)條件模式基條件FP樹產(chǎn)生的頻繁模式I5I2 I1:1，I2 I1 I3:1I2 I5:2, I1 I5:2, I2 I1 I5:2I4I2 I1:1,I2:1I2 I4:2I3I2 I1 :2,I2:2,I1:2,I2 I3:4,I1 I3:4,I2 I1 I3:2I1I2:4I2 I1:4Frequen