FP-growth算法(Frequent Pattern-growth)使用了一種緊縮的數據結構來存儲查找頻繁項集所需要的全部信息。
基本介紹
- 中文名：FP-tree
- 屬性：算法
- 全稱：頻繁模式樹
- 領域：計算機數據
FP-tree定義,FP-tree構造算法,FP-tree的相關的性質定理,
FP-tree定義
(1)頻繁模式樹(Frequent Pattern tree)簡稱為FP-tree，是滿足下列條件的一個樹結構：它由一個根節點(值為null)、項前綴子樹(作為子女)和一個頻繁項頭表組成。
(2)項前綴子樹中的每個結點包括三個域：item_name、count和node_link，其中：
item_name記錄結點表示的項的標識；count記錄到達該結點的子路徑的事務數；
node_link用於連線樹中相同標識的下一個結點，如果不存在相同標識下一個結點，則值為“null”。
(3)頻繁項頭表的表項包括一個頻繁項標識域：item_name和一個指向樹中具有該項標識的第一個頻繁項結點的頭指針：head of node_link。
對於包含在FP-tree中某個結點上的項α，將會有一個從根結點到達α的路徑，該路徑中不包含α所在結點的部分路徑稱為α的前綴子路徑(prefix subpath)，α稱為該路徑的後綴。在一個FP-tree中，有可能有多個包含α的結點存在，它們從頻繁項頭表中的α項出發，通過項頭表中的head of node_link和項前綴子樹中的node_link連線在一起。FP-tree中每個包含α的結點可以形成α的一個不同的前綴子路徑，所有的這些路徑組成α的條件模式基(conditional pattern base)。用α的條件模式基所構建的FP-tree稱為α的條件模式樹(conditional FP-tree)。
FP-tree構造算法
輸入：事務資料庫D和最小支持度閾值minσ。
輸出：D所對應的FP-tree。
方法：FP-tree是按以下步驟構造的：
(1)掃描事務庫D，獲得D中所包含的全部頻繁項集1F，及它們各自的支持度。對1F中的頻繁項按其支持度降序排序得到L。
(2)創建FP-tree的根結點T，以“null”標記。再次掃描事務庫。對於D中每個事務，將其中的頻繁項選出並按L中的次序排序。設排序後的頻繁項表為[p|P]，其中p是第一個頻繁項，而P是剩餘的頻繁項。調用insert_tree([p|P],T)。insert_tree([p|P],T)過程執行情況如下：如果T有子女N使N .item_name=p.item_name，則N的計數增加1；否則創建一個新結點N，將其計數設定為1，連結到它的父結點T，並且通過node_link將其連結到具有相同item_name的結點。如果P非空，遞歸地調用insert_tree(P，N)。FP-tree是一個高度壓縮的結構，它存儲了用於挖掘頻繁項集的全部信息。FP-tree所占用的記憶體空間與樹的深度和寬度成比例，樹的深度一般是單個事務中所含項目數量的最大值；樹的寬度是平均每層所含項目的數量。由於在事務處理中通常會存在著大量的共享頻繁項，所以樹的大小通常比原資料庫小很多。頻繁項集中的項以支持度降序排列，支持度越高的項與FP-tree的根距離越近，因此有更多的機會共享結點，這進一步保證了FP-tree的高度壓縮。
FP-tree的相關的性質定理
基於FP-tree挖掘頻繁閉項集,需要了解FP-tree如下性質和定理:
性質2.1(結點鏈性質)對於任何頻繁項ia，從FP-tree的頭表對應ia項的頭指針(headof node_link)開始，通過遍歷ia的結點鏈(node_link)可以挖掘出所有包含ia的頻繁模式。
性質2.2(前綴路徑性質)為了計算以ia為後綴的頻繁模式，僅僅需要在FP-tree中計算ia結點的前綴路徑，並且前綴路徑中每個結點的頻繁計數等於ia結點的頻繁計數。
定理2.3(分段增長)設α為事務資料庫D中的一個項集，B是α的條件模式基，而β是B中的一個項集，那么在D中α∪β的支持度等於B中β的支持度。
推論2.1(模式增長)設項α為事務數據D中的一個項集，B是α的條件模式基，13而β是B中的一個項集，那么α∪β為頻繁項集的充分必要條件是β也為頻繁項集。
定理2.4(單路徑頻繁項集產生)如果FP-treeT包含一條單路徑P，那么T包含的所有頻繁項集的集合可以通過枚舉路徑P中結點的所有可能組合得到，其支持度計數為組合中結點的支持度計數的最小值。
定理2.5給定一個事務資料庫D,最小支持度閾值minσ和頻繁項頭表=<……>nLi,i,,i12。挖掘頻繁閉項集的問題可以分解為n個子問題：第j(1≤j≤n)個子問題是找到所有包含ijn+1?但不包含i(n1jkn)k+?<≤的頻繁閉項集。
可以看出，後挖掘到的頻繁閉項集不可能包含先前找到的頻繁閉項集，但是它可能被已有的一個頻繁閉項集所包含，因此在挖掘過程中要對新挖掘的候選頻繁閉項集進行檢驗。如果剛得到的候選頻繁閉項集X不是已有的一個頻繁閉項集的子集或者兩者的支持度不同，那么就說X通過了FCI超集檢測，是一個頻繁閉項集。
定理2.6如果X是一個頻繁閉項集，那么在X的條件模式基中不存在任何一個項i出現在每一個事務中。
定理2.7如果Y是一個最大項集合(Y滿足：出現在X的條件模式基的每一個事務中，但Y的直接超集不滿足這一性質)，並且X∪Y通過了FCI超集檢測，那么X∪Y是一個頻繁閉項集。
定義2.5單路徑候選頻繁閉項集：設i是X的條件模式基中的一個頻繁項目，如果X的條件模式樹中只有一個結點N標記為i，並且N的所有祖先結點只有一個子女，N若滿足下列三個條件之一：
(1)N沒有子女。
(2)N有兩個以上的子女。
(3)N有一個子女，它的支持度計數小於N的。
那么單路徑候選頻繁閉項集就是X∪Z，Z包含N和N的祖先(除根結點)。如果條件模式X的條件FP-tree存在單路徑，在單路徑中提取候選頻繁閉項集的個數為單路徑中具有不等的頻度個數。
定理2.8對單路徑候選頻繁閉項集Y，如果Y通過了FCI超集檢測，則Y是一個頻繁閉項集。
定理2.9 X和Y是兩個頻繁項集且具有相同的支持度。如果X?Y且Y是閉項集，那么不存在只包含X不包含Y?X的頻繁閉項集。
