« Social Graph 與 Semantic Web三言兩語(yǔ)：隱私問題與個(gè)性化服務(wù) »推薦系統(tǒng)：關(guān)聯(lián)規(guī)則(3) —— FP-Growth 算法
本文可以任意轉(zhuǎn)載，轉(zhuǎn)載時(shí)請(qǐng)務(wù)必以超鏈接形式標(biāo)明文章
原始出處 與
版權(quán)信息。
http://www.guwendong.cn/post/2008/fpgrowth_algorithm.htmlMonday, January 21, 2008 10:19:41 AM 發(fā)布:guwendong
在 1994 年
Rakesh Agrawal 提出了
Apriori 算法之后，關(guān)聯(lián)規(guī)則挖掘技術(shù)的可用性得到了很大的提高。而且因?yàn)殛P(guān)聯(lián)規(guī)則挖掘與生俱來(lái)的商業(yè)意義，使得它迅速成為了一個(gè)非常熱門的研究領(lǐng)域，新的算法也不斷地涌現(xiàn)出來(lái)。這其中，實(shí)用性比較強(qiáng)的一個(gè)算法，是由
韓家瑋教授提出的 FP-Growth 算法。FP-Growth 算法在 2000 年發(fā)表的這個(gè) paper 《
Mining Frequent Patterns without Candidate Generation》里有詳細(xì)的介紹。讀這篇 paper，我個(gè)人建議一定要同時(shí)把引文也都看一看，2000 年之前與關(guān)聯(lián)規(guī)則挖掘相關(guān)的重要 paper，基本上都在里面了。
FP-Growth 算法的核心是 FP-Tree（Frequent Pattern Tree，頻繁模式樹）的構(gòu)建，這個(gè)特殊的數(shù)據(jù)結(jié)構(gòu)，是 FP-Growth 算法與
Apriori 算法相比，性能顯著提高的原因所在。不過，仔細(xì)分析一下 FP-Tree 的實(shí)現(xiàn)，可以發(fā)現(xiàn)它與字符串處理算法中常用的
Prefix Tree 算法，有著異曲同工之妙。FP-Tree 通過合并一些重復(fù)路徑，實(shí)現(xiàn)了數(shù)據(jù)的壓縮，從而使得將頻繁項(xiàng)集加載到內(nèi)存中成為可能。之后以樹遍歷的操作，替代了
Apriori 算法中最耗費(fèi)時(shí)間的事務(wù)記錄遍歷，從而大大提高了運(yùn)算效率。詳細(xì)的理論講解可以閱讀上面的論文，我這里還是把其中的例子翻譯一下。
某數(shù)據(jù)庫(kù) DB 里有 5 條事務(wù)記錄，取最小支持度（min support threshold）為 3，則生成 FP-Tree 的過程如下：
1、掃描一遍數(shù)據(jù)庫(kù)，獲取所有頻繁項(xiàng)，刪除頻率小于最小支持度的項(xiàng)。在此操作的過程中，還可以得到每個(gè)項(xiàng)的出現(xiàn)頻率，供后續(xù)步驟使用。這一步完成之后，我們得到以下頻繁項(xiàng)， { (c:4), (f:4), (a:3), (b:3), (m:3), (p:3) }，“:”之后的數(shù)字表示對(duì)應(yīng)項(xiàng)的出現(xiàn)頻率。這個(gè)結(jié)果是排好順序的，首先按照頻率從達(dá)到小排序，再按照字母順序排序。需要注意的是這里的排序非常重要，之后每個(gè)事務(wù)中的項(xiàng)都要按照這個(gè)順序進(jìn)行排列，這個(gè)是有效合并重復(fù)路徑的前提。
處理之后的數(shù)據(jù)庫(kù)記錄為：
TID
原始事務(wù)數(shù)據(jù)
處理后數(shù)據(jù)
100
f, a, c, d, g, i, m, p
c, f, a, m, p
200
a, b, c, f, l, m, o
c, f, a, b, m
300
b, f, h, j, o
f, b
400
b, c, k, s, p
c, b, p
500
a, f, c, e, l, p, m, n
c, f, a, m, p
2、第二次掃描數(shù)據(jù)庫(kù)，在第一次處理完成的結(jié)果基礎(chǔ)上，構(gòu)建 FP-Tree。
1) 取出第一條事務(wù)數(shù)據(jù)，構(gòu)建 FP-Tree 的第一條路徑，{ c, f, a, m, p }。注意其中項(xiàng)的排序與第一步中得到的頻繁項(xiàng)集合的排序是一致的。
2) 取出第二條事務(wù)數(shù)據(jù)，{ c, f, a, b, m }，不難發(fā)現(xiàn)，它與第一條路徑共享了部分?jǐn)?shù)據(jù){ c, f, a }。因此，可以重復(fù)利用已有的路徑，只需要將其計(jì)數(shù)加 1，即{ (c:2), (f:2), (a:2) }。而對(duì)于后面不同的部分，我們創(chuàng)建新的路徑，{ (b:1), (m:1) }，其中，b 為 a 的子節(jié)點(diǎn)，m 為 b 的子節(jié)點(diǎn)。
3) 取出第三條事務(wù)數(shù)據(jù)，{ f, b }，發(fā)現(xiàn)沒有重復(fù)路徑存在。但 f 點(diǎn)是存在的，因此，可以重復(fù)利用 f 點(diǎn)，新建一個(gè) b 節(jié)點(diǎn)，作為 f 的子節(jié)點(diǎn)，得到路徑{ {f:3}, (b:1) }。注意，之前已經(jīng)存在的 b 節(jié)點(diǎn)無(wú)法重復(fù)使用，因?yàn)槠涓腹?jié)點(diǎn)為 a。
4) 取出第四條事務(wù)數(shù)據(jù)，{ c, b, p }，發(fā)現(xiàn)沒有重復(fù)路徑存在。因此，從現(xiàn)有 c 點(diǎn)出發(fā)，構(gòu)建一條新路徑{ (c:3), (b:1), (p:1) }。
5) 取出第五條事務(wù)數(shù)據(jù)，{ c, f, a, m, p }，同上原理構(gòu)建路徑，{ (c:4), (f:4), (a:3), (m:2), (p:2) }。
經(jīng)過兩遍數(shù)據(jù)庫(kù)掃描，完成了 FP-Tree 的構(gòu)建。在此例中，c 點(diǎn)為整個(gè) FP-Tree 的唯一根節(jié)點(diǎn)，但其實(shí)多數(shù)情況下，根節(jié)點(diǎn)并不是唯一的，即有多棵子樹。因此，為了方便樹結(jié)構(gòu)的遍歷，可以人為添加一個(gè)超級(jí)根節(jié)點(diǎn)，通常標(biāo)記為 root<null>。參照下圖，可以更清楚的理解整個(gè)過程。
得到了 FP-Tree 樹之后，再遍歷整棵樹獲取滿足一定置信度的關(guān)聯(lián)規(guī)則，就比較簡(jiǎn)單了。具體的理論證明，以及與
Apriori 算法的 performance 對(duì)比，論文里講得非常清楚，有興趣的朋友可以看一下。
關(guān)聯(lián)規(guī)則算法系列文章
1）
關(guān)聯(lián)規(guī)則介紹2）
Apriori 算法3）FP-Growth 算法，這篇文章和上一篇隔得時(shí)間有些長(zhǎng)了
預(yù)報(bào)：多層關(guān)聯(lián)規(guī)則，分布式關(guān)聯(lián)規(guī)則，關(guān)聯(lián)規(guī)則評(píng)價(jià)標(biāo)準(zhǔn)。
