Apriori算法是一種最有影響的挖掘 0-1 布爾關(guān)聯(lián)規(guī)則頻繁項集的算法。這種算法利用了頻繁項集性質(zhì)的先驗知識（因此叫做priori）。Apriori使用了自底向上的實現(xiàn)方式（如果集合 I 不是頻繁項集，那么包含 I 的更大的集合也不可能是頻繁項集），k - 1 項集用于探索 k 項集。首先，找出頻繁 1 項集的集合($L_1$)，$L_1$用于找頻繁 2 項集的集合 $L_2$，而 $L_2$ 用于找 $L_3$，如此下去，直到不能找到滿足條件的頻繁 k 項集。搜索每個 $L_k$ 需要一次全表數(shù)據(jù)庫掃描。
我們假設(shè)一個很小的交易庫：{1,2,3,4}, {1,2}, {2,3,4}, {2,3}, {1,2,4}, {3,4}, {2,4}
首先我們先要計算發(fā)生頻數(shù)（或者叫做support）
| item | support | |
|---|---|---|
| {1} | 3| | |
| {2} | 6| | |
| {3} | 4| | |
| {4} | 5| |
1項集的最低頻數(shù)是3，我們姑且認(rèn)為他們都是頻繁的。因此我們找到1項集所有可能組合的pairs：
| item | support | |
|---|---|---|
| {1,2} | 3| | |
| {1,3} | 1| | |
| {1,4} | 2| | |
| {2,3} | 3| | |
| {2,4} | 4| | |
| {3,4} | 3| |
在這里，{1,3}, {1,4} 不滿足support大于3的設(shè)定（一般support是3/(3 + 6 + 4 + 5)），因此還剩下的頻繁項集是：
| item | support | |
|---|---|---|
| {1,2} | 3| | |
| {2,3} | 3| | |
| {2,4} | 4| | |
| {3,4} | 3| |
也就是說，包含{1,3}, {1,4}的項集也不可能是頻繁的，這兩條規(guī)則被prune掉了；只有{2,3,4} 是可能頻繁的，但它的頻數(shù)只有2，也不滿足support條件，因此迭代停止。
但我們可以想象，這種算法雖然比遍歷的方法要好很多，但其空間復(fù)雜度還是非常高的，尤其是 $L_1$ 比較大時，$L_2$ 的數(shù)量會暴增。而且每次Apriori都要全表掃描數(shù)據(jù)庫，開銷也非常大。
即便如此apriori算法在很多場景下也足夠用。在R語言中使用arules包來實現(xiàn)此算法（封裝的是C實現(xiàn)，速度很快噢）
前文提到了用apriori需要全表掃描，對于超大型數(shù)據(jù)會出現(xiàn)一些問題。如果有一種方法，可以不每次全表掃描，而是用一個簡潔的數(shù)據(jù)結(jié)構(gòu)（條件數(shù)據(jù)庫）把整個數(shù)據(jù)庫的信息都包含進(jìn)去，通過對數(shù)據(jù)結(jié)構(gòu)的遞歸就完成整個頻繁模式的挖掘，并保證最低的搜索消耗。這種方法就是FP growth算法。這個算法因為數(shù)據(jù)結(jié)構(gòu)的 size 遠(yuǎn)遠(yuǎn)小于原始的數(shù)據(jù)庫，所有的數(shù)據(jù)操作可以完全在內(nèi)存中計算，挖掘速度就可以大大提高。
FP growth 算法包含兩部分：存儲的FP tree 和對應(yīng)的FP 算法：
J. Han 對 FP-tree 的定義如下：
我們拿一個例子來說明問題。假如我們數(shù)據(jù)庫中記錄的交易信息如下（最低support為3）：
| No. | transactions | Sort | |
|---|---|---|---|
| 1 | ABDE | BEAD| | |
| 2 | BCE | BEC| | |
| 3 | ABDE | BEAD| | |
| 4 | ABCE | BEAC| | |
| 5 | ABCDE | BEACD| | |
| 6 | BCD | BCD| |
首先我們先要了解所有的一項集出現(xiàn)的頻率（support，重新排序的結(jié)果見上圖的Sort部分）：B(6), E(5), A(4), C(4), D(4)。
對于排序后的每條記錄的迭代后 FP-tree 結(jié)構(gòu)變化過程為（也就是一條一條計數(shù)的增加）：
也就是說，原始數(shù)據(jù)被壓縮到和最后那張圖一樣的結(jié)構(gòu)上。
接著是比較關(guān)鍵的 FP-tree 的挖掘，過程見下圖：
對于D這個節(jié)點來說，首先它的頻繁項集是 $D(4)$，它包含在三條鏈路里：
$ ( B(6),E(5),A(4) ), ( B(6),E(5),A(4),C(2) ), ( B(6),C(1) ) $
第一條鏈路里D有兩次出現(xiàn)，而其他兩個鏈路在D的條件下各出現(xiàn)了一次。因此我們說D有3個前綴路徑
$ (BEA:2),(BEAC:1),(BC:1) $
根據(jù)這個信息我們重構(gòu)D條件下的 FP-tee，則如下圖中 $Project:D(4)$ 的結(jié)構(gòu)。當(dāng)然還沒有完，還要繼續(xù)搜索可能的規(guī)則，因為我們的 support 為3，因此 $Project:D(4)$ 中，最末端的兩個 $C(1)$ 則應(yīng)該減枝掉。而A、E、B的頻數(shù)依然可以被使用，即 $DA(3)、DE(3)、DB(4)$。
對于C這個節(jié)點來說，同樣可以找到它的前綴路徑 $(BEA:2),(BE:1),(B:1)$，因此得到 $Project:C(4)$ 的結(jié)構(gòu)，A被減枝掉，則最后剩余了 $CE(3),CEB(3),CB(4)$。
再向上，找A節(jié)點；找E節(jié)點；找B節(jié)點；這樣一步一步搜索所有可能的結(jié)果。最終滿足support大于3條件的頻繁項集即為 $ DAE, DAEB, DAB, DEB, CE, CEB, CB, AE, AEB, AB, EB $
當(dāng)然，上面只是簡單的把 FP-tree 的原理說明了一下，里面的一些trick并沒有提及，感興趣的讀者可以找一找相關(guān)paper。
在R中沒有現(xiàn)成的包來做這個事情，但有意思的是arules包的作者也寫了 FP-tree 算法，只是沒有封裝而已。當(dāng)然只要有算法的C代碼，嵌入到R環(huán)境中也是不難的。
先到作者的主頁下載相關(guān)的 源代碼 ，我選擇是的fpgrowth.zip的C代碼編譯通過。
cd /home/liusizhe/download/fpgrowth/fpgrowth/src/makemake install./fpgrowth -m2 -n5 -s0.075 /home/liusizhe/experiment/census.dat frequent參數(shù)的話，可以直接參考fpgrowth的幫助，比如上面m對應(yīng)的是最小項集，n對應(yīng)的最大項集，s是support值
