關(guān)聯(lián)規(guī)則如何并行實(shí)現(xiàn)呢？一個(gè)很直觀的想法是要么分?jǐn)?shù)據(jù)要么分計(jì)算。本文要說(shuō)的是分?jǐn)?shù)據(jù)，想法來(lái)自mahout的fp-tree并行實(shí)現(xiàn)。其中分?jǐn)?shù)據(jù)的博客已在前篇 mahout關(guān)聯(lián)規(guī)則FPGrowthDriver源碼分析之如何分?jǐn)?shù)據(jù) 中說(shuō)明，如何建樹可以在網(wǎng)上查找（這個(gè)相對(duì)來(lái)說(shuō)比較簡(jiǎn)單）或者直接看此片論文：《Mining FrequentPatterns without Candidate Generation》，這篇博客要說(shuō)的是如何挖掘已經(jīng)建好的FP-tree，也是參考《Mining FrequentPatterns without Candidate Generation》的（最好對(duì)照原篇來(lái)看，原篇為全英）。

先把建好的樹貼出來(lái)看：

挖掘的過(guò)程即為遍歷Header table中的每個(gè)item，然后重新構(gòu)造事務(wù)集，以及相應(yīng)的f-list，然后重新建樹的過(guò)程。下面就p和m項(xiàng)目進(jìn)行演示：

查找項(xiàng)目p在fp-tree的鏈接可以找到兩條路徑：f,c,a,m:2; c,b:1 這里的次數(shù)以p的次數(shù)為準(zhǔn)，比如f:4,c:3,a:3,m:2，因?yàn)楹竺娴膒:2，所以f,c,a,m:2；

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

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

對(duì)于項(xiàng)目m，其事務(wù)集為 {[f,c,a:2],[f,c,a,b:1]}，g-list: [f:3,c:3,a:3]，事務(wù)集根據(jù)g-list進(jìn)行刪減項(xiàng)目得到新的事務(wù)集為{[f,c,a:2],[f,c,a:1]}，則由新的事務(wù)集和g-list構(gòu)造的fp-tree為：

對(duì)上面的樹的挖掘和最開始的樹是一樣的，即分別對(duì)項(xiàng)目a、c、f進(jìn)行挖掘。

1. 項(xiàng)目a：

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

2. 項(xiàng)目c：

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

3. 項(xiàng)目f：

直接輸出模式（fm：3）

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

分享，快樂(lè)，成長(zhǎng)

轉(zhuǎn)載請(qǐng)注明出處： http://blog.csdn.net/fansy1990

挖掘FP-Tree