FP-Growth可以高效地發(fā)現(xiàn)頻繁項(xiàng)集
發(fā)現(xiàn)事務(wù)數(shù)據(jù)中的公共模式
FP-Growth與Apriori相比翘盖，是基于Apriori的構(gòu)建，但是將數(shù)據(jù)集存儲(chǔ)在FP樹(shù)夜牡，這樣使得算法的執(zhí)行速度快于Apriori莱找，通常性能要好兩個(gè)數(shù)量級(jí)以上。
FP-Growth只需要對(duì)數(shù)據(jù)庫(kù)進(jìn)行兩次掃描咏闪，而Apriori對(duì)每個(gè)潛在的頻繁項(xiàng)集都會(huì)掃描數(shù)據(jù)集判定給定模式是否頻繁。FP過(guò)程如下：
1）構(gòu)建FP樹(shù)
2）從FP樹(shù)中挖掘頻繁項(xiàng)集
同搜索樹(shù)不同的是摔吏，一個(gè)元素項(xiàng)可以在一顆FP樹(shù)中出現(xiàn)多次鸽嫂，F(xiàn)P樹(shù)會(huì)存儲(chǔ)項(xiàng)集出現(xiàn)的頻率，相似元素的集合會(huì)共享樹(shù)的一部分征讲，只有當(dāng)集合間完全不同時(shí)才會(huì)分叉
在FP樹(shù)中Z出現(xiàn)了5次据某，集合{r,z}出現(xiàn)了1次，那么可以推出一定是z本身或者其他符號(hào)一起出現(xiàn)了4次诗箍。
FP-growth的工作流程是癣籽，首先建立FP樹(shù)，然后利用它來(lái)挖掘頻繁項(xiàng)集滤祖。為構(gòu)建FP樹(shù)需要對(duì)原始數(shù)據(jù)掃描兩遍筷狼，第一遍對(duì)所有元素項(xiàng)的出現(xiàn)次數(shù)進(jìn)行計(jì)數(shù)，如果某元素是不頻繁的匠童，那么包含該元素的超級(jí)也是不頻繁的埂材，所以就不用考慮這些元素的超級(jí)。
第一遍掃描統(tǒng)計(jì)出現(xiàn)的頻率汤求，第二遍掃描只考慮那些頻繁的元素
第一次遍歷數(shù)據(jù)集會(huì)獲得每個(gè)元素項(xiàng)的出現(xiàn)頻率俏险。接下來(lái)，去掉不滿足最小支持度的元素項(xiàng)扬绪。再下一步構(gòu)建FP樹(shù)竖独。在構(gòu)建時(shí)，讀人每個(gè)項(xiàng)集并將其添加到一條已經(jīng)存在的路徑中挤牛。如果該路徑不存在莹痢，則創(chuàng)建一條新路徑。每個(gè)事務(wù)就是一個(gè)無(wú)序集合。假設(shè)有集合{z格二，x，y}和比{y,z,r} ,那么在FP樹(shù) , 相同項(xiàng)會(huì)只表示一次竣蹦。
為了解決此問(wèn)題顶猜，在將集合添加到樹(shù)之前，需要對(duì)每個(gè)集合進(jìn)行排序痘括。排序基于元素項(xiàng)的絕對(duì)出現(xiàn)頻率來(lái)進(jìn)行长窄。使用圖12-2中的頭指針節(jié)點(diǎn)值，對(duì)表12-1中數(shù)據(jù)進(jìn)行過(guò)濾纲菌、重排序后的數(shù)據(jù)顯示在表12-2中
對(duì)事務(wù)記錄進(jìn)行過(guò)濾和排序之后就可以構(gòu)建FP樹(shù)了挠日，從空集開(kāi)始，向其中不斷添加頻繁項(xiàng)集翰舌，過(guò)濾嚣潜、排序后的事務(wù)添加到樹(shù)中，如果樹(shù)中已存在現(xiàn)有元素椅贱，則增加現(xiàn)有元素值懂算，否則則添加分支
----從一顆FP樹(shù)中挖掘頻繁項(xiàng)集
1. 從FP樹(shù)中獲得條件模式基
2. 利用條件模式基，構(gòu)建一個(gè)條件FP樹(shù)
3. 迭代重復(fù)1）2）直到樹(shù)只包含一個(gè)元素
--條件模式基
---創(chuàng)建條件FP樹(shù)
