fptree演算法

1. FP-growth的演算法思想

基本舉鄭思路：不斷地迭代FP-tree 的構正鎮頌造和投影過程
演算法描述如下：
1、對於每個頻繁項，構造它的條件投影資料庫和投影FP-tree。
2、對每個新構建的FP-tree重復這個過旅桐程，直到構造的新FP-tree為空，或者只包含一條路徑。
3、當構造的FP-tree為空時，其前綴即為頻繁模式；當只包含一條路徑時，通過枚舉所有可能組合並與此樹的前綴連接即可得到頻繁模式。

2. 什麼是 fptree 演算法

FP—tree由標記為「null」的一個根節點(root)、作為根節點之子節點的項前綴子樹(item prefix subtrees)的集合、和—個頻陸缺繁項頭表(frequent item header table)所組成。
項前綴子樹中的每個節點包含3個域：item_name,count和node_link。item _name記錄了該節點所代表的項的名字。count記錄了所在路徑代表的事務中達到此節點的事務個數。 node_link指向下一個具有同樣的item_name域的節點，如果沒有這樣一個節點，則其值被置為null。
頻繁項頭表包含兩個域：Item_name和head of node_link. head of node_link指向FP—tree中具有相同Item_name的第一個節點。
根據FP_tree 的定義，我們得到FP_tree的構造方法
2 FP—tree的生成
FP—tree是通過兩次掃描事務集建立的.
(1)掃描陵瞎事務集D，獲得D中所包含的全部頻繁項集合F，及它們各自的支持度。對F中的頻繁項按其支持度降序排序,結果記為L；
(2)創建FP—tree的根節點T，以「null」標(3) 記；然後對D中的每個事務Trans進行如下操作：根據L中的順序，選出並排序Trans的頻繁項．設排序後的頻繁項表為[x|P]，其中x是第一個頻繁項。而P是剩餘的頻繁項:調用insert—tree([x|P]，T)：insert—tree([x|P]，T)過程執行情況如下：如果T有子女N並使得N.item_name=x.item_name，則N的計數增加1；否則創建一個新節點N，將其計數設置為1，鏈接到它的父節點T、、並且通過節點鏈結構將其鏈接到具有相同item_name的節點；如果P非空，遞歸地調用INSERT—tree(P，N)。在事務集再次掃描完畢時，一個完全的FP—tree就建成了。
3 頻繁模式的挖掘
FP—tree被建立後，頻繁模式是採用下面的FP—growth方法對FP—tree進行挖掘得到的. Procere FP_growth(Tree，α)／／tree為α的條件模式樹，α為後綴項(集)
{ if Tree 僅含一條路徑P then
for 路徑P中節點的每個組合(記作?) do
產生模式?Uα、並且把它的支持度supcoun指定為?中節點的最小支持度
else for 對Tree的頭表從表尾到表頭的每一個表項（記為α1）do {
產生一個模式?＝α1Uα，其支持度計數supcount=α1．supcount：
創建?的條件模式基，然後構造?的條件模式樹FP—tree? ；
if FP—tree ?= !Φ then 調用FP_growth(FP—tree?、?)}
從演算法2、3中，我們可以看出FP—growth挖掘過程是一種分而治之的過程。而且，即使資料庫可能產生指數級大量的頻繁模式，FP—tree的規模還是很小，不會呈指數級增長。例如，對於一個長度為100的頻繁模式「a1，…，a100」，FP—tree只會生成唯一一條長度為100的路徑，如「a1a2…a100」。而且，FP—growth演算法可以導出所有的大約1030個頻繁模式(如果時間允許的話)，如「a1, a2,..，a1a2，…，a1a2a3：，…，a1…a100」。
3.程序實現
程序在定義數據結構和實現演算法的時候主要考慮一下因素。
首先速度。速度問題在頻繁集產生的演算法中應該是比較重要的.因為它們常常涉及大量數據的處理.因此在程序中許多需要排序的數據結構都使用了平衡樹,這是一種高效的對全序元素的組織方式。
其次,空間。同樣因為要處理大量的數據,所以對內存的管理要尤其嚴格,如果出現內存泄漏將是很麻煩的事情。
第三，編程風格的考慮.要盡量採用通用化的代碼.因為對於一個比較大的系統來說，任何一個小的部分都應該清楚明白,便於別人閱讀和修改。
基於上面三點尺悉空，在對程序的數據結構的定義和演算法的實現的時候大量採用了C++的標准模板庫(STL,Standard Template Library).這是基於以下的事實,關聯規則的挖掘所涉及到的數據結構和基本演算法都是以往的常用數據結構和演算法,如向量類,集合類,快速排序演算法等.而STL正是包含了這樣許多通用的數據結構和基本演算法的庫。
例如,在STL中有一大類模板叫容器模板(container),簡單的說就是包含了許多元素的類的模板,象vector,array,set等就屬於容器模板.對於這些模板中的元素的訪問都可以通過它們的遍歷子,用完全一致的方式進行.請看下面兩段程序清單：
void print(FreqSet* pSet){
FreqSet_Iter fit;
for(fit=pSet->begin();fit!=pSet->end();fit++){
printf("%s %d \n",(*fit).second.name,(*fit).second.count);
}
}
void print(Table* pTable){
Table_Iter tit;

for(tit=pTable->begin();tit!=pTable->end();tit++){
printf("%s %d \n",(*tit).name,(*tit).count);
}
}
這兩個函數的作用是在調試的時候分別列印出頻繁集pSet和頭表pTable中的元素。
盡管pSet的類FreqSet是由map模板生成的,pTable的類Table是由multiset生成的,但對它們的元素的訪問形式幾乎一模一樣都是利用相應的遍歷子.涉及的函數名也很相似.其實,所有的容器模板都定義了函數begin()和end()代表元素列表的起始和結束.另外還有大量的具有相同名字和類似功能的函數,方便了我們對數據結構的管理。
在選擇資料庫訪問方式的時候,用了最近比較流行的ADO方式,它比ODBC更加靈活,速度也有改善.對網路資料庫的支持也很好。
對應於演算法描述中所出現的各個對象分別定義了一些數據結構，僅以trans為例說明
class Trans:public std::vector<Item>
{
public:
int TID;
Trans(){TID=0;};
Trans(int t){
TID=t;
}
bool operator==(const Trans& right);
bool operator<(const Trans& right);
}
typedef Trans::iterator Trans_Iter;
Trans類對應於交易對象(Transaction).對它的定義利用了STL中的vector模板,把它定義為一個以Item為元素的向量.把它定義為向量,是因為後來需要對其中的元素進行排序,向量可以使用快速排序。
這個Trans 類身肩兩任,它不僅代表事務對象,還在最後的結果輸出中還被用來存放頻繁集。
Trans_Iter是Trans類的遍歷子.在以後使用STL容器模板定義的類都會有一個與之相對應的遍歷子,不再贅述。
作者根據演算法用 Vsual C++編寫了程序，程序己在機器上調試通過（運行環境為： Windows Xp、Vsual C++ 6．0）．為節約篇幅，並且方便用戶閱讀，作者列出了部分關鍵程序清單
//根據條件模式庫來生成用於構建條件樹的頻繁項
void FPTree::BuildCPTree(long p_Frequnce)
{
std::vector<std::vector<associate> >::iterator it_CPBase=m_CPBase.begin();
std::vector<associate>::iterator it_vector,it_temp1;
std::map<std::string,int> Item_include;//包含非頻繁的項的集合
std::map<std::string,int>::iterator it_map,it_temp;
std::string l_string;
long Frequnce=p_Frequnce;
bool flag=true;
int l_test;
//統計每個項目的頻繁度
for (;it_CPBase!=m_CPBase.end();it_CPBase++)
{
it_vector=(*it_CPBase).begin();

while (it_vector!=(*it_CPBase).end())
{
l_string=(*it_vector).chr;
l_test=(*it_vector).num;

if (Item_include.count(l_string))
{
Item_include[l_string]+=(*it_vector).num;
l_test=Item_include[l_string];
}
else
Item_include[l_string]=(*it_vector).num;

it_vector++;
}
}
//除去map中的非頻繁項
bool flag1=true;
it_map=Item_include.begin();

while ((it_map!=Item_include.end())&& flag1)
{
l_string=it_map->first;
l_test=it_map->second;
if (it_map->second < Frequnce)
{
it_temp=it_map;
it_map++;
Item_include.erase(it_temp);

if (it_map==Item_include.end())
flag1=false; }
else
it_map++;
}
if (!Item_include.empty())
{

3. FP-growth演算法的 java 實現源碼

http://portal.acm.org/citation.cfm?id=1133907 這里有PDF下載 源代碼： http://www.programsalon.com/view/downloads36/sourcecode/math/112919/fpgrowth/fptree.cpp__.htm 或 http://www.programsalon.com/downloads67/sourcecode/math/detail243513.html

4. 模式挖掘（一）：頻繁項集挖掘演算法Apriori和FP Tree

Apriori是最常用的頻繁項集挖掘演算法，其計算邏輯簡單易於直觀理解。在實際應用中舉例，其易於從大量訂單數據中獲取頻繁出現的組合項集，以便於輸出計算單元之間的關聯度，從而給組套銷售、上架擺放等提供建議。下面介紹下工作中總結的知識，和需要避開的問題。

以訂單數據為例。在大量的訂單中，如何評價某一商品組合對的出現頻繁？其組合出現的次數多於其它組合嗎。若訂單覆蓋的商品品類豐富，那麼需求量不高的品類的組合便會被淹沒在快消品的組合里。所以在Apriori中有從三個不同的角度評價頻繁項集，描述元素關聯關系的指標：支持度、置信度、提升度。

在Apriori中有三個維度的頻繁項集的指標： 支持度 、 置信度 、 提升度 。下面以二元的組合舉例說明。
支持度：

置信度：

提升度：

5. 關聯分析的關聯分析的方法

Apriori演算法是挖掘產生布爾關聯規則所需頻繁項集的基本演算法，也是最著名的關聯規則挖掘演算法之一。Apriori演算法就是根據有關頻繁項集特性的先驗知識而命名的。它使用一種稱作逐層搜索的迭代方法，k—項集用於探索（k+1）—項集。首先，找出頻繁1—項集的集合．記做L1，L1用於找出頻繁2—項集的集合L2，再用於找出L3，如此下去，直到不能找到頻繁k—項集。找每個Lk需要掃描一次資料庫。
為提高按層次搜索並產生相應頻繁項集的處理效率，Apriori演算法利用了一個重要性質，並應用Apriori性質來幫助有效縮小頻繁項集的搜索空間。
Apriori性質：一個頻繁項集的任一子集也應該是頻繁項集。證明根據定義，若一個項集I不滿足最小支持度閾值min_sup，則I不是頻繁的，即P（I）<min_sup。若增加一個項A到項集I中，則結果新項集（I∪A）也不是頻繁的，在整個事務資料庫中所出現的次數也不可能多於原項集I出現的次數，因此P（I∪A）<min_sup，即（I∪A）也不是頻繁的。這樣就可以根據逆反公理很容易地確定Apriori性質成立。
針對Apriori演算法的不足，對其進行優化：
1）基於劃分的方法。該演算法先把資料庫從邏輯上分成幾個互不相交的塊，每次單獨考慮一個分塊並對它生成所有的頻繁項集，然後把產生的頻繁項集合並，用來生成所有可能的頻繁項集，最後計算這些項集的支持度。這里分塊的大小選擇要使得每個分塊可以被放入主存，每個階段只需被掃描一次。而演算法的正確性是由每一個可能的頻繁項集至少在某一個分塊中是頻繁項集保證的。
上面所討論的演算法是可以高度並行的。可以把每一分塊分別分配給某一個處理器生成頻繁項集。產生頻繁項集的每一個循環結束後．處理器之間進行通信來產生全局的候選是一項集。通常這里的通信過程是演算法執行時間的主要瓶頸。而另一方面，每個獨立的處理器生成頻繁項集的時間也是一個瓶頸。其他的方法還有在多處理器之間共享一個雜湊樹來產生頻繁項集，更多關於生成頻繁項集的並行化方法可以在其中找到。
2）基於Hash的方法。Park等人提出了一個高效地產生頻繁項集的基於雜湊（Hash）的演算法。通過實驗可以發現，尋找頻繁項集的主要計算是在生成頻繁2—項集Lk上，Park等就是利用這個性質引入雜湊技術來改進產生頻繁2—項集的方法。
3）基於采樣的方法。基於前一遍掃描得到的信息，對它詳細地做組合分析，可以得到一個改進的演算法，其基本思想是：先使用從資料庫中抽取出來的采樣得到一些在整個資料庫中可能成立的規則，然後對資料庫的剩餘部分驗證這個結果。這個演算法相當簡單並顯著地減少了FO代價，但是一個很大的缺點就是產生的結果不精確，即存在所謂的數據扭曲（Dataskew）。分布在同一頁面上的數據時常是高度相關的，不能表示整個資料庫中模式的分布，由此而導致的是采樣5%的交易數據所花費的代價同掃描一遍資料庫相近。
4）減少交易個數。減少用於未來掃描事務集的大小，基本原理就是當一個事務不包含長度為志的大項集時，則必然不包含長度為走k+1的大項集。從而可以將這些事務刪除，在下一遍掃描中就可以減少要進行掃描的事務集的個數。這就是AprioriTid的基本思想。 由於Apriori方法的固有缺陷．即使進行了優化，其效率也仍然不能令人滿意。2000年，Han Jiawei等人提出了基於頻繁模式樹（Frequent Pattern Tree，簡稱為FP-tree）的發現頻繁模式的演算法FP-growth。在FP-growth演算法中，通過兩次掃描事務資料庫，把每個事務所包含的頻繁項目按其支持度降序壓縮存儲到FP—tree中。在以後發現頻繁模式的過程中，不需要再掃描事務資料庫，而僅在FP-Tree中進行查找即可，並通過遞歸調用FP-growth的方法來直接產生頻繁模式，因此在整個發現過程中也不需產生候選模式。該演算法克服了Apriori演算法中存在的問顥．在執行效率上也明顯好於Apriori演算法。

6. FP-tree的演算法思想 舉例實現演算法

該演算法只進行2次資料庫掃描.它直接壓縮資料庫成一個頻繁模式樹,作後通過這課樹生成關聯規則.
演算法關鍵步驟螞指彎:第一步是逗碰利用事物資料庫中的數據構造FP-tree;第二悶悶步是從FP_tree中挖掘頻繁模式.