關聯規則如何并行實現呢？一個很直觀的想法是要么分數據要么分計算。本文要說的是分數據，想法來自mahout的fp-tree并行實現。其中分數據的博客已在前篇 mahout關聯規則FPGrowthDriver源碼分析之如何分數據 中說明，如何建樹可以在網上查找（這個相對來說比較簡單）或者直接看此片論文：《Mining FrequentPatterns without Candidate Generation》，這篇博客要說的是如何挖掘已經建好的FP-tree，也是參考《Mining FrequentPatterns without Candidate Generation》的（最好對照原篇來看，原篇為全英）。

先把建好的樹貼出來看：

挖掘的過程即為遍歷Header table中的每個item，然后重新構造事務集，以及相應的f-list，然后重新建樹的過程。下面就p和m項目進行演示：

查找項目p在fp-tree的鏈接可以找到兩條路徑：f,c,a,m:2; c,b:1 這里的次數以p的次數為準，比如f:4,c:3,a:3,m:2，因為后面的p:2，所以f,c,a,m:2；

則其事務集為{[f,c,a,m:2],[c,b:1]},其g-list為c:3;所以其建好的樹為：

由于上面的樹是單支（原文為：only onebranch），所以可以直接輸出模式cp：3。（此處默認的閾值為3）

對于項目m，其事務集為 {[f,c,a:2],[f,c,a,b:1]}，g-list: [f:3,c:3,a:3]，事務集根據g-list進行刪減項目得到新的事務集為{[f,c,a:2],[f,c,a:1]}，則由新的事務集和g-list構造的fp-tree為：

對上面的樹的挖掘和最開始的樹是一樣的，即分別對項目a、c、f進行挖掘。

1. 項目a：

輸出(am：3)模式同時調用"mine(f:3,c:3)|am" ,"mine(f:3,c:3)|am" 輸出（cam:3,fam:3）模式，以及調用"mine(f:3)|cam",這個調用輸出（fcam:3）模式 ；

2. 項目c：

輸出（cm：3）模式同時調用"mine(f:3)|cm"，"mine(f:3)|cm"輸出（fcm：3）

3. 項目f：

直接輸出模式（fm：3）

所以最原始的樹上面項目p生成的模式為：（cp：3），項目m生成的模式為：（am:3）(cam:3)（fam:3）（fcam:3）（cm:3）（fcm:3）（fm:3）。其他的項目按照上面同樣的規則進行生成頻繁項目集。

分享，快樂，成長

轉載請注明出處： http://blog.csdn.net/fansy1990

挖掘FP-Tree