fp演算法

⑴ 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的高度壓縮。