频繁项集挖掘之apriori和fp-growth
Apriori和fp-growth是頻繁項集(frequent?itemset?mining)挖掘中的兩個經典算法，主要的區別在于一個是廣度優先的方式，另一個是深度優先的方式，后一種是基于前一種效率較低的背景下提出來的，雖然都是十幾年前的，但是理解這兩個算法對數據挖掘和學習算法都有很大好處。在理解這兩個算法之前，應該先了解頻繁項集挖掘是做什么用的。
頻繁項集挖掘是關聯規則挖掘中的首要的子任務。關聯規則挖掘是要找出一個數據集上，滿足一定條件的項集。這些項的集合能構成?形如蘊含式"A=>B"這樣的“規則”。這個"=>"符號是通過一些條件來定義的，如果沒有條件那當然所有的項組合都能形成這樣的關系。頻繁程度就是一種要求，也就是AB共同次數出現了超過閾值。?A和B能否形成"=>"規則，?就要根據定義來算，那首先就得把A、B需要的條件挖出來，也就是頻繁項集挖掘要做的。
關聯規則定義比較容易能搜到，頻繁項集挖掘簡單的說就是：給定一個項列表list?=?{A,B,C,...}，一個數據集D的每條記錄都是list?的子集，要找出數據集中頻繁共同出現次數超過閾值t，也就是支持度，的所有組合。
這個挖掘其實不好做，因為結果可能是list?中所有項的組合，有2^|list|個可能，搜索空間是個組合爆炸的空間。看下圖，先別看紅字紅線：
? ? ? ? ? ? ? ? ??
要弄好這件事不僅需要有效減小搜索空間，而且對每個可能的搜索都必須快速完成。所以頻繁項集挖掘在算法實踐和編碼實現上就要有非常強的技巧。我們就來深入學習apriori和fp-growth中的搜索方式和技巧。這兩個算法很容易找到完整的步驟，這里會更注重里面一些精彩之處，但是可能書寫不會那么規范，建議和完整算法對照來讀。
先來看看apriori。Apriori采用廣度優先的搜索方式，縮小搜索空間用到了一個稱為apriori的性質。Apriori性質是這么說的：頻繁項集的所有非空子集必然也是頻繁的。這是很顯然的，比如?同時包含項AB的記錄條數肯定比只包含A的記錄少。這條性質反過來也可以這么說：如果一個項集是非頻繁的，那么它的超集必然也是非頻繁的。
算法過程如下：
?輸入:數據集D，支持度minsup
?輸出:滿足支持度的所有項集的集合L
?L1?=?發現1-項集(D);?
?for?(k=2;Lk-1?≠Φ?;k++)?{
? ? ??Ck?=?連接剪枝生成(Lk-1,?minsup)
? ? ? 掃描D，為Ck中每個項集c?統計?c.count
? ? ? 保留Lk?={c?∈?Ck|c.count≥min_sup}
? ? ? L?=?L?∪?Lk??
?}
?Return?L
其中算法精華在于?連接剪枝生成(Lk-1,?minsup)?這一步，?包含連接步和剪枝步兩個動作：
1.?連接步：長度k-1的項連接成長度k的項；具體就是對兩個k-1長的項L1和L2，必須滿足前k-2個項都相同才能連接，最后把L1和L2剩下的最后一項加起來，形成k的長度的項。
2.?剪枝步：k項連接完成后，檢查其所有k-1子集是否是頻繁的，如果是，才保留作為候選項。
可以通過一張截圖來演示一下apriori的過程：
對應第一張圖，連接步是從第k層的項集，向下擴展一層的候選項集，剪枝步能夠通過apriori性質過濾掉那些肯定非頻繁的項集。
Apriori的框架其實很小，但是可以想象得到主要的兩個步驟：?連接+剪枝（也就是候選集生成），以及，候選集統計是很耗費時間的。
剪枝步也需要對每個k-候選項集的k-1子集都進行一次檢測，也很耗費時間；統計頻繁次數是必須的，因此需要掃描數據庫，經歷I/O。那么有必要剪枝，直接統計會不會更好呢，雖然沒有試驗過，但我估計還是剪枝以后減少候選集的統計更劃算。而這兩個耗時的步驟在實現上如果能使用到技巧，對算法時間影響最直接。比如剪枝步中k-1候選項集需要逐一向已有的k-1頻繁項集查詢，這用什么數據結構最好？又如掃描數據庫的時候是否能過進行一些壓縮，相同的記錄進行合并減少遍歷次數，以及過濾掉對統計沒用的記錄？
面對apriori的問題，感覺Fp-growth突然間就冒出來了，它是一個挖掘方式和apriori完全不一樣的算法，直接看可能不那么像apriori直觀，因為算法一開始就介紹了它采用的數據結構和挖掘方式。所以我們先對比下apriori和fp-growth的差異在哪，再介紹它的算法。
簡單的說apriori是先產生一批候選項集，再通過原數據集去過濾非頻繁項集：先找A、B、C，檢查一下通過了，再找AB、AC、AB，檢查又通過了，再到ABC...?這樣的廣度優先的方式。而fp-growth是先從數據集中找頻繁的項，再從包含這個頻繁項的子數據集中找其他的頻繁項，把它們倆連起來也肯定是頻繁的：先找A，再在找包含A的子數據庫里，找到B，就得到AB是頻繁，再再包含AB的子數據庫里，找到C，ABC就是頻繁了。
在了解了fp-growth的大致思路以后，我們就能介紹它采用的數據結構和算法了。
首先fp-growth采用了一個叫fp-tree?的數據結構去壓縮存儲數據集，放到內存里，這樣以后過問原數據集的事就不必經過IO了。
Fp-tree主要是一種前綴樹，和字典樹（trie）接近，并且節點把項的次數也記錄下了。字符的順序有所不同，字典樹用的是字母表順序，fp-tree?(frequent?pattern?tree)用的是字母表的頻率降序，這樣的好處是出現次數多的項作為共享前綴的概率也大，fp-tree的壓縮率就高（后面還會提到），根據apriori性質，非頻繁的項沒用，因此fp-tree上可以沒有它們。
根據前面提到fp-growth步驟，需要找數據庫上包含某個項的子數據庫，不能從樹根開始搜索，因此為了方便，需要把fp-tree中所有枝干、葉子上相同的項全串一起，這樣項從一個起點開始，向樹根遍歷，就能得到包含這個項的子數據庫了。這些起點和串起相同節點的鏈就是fp-tree的另一個部分：頭表和兄弟鏈。頭表包含樹上所有的單項，并是兄弟鏈的起點，那么fp-tree不僅完整記錄了數據庫里所需的信息，還能找到對任一項找到包含了它的子數據庫。
有了fp-tree，挖掘頻繁項集就變得直觀了。首先是壓縮數據庫，過濾非頻繁項，得到一棵fp-tree?1號，對于一個項，比如A，通過兄弟鏈，遍歷樹找出?包含A的子樹(庫)，又稱A的條件模式樹(庫)，英文原文叫condition?pattern?tree(base)。然后把這個子庫當做一個新的數據庫2號，過濾2號庫非頻繁項，建立一個小點的fp-tree?2號，那么那個A與這個2號樹里的所有項，連起來肯定也是頻繁的；比如有B，同理把B的條件樹找出，也建立個fp-tree?3號，就能得到AB和3號樹上的項連起來也肯定是頻繁的。這個過程遞歸完成，建立不出條件子樹遞歸就跳出去。
算法包含兩個部分：
1.?是建立fp-tree：掃描一遍數據庫，得到每個項的支持度，排序并過濾非頻繁項；再掃描一次數據庫，每條記錄按順序排序，添加到fp-tree上。
2.?調用算法FP_growth(FP-tree,?null)。
???Function?Fp_growth(FP-tree,?a){
?if(fp-tree?是單條路徑){
???對路徑上的組合b，?都連接a，輸出b∪?a?
?}else{
???For?each?項ai?in?頭表{
?????輸出一個模式b=?ai∪?a，其支持度?support?=ai.support?
?????構造b的條件模式庫，然后構造b的條件模式樹 Treeb;?
?????If?(Treeb?不為空){
????????調用算法FP_growth(Treeb,b?)
??}
?}
?}
FP_growth是個遞歸算法，期間需要反復遍歷樹和構建fp-tree。fp-growth中判斷單路徑部分可以不要，最后實際結果其實是和下面部分是一樣的，但是直接計算單路徑產生所有組合會便捷很多。另外一點，fp-tree要按支持度降序的順序的好處有幾點？前面說了可以提高共享前綴的可能，提高壓縮率，樹小了，遍歷的步數還能減小，尋找最優壓縮的順序是個NP難問題，因此選這個辦法能有個比較好的壓縮率足夠了。
fp-growth雖然號稱不產生候選集，但是實際上候選集產生已經在尋找條件子庫的時候隱隱產生了，剪掉非頻繁候選項的時候是通過建樹步驟中的第一小步完成的。
fp-growth在實現上也可以有很多技巧，比如尋找條件子樹的時候，同一條路徑會被遍歷很多次，如何有效避免（后來han自己提出，遇到掃把型的fp-tree，即上面是單路徑、下面分叉的，可以把單路徑所有的組合分別連接到下面的部分挖掘結果上輸出，那就不用遍歷上面的單路徑了）?另外樹上節點用什么數據結構保存指向子孫節點的指針，能同時兼顧查詢時間和空間？
最后我們總結一下apriori和fp-growth之間的聯系和差異。
初讀fp-growth算法，估計都感覺不到它和apriori有什么關系，但我個人猜測fp-growth是從apriori的統計候選集太耗時的那里?改良開始的，希望實現候選項集的更快速的計算支持度，最后就徹底的改變的搜索頻繁項集的方式。我覺得兩個算法的最根本的差異在于apriori是以搜索項集組合的空間作為基礎，通過數據庫來對照。而fp-growth是以數據庫為基礎，在里面尋找項集是否頻繁，表現為搜索方式一個是廣度優先一個是深度優先。。
apriori的那剪枝步和統計支持度在fp-growth上就是不斷的建fp-tree和遍歷。而前者的統計需要經過的IO，后者已經壓縮到內存了；但fp-growth不是在所有數據集上都比apriori強，比如在稀疏的數據集上，fp-tree每個節點可能包含非常多子孫，因此保存子孫節點的指針也是很大開銷，fp-tree本來就是通過壓縮使得數據集能被內存容納，結果導致最后fp-tree起不到壓縮效果適得其反。優化實現的apriori在稀疏數據集上也往往比fp-growth要快。
這里fp-growth在大部分地方是完勝了apriori，后面很多改進都是基于深度優先的思想，并且更注重實現上的技巧。現在我們也沒必要去費太多精力去改進這兩個算法了，因為頻繁項集挖掘是個組合爆炸的時間復雜度。在2003?2004年ICDM舉辦過兩個workshop就是專門比誰實現的頻繁項集挖掘最好（搜"FIMI?03"，網站里有很多的源碼）。在這里想多提一點，數據挖掘中，沒有算法能在所有數據集上PK掉其他算法。因此我們應該了解一種任務的多種算法，看看它們為什么和如何在不同的數據集上體現出自己的優勢，這樣，通過比較我們不僅能更好的理解和掌握它們的精華，更能在當我們遇到新的數據集的時候，選取合適算法甚至做出針對性的優化措施。
總結
以上是生活随笔為你收集整理的频繁项集挖掘之apriori和fp-growth的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 中文情感分析语料库
- 下一篇： 数据挖掘: 频繁项集挖掘(购物篮问题)