2.4.2　FP-growth算法

1994年，R.Agrawal和R.Srikant提出了Apriori算法。Apriori算法是一種在關系數據庫上頻繁進行項目集挖掘和關聯規(guī)則學習的算法。通過識別數據庫中頻繁出現的單個項目并將它們擴展到越來越大的項目集，可確定頻繁項目集。Apriori算法的目標是明確數據庫總體趨勢的關聯規(guī)則。Apriori算法的命名源于使用了頻繁項目集屬性的先驗知識，主要采用迭代方法或逐級搜索，通過k個頻繁項目集來查找k+1個項目集。為了提高生成頻繁項目集的效率，使用了一個稱為Apriori的重要屬性，該屬性有助于減少搜索空間。但Apriori算法存在一些實際問題，例如，在每個步驟中都必須構建候選集，為了構建候選集，Apriori算法必須重復掃描數據庫，這些問題不可避免地會使Apriori算法變慢。

為了克服這些冗余步驟，業(yè)界開發(fā)了一種新的頻繁項目集挖掘算法，稱為頻繁模式增長（FP-growth）算法。FP-growth算法是對Apriori算法的改進，FP-growth算法減少了對頻繁項目集的搜索，使用頻繁模式樹（Frequent Pattern Tree）或FP樹的形式來表示數據庫，這種樹結構能夠保持項目集之間的關聯。

FP-growth算法的步驟如下：

（1）掃描數據庫，以查找數據庫中出現的項目集。此步驟與Apriori算法的第一步相同，數據庫中每個項目集的計數稱為支持計數（Support Count）或1-項目集（1-itemset）頻率。例如，事務-項目清單列表如表2.5所示。

對于表2.5所示的項目集來說，計數的閾值為50%，即0.5×6=3，意味著最小的支持min_sup=3。計算每個項目集，可得到項目-計數列表，如表2.6所示。

按降序對項目集進行排序，可得到降序排列的項目-計數列表，如表2.7所示。

（2）創(chuàng)建FP樹，如圖2.12所示。

①創(chuàng)建樹的根，用Null表示。

②事務（Transaction）T1的第1次掃描：包含I1、I2、I3三個項，即計數為{I1:1}、{I2:1}、{I3:1}，其中I2作為子級連接到根，I1連接到I2，I3連接到I1。

③T2：包含I2、I3和I4，其中I2連接到根，I3連接到I2，I4連接到I3，此分支將共享T1中已使用的I2節(jié)點。

④I2的計數加1，I3作為子級連接到I2，I4作為子級連接到I3；計數為{I2:2}、{I3:1}、{I4:1}。

⑤T3：包括I4、I5，在創(chuàng)建子級時，具有I5的新分支連接到I4。

⑥T4：包括I1、I2、I4，順序為I2、I1、I4，I2已連接到根節(jié)點，因此將增加1；類似地，由于I1已與T1中的I2連接，因此I1將增加1，計數為{I2:3}、{I1:2}、{I4:1}。

⑦T5：包括I1、I2、I3、I5，順序為I2、I1、I3、I5，因此計數為{I2:4}、{I1:3}、{I3:2}、{I5:1}。

⑧T6：包括I1、I2、I3、I4，順序為I2、I1、I3、I4，因此計數為{I2:5}、{I1:4}、{I3:3}、{I4:1}。

（3）再次掃描數據庫并檢查事務。檢查第一個事務并找出其中的項目集，具有最大計數的項目集位于頂部，具有較小計數的項目集位于其次，依次類推。也就是說，FP樹的分支由事務項目集按計數的降序排列。

（4）檢查數據庫中的下一個事務。項目集按計數的降序排列，如果此事務的任何項目集已經存在于另一個分支中，則該事務分支將為根共享一個公共前綴（Common Prefix），也就是說，公共項目集在此事務中連接到另一個項目集的新節(jié)點。

（5）項目集的計數會隨著事務的發(fā)生而增加，在創(chuàng)建事務以及連接公共節(jié)點和新節(jié)點時，它們的數量都會增加1。

（6）挖掘創(chuàng)建的FP樹。檢查最低節(jié)點以及最低節(jié)點的連接，最低節(jié)點表示頻率模式長度1，由此，遍歷FP樹中的路徑，此路徑稱為條件模式庫。條件模式庫是一個子數據庫，由FP樹中帶有最低節(jié)點的前綴路徑組成。

（7）構造條件FP樹，該FP樹由路徑中的一組項目集形成；在條件FP樹中考慮滿足閾值支持的項目集。

（8）從條件FP樹生成頻繁模式，如表2.8所示。

總之，與Apriori算法相比，FP-growth算法的速度更快，并且對于挖掘長期和短期頻繁模式而言都是有效且可擴展的。FP-growth算法的缺點是它比Apriori算法更加煩瑣且難以構建，當數據庫很大時無法共享內存。