?? algorithm description
字號:
FP_growth算法描述:
FP_growth算法有兩個特點;一是將事務中的項集壓縮存儲到一棵樹上。二是在這棵樹上用遞歸的方法挖掘頻繁項集。
一、構造FPTree:
FPTree由ItemTb表和一棵Tree組成。ItemTb表中按項的支持度計數從大到小的順序將數據庫中所有的項進行排列。ItemTb
表包含三個數組一個是項的名稱item,一個是項的支持度計數count,一個是指向該項在樹中第一個結點的頭結點數組link。
Tree的結點結構較復雜
^
|
pa|rent child item count bnode
__|_____________________________________
|_______|____|___|_______|_______|______-|--> 兄弟結點
|
v
link next
____________ 描述孩子結點的下一個結點 __________
|__|___|____-|--------------------->|__|__|____|
| |
V V
孩子結點 孩子結點
parent指向父結點,child的link指向孩子結點,next指向描述下一個孩子的結點
bnode的作用是將樹中所有相同項的結點串起。
構造FPTree的過程是:
1、首先讀取數據庫中所有種類的項和這些項的支持度計數。存入到itTotal鏈表中。
2、將itTotal鏈表按照支持度計數從大到小排序
3、將itTotal鏈表插入到ItemTb表中
4、第二便讀取數據庫中的事務,將事務中的項按照支持度計數由大到小的順序插入到樹中。
5、遍歷樹,將屬于同一項的結點通過bnode指針連接起來。
本程序中,FP-tree中存儲了所有的項集,沒有考慮最小支持度。只是在FP-growth中挖掘頻繁項集時考慮最小支持度
二、FP_growth算法:
從一棵FPTree的ItemTb表中取得第一個項I1。如果該項的支持度計數滿足最小支持度計數{
1、把該項I1加入到存儲挖掘到的頻繁項集的數據結構ItemSet中
2、得到該項I1在目前FPTree中的條件模式基,即該項在樹中的結點的前綴路徑(路徑中不再包括該項)。
注意該項I1的條件模式基中各個項的支持度計數相等,等于該項I1的支持度計數
3、每條路徑看作一個事務,用這些路徑建造該項的條件FPTree,然后遞歸調用FP_growth算法。
在遞歸調用FP_growth算法時,那些大于支持度計數的項作為項I1的孩子結點存儲在ItemSet中。
}
繼續ItemTb表中滿足支持度計數的其他項 。
ItemSet中的存儲結果舉例:
I1 child
______ child _______
|__|__-|------>|___|___|
| |
next | next |
I2 V I3 V
_____ ________ child _______
|_____| |___|___-|------>|___|___|
| |
next | |
V I4 V
它表示I1是從最初的FPTree中得到的頻繁項,然后產生I1的條件FPTree fpt1后得到I3是該fpt1的頻繁項。
在fpt1上產生I3的條件FPTree fpt2得到I4是fpt2 的頻繁項。
I2是從最初FPTree中得到的第二個頻繁項。
因此得到的最大頻繁項集是{I1 I3 I4}和{I2}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -