2004 年，A Javed 等人在文章《Frequent Pattern Mining on Message Passing Multiprocessor Systems》中提出了一種基於模式增長的分散式頻繁項集挖掘算法——PFP-tree 算法。PFP-tree 算法運用在訊息傳遞型多核處理器中。首先，各處理器分別處理本地的數據集，計算並得到局部的頻繁1-項集；接著，各處理器之間相互交換頻1-項集，生成全局的項頭表（header table）；然後，各處理器創建局部 FP-tree 並掃描項頭表，交換各自的局部條件模式基。最後，在得到全局的條件模式基後，生成條件 FP-tree 並運用 FP-growth 算法在條件 FP-tree上遞歸挖掘頻繁項集。
基本介紹
- 中文名：PFP-tree算法
- 外文名：PFP-tree algorithm
- 領域：數據挖掘
- 定義：分散式頻繁項集挖掘算法
- 機制：訊息傳遞機制
- 基本算法：FP-growth 算法
簡介,FP-growth 算法,TPFP-tree算法,訊息傳遞接口,
簡介
PFP-tree 算法是一種基於 MPI的挖掘算法，其中MPI 的全稱是 Message Passing Interface，它是一種訊息傳遞標準，同時也是一項被廣泛採用的並行編程技術。基於MPI 的頻繁項集挖掘算法都是一些並行算法，它們的特點是各個計算節點並行地挖掘頻繁項集，因此算法的效率很高。但是它們也有很多的缺點，比如：沒有容錯能力、節點之間需要進行大量的通信等等，這些缺點嚴重影響了算法的性能。PFP-tree 算法是基於訊息傳遞機制並行運行多個FP-growth算法。
FP-growth 算法
FP-growth算法是 Jiawei Han 等人在 2000 年提出的一種基於頻繁模式樹（Frequent Pattern tree，FP-tree）的頻繁項集挖掘算法，它通過遞歸地方式來構建條件 FP-tree，以及在條件FP-tree 上進行頻繁項集挖掘。FP-growth 採用了一種分治策略的思想，它將一個問題遞歸地轉化為若干個子問題。FP-tree 存儲了壓縮後的事務數據以及關於頻繁項集的關鍵信息，它是一種定義為如下的樹結構：
1）它包含了一個根節點，記為 null，一個項前綴子樹的集合作為根節點的孩子，以及一個頻繁項頭表；
2）項前綴子樹的每一個節點包含了三個域：item-name、count 和 node-link，其中 item-name 表示這個節點所代表的項，count 表示的是到達該節點的路徑的部分所表示的事務數目，而 node-link（虛線）則指向在 FP-tree 中具有相同item-name 的下一個節點，如果沒有下一個節點的話則為 null，實線表示的是父親節點和子節點之間的關係。
3）頻繁項頭表的每一條記錄都包含有兩個域：item-name 和 node-link（虛線）的起始位置，node-link 的起始位置記錄著 FP-tree 中具有相同項的連結所在的起始地址。
算法的整體思路是這樣的：首先，通過資料庫的一次掃描，計算並得到支持度大於等於最小支持度閾值ξ的頻繁 1-項集，並對頻繁 1-項集按照支持度的遞減順序排序放在項頭表（header table）中；接著，第二次掃描資料庫，構建 FP-tree：
對於資料庫中的每一條事務記錄 T，根據項頭表對 T 中的項按遞減順序排序並刪除不在項頭表中的項，之後按照構造 FP-tree 的方法將 T 插入 FP-tree 中並更新項頭表的節點連結，當資料庫掃描完成之後，FP-tree 也同時建立好了；
最後，在FP-tree 上進行頻繁項集挖掘：在項頭表（header table）中，從項頭表的下面往上開始，由長度為 1 的頻繁模式（即頻繁 1-項集，初始的後綴模式）開始，構造它的條件模式基。這些條件模式基可以看成是一個子事務資料庫，它是由 FP-tree中與後綴模式一起出現的前綴路徑集所組成。接著，算法開始構造這個初始後綴模式的條件 FP-tree，構造方式與構造 FP-tree 的方式一樣，然後遞歸地在該條件FP-tree 上實現挖掘，這個過程是一個遞歸挖掘的過程，模式的增長方式是通過將後綴模式與條件 FP-tree 產生的頻繁模式連線起來，從而實現模式的增長。
TPFP-tree算法
2008 年，J Zhou 等人在文章《Tidset-Based Parallel FP-tree Algorithm for the Frequent Pattern Mining Problem on PC Clusters》中提出了另一種並行挖掘頻繁項集的方法—TPFP-tree 算法。TPFP-tree 算法採用事務標識（Transaction identification set，Tidset）來構建TPFP-tree，即通過事務標識 Tidset 來直接選擇事務，而不是通過掃描資料庫。Tidset 是一個表結構，它記錄了所有事務的 ID，而每個事務包含了相關的數據項，所以 Tidset 所占用的記憶體基本上和計算節點的局部子資料庫一樣大。也正是因為如此，TPFP-tree 算法約束了目標資料庫的大小。
訊息傳遞接口
訊息傳遞接口（MPI）是一個跨語言的通訊協定，用於編寫並行計算機。支持點對點和廣播。或指基於訊息傳遞的一種並行編程規範和編程環境，實現並行執行的進程或執行緒之間的數據交換和同步。MPI是一個信息傳遞應用程式接口，包括協定和和語義說明，他們指明其如何在各種實現中發揮其特性。MPI的目標是高性能，大規模性，和可移植性。MPI在仍為高性能計算的主要模型。主要的MPI-1模型不包括共享記憶體概念，MPI-2隻有有限的分布共享記憶體概念。 但是MPI程式經常在共享記憶體的機器上運行。在MPI模型周邊設計程式比在NUMA架構下設計要好因為MPI鼓勵記憶體本地化。
