[Rules Mining][P1] Frequent Pattern Mining

05-25

來自專欄美國天空的新月

最近在工作中遇到了跟Association Rule Mining有點關係的Project (Association rule learning)，補一下這方面的知識和上一篇文章（[ML System] MacroBase - 不僅告訴你出事了還告訴你為什麼的實時分析系統）的坑。

什麼是Association Rule Learning

這個是數據挖掘的經典問題。經典例子就是在零售業，我們如何發現類似於「買了牛油和麵包的顧客大部分會同時購買牛奶「這樣的Insights。對於基本概念的符號這裡不再贅述，大家可以點進去上面Wikipedia的鏈接看。基本上整個演算法會分成兩個步驟：

找到所有Support大於一定閾值，也就是在整個資料庫裡面出現得足夠頻繁的ItemSet（也叫Frequent Pattern, FP)。這步可以大大縮小下一步的搜索空間
根據上一步的結果進行對Frequent Pattern之間的關係進行挖掘

比如說有兩個FP, {Beer} 和 {Beer, Diaper} 以及對應的出現次數，我們就可以算出Association: Beer -> Diaper的Confidence。

目的就是找到Confidence最高的一系列的Associations。本文主要講第一步，Frequent Pattern Mining是怎麼實現的。

入門演算法：Apriori algorithm

這個演算法有很多變種，這裡只說最簡單的版本。基本思路是廣度優先搜索，也就是

先遍歷資料庫找到size為1的所有Frequent Pattern {A, B, C, D, E}，稱為L1
從 $L_{k-1}$ 得到 $L_{k}$ 的方法如下：

對於 $L_{k-1}$ 中的每個Pattern，加上一個之前的沒有的Item，經過一個快速的篩選，決定新Pattern是否進入 $Candidate_{k}$
對資料庫再次進行遍歷，選出 $Candidate_{k}$ 中出現頻率確實達到閾值的的Pattern，從而得到 $L_k$

這裡關鍵的Insight就是上面「快速的篩選」，這步可以大大縮小Candidate Set的大小。它採用的定理是：

$L_k$ 中的每個Pattern，其所有長度為k-1的subpattern必然在 $L_{k-1}$ 中

這個定理要證明很簡單。假如一個Pattern在 $L_k$ 中，那就證明它在整個資料庫中出現的頻率大於閾值。由於它的每個subpattern的出現次數肯定大於等於它自身的出現次數，也就是大於閾值，所以subpattern肯定也都是Frequent Pattern

我們來看一個例子。假如當前L2 = {AB, AC, BC, AD}, 現在要計算L3。首先給AB加一個C，得到ABC，然後發現ABC的三個size=2的subpattern：AB，AC，BC都在L2裡面，所以ABC可以進行Candidate Set；然後給AB加一個D，得到ABD，發現AB，AD在L2裡面，但是BD不在L2，也就證明ABD的出現次數 <= BD 的出現次數 < 我們要的閾值，所以肯定不可能在L3中。所以之後遍歷資料庫的時候，只需要計算ABC的出現次數即可。

進階演算法：FP-Growth Tree

這個演算法是2000年的時候發表的但現在貌似沿用至今https://www.cs.sfu.ca/~jpei/publications/sigmod00.pdf 證明是非常經典和優秀的演算法。

整個演算法分為兩個階段：

第一階段，把整個資料庫壓縮成一個（大多數情況下）更加compact的數據結構，稱為FP Tree (Frequent Pattern Tree)。儘管經過了壓縮，但是這個數據結構仍然包含找出所有Frequent Pattern所需的全部信息。為了方便理解，可以把這個聯想成跟索引功能類似的東西
第二階段，基於FP Tree遍歷找出所有FP

第一階段

我們先來看第一階段是怎麼壓縮資料庫的。這裡需要遍歷兩次資料庫：

第一次遍歷，找出所有單個Frequent Item，並且對其按照Frequency從高到低排序。根據前面Apriori演算法的基礎，我們知道所有的Frequent Pattern必定由這些Item組合產生。我們也基本上可以忽略其他所有的Item
第二次遍歷，對於資料庫里的每個數據點（方便起見我們稱為Transaction），只看它有哪些Frequent Item，並且按照第一步得到的順序，然後就得到了一個有序的列表。

例子如下圖

在第二次遍歷的時候，我們把每個數據點轉化成一個有序列表，然後就是把所有的列表用一個prefix tree組織起來。知道Tries Tree的同學應該到這裡就比較好理解，基本就把[f,c,a,m,p] 當作是"fcamp"作為一個字元串，然後插入樹中。不同的是，這個樹除了維護所有出現過的prefix之外，還維護了對應的出現次數。例子如下：

我們先看右邊，基本就是一個Tries Tree，外加每個節點帶上了對應的Frequency，這個Frequency留著後面計算Pattern Frequency的時候用。

還有一點不同的是上圖左邊的部分：對於每個Frequent Item，它會用一個鏈表把所有屬於同一個Item的樹節點串聯起來。這也是為了第二步遍歷方便，也不影響構造樹的時候的複雜度。

我們先暫定一下，看一下第一步給我們帶來了什麼：

整個資料庫肯定得到了壓縮。一方面，我們去掉了所有跟Frequent Item無關的item。另以方便，我們把每個Transaction用一個字元串表示起來，然後用prefix樹，相當於很多相關的信息merge起來了
在構造這個樹的過程中我們還順帶建立起了一個橫向的索引，而這個索引在第二步會使得計算變得非常方便

第二階段

這階段的演算法非常簡單：對於每個Frequent Item，我們遍歷它對應的橫向鏈表，找到FP Tree中這個Item對應的所有的Node，以及對應的樹的分支（稱為Path）。然後黑魔法就開始了。我們直接看圖：

我們現在正在找出以m結尾的Frequent Pattern（還記得我們之前按照Frequency對所有Frequent Item排序嗎）。流程如下：

根據橫向鏈表，找到兩個跟m相關的節點
對於第一個節點，我們看到m:2，這說明(f, c, a, m) 這個pattern出現的次數是2 。這裡注意即使f是4，c和a是3，但是因為m只有2，所以就證明這個4和3裡面多出來的部分是從其他地方來的，在這裡我們只考慮跟m:2相關的，所以我們不care。因此，看上圖右上角的部分，我們得到m的第一個Conditional Pattern Base 為 {f:2, c:2, a:2}。以此類推得到第二個為{f:1, c:1, a:1, b:1}
我們把第二步找到的Base也都Merge成樹狀結構，得到{f:3, c:3, a:3, b:1}
現在其實得到了一個有兩條路徑的subtree，所以recursively call本演算法

如果subtree只有一條路徑，沒有分支，比如{f:3, c:3, a:3}，那就直接算出所有組合即可

最後遞歸之後會得到"fm", "cm", "am", "fcm", "fam", "cam", "fcam" 都是滿足條件的Frequent Pattern

(其實文字描述很難描述清楚，維基百科上這個圖比較好理解https://upload.wikimedia.org/wikipedia/commons/e/e5/FPG_FIG_03.jpg ）

根據FP Tree的構造方式我們可以證明這個結果是正確的，證明就略過了。

跟A-priori相比，個人認為最大的優化在於第二步——由於經過了壓縮，橫向鏈表的遍歷所需次數肯定是少於原來資料庫的size的（當然worst case還是同一個數量級的，但是大多數情況下會少不少），遍歷完之後加起來，第三步又快速filter掉一波Candidate，最後第四步直接combination一跑（這個怎麼都跑不掉的）結果就出來了，省了很多無用的搜索。

再進一步：Large Scale FP-Growth

當數據量太大的時候，直接構造FP Tree內存會爆掉。在這個情況下可以考慮對數據進行Partition。

我們之前看到，FP-Growth的第二步是一個一個item來的，那麼由這個思路出發，我們就可以在針對某個Item進行計算的時候，只載入跟這個Item相關的 Transaction，構造一個FP-Tree計算，然後釋放掉內存，再對下一個Item重複同樣的操作。

同樣來看上面的例子：Frequent Item為{f, c, a, b, m, p} 按出現次數從多到少排序。

第一步：我們先載入所有包含p的Transaction，然後按照前面提到的演算法算一次。

第二步：我們把p從所有Transaction裡面刪掉，然後載入所有包含m的Transaction，構造Tree，算一次

第三步：把m都刪掉，然後算b，然後是a,c,f...

這裡的關鍵是要按照頻率從低到高的順序來。原因的話，是因為你如果回想前面FP-Growth的演算法，第二步在找Conditional Pattern Base的時候我們是看前綴而不看後面的。也就是說，如果我們先算m，刪掉m再算p的話，因為算p的時候其實是要考慮到m的，所以出來的結果就是不正確的了。

PS：另外一個應對數據太大問題的辦法就是用disk存儲FP-Tree，類似於B-tree。

有了FP-Growth基本就可以解決大多數Frequent Pattern Mining的問題了，在Spark裡面也有對應的實現可以直接用。下一篇文章會講Association Rule Mining 的第二步：有了Frequent Pattern之後怎麼發現Rule。